SequentialMerkleProofs
A sequential Merkle proof is a proof that leaves appear sequentially in a Merkle tree.
State Variables
EMPTY_TREE_ROOT
bytes32 internal constant EMPTY_TREE_ROOT = 0;
LEAF_PREFIX
The leaf prefix used to hash to a leaf ("leaf|").
bytes5 internal constant LEAF_PREFIX = 0x6c6561667c;
NODE_PREFIX
The node prefix used to hash to a node ("node|").
bytes5 internal constant NODE_PREFIX = 0x6e6f64657c;
ROOT_PREFIX
The root prefix used to hash to a root.
bytes5 internal constant ROOT_PREFIX = 0x726f6f747c;
Functions
verify
Verifies a sequential Merkle proof.
proofElements_[0] is the total number of leaves in the Merkle tree, the rest are the decommitments.
Can also revert with an array out-of-bounds access panic.
function verify(bytes32 root_, uint256 startingIndex_, bytes[] calldata leaves_, bytes32[] calldata proofElements_)
internal
pure;
Parameters
| Name | Type | Description |
|---|---|---|
root_ | bytes32 | The root of the Merkle tree. |
startingIndex_ | uint256 | The index of the first leaf provided. |
leaves_ | bytes[] | The leaves to prove sequential existence from the starting index. |
proofElements_ | bytes32[] | The Merkle proof data. |
getRoot
Gets the root of a sequential Merkle proof.
proofElements_[0] is the total number of leaves in the Merkle tree, the rest are the decommitments.
Can also revert with an array out-of-bounds access panic.
function getRoot(uint256 startingIndex_, bytes[] calldata leaves_, bytes32[] calldata proofElements_)
internal
pure
returns (bytes32 root_);
Parameters
| Name | Type | Description |
|---|---|---|
startingIndex_ | uint256 | The index of the first leaf provided. |
leaves_ | bytes[] | The leaves to prove sequential existence from the starting index. |
proofElements_ | bytes32[] | The Merkle proof data. |
getLeafCount
Extracts the leaf count from a sequential Merkle proof, without verifying the proof.
proofElements_[0] is the total number of leaves in the Merkle tree.
Does not verify the proof. Only extracts the leaf count from the proof elements.
function getLeafCount(bytes32[] calldata proofElements_) internal pure returns (uint32 leafCount_);
Parameters
| Name | Type | Description |
|---|---|---|
proofElements_ | bytes32[] | The Merkle proof data. |
_bitCount32
Counts number of set bits (1's) in 32-bit unsigned integer.
See https://en.wikipedia.org/wiki/Hamming_weight implementation popcount64b.
Literals are inlined as they are very specific to this algorithm/function, and actually improve readability, given their patterns.
function _bitCount32(uint256 n_) internal pure returns (uint256 bitCount_);
Parameters
| Name | Type | Description |
|---|---|---|
n_ | uint256 | The number to count the set bits of. |
Returns
| Name | Type | Description |
|---|---|---|
bitCount_ | uint256 | The number of set bits in n_. |
_roundUpToPowerOf2
Rounds a 32-bit unsigned integer up to the nearest power of 2.
Literals are inlined as they are very specific to this algorithm/function, and actually improve readability, given their patterns.
function _roundUpToPowerOf2(uint256 n_) internal pure returns (uint256 powerOf2_);
Parameters
| Name | Type | Description |
|---|---|---|
n_ | uint256 | The number to round up to the nearest power of 2. |
Returns
| Name | Type | Description |
|---|---|---|
powerOf2_ | uint256 | The nearest power of 2 to n_. |
_getBalancedLeafCount
Gets the balanced leaf count for a sequential Merkle proof.
function _getBalancedLeafCount(uint256 leafCount_) internal pure returns (uint256 balancedLeafCount_);
Parameters
| Name | Type | Description |
|---|---|---|
leafCount_ | uint256 | The number of leaves in the Merkle tree. |
Returns
| Name | Type | Description |
|---|---|---|
balancedLeafCount_ | uint256 | The balanced leaf count. |
_getRoot
Gets the root of a sequential Merkle proof.
proofElements_[0] is the total number of leaves in the Merkle tree, the rest are the decommitments.
function _getRoot(uint256 startingIndex_, bytes32[] memory hashes_, bytes32[] calldata proofElements_)
internal
pure
returns (bytes32 root_);
Parameters
| Name | Type | Description |
|---|---|---|
startingIndex_ | uint256 | The index of the first leaf provided. |
hashes_ | bytes32[] | The leaf hashes (in reverse order) to prove sequential existence from the starting index. |
proofElements_ | bytes32[] | The Merkle proof data. |
_isEven
The following variables are used while iterating through the root reconstruction from the proof.
readIndex_ is the index of hashes_ circular queue currently being read from.
writeIndex_ is the index of hashes_ circular queue currently being written to.
proofIndex_ is the index of proofElements_ array that is to be read from.
upperBound_ is the rightmost tree index, of the current level of the tree, such that all nodes to the
right, if any, are non-existent.
lowestTreeIndex_ is the tree index, of the current level of the tree, of the leftmost node we have.
highestLeafNodeIndex_ is the tree index of the rightmost leaf node we have.
nodeIndex_ is the tree index of the current node we are handling.
nextNodeIndex_ is the tree index of the next node we may be handling.
root_ will temporarily be used as the right part of the node pair hash, it is being used to save
much needed stack space.
left_ is the left part of the node pair hash.
function _isEven(uint256 n_) internal pure returns (bool isEven_);
_isLeftAnExistingHash
Checks if the left part of the hash should be an existing computed hash.
function _isLeftAnExistingHash(uint256 nodeIndex_, uint256 nextNodeIndex_)
internal
pure
returns (bool isLeftAnExistingHash_);
Parameters
| Name | Type | Description |
|---|---|---|
nodeIndex_ | uint256 | The index of the current node in the tree indices array. |
nextNodeIndex_ | uint256 | The index of the next (lower) node in the tree indices array. |
Returns
| Name | Type | Description |
|---|---|---|
isLeftAnExistingHash_ | bool | True if the left part of the hash should be an existing computed hash. |
_hashLeaf
Hashes a leaf of arbitrary size into a 32-byte leaf node.
function _hashLeaf(bytes calldata leaf_) internal pure returns (bytes32 hash_);
Parameters
| Name | Type | Description |
|---|---|---|
leaf_ | bytes | The leaf to hash. |
Returns
| Name | Type | Description |
|---|---|---|
hash_ | bytes32 | The hash of the leaf. |
_hashNodePair
Hashes a pair of 32-byte nodes into a 32-byte parent node.
function _hashNodePair(bytes32 leftNode_, bytes32 rightNode_) internal pure returns (bytes32 hash_);
Parameters
| Name | Type | Description |
|---|---|---|
leftNode_ | bytes32 | The left node to hash. |
rightNode_ | bytes32 | The right node to hash. |
Returns
| Name | Type | Description |
|---|---|---|
hash_ | bytes32 | The hash of the pair of nodes. |
_hashPairlessNode
Hashes a 32-byte node, without a right paired node, into a 32-byte parent node.
function _hashPairlessNode(bytes32 node_) internal pure returns (bytes32 hash_);
Parameters
| Name | Type | Description |
|---|---|---|
node_ | bytes32 | The node to hash. |
Returns
| Name | Type | Description |
|---|---|---|
hash_ | bytes32 | The hash of the node. |
_hashRoot
Hashes the topmost 32-byte node in the tree, combined with the tree's leaf count, into a 32-byte root.
function _hashRoot(uint256 leafCount_, bytes32 node_) internal pure returns (bytes32 hash_);
Parameters
| Name | Type | Description |
|---|---|---|
leafCount_ | uint256 | The number of leaves in the Merkle tree. |
node_ | bytes32 | The topmost node in the tree. |
Returns
| Name | Type | Description |
|---|---|---|
hash_ | bytes32 | The root hash of the tree. |
_getReversedLeafNodesFromLeaves
Get leaf nodes from arbitrary size leaves in calldata, in reverse order.
function _getReversedLeafNodesFromLeaves(bytes[] calldata leaves_)
internal
pure
returns (bytes32[] memory leafNodes_);