# Implementation Details ### Overview The type of merkle tree implemented in the Vea [inbox](https://github.com/kleros/vea/blob/2410617e6e6c243bc3108059c39703350031ead2/contracts/src/arbitrumToEth/VeaInboxArbToEth.sol) is sometimes referred to as a merkle mountain range ([MMR](https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md)). Without additional context, merkle trees are usually understood to be perfectly balanced binary trees with a fixed height. MMRs on the other hand grow in height as more leafs are inserted, and can be represented by a set of merkle subtrees, referred to as merkle "mountain ranges" due to their shape, see diagram below.

Merkle Mountain Range representing 7 messages

### Leaf Hashing All leafs are double hashed to avoid [second preimage attacks](https://flawed.net.nz/2018/02/21/attacking-merkle-trees-with-a-second-preimage-attack/). ### Inbox Data Structure Merkle mountain ranges efficiently represent the state of all messages with a limited amount of data made available in the vea inbox contract stored in the [inbox](https://github.com/kleros/vea/blob/2410617e6e6c243bc3108059c39703350031ead2/contracts/src/arbitrumToEth/VeaInboxArbToEth.sol#L34) variable. ``` bytes32[64] public inbox; // stores minimal set of complete subtree roots of the merkle tree to increment. ``` The [inbox](https://github.com/kleros/vea/blob/c78180985507611b3f6b69c2863a7a36e1daed47/contracts/src/arbitrumToEth/VeaInboxArbToEth.sol#L50) represents the 'mountain ranges' or subtrees of varying height. eg inbox\[4] = root of a merkle tree of size 2^4 = 16 leaves. The inbox state for the above merkle tree example with 7 messages is given by the table below.

Count	Inbox[2]	Inbox[1]	Inbox[0]
0b101	H(1,4)	H(5,6)	H(7)

where we use the notation H as a short-hand for: * H(1,4) = root of merkle tree representing messages m1, m2, m3, m4 * H(5,6) = root of merkle tree representing messages m5, m6 * H(7) = root of merkle tree representing message m7 ### Notation $$ H(n):= keccak(keccak(m\_n))) $$ H(n) represents the n-th leaf which is the double hash of the n-th message m\_n. H(n,m) represents an interior node of the tree which is the merkle root representing the leaves H(n), H(n+1), ..., H(m). The parent of a pair of nodes is calculated by sorting & concatenating the nodes, and hashing the result. for example $$ H(1,2):= keccak(H(1) \mathbin{||}H(2)) $$ $$ H(3,4):= keccak(H(3) \mathbin{||}H(4) $$ $$ H(1,4):= keccak(H(1,2) \mathbin{||}H(3,4)) $$ Note that we should sort hash pairs before hashing. eg. if H(2) < H(1), then we would concatenate in the opposite order. $$ H(1,2) = keccak(H(2) \mathbin{||}H(1)) $$ Above we neglect the sorting notation for brevity. ### Inbox State Examples & Properties Another example, showing the inbox state step by step for 7 insertions.

Count	Inbox[2]	Inbox[1]	Inbox[0]
0b001	---	---	H(1)
0b010	---	H(1,2)	"H(1)"
0b011	---	H(1,2)	H(3)
0b100	H(1,4)	"H(1,2)"	"H(3)"
0b101	H(1,4)	"H(1,2)"	H(5)
0b110	H(1,4)	H(5,6)	"H(5)"
0b111	H(1,4)	H(5,6)	H(7)

Note some properties about the on bits ("1s") in count: * The fist set bit of count corresponds to the modified inbox index. * The on bits of count indicate the minimal data to represent the tree. For example, when count = 0b010, inbox\[0] is set to H(1). However inbox\[1] = H(1,2) which implicitly includes H(1), so inbox\[0] is not needed to encode the tree. From the perspective of data availability, we can forget about H(1) in the slot represented by inbox\[0]. For that reason it is represented in quotation marks and can be overwritten in future steps, reusing the dirty inbox slot for efficiency. ### Calculating the root example To calculate the root, we hash together the data in each inbox slot corresponding to an on bit in count, from the lowest index to the highest.

Count	Inbox[2]	Inbox[1]	Inbox[0]	root
0b001	---	---	H(1)	H(1)
0b010	---	H(1,2)	"H(1)"	H(1,2)
0b011	---	H(1,2)	H(3)	H( H(3) , H(1,2) )
0b100	H(1,4)	"H(1,2)"	"H(3)"	H(1,4)
0b101	H(1,4)	"H(1,2)"	H(5)	H( H(1,4) , H(5) )
0b110	H(1,4)	H(5,6)	"H(5)"	H( H(1,4) , H(5,6) )
0b111	H(1,4)	H(5,6)	H(7)	H(H(1,4),H(H(5,6),H(7)))

## Other resources Here are some useful resources to better understand merkle mountain ranges. The notation and indices used in the below resources differs from the notation used in this document. Resources are meant to be illustrative and supplemental. * [opentimestamps/opentimestamps-server](https://github.com/opentimestamps/opentimestamps-server/blob/master/doc/merkle-mountain-range.md) * [mimblewimble/grin](https://github.com/mimblewimble/grin/blob/master/doc/mmr.md) --- # 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.vea.ninja/introduction/technical-deep-dive/implementation-details.md?ask= ``` 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.