Merkle Proving Transaction Inclusion

The Creditcoin Decentralized Oracle uses merkle proving to determine whether a transaction is part of a given block. It is the second of two key proofs certifying 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.

When we conduct merkle proof verification in a STARK environment, it takes several minutes to compute a result. That's a few minutes during which users are waiting for bridging to complete. If we didn't use merkle proving, then STARK proving could take much longer (30 minutes vs 5).

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 usually provisions only certain fields from a transaction rather than the entirety of the transaction itself. This is done to save resources in a number of areas including STARK proof compute time and on-chain storage space for oracle results.

📝 Starknet Pederson Merkle Tree: The Creditcoin Decentralized Oracle uses a STARK friendly variant of merkle trees known as a Starknet Pederson Merkle Tree. This allows the prover to generate a STARK proof certifying that it conducted merkle proof verification truthfully for a given block and transaction.

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. This transaction is hashed along with other transaction in the same block to form a merkle node, with each merkle node being recursively hashed together until they form a single root hash.

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 prover generates this merkle proof and wraps it in a STARK proof so that we can easily verify the truthfulness of this computation.

Once the prover has generated a valid STARK proof for the inclusion of T1 in a specific block, we can finally retrieve the fields we want from T1.