Tech Talks, Projekte und Forschung

Tech-Talk: Wie funktionieren Zero-Knowledge Proofs?

Markus Knecht | 17. April 2025

In diesem Teck-Talk gab Markus Knecht einen Einblick in die Funktionsweise von Zero-Knowledge Proofs (zkP), sowie den Bausteinen, die für sogenannte Zero Knowledge Virtual Machines (zkVM) verwendet werden. Dabei wurde der STARK (Succinct Transparent Argument of Knowledge) Algorithmus anhand eines Beispiels vorgestellt. Im Beispiel wurde gezeigt, wie man für eine minimalistische virtuelle Maschine, bestehend aus einer trivialem CPU und einem unveränderlichen Memory, die korrekte Ausführung eines Programms beweisen kann.

Zero Knowledge Proofs

Ein Zero Knowledge Proof is ein kryptografisches Verfahren welches es einem erlaubt zu Beweisen, dass man die Inputs zu einer Funktion kennt, so dass diese zu wahr evaluiert. Dabei hat ein Zero-Knowledge Proof zwei Vorteile gegenüber dem erneuten Ausführen der Funktion.

  • Das Verifizieren des Beweises hat eine Zeit-Komplexität von O(log2(n)) für STARKs wobei n von der Laufzeit der Funktion abhängt. Oder anders ausgedrückt hätte das erneute Ausführen der Funktion die Zeit-Komplexität O(n). Für rechenintensive Funktionen, deren Ausführung mehrfach geprüft werden muss (z.B. von verschiedenen Parteien), kann somit Zeit eingespart werden.
  • Der Ersteller des Beweises (Prover) kann selektiv entscheiden, welche Inputs der Funktion er offenlegt und welche er geheim hält. Die Funktion selbst muss jedoch auch dem Überprüfer des Beweises (Verifier) bekannt sein.

Theoretische Konstruktionen für universelle Zero-Knowledge Proofs sind bereits länger bekannt, jedoch war das Erstellen von Beweisen mit einem unpraktikablen hohen Aufwand verbunden. Mit dem Aufkommen der Blockchain Technologie stieg das Bedürfnisse für Zero-Knowledge Proofs an, was zu mehr Forschung führte welche in praktisch einsetzbaren Protokollen, wie zum Beispiel dem STARK Algorithmus, geführt haben.

Historie von Zero Knowledge Proofs

Über die letzten Jahren haben Zero Knowledge Proof Systeme rasante Fortschritte gemacht und mehrere Generationen durchlaufen, welche zu den heute einsetzbaren Zero-Knowledge Virtual Maschines führten.

  • Erste Generation: Problem Spezifische Zero Knowledge Proofs
    Es musste für jede Funktion von Hand eine analoge mathematische Beschreibung erstellt werden. Dieser Prozess dauerte lange und setzte Expertenwissen voraus und wurde deshalb nur sehr spärlich verwendet.
  • Zweite Generation: Baustein Basierte Zero Knowledge Proofs
    Experten entwickeln Bausteine, wie zum Beispiel ein Baustein, um Hashfunktionen zu berechnen. Diese können dann von Entwicklern mit weniger Wissen kombiniert werden, um daraus komplexere Funktionen zu bauen.
  • Dritte Generation: CPU’s mit vereinfachtem Instruktionsset
    Experten entwickeln zkP’s, welche ausführbaren Bytecode als Input verwenden und dessen korrekte Anwendung auf die anderen Inputs beweisen. Dadurch können nun beliebige Programme ausgeführt werden. Die Fähigkeiten dieser Virtuellen CPU’s und des zugehörigen Instruktionssatzes waren jedoch oft sehr limitiert.
  • Vierte Generation: Zero Knowledge Virtual Machines
    Die Weiterentwicklung der dritten Generation beinhalteten nun gängige Komponenten wie ein Read-Write Memory, kryptografische Co-Prozessoren und vieles mehr. Den grössten Impakt hatte jedoch die Entwicklung von Techniken, welche das effiziente Ausführen gängiger Instruktionssätze wie zum Beispiel RISC-V erlaubte, wodurch Programme nun in gängigen Sprachen wie C, Rust oder C++ geschrieben werden können.

