Era
ZKsync
FoundryLayer 2
500,000 USDC
View results
Previous Next
Submission Details
Severity: medium
Valid

Path Length Validation Bug Breaks Single-Node Merkle Tree Security Guarantees

cheatc0d33

Summary

The Merkle library in ZKSync's core protocol contains a critical validation issue that prevents verification of minimal but valid Merkle tree states. At the heart of the vulnerability is a well-intentioned but overly restrictive check in _validatePathLengthForSingleProof:

https://github.com/Cyfrin/2024-10-zksync/blob/cfc1251de29379a9548eeff1eea3c78267288356/era-contracts/l1-contracts/contracts/common/libraries/Merkle.sol#L125C26-L125C27

function _validatePathLengthForSingleProof(uint256 _index, uint256 _pathLength) private pure {
if (_pathLength == 0) {
revert MerklePathEmpty();
}
// ...
}

This validation unconditionally rejects empty Merkle paths - a decision that breaks the foundational mathematics of Merkle trees. By definition, a single-node Merkle tree (height = 0) is a valid construction where the leaf hash is identical to the root hash, requiring no proof path since no siblings exist to prove against. The current implementation makes it impossible to represent this state, despite it being both mathematically valid and practically necessary.

This limitation propagates through the ZKSync ecosystem in subtle but dangerous ways. Systems built on this library, like token distribution contracts or state transition verifiers, are forced into one of three harmful patterns:

  1. Creation of synthetic proof paths using dummy nodes, wasting gas and complicating verification

  2. Implementation of parallel verification logic specifically for single-node states, fragmenting security-critical code

  3. Complete bypass of Merkle verification for initial states, potentially missing important security checks

What makes this particularly concerning is that the same codebase correctly handles single-node trees in its batch verification path through calculateRootPaths. This inconsistency suggests the restriction wasn't a deliberate security decision but rather an oversight that made it through multiple audits.

Proof of Concept

The vulnerability manifests most clearly in the initialization phase of Merkle-based systems. Consider a standard merkle airdrop contract:

contract MerkleAirdrop {
using Merkle for bytes32;
bytes32 public merkleRoot;
mapping(address => bool) public claimed;
function seedInitialGrant(address recipient, uint256 amount) external {
require(merkleRoot == bytes32(0), "Already initialized");
// Create leaf for single grant
bytes32 leaf = keccak256(abi.encode(recipient, amount));
// PROBLEMATIC: Cannot use standard verification path for initial state
// Option 1: Bypass Merkle verification entirely (dangerous)
merkleRoot = leaf;
// Option 2: Force dummy node (wasteful)
bytes32 dummyNode = bytes32(0);
bytes32[] memory dummyPath = new bytes32[]();
dummyPath[0] = dummyNode;
merkleRoot = Merkle.calculateRoot(dummyPath, 0, leaf);
}
function claim(bytes32[] calldata proof, uint256 index) external {
bytes32 leaf = keccak256(abi.encode(msg.sender, amount));
// Verification fails for valid single-node state
bytes32 root = Merkle.calculateRoot(proof, index, leaf);
require(root == merkleRoot, "Invalid proof");
require(!claimed[msg.sender], "Already claimed");
claimed[msg.sender] = true;
// Transfer tokens...
}
}

The issue becomes even more apparent when we look at how the same codebase handles batch verification:

function calculateRootPaths(
bytes32[] memory _startPath,
bytes32[] memory _endPath,
uint256 _startIndex,
bytes32[] memory _itemHashes
) internal pure returns (bytes32) {
// Correctly handles single node case
if (pathLength == 0 && (_startIndex != 0 || levelLen != 1)) {
revert MerklePathEmpty();
}
// ...
}

This inconsistency creates a footgun: developers seeing the batch verification work correctly might assume single proofs work the same way, leading to subtle vulnerabilities in production systems.

Recommended mitigation steps

The solution requires realigning the validation with Merkle tree mathematics while preserving the security properties of the current implementation. Here's a corrected implementation:

function calculateRoot(
bytes32[] calldata _path,
uint256 _index,
bytes32 _itemHash
) internal pure returns (bytes32) {
uint256 pathLength = _path.length;
// Handle mathematically valid single-node case
if (pathLength == 0) {
if (_index == 0) {
// Single node tree: leaf hash = root hash
return _itemHash;
}
// Still reject empty paths for non-zero indices
revert MerklePathEmpty();
}
// Existing bounds checking for multi-node trees
if (pathLength >= 256) {
revert MerklePathOutOfBounds();
}
if (_index >= (1 << pathLength)) {
revert MerkleIndexOutOfBounds();
}
​
bytes32 currentHash = _itemHash;
for (uint256 i; i < pathLength; i = i.uncheckedInc()) {
currentHash = (_index % 2 == 0)
? efficientHash(currentHash, _path[i])
: efficientHash(_path[i], currentHash);
_index /= 2;
}
return currentHash;
}

This fix harmonizes single-node and batch verification behaviors while maintaining strict validation for all other cases.

The change is fully backward compatible - existing multi-node proofs continue working exactly as before, while systems can now correctly handle single-node states without workarounds.

Updates

Lead Judging Commences

inallhonesty Lead Judge 7 months ago
Submission Judgement Published
Validated
Assigned finding tags:

Path Length Validation Bug Breaks Single-Node Merkle Tree Security Guarantees

Support

FAQs

Can't find an answer? Chat with us on Discord, Twitter or Linkedin.