zkSNARKs: Krypto statt Ungeheur

Beweise ohne Wissen

Zero Knowledge Proofs (zk-Proofs) sind ein Konzept, mit dem man Beweise ohne weiteres Wissen erbringen kann: Man beweist anderen Akteuren etwas, ohne ihnen Informationen über die bewiesenen Dinge selbst geben zu müssen. Dieser Vorgang ersetzt an vielen Stellen Vertrauen oder Reputation – und damit eine Funktion, die heute neutrale Institutionen übernehmen, oder die erst über Zeit belastbar entsteht. Technische Lösungen können für diese Beweise bald sofortige Sicherheit bieten. Für digitalisierte geschäftliche Abläufe hat das enormes Potenzial.

Im Blog beschreibe ich die technischen Grundlagen.

Bei Zero Knowledge Proofs gibt es immer jemanden, die_der etwas nachweist, den sogenannten Prover, und denjenigen, der_dem etwas bewiesen wird, den Verifier. Der Vorteil liegt auf der Hand: Man kann auf Mittelsmänner verzichten, die bezahlt werden müssen oder einen Prozess verlangsamen. Es kommen andere Vorteile hinzu: Beispielsweise schließt man durch den automatisierten Proof menschliche und Hardware-Fehler aus. Letztlich basieren zk-Proofs auf Berechnungen*, und mit ihnen kann sichergestellt werden, dass das Gegenüber richtig gerechnet hat. Hinzukommt, dass keine “trusted Hardware”, etwa Intel SGX, verwendet werden muss. Und schließlich können sogar auf einem kompromittierten System nur Proofs erstellt werden, die entweder korrekt sind, oder durch den Verifier als falsch erkannt werden. Natürlich gelten diese Aussagen nicht für jedes zk-Proof-System gleichermaßen. Aber es gibt schon Ansätze, die fast alles bieten.

---

Ein falsches Ergebnis als ein Korrektes auszugeben ist praktisch nicht möglich, solange die kryptographischen Annahmen halten. In diesem Fall gilt die knowledge-of-exponent-Annahme, das heißt, dass es der Teil im Protokoll ist, der theoretisch am einfachsten angreifbarer ist. Aktuell wird davon ausgegangen, das diese unsicherer ist als beispielsweise die Diskreter-Logarithmus-Annahme, aber immer noch als vergleichsweise sicher gilt. Sicher – oder praktisch nicht verfälschbar – bedeutet hier: Computational Soundness. Im Gegensatz zu Perfect Soundness, die jedem theoretischen Angriff mit unbegrenzter Hardware widerstehen kann, gilt für Computational Soundness “nur” eine gewisse Wahrscheinlichkeit, nicht per Brute-Force-Verfahren gebrochen werden zu können. Das Brechen mit heutiger und aus realistisch betrachteter Zukunft stammender Hardware gilt aber als astronomisch unwahrscheinlich (mit SNARKs im Bereich 1/2^128).

---

George R.R. Martin-Fans sind Snarks aus Nan’s Erzählungen bekannt. Eingeführt wurden die Fabelwesen im englischen Sprachraum von Lewis Carroll. Diese wunderschönen Illustrationen erstellte Illustrator Henry Holiday für dessen Buch “The Hunting Of The Snark”. Der Begriff hat mittlerweile viele verschiedene Bedeutungen. Mehr bei Wikipedia.

zkSNARKs: kurze Beweise ohne Interaktion fürs Verifizieren

Eine Spielart von zk-Proofs sind zkSNARKs. zkSNARK steht für “zero-knowledge Succinct Non-Interactive Argument of Knowledge”.

Kurz zusammen gefasst ist das ein Beweis (Argument of Knowledge), der kurz (Succinct) und nicht interaktiv (Non-Interactive) ist. Nicht-interaktiv meint hier ohne Interaktion zwischen Prover und Verifier, über das Teilen des Proofs selbst hinaus. Hinzu kommt die oben beschriebene Eigenschaft “zero knowledge”, also dass der Verifier Eingangswerte und/oder Ausgangswerte nicht kennen muss.