Nicht nur hat sich die Art wie man zkP’s erstellt über die Generationen geändert, sondern es gab auch massive Fortschritte was die Effizienz der Beweiserstellung angeht und es werden weiterhin rasante Fortschritte erzielt.

Succinct Transparent Argument of Knowledge (STARK)

Der STARK Algorithmus wurde genauer vorgestellt, welcher sich vor allem im Bereich der zkVM’s etabliert hat, da er einige Vorteile gegenüber Alternativen bietet:

  • Die Struktur des Algorithmus eignet sich gut für wiederholende Operationen (Schleifen).
  • Der Algorithmus skaliert gut sodass es keine Beschränkung der Laufzeit des auszuführenden Programmes gibt.
  • Der Algorithmus und sein Setup sind transparent, was soviel bedeutet wie das kein Setup benötigt wird in dem geheimen Informationen (wie private Schlüssel) involviert sind.
  • Der Algorithmus basiert auf etablierten als sicher geltenden kryptographischen Annahmen (Existenz von Einweg Funktionen, auch Hashfunktionen genannt).
  • Der Algorithmus ist resistent gegen Angriffe von Quantenrechnern.

Ausführungsrepräsentation

Der Algorithmus basiert im Kern auf einem sogenannten Ausführung-Trace. Das heisst, man hatte eine Menge von Zellen die den momentanen Ausführungszustand enthalten. Diese werden gebraucht um die Werte von Registern sowie interne Berechnungszuständen abzubilden. Danach wird wiederholt einen neuen Zustand aus dem vorherigen berechnet. Dies ist analog zur funktionsweise eines CPU’s, welcher in jedem Zyklus neue Werte für einige seiner Register basierend auf den vorherigen Registerwerte berechnet. Im Unterschied zur funktionsweise in einem CPU wird bei einem STARK der alte Zustand nicht überschrieben. Stattdessen bildet der neue Zustand eine neue Zeile im Ausführungs-Trace. Der Trace ist somit eine Tabelle wobei die Zeilen dem Zustand zwischen den Berechnungsschritten entsprechen und die Spalten der Entwicklung der Werte eines Registers während der Ausführung. Eine Zelle ist somit der Wert eines Registers nach einem Bestimmten Ausführungsschritt.

Berechnungsrepresentation

Um für einen solchen Trace einen Beweis zu erstellen, dass sowohl der Initial/Endzustand sowie alle Zustands Übergänge korrekt berechnet wurden, und der Semantik der implementierten virtuellen Maschine entsprechen, wird eine mathematische Repräsentation dieser Semantik benötigt. Dazu wird ein aus Polynomen bestehendes Constraint-System erstellt. Ein Constraint-System besteht aus mathematisch formulierten und überprüfbaren Bedingungen. Das System ist so aufgebaut, dass nur wenn der Trace einer korrekten Ausführung entspricht alle Bedingungen eingehalten sind. Die Bedingungen werden als Polynome dargestellt welche zu 0 evaluieren wenn diese eingehalten sind.
Es gibt drei unterschiedlicher Bedingungstypen in einem herkömmlichen STARK System. Der Typ bestimmt, welche Zeilen als Input für das entsprechende Polynom verwendet werden:

  • Eingabe Bedingungen: Werden auf die erste Zeile angewandt und werden zur Etablierung eines korreten Startzustands, inklusive den Werten der öffentlichen Programmargumenten, verwendet.
  • Ausgabe Bedingungen: Werden auf die letzte Zeile angewandt und werden zur Etablierung eines korreten Endzustands, inklusive den öffentlichen Programmrückgabewerten, verwendet.
  • Übergangs Bedingungen: Werden auf jedes Paar von aufeinanderfolgenden Zeilen angewandt und werden zur Überprüfung von Zustandsübergängen verwendet.

Die meisten dieser Bedingungen sind statisch und beschreiben die Ausführungssemantik der zkVM. Einige sind pro Ausführung definiert und forcieren die öffentlichen Programmwerte (Argument oder Rückgabe) sowie den verwendeten Programmcode (Code Memory). Ein Beweis zusammen mit öffentlichen Werten aus einem Setup, enthalten alle Informationen sodass der Beweis-Überprüfer das ganze Constraint-System kennt, wodurch es die Basis für den Algorithmus bildet.

