CODESPECT audited a Cairo-based privacy mixer on Starknet, inspired by Tornado Cash. It uses zero-knowledge proofs to break the on-chain link between depositor and recipient.
I (Talfao) audited the protocol together with my colleague Kalogerone as part of CODESPECT's security assessment. Among the findings identified during the review, one issue stood out due to its potential impact on withdrawals under certain edge conditions.
How Protocol Works (In Brief)
When a user deposits, their commitment is inserted as a leaf into a Merkle tree. The tree root is stored on-chain. To withdraw privately, the user generates a ZK proof off-chain demonstrating that their deposit exists in the tree. The proof is then verified on-chain, and funds are sent to a recipient without revealing the original depositor.
The proof is cryptographically tied to the Merkle tree state. If the structure of the tree changes in an unexpected way, previously generated proofs may no longer validate.
The Vulnerability: Merkle Tree Capacity Handling
The Pool contract initializes its Merkle tree with depth 10:
self.levels.write(10);
A tree with depth 10 can contain 1,024 deposits. However, the contract did not explicitly enforce this limit during insertion.
Once the deposit index reaches 1,024 (the 1,025th deposit), the insert() logic begins reusing intermediate nodes in a way that conflicts with earlier paths in the tree. Specifically, subtree[0] is updated again even though the new leaf belongs to a different branch of the tree.
This results in a situation where the internal structure of the tree no longer corresponds to the original insertion paths.
A Concrete Example
| Step | State |
|---|---|
| Initial | User A deposits at index 0. subtree[0] is set based on their commitment. |
| 1,023 more deposits | The tree reaches its designed capacity. |
| Deposit at index 1,024 | insert() updates subtree[0] again as part of the new insertion path. |
| User A attempts withdrawal | Their proof references the earlier Merkle path derived from the original tree state. |
| Result | The proof no longer validates against the updated tree state, preventing withdrawal. |
Importantly, the 1,025th deposit transaction succeeds normally and does not produce an explicit error or warning.
Why This Matters for Privacy Mixers
In many protocols, issues affecting withdrawals can potentially be mitigated through governance actions or upgrades. Privacy mixers introduce additional constraints because users are intentionally anonymous.
If a deposit becomes unwithdrawable due to an unexpected state change, identifying and compensating the affected user may be significantly more difficult. This makes the correctness of the underlying data structures particularly important.
The Fix
The issue was addressed by replacing the tree implementation with a lazy tower data structure, following the reference approach used in the Solidity implementation of Tornado Cash.
This structure ensures that insertions remain consistent even as the tree grows, and avoids overwriting intermediate nodes in a way that could invalidate earlier paths.
Lessons for Auditors and Developers
1. Always enforce Merkle tree capacity limits.
Even when the theoretical capacity is known, it is important to ensure the implementation enforces it at runtime.
2. Consider protocol-specific recovery constraints.
In privacy-preserving systems, user anonymity can limit the ability to remediate issues after deployment.
3. Test boundary conditions explicitly.
Edge cases such as capacity − 1, capacity, and capacity + 1 are particularly valuable for uncovering structural issues in data structures.
4. Successful execution does not always imply correctness.
Transactions may complete without reverting while still introducing unintended state changes.
Conclusion
The Merkle tree is a foundational component of privacy mixers, enabling deposits to be proven without revealing identities. As this case illustrates, subtle edge conditions in its implementation can have significant downstream effects on proof validity.
The issue highlights the importance of carefully validating assumptions about core data structures, particularly in systems where recovery options may be limited.
This issue was identified by Talfao and Kalogerone as part of CODESPECT's security assessment of the Typhoon Mixer protocol. The full audit report is available here. For smart contract security audits, reach out to CODESPECT.