Common Vulnerabilities in ZK Proof

📝Introduction

In this article, our aim is to explain in the simplest and most comprehensible language to Blockchain Security Researchers and ZK-cryptography Engineers about the typical vulnerabilities one might encounter when working with zk-based solutions.

Over the past few years, with the advancement of development tools, solutions built using ZK-cryptography have gained increasing popularity. Such solutions undoubtedly offer a wide range of benefits. However, like smart contracts, they also have vulnerabilities.

The situation is complicated by the fact that due to the relative novelty of the technology, the culture of security review and audit is still very underdeveloped. There are no universally accepted methodologies for auditing ZK solutions, and most identified vulnerabilities do not provide a full understanding of the general attack vector. Only top cryptographers and mathematicians undertake the task of auditing, and that too for a hefty fee.

Given the above, the need for producing materials on the security of ZK solutions becomes clear. Yes, perhaps the developers of these solutions are not always PhDs in Applied Mathematics and cannot independently take into account all security aspects, but they can follow basic recommendations that will help them avoid the most common mistakes during development.

This article serves as such a guide for regular developers. Let’s now look at the stages and conditions under which your zk-protocol might be vulnerable.

🔍1. Under-constrained and Non-Deterministic Circuits

Designing and building a ZK-protocol always involves working with circuits, as they are the fundamental building blocks from which the entire system is constructed. The challenge lies in the fact that these blocks often have varying shapes, which means the security of each needs to be considered separately. Let’s delve into what issues might arise when creating these “blocks”.

Context

Zero-Knowledge schemes consist of mathematical equations and logical conditions for them (these are the “constraints”), which are necessary to verify proofs without revealing the specific information used to generate them.

The vulnerability we’re discussing arises in situations where ZK-protocols lack the necessary constraints for proof creators (“provers”). This allows them to find and exploit loopholes in the rules governing the proving scheme.

If a ZK-scheme is insufficiently constrained, its integrity cannot be assured, as using unconstrained input values can be exploited by malicious actors to generate fake proofs, thereby compromising the scheme.

Abstract Example

Imagine we have a ZK-scheme designed to verify that a user knows a secret number s, which is the square root of a public number p. This implies that s * s = p.

Ideally, our scheme should ascertain that:

• The user genuinely knows s.
• s is indeed the square root of p.

Now, let’s assume our scheme lacks adequate constraints. For instance, it doesn’t demand that s always be a positive number. In this case, if p = 9, then s could be either 3 or -3. If our aim was to ensure the user knows the positive root, our scheme is under-constrained as it permits negative values of s.

With such a scheme, a malicious actor could produce a false proof of knowledge, even if they’re uncertain about which of the two values is the secret.

Specific Example

Let’s delve into a similar example written in circom. The task of the scheme below is to verify that the prover knows two secret factors (factorOne, factorTwo), not equal to one, whose product corresponds to the public parameter val.

pragma circom 2.0.0;

template NonIdentityFactors() {
 signal factorOne;
 signal factorTwo;
 signal val;

 val <== factorOne * factorTwo;
}

component main{public [val]} = Factors();

There are 3 problems with this scheme:

• It doesn’t check if the factors are not equal to one.
• It doesn’t ensure that the factor values are positive.
• It doesn’t ascertain that the product of the factors is less than the order of the scalar field.

The first problem allows one to simply input two ones as factors and generate a fake proof based on that.

The second issue permits the use of negative values for the original factors, allowing the generation of two proofs instead of one.

Understanding the third problem requires us to delve deeper into the concept of scalar fields in cryptography:

• Imagine we have a scalar field with an order of 100 (which is unrealistically small for real cryptography but will suffice for this example). If factorOne = 10 and factorTwo = 11, then factorOne * factorTwo = 110, which exceeds the order of the scalar field. In this context, if there’s no explicit constraint ensuring that the product of the factors is less than the order of the scalar field, the result might be incorrectly interpreted as 10. This is known as the “Wrap-Around” effect.
• Scalar fields are utilized as they eliminate this effect and exclude additional factor combinations whose product can yield the same result as the product of the original secret factors.

