# Exotic Cells

Every Cell has its own type encoded by an integer from -1 to 255.
Cell with type -1 is an `ordinary`

Cell, and all others Cells called `exotic`

or `special`

.
The type of an exotic cell is stored as the first eight bits of its data. If an exotic cell has less than eight data bits, it is invalid.
Currently, there are 4 exotic Cell types:

`{`

Prunned Branch: 1,

Library Reference: 2,

Merkle Proof: 3,

Merkle Update: 4

}

### Pruned Branch

Pruned branches are Cells that represent deleted subtrees of Cells.

They can have level `1 <= l <= 3`

and contain exactly `8 + 8 + 256 * l + 16 * l`

bits.

First byte is always `01`

- Cell type. The second one is the Pruned Branch level mask. Then goes `l * 32`

bytes hashes of deleted subtrees and after that `l * 2`

bytes depths of deleted subtrees.

The level `l`

of a Pruned branch Cell may be called its De Bruijn index, because it determines the outer Merkle proof or Merkle update during the construction of which the branch has been pruned.

Higher hashes of Pruned branches are stored in their data and can be obtained like this:

`Hash_i = CellData[2 + (i * 32) : 2 + ((i + 1) * 32)]`

### Library Reference

Library reference cells are used for using libraries in smart contracts.

They always have level 0, and contain `8 + 256`

bits.

First byte is always `02`

- Cell type. Next 32 bytes are Representation hash of the library cell being referred to.

### Merkle Proof

Merkle Proof cells are used to verify that a portion of the Cell tree data belongs to the full tree. This design allows the verifier to not store the whole content of the tree, while still being able to verify the content by root hash.

Merkle Proof has exactly one reference and its level `0 <= l <= 3`

must be `max(Lvl(ref) - 1, 0)`

. These cells contain exactly `8 + 256 + 16 = 280`

bits.

First byte is always `03`

- Cell type. Next 32 bytes are `Hash_1(ref)`

(or `ReprHash(ref)`

if reference level is 0). The next 2 bytes are depth of the deleted subtree, which was replaced by the reference.

The higher hashes `Hash_i`

of Merkle Proof Cell are computed similarly to the higher hashes of an ordinary cell, but with `Hash_i+1(ref)`

used instead of `Hash_i(ref)`

.

### Merkle Update

Merkle update cells are always have 2 refs and behave like a Merkle proof for both of them.

Merkle Update level `0 <= l <= 3`

is `max(Lvl(ref1) − 1, Lvl(ref2) − 1, 0)`

. They contain exactly `8 + 256 + 256 + 16 + 16 = 552`

bits.

First byte is always `04`

- Cell type. Next 64 bytes are `Hash_1(ref1)`

and `Hash_2(ref2)`

- called old hash and new hash. Then goes 4 bytes with actual depth of deleted old subtree and deleted new subtree.

## Simple Proof verifying example

Let's assume there is a Cell `c`

:

`24[000078] -> {`

32[0000000F] -> {

1[80] -> {

32[0000000E]

},

1[00] -> {

32[0000000C]

}

},

16[000B] -> {

4[80] -> {

267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040],

512[00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000064]

}

}

}

But we know only its hash `44efd0fdfffa8f152339a0191de1e1c5901fdcfe13798af443640af99616b977`

, and we want to prove that cell `a`

`267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040]`

is actually a part of the `c`

, without receiving the whole `c`

.
So we ask the prover to create a Merkle Proof, replacing all branches that we are not interested in with Pruned branch cells.

The first `c`

descendant from which there is no way to get to `a`

is `ref1`

:

`32[0000000F] -> {`

1[80] -> {

32[0000000E]

},

1[00] -> {

32[0000000C]

}

}

So the prover computes its hash (`ec7c1379618703592804d3a33f7e120cebe946fa78a6775f6ee2e28d80ddb7dc`

), creates a Pruned Branch `288[0101EC7C1379618703592804D3A33F7E120CEBE946FA78A6775F6EE2E28D80DDB7DC0002]`

and replaces `ref1`

with this Pruned Branch.

The second one is `512[0000000...00000000064]`

, so the prover creates Pruned branch to replace this Cell as well:

`24[000078] -> {`

288[0101EC7C1379618703592804D3A33F7E120CEBE946FA78A6775F6EE2E28D80DDB7DC0002],

16[000B] -> {

4[80] -> {

267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040],

288[0101A458B8C0DC516A9B137D99B701BB60FE25F41F5ACFF2A54A2CA4936688880E640000]

}

}

}

The result Merkle Proof which prover sends to verifier (us in this example) looks like this:

`280[0344EFD0FDFFFA8F152339A0191DE1E1C5901FDCFE13798AF443640AF99616B9770003] -> {`

24[000078] -> {

288[0101EC7C1379618703592804D3A33F7E120CEBE946FA78A6775F6EE2E28D80DDB7DC0002],

16[000B] -> {

4[80] -> {

267[800DEB78CF30DC0C8612C3B3BE0086724D499B25CB2FBBB154C086C8B58417A2F040],

288[0101A458B8C0DC516A9B137D99B701BB60FE25F41F5ACFF2A54A2CA4936688880E640000]

}

}

}

}

When we (verifier) get the Proof Cell we make sure that its data contains the `c`

hash and then compute `Hash_1`

from the only Proof reference: `44efd0fdfffa8f152339a0191de1e1c5901fdcfe13798af443640af99616b977`

, and compare it to the `c`

hash.

Now, when we've checked that hashes are match, we need to go deep in the Cell and verify that there is a Cell `a`

(we were interested in).

Such proofs repeatedly reduce the computational load and the amount of data that needs to be sent to or stored in the verifier.