🔫Zk-Kit: Missing Smart Contract Range Check

Book an audit with Zokyo

Summary

Related Vulnerabilities: 3. Arithmetic Over/Under Flows

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 zk 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");

Conclusion :

1. Initialization of the Merkle Tree: To set up the merkle tree, an initial value for the tree's "zero leaf" must be specified.

2. Overflow Risk with uint256: Solidity’s uint256 can accommodate numbers larger than the snark scalar field order. If someone initializes the merkle tree's zero leaf with a value exceeding this scalar field order, it can cause arithmetic overflows. This overflow becomes problematic, especially if the zero leaf is part of a merkle tree inclusion proof necessary for a zk proof.

let's delve deeper into why proofs would be invalid when the values are greater than the snark scalar field order.

Zero-knowledge proofs, particularly those like zk-SNARKs (Succinct Non-Interactive Arguments of Knowledge), have a mathematical structure that relies heavily on the arithmetic in a particular finite field. A finite field is a set with a limited number of elements where arithmetic operations (addition, multiplication, etc.) wrap around upon reaching a certain number, similar to a clock that wraps around after 12 hours. In the case of zk-SNARKs, this number is the "snark scalar field order."

1. Scalar Field Arithmetic: When we perform arithmetic for zk proofs, all computations happen within this finite field. This is important because it means all numbers used in the computation must be less than the scalar field order.

2. Overflow and Wrapping Around: If you have a number equal to or larger than the scalar field order, it effectively wraps around and becomes a much smaller number. So, an operation involving such a number won't produce the expected result because the number used in the arithmetic is not the large number you thought but rather its "wrapped around" small counterpart.

3. Merkle Tree and Zero-knowledge Proofs: In your provided context, the Merkle tree (from Zk-Kit) plays a vital role in constructing zk proofs. When constructing or verifying a zk proof, a prover or verifier may need to use Merkle tree values to perform certain operations. If a value from the tree, especially the foundational zero leaf, is larger than the scalar field order, it will "wrap around" during any computation. This inconsistency makes the result of the computation different from what it would be if the value were within the correct range. Hence, the proof will be based on incorrect computations and, therefore, will be invalid.

4. Semaphore's Use Case: If the identityCommitment in the Merkle tree has a zero leaf that's too large, then any zk proof involving that commitment could produce incorrect results due to the aforementioned overflow. As a result, a user trying to prove their membership in the Semaphore system would produce a proof that the system sees as invalid—even if the user is a legitimate member.

References

1. Reported Github Issue
2. Commit of the Fix