Thus, in the vulnerability we’ve examined, we can identify a subtype: Non-Deterministic Circuits. As some of you might have deduced, a non-deterministic circuit is such an Under-Constrained Circuit whose design flaws lead to the violation of the determinism principle. This manifests as the potential to generate multiple nullifiers for the same commitment, essentially triggering double-spending. Violating this principle doesn’t always result in a vulnerability but significantly elevates the uncontrollable entropy level of the ZK-protocol.

Issue summary

Just as smart contracts undergo audits and checks for known vulnerabilities, ZK-schemes should be regularly tested for “under-constrained” conditions. This might encompass automated testing, unit tests, and boundary condition testing.

2. Arithmetic Over/Under Flows

Context

This vulnerability arises due to the characteristics of mathematics over Prime Finite Fields and Scalar Fields. These types of fields have gained widespread use in Zero-Knowledge cryptography because they offer an excellent balance of cryptographic robustness, computational efficiency, compatibility with ZK-protocols, and a high degree of adaptability.

Prime Finite Fields are defined in the set {0; ... ;p-1}, where p is a prime number. Within these limits, operations like addition, subtraction, multiplication, and division (excluding division by zero) are defined and performed using mod p.

• Overflows occur when the result of an arithmetic operation exceeds the upper boundary of the allowable range (in this case, p−1).
• Underflows occur when the result falls below the lower boundary (in this instance, 0).

Semaphore case (double spend)

Let’s examine a real-world example of this vulnerability from the Semaphore project, which was uncovered by Roman Semyonov in 2019. Imagine that:

p = 21888242871839275222246405745257275088548364400416034343698204186575808495617

If one overlooks the fact that finite fields have boundaries, a bug will emerge where the following statements are true:

(0 - 1) === 21888242871839275222246405745257275088548364400416034343698204186575808495616;
(21888242871839275222246405745257275088548364400416034343698204186575808495616 + 1) === 0;

Since the computational result strictly lies within the range [0 ; p-1], then 0-1 will yield p-1, and vice versa.

Specific Example

To illustrate how this might look in code, let’s assume we have the following ZK-scheme:

pragma circom 2.0.0;

template getNewBalance() {
    signal input currentBalance;
    signal input withdrawAmount;
    signal output newBalance;

    newBalance <== currentBalance - withdrawAmount;
}

If a user inputs a “withdrawAmount” that is greater than their “currentBalance”, the output “newBalance” will underflow and represent an extremely large number close to p. Clearly, this isn’t what the scheme’s author intended.

To rectify this, we can add checks to ensure that the input data is within permissible bounds. We’ll use standard templates from the circom library to ensure that no inputs lead to unexpected outputs:

pragma circom 2.0.0;

template getNewBalance() {
    signal input currentBalance;
    signal input withdrawAmount;
    signal output newBalance;

    // Ensure that both values are positive.
    component n2b1 = Num2Bits(64);
    n2b1.in <== withdrawAmount;
    component n2b2 = Num2Bits(64);
    n2b2.in <== currentBalance;

    // Ensure that withdrawAmount <= currentBalance.
    component lt = LessThan(64);
    lt.in[0] = withdrawAmount;
    lt.in[1] = currentBalance + 1;

    lt.out === 1;

    newBalance <== currentBalance - withdrawAmount;
}

Here, Num2Bits(n) is used as a range check to ensure that the input data lies within [0, 2^n - 1], where n is the field size. Had we forgotten these range checks, a hacker could input a withdrawal amount equal to p-1, as in the first example.

3. Mismatching Bit Lengths

Context

To understand the upcoming vulnerability, let’s consider the ZK-scheme below, designed to check if one input is lesser than the other.

pragma circom 2.0.0;

template LessThan(n) {
    // Protection against the use of ineffective inputs.
    assert(n <= 252);
    // Array of numbers to compare: in[0] and in[1].
    signal input in[2];
    // Result of comparing: true(1) or false(0).
    signal output out;

    // 1)Numeric value -> binary representation;
    // 2)Use extra bit for overflow protection.
    component n2b = Num2Bits(n+1);

    // 1)Add 2^n to in[0] -> assert that the result is always positive;
    // 2)Find delta between in[0] and in[1];
    // 3)Represent result as binary boolean value.
    n2b.in <== in[0] + (1<<n) - in[1];

    // 1)Take the result of n2b.in (can be 0 or 1);
    // 2)Substract it from 1;
    // 3)Write result as output.
    out <== 1 - n2b.out[n];
}

