Transaction Proofs Skiplist

Transaction proofs algorithm based on skiplist like chain

To prove that transaction with TxId is part of 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.

First part is easy and described many times in blockchain related literature:

• Transaction is part of block Merkle tree
• Merkle tree root is part of BlockHeader
• Proof is 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 tree and thus not part of proof

Second part is tricky one. Naive implementation is to return all blocks hashes from genesis block to block we want to validate, given user already keep genesis block locally. Size of proof is O(N), not acceptable for big ledgers.

Another option discussed in Transactions Proof page and require dynamic Merkle tree. Size of proof is O(log(N)), but it computational or space ineffective.

Here we discuss third implementation, that provides proof of O(log(N)) size and computation and space effective.

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

• Let's mark blocks in picture as 0,1,2,3,4
• To validate block 3
  • Block 3 contains only one hash, of block 2, so we add block 2 header to proof.
  • Block 2 contains two hashes, block 1 and block 0, so we add block 0 hash
  • We done because block 0 is 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 fatch 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
}

Next step is to validate transaction existence in block merkle 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
}