MerkleMath

Git Source

Functions

proofRoot

Calculates the merkle root for the given leaf and merkle proof.

Will revert if proof length exceeds the tree height.

function proofRoot(uint256 index, bytes32 leaf, bytes32[] memory proof, uint256 height)
    internal
    pure
    returns (bytes32 root_);

Parameters

Returns

getParent

Calculates the parent of a node on the path from one of the leafs to root.

Apply unchecked to all ++h operations

function getParent(bytes32 node, bytes32 sibling, uint256 leafIndex, uint256 nodeHeight)
    internal
    pure
    returns (bytes32 parent);

Parameters

getParent

Calculates the parent of tow nodes in the merkle tree.

We use implementation with H(0,0) = 0 This makes EVERY empty node in the tree equal to ZERO, saving us from storing H(0,0), H(H(0,0), H(0, 0)), and so on

function getParent(bytes32 leftChild, bytes32 rightChild) internal pure returns (bytes32 parent);

Parameters

Returns

calculateRoot

Calculates merkle root for a list of given leafs. Merkle Tree is constructed by padding the list with ZERO values for leafs until list length is 2**height. Merkle Root is calculated for the constructed tree, and then saved in leafs[0].

Note:

• leafs values are overwritten in the process to avoid excessive memory allocations.
• Caller is expected not to reuse hashes list after the call, and only use leafs[0] value, which is guaranteed to contain the calculated merkle root.
• root is calculated using the H(0,0) = 0 Merkle Tree implementation. See MerkleTree.sol for details.

Amount of leaves should be at most 2**height

function calculateRoot(bytes32[] memory hashes, uint256 height) internal pure;

Parameters

calculateProof

Generates a proof of inclusion of a leaf in the list. If the requested index is outside of the list range, generates a proof of inclusion for an empty leaf (proof of non-inclusion). The Merkle Tree is constructed by padding the list with ZERO values until list length is a power of two AND index is in the extended list range. For example:

• hashes.length == 6 and 0 <= index <= 7 will "extend" the list to 8 entries.
• hashes.length == 6 and 7 < index <= 15 will "extend" the list to 16 entries.

Note: leafs values are overwritten in the process to avoid excessive memory allocations. Caller is expected not to reuse hashes list after the call.

h, leftIndex, rightIndex and levelLength never overflow

function calculateProof(bytes32[] memory hashes, uint256 index) internal pure returns (bytes32[] memory proof);

Parameters

Returns

getHeight

Returns the height of the tree having a given amount of leafs.

h, leftIndex, rightIndex and levelLength never overflow

function getHeight(uint256 leafs) internal pure returns (uint256 height);