The result of the LessThan check is given as a binary signal output:

• First input is less than the second | out = 1
• First input is greater than the second | out = 0

While the scheme does work, without additional checks, it’s vulnerable to mismatches in the bit length of the input values. Let’s explore how one can exploit this scheme.

Attack scenario

The main idea behind the attack is to leverage the absence of checks for inputs. An attacker can provide inputs with different bit lengths (i.e., the number of bits required to represent the number in binary).

This will cause an underflow at the Num2Bits input, allowing the output to be constructed as 0, even if in[0] < in[1]. Now, let’s try this with numbers.

Suppose n = 3. This means the expected inputs in[0] and in[1] should be 3-bit numbers, i.e., within the range of 0 to 7. However, an attacker might attempt to feed a number that has more than n bits.

Attacker inputs

• in[0] = 1 (001 in binary)
• in[1] = 9 (1001 in binary)

When calculating the value in[0] + (1<<n) - in[1], it is anticipated that the result will always be non-negative. But, if in[1] has more than n bits, the outcome could very well be negative.

Result processing

1. n2b.in <== 1 + (1<<3) - 9 // (1<<3) is 1*(2^3)
2. n2b.in <== 1 + 8 - 9
3. n2b.in <== 0 // Result says that 1 > 9, which is a bug

Vulnerability mitigation

The vulnerability discussed in the presented scenario is addressed by incorporating additional bit-length checks of the input data into the scheme. This ensures they match the expected range and do not result in erroneous computations and unexpected behavior.

This can be achieved through the integration of Num2Bits scheme instances:

1. Both input1 and input2 are constrained to maxBits bits. This ensures the input data won’t exceed the anticipated bit length, thus preventing unforeseen behavior.
2. The inputs are then passed to the revised LessThan(maxBits) template, where maxBits represents the maximum number of bits that can be represented in the input data.

pragma circom 2.0.0;

template ProtectedComparison {
    signal input1;
    signal input2;
    signal maxBits;

    // Constrain input1 to maxBits
    component bitCheck1 = Num2Bits(maxBits);
    bitCheck1.in <== input1;
    // Constrain input2 to maxBits
    component bitCheck2 = Num2Bits(maxBits);
    bitCheck2.in <== input2;

    // Compare input1 to input2
    component lt = LessThan(maxBits);
    lt.in[0] <== input1;
    lt.in[1] <== input2;

    // Ensure input1 < input2
    lt.out === 1;
}

It’s crucial to understand that theoretically, unconstrained inputs can lead to other types of problems:

• Incorrect computation results
• Exceeding permissible value boundaries
• Inability to create proof

Hence, when designing circuits, an effort should be made to consider as many attack scenarios as possible in order to embed additional safeguards.

4. Unused Public Inputs Optimized Out

Context

This vulnerability pertains to situations where specific public inputs of a ZK-scheme are not utilized in any constraints, rendering them invisible to the optimizer during the compilation of the DSL program into R1CS.

An optimizer is a tool or a component of the compiler that aims to simplify the scheme and reduce the number of constraints that need to be checked during the proof verification. This is crucial since the size and complexity of the scheme directly influence the efficiency and performance of the Zero-Knowledge proof creation and verification processes.

Abstract Example

To analyze this type of vulnerability, consider the following code segment:

pragma circom 2.0.0;

component UnusedPubInput() {
 signal inOne;
 signal inTwo;
 signal inThree;

 signal output out;

 out <== inOne + inTwo;
}

component main{public [inThree]} = UnusedPubInput()

As can be seen, the public input inThree is not involved in any constraint. The optimizer might entirely exclude it from the final scheme since it doesn’t affect computations or proof verifications. This leaves room for potential abuse since the proof can be successfully generated with any value of inThree.

At first glance, this situation might not seem too dangerous. However, for some protocols, such as Tornado Cash and Semaphore, the presence of such a vulnerability can lead to critical errors. Let’s see how this vulnerability might lead to a hack in the Semaphore protocol’s logic.