Die Beweise drehen sich meist um die korrekte Ausführung bestimmter Programme: Man kennt Input-Werte, die nach dem Durchlaufen des Programms bestimmte Output-Werte liefern. Hierbei steht es dem Prover frei, bestimmte Werte geheim zu halten oder öffentlich zu machen. Ein Beispiel:

Die Aufgabe ist das Finden von drei Primfaktoren einer Zahl, zum Beispiel 7 * 5 * 2 = 70. Hierbei kann der Beweis so aufgebaut sein, dass man nur beweist, das man drei valide Zahlen hat. So offenbart man nur die Gültigkeit des Ergebnisses, und nicht die Lösung. Alternativ könnte man eine der Zahlen offenbaren, etwa die 2. Daraus wird klar, dass wir die beiden anderen Zahlen kennen, nämlich 5 und 7, die zusammen mit der 2 als dritter, öffentlicher Zahl das gewünschte Ergebnis “70” liefern.

zkSNARKs sind eine relativ neue Technologie. Das Besondere an ihnen ist, dass sie fast vollständig generell sind, und man quasi alles Erdenkliche beweisen kann – wenn das zu beweisende Programm eine endliche Laufzeit hat, und wenn die Hardware gut genug ist. Dieser letzte Punkt ist ein wesentlicher Faktor für die Arbeit mit zk-SNARKs: Die Berechnung der Proofs ist aktuell extrem speicher- und rechenintensiv, hier ist eindeutig noch Luft nach oben, auch wenn einige neuere Entwicklungen deutliche Verbesserungen bringen. So konnte das zCash-Projekt beispielsweise die Generierung von Proofs von im Schnitt 37 Sekunden auf 2,3 Sekunden reduzieren. Dabei darf man nicht vergessen, dass bestimmte Operationen sehr effizient umgesetzt werden können, zum Beispiel x + y. Andere Berechnungen, etwa etwa x < y, fordern erheblich mehr Aufwand und damit Rechenpower. Warum das so ist, werden wir später sehen.

Dass die Ausführung des Programms korrekt war, ist für den Verifier immer nur eine Wahrscheinlichkeit. Bei der Konstruktion des Protokolls ist es relativ frei wählbar, wie hoch diese Wahrscheinlichkeit ist. Gewöhnlich wird sie so hoch gewählt (zb. 1 – 1/2^128), dass eine Computational Soundness (im Gegensatz zu Perfect Soundness, siehe oben) erreicht wird. Das bedeutet, dass eine falsch-positive Verifizierung mit absehbarer Hardware-Entwicklung praktisch unmöglich ist.

SNARK ist nur ein Technologie-Ansatz mit vielen verschiedenen Implementierungsmöglichkeiten. Dabei können Teile des Ganzen durch alternative Konzepte ersetzt werden. Und es gibt nicht den einen SNARK, sondern eine Reihe von verschiedenen Möglichkeiten. Aktuelle Alternativen betrachten wir am Ende des Artikels.

Mögliche Anwendungen

zk-Proofs können in vielen Anwendungsfällen benutzt werden. Besonders interessant sind sie in Verbindung mit Blockchain-Technologie. So können alle Vorteile von öffentlichen Blockchains genutzt werden, ohne schützenswerte (etwa geheime oder persönliche) Daten öffentlich zu machen.

Ein Beispiel ist einer der bekanntesten Use Cases von Blockchain, dezentrales Geld. Die zCash Blockchain ermöglicht das vollkommen anonyme Versenden von Geld, d.h. weder Sender noch Empfänger noch der Betrag der Transaktion sind bekannt. (Im Moment ist übrigens nicht jede Transaktion in zCash anonym, die Option muss extra ausgewählt werden.) Das Ganze läuft auf Basis von zkSNARKs. Hierbei garantieren die Proofs, dass der Sender das Geld tatsächlich hat und das durch die Transaktion kein neues Geld geschaffen wurde. Sicherheit über die Unmöglichkeit, neues Geld zu erschaffen, wird durch die korrekte Durchführung des “Trusted Setups” von zCash erreicht. Mehr dazu im nächsten Kapitel.

