> For the complete documentation index, see [llms.txt](https://zokyo-auditing-tutorials.gitbook.io/zokyo-tutorials/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zokyo-auditing-tutorials.gitbook.io/zokyo-tutorials/tutorial-16-zero-knowledge-zk/bugs-in-the-wild/zk-kit-missing-smart-contract-range-check.md).

# Zk-Kit: Missing Smart Contract Range Check

{% hint style="info" %}
[**Book an audit with Zokyo**](https://www.zokyo.io/)
{% endhint %}

**Summary**

Related Vulnerabilities: 3. [Arithmetic Over/Under Flows](/zokyo-tutorials/tutorial-16-zero-knowledge-zk/common-vulnerabilities-in-zk-code/arithmetic-over-under-flows.md)

Identified By: [PSE Security Team](https://twitter.com/PrivacyScaling)

The Zk-Kit smart contracts implement an [incremental merkle tree](/zokyo-tutorials/tutorial-16-zero-knowledge-zk/definitions-and-essentials/incremental-merkle-tree.md). 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](https://github.com/privacy-scaling-explorations/zk-kit/issues/23)
2. [Commit of the Fix](https://github.com/privacy-scaling-explorations/zk-kit/pull/24)


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://zokyo-auditing-tutorials.gitbook.io/zokyo-tutorials/tutorial-16-zero-knowledge-zk/bugs-in-the-wild/zk-kit-missing-smart-contract-range-check.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.