Zero Knowledge, Full Coverage: A Fuzzing Paradox

Innokentii Sennovskii (Head of the Security Team · Aztec Labs)

POC2025 (Power of Community) · Main Stage

Overview

Innokentii Sennovskii, Head of the Security Team at Aztec Labs, presented a compelling talk titled "Zero Knowledge, Full Coverage: A Fuzzing Paradox" at the POC conference. This presentation delved into the unique and significant challenges of securing Zero-Knowledge (ZK) circuits, which form the backbone of many modern privacy-preserving applications. Sennovskii highlighted the inherent difficulties in applying traditional vulnerability discovery techniques, such as coverage-guided fuzzing, to ZK circuits due to their distinct architectural properties, particularly the absence of explicit branching.

Watch on YouTube · Slides

Visual summary for Zero Knowledge, Full Coverage: A Fuzzing Paradox by Innokentii Sennovskii
Visual summary for Zero Knowledge, Full Coverage: A Fuzzing Paradox by Innokentii Sennovskii

Key moments

  1. 0:00 Introduction to Zero Knowledge Fuzzing Paradox
  2. 1:17 Sudoku Example: Intuitive Zero Knowledge Proof
  3. 10:45 What are ZK Circuits and their structure?
  4. 19:50 Identifying Types of Zero Knowledge Circuit Bugs
  5. 24:10 The Fuzzing Paradox for ZK Circuits (no branching)
  6. 26:30 Solution: Using Brillig VM for Coverage Guidance
  7. 36:10 Q&A: Role of Brillig VM in ZK Fuzzing

Zero Knowledge, Full Coverage: A Fuzzing Paradox

Speakers: Innokentii Sennovskii, Head of the Security Team, Aztec Labs

Conference: POC

YouTube: https://www.youtube.com/watch?v=37-RrUxAUgM

Overview

Innokentii Sennovskii, Head of the Security Team at Aztec Labs, presented a compelling talk titled "Zero Knowledge, Full Coverage: A Fuzzing Paradox" at the POC conference. This presentation delved into the unique and significant challenges of securing Zero-Knowledge (ZK) circuits, which form the backbone of many modern privacy-preserving applications. Sennovskii highlighted the inherent difficulties in applying traditional vulnerability discovery techniques, such as coverage-guided fuzzing, to ZK circuits due to their distinct architectural properties, particularly the absence of explicit branching.

The talk is crucial for anyone involved in the development and security of ZK-based systems. As ZK proofs gain traction across various domains—from private blockchain transactions and identity verification to verifiable computation—ensuring their correctness and soundness becomes paramount. Flaws in ZK circuits can lead to devastating consequences, including the acceptance of invalid proofs (soundness bugs) or the inability to prove valid statements (completeness bugs). Sennovskii's work introduces innovative methodologies to adapt and enhance fuzzing techniques for this complex environment, offering a scalable and cost-effective alternative to traditional, often limited, security audits.

The "paradox" in the title aptly captures the core tension: Zero-Knowledge proofs are designed to reveal minimal information, yet effective fuzzing often relies on deep insight into program execution paths. Sennovskii addresses this by exploring how AI-assisted automation and novel coverage metrics can bridge this gap, offering a path towards achieving "full coverage" in a domain traditionally resistant to such approaches. This talk provides invaluable insights into the future of ZK circuit security, emphasizing the need for specialized tools and techniques to meet the evolving demands of this critical technology.

Background

▶ Watch: Introduction to Zero Knowledge Fuzzing Paradox (0:00)

