💻 computer science

Formally Verifying Noir Zero Knowledge Programs with NAVe

Dieses Paper präsentiert NAVe, einen Open-Source-Formal-Verifier, der SMT-LIB und den cvc5-Solver verwendet, um die Korrektheit und die ordnungsgemäßen Constraints von Noir Zero-Knowledge-Programmen formal zu verifizieren, indem er deren ACIR-Zwischenrepräsentation in endliche Körper-Polynomgleichungen übersetzt.

Ursprüngliche Autoren: Pedro Antonino, Namrata Jain

Veröffentlicht 2026-01-15

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Pedro Antonino, Namrata Jain

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie bauen einen Hochsicherheits-Tresor. Sie möchten einem Bankmanager beweisen, dass Sie die Kombination zum Tresor kennen, ohne ihm die Kombination tatsächlich zu verraten. Das ist die Magie von Zero-Knowledge-Beweisen (ZK-Proofs).

Der Bau dieser Tresore ist jedoch knifflig. Die „Blaupausen“ für diese Beweise sind komplexe mathematische Rätsel, die man arithmetische Schaltkreise nennt. Wenn auch nur eine einzige Zeile der Blaupause falsch ist, könnte der Tresor unsicher sein oder der Beweis könnte fehlschlagen.

Dieses Paper stellt ein neues Werkzeug namens NAVe (Noir Acir Verifier) vor, das diese Blaupausen auf Fehler überprüft, bevor sie jemals verwendet werden. So funktioniert es, einfach erklärt:

1. Das Problem: Das „Geheime Rezept“ vs. das „Kochbuch“

Die Autoren konzentrieren sich auf eine Programmiersprache namens Noir. Betrachten Sie Noir als ein hochsprachliches Kochbuch, das es einfach macht, Rezepte für diese Tresore zu schreiben.

Der Koch (Entwickler): Schreibt ein Rezept in leicht lesbarem Noir.
Der Übersetzer (Compiler): Verwandelt dieses Rezept in eine strikte, niederschwellige Bedienungsanleitung namens ACIR. Diese Anleitung ist eine Liste von mathematischen Gleichungen, die der Computer lösen muss, um zu beweisen, dass der Tresor sicher ist.
Die Gefahr: Manchmal macht der Übersetzer einen Fehler, oder der Koch vergisst einen entscheidenden Schritt. In der Welt von ZK wird dies als „unterbestimmt“ (under-constrained) bezeichnet. Es ist, als würde man ein Rezept schreiben, das sagt „Salz hinzufügen“, aber vergisst zu sagen, wie viel. Das Ergebnis ist zwar essbar, aber nicht das Gericht, das man eigentlich beabsichtigt hat.

2. Die Lösung: Der „Mathematik-Detektiv“ (NAVe)

Die Autoren haben NAVe entwickelt, einen formalen Verifizierer. Betrachten Sie NAVe als einen superintelligenten Mathematik-Detektiv, der die niederschwellige Bedienungsanleitung (ACকIR) liest und prüft, ob die Mathematik tatsächlich zu dem passt, was der Koch beabsichtigt hat.

NAVe nutzt eine leistungsstarke Logik-Engine (einen sogenannten SMT-Solver), um Fragen zu stellen wie:

„Wenn ich eine geheime Zahl einsetze, führt die Mathematik dann immer zum korrekten öffentlichen Beweis?“
„Gibt es einen Weg, das System mit einer gefälschten Zahl zu überlisten?“

Wenn die Mathematik fehlerhaft ist, sagt NAVe nicht einfach „Fehler“. Es agiert wie ein Detektiv, der eine Spur findet: Es zeigt dem Entwickler genau auf, welche Zahl er hätte verwenden können, um das System zu brechen. Dies hilft ihm, die Blaupause sofort zu korrigieren.

3. Zwei Wege, das Rätsel zu lösen

Das Paper beschreibt zwei verschiedene Arten, wie NAVe die mathematischen Rätsel übersetzt, um sie zu lösen:

Der Weg der ganzen Zahlen: Es behandelt die Zahlen wie reguläre ganze Zahlen (1, 2, 3...) und prüft die Mathematik nach Standard-Arithmetikregeln.
Der Weg der endlichen Körper (Finite Fields): Es behandelt die Zahlen so, als befänden sie sich auf einer kreisförmigen Uhr (wo man nach einer bestimmten Zahl wieder bei Null beginnt). Genau so funktionieren die eigentlichen ZK-Beweise.

