Transaction Proofs Skiplist

Transaction 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

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 validate 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
  • Nest stage is find path to genesis
    • 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

Please note that algorithm above allows to build proofs from multiple blocks in one operation. For example, proof form blocks 3 and 5 will include (8, 6, 5, 4, 3, 2, 0)

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 {
  uint64 block_number = 1;
  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:

validateBlocksProofInLedger(blocksProof.GetPath())

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
}