Zero-Knowledge Proofs (ZKPs) are cryptographic protocols that enable one party (the prover) to convince another party (the verifier) that a given statement is true, without revealing any information beyond the veracity of the statement itself. Sennovskii introduced this concept with a classic, intuitive example: proving knowledge of a Sudoku solution without revealing the solution itself, using a system of shuffled card decks. This demonstration highlights the core principles of completeness (a truthful prover can always convince a verifier), soundness (a dishonest prover cannot convince a verifier of a false statement), and zero-knowledge (the verifier learns nothing beyond the statement's truth).

Technically, ZKPs often rely on computationally hard problems like the discrete logarithm problem, where exponentiation is easy but finding the logarithm in a large finite field is practically impossible. Sennovskii illustrated how this primitive can be used to construct a basic ZKP, and how, with a slight modification (replacing the verifier's challenge with a hash), it becomes a Schnorr signature, a widely used cryptographic scheme.

Modern applications of ZKPs are diverse and impactful:

  • Private payments on blockchains: Enabling transactions without revealing sender, receiver, or amount.
  • Identity checks: Proving attributes (e.g., being over 18, being a citizen of a specific country) from a digital passport (like ZK passport) without revealing other personal details.
  • Email receipt verification: Proving receipt of an email from a particular company, potentially revealing only parts of the content, while keeping other information private.
  • Verifiable binary execution: Proving that a specific input to a program (e.g., a RISC-V binary) will yield a particular output, without revealing the input or the full execution trace.

For these complex applications, developers use ZK circuits, which are essentially programs designed for the ZK world. Unlike traditional programs, ZK circuits operate within specific constraints:

  • Program Conversion: A standard program description is converted into a circuit description, optimized for cryptographic primitives.
  • Prover's Role: The prover uses this circuit to generate a trace (intermediate variables) and then a proof using a backend.
  • Verifier's Role: The verifier uses a verification key (analogous to a public key) derived from the same circuit description to check the proof.
  • Visibility: Values must be explicitly declared as public (revealed to the verifier) or private (known only to the prover).
  • Base Type: The fundamental data type is typically a field element (e.g., a 254-bit prime number in Noir), not standard integers like U8 or U32. All other types are built upon this.
  • Finite Execution Length: ZK circuits are not Turing complete; they have a predefined, limited execution trace, meaning the number of "CPU instructions" is bounded.

The Noir language, described as "Rust-like," compiles into an Algebraic Circuit Intermediate Representation (ACIR). This representation consists primarily of:

  • Asserts (Constraints): Equations that define the rules and relationships between variables and intermediate states. Any set of variable values (a witness) that satisfies these equations forms a valid proof. For example, A * B = C is a constraint.
  • Blackbox Opcodes: These leverage specific, optimized functionalities of the underlying proving system, extending beyond standard algebraic constraints (e.g., range checks like 0 <= value < 2^32 - 1).
  • Brill Calls: These are calls to unconstrained functionality. This is critical for computations that are hard to perform efficiently within the finite field logic of a circuit (e.g., square roots). The prover computes these values outside the circuit and then inserts them, relying on subsequent asserts to constrain them against desired properties.

Sennovskii detailed how a simple Fibonacci program in Noir would translate into these constraints, demonstrating how conditional logic (if/else) is often implemented not with traditional branches, but by using intermediate boolean variables (0 or 1) and linear combinations. This approach, while necessary for ZK circuit construction, presents a significant hurdle for traditional coverage-guided fuzzing, which relies on identifying and traversing explicit branches.

Key Findings

▶ Watch: What are ZK Circuits and their structure? (10:45)

The core problem addressed by Sennovskii is the "fuzzing paradox" for ZK circuits: traditional coverage-guided fuzzing relies heavily on identifying and exploring different execution paths (branches) within a program. However, ZK circuits, when compiled into their algebraic intermediate representation (ACIR), fundamentally lack explicit branching. They are a flattened list of constraints, making standard code coverage metrics ineffective. This limitation pushes fuzzing back into a less efficient blackbox approach, where the probability of finding deep vulnerabilities is significantly reduced.

Sennovskii's key findings and contributions to overcome this challenge include:

  1. Leveraging Brillig VM for Coverage: Noir, the Rust-like language for ZK circuits, supports unconstrained functions that are compiled to Brillig, a virtual machine. Crucially, Brillig does have branching, continuous memory, and supports standard integer types (U64, U128). This allows the same ZK circuit code to be compiled into a Brillig variant, providing a "twin" execution environment from which traditional branch coverage can be extracted. This is a novel approach to guide fuzzing for the ACIR.
  1. Balancing ACIR and Brillig Execution: While Brillig provides coverage, the ultimate goal is to find bugs in the ACIR. ACIR execution is computationally intensive due to finite field logic and the lack of "quick exit" paths. To optimize the fuzzing process, Sennovskii implemented a strategy to split execution time between the fast, coverage-rich Brillig VM and the slow, bug-checking ACIR. This balance means Brillig is executed approximately 10 times more often than ACIR, allowing for broader exploration of the target program while still validating potential vulnerabilities against the actual circuit.
  1. Instrumenting Intermediate Boolean Values for Implicit Branching: Many ZK circuit developers avoid explicit if statements even in Brillig-compatible code, preferring to implement conditional logic using intermediate boolean variables (0 or 1) and conditional selects (e.g., result = cond val_if_true + (1 - cond) val_if_false). This "flattened" logic still lacks explicit branches, even in the Brillig VM, making coverage difficult. Sennovskii addressed this by parsing the final witness from ACIR execution and monitoring the values of these intermediate boolean variables. By identifying new combinations or states of these booleans, the fuzzer can effectively explore different logical paths that are implicitly defined by these variables, even without explicit branches.
  1. Introduction of Fuzzing Oracles for Invariant Checking: To move beyond simply detecting constraint failures and target specific types of bugs, Sennovskii introduced fuzzing oracle integration. This allows developers to define external "oracles" (e.g., a trusted reference implementation like OpenSSL for cryptographic primitives, or a standard library like Python's JSON parser for data processing) that can independently verify the correctness of a circuit's behavior for a given input. The fuzzer checks if the circuit's output aligns with the oracle's expected output, enabling the detection of subtle invariant violations and completeness bugs. This is a powerful technique for differential testing against a known-good implementation.

These findings collectively represent a significant leap forward in making coverage-guided fuzzing a viable and effective strategy for securing Zero-Knowledge circuits, addressing their unique challenges head-on.

Technical Deep Dive

▶ Watch: Identifying Types of Zero Knowledge Circuit Bugs (19:50)

Securing Zero-Knowledge (ZK) circuits presents a unique set of technical challenges that traditional software security methods struggle to address. Sennovskii's talk meticulously breaks down these complexities and introduces an innovative fuzzing framework designed to overcome them.

At its core, a ZK circuit, particularly in languages like Noir, is a program that gets compiled into an Algebraic Circuit Intermediate Representation (ACIR). This ACIR is a collection of mathematical equations or constraints that must be satisfied by a set of input and intermediate values (the witness) for a proof to be valid. Unlike conventional programs that execute sequentially with explicit control flow, ACIRs are essentially static systems of equations.

ZK Circuit Structure and ACIR:

  • Public vs. Private: Inputs and outputs are rigorously categorized. public values are visible to the verifier, while private values are known only to the prover. A common bug could be accidentally marking a sensitive private value as public, leading to a zero-knowledge bug.
  • Field Elements: The fundamental data type in ZK circuits is a large finite field element, not standard integers. For Noir, this is often a 254-bit prime number. Operations (addition, multiplication) are performed modulo this prime. This makes arithmetic different from standard integer arithmetic, where overflows wrap around.
  • Finite Execution: ZK circuits are not Turing-complete. They are designed for a fixed, maximum number of steps or constraints. This means complex algorithms must be "unrolled" or expressed within these bounds.
  • Constraints (Asserts): These are the bedrock of ACIR. An assert statement in Noir translates directly to an algebraic constraint. For example, x * y == z becomes a constraint. If any constraint is violated, the proof is invalid.
  • Blackbox Opcodes: These are specialized, optimized operations provided by the underlying proving system, often for common cryptographic tasks or range checks. For instance, ensuring a value v is within 0 <= v < 2^32 - 1 is a common blackbox operation.
  • Brill Calls (Unconstrained Functions): For operations that are computationally expensive or impossible within finite field arithmetic (e.g., square roots, complex hashing), the circuit can use brill calls. The prover computes the result of these functions outside the circuit (unconstrained) and then inserts the result back into the circuit. It is then the responsibility of subsequent asserts to ensure this external computation was correct and adheres to the desired logic. Misusing or inadequately constraining brill call outputs is a common source of soundness bugs.

Types of ZK Bugs:

Sennovskii categorized ZK circuit bugs into three main types:

  1. Soundness Bugs: These occur when an invalid statement can be proven as true. They often stem from:
  • Missing Constraints: The most common cause. If a necessary rule isn't enforced by an assert, a malicious prover can manipulate the witness to satisfy the existing constraints while violating the intended logic. Example: Implementing a U128 primitive using two U64s, but instead of checking (a_high == b_high) && (a_low == b_low), the developer checks (a_high - b_high) * (a_low - b_low) == 0. This allows a valid proof even if only one part (high or low) matches, accepting an incorrect U128 value.
  • Logic Issues: Incorrectly formulated constraints.
  • Misuse of Unconstrained Functions: Relying on brill calls without sufficient subsequent constraints to verify their output.
  1. Completeness Bugs: These occur when a valid statement cannot be proven as true. This means a correct prover cannot generate a valid witness or proof. Examples include:
  • Incorrect Circuit Implementation: Forgetting to handle edge cases in logic.
  • Primitive Misimplementation: A common issue is overlooking finite field arithmetic specifics. For instance, if a developer intends to implement sum % 2^256 (regular U8 wrapping add) but uses standard finite field addition, it won't wrap around at 2^256 but at the field prime. This limits valid solutions, potentially making correct inputs unprovable.
  1. Zero-Knowledge Bugs: These involve inadvertently leaking sensitive information. While critical, they are generally harder to detect with automated fuzzing techniques as they often relate to the proving backend or incorrect public/private declarations.

Limitations of Traditional Security Techniques:

  • Unit/End-to-End Testing: Developer-dependent, limited coverage, often misses component interactions or unexpected edge cases.
  • Formal Verification: Powerful for small, isolated primitives but struggles immensely with scalability for larger, composed circuits. Tools like CBC5 quickly hit resource limits.
  • Audits: Highly human-dependent, non-scalable, and prohibitively expensive (up to $25,000 per researcher per week).

The Fuzzing Solution: Bridging the Gap with Brillig

The core innovation lies in adapting fuzzing for ZK circuits. Traditional graybox fuzzing uses coverage (e.g., branch coverage) to guide mutations, prioritizing inputs that explore new code paths. The challenge is ACIR's lack of branches.

Sennovskii's solution leverages Brillig, a virtual machine used by Noir for unconstrained functions. Critically, Brillig VM code does have branching, continuous memory, and operates on standard integer types (U64, U128). The strategy is:

  1. Dual Compilation: Compile the ZK circuit code not just to ACIR, but also to a Brillig VM variant.
  2. Brillig for Coverage: The fuzzer executes test cases in the Brillig VM. Because Brillig has branches, standard coverage metrics can be collected. New coverage guides subsequent mutations.
  3. ACIR for Bug Detection: The same test case that generated new coverage in Brillig is then submitted to the ACIR for full constraint checking. If a constraint fails, a bug is found.

Optimizing Fuzzing Performance:

ACIR execution is slow (254-bit finite field arithmetic, no quick exits). To maximize exploration speed, Sennovskii implemented a balanced execution strategy:

  • The fuzzer splits its time between Brillig and ACIR execution.
  • Brillig is executed approximately 10 times more often than ACIR. This allows rapid exploration of the program's state space via Brillig's fast execution and branch coverage, while still regularly checking for ACIR-specific bugs.

Addressing Implicit Branching:

Even with Brillig, many ZK circuit developers implement conditional logic using intermediate boolean variables (0 or 1) and conditional selects, avoiding explicit if statements. This results in a "single trace" even in the Brillig VM, hindering branch coverage.

To overcome this, Sennovskii's fuzzer parses the final witness generated by ACIR execution. It specifically monitors these intermediate boolean variables. If a new combination or state of these booleans is observed, it's considered new "coverage," guiding the fuzzer to explore these implicitly defined logical paths. This allows the fuzzer to "explore all of the switches and all of the different states within the program" even without explicit branching.

Targeting Specific Conditions with Fuzzing Oracles:

Beyond finding any constraint violation, sometimes developers need to verify specific invariants or target particular conditions. The fuzzer includes a mechanism to target specific assertions, allowing it to ignore other "failure conditions" and focus on a particular invariant.

A powerful extension is fuzzing oracle integration. This involves setting up a JSON RPC server that acts as an external "oracle" or reference implementation. The fuzzer feeds inputs to both the ZK circuit and the oracle. The oracle then independently checks the correctness of the output or behavior for that input. For example, fuzzing a cryptographic primitive in a ZK circuit could use an OpenSSL library as an oracle for differential testing. Similarly, fuzzing a JSON parsing circuit could use a Python JSON parser as an oracle. This robustly detects completeness bugs and invariant violations.

Additional Features:

The fuzzing framework for Noir also includes:

  • Multifuzzing: Parallel execution across multiple threads.
  • Time and Count Limits: For controlled fuzzing campaigns.
  • Fast Tests: For CI/CD integration.
  • Specialized Mutations: Tailored mutation strategies for various basic types and complex structures (e.g., parsing a struct input and mutating its internal fields).
  • Case Splicing: Combining parts of different interesting test cases.
  • Autodig: Extracting values from both Brillig and ACIR representations to enrich the corpus.

This comprehensive technical approach transforms fuzzing from a blackbox endeavor into a sophisticated, coverage-guided, and oracle-supported security analysis tool for the intricate world of Zero-Knowledge circuits.

Demo / Proof of Concept

▶ Watch: Solution: Using Brillig VM for Coverage Guidance (26:30)

While Sennovskii's talk primarily focused on the technical underpinnings and methodology, he provided a concrete example illustrating the practical application and efficacy of the developed fuzzing framework. He demonstrated fuzzing a JSON library implemented in a ZK circuit.

The objective was to identify if the ZK circuit's JSON parser could incorrectly parse an invalid JSON object, or if it would fail to parse a valid one (a completeness bug). To achieve this, the fuzzing setup leveraged an oracle integration:

  • The fuzzer generated various string inputs, representing potential JSON objects.
  • Each generated input was fed into the ZK circuit's JSON parsing logic.
  • Simultaneously, the same input was sent to an external Python JSON parser, which served as the trusted oracle.
  • The fuzzer then compared the parsing result (success/failure, and potentially the parsed structure) from the ZK circuit with that of the Python oracle.
  • Any discrepancy—where the ZK circuit parsed an invalid JSON string that the Python oracle rejected, or failed to parse a valid string that the oracle accepted—would indicate a bug (a soundness or completeness issue) in the ZK circuit's implementation.

This demonstration was performed using 64 threads concurrently, showcasing the multifuzzing capabilities and the scalability of the approach. The ability to run such an intensive, oracle-guided fuzzing campaign highlights the framework's potential to uncover subtle, yet critical, vulnerabilities in complex ZK circuit implementations that would be difficult to find through manual auditing or limited testing. It serves as a strong proof of concept for the power of differential testing combined with coverage-guided fuzzing in the ZK domain.

Defensive Implications

▶ Watch: Q&A: Role of Brillig VM in ZK Fuzzing (36:10)

The insights presented by Innokentii Sennovskii offer critical guidance for developers and security professionals working with Zero-Knowledge circuits. The unique architecture of ZK circuits demands a paradigm shift in defensive strategies, moving beyond traditional testing methodologies.

  1. Embrace Fuzzing as a Primary Security Tool: Given the limitations and high costs associated with formal verification and manual audits, fuzzing, particularly coverage-guided fuzzing, should become a cornerstone of ZK circuit security. Developers should integrate fuzzing into their CI/CD pipelines to catch bugs early and continuously.
  1. Leverage Brillig for Enhanced Coverage: For Noir developers, understanding and utilizing the Brillig VM for coverage collection is paramount. Even if the primary circuit logic is in ACIR, ensuring that unconstrained functions or even the main circuit logic can be compiled to Brillig provides an invaluable source of coverage information, transforming blackbox fuzzing into a more effective graybox approach.
  1. Instrument Intermediate Boolean Values: Developers should be aware that conditional logic implemented via intermediate boolean variables (e.g., if (cond) { A } else { B } becoming result = cond A + (1 - cond) B) can obscure execution paths from traditional branch coverage. Tools that monitor the witness and track the states of these implicit boolean "switches" are essential for achieving comprehensive coverage.
  1. Implement Robust Fuzzing Oracles: For critical components, especially cryptographic primitives or complex data parsers, developers should develop fuzzing oracles. These external, trusted reference implementations (e.g., OpenSSL, standard library parsers) enable differential testing, allowing the fuzzer to verify invariants and detect both soundness and completeness bugs by comparing the circuit's behavior against a known-good baseline. This is especially crucial for ensuring that the circuit correctly handles edge cases and complex inputs.
  1. Scrutinize brill Calls and Their Constraints: brill calls (unconstrained functions) are powerful but dangerous. Defenders must ensure that every brill call's output is rigorously constrained by subsequent asserts within the ACIR. Inadequate constraints around brill outputs are a prime source of soundness bugs. A thorough review process for any logic involving brill calls is indispensable.
  1. Understand Finite Field Arithmetic: The base type of ZK circuits is a finite field element. Developers must be acutely aware that operations behave differently than standard integer arithmetic (e.g., no wrapping overflow at 2^N but at the field prime). This is a common source of completeness bugs if not handled correctly (e.g., using wrapping_add equivalent when needed).
  1. Prioritize Constraint Correctness: The foundation of ZK circuit security lies in the correctness and completeness of its constraints. Missing or incorrectly formulated constraints are the most common cause of soundness bugs. Thorough design and review of constraints, coupled with fuzzing to validate their behavior, are essential.

By adopting these defensive implications, the ZK circuit ecosystem can mature with a stronger security posture, ensuring that the promise of zero-knowledge technology is delivered without compromising on correctness or reliability.

Key Takeaways

  • Traditional fuzzing struggles with ZK circuits: The algebraic intermediate representation (ACIR) of ZK circuits lacks explicit branching, making standard coverage-guided fuzzing ineffective for vulnerability discovery.
  • Brillig VM is a game-changer for coverage: By compiling ZK circuit code to the Brillig virtual machine, which does support branching, developers can extract crucial coverage information to guide fuzzing, even though bugs are found in the ACIR.
  • Balanced execution optimizes fuzzing: To overcome the computational cost of ACIR execution, the fuzzing framework intelligently balances execution, running Brillig for exploration approximately 10 times more often than ACIR for bug verification.
  • Implicit branching requires new coverage metrics: When developers use boolean intermediate values for conditional logic (instead of explicit branches), fuzzers must instrument and track the states of these values in the ACIR witness to achieve effective coverage.
  • Fuzzing oracles enhance bug detection: Integrating external, trusted reference implementations (oracles) allows for differential testing, enabling the fuzzer to target specific invariants and uncover subtle soundness and completeness bugs.
  • Fuzzing offers a scalable alternative: Automated fuzzing provides a more scalable, cost-effective, and comprehensive approach to ZK circuit security compared to expensive manual audits and the scalability limitations of formal verification.

About the Speaker(s)

Innokentii Sennovskii is the Head of the Security Team at Aztec Labs, a prominent organization at the forefront of Zero-Knowledge technology. His primary focus is dedicated to ensuring the security of every component within zero-knowledge protocols. Beyond his work at Aztec Labs, Sennovskii is also an active member of the cybersecurity community, serving as an organizer for the CTFZone competition. He further contributes to the field by teaching attacks on applied cryptography systems at the university level, sharing his expertise with the next generation of security professionals. His deep understanding of both theoretical cryptography and practical security vulnerabilities makes him a leading voice in the secure development of ZK systems.

Reviews

Dr. Zero (Offensive Security Researcher) — SOLID

Solid applied security research that addresses a real gap: how do you fuzz something with no branches? Sennovskii delivers a practical, working solution for ZK circuits, not a theoretical hand-wave. The Brillig VM trick for coverage extraction is genuinely clever, and the oracle integration for differential testing shows mature tooling thinking.

Heather Calloway (CISO) — SOLID

Deep-technical work on fuzzing ZK circuits — clever adaptation of coverage-guided techniques to a domain that structurally resists them. Not governance material, but if you're running blockchain infrastructure or evaluating ZK-based vendors, the takeaway is simple: this class of system is harder to audit than traditional code, and the tooling is still maturing.

→ Top-rated talks at POC2025 (Power of Community)

All talks from POC2025 (Power of Community)