Die Autoren stellten fest, dass keine der beiden Methoden für jede Situation perfekt ist. Manchmal ist der „Ganze-Zahlen-Detektiv“ schneller; ein anderes Mal ist der „Endliche-Körper-Detektiv“ besser. Sie schlagen vor, beide Detektive gleichzeitig einzusetzen, um das beste Ergebnis zu erzielen.

4. Die „Unconstrained“-Falle

Ein einzigartiges Merkmal von Noir ist der „unconstrained Code“ (nicht eingeschränkter Code). Stellen Sie sich einen Teil des Rezepts vor, in dem der Koch erlaubt ist, die Zutaten zu raten, ohne dass dies überprüft wird. Dies ist nützlich für die Geschwindigkeit, aber gefährlich, wenn der Koch falsch rät.

Das Risiko: Ein Entwickler könnte Code schreiben, der so aussieht, als würde er die Zutaten prüfen, aber weil er sich im „unconstrained“-Abschnitt befindet, erzwingt der Computer die Prüfung nicht tatsächlich.
NAVes Aufgabe: NAVe sucht gezielt nach diesen „Geister-Checks“. Es verifiziert, dass selbst wenn ein Entwickler den „Rate-Abschnitt“ verwendet, er eine separate, strikte Regel (ein assert) hinzugefügt hat, um sicherzustellen, dass die Vermutung tatsächlich korrekt war.

5. Was sie herausgefunden haben

Die Autoren haben NAVe an einer Vielzahl bestehender Noir-Programme getestet:

Es funktioniert: NAVe hat erfolgreich Fehler in Programmen gefunden, bei denen die Mathematik nicht mit der Absicht übereinstimmte.
Der Engpass: Sie entdeckten, dass das Überprüfen von „Bereicheinschränkungen“ (Range Constraints – also sicherzustellen, dass eine Zahl innerhalb einer bestimmten Anzahl von Bits liegt, wie etwa die Prüfung, ob eine Zahl zwischen 0 und 255 liegt) sehr schwierig für den Mathematik-Detektiv ist. Es dauert manchmal sehr lange oder bleibt stecken.
Die Zukunft: Sie planen, bessere „Abkürzungen“ (Abstraktionen) zu entwickeln, um dem Detektiv zu helfen, diese kniffligen Bereichs-Rätsel schneller zu lösen.

Zusammenfassung

Kurz gesagt ist NAVe ein Sicherheitsnetz für Entwickler, die datenschutzwahrende Anwendungen erstellen. Es übersetzt ihren Code in eine strikte mathematische Sprache und nutzt einen leistungsstarken Solver, um sicherzustellen, dass der Code genau das tut, was er behauptet – und fängt dabei subtile Bugs ab, die ansonsten zu Sicherheitsfehlern führen könnten. Es ist wie ein strenger Inspektor, der die strukturelle Integrität einer Brücke prüft, bevor jemand darauf fahren darf.

Technische Zusammenfassung: Formale Verifizierung von Noir Zero-Knowledge-Programmen mit NAVe

Problemstellung
Zero-Knowledge (ZK)-Beweissysteme stützen sich auf arithmetische Schaltkreise – Mengen von Polynomgleichungen über endlichen Körpern – um zu verifizieren, dass eine private Eingabe $W$ eine Relation $R(X, W)$ erfüllt, ohne $W$ preiszugeben. Hochsprachbasierte Domänenspezifische Sprachen (DSLs) wie Noir vereinfachen die Erstellung dieser Schaltkreise, indem sie Code in eine Zwischenrepräsentation namens ACIR (Abstract Circuit Intermediate Representation) kompilieren. Diese Abstraktion führt jedoch subtile Schwachstellen ein. Speziell unterstützt Noir „unconstrained code“ (über unconstrained-Funktionen und unsafe-Blöcke), der darauf ausgelegt ist, die Effizienz des Beweisers zu steigern, indem komplexe Berechnungen auf den Beweiser auslagert. Wenn Entwickler versäumen, manuell entsprechende Constraints (z. B. via assert-Statements) für die Ergebnisse von unconstrained Code hinzuzufügen, spiegelt der generierte arithmetische Schaltkreis die beabsichtigte Relation möglicherweise nicht korrekt wider. Dieser „unter-beschränkte“ (under-constrained) Bug kann zu schwerwiegenden Sicherheitslücken führen, wie etwa der Erlaubnis eines Beweisers, gültige Beweise für falsche Aussagen zu generieren. Bestehende formale Verifizierungswerkzeuge zielen weitgehend auf niedrigere Schaltkreis-DSLs (wie Circom) ab oder erfordern interaktives Theorembeweisen, wodurch ihnen eine automatisierte, skalierbare Verifizierung für hochsprachbasierte Noir-Programme und deren spezifische Merkmale wie Speichermanipulation und Black-Box-Funktionen fehlt.

