# Merkle Proving Transaction Inclusion

{% hint style="danger" %}
**Outdated Documentation:** This page covers the architecture used for USC V1, which was deprecated on 2026-03-30. For the latest documentation, please visit: [usc documentation](https://docs.creditcoin.org/usc)
{% endhint %}

> 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.

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 :newspaper: [merkle proof](https://medium.com/@swastika0015/merkle-proofs-explained-208a72971a50#c6a9). 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`.

<figure><img src="/files/VltJKMufPZfUypi0uOBD" 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/usc-v1/creditcoin-oracle-subsystems/proving/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.