zkFuzz

Foundation and Framework for
Effective Fuzzing of
Zero-Knowledge Circuits

Core Logic of zkFuzz

for i ← 1, 2, ··· MAX_GENERATION do
  // 1. Fuzzing Setup
  Generate input data x
  Mutate P to P'
  
  // 2. Execution
  Execute both P and P' on x:
  P(x) = (z, y), P'(x) = (z', y')

  // 3. Trace-Constraint Consistency Test (TCCT)
  if y ≠ ⊥ and C(x, z, y) = false then
    Report "Over-Constrained Problem"

  if y' ≠ ⊥ and y ≠ y' and C(x, z', y') = true then
    Report "Under-Constrained Problem"

Securing the Zero-Knowledge Future

Accepted at IEEE Symposium on Security and Privacy (S&P) 2026

Zero-Knowledge Proofs (ZKPs) are the bedrock of next-generation privacy and trustless scaling. However, the complexity of cryptographic circuits leaves them prone to critical vulnerabilities, where a single bug can compromise user privacy or drain millions in assets.

Developed at Columbia University, zkFuzz bridges the gap between theoretical foundations and practical security. Our research tackles the fundamental challenges of circuit verification while providing a robust framework for real-world testing. To date, our tools have successfully identified more than 70 zero-day bugs across various ZKP systems.

What is Zero-Knowledge Proof?

Zero-Knowledge Proof (ZKP) allows one party (the Prover) to prove to another (the Verifier) that a statement is true. This enables the Verifier to verify the proof succinctly, often exponentially faster than the original computation, without revealing any underlying secret information. This cryptographic magic fuels two major revolutions in blockchain:

Workflow of ZKP


[ PROVER ]                                        [ VERIFIER ]
   |                                                  |
   |-- [Secret Data]                                  |
   |        (Remains Private!)                        |
   |                                                  |
   | Run Proving Computation                          |
   |                                                  |
   +-----> [ZK-Proof] ----------------------------->  |
               (Reveals No Secrets)                   |
                                                      |
                                                      | 🔍 Verify Proof
                                                      |    (Succinct & Fast)
                                                      |
   <----------------------------------------- [ ✅ VALID / ❌ INVALID ]

Privacy

Users can verify facts without exposing sensitive data.

Identity: Proving you are over 21 without revealing your birth date or ID card.
Finance: Verifying a transaction is valid without disclosing the sender's balance.

Scalability

Heavy computations run off-chain.

Validity Rollups: Bundling thousands of transactions into a single batch and generating one tiny proof. The blockchain only verifies this proof, lowering gas costs.

The Challenge: Circuit Vulnerabilities

While the math is secure, the code (circuits) is fragile. Developers struggle to correctly implement circuits, leading to two opposing types of bugs. zkFuzz provides a unified framework to detect both:

Under-constrained

(Soundness Error)
Missing constraints allow attackers to forge proofs for false statements (e.g., stealing funds).

Over-constrained

(Completeness Error)
Excessive constraints cause the system to reject valid proofs from honest users (DoS).

What is zkFuzz?

zkFuzz is a novel mutation-based fuzzing framework designed to detect vulnerabilities in Zero-Knowledge (ZK) circuits. It automates the detection of soundness and completeness bugs that traditional static analyzers and formal verification tools often miss.

Mutation-Based Fuzzing

Unlike static analysis and formal verification tools, zkFuzz actively mutates the witness generation logic and injects edge-case inputs to trigger hidden vulnerabilities dynamically.

Unified Formulation via TCCT

TCCT is the first theoretical model defining bugs as computation-constraint inconsistencies. This unified framework captures both soundness and completeness errors, surpassing prior theoretical definitions.

Get Started in Seconds

View Full CLI Documentation

user@zkfuzz:~

$ git clone https://github.com/Koukyosyumei/zkFuzz.git
Cloning into 'zkFuzz'...
$ cd zkFuzz && cargo install --path ./
Finished release [optimized] target(s) in 1.2s
$ zkfuzz target.circom

Theoretical Foundation

Trace-Constraint Consistency Test (TCCT)

Definitions

Witness Generation Program

The imperative code that computes values (witnesses) step-by-step: P(x) = (z, y), returning the intermediate value z and the output y on the input x.

Circuit Constraints

The set of mathematical equations C(x, y, z) = 1 or 0 that verify the witness values.

T(P)

Trace Set

The set of all execution traces actually generated by running P.

S(C)

Constraint Satisfaction Set

The set of all value assignments that mathematically satisfy C.

Inconsistencies (Bugs)

We formalize ZK bugs as set-theoretic inconsistencies between the Trace Set (T(P)) generated by the program and the Constraint Satisfaction Set (S(C)) allowed by the circuit.

Under-constrained (Soundness) Π xy (S (C)) ∖ Π xy (T (P)) \neq \emptyset The circuit accepts an Input/Output pair (x, y) that the program never generates (or aborts on). *Using projection Π xy allows avoiding false positives if only intermediate values differ. Over-constrained (Completeness) T (P) ∖ S (C) \neq \emptyset A valid trace generated by the program is rejected by the circuit constraints. *Valid honest proofs fail to verify.

System Architecture

zkFuzz System Design — Figure: Basic workflow of ZKFUZZ. This fuzzing framework systematically mutates program logic and feeds artificially generated input data to the original and mutated programs to catch inconsistencies between the program and the constraint.

zkFuzz moves beyond traditional input-only fuzzing. It employs a Joint Mutation Strategy that evolves both the witness generation logic (𝒫) and the input data simultaneously.

1. Mutator Engine

Generates program variants by altering operators and removing assertions to explore deviant behaviors that static analysis might miss.

2. Target Selectors

Strategically guides the fuzzer towards critical edge cases (e.g., Zero-Division, Hash-Check patterns) using static analysis hints.

3. TCCT Detector

Cross-checks execution traces against constraints. Any inconsistency found is immediately flagged as a vulnerability.

Detected Vulnerabilities

This project has identified more than 70 zero-day vulnerabilities. Below is a selected list of critical bugs found in popular projects and libraries.

Project / Library	ID	DSL	Description	Status
raimo/passport-zk-circuits	#60	Circom	Missing range checks in division making the circuit non-deterministic.	Fixed
worm-privacy/proof-of-burn	#1	Circom	Missing range checks in balance verification, allowing invalid transactions.	Fixed
aptos-labs/keyless-zk-proofs	#50	Circom	Unused output making the circuit non-deterministic.	Fixed
banyancomputer/hot-proofs-blake3-circom	#10	Circom	Missing range checks in hash calculation.	Fixed
siv-org/verifiable-private-overrides	#13	Circom	Missing constraint due to `<--` operator	Fixed
zkemail/zk-regex	#83	Circom	Missing range checks in regex verification allowing arbitrary string acceptance.	Confirmed
masa-finance/masa-zkSBT	#177	Circom	Misuse of `assert` causing computation aborts not constrained in the circuit.	Confirmed
tokamak-network/zvm	-	Circom	Misuse of `assert` causing computation aborts not constrained in the circuit.	Archived
...and 80+ more bugs found across various Circom and Plonky3 projects.

Publications

zkFuzz: Foundation and Framework for Effective Fuzzing of Zero-Knowledge Circuits
Hideaki Takahashi, Jihwan Kim, Suman Jana, Junfeng Yang
IEEE Symposium on Security and Privacy (S&P), 2026

PDF arXiv Code Click to cite (BibTeX)