Methodik
Die Autoren schlagen NAVe (Noir Acir Verifier) vor, ein Open-Source-Formal-Verifizierungs-Framework, das auf der ACIR-Zwischenrepräsentation operiert, anstatt auf dem hochsprachbasierten Noir-Quellcode. Diese Wahl gewährleistet Stabilität gegenüber der Evolution der Sprache und ermöglicht es dem Tool, potenziell andere Sprachen zu unterstützen, die auf ACIR abzielen.

Formalisierung via SMT-LIB: Der Kern von NAVe ist eine Formalisierung einer Teilmenge von ACIR-Opcodes in Satisfiability Modulo Theories (SMT)-Formeln. Die Autoren implementieren zwei unterschiedliche Kodierungen:
- Endlicher Körper-Kodierung (Finite Field Encoding): Nutzt eine nicht-standardmäßige Theorie endlicher Körper primärer Ordnung, die im cvc5-Solver implementiert ist. Dieser Ansatz verwendet spezifische Operatoren wie ff.add, ff.mul und ff.bitsum, um die Körperarithmetik direkt zu modellieren.
- Ganzzahl-Arithmetik-Kodierung (Integer Arithmetic Encoding): Nutzt die Standardtheorie der ganzen Zahlen in SMT-LIB. Sie stützt sich auf den Isomorphismus zwischen endlichen Körpern primärer Ordnung $p$ und ganzen Zahlen modulo $p$ , wobei Körperoperationen als modulare Ganzzahlarithmetik (z. B. (mod (+ ...) p)) kodiert werden.
Opcode-Semantik: Die Formalisierung deckt wesentliche ACIR-Opcodes ab:
- AssertZero: Kodiert als eine durch eine Polynomgleichung definierte Constraint, die gleich Null ist.
- BlackBoxFuncCall: Speziell formalisiert für den Range-Check-Opcode. In der Finite-Field-Kodierung wird dies mittels einer binären Zerlegung (bitsum) modelliert und durch Constraints ergänzt, die sicherstellen, dass die Bits 0 oder 1 sind. In der Integer-Kodierung wird dies unter Verwendung von Standard-Ganzzahl-Ordnungsbeschränkungen ( $x < 2^n$ ) modelliert.
- MemoryOp und MemoryInit: Formalisiert zur Verfolgung von Array-Mutationen mittels einer Map von Indizes zu Witness-Werten, wobei sowohl Lese- als als auch Schreibvorgänge sequenziell gehandhabt werden.
- BrilligCall: Repräsentiert unconstrained Code; diese werden als die immer erfüllte Constraint true (oder ignoriert) übersetzt, da das Ziel des Verifizierers darin besteht, die Constraints außerhalb der unconstrained Blöcke zu prüfen.
Verifizierungs-Workflow:
- Das Tool integriert sich mit Nargo, dem Noir-Paketmanager, als ein formal-verify-Befehl.
- Entwickler annotieren Noir-Programme mit verify_assert(b: bool)-Statements. Im Gegensatz zu Standard-assert-Statements, die arithmetische Schaltkreis-Constraints generieren, erzeugt verify_assert eine Beweisverpflichtung (proof obligation).
- NAVe kompiliert das Noir-Programm zu ACIR, übersetzt die ACIR-Opcodes in SMT-Formeln und konstruiert eine Verifizierungsformel $F = \text{ACIR}_{\text{constraints}} \land \neg \text{verify\_assert}_{\text{condition}}$ .
- Der cvc5-Solver prüft die Erfüllbarkeit von $F$ . Wenn $F$ unerfüllbar (unsatisfiable) ist, ist die Verifizierungsbedingung erfüllt (das Programm ist korrekt beschränkt). Wenn $F$ erfüllbar (satisfiable) ist, liefert der Solver ein Modell (Gegenbeispiel), das eine Witness-Zuweisung zeigt, welche die Bedingung verletzt, was die Fehlersuche erleichtert.

