# Overview (https://docs-kyrm16yq7-ton-core-docs.vercel.app/llms/foundations/proofs/overview/content.md)



A **proof** is a tree-based structure that contains the necessary data and can be verified by a proof requester.
To prove something means to construct such a structure. The exact structure may differ depending on the use case. For example, suppose a proof is to be validated off-chain and requires multiple cell trees; the native TON approach is to construct a Bag of Cells (BoC) containing all the necessary cells. This is precisely what a liteserver does when data is requested from the blockchain.

<Callout>
  It is highly recommended to familiarize yourself with [Exotic cells](/llms/foundations/serialization/merkle/content.md) first. This article primarily covers situations where you want to verify a proof in a smart contract. However, the same techniques can be used to validate proofs off-chain.
</Callout>

There are several key points to consider when proving anything on-chain.

* The only trusted information available in a smart contract is a few recent masterchain blocks.
* Some data is stored directly within **blocks**.
* Additional information is maintained within the workchain **state**.
* **Blocks** serve as diffs that reflect changes to the **state** over time. Think of **blocks** as Git commits and the **state** as your repository.
* Latest TL-B schemas can be found in the [TON Monorepo](https://github.com/ton-blockchain/ton/blob/master/crypto/block/block.tlb). They may evolve, typically in backward-compatible ways.

## More about blocks [#more-about-blocks]

We need to examine the block layout to determine what we can prove and how to do it.

Each block (shardchain block, masterchain block) has a unique block ID:

```tlb
block_id_ext$_ shard_id:ShardIdent seq_no:uint32
  root_hash:bits256 file_hash:bits256 = BlockIdExt;
```

* `ShardIdent` contains information about the workchain and the shard the block belongs to.
* `seq_no` is the sequence number of the current block.
* `root_hash` is the hash of the block data (block header).
* `file_hash` helps validators optimize processes; typically, you don’t need it.

A full block structure is as follows:

```tlb
block#11ef55aa global_id:int32
  info:^BlockInfo value_flow:^ValueFlow
  state_update:^(MERKLE_UPDATE ShardState)
  extra:^BlockExtra = Block;
```

The most relevant field here is `state_update`. This `MERKLE_UPDATE` cell stores the old and new hashes of the shardchain state. Note that the masterchain always consists of a single shard, so inspecting a masterchain block reveals the masterchain state hash.

Another relevant field is `extra`:

```tlb
block_extra in_msg_descr:^InMsgDescr
  out_msg_descr:^OutMsgDescr
  account_blocks:^ShardAccountBlocks
  rand_seed:bits256
  created_by:bits256
  custom:(Maybe ^McBlockExtra) = BlockExtra;
```

Inspecting a masterchain block reveals the `McBlockExtra` field:

```tlb
masterchain_block_extra#cca5
  key_block:(## 1)
  shard_hashes:ShardHashes
  shard_fees:ShardFees
  ^[ prev_blk_signatures:(HashmapE 16 CryptoSignaturePair)
     recover_create_msg:(Maybe ^InMsg)
     mint_msg:(Maybe ^InMsg) ]
  config:key_block?ConfigParams
= McBlockExtra;
```

The `shard_hashes` field is essential, as it holds the latest known shardchain blocks, which are critical for basechain proofs.

For detailed inspections, it is convenient to use the [official explorer](https://explorer.toncoin.org/).

## High-level overview of proofs [#high-level-overview-of-proofs]

### Prove a transaction in masterchain [#prove-a-transaction-in-masterchain]

To prove a transaction's existence in the **masterchain**:

1. Obtain a trusted masterchain block `root_hash` using TVM instructions (`PREVMCBLOCKS`, `PREVMCBLOCKS_100`, `PREVKEYBLOCKS`).
2. The user provides a complete masterchain block that should be validated against the trusted hash.
3. Parse the block to extract the transaction.

### Prove a transaction in basechain [#prove-a-transaction-in-basechain]

For **basechain** transactions:

1. Follow *steps 1-2* above to get a trusted `masterchain` block.
2. Extract the `shard_hashes` field from the masterchain block.
3. User provides the full shardchain block that should be validated against the trusted hash.
4. Parse the shardchain block to find the transaction.

### Prove account states [#prove-account-states]

Sometimes, data is not in block diffs but within the `ShardState` itself. To prove an account's state in the **basechain**:

1. Parse the shardchain block’s `state_update` field. This exotic cell contains two `ShardState` hashes (before and after the block).
2. The user provides a `ShardState` that must be validated against the hash obtained in *step 1*.

<Callout>
  You can only prove the state at block boundaries (not intermediate states).
</Callout>

## Understanding pruned branch cells [#understanding-pruned-branch-cells]

Familiarize yourself with pruned branch cells and the concept of &#x2A;*hash0(cell)**.

<Mermaid
  chart="graph TD
    subgraph &#x22;v2&#x22;
        B1((&#x22;c0&#x22;)) --> B2((&#x22;c1&#x22;))
        B2 -.-> B3((&#x22;c2&#x22;))
    end

    subgraph &#x22;v1&#x22;
        A1((&#x22;c0&#x22;)) --> A2((&#x22;c1&#x22;))
        A2 --> A3((&#x22;c2&#x22;))
    end"
/>

*v1* is a regular cell tree; in *v2*, the cell *c1* becomes a pruned branch, removing its content and references. However, if you only need *c0*, there’s no practical difference, as `$hash_0(v1) == hash_0(v2)$`.

* `hash0(cell)` ignores pruned branches, returning the original tree’s hash.
* `reprHash(cell)` accounts for everything. Matching `reprHashes` ensures cell path equivalency.

<Callout>
  Use `HASHCU` for representation hash and `CHASHI`/`CHASHIX` for different-level hashes.
</Callout>

## Composing proofs [#composing-proofs]

If you have two cell trees:

<Mermaid
  chart="graph TD
    subgraph &#x22;v1&#x22;
        A1((&#x22;c0&#x22;)) --> A2((&#x22;pruned(c1)&#x22;))
        A2 -.-> A3((&#x22;c2&#x22;))
    end
    subgraph &#x22;v2&#x22;
        B1((&#x22;c1&#x22;)) --> B2((&#x22;c2&#x22;))
    end"
/>

Approaches:

* Parse **v1** to get `$hash_0(c1) = x$` and verify the provided **v2**.
* Concatenate **v2** with **v1** to reconstruct the original tree.

<Mermaid
  chart="graph TD
    subgraph &#x22;v1&#x22;
        A1((&#x22;c0&#x22;)) --> A2((&#x22;c1&#x22;))
        A2 ---> A3((&#x22;c2&#x22;))
    end"
/>

<Callout>
  * Trusted data hashes may be separated from cells (e.g., `PREVMCBLOCKS`).
  * Replacing pruned cells with actual cells changes the `MERKLE_UPDATE` cell hash.
    Always manually validate proofs against trusted hashes in these cases.
</Callout>

## Real-world example [#real-world-example]

Let's consider a scenario where we want to prove that a particular account has a specific state. This is useful because having a state allows you to call a get-method on it or even emulate a transaction.
In this particular example, we want to prove the state of a JettonMaster and then call the `get_wallet_address` method on it. This way, even if a particular JettonMaster does not support [TEP-89](https://github.com/ton-blockchain/TEPs/blob/master/text/0089-jetton-wallet-discovery.md), it is still possible to obtain the wallet address for a specific account.

The [full example](https://github.com/tact-lang/dex-tolk/blob/main/sources/contracts/proof.tolk) is too large for this article, but let's cover some key points.

This is an example of the proof composition technique described above. It is convenient because for `getRawAccountState`, the [liteserver](/llms/ecosystem/nodes/overview/content.md) returns two items:

* the account state itself
* a BoC containing two proofs

The first is a shardchain block proof, and the second is a shard state proof.

We will save gas and improve parsing convenience by concatenating the `AccountState` with the `ShardState` proof, which is a cell tree where all branches are pruned except for the path from the root to the `AccountState`. The `AccountState` itself is also pruned so that we will substitute the pruned `AccountState` with the actual one.

```ts
const accountStateAndProof = await client.liteServer.getRawAccountState(
    jettonMinterToProofStateFor,
    {
        target_block: blockToProofToStrId,
    },
)

const proofs = Cell.fromBoc(Buffer.from(accountStateAndProof.proof, "hex"))

const scBlockProof = proofs[0]
const newShardStateProof = proofs[1]
const newShardState = newShardStateProof.refs[0]
const accountState = Cell.fromHex(accountStateAndProof.state)

const {path} = walk(newShardState, 0, [], null) // Find the deepest pruned branch cell
const patchedShardState = rebuild(newShardState, path, accountState) // And replace it with the actual account state
```

Another interesting point is how we access the hash of the last known `ShardBlock`.

```tolk title="Tolk"
@pure
fun slice.preloadIthRef(self, idx: int): cell
    asm "PLDREFVAR"

@inline
fun findShardInBinTree(root: cell, addr: address, shardBitLen: int): ShardDescr {
    var curCs = root.beginParse();
    val (_, accountId) = addr.getWorkchainAndHash();
    var bitMask = 1 << 255;
    repeat (shardBitLen) {
        if ((accountId & bitMask) != 0) {
            // If the bit is 1, go to the right child.
            curCs = curCs.preloadIthRef(1).beginParse();
        } else {
            // If the bit is 0, go to the left child.
            curCs = curCs.preloadIthRef(0).beginParse();
        }
        bitMask = bitMask >> 1;
    }
    curCs.skipBits(1); // Skip the leaf tag of the tree node.
    return ShardDescr.fromSlice(curCs);
}

// ...

var blockExtra = blockHeader.extra;
val mcBlockExtra = McBlockExtra.fromCell(blockExtra.loadRef().beginParse().preloadIthRef(3));
// shardHashes is a hashmap (workchain -> ShardDescr).
// Only the ShardDescr for workchain 0 is needed, since the target account is in basechain.
// `mustGet` is safe here because the block is already validated, and every valid masterchain block has a ShardDescr for workchain 0.
val binTreeWithShardDescr: cell = mcBlockExtra.shardHashes.mustGet(0);
val shardDescr = findShardInBinTree(binTreeWithShardDescr, jettonMaster, shardBitLen);
```

```tlb
_ (HashmapE 32 ^(BinTree ShardDescr)) = ShardHashes;
```

A `BinTree&#x60; is a TL-B structure that operates straightforwardly. It stores a single bit to indicate whether the current cell is a leaf. If it is a leaf, it stores the &#x2A;*`ShardDescr`**. Otherwise, the cell holds two references: a left child and a right child.

Since a shard identifier is a binary prefix of an address, we can traverse the tree by following the path of bits in the address.