Merkle Trees
Merkle Tree and Removable Merkle Tree Implementations
In this protocol, the Merkle tree is adapted for dynamic state management: it not only represents a static commitment but also supports incremental updates such as appending new leaves or, in some configurations, deleting existing ones. This ensures the tree can evolve as new commitments (e.g., deposits, transactions, or records) are added, while still allowing efficient proof verification
Incremental Insertions
A key modification to the standard Merkle tree is the append-only insertion rule. New leaves are always added at the end of the leaf layer, filling positions from left to right. This deterministic rule avoids ambiguity about where elements are placed, which is crucial when multiple parties interact with the same structure in parallel. By forcing sequential filling, the tree maintains a clear mapping between leaf indices and insertion order.
The tree does not need to recompute every internal node on each insertion. Instead, it updates only the nodes along the insertion path up to the root. This makes the update process efficient, scaling logarithmically with the depth of the tree, even when the dataset becomes very large.
Root History and Stability
Because the root changes with every insertion, the design incorporates a mechanism to retain a sliding window of recent roots. This allows proofs generated against slightly older states to remain valid for a period of time. Retaining a fixed number of roots prevents denial-of-service scenarios in which a malicious actor could continually insert new elements and force honest participants’ proofs to become invalidated too quickly. In practice, maintaining a bounded history (for example, the last 100 roots) balances security with memory usage.
Write-Optimized Variant
For high-throughput cases where only new insertions matter, a write-only, frontier-based variant is used. Instead of storing the entire tree, it tracks only the “right frontier”—the minimal set of nodes needed to recompute the root when new leaves arrive. When an insertion occurs, the tree bubbles the new value upward, combining it with siblings as needed. The hashing rule is defined recursively:
If both children of a node exist, the node’s value is Hash(left, right).
If only the left child exists, the node’s value is Hash(left, 0), with zero acting as a placeholder.
This convention ensures that incomplete subtrees can still produce deterministic roots without requiring fully populated right children. It also minimizes memory usage, since only a small set of nodes is stored.
Removal-supporting Variant
In contexts where elements may need to be removed or replaced, a fully mapped variant of the Merkle tree is employed. Unlike the frontier-based design, this version maintains the entire internal structure in memory (or in a mapping). The layout follows a binary-heap indexing scheme:
The root node resides at index 0.
The left child of node i is at position 2*i, and the right child at 2*i + 1.
Leaves are placed sequentially from left to right, beginning at a minimum index offset that marks the start of the leaf layer.
When inserting or deleting a leaf, the change is propagated upward, recomputing parent nodes along the path until the structure is consistent again. The depth needed is determined by the logarithm (base-2) of the current number of leaves, rounded up to the nearest integer.
This design has higher storage costs but provides the flexibility of removals and updates, which are necessary in some protocol scenarios where commitments can be revoked or expired.
Summary of Trade-offs
Append-only tree (frontier-based): Minimal storage, efficient updates, suitable when only insertions are allowed.
Deletion-capable tree (fully mapped): Larger storage footprint, but supports richer operations, including removing or replacing commitments.
Both variants: Retain a history of recent roots to ensure stability and resist malicious attempts to disrupt proof validity.
Last updated