Transaction Proofs Skiplist

Transaction and DB state proofs algorithm based on skiplist like chain

To prove that transaction with TxId is part of the ledger, first, we need to prove that transaction is part of block Merkle tree and second, we need to prove that block is part of ledger.

The first part is easy and described many times in blockchain-related literature:

• The transaction is part of block Merkle tree
• Merkle tree root is part of BlockHeader
• The proof is the path inside Merkle Tree (list of hashes) from transaction to tree root
  • This path starts with transaction hash, transaction sibling in tree hash, hash of sibling level above and so on, until root
  • For example, Tx3 proof composed of 4 hashes 15.., 78.., A2.., F5..
    • B3.. is root of the tree and thus not part of proof

Worth to mention that not only transactions Merkle tree stored in ledger, but world state trie root as well, as it described in Provenance document. Proof for specific state existence at block time done by providing path in Merkle-Particia trie from specific key->valie pair hash to root of trie stored in block header.

The second part is tricky one. The naive implementation is to return all blocks hashes from the genesis block to block we want to validate, given users already keep the genesis block locally. The size of proof is O(N), not acceptable for big ledgers.

Another option discussed in Transactions Proof page and require a dynamic Merkle Tree. The size of proof is O(log(N)), but it is computational or space inefficient.

Here we discuss third implementation, which provides proof of O(log(N)) size and computation and space-efficient.

If , block header, in addition to previous block hash, should contain hash of block, see example below:
Worth mentioning, that block with index will contain i hashes in its header.

Validation algorithm just finds the shortest path from last block in ledger to block i and from block i to the genesis block, returning BlockHeader for each block in the path.

• Let's mark blocks in the picture as 0,1,...,7,8
• To generate proof block 3
  • First we build path from last block to 3
    • Adding header of last block, 8
    • 8 has 4 hashes, one of them to block 4, so adding 4's header
    • 4 has access to 3, we will add 3's header as well, for consistency
  • Next stage is find path to genesis block
    • Block 3 contains only one hash, of block 2, so we add the header of block 2
    • Block 2 contains two hashes, block 1 and block 0, so we add block 0 hash
  • As result, we have (8, 4, 3, 2, 0)
  • Now lets reverse it, because it is easier to validate hashes for genesis block
• Validation of proof done by checking hash references in all blocks in path

Proof generation and validation algorithm

Proof generation:

• Zero step – user provided with receipt (block header) from another user who claim that some block is part of ledger
• First step – user requests header of last block in ledger, without discovering what block he wants to validate
  • User can store genesis block apriori or request it as well
• Second step – user requests the shortest path in skip list from block he validates to genesis block
• The third step – user requests the shortest path from last block (first step) to block he validates
• The forth step – user validates all apriori known headers - genesis, block, last - in both paths and concatenate both paths, result is block proof

Proof validation:

• For each block header in proof, starting from Genesis
  • Calculate block hash, by calculating block header hash
  • If calculated hash is in next block header hashes list, continue
  • If not, fail

Optimization - Because result of each call to Commit() is block header, user can use this header, only make sure that it has higher block number

Please note that algorithm above allows to build proofs from multiple blocks in one operation. For example, proof for blocks 3 and 5 will include (8, 6, 5, 4, 3, 2, 0). It is useful while validating specific value history.

From two algorithms above, we derive 2 types of proofs we need

• One to prove that transaction is part of blocks merkle tree
• Another is to prove that block(s) is/are part of ledger Full transaction proof structure will be as follows:

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

message BlockProof {
  repeated BlockHeader path = 2;
}

How to prove transaction existence

First we fetch transaction and validate its signature:

func validateTxSignature(txBytes, signature []byte) (bool, error) {
	verifier, err := ...
	if err != nil {
		return false, nil
	}
	err = verifier.Verify(txBytes, signature)
	if err != nil {
		return false, err
	}
	return true, nil
}

The next step is to validate transaction existence in block Merkel Tree

func validateTransactionProofInBlock(proof *types.TxProof, txBytes []byte) (bool, error){
	digest := sha256.New()
	_, err := digest.Write(txBytes)
	if err != nil {
		return false, err
	}
	currHash := digest.Sum(nil)
	for _, treeHash := range proof.GetPath() {
		currHash = CatHashes(currHash, treeHash)
	}
	return bytes.Equal(currHash, proof.Header.MerkleTreeRoot), nil
}

At last step, we validate hash path last block to block in question and from it to genesis in skip list:

func validateBlocksProofInLedger(path []*types.BlockHeader) (bool, error) {
	for i := 0; i < len(path) - 1; i++ {
		blockHash, err := calculateBlockHashFromHeader(path[i])
		if err != nil {
			return false, fmt.Errorf("can't calculate block hash: %v", err)
		}
		if !findHashInHeader(blockHash, path[i+1]) {
			return false, fmt.Errorf("hash not found: %v", err)
		}
	}
	return true, nil
}