# Merkle Proving Transaction Inclusion

> In case you aren't already familiar with Merkle proofs,  :newspaper: [this article](https://medium.com/@swastika0015/merkle-proofs-explained-208a72971a50) 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](https://medium.com/@swastika0015/merkle-proofs-explained-208a72971a50#c6a9). 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`.

<figure><img src="/files/4mk1mvjJIm8CyiYhi1b1" alt=""><figcaption></figcaption></figure>


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://docs.creditcoin.org/usc/creditcoin-oracle-subsystems/query-proof-and-verification/merkle-proving-transaction-inclusion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.