MerkleTree

MerkleTree is work based on Nomad's Merkle.sol, which is used under MIT OR Apache-2.0 link. With the following changes:

Adapted for Solidity 0.8.x.
Amount of tree leaves stored externally.
Added thorough documentation.
H(0,0) = 0 optimization from ER forum post.

Nomad's Merkle.sol is work based on eth2 deposit contract, which is used under CC0-1.0 link. With the following changes:

Implemented in Solidity 0.7.6 (eth2 deposit contract implemented in Vyper).

H() = keccak256() is used as the hashing function instead of sha256().

State Variables

MAX_LEAVES

For root calculation we need at least one empty leaf, thus the minus one in the formula.

uint256 internal constant MAX_LEAVES = 2 ** ORIGIN_TREE_HEIGHT - 1;

Functions

insertBase

Inserts node into merkle tree

Reverts if tree is full

function insertBase(BaseTree storage tree, uint256 newCount, bytes32 node) internal;

Parameters

Name	Type	Description
`tree`	`BaseTree`
`newCount`	`uint256`	Amount of inserted leaves in the tree after the insertion (i.e. current + 1)
`node`	`bytes32`	Element to insert into tree

rootBase

Calculates and returns current root of the merkle tree.

function rootBase(BaseTree storage tree, uint256 count) internal view returns (bytes32 current);

Parameters

Name	Type	Description
`tree`	`BaseTree`
`count`	`uint256`	Current amount of inserted leaves in the tree

Returns

Name	Type	Description
`current`	`bytes32`	Calculated root of `tree`

initializeRoots

Initializes the historical roots for the tree by inserting an empty root.

function initializeRoots(HistoricalTree storage tree) internal returns (bytes32 savedRoot);

insert

Inserts a new leaf into the merkle tree.

Reverts if tree is full.

function insert(HistoricalTree storage tree, bytes32 node) internal returns (bytes32 newRoot);

Parameters

Name	Type	Description
`tree`	`HistoricalTree`
`node`	`bytes32`	Element to insert into tree

Returns

Name	Type	Description
`newRoot`	`bytes32`	Merkle root after the leaf was inserted

root

Returns the historical root of the merkle tree.

Reverts if not enough leafs have been inserted.

function root(HistoricalTree storage tree, uint256 count) internal view returns (bytes32 historicalRoot);

Parameters

Name	Type	Description
`tree`	`HistoricalTree`
`count`	`uint256`	Amount of leafs in the tree at some point of time

Returns

Name	Type	Description
`historicalRoot`	`bytes32`	Merkle root after `count` leafs were inserted

update

Updates the value for the leaf with the given index in the Dynamic Merkle Tree.

Will revert if incorrect proof of inclusion for old value is supplied.

function update(DynamicTree storage tree, uint256 index, bytes32 oldValue, bytes32[] memory branch, bytes32 newValue)
    internal
    returns (bytes32 newRoot);

Parameters

Name	Type	Description
`tree`	`DynamicTree`	Dynamic merkle tree
`index`	`uint256`	Index of the leaf to update
`oldValue`	`bytes32`	Previous value of the leaf
`branch`	`bytes32[]`	Proof of inclusion of previous value into the tree
`newValue`	`bytes32`	New leaf value to assign

Returns

Name	Type	Description
`newRoot`	`bytes32`	New value for the Merkle Root after the leaf is updated