Auf Ethereum lässt sich das Ganze dank der Ethereum Virtual Machine (EVM) noch weiter treiben. Da die EVM quasi Turing-vollständig ist und mit SNARKs fast beliebige Programme bewiesen werden können, sind den Anwendungsfällen kaum Grenzen gesetzt. Da das Erstellen von Proofs aber noch recht teuer ist, sind ist sie in der Größe aktuell noch sehr beschränkt. Ein Beweis für das korrekte Rendern eines Bilds oder Films in einem dezentralen Umfeld wäre ein schöner Anwendungsfall, der derzeit noch am Aufwand der Berechnungen scheitert.

Wenn man die Blockchain als unparteiischen Schiedsrichter betrachtet, kann sie – wie anfangs erwähnt – zusammen mit zk-Proofs in jeder Branche bezahlte Mittelsmänner oder langwierigen Reputationsaufbau überflüssig machen. Dabei geht es nicht immer um große Abläufe, hinter denen eigene weitreichende Geschäftsmodelle stehen. Es können auch sehr überschaubare Services abgelöst werden, etwa das Einloggen über einen externen Login-Dienst. Im Vergleich zu anderen Diensten wie Google oder Facebook könnte der Nachweis deutlich datensparsamer werden: Eine Anwendung die SNARKs zur Anmeldung nutzt kann sicher stellen, dass sich ein echter Mensch anmeldet. Wenn die Person nun beweisen könnte, dass sie ein echter Mensch ist, beispielsweise dadurch, dass sie ein deutscher Staatsbürger ist, ohne dabei gleich sämtliche persönlichen Daten offenlegen zu müssen, dann bräuchte man den Vertrauen schaffenden Mittelsmann nicht mehr.

Sinnvolle Verwendung können zkSNARKs auch bei Wahlen oder beim Authentifizieren finden. Wie man beispielsweise eine Wahl umsetzten könnte, werden wir im zweiten Teil diese Artikels sehen.

SNARKs (ohne zk) können für Anwendungsfälle genutzt werden, in denen Geheimhaltung nicht wichtig ist, sondern nur die korrekte Ausführung von Berechnungen. Genutzt wird das schon heute für die Skalierung der Ethereum Mainchain, beispielsweise durch Roll-up. Hierbei werden mehrere Transaktionen off-chain aggregiert und dann in einer einzigen State-Veränderung auf die Mainchain gebracht. Das spart den Overhead von vielen einzelnen Transaktionen und garantiert trotzdem die korrekte Anwendung der einzelnen State-Veränderungen.

Es gibt bereits Anwendungsfälle, in denen das Konzept in Erprobung ist:

• Identitätsbeweise: etwa der Beweis eines bestimmten Mindestalters, ohne das Alter konkret anzugeben oder weitere Daten zum Beweis angeben zu müssen (Namen, Wohnort);
• Spiele mit nicht perfekter Information: beim Spiel “Schiffe versenken” der Beweis, das an einer bestimmten Stelle wirklich kein Schiff ist;
• Ultra Light Clients: sie erhalten von Light Servern Proofs über den aktuellen State der Chain, ohne selber aufwendig die Korrektheit überprüfen zu müssen; sie bekommen ähnliche Sicherheit wie eine Full Node;
• Constant Size Blockchains wie coda: durch rekursive SNARKs kann die Korrektheit der Blockchain bis zu einem gewissen Block garantiert werden, d.h. alte States/Blöcke müssen bei einem sync nicht mehr überprüft werden;
• Private Smart Contracts mit wenig Speicherverbrauch, hierbei beweisen die Proofs, dass Berechnungen mit dem korrekten Code durchgeführt wurden und dass die State-Veränderung valide ist. Code und Storage müssen dabei off-Chain zwischen Teilnehmern geteilt werden.

Aufbau