Beweiserstellung

Die Beweiserstellung geschieht im einem interaktiven Modell, in welchem der Beweiser und Überprüfer während der Beweis-Erstellung kommunizieren können. Die gesamte Kommunikation wird dabei in einem sogenannten Journal festgehalten. Solange die vom Überprüfer durchgeführten Berechnungen nur auf Werte aus dem Journal sowie Zufallszahlen als Inputs haben, kann die Fiat–Shamir heuristic angewandt werden, um den Überprüfer zu simulieren und die Interaktionsschritte aus der Beweis-Erstellung zu eliminieren. Die Beweiserstellung im STARK Algorithmus läuft folgendermassen ab.

Phase 1: Ausführung

  • Definieren des Initialzustandes (erste Zeile) durch setzten von öffentlichen und geheimen Werten in den entsprechenden Registern.
  • Erstellen des Ausführungtraces durch ausführen des Programms
  • Extrahieren der öffentlichen Rückgabewerte
  • Senden (im Journal festhalten) der öffentlichen Werte sowie vom Beweis-Überprüfer benötigte Metadaten wie die Anzahl der Zeilen im Trace.

Nach dieser Phase ist alles bekannt, so dass beide Seiten das anzuwendende Constraint-System konstruieren können.

Phase 2: Verschleierung

  • Der Trace wird am Ende um neue Zeilen mit zufälligen Werten ergänzt. Dies dient zum einen um geheime Daten zu schützen, wie auch um sicherzustellen, dass die Tracelänge eine Zweierpotenz ist, was die Effizienz der verwendeten Algorithmen steigert.
    (Auf diese zusätzlichen Zeilen werden keine Bedingungen geprüft)
  • Die Spalten des Traces werden als Polynome interpretiert, so dass die Auswertung an einem pro Zeile (Zustand) vorbestimmten Index Wert den zugehörigen Spalten (Register) Wert berechnet. Die Zeilen Index Werte sind von der Ausführungstrace-Länge ableitbar.
  • Die Spalten Polynome werden an weiteren unterschiedlichen Index Werten ausgerechnet um neue Zeilen zu generieren. Auch diese Inputwerte können aus der Ausführungstrace-Länge abgeleitet werden. Die Anzahl der neu generierten Zeilen ist ein vordefiniertes Mehrfaches der originallänge (z.B: das vierfache). Dieser Subalgorithmus zum ableiten von zusätzlichen Werten ist auch als Reed-Solomon-Code bekannt.

Nach dieser Phase sind beiden Parteien die Zeilen-Index-Werte für die Spaltenpolynome aller Zeilen bekannt. Die Spalten Polynome (und somit die Werte aller Zellen) sind nur dem Beweiser bekannt. Durch betrachten einzelner Zusatzzeilen kann kein Rückschluss auf die Werte im Ausführungstrace geschlossen werden. Dies würde erst möglich werden, wenn man gleich viele Zeilen hat, wie im Ausführungstrace waren.

Phase 3: Commitment

  • Aus allen zusätzlichen Zeilen (ohne den ursprünglichen Ausführungstrace) wird ein Commitment berechnet (Ein einzelner Wert). Die Commitment Berechnung basiert auf einem sogenannten Vector Commitment Scheme (STARK verwendet Merkle Trees).
  • Senden (im Journal festhalten) des Commitments an den Überprüfer.

Aus einem Commitment sind keine Rückschlüsse auf den Inhalt aus welchem dieses berechnet wurde möglich, aber es erlaubt selektive Inputs (in diesem Fall Zeilen) offenzulegen und zu beweisen, dass dies der Input war, welcher zur Commitment Berechnung verwendet wurde.

