💻 computer science

Formally Verifying Noir Zero Knowledge Programs with NAVe

This paper presents NAVe, an open-source formal verifier that uses SMT-LIB and the cvc5 solver to formally verify the correctness and proper constraints of Noir zero-knowledge programs by translating their ACIR intermediate representation into finite field polynomial equations.

Original authors: Pedro Antonino, Namrata Jain

Published 2026-01-15

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Pedro Antonino, Namrata Jain

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a high-security vault. You want to prove to a bank manager that you know the combination to the vault without actually telling them what the combination is. This is the magic of Zero-Knowledge (ZK) proofs.

However, building these vaults is tricky. The "blueprints" for these proofs are complex mathematical puzzles called arithmetic circuits. If a single line of the blueprint is wrong, the vault might be insecure, or the proof might fail.

This paper introduces a new tool called NAVe (Noir Acir Verifier) designed to check these blueprints for errors before they are ever used. Here is how it works, explained simply:

1. The Problem: The "Secret Recipe" vs. The "Cookbook"

The authors focus on a programming language called Noir. Think of Noir as a high-level cookbook that makes it easy to write recipes for these vaults.

The Cook (Developer): Writes a recipe in easy-to-read Noir.
The Translator (Compiler): Turns that recipe into a strict, low-level instruction manual called ACIR. This manual is a list of math equations that the computer must solve to prove the vault is secure.
The Danger: Sometimes, the translator makes a mistake, or the cook forgets to include a crucial step. In the world of ZK, this is called being "under-constrained." It's like writing a recipe that says "add salt" but forgetting to say how much. The result might be edible, but it's not the dish you intended.

2. The Solution: The "Math Detective" (NAVe)

The authors created NAVe, a formal verifier. Think of NAVe as a super-smart math detective that reads the low-level instruction manual (ACIR) and checks if the math actually adds up to what the cook intended.

NAVe uses a powerful logic engine (called an SMT solver) to ask questions like:

"If I put in a secret number, does the math always result in the correct public proof?"
"Is there any way to trick the system with a fake number?"

If the math is broken, NAVe doesn't just say "Error." It acts like a detective finding a clue: it shows the developer exactly which number they could have used to break the system. This helps them fix the blueprint immediately.

3. Two Ways to Solve the Puzzle

The paper describes two different ways NAVe translates the math puzzles to solve them:

The Integer Way: It treats the numbers like regular whole numbers (1, 2, 3...) and checks the math using standard arithmetic rules.
The Finite Field Way: It treats the numbers as if they are on a circular clock (where after a certain number, you wrap back to zero). This is how the actual ZK proofs work.

The authors found that neither method is perfect for every situation. Sometimes the "Integer" detective is faster; other times, the "Finite Field" detective is better. They suggest using both detectives at the same time to get the best results.

4. The "Unconstrained" Trap

A unique feature of Noir is "unconstrained code." Imagine a part of the recipe where the chef is allowed to guess the ingredients without being checked. This is useful for speed, but dangerous if the chef guesses wrong.

The Risk: A developer might write code that looks like it checks the ingredients, but because it's in the "unconstrained" section, the computer doesn't actually force the check.
NAVe's Job: NAVe specifically looks for these "ghost checks." It verifies that even if a developer uses the "guessing" section, they have added a separate, strict rule (an assert) to make sure the guess was actually correct.

5. What They Found

The authors tested NAVe on a variety of existing Noir programs:

It Works: NAVe successfully caught errors in programs where the math didn't match the intent.
The Bottleneck: They discovered that checking "range constraints" (making sure a number fits within a specific number of bits, like checking if a number is between 0 and 255) is very hard for the math detective. It sometimes takes a long time or gets stuck.
The Future: They plan to build better "shortcuts" (abstractions) to help the detective solve these tricky range puzzles faster.

Summary

In short, NAVe is a safety net for developers building privacy-preserving applications. It translates their code into a strict mathematical language and uses a powerful solver to ensure that the code does exactly what it claims to do, catching subtle bugs that could otherwise lead to security failures. It's like having a rigorous inspector check the structural integrity of a bridge before anyone is allowed to drive over it.

Technical Summary: Formally Verifying Noir Zero Knowledge Programs with NAVe

Problem Statement
Zero-Knowledge (ZK) proof systems rely on arithmetic circuits—sets of polynomial equations over finite fields—to verify that a private input $W$ satisfies a relation $R(X, W)$ without revealing $W$ . High-level Domain-Specific Languages (DSLs) like Noir simplify the creation of these circuits by compiling code into an intermediate representation called ACIR (Abstract Circuit Intermediate Representation). However, this abstraction introduces subtle vulnerabilities. Specifically, Noir supports "unconstrained code" (via unconstrained functions and unsafe blocks) designed to improve proving efficiency by offloading complex computations to the prover. If developers fail to manually add corresponding constraints (e.g., via assert statements) for the results of unconstrained code, the generated arithmetic circuit may not accurately capture the intended relation. This "under-constrained" bug can lead to severe security vulnerabilities, such as allowing a prover to generate valid proofs for false statements. Existing formal verification tools largely target lower-level circuit DSLs (like Circom) or require interactive theorem proving, lacking automated, scalable verification for high-level Noir programs and their specific features like memory manipulation and black-box functions.