In diesem Teil gehen wir grob über den theoretischen Aufbau von zkSNARKs. Um tiefer einzusteigen, braucht man Wissen über elliptische Kurvenkryptographie, Polynome allgemein und natürlich etwas Informatik. Weiterführende Links gibt es weiter unten.

Die ersten Schritte zeigen bereits, wie das Programm verarbeitet werden muss, um bewiesen werden zu können. Mit diesem Wissen kann man das eigene Programm so gestalten, dass Beweise deutlich schneller und leichtgewichtiger erzeugt werden können. Schon die Wahl der richtigen Hashfunktion kann einen 10-fachen Vorteil bringen (sha-256 vs. MiMC).

Die Grafik von Eran Tromer bei medium.com zeigt den Ablauf.

Ganz am Anfang haben wir ein beliebiges Programm, dessen korrekte Ausführung wir beweisen wollen. Wir reden hier also immer von dem Konzept “Programm” und nicht von einem bestimmtem. Noch sind die Tools nicht so weit, dass es in einer beliebigen Programmiersprache geschrieben sein kann. Aber es gibt schon die ersten neuen Sprachen, die hierfür geeignet sind. Im zweiten Teil des Artikels wird in einem Beispiel eine solche verwendet werden.

Das Programm kann also nicht direkt verwendet werden, deshalb können wir auch noch keine herkömmlichen Sprachen verwenden. Zunächst muss es in einen sogenannten Algebraic Circuit umgewandelt werden, da SNARKs nur arithmetische Berechnungen beweisen können. Die neuen Sprachen sind extra darauf ausgelegt, direkt in solche Circuits zu kompilieren. Dieses Umwandeln wird auch Flattening genannt. Sämtliche Operationen werden in eine simple Form gebracht, die in etwa so aussehen können:

temp_1 = in_1 * in_1
~out = temp_1 * in_1

Hier wird eine Input-Variable (in_1) hoch drei genommen. Das Ergebnis der ersten Operation wird in eine Output-Variable (~out) geschrieben.

Diese Circuits müssen nun in ein sogenanntes Rank-1-Constraint-System (R1CS) gebracht werden, um sie anschließend als Polynome codieren zu können. Das R1CS besteht hier aus 4 Vektoren, wobei es die drei Vektoren a, b und c gibt, sowie den Vektor s, der als Lösung dient. Die vier Vektoren müssen folgende Formel bilden, wobei “.” das Skalarprodukt zweier Vektoren bildet:

s . a * s . b - s . c = 0 

Außerdem müssen die Variablen der Circuits auf den Vektor s gemappt werden. Hier wäre das:

('in_1', 'temp_1', '~out')

Eventuell braucht man eine Dummy-Variable ~one, um Konstanten zu definieren.

Die Variablen dieses Vektor haben alle einen eindeutigen Wert, wenn der Inputwert feststeht. Diesen Vektor nennt man Witness. Für den Wert 5 würde der Vektor lauten:

(5,25,125)

Nun müssen die Vektoren a, b und c für jeden Constraint, das heißt: jede Zeile, so gewählt werden, dass das R1CS korrekt ist. Es gibt bestimmte Standardmethoden für die Operationen plus, minus, mal oder geteilt. Für das erste Constraint würde das so aussehen:

a = (1,0,0)
b = (1,0,0)
c = (0,1,0)

Das System wäre also:

(5,25,125) . (1,0,0) * (5,25,125) . (1,0,0) - (5,25,125) . (0,1,0) = 0
5 * 5 - 25 = 0

Alle Constraints zusammen sehen dann so aus:

A
 (1,0,0)
 (1,0,0)
B
 (1,0,0)
 (0,1,0)
C
 (0,1,0)
 (0,0,1)

Here is also the biggest potential performance gain for a developer looking to write SNARK circuits. This conversion shows how important it is to have circuits that are as small as possible and have few constraints. Of course, the constraints still have to be chosen in such a way that cheating is not possible. Sometimes, for example, input 1 is a simple solution (e.g. when finding factors), which is not desired because it does not correspond to the original intention of the use case. So certain checks are important.