Phase 4: Constraint-Evaluation-Beweis

  • Die Polynome im Constraint-System haben Zeilen als Input. Dies ist das gleiche wie die Verwendung der Zeilen-Index-Werte als Input und substituieren der Spaltenzugriffe durch die Evaluation des entsprechenden Spaltenpolynoms an diesem Index-Wert. Dadurch erhält der Beweiser neue Polynome, die nur noch vom Zeilen-Index-Wert abhängig sind.
  • Für jeden Typ von Constraint (Input, Output und Transitive) wird ein sogenanntes Nullifier Polynom generiert, das genau für die Zeilen-Index-Werte zu 0 evaluiert auf welche die Constraint Polynom dieses Typs angewandt werden. Die Nullifier können aus der Ausführungstrace-Länge berechnet werden.
  • Der Beweiser berechnet nun sogenannte Validity Polynome in dem er jedes Constraint Polynom durch das entsprechende Nullifier Polynom dividiert. Hier kommt ein mathematischer Fakt zum Zuge, welcher besagt, dass ein Polynom nur durch ein anderes restlos dividierbar ist, falls alle Nullstellen im Divisor (Nullifier) auch Nullstellen im Dividend (Constraint) sind. Verletzte der Ausführungstrace eine Bedingung des Constaint Systems, so hat die division des entsprechenden Traces einen Rest.
  • Der Beweiser sendet (im Journal festhalten) die Validity-Polynome (deren Koeffizienten) an den Überprüfer.

Der Überprüfer hat nun alles was er braucht, um zu überprüfen, dass die Validity-Polynome korrekt berechnet wurden und die Division Restlos war. In realen Protokollen existiert vor dem Senden der Validity-Polynome noch ein extra Schritt, der es erlaubt, alle Validity-Polynome in eines zusammenzufassen.

Phase 5: Beweis Überprüfung

  • Zuerst überprüft der Überprüfer, dass die Anzahl Koeffizienten der Validity-Polynome einem bestimmten Threshold nicht unterschreiten (Dieser ist aus dem Constraint und der Ausführungstrace-Länge berechenbar). Dies ist nötig, um sicherzustellen, dass der Beweiser nicht ein gefälschtes Polynom liefert, welches das Resultat einer restbehafteten Polynomdivision interpoliert.
  • Der Überprüfer selektiert zufällig einige der Zusatzzeilen, zu welchen der Beweiser in Phase 3 Committet hat und sendet deren Zeilen-Index-Wert dem Beweiser (Journal Eintrag)
  • Der Beweiser legt die entsprechenden Zeilen offen und sendet sie dem Überprüfer (inklusive Beweis das sie zu dem Committment gehörten).
  • Der Überprüfer verwendet die Zeilen nun, um den Wert an der zugehörigen Stelle im entsprechenden Validity-Polynom zu berechnen, in dem er das Constraint-Polynom auf der offengelegten Zeile auswertet und durch die entsprechende Auswertung des Nullifier teilt.
  • Danach wertet der Überprüfer das Validity-Polynom über die übergebenen Koeffizienten aus und vergleicht die beiden Resultate.

Je mehr Punkte der Überprüfer auswertet, um so sicherer ist er, dass der Beweis korrekt ist. Dieser Verifizierungsalgorithmus hat eine lineare Zeitkomplexität im Vergleich zur Länge des Ausführungstraces, da die Validity-Polynome viele Koeffizienten haben (in der selben Grössenordnung wie die Länge des Ausführungstraces). In praktischen STARK Implementationen wird die Phase 5 deshalb mithilfe des FRI Algorithmus (Fast-Reed-Solomon Interactive Oracle Proof of Proximity) gemacht, welcher eine poly-logarithmische Zeitkomplexität hat.

Beweiserstellung in Excel

Während des Techtalks wurden anstelle von Folien ein Excel verwendet um die Inhalte zu Präsentieren. Dieses hatte nicht nur Fachliche Informationen sondern implementierte auch eine kleine Beispielshafte zkVM. Dabei wurden jedoch aus Gründen der Performanz einige Vereinfachungen gemacht, so wie ungenügend grosse Parameter gewählt. Deshalb ist diese nur für Demonstrationszwecke gedacht.

Excell zkVM und Erklärungen

zurück zu allen Beiträgen

Kommentare

Keine Kommentare erfasst zu Tech-Talk: Wie funktionieren Zero-Knowledge Proofs?

Neuer Kommentar

×