Attack Scenario

Semaphore is a zero-knowledge-based application that allows users to prove their membership in a specific group and send signals without revealing their identity. In the Semaphore context, a “signal” is any message or data a user wishes to transmit while maintaining anonymity.

The hashed signal a user wishes to send acts as the public input susceptible to the described vulnerability. Since the input holding this signal is ignored by the optimizer, a situation might arise where, with the same verified inputs, one can generate any number of valid proofs with different signal hashes. Such a scenario explicitly violates the protocol’s working logic and is a critical vulnerability.

Vulnerability Mitigation

To mitigate this problem, one only needs to make the optimizer stop ignoring variables not used in the main logic. To do this, one can simply add mock logic that the optimizer will recognize as valid. Here’s how it might be implemented in the Tornado Cash code:

// Add hidden signals to make sure that tampering with recipient or fee will invalidate the SNARK proof.
// Most likely it is not required, but it's better to stay on the safe side and it only takes 2 constraints.
// Squares are used to prevent optimizer from removing those constraints.
signal recipientSquare;
signal feeSquare;
signal relayerSquare;
signal refundSquare;

recipientSquare <== recipient * recipient;
feeSquare <== fee * fee;
relayerSquare <== relayer * relayer;
refundSquare <== refund * refund;

5. Frozen Heart: Forging of Zero Knowledge Proofs

This vulnerability has such an unusual name because it lies at the very heart of the protocols susceptible to it — the implementation of the Fiat-Shamir transformation mechanism that turns interactive protocols into non-interactive ones. The original name belongs to the security researchers of the Trail of Bits company.

This vulnerability is too complex and generalized to be fully disclosed within this article, so we will provide only a general description, as most ZK-engineers need to be at least simply aware of its existence.

The essence of it is that the Fiat-Shamir transformations are often implemented from scratch based on the original scientific publication where this mechanism was first introduced. As one can guess, these works lack practical recommendations and warnings about potential pitfalls or vulnerabilities when implemented in real code.

This issue closely resembles the use of custom library curves and ERC standards in traditional blockchain development. However, here, identifying problematic areas becomes an even more challenging task for an ordinary engineer.

As a solution to this problem, one can look at the advice given in the Trail of Bits supported project ZK Docs. Also, one can study audited implementations in more detail and cautiously take pieces of code from them if the source code is public.

6. Trusted Setup Leak

Every designed zk-protocol begins with a procedure known as the trusted setup if it’s built on the SNARK-like proving systems (It’s worth noting that ZK-STARK and Bulletproof systems do not require a trusted setup at all).

Trusted Setup mechanism

A universal trusted setup is required to generate public and private parameters. Through these parameters, the prover can create a reliable proof for the verifier that they have information about a secret polynomial, which allows them to pass the verification any number of times.

However, during the universal trusted setup, certain parameters, referred to as “toxic waste,” must be destroyed upon its completion. Incorrect disposal of this toxic waste could allow hackers the ability to forge fake proofs without knowing the witness. To efficiently dispose of the toxic waste, Multi-Party Computation (MPC) is often used during the setup. As long as at least one participant disposes of their data portion after the process, the undesirable parameters become irrecoverable.

It’s essential to note that some earlier proving systems, like Groth16 and Pinnochio, required a trusted setup for every new circuit. This type of setup is called a Common Trusted Setup, while MPC is used in the Universal Trusted Setup.

Vulnerability in Practice

To understand the potential problems arising from insufficient disposal of toxic waste, let’s examine a real-life vulnerability in the Zcash protocol discovered in 2018.

The Zcash algorithm for generating public and private parameters, BCTV-14, produces additional parameters during its operation that violate the soundness of the proving system.

In the Zero-Knowledge protocol context, soundness ensures that a dishonest prover cannot convince the verifier of the truthfulness of a false statement. This principle ensures that if a statement is false, the likelihood of its acceptance by the verifier is minimal and can be practically reduced to zero by adjusting the protocol parameters.

BCTV-14 is a custom implementation of the snark-scheme PGHR13, modified for performance and adaptation for the asymmetric pairing setting.

