Zk-Kit: Missing Smart Contract Range Check
Zk-Kit: Missing Smart Contract Range Check
Identified By: PSE Security Team
The Zk-Kit smart contracts implement an incremental merkle tree. The intent is for this merkle tree to be involved with zero-knowledge proofs, so all values must be less than the snark scalar field order in order to prevent overflows.
Background
Semaphore is the first consumer of the Zk-Kit merkle tree implementation. When members sign up via the Semaphore smart contracts, they use an identityCommitment that is stored in the on-chain Zk-Kit merkle tree. The zero knowledge proof will then prove that they have a valid commitment in the tree.
The Vulnerability
When initializing the merkle tree, you must specify a value for the zero leaf:
// From zk-kit/incremental-binary-tree.sol/contracts/IncrementalBinaryTree.sol
// before the fix
function init(
IncrementalTreeData storage self,
uint8 depth,
uint256 zero
) public {
require(depth > 0 && depth <= MAX_DEPTH, "IncrementalBinaryTree: tree depth must be between 1 and 32");
self.depth = depth;
for (uint8 i = 0; i < depth; i++) {
self.zeroes[i] = zero;
zero = PoseidonT3.poseidon([zero, zero]);
}
self.root = zero;
}
Since the Solidity uint256 allows for numbers greater than the snark scalar field order, a user could unknowingly initialize a merkle tree with the zero leaf value greater than the snark scalar field order. This will also directly cause overflows if the zero leaf is part of a merkle tree inclusion proof needed for a zk proof.
The Fix
During initialization, it must be enforced that the given zero leaf value is less than the snark scalar field order. To enforce this, the following require statement was added to the init function:
// From zk-kit/incremental-binary-tree.sol/contracts/IncrementalBinaryTree.sol
// after the fix
require(zero < SNARK_SCALAR_FIELD, "IncrementalBinaryTree: leaf must be < SNARK_SCALAR_FIELD");
Related Vulnerabilities:
Arithmetic Over/Under Flow vulnerability