LibMerkle32

This library is meant for creating and verifying Merkle proofs.

Each Merkle tree is assumed to have 2^height leaves.

Nodes are concatenated pairwise and hashed with keccak256.

Siblings are in bottom-up order, from leaf to root.

Functions

Compute the root of a Merkle tree from its leaves.

Raises an error if more than 2^height leaves are provided.


function merkleRoot(bytes32[] memory leaves, uint256 height)
    internal
    pure
    returns (bytes32);

Parameters

Name	Type	Description
`leaves`	`bytes32[]`	The left-most leaves of the Merkle tree
`height`	`uint256`	The height of the Merkle tree

Returns

Name	Type	Description
`<none>`	`bytes32`	The root hash of the Merkle tree

Compute the siblings of the ancestors of a leaf in a Merkle tree.

Raises an error if the provided index is out of bounds.

Raises an error if more than 2^height leaves are provided.


function siblings(bytes32[] memory leaves, uint256 index, uint256 height)
    internal
    pure
    returns (bytes32[] memory);

Parameters

Name	Type	Description
`leaves`	`bytes32[]`	The left-most leaves of the Merkle tree
`index`	`uint256`	The index of the leaf
`height`	`uint256`	The height of the Merkle tree

Returns

Name	Type	Description
`<none>`	`bytes32[]`	The siblings of the ancestors of the leaf in bottom-up order

Compute the root of a Merkle tree after replacing one of its leaves.

Raises an error if the provided index is out of bounds.


function merkleRootAfterReplacement(bytes32[] calldata sibs, uint256 index, bytes32 leaf)
    internal
    pure
    returns (bytes32);

Parameters

Name	Type	Description
`sibs`	`bytes32[]`	The siblings of the ancestors of the leaf in bottom-up order
`index`	`uint256`	The index of the leaf
`leaf`	`bytes32`	The new leaf

Returns

Name	Type	Description
`<none>`	`bytes32`	The root hash of the new Merkle tree

Compute the parent of two nodes.

Uses assembly for extra performance


function parent(bytes32 leftNode, bytes32 rightNode)
    internal
    pure
    returns (bytes32 parentNode);

Parameters

Name	Type	Description
`leftNode`	`bytes32`	The left node
`rightNode`	`bytes32`	The right node

Returns

Name	Type	Description
`parentNode`	`bytes32`	The parent node

Compute the parent level of an array of nodes.

The default node of a parent level is the parent node of two default nodes.


function parentLevel(bytes32[] memory nodes, bytes32 defaultNode)
    internal
    pure
    returns (bytes32[] memory);

Parameters

Name	Type	Description
`nodes`	`bytes32[]`	The array of left-most nodes
`defaultNode`	`bytes32`	The default node after the array

Returns

Name	Type	Description
`<none>`	`bytes32[]`	The left-most nodes of the parent level

Get the node at some index


function at(bytes32[] memory nodes, uint256 index, bytes32 defaultNode)
    internal
    pure
    returns (bytes32);

Parameters

Name	Type	Description
`nodes`	`bytes32[]`	The array of left-most nodes
`index`	`uint256`	The index of the node
`defaultNode`	`bytes32`	The default node after the array