During the key generation for the prover and verifier, polynomial operations result in specific variables being recorded. These variables, unused thereafter, are considered toxic waste since they can be harnessed to create fake proofs.

Typically, such dangerous variables are intentionally deleted. However, in Zcash’s case, due to inadequate control, they were recorded in the MPC ceremony transcript. As a result, anyone with access to this transcript could create fake proofs. To mitigate this vulnerability, Zcash had to release an update for the Sapling Network, transitioning the protocol to the Groth16 proving system, for which a safe Sapling Ceremony was conducted.

7. Assigned but not Constrained

One common pitfall in zk-protocol development is the misunderstanding between merely declaring inputs in the ZK-circuit logic and setting constraints for these inputs.

Context

Assignments are mere variable declarations that don’t add any restrictions that need to be met to generate a valid proof.

Constraints, on the other hand, are mathematical equations that set conditions the inputs must satisfy after being subjected to the mathematical operations defined in the circuit’s logic. Essentially, they add equations to the R1CS file. If the outcome of applying the defined mathematical operations to the inputs isn’t as expected, it implies that the prover doesn’t know the witness, preventing them from generating a valid proof.

The vulnerability arises when developers rely on assignments, believing they act as constraints. In other words, they might mistakenly assume that a value assigned to a variable will invariably adhere to certain rules or constraints, when in fact it can be arbitrary.

Vulnerability in Practice

To grasp the distinction between these two entities, let’s examine a sample ZK-circuit:

pragma circom 2.0.0;

template IsZero() {
    signal input in;
    signal output out;
    signal inv;

    inv <-- in!=0 ? 1/in : 0;
    out <== -in*inv +1;
    in*out === 0;
}

component main {public [in]}= IsZero();

Here, the vulnerability is illustrated using the assignment operator (<--). The inv variable is assigned a value based on an input, but this value isn’t constrained – it can be altered by the proof creator in any manner as long as it satisfies the constraints. This means that while a “well-intentioned” participant would follow the assignments as intended, a “malicious” participant can pick any value for inv, potentially leading to incorrect outcomes that, nonetheless, will pass verification if they don’t breach the constraints.

To safeguard against this vulnerability, developers must ensure that all critical variables and states are strictly constrained by relevant mathematical equations rather than just being assigned. This ensures proofs can be checked against these equations, making it impossible to produce a valid proof with incorrect or tampered variable values.

Conclusion

So, summarizing all the aforementioned points, what conclusions can we draw?

1. The infrastructure for crafting zk-SNARKs is still relatively immature. Best practices and guidelines for writing secure circuits are evolving slowly and being implemented even more gradually. However, we highly recommend paying attention to the resources we’ve presented as they offer genuinely valuable practical insights.
2. If you are developing a ZK solution and are unsure about its security, we advise you to adequately assess the existing risks and not to compromise on safety. Seek out professionals who can thoroughly audit your ZK solution; you’ll thank yourself multiple times later.
3. We also suggest that you rigorously test your ZK solutions. For this purpose, tools like circom_tester exist, along with a more user-friendly integration, hardhat-circom.
4. For a ZK audit, you can reach out to us! We have a team of over 10 highly skilled specialists with vast experience in both smart contracts and core ZK solutions. You’ll be satisfied with the outcome!🦾

References

[[1]](https://github.com/0xPARC/zk-bug-tracker#common-vulnerabilities-header) — “ZK Bug tracker” — 0XPARC

[[2]](https://vitalik.ca/general/2022/03/14/trustedsetup.html) — “How do trusted setups work?” — Vitalik Buterin

[[3]](https://electriccoin.co/blog/zcash-counterfeiting-vulnerability-successfully-remediated/) — “Zcash Counterfeiting Vulnerability Successfully Remediated” — ECC Posts

[[4]](https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/) — “Coordinated disclosure of vulnerabilities affecting Girault, Bulletproofs, and PlonK” — Trail of Bits

[[5]](https://github.com/a16z/evm-powers-of-tau/issues/3) — “Insecure implementation of the Fiat-Shamir transformation” — seresistvanandras on a16z “evm powers of tau repo”