Skip to content

Provenance

Jump to bottom
Gennady Laventman edited this page Nov 12, 2020 · 11 revisions

Provenance and Transactions Proofs

Provenance API give user access to

  • key->value history
  • block header data
  • transaction existence in block proof
  • block(s) existence in ledger proof
  • specific db key->value existence at specific (block) time proof
// Provenance access to historical data and data integrity proofs
type Provenance interface {
	// GetTxProof returns proof that tx with give id is part of blocks merkle tree (path to root)
	GetTxProof(txId []byte) (*types.TxProof, error)
	// GetBlocksProof returns proof that each block in list of blocks connected to another and to genesis
	// by providing shortest path in skip list between blocks in list
    // Please note that genesis block index (0) is not part of arguments - no need to pass same argument over nd over again
	GetBlocksProof(blocks []uint64, ledgerheight uint64) (*types.BlockProof, error)
	// GetHistory return full history for given key in db
	GetHistory(dbName, key string) (HistoryIterator, error)
	// GetTransaction returns transaction envelope by its id
	GetTransaction(txId []byte) (*types.TransactionEnvelope, error)
	// GetTransactionBlockHeader returns block header that contains transaction by txid
	GetTransactionBlockHeader(txId []byte) (*types.BlockHeader, error)
	// GetBlockHeader returns block header
	GetBlockHeader(number uint64) (*types.BlockHeader, error)
	// GetLstBlockHeader returns block header of last known block in ledger
	GetLastBlockHeader() (*types.BlockHeader, error)
	// GetStateProof returns merkle-patricia trie path to given state in given block
	GetStateProof(ledgerheight uint64, db, key string) ([][]byte, error)
}

type HistoryIterator interface {
	Next() (*api.HistoricalData, error)
	Close()
}

Based on this API, we can check

  • ledger integrity by accessing block headers and validating consistency of ledger merkle list
  • transaction existence proof composed of merkle tree path to transaction in block and block existence proof: GetTxProof() and GetBlocksProof()
  • block existence proof algorithm described in Transaction-Proofs-Skiplist, proof data accessed using GetBlockProof() API
  • proof of active and past states can be done by GetStateProof() proving existence of all state changes
    • retrieve key->value history by using GetHistory() API and provide proofs for all transaction references returned
      • referenced blocks existence proof in this case can be done by single call to GetBlockProof() with (genesis, history referenced blocks, last block) argument

Block header data

Block header contains all data required to prove existence of transaction or/and specific state at block time

  • Block number
  • List of hashes (pointers) in ledger skip list
  • Block time
  • Two merkle tree roots
    • Transactions merkle tree root
    • DB state merkle-patricia tree root - ethereum style
// BlockHeaderBase holds the block metadata and the chain information
// that computed before transaction validation
message BlockHeaderBase {
  uint64 number = 1;
  // Hash of (number - 1) BlockHeaderBase
  bytes previous_base_header_hash = 2;
  // Root of Merkle tree that contains all transactions, without validation data
  bytes tx_merkel_tree_root_hash = 3;
  // Hash of BlockHeader of last block already committed to ledger
  bytes last_committed_block_hash = 4;
  // Number of last block already committed to ledger
  uint64 last_committed_block_num = 5;
}

// BlockHeader holds, in addition to base header, extra block metadata and the chain information
// that computed after transactions validation
message BlockHeader {
  BlockHeaderBase base_header = 1;
  // Skip chain hashed, based of BlockHeader hashed of blocks connected in blocks skip list
  repeated bytes skipchain_hashes = 2;
  // Root hash of system wide state merkle-particia tree
  bytes state_merkel_tree_root_hash = 3;
  // Validation info for transactions in block.
  repeated ValidationInfo validation_info = 4;
}

Detailed proofs

Block X proof contains connected list of blocks from the latest ledger block to block X and from the block X to genesis

message BlockProof {
  uint64 block_number = 1;
  repeated BlockHeader path = 2;
}

Transaction contains block header and path in merkle tree in the block to tree root

message TxProof {
  BlockHeader header = 1;
  repeated bytes path = 2;
}

State proof block header and path in merkle-patricia tree in the block to tree root

message StateProof {
  BlockHeader header = 1;
  repeated Node path = 2;
}

Detailed explanation for transaction existence proof, based on data stored during tx commit

  • During transaction commit, block header returned as proof
  • At some point in future we need to prove that tx is part of ledger, using proof stored since tx commit
    • First, we receive last block header by calling GetLastBlock()
    • Genesis block was stored by user apriori
    • We call GetBlockProof(genesis, blockX, lastBlock) and validate proof by validating blocks pointers
    • Second, we call GetTxProof() for tx path in the block merkle tree and GetTransaction() for tx content
    • We validate proof using tx hash and merkle root stored in block header

Detailed explanation of existence of specific value at specific time explained in certificate management use case. Value change in block X proof explained in asset transfer use case.

To check whole history of specific key in database, we use GetHistory API who provides all values of specific keys over time, including references to transactions that change this key. It is possible form this data, using GetTxProof, GetBlockProof and GetTransactions API, to provide proof of change of specific key at specific time in specific transaction. Instead using GetTxProof and GetTransaction, we can use GetStateProof, just to prove state changes in blocks.

