Transaction Proofs

Proof generation algorithm

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.

The data in tuple used to create cryptographic proof:

TxId used to validate that transaction is part of block identified by BlockNumber
- We assume that transactions stored in block as Merkle Tree and based on this is easy to generate cryptographic proof transaction with current TxId is part of block
  - For example, to prove that Tx3 is part of block Merkle tree with root B3.. , we need Tx3, its hash – 15.. and 78.. (hash of sibling transaction), A2.. (sibling in Merkle tree), F5.. (sibling in Merkle tree).
In addition, like QLDB, we will build a continuously updating Merkle tree of ledger blocks
- This tree will be used to generate proof that block is part of ledger
- To provide proof that block with Merkle root B3.. is part of ledger, we provide: 33.. (previous block hash), C3.. (next block hash), 15.. (sibling in Merkle tree), 76.. (sibling in Merkle tree) – more or less same procedure as proof for Tx in block
- Please note, that as part of proof request, ledger height at a time provided, so some parts of merkle tree require recalculation, to be relevant to given ledger height.
So, at the end, as proof, we provide Tx hash, siblings in block Merkle tree until root, prev block hash, next block hash, siblings in ledger Merkle tree until root
- For all entities with signatures, like Tx, Block, we will provide signatures as well
If we want to store more that one Merkle tree inside block, for example, to store all state changes in block, it is really simple to provide proofs for leaf in any of Merkle trees
- Lets mark root of Tx Merkle tree as TxTreeRoot and root of state changes Merkle tree as StateTreeRoot
- We store hash of TxTreeRoot||StateTreeRoot in block header, along/instead of TxTreeRoot and StateTreeRoot. Lets call it as MergedTreeRoot. This way we merged both Merkle trees
  - This way we can add any numbers of Merkle trees inside block, if we need
- To calculate block hash, we use PrevBlockHash||MergedTreeRoot
- To provide proof for transaction, we add StateTreeRoot in list of provided hashes before PrevBlockHash, to calculate MergedTreeRoot
- To provide proof for state change, we add TxTreeRoot in list of provided hashes before PrevBlockHash, to calculate MergedTreeRoot

Final remark - because we need ledger Merkle tree root for validations, we can return it, along with ledger height, as response to commit

For Merkle tree example API Merkle Tree Builder

Example how to validate all changes to marble

Based on Marbles example

For proof and provenance APIs, see Client API document

func (t *Marbles) checkOwnershipChange(key string) error {
	start := time.Date(0,0,0,0,0,0,0, time.Now().Location())
	end := time.Now()
	iter, _ := t.db.GetHistoricalIterator(key, start, end)

	merkleRoot, ledgerHeight, _ := t.db.GetMerkleRoot()

	for iter.Next() {
		tx, _ := t.db.GetTx(iter.Value().txId)
		hashes, txSignatures, _, _ := t.db.GetTxProof(tx.GetTxId(), ledgerHeight)
		if len(txSignatures) != 1 {
			return fmt.Errorf("Wrong tx signatures number")
		}

		if ValidateTransaction(tx, txSignatures[0], iter.Value().key, iter.Value().value) != nil {
			return fmt.Errorf("Wrong tx")
		}

		currHash := GetTxHash(tx)

		for _, hash := range hashes {
			currHash = CatHashes(currHash, hash)
		}

		if bytes.Compare(merkleRoot, currHash) != 0 {
			return fmt.Errorf("Validation fails, no matched Merkle tree root")
		}

		marble := marble{}
		json.Unmarshal(iter.Value().value, &marble) //unmarshal it aka JSON.parse()
		fmt.Printf("Marble owner change %s at %s was validated", marble.Owner, iter.Value().txTime.String())

	}
	return nil
}

// Function that should validate transaction integrity - signature, it contains WSet that writes given value to given key
func ValidateTransaction(tx Transaction, sig Signature, key string, value []byte) error {
	if bytes.Compare(tx.GetSignature(), sig) != 0 {
		return fmt.Errorf("Signature validation failed")
	}
	if bytes.Compare(tx.GetWSet().GetKeyValue(key), value) != 0 {
		return fmt.Errorf("WSet validation failed")
	}
	return nil
}