Methodology
The authors propose NAVe (Noir Acir Verifier), an open-source formal verification framework that operates on the ACIR intermediate representation rather than the high-level Noir source code. This choice ensures stability against language evolution and allows the tool to potentially support other languages targeting ACIR.

Formalization via SMT-LIB: The core of NAVe is a formalization of a subset of ACIR opcodes into Satisfiability Modulo Theories (SMT) formulas. The authors implement two distinct encodings:
- Finite Field Encoding: Utilizes a non-standard theory of finite fields of prime order implemented in the cvc5 solver. This approach uses specific operators like ff.add, ff.mul, and ff.bitsum to directly model field arithmetic.
- Integer Arithmetic Encoding: Leverages the standard theory of integers in SMT-LIB. It relies on the isomorphism between finite fields of prime order $p$ and integers modulo $p$ , encoding field operations as modular integer arithmetic (e.g., (mod (+ ...) p)).
Opcode Semantics: The formalization covers key ACIR opcodes:
- AssertZero: Encoded as a polynomial equation constraint equal to zero.
- BlackBoxFuncCall: Specifically formalized for the Range check opcode. In the finite-field encoding, this is modeled using a binary decomposition (bitsum) and constraints ensuring bits are 0 or 1. In the integer encoding, it is modeled using standard integer ordering constraints ( $x < 2^n$ ).
- MemoryOp and MemoryInit: Formalized to track array mutations using a map of indices to witness values, handling both read and write operations sequentially.
- BrilligCall: Representing unconstrained code, these are translated as the always-satisfied constraint true (or ignored), as the verifier's goal is to check the constraints outside the unconstrained blocks.
Verification Workflow:
- The tool integrates with Nargo, Noir's package manager, as a formal-verify command.
- Developers annotate Noir programs with verify_assert(b: bool) statements. Unlike standard assert statements which generate circuit constraints, verify_assert creates a proof obligation.
- NAVe compiles the Noir program to ACIR, translates the ACIR opcodes into SMT formulas, and constructs a verification formula $F = \text{ACIR}_{\text{constraints}} \land \neg \text{verify\_assert}_{\text{condition}}$ .
- The cvc5 solver checks the satisfiability of $F$ . If $F$ is unsatisfiable, the verification condition holds (the program is correctly constrained). If $F$ is satisfiable, the solver returns a model (counterexample) showing a witness assignment that violates the condition, aiding in debugging.

Key Contributions

Formalization of ACIR: The first formalization of a subset of the ACIR language using SMT-LIB, covering complex features like memory operations, range checks, and the distinction between constrained and unconstrained code.
Dual Encoding Strategy: The proposal of two complementary encodings (finite-field theory and integer arithmetic) to leverage different solver capabilities.
NAVe Tool: An open-source, automated formal verifier integrated into the Noir ecosystem (Nargo), designed to be accessible to developers without requiring interactive theorem proving.
Empirical Evaluation: A comprehensive evaluation of NAVe on a suite of Noir test programs, analyzing performance across different constraint types and solver configurations.

Results
The authors evaluated NAVe on 4 distinct sets of Noir programs (verified conditions, falsified conditions, with and without range checks) using the cvc5 solver.

Solver Performance: No single backend (integer encoding, finite-field --ff=gb, or finite-field --ff=split) consistently outperformed the others. The results indicate that the encodings are complementary; some programs are solved faster by one encoding, while others time out on that same encoding but succeed on another.
Impact of Range Checks: Programs containing Range checks (BlackBoxFuncCall opcodes) significantly increased verification time. The --ff=split configuration, which approximates the finite-field theory, showed superior performance on programs with large range checks compared to the default --ff=gb configuration, though timeouts still occurred for complex cases.
Counterexample Generation: The tool successfully generated counterexamples for falsified conditions, demonstrating its utility in identifying under-constrained logic.

Significance and Claims
The paper claims that NAVe addresses a critical gap in the ZK ecosystem by providing an automated, scalable method to verify high-level ZK programs for under-constrained bugs, a class of errors that has led to real-world vulnerabilities. By targeting ACIR, the tool remains robust against changes in the high-level Noir syntax and is potentially applicable to other languages targeting the same intermediate representation.

The authors modestly frame their work as a step toward broader verification capabilities. They acknowledge that their current formalization covers only a subset of ACIR (excluding recursive Call opcodes and most BlackBoxFuncCalls except Range). They identify the high cost of verifying range checks as a primary limitation, suggesting that future work must focus on developing abstractions or approximations to handle these complex constraints efficiently. The paper positions NAVe not as a complete solution for all ZK verification needs, but as a practical, integrated tool that demonstrates the feasibility of automated formal verification for Noir and charts a path for improving solver handling of complex bit-level constraints.