Worth to note that GetTxProof and GetTransaction provides addition transaction authenticity proof based on transaction signature, but not always can be used due ALC restrictions.

Access to Provenance API

As we can see here, the API is Blockchain DB installation level API, not single DB level API and it exposed by DBConnector, but this need to be discussed.

// DBConnector handle connectivity between sdk and Blockchain Database cluster
type DBConnector interface {
	...
	// GetProvenance returns blockchain db provenance interface
	GetProvenance() Provenance
}

Historical data

As mentioned in Transaction document, during provenance data creation phase, {Key, newValue, BlockTime, BlockNumber, TxTime, TxId, ClientId, IsDelete, IsOk} tuple stored as provenance data for each key in WSet.

GetHistory returns slice of history values based on data stored in provenance tuple

message HistoricalValue {
  // DB key
  string key = 1;
  // Historical value
  bytes value = 2;
  // Sequencer time when block was created
  google.protobuf.Timestamp blocktime = 3;
  // Transaction that did the change
  bytes txId = 4;
  // Block number that holds changing tx
  uint64 blocknumber = 5;
  // Is this tx deleted this key
  bool isDelete = 6;
}

World state - Patricia Merkle Trie

As mentioned earlier, in addition to block existence proofs and transaction existence proofs, we need to prove db state at the specific time (block). For that we will build ethereum inspired Patricia-Merkle trie for all key->value pairs that exist - db state tree.

This tree is an optimized dictionary (radix) tree, that use hexadecimal key representation as path in tree. Ethereum world state trie

Worth to mention that this tree should provide time travelling and only part of tree related to keys in tx wset actually stored with block, and the data in the old block can still be accessed normally. PatriciaMerkleTrie

Use cases - Asset transfer

User wants to know whole asset history, specially asset transfers.

Asset stored as data entity assetId->asset in database, one of its fields is asset owner

To prove specific asset transfer took place between A and B, user should prove that in block X asset owner field had value A and in block X + 1 it had value B.

Proof itself composed of blocks X and X + 1 headers.

  • To get the proof
    • User get whole asset history using GetHistory()
    • Block with required asset transfer tx located - transaction that changes owner field to B
    • User gets Block header for this block and previous one using GetBlockHeader()
  • To validate the proof
    • The proof of blocks X and X+1 existence generated bt single call to GetBlockProof()
    • The proof of new state (owner=B) for the specific asset generated using GetStateProof()
    • Proof of previous state generated by using GetStateProof() with the previous block and owner (owner=A)
    • State proofs validated using path validation, block proof validation described in Transaction-Proofs-Skiplist

Use cases - certificates management

User wants to provide proof he had specific certificate at specific time.

To prove existence of specific certificate at specific time, user has to locate ledger block (X) with the biggest time of all blocks with time smaller of specific time. This will provide proof of certificate existence at block time.

To validate the proof:

  • Proof of block X existence generated using GetBlockProof()
  • Proof of certificate issuing generated using GetStateProof()
  • State proofs validated using path validation, block proof validation described in Transaction-Proofs-Skiplist

If we generate proofs for latest block, for example, we can validate certificate validity until now

Access to provenance data

For now, we go with the simplest approach - if user now have read access to given key, it can access its historical data as well, even if it didn't has access to this key in the past.

Transaction time

To eliminate difference between client clocks, Transaction time set to be equal to block time. We need to add time to block header.

Trust assumption

  • Servers contain correct, non altered ledger.
  • No malicious servers, i.e. each server returns "honest" response for any claim
    • Is block part of ledger? Block header is a claim.
    • Is tx part of block? Block header and full tx content is a claim.
    • Is particular state exist at a block X?
  • There is possibility of MiTM attack, although I can't think about any scenario that server signed time anchored response can be pre-collected and used for attack
  • There are two different approach how server validate claims:
    • Server response can replay with full proof, QLDB/Bitcoin/whatever ledger you want style and user validate this proof using its knowledge about system internals - Merkle trees, Radix trees, Skip lists, etc
    • Response contains claim itself, time anchor in way of the latest ledger block and just simple "yes/no" answer

REST API

This is smaller REST API that should be exposed from server to SDK in order to implement API discussed above.

History API

We support getting history with pagination, based on last returned an item index and page size

GET /history/{key}?index={skipIndex}&pageSize={size}

Raw ledger data API

It is more or less same API as exposed to used

GET /ledger/tx/{txId}
GET /ledger/block/{blockId}
GET /ledger/height
GET /ledger/blockByTx/{txId}

Proofs API

I am not sure how to implement blocks proof request, that may contain

GET /proof/block/ (????)
GET /proof/tx/{txId}
GET /proof/state/{height}/{db}/{key}

Topics to discuss

  • Because of ALC restrictions, specific user can be allowed to see only some parts of transaction RSet and WSet
    • Is it possible to arrange tx rset and wset entries in merkle tree like structure, to prove existing of specific RW entity without reviling all tx?
  • Do we need raw tx access/proof API at all?
  • As proof, do we want a server to return only signed "yes/no" answer of whole proof(?) and leave to user to validate it?
  • How to implement GetBlocksProof() for multiple blocks with REST API?
Clone this wiki locally