Merkle Proving Transaction Inclusion

The Creditcoin Decentralized Oracle uses Merkle proving to determine whether a transaction is included in a given block. It is the second of two key proofs that certify oracle results.

In case you aren't already familiar with Merkle proofs, 📰 this article should give you a basic understanding of their use in the context of blockchain.

Motivation

When checking whether a transaction is part of a given block, we can either look through all the transactions in that block or use a Merkle proof. Blocks can contain a very large number of transactions, so checking them one by one until we find the transaction we are looking for is wildly inefficient! When verifying a Merkle proof we only need to access log₂(n) hashes in a block with n transactions. This would be about 20 hashes for 1,000,000 transactions! A big difference.

Key Terms:

📝 Merkle Tree: A balanced tree data structure of hashes used to efficiently verify the integrity of large sets of data. With the root of a Merkle tree and a small number of hashes from that tree, we can efficiently determine whether any given piece of data belongs to the set it describes. This property allows us to efficiently determine whether any transaction T is contained in a block B , where B might contain many such transactions.

📝 Root (Merkle Root): A Merkle root is the single cryptographic hash at the top of a Merkle tree, allowing us to rapidly verify the integrity of all the data stored in that tree.

📝 Field: In this context, a field is a part of a blockchain transaction. For example, a field could be the transaction status (success/failure) or the value field of a transfer event emitted by that transaction. The Creditcoin Decentralized Oracle extracts transaction data directly from verified transaction bytes.

📝 Standard Merkle Tree: The Creditcoin Decentralized Oracle uses standard Merkle trees (Keccak-256 hashing). Merkle proofs are verified natively by the precompile, providing fast and efficient verification without requiring specialized proof systems.

Merkle Proving Transaction Fields

In the example below, we show how fields containing the data we want are packed in transactions then hashed to form a Merkle tree. Transaction 1, as shown below, is an ERC20 transfer. This implies it has fields such as from, to, and value.

Other fields have been excluded from this diagram for simplicity's sake.

Note how the transaction fields we want to prove are all part of a single transaction, T1. Each transaction in the block is hashed to form a leaf node. These leaf nodes are then combined pairwise and hashed to form parent nodes, with this process continuing recursively until a single root hash is created.

Using the hashes of each sibling node along the path to T1 in combination with the Merkle root itself, we can prove that T1 was part of this specific block. This is known as a 📰 Merkle proof. The Proof Generation API generates this Merkle proof and submits it (along with continuity proof) for verification to the native precompile, which verifies it by reconstructing the path from transaction to root.

Once the precompile has verified the Merkle proof (confirming T1 is included in the block), the transaction data is immediately available. USC contracts can then decode the fields they need directly from T1.