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 block i to the genesis block, returning BlockHeader for each block in the path.

• Let's mark blocks in the picture as 0,1,2,3,4
• To validate block 3
  • Block 3 contains only one hash, of block 2, so we add the header of block 2 to proof.
  • Block 2 contains two hashes, block 1 and block 0, so we add block 0 hash
  • We done because block 0 is the genesis block

Full transaction proof structure will be as follows:

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

How to prove transaction existence

After accepting types.Proof, 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.Proof, 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.GetBlockProof() {
		currHash = CatHashes(currHash, treeHash)
	}
	return bytes.Equal(currHash, proof.Header.MerkleTreeRoot), nil
}

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

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