Next, the R1CS must be converted into so-called QAPs (Quadratic Arithmetic Program) . In principle, this means that the vectors are converted into “equivalent” polynomials. The polynomials are constructed in such a way that at certain values ​​for x, namely the corresponding constraints, they again have the values ​​of the previously found vectors.

Jetzt müssen wir nur noch eine Lösung für unser QAP finden. Da wir nun Polynome anstelle von lauter einzelnen R1CSs haben, können wir alles auf einmal lösen. Hierfür suchen wir ein Polynom Z, das folgende Gleichung löst:

A(x) * B(x) - C(x) = H * Z(x)

Um das ganze System zu prüfen, müssen wir jetzt verifizieren, ob Z an allen Constraints gleich 0 ist.

Ab diesem Punkt wird es deutlich komplexer. Deswegen schauen wir uns die nächsten Schritte vereinfacht an. Für alle die tiefer eintauchen möchten sei diese Artikelserie von Vitalik Buterin: Teil 1, Teil 2, Teil 3 empfohlen.

Im nächsten Schritt geht es weiter mit bilinearen elliptischen Kurven, die durch das Trusted-Setup möglich werden. Das Trusted-Setup bringt hierbei die nötigen Faktoren, die die beiden Kurven “verknüpfen”. Es darf nicht von der einen Kurve auf die andere geschlossen werden können, sonst ist die zero-knowledge-Eigenschaft gebrochen, bzw. es können “falsche” Proofs erstellt werden, die alle Verifizierer als korrekt deuten würden.

Die Polynome aus der Gleichung oben werden in eine lineare Kombination von elliptischen Kurvenpunkten umgewandelt. Diese Kombination wird dann auf der anderen Kurve dargestellt. Die resultierende Kombination ist schließlich der Proof. Ein Verifizierer kann überprüfen, dass das Gleichungssystem korrekt ist, dass alle Schritte korrekt durchgeführt wurden; er weiß trotzdem nicht, wie die tatsächlichen Lösungen aussehen.

Diese starke Vereinfachung hilft hoffentlich zu verstehen, wie das Konzept funktioniert.

Tradeoffs zu anderen Systemen

Es gibt andere Proof-Systeme als Alternative zu SNARKs, die ähnliche Funktionen bei anderen Tradeoffs mitbringen.

Zum einen gibt es den Ansatz, spezielle, genau angepasste und dadurch sehr optimierte Proofs zu verwenden. Damit erreicht man sehr genau das, was man möchte. Dafür ist der Aufwand natürlich größer, da man, sofern der Anwendungsfall nicht bereits gemacht wurde, selbst die nötigen Proofs konzipieren und umsetzen muss. Außerdem müssen meist neue Proofs beziehungsweise Protokolle für Erweiterungen oder Änderungen des Anwendungsfalls erstellt werden. Der Overhead ist hierbei deutlich größer als bei der Nutzung von existierenden Tools für generelle Proofs.

Der größte Vorteil hierbei ist die Möglichkeit, deutlich kleinere und schnellere Proofs nutzen zu können. Gerade im Zusammenhang mit Blockchains, wo Rechenleistung und Aufwand recht teuer sind, kann sich der höhere Aufwand lohnen. Ein hervorragendes Beispiel ist hier das Aztec-Protokoll. Es erzeugt und nutzt private ERC-20 Token; dafür ist es bereits heute nutzbar und Transaktionen kosten “nur” 500.000 – 900.000 Gas. Durch das vorgeschlagene EIP-1108 kann das auf 300.000 Gas und weniger reduziert werden. Normale ERC-20 Transfers kosten etwa 50.000 Gas. Die private Transaktion könnte also nur sechs Mal so viel kosten. ERC-20 Transfers mit zkSNARKs kosten etwa 1.600.000 Gas, sind aktuell also etwa doppelt so teuer wie Aztec-Transfers.

Zum anderen gibt es Alternativen, die genau wie SNARKs Beweise für alle möglichen Arten von Probleme erstellen können, sind STARKs und Bulletproofs. Beides sind noch recht junge Konzepte. Sie teilen die Eigenschaften zero knowledge und Anwendbarkeit auf generelle Probleme mit SNARKs.

