> 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/dark-forest-v0.3-missing-bit-length-check.md).

# Dark Forest v0.3: Missing Bit Length Check

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

**Summary**

Related Vulnerabilities: 1. [Under-constrained Circuits](/zokyo-tutorials/tutorial-16-zero-knowledge-zk/common-vulnerabilities-in-zk-code/under-constrained-circuits.md), 2. [Nondeterministic Circuits](/zokyo-tutorials/tutorial-16-zero-knowledge-zk/common-vulnerabilities-in-zk-code/nondeterministic-circuits.md), 3. [Arithmetic Over/Under Flows](/zokyo-tutorials/tutorial-16-zero-knowledge-zk/common-vulnerabilities-in-zk-code/arithmetic-over-under-flows.md), 4. [Mismatching Bit Lengths](/zokyo-tutorials/tutorial-16-zero-knowledge-zk/common-vulnerabilities-in-zk-code/mismatching-bit-lengths.md)

Identified By: [Daira Hopwood](https://github.com/daira)

A *RangeProof* circuit was used to prevent overflows. However, it used the CircomLib [*LessThan*](https://github.com/iden3/circomlib/blob/master/circuits/comparators.circom#L89) circuit to ensure this, which expects a maximum number of bits for each input. The inputs did not have any constraints on the number of bits, so an attacker could use large numbers to achieve a successful *RangeProof* even though the number was out of range.

**Background**

Dark Forest,, had a missing bit length check from its early circuits. In order to prevent underflows their circuit included a *RangeProof* template to ensure that an input is within bounds to prevent an overflow.

```
// From darkforest-v0.3/circuits/range_proof/circuit.circom
template RangeProof(bits, max_abs_value) {
    signal input in;

    component lowerBound = LessThan(bits);
    component upperBound = LessThan(bits);

    lowerBound.in[0] <== max_abs_value + in;
    lowerBound.in[1] <== 0;
    lowerBound.out === 0

    upperBound.in[0] <== 2 * max_abs_value;
    upperBound.in[1] <== max_abs_value + in;
    upperBound.out === 0
}
```

The *LessThan* template compares two inputs, and outputs 1 if the first input is less than the second input. In the *RangeProof* circuit, the *LessThan* circuit is essentially used as a GreaterEqThan, requiring that the output is 0. The *LessThan* template takes in the max number of bits for both inputs as a parameter, but does not actually check this constraint.

```
// From circomlib/circuits/comparators.circom
template LessThan(n) {
    assert(n <= 252);
    signal input in[2];
    signal output out;

    component n2b = Num2Bits(n+1);

    n2b.in <== in[0]+ (1<<n) - in[1];

    out <== 1-n2b.out[n];
}
```

**The Vulnerability**

Therefore, in the *RangeProof* example the *LessThan* circuit is used with an expected maximum number of bits, but the inputs *max\_abs\_value* and *in* are never constrained to that number. An attacker could input *max\_abs\_value* and *in* values that contain more bits than the expected max. Since *LessThan* is expecting the two inputs to have a maximum number of bits, it may output an incorrect result. An attacker would be able to satisfy the *RangeProof* even though the input is out of range.

**The Fix**

In order to prevent this attack, a check was needed on the number of bits of *max\_abs\_value* and *in*. They must be constrained to \*bits \*\*\*\*\*(the template input parameter) number of bits. The following is the implemented fix in production:

```
// From darkforest-eth/circuits/range_proof/circuit.circom

// NB: RangeProof is inclusive.
// input: field element, whose abs is claimed to be <= than max_abs_value
// output: none
// also checks that both max and abs(in) are expressible in `bits` bits
template RangeProof(bits) {
    signal input in;
    signal input max_abs_value;

    /* check that both max and abs(in) are expressible in `bits` bits  */
    component n2b1 = Num2Bits(bits+1);
    n2b1.in <== in + (1 << bits);
    component n2b2 = Num2Bits(bits);
    n2b2.in <== max_abs_value;

    /* check that in + max is between 0 and 2*max */
    component lowerBound = LessThan(bits+1);
    component upperBound = LessThan(bits+1);

    lowerBound.in[0] <== max_abs_value + in;
    lowerBound.in[1] <== 0;
    lowerBound.out === 0

    upperBound.in[0] <== 2 * max_abs_value;
    upperBound.in[1] <== max_abs_value + in;
    upperBound.out === 0
}
```

**Conclusion**

1. **The Problem with RangeProof**:
   * The RangeProof circuit's goal is to ensure that a given input number (let's call it `in`) doesn't exceed a certain maximum absolute value (`max_abs_value`).
   * To achieve this, the RangeProof circuit utilized a module named `LessThan` from the CircomLib library.
   * The problem arose because `LessThan` was designed to work with numbers of a certain bit length, but the RangeProof didn't ensure that the numbers it received respected that bit length. This means that, with clever input, a malicious actor could make the `LessThan` function return an incorrect result, which would then allow an out-of-range number to be mistakenly approved by the RangeProof.
2. **The Specifics of `LessThan`**:
   * The `LessThan` module is pretty straightforward. It compares two numbers and outputs 1 if the first number is smaller than the second.
   * Here’s the trick: `LessThan` is designed to work with numbers of a certain maximum bit length (specified as `n`). If the numbers have more bits than that, the function will not behave correctly.
3. **How This Can Be Exploited**:
   * Without constraints on the inputs' bit lengths, an attacker can input numbers for `max_abs_value` and `in` that have more bits than the LessThan function expects.
   * This can cause the LessThan function to return an incorrect result, allowing the attacker to satisfy the RangeProof even if the number is actually out of range.
4. **The Fix**:
   * To address this vulnerability, the developers added constraints on the bit lengths of the inputs (`max_abs_value` and `in`). They ensured that these inputs have a bit length that aligns with what the `LessThan` function expects.

The described vulnerability has to do with a weakness in the constraint system of a zero-knowledge proof, specifically related to the `RangeProof` that ensures an input number is within a certain range. Let's unpack the implications and potential attacks:

1. **The Purpose of RangeProof**: The primary purpose of a `RangeProof` is to prove that a particular number lies within a certain range without revealing the exact number. In this context, it's crucial to ensure that the proof is bulletproof, because if an attacker can convince a verifier that a number lies within a range when it actually doesn't, it can break the integrity of the whole system.
2. **Potential Attack**: If an attacker can feed the `LessThan` function with numbers that have more bits than expected, they might get the function to output an incorrect result. This could potentially allow an attacker to submit an out-of-range number while still producing a valid `RangeProof`—effectively lying about the number being within the range.
3. **Implications**: Let's use an analogy. Imagine a secured gate that only allows cars of a certain size to pass through. If someone found a way to trick the gate's sensor into allowing larger vehicles, they could potentially smuggle unauthorized or dangerous items. Similarly, if the `RangeProof` is not robust, it could lead to unauthorized or malicious transactions, a breach of privacy, or other unwanted outcomes, depending on the application.
4. **Why It's a Big Issue**:
   * **Trust**: In cryptographic systems, especially ones like zero-knowledge proofs, trust is paramount. If there's a vulnerability that allows someone to produce a misleading proof, it undermines the whole system.
   * **Financial Implications**: Many zero-knowledge systems, including zk-SNARKs, are used in financial systems like certain blockchain implementations. If an attacker can misrepresent a transaction, they might be able to steal or double-spend funds.
   * **Privacy Breach**: ZK systems often handle sensitive data. A vulnerability could lead to a breach of privacy or unauthorized data access.
   * **Integrity of Computation**: In some systems, ensuring a value is within a certain range might be critical for other computations. If an out-of-bounds value is introduced, it could lead to unexpected behaviors or errors elsewhere in the system.

**References:**

1. [ZKPs for Engineers: A look at the Dark Forest ZKPs](https://blog.zkga.me/df-init-circuit) (See the “Bonus 1: Range Proofs” section)
2. [Commit of the Fix](https://github.com/darkforest-eth/circuits/commit/1b5c8440a487614d4a3e6ed523df0aee71a05b6e#diff-440e6bdf86d42398f40d29b9df0b9e6992c6859194d2a7f3c8c68fb46d0f2040)


---

# 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/dark-forest-v0.3-missing-bit-length-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.