Provenance

Provenance and Transactions Proofs

Provenance API give user access to

• key->value history
• raw transaction data (????)
• block header data
• transaction existence in block proof
• block(s) existence in ledger proof
• specific db ley->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
	// by providing shortest path in skip list between blocks in list
	GetBlocksProof(blocks []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(size uint64, db, key string, value []byte) ([][]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

// BlockHeader holds the block metadata and the chain information
message BlockHeader {
  uint64 number = 1;
  // Hash of previous block and rest of skip list hashes - staring from previous block
  repeated bytes previous_block_header_hash = 2;
  bytes transactions_hash = 3;
  google.protobuf.Timestamp blocktime = 4;
  // Transactions merkle tree root
  bytes merkle_tree_root = 5;
  // Whole db state merkle-patricia trie root
  bytes db_state_root = 6;
}

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 and state proof contains block header and path in merkle tree/merkle-patricia tree in the block to tree root

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

message StateProof {
  BlockHeader header = 1;
  repeated bytes 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 binary key representation as path in tree

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.

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.