IncrementalMerkleTreeLib
Title: IncrementalMerkleTreeLib
Authors: David Dada, Modified from zk-kit Solidity (https://github.com/privacy-scaling-explorations/zk-kit.solidity)
Poseidon-hashed, dynamic-depth incremental Merkle tree with a recent-root history ring. The commitment accumulator for nullifier-based privacy schemes: insert commitments as leaves, then prove membership in a ZK circuit against any recent root.
Wraps the PSE-audited LeanIMT (Semaphore v4 audit, Mar 2024) for the tree math
and adds a Tornado-style root-history ring so a proof built against a slightly
stale root still verifies as the tree grows between proof generation and
submission. Poseidon hashing is MANDATORY: the proving circuits hash with
Poseidon, so a keccak tree (e.g. OpenZeppelin MerkleProof) would NOT verify and
must never be substituted. Stateless helper — no own ERC-7201 slot; Tree is
held inline in the consumer's namespaced storage. Leaves must be non-zero and
strictly less than the SNARK scalar field (enforced by LeanIMT).
Constants
ROOT_HISTORY_SIZE
Number of recent roots retained for membership proofs. A proof remains valid as long as fewer than this many insertions happen between generation and use.
uint256 internal constant ROOT_HISTORY_SIZE = 30;Functions
insert
Inserts leaf and records the new root in the history ring.
function insert(Tree storage self, uint256 leaf) internal returns (uint256 newRoot);Parameters
| Name | Type | Description |
|---|---|---|
| self | Tree | The tree storage reference. |
| leaf | uint256 | The leaf (commitment) to insert; must be non-zero and < SNARK field. |
Returns
| Name | Type | Description |
|---|---|---|
| newRoot | uint256 | The tree root after insertion. |
root
Returns the current tree root (0 for an empty tree).
function root(Tree storage self) internal view returns (uint256);Parameters
| Name | Type | Description |
|---|---|---|
| self | Tree | The tree storage reference. |
Returns
| Name | Type | Description |
|---|---|---|
| <none> | uint256 |
isKnownRoot
Returns whether r is the current root or one of the recent historical roots.
The zero root is never "known". Walks the live ring window newest-first.
function isKnownRoot(Tree storage self, uint256 r) internal view returns (bool);Parameters
| Name | Type | Description |
|---|---|---|
| self | Tree | The tree storage reference. |
| r | uint256 | The candidate root. |
Returns
| Name | Type | Description |
|---|---|---|
| <none> | bool |
has
Returns whether leaf is present in the tree.
function has(Tree storage self, uint256 leaf) internal view returns (bool);Parameters
| Name | Type | Description |
|---|---|---|
| self | Tree | The tree storage reference. |
| leaf | uint256 | The leaf to query. |
Returns
| Name | Type | Description |
|---|---|---|
| <none> | bool |
size
Returns the number of leaves in the tree.
function size(Tree storage self) internal view returns (uint256);Parameters
| Name | Type | Description |
|---|---|---|
| self | Tree | The tree storage reference. |
Returns
| Name | Type | Description |
|---|---|---|
| <none> | uint256 |
depth
Returns the current dynamic depth of the tree.
function depth(Tree storage self) internal view returns (uint256);Parameters
| Name | Type | Description |
|---|---|---|
| self | Tree | The tree storage reference. |
Returns
| Name | Type | Description |
|---|---|---|
| <none> | uint256 |
Structs
Tree
struct Tree {
LeanIMTData _leanIMT; // audited LeanIMT tree state (size, depth, sideNodes, leaves)
uint256 _currentRootIndex; // ring position of the most recent root
uint256 _rootCount; // total number of roots ever recorded
mapping(uint256 index => uint256 root) _rootHistory; // ring buffer of recent roots
}Properties
| Name | Type | Description |
|---|---|---|
| _leanIMT | LeanIMTData | |
| _currentRootIndex | uint256 | |
| _rootCount | uint256 | |
| _rootHistory | mapping(uint256 index => uint256 root) |