## Upgrading Commitment Storage: Introducing the On-Chain Incremental Merkle Tree In our ZK-Mixer, managing user commitments securely and efficiently is paramount. Previously, we tracked commitments by simply marking them as present in a mapping within our `Mixer.sol` contract, like so: `s_commitments[_commitment] = true;`. While functional, this approach lacks the advanced capabilities needed for more complex zero-knowledge proof systems. To enhance our mixer, we are transitioning to a more sophisticated data structure: an on-chain Incremental Merkle Tree (IMT). This structure allows for efficient addition of new leaves (commitments) and, crucially, provides a compact way to prove membership, which is essential for ZK-proof verification. The primary change occurs within the `deposit` function of `Mixer.sol`. Instead of the direct mapping update, we will now insert the commitment into our IMT. This is achieved by replacing the old line with a call to an internal function, `_insert(_commitment)`. This function will be defined in a separate, dedicated contract for the IMT logic, which `Mixer.sol` will then inherit. Here's how the `deposit` function in `Mixer.sol` will be modified: ```solidity // In Mixer.sol (within the deposit function) // Old line (to be replaced): // s_commitments[_commitment] = true; // New line: // Add the commitment to the on-chain incremental Merkle tree containing all of the commitments _insert(_commitment); ``` This modular approach—separating the IMT logic—enhances code organization and reusability. ## Structuring the `IncrementalMerkleTree.sol` Contract To house the logic for our Incremental Merkle Tree, we create a new Solidity file named `IncrementalMerkleTree.sol` within the `src` directory. This contract will encapsulate all functionalities related to the IMT. The initial structure of `IncrementalMerkleTree.sol` includes the standard SPDX license identifier and the pragma directive specifying the Solidity compiler version: ```solidity // SPDX-License-Identifier: MIT pragma solidity ^0.8.24; contract IncrementalMerkleTree { // IMT implementation will be developed here } ``` Inside this `IncrementalMerkleTree` contract, we define the `_insert` function. This internal function is responsible for adding a new leaf (which, in our ZK-Mixer context, is a commitment) to the Merkle tree. It accepts a `bytes32 _leaf` as input. Declaring it as `internal` allows it to be called from the `Mixer` contract, which will inherit `IncrementalMerkleTree`. ```solidity // In IncrementalMerkleTree.sol contract IncrementalMerkleTree { // ... (other declarations will be added) function _insert(bytes32 _leaf) internal { // Implementation of the insertion logic for the incremental Merkle tree. // This function will update the tree structure with the new commitment // and maintain the integrity of the Merkle root. // The detailed logic for insertion will be covered subsequently. } } ``` ## Defining and Validating the Merkle Tree Depth An Incremental Merkle Tree, in this implementation, will have a fixed depth (or height). This depth is a crucial parameter that determines the tree's capacity and influences computational costs. We need to store this depth and ensure it's set to a valid value upon deployment. We declare a state variable `i_depth` of type `uint32` to store the tree's depth. - `uint32` is chosen as the data type because the maximum depth of the tree is not expected to exceed values representable by a 32-bit unsigned integer (e.g., a depth of 32 is a common practical limit). - The variable is declared `public`, which automatically creates a getter function, allowing external contracts or clients to read its value. - Crucially, `i_depth` is `immutable`. This means its value can only be set once, within the contract's constructor, and cannot be modified thereafter. Using `immutable` is gas-efficient for variables that are set at deployment and never change. ```solidity // In IncrementalMerkleTree.sol contract IncrementalMerkleTree { uint32 public immutable i_depth; // ... (other parts of the contract) } ``` The tree's depth is initialized in the `IncrementalMerkleTree` contract's `constructor`. The constructor accepts a `uint32 _depth` argument. Before setting `i_depth`, we perform essential validation checks: 1. **Depth must be greater than zero:** A tree with zero depth is not meaningful. 2. **Depth should be less than 32:** A depth of 32 or more is generally considered too large for practical on-chain Merkle tree implementations. This limit is due to several factors: * **Pre-computation of Zero Hashes:** The IMT often requires pre-computing and storing "zero hashes" for various levels (subtrees consisting entirely of empty leaves). An excessively large depth would make the storage and pre-computation of these zero hashes prohibitively expensive in terms of gas. * **Circuit Complexity in ZK-SNARKs:** In ZK-SNARK applications like our mixer, the number of leaves is 2^depth. A larger depth significantly increases the complexity and computational cost (e.g., number of hash operations) within the ZK-proof generation and verification circuits. Keeping the depth manageable (e.g., < 32) is vital for performance and cost-effectiveness. To handle these validation failures efficiently, we use custom errors. Custom errors are more gas-efficient than traditional string-based `revert` messages and allow for more specific error typing. We define `IncrementalMerkleTree_DepthShouldBeGreaterThanZero` and `IncrementalMerkleTree_DepthShouldBeLessThan32`. Here's the constructor implementation with depth validation: ```solidity // In IncrementalMerkleTree.sol contract IncrementalMerkleTree { uint32 public immutable i_depth; // Custom errors for depth validation error IncrementalMerkleTree_DepthShouldBeGreaterThanZero(); error IncrementalMerkleTree_DepthShouldBeLessThan32(); constructor(uint32 _depth) { // Validation 1: Depth must be greater than 0 if (_depth == 0) { revert IncrementalMerkleTree_DepthShouldBeGreaterThanZero(); } // Validation 2: Depth should be less than 32 if (_depth >= 32) { revert IncrementalMerkleTree_DepthShouldBeLessThan32(); } i_depth = _depth; // Further initialization logic for the tree will follow here. } function _insert(bytes32 _leaf) internal { // ... (insertion logic) } } ``` ## Preparing for Tree Initialization with Zero Values With the tree depth set and validated in the constructor, the next critical step is to initialize the Merkle tree itself. For an Incremental Merkle Tree, this typically involves: 1. **Initializing the tree with zeros:** This means pre-calculating the hash values for an empty tree structure up to its root. For example, the leaves would be a default "zero value," and these would be hashed pairwise up the levels to determine the initial root of an empty tree. 2. **Precomputing zero subtrees:** We need to compute and store the Merkle roots of subtrees of various heights that are entirely composed of these zero values (e.g., `zeros[0]` is the hash of an empty leaf, `zeros[1]` is `hash(zeros[0], zeros[0])`, and so on). These precomputed "zero hashes" are essential for efficiently inserting new, actual leaves into a partially filled tree. When a new leaf is added, and its sibling is an empty slot, the corresponding precomputed zero hash is used for the Merkle path calculation. 3. **Storing the initial root:** The root hash of this initially zero-filled tree will be stored in a state variable. This root will change as new commitments are inserted. These initialization steps, which will be detailed in a subsequent lesson, are crucial for the correct and efficient operation of the Incremental Merkle Tree. They ensure that we can correctly calculate Merkle proofs and update the tree root as new leaves are added.