Wesentliche Beiträge

Formalisierung von ACIR: Die erste Formalisierung einer Teilmenge der ACIR-Sprache unter Verwendung von SMT-LIB, die komplexe Funktionen wie Speicheroperationen, Range-Checks und die Unterscheidung zwischen beschränktem und unbeschränktem Code abdeckt.
Duale Kodierungsstrategie: Der Vorschlag zweier komplementärer Kodierungen (Finite-Field-Theorie und Ganzzahl-Arithmetik), um unterschiedliche Solver-Kapazitäten zu nutzen.
NAVe-Tool: Ein Open-Source-automatisierter formaler Verifizierer, der in das Noir-Ökosystem (Nargo) integriert ist und darauf ausgelegt ist, für Entwickler ohne die Notwendigkeit von interaktivem Theorembeweisen zugänglich zu sein.
Empirische Evaluierung: Eine umfassende Evaluierung von NAVe anhand einer Suite von Noir-Testprogrammen, die die Performance über verschiedene Constraint-Typen und Solver-Konfigurationen hinweg analysiert.

Ergebnisse
Die Autoren evaluierten NAVe auf 4 distinkten Sätzen von Noir-Programmen (verifizierte Bedingungen, falsifizierte Bedingungen, mit und ohne Range-Checks) unter Verwendung des cvc5-Solvers.

Solver-Performance: Kein einzelnes Backend (Integer-Kodierung, Finite-Field --ff=gb oder Finite-Field --ff=split) war konsistent leistungsfähiger als die anderen. Die Ergebnisse zeigen, dass die Kodierungen komplementär sind; einige Programme werden schneller durch eine Kodierung gelöst, während andere bei derselben Kodierung einen Timeout verursachen, aber bei einer anderen erfolgreich sind.
Auswirkung von Range-Checks: Programme, die Range-Checks enthalten (BlackBoxFuncCall-Opcodes), erhöhten die Verifizierungszeit signifikant. Die --ff=split-Konfiguration, die die Finite-Field-Theorie approximiert, zeigte eine überlegene Performance bei Programmen mit großen Range-Checks im Vergleich zur Standard --ff=gb-Konfiguration, obwohl bei komplexen Fällen weiterhin Timeouts auftraten.
Gegenbeispiel-Generierung: Das Tool konnte erfolgreich Gegenbeispiele für falsifizierte Bedingungen generieren, was seinen Nutzen bei der Identifizierung von unter-beschränktem Code (under-constrained logic) demonstriert.

Bedeutung und Ansprüche
Das Paper behauptet, dass NAVe eine kritische Lücke im ZK-Ökosystem schließt, indem es eine automatisierte, skalierbare Methode zur Verifizierung von hochsprachbasierten ZK-Programmen auf unter-beschränkte Bugs bietet – eine Klasse von Fehlern, die zu realen Sicherheitslücken geführt hat. Durch die Zielsetzung auf ACIR bleibt das Tool robust gegenüber Änderungen der hochsprachbasierten Noir-Syntax und ist potenziell auf andere Sprachen anwendbar, die auf dieselbe Zwischenrepräsentation abzielen.

Die Autoren rahmen ihre Arbeit bescheiden als einen Schritt hin zu breiteren Verifizierungsmöglichkeiten ein. Sie räumen ein, dass ihre aktuelle Formalisierung nur eine Teilmenge von ACIR abdeckt (unter Ausschluss rekursiver Call-Opcodes und der meisten BlackBoxFuncCalls außer Range). Sie identifizieren die hohen Kosten der Verifizierung von Range-Checks als primäre Einschränkung und schlagen vor, dass zukünftige Arbeiten darauf fokussieren müssen, Abstraktionen oder Approximationen zu entwickeln, um diese komplexen Constraints effizient zu handhaben. Das Paper positioniert NAVe nicht als vollständige Lösung für alle ZK-Verifizierungsbedürfnisse, sondern als ein praktisches, integriertes Werkzeug, das die Machbarkeit automatisierter formaler Verifizierung für Noir demonstriert und einen Weg für die Verbesserung des Solver-Handlings komplexer Bit-Level-Constraints aufzeigt.