STARKs haben beispielsweise kein trusted Setup. Damit umgehen sie eine der größten Schwächen von SNARKs. Sie gelten aktuell als Post-Quantum sicher, haben dafür aber noch deutlich größere Proofs (ca. 40kb). Hier gab es in den letzten Monaten schon deutliche Verbesserungen, dank eines koordinierten Forschungsaufwandes.

Bulletproofs können auch auf ein trusted Setup verzichten, aber der Aufwand für den Verifizierer wächst linear mit der Größe des Proofs. Gerade für On-Chain-Verifizierung ist das natürlich sehr unpraktisch.

Alternativen gibt es also – nicht unwichtig für den Fall, dass nicht alle Systeme ungebrochen bleiben. Für einen Überblick sei die Zusammenstellung bei github.com/matter-labs empfohlen.

Und was kommt noch?

Die Zukunftsaussichten für SNARKs sind sehr gut. Es gibt bereits Post-Quantum-sichere Ansätze, basierend auf Lattice-Kryptographie. Der Ansatz ersetzt die Elliptischen-Kurven-Operationen durch Lattice-Äquivalente.

SONICs, eine alternative SNARK-Konstruktion, verfolgen einen fast komplett neuen Ansatz. Hier kann man Verbesserungen auf jeder Ebene erwarten. So reicht hier ein einzelnes Trusted-Setup für alle möglichen Proofs, auch anwendungsübergreifend. Wenn das dann mit einer Multi-Party-Computation (MPC) mit großer Teilnehmerzahl generiert wird, dann kann das Vertrauen in die Sicherheit sehr groß sein. Alle folgenden Anwendungsfälle können fortan dieses eine Setup nutzen. Zwar ist das Trusted-Setup leider immer noch nicht vollständig eliminiert, aber es ist ein riesiger Schritt vorwärts.

Zusätzlich wird das Trusted-Setup nochmal deutlich vertrauenswürdiger, da weiter auf dem Bestehenden aufgebaut werden kann. Die generierten Parameter können also nachträglich noch verbessert und damit sicherer gemacht werden. Da die MPC so aufgebaut ist, dass nur einer der Teilnehmer ehrlich handeln muss, um alles sicher zu machen, bietet die kontinuierliche Erneuerung eine fast vollständige Beseitigung des Trusted-Setups. Denn wenn man beispielsweise keinem der ursprünglichen Teilnehmer vertraut, kann man einfach nachträglich noch teilnehmen und selbst dafür sorgen, dass man dem Setup vertrauen kann.

Noch aktueller ist ein Paper, das eine Konstruktion mit dem Namen Spartan beschreibt. Diese ermöglicht ganz neue SNARKs die vollkommen ohne ein Trusted Setup funktionieren. Da dieser Ansatz aber noch mehr komplexe Kryptographie beinhaltet und wirklich neu ist (Stand Juni 2019), ist es schwer eine Aussage zu treffen, ob er wirklich wasserdicht ist. Das Potential für vollkommen vertrauensfreie SNARKs ist aber da.

Desweitern gibt es gute Entwicklungen im Bereich von Kryptoprimitiven, die die Praktikabilität von SNARKs deutlich verbessern. Beispielsweise Hashfunktionen, wie MiMCs die auch im zweiten Teil im Beispiel verwendet werden. MiMCs sind 10 mal kleiner in einem Circuit als sha-256. Oder die noch neuere Friday Funktion die nochmal 2-3 mal kleiner als MiMCs sind.

Das war nur ein Auszug an Beispielen, die die Praktikabilität von SNARKs deutlich erhöhen. Es bleibt zu erwarten, dass die Innovationskurve hier noch eine ganze Weile steil bleibt. Dranbleiben lohnt sich also.

---

Leseecke:

• Artikelserie von Vitalik Buterin: Teil 1, Teil 2, Teil 3
• https://ethresear.ch/t/zero-knowledge-proofs-starter-pack/4519
• https://zkp.science/

Über den Autor