Privacy in Web3 is often seen as a "black box" of complex zero-knowledge proofs. However, the heart of most privacy protocols like Tornado Cash is a much older and simpler structure: the Merkle Tree.
Recently, while building a research-based ETH Mixer, I ran into a classic synchronization issue between on-chain verification and off-chain proof generation. Here is what I learned about Merkle Tree stability and how to avoid the "Invalid Proof" trap.
The Architecture
The goal was simple:
Deposit: A user sends 1 ETH and a hash (commitment).
Mix: The commitment is added to a Merkle Tree.
Withdraw: The user provides a Merkle Proof to withdraw 1 ETH to a new address without revealing the original deposit.
The Pitfall: Sorted Hashes
Initially, I used a sorted-hash Merkle Tree. In this approach, nodes are sorted before hashing:
Solidity
// Vulnerable logic for manual proof generation
computedHash = a <= b ? keccak256(abi.encodePacked(a, b)) : keccak256(abi.encodePacked(b, a));
The Problem: While this saves some gas on-chain (you don't need to pass "left/right" flags), it makes manual proof generation in a test environment a nightmare. If even one leaf changes or is empty (bytes32(0)), the entire path's sorting can flip.
In my Foundry tests, I kept getting Invalid Merkle proof because my off-chain proof generator couldn't perfectly sync with the contract's sorting logic for empty slots.
The Fix: Index-Based Stability
I refactored the protocol to use a Deterministic Indexed Tree. Instead of sorting by value, we use the leaf's index to determine its position.
Even Index: You are the Left child.
Odd Index: You are the Right child.
Solidity
// Stable verification logic
if (index % 2 == 0) {
computedHash = keccak256(abi.encodePacked(computedHash, proofElement));
} else {
computedHash = keccak256(abi.encodePacked(proofElement, computedHash));
}
index /= 2;
Lessons for Security Researchers
Predictability over Gas (sometimes): Sorting saves a few hundred gas, but increases the risk of integration bugs between the frontend and the smart contract.
The "Empty Leaf" Trap: Always be consistent with how you handle padding. Using bytes32(0) for empty leaves is standard, but your proof generator must mirror this exactly.
Foundry is a lifesaver: Using forge test -vv allowed me to trace the hash updates step-by-step and find exactly where the test and the contract diverged.
Check out the Code
You can find the full implementation, including the fixed test suite and the Post-Mortem, in my repository:
👉 github.com/rdin777/merkle-mixer-research
#solidity #blockchain #web3 #security #foundry
Top comments (0)