Explanation

Lets see how thing executed

First, we query DB for all changes that happens to key - t.db.GetHistoricalIterator(key, start, end)
Second, we ask DB for current Merkle Tree Root and current Ledger Height - merkleRoot, ledgerHeight, _ := t.db.GetMerkleRoot()
Third, we pass over all changes that happens to value associated with key and provide proof this change really exist in ledger - for iter.Next() {...}
- We pull transaction by txId stored in provenance data - tx, _ := t.db.GetTx(iter.Value().txId)
- We ask DB to provide hashes and signatures to check tx legitimacy
  - Please notice that we asked DB for Merkle Tree Root before we decide what transaction we plan to check, so it can't be altered
- We validate that transaction contains WSet that actually change value associated with key if what returned by provenance query and that transaction signature is correct - ValidateTransaction(tx, txSignatures[0], iter.Value().key, iter.Value().value)
- We check hashes all the way to root
```
currHash := GetTxHash(tx)
for _, hash := range hashes {
    currHash = CatHashes(currHash, hash)
}
if bytes.Compare(merkleRoot, currHash) != 0 {
// Validation fails
}
```
- For example, if we use tree from pic below and want to validate Tx3, hashes list should contain following hashes {78.., A2.., F5.., 33.., C3.., 15.., 76..}, to finish calculation with correct Merkle Root C5..

Ledger Merkle tree

Basic Merkle Tree API

// Tree defines basic merkle tree API
// Leaf in tree are bytes array and serialization/deserialization is out of scope
type Tree interface {
	// Add single leaf to tree, usually used by dynamic (growing over time) tree
	Add(leaf []byte) ([]byte, error)
	// Build full tree from list of leaves, usually used for static tree, when all nodes already exist
	Build(leafs [][]byte) ([]byte, error)
	// GetSize returns current tree size
	GetSize() uint64
	// GetRoot return tree root hash for given tree size, then size is lower or equals to result of GetSize
	// for any size that lower then GetSize, we need to do root recalculations
	GetRoot(size uint64) ([]byte, error)
	// GetLeaf return leaf with given index
	GetLeaf(index uint64) ([]byte, error)
	// GetAllLeaves returns all leaves in tree
	GetAllLeaves() [][]byte
	// GetProof return list of hashes (correct for given tree size) that represent path from leaf to tree root
	// First Hash in list is leaf hash, last hash in list is tree root
	GetProof(size, index uint64) ([]byte, error)
}

Actually, time tree size means number of leaves in tree.

Proof API exposed to user by SDK

As explained above, blockchain db contains two level of Merkle Trees - one stayic at block level and one dynamic tree of blocks First, each commit to db returns Digest, contains current root of bocks tree and legder height, which is equals to tree size

message Digest {
  // Ledger merkle tree root
  bytes root_hash = 1;
  // Ledger height
  uint64 height = 2;
}

Upon proof request for transaction from user, transaction proof message returned

message Proof {
  BlockHeader header = 1;
  repeated bytes block_proof = 2;
  repeated bytes ledger_proof = 3;
}

It used in Provenance API:

// Provenance access to historical data and data integrity proofs
type Provenance interface {
	// GetMerkleRoot returns the current block merkle root hash and the last committed
	// block number
	GetMerkleRoot() (*types.Digest, error)
	// GetProof returns two paths imn Merkle tree - one for transaction in block and one for block in ledger
	GetProof(txId []byte, height uint64) (*types.Proof, error)
	// GetHistory return full history for given key in db
	GetHistory(dbName, key string) ([]*types.HistoricalValue, error)
	// GetTransaction returns transaction envelope by its id
	GetTransaction(txId []byte) (*types.TransactionEnvelope, error)
}

Provide feedback

Saved searches