identiPay uses an incremental Merkle tree to track note commitments in the shielded pool. The tree uses Poseidon hashing for compatibility with ZK circuits and implements the “filled subtrees” optimization for O(depth) insertion without storing all nodes.
fun insert_leaf<T>(pool: &mut ShieldedPool<T>, leaf: u256): u256 { let mut current_index = pool.next_leaf_index; let mut current_hash = leaf; let depth = pool.tree_depth as u64; // Precompute zero hashes for each level let mut zero_hashes = vector[]; let mut zh = zero_leaf(); // 0u256 let mut i = 0; while (i < depth) { zero_hashes.push_back(zh); zh = hash_pair(zh, zh); // Poseidon(zh, zh) i = i + 1; }; i = 0; while (i < depth) { if (current_index % 2 == 0) { // Left child: sibling is the zero hash at this level. // Update filled_subtrees since this left subtree is now the latest. *pool.filled_subtrees.borrow_mut(i) = current_hash; current_hash = hash_pair(current_hash, *zero_hashes.borrow(i)); } else { // Right child: sibling is the stored filled subtree (left neighbor). let left = *pool.filled_subtrees.borrow(i); current_hash = hash_pair(left, current_hash); }; current_index = current_index / 2; i = i + 1; }; current_hash // New root}
These are precomputed during initialization (shielded_pool.move:80):
entry fun create_pool<T>(ctx: &mut TxContext) { let mut filled = vector[]; let mut current_zero = zero_leaf(); let mut i = 0; while (i < (DEFAULT_TREE_DEPTH as u64)) { filled.push_back(current_zero); current_zero = hash_pair(current_zero, current_zero); i = i + 1; }; let pool = ShieldedPool<T> { // ... merkle_root: current_zero, // Initial root = Z[20] filled_subtrees: filled, // ... }; transfer::share_object(pool);}
Initial root: Z[20] (hash of completely empty tree)
To withdraw from the shielded pool, users need a Merkle proof that their commitment exists in the tree.Off-chain indexer (not shown in provided code, but required for production):
interface MerkleProof { pathElements: bigint[]; // Sibling hashes (depth elements) pathIndices: number[]; // 0 = left, 1 = right (depth elements)}function getMerkleProof( commitments: bigint[], // All leaves in tree leafIndex: number, // Index of target leaf depth: number // Tree depth): MerkleProof { const pathElements: bigint[] = []; const pathIndices: number[] = []; let currentIndex = leafIndex; for (let level = 0; level < depth; level++) { const isRightChild = currentIndex % 2 === 1; const siblingIndex = isRightChild ? currentIndex - 1 : currentIndex + 1; // Get sibling hash (or zero hash if beyond current tree size) const sibling = siblingIndex < commitments.length ? computeHashAtIndex(commitments, siblingIndex, level) : getZeroHash(level); pathElements.push(sibling); pathIndices.push(isRightChild ? 1 : 0); currentIndex = Math.floor(currentIndex / 2); } return { pathElements, pathIndices };}
pathElements = [L3, H1, H23] (siblings at each level)
pathIndices = [0, 0, 0] (L2 is left child at all levels)
Verification:
Level 0: H2 = Poseidon(L2, L3) (L2 is left, L3 is right)
Level 1: H01 = Poseidon(H0, H1) … wait, we need H0!
Correction: The example above is incomplete. A full depth-20 proof requires 20 sibling hashes. The exact path depends on the tree state when the commitment was inserted.
See Pool Spend Circuit for a complete proof generation/verification example.
Given a commitment C and its Merkle proof, can an attacker find a different commitment C' with the same root?Answer: No, assuming Poseidon second preimage resistance. Changing any leaf propagates to the root via different hash inputs.
Can an attacker observe a pending deposit and frontrun it with their own?Impact: Minimal. Even if frontrun, the original deposit still succeeds (just at a later leaf index). The attacker gains no advantage.
#[test]fun test_merkle_insertion() { let mut ctx = tx_context::dummy(); create_pool<SUI>(&mut ctx); let mut pool = /* get pool */; // Insert first leaf let leaf1 = 12345u256; let root1 = insert_leaf(&mut pool, leaf1); // Verify root changed assert!(root1 != pool.merkle_root); // Root updated // Insert second leaf let leaf2 = 67890u256; let root2 = insert_leaf(&mut pool, leaf2); // Verify root changed again assert!(root2 != root1);}
Currently, each deposit inserts one leaf. For high-throughput scenarios, consider batching:
// NOT IMPLEMENTED - pseudocodeentry fun batch_deposit<T>( pool: &mut ShieldedPool<T>, commitments: vector<u256>, coins: vector<Coin<T>>, // ...) { let n = commitments.length(); let mut i = 0; while (i < n) { // Process deposits... i = i + 1; }; // Single root update at the end pool.merkle_root = final_root;}
