Zero-Knowledge-Proofs: Eine Einführung in die Grundlagen

Einführung

Zero-Knowledge-Proofs gehören zu den leistungsfähigsten Werkzeugen, die Kryptografen entwickelt haben. Leider versteht sie die breite Öffentlichkeit kaum. Dieser Artikel soll das ändern und bietet einen umfassenden Überblick über Zero-Knowledge-Proofs, ausgehend von ihren grundlegenden Prinzipien. Wir behandeln die Theorie, Mathematik und Kryptografie hinter Zero-Knowledge-Proofs, damit jeder die neuesten Entwicklungen auf Solana verstehen kann, insbesondere ZK Compression und die Zukunft der Interoperabilität.

Dieser Artikel setzt Kenntnisse über das Programmiermodell von Solana und die kryptografischen Primitive von Blockchain-Systemen voraus, darunter Hashfunktionen, Hashzeiger, Merkle-Bäume und nebenläufige Merkle-Bäume. Wenn diese Konzepte neu für dich sind, lies zuerst diese früheren Blogartikel:

• Kryptografische Werkzeuge 101 – Hashfunktionen und Merkle-Bäume erklärt
• Das Programmiermodell von Solana: Eine Einführung in die Entwicklung auf Solana

Dieser Artikel ist modular aufgebaut. Wenn diese Themen neu für dich sind, solltest du alle Abschnitte und Unterabschnitte der Reihe nach lesen. Wenn du mit bestimmten Themen bereits vertraut bist oder gezielt etwas lernen möchtest, kannst du aber problemlos direkt in einen bestimmten Abschnitt einsteigen.

Dies ist außerdem der erste Artikel einer zweiteiligen Reihe über Zero-Knowledge-Proofs. Wir empfehlen dringend, zuerst diesen Artikel zu lesen, bevor du mit Zero-Knowledge-Proofs: Ihre Anwendungen auf Solana fortfährst.

Die Theorie hinter Zero-Knowledge-Proofs

1989 veröffentlichten die MIT-Forscher Shafi Goldwasser, Silvio Micali, der Gründer von Algorand, und Charles Rackoff The Knowledge Complexity of Interactive Proof Systems. Sie arbeiteten an Systemen, in denen eine Partei, der Prover, Nachrichten mit einer zweiten Partei, dem Verifier, austauscht, um sie von der Wahrheit einer mathematischen Aussage zu überzeugen. Sie stellten als Erste die Frage: „Was, wenn Prover und Verifier einander nicht vertrauen?“ Entscheidend ist dabei, wie viele Informationen der Verifier während dieses Nachrichtenaustauschs zusätzlich zur Tatsache erhält, dass die Aussage wahr ist. Der Prover könnte den Verifier beispielsweise davon überzeugen wollen, dass er die Lösung eines komplexen Rätsels kennt, ohne die Lösung selbst offenzulegen.

Welche Art von Problemen wollen wir überhaupt lösen?

Dreifärbung von Graphen

Die Dreifärbung von Graphen ist ein klassisches Problem der Informatik und Graphentheorie. Dabei werden die Knoten eines Graphen mit drei Farben so eingefärbt, dass keine benachbarten Knoten dieselbe Farbe haben. Bei einem Graphen mit drei Knoten ist das einfach. Mit zunehmender Anzahl von Knoten wird es jedoch immer schwieriger.

Ein praktischer Anwendungsfall dafür ist die Stundenplanung an Universitäten. An einer großen Universität müssen Stundenpläne so erstellt werden, dass sich die Lehrveranstaltungen eines Studenten nicht überschneiden. Jede Lehrveranstaltung lässt sich als Knoten in einem Graphen darstellen. Kanten stehen für Studenten, die beide Lehrveranstaltungen besuchen. So wird sichergestellt, dass zwei Lehrveranstaltungen mit gemeinsamen Studenten nicht gleichzeitig stattfinden. Weitere Einschränkungen betreffen Raumkapazitäten, bevorzugte Zeiten der Professoren und eine gleichmäßige Verteilung der Lehrveranstaltungen über die Woche. Lehrveranstaltungen müssen also Zeitfenster und Räume so zugewiesen werden, dass zwei benachbarte Lehrveranstaltungen nie dasselbe Zeitfenster belegen. Dafür lässt sich die Dreifärbung von Graphen nutzen.

Stell dir nun vor, der endgültige Stundenplan müsse von einer externen Wirtschaftsprüfungsgesellschaft geprüft werden. Aufgrund bestimmter Datenschutzvorschriften darf die Universität keine detaillierten Informationen zur Kursbelegung an die Prüfer weitergeben. Stattdessen muss sie nachweisen, dass der endgültige Stundenplan alle erforderlichen Bedingungen erfüllt, ohne offenzulegen, welche Studenten welche Lehrveranstaltungen besuchen. 

Dazu muss die Universität einen Graphen erstellen, in dem jeder Knoten eine Lehrveranstaltung darstellt. Zwischen zwei Knoten wird eine Kante gezogen, wenn die entsprechenden Lehrveranstaltungen mindestens einen gemeinsamen Studenten haben. Die Universität weist jeder Lehrveranstaltung ein Zeitfenster zu, sodass zwei benachbarte Lehrveranstaltungen nie gleichzeitig stattfinden. Anschließend würde sich die Universität mithilfe eines kryptografischen Commitment-Verfahrens auf ihren fertigen Stundenplan festlegen. Dabei erstellt sie einen kryptografischen Hash für das zugewiesene Zeitfenster jeder Lehrveranstaltung und gibt die Hashes an den Verifier weiter, ohne die Zeitfenster offenzulegen. Die externe Wirtschaftsprüfungsgesellschaft wählt dann zufällig Paare benachbarter Lehrveranstaltungen aus, um die zugewiesenen Zeitfenster zu prüfen. Die Universität legt die festgeschriebenen Zeitfenster des ausgewählten Paars benachbarter Lehrveranstaltungen offen und stellt die ursprünglichen Commitments, also die Hashes, bereit. So kann die externe Wirtschaftsprüfungsgesellschaft die offengelegten Werte prüfen. Die letzten Schritte aus Anfechtung, Offenlegung und Prüfung werden wiederholt, bis die externe Wirtschaftsprüfungsgesellschaft überzeugt ist, dass sich keine Lehrveranstaltungen überschneiden. Ich empfehle die interaktive Zero-Knowledge-Demonstration zur Dreifärbbarkeit des MIT, um diese Schritte in Echtzeit zu verfolgen.

Die Universität möchte der externen Wirtschaftsprüfungsgesellschaft beweisen, dass sie einen korrekten Stundenplan kennt. Das heißt, sie möchte einer anderen Partei beweisen, dass sie etwas weiß. Das Praktische an diesem Problem ist, dass es NP-vollständig ist.

NP-Vollständigkeit

In der Komplexitätstheorie ist ein Problem NP-vollständig, wenn:

• die Ausgabe für jede Eingabe des Problems entweder „Ja“ oder „Nein“ lautet
• sich eine „Ja“-Antwort mit einer kurzen Lösung belegen lässt
• sich die Korrektheit jeder Lösung schnell prüfen lässt und ein Brute-Force-Algorithmus durch Ausprobieren aller möglichen Lösungen eine Lösung finden kann

NP-vollständige Probleme sind wichtig, weil sie die schwierigsten Probleme innerhalb der Klasse NP darstellen. Es handelt sich also um eine Gruppe sehr schwieriger Rätsel, bei denen sich eine vermutete Lösung in Polynomialzeit leicht prüfen lässt, die Lösung selbst aber schwer zu finden ist. Diese Probleme zeichnen sich durch ihre universelle Simulierbarkeit aus. Wenn wir ein NP-vollständiges Problem schnell lösen können, können wir jedes NP-Problem auf ein NP-vollständiges Problem reduzieren oder in eines umwandeln und seine Lösung in Polynomialzeit finden. Auch Lösungen NP-vollständiger Probleme lassen sich leicht prüfen. 

Damit haben wir eine ganze Klasse von Problemen, deren Lösungen wir mit Zero-Knowledge-Proofs effizient beweisen können. Beispiele dafür sind:

• Problem des Handlungsreisenden – Finde für eine Liste von Städten und den Entfernungen zwischen allen Paaren die kürzeste Route, die jede Stadt genau einmal besucht und zum Ausgangspunkt zurückkehrt. Dieses Problem hat zahlreiche Anwendungen in Logistik, Routenplanung, Fertigung und Lieferkettenmanagement
• Rucksackproblem – Bestimme für eine Menge von Gegenständen, wie viele Exemplare jedes Gegenstands in eine Auswahl aufgenommen werden sollen, sodass das Gesamtgewicht höchstens einem vorgegebenen Grenzwert entspricht und der Gesamtwert möglichst groß ist. Dieses Problem tritt häufig im Finanzwesen und bei der Ressourcenverteilung auf
• Aufgabenplanung – Plane eine Menge von Aufgaben mit bestimmten Laufzeiten und Fristen auf einer einzelnen Maschine so, dass die Gesamtstrafe für verspätete Aufgaben minimiert wird. Das hat zahlreiche Anwendungen in Informatik, Fertigung und Projektmanagement

Darüber hinaus besagt das Cook-Levin-Theorem, dass das boolesche Erfüllbarkeitsproblem NP-vollständig ist. Jedes Problem, dessen Variablen sich so durch Wahrheitswerte ersetzen lassen, dass das Ergebnis am Ende wahr ist, kann also in ein NP-vollständiges Problem umgewandelt werden. Daraus folgt, dass sich jedes Problem, das wir auf eine Reihe von Wahr-oder-falsch-Fragen reduzieren können, effizient mit Zero-Knowledge-Proofs beweisen lässt.

Eigenschaften eines Zero-Knowledge-Proofs

Aufgrund der Komplexität und Bedeutung NP-vollständiger Probleme ist es entscheidend, Lösungen für diese Problemklasse effizient und sicher beweisen zu können. Zero-Knowledge-Proofs ermöglichen das, ohne den Schutz der beteiligten Informationen zu beeinträchtigen. Goldwasser, Micali und Rackoff schlugen vor, dass alle Zero-Knowledge-Proofs die folgenden Eigenschaften erfüllen müssen:

• Vollständigkeit – Ein ehrlicher Prover wird den Verifier schließlich überzeugen
• Korrektheit – Ein betrügerischer Prover kann einen Verifier niemals von einer falschen Aussage überzeugen
• Zero-Knowledge-Eigenschaft – Die Interaktion zwischen Prover und Verifier verrät nur, ob eine Aussage wahr ist, und sonst nichts

Mit den robusten Eigenschaften von Zero-Knowledge-Proofs können wir Tatsachen oder die Kenntnis bestimmter Informationen in vielen Kontexten nachweisen. Dabei schützen wir die Privatsphäre und gewährleisten präzise Korrektheit. In späteren Abschnitten untersuchen wir, warum das für Anwendungen mit hohen Sicherheits- und Effizienzanforderungen wie Blockchains so wertvoll ist.

Interaktiv oder nicht interaktiv

Zero-Knowledge-Proofs folgen meist derselben dreistufigen Struktur:

• Der Prover erzeugt eine Lösung für die Berechnung, den sogenannten Witness, und sendet anschließend ein Commitment zur Antwort des Witness
• Der Verifier antwortet mit einem zufällig erzeugten Challenge-Wert
• Der Prover berechnet den endgültigen Proof anhand des Commitments und der Challenge

Diese Struktur ist von Natur aus interaktiv: Der Prover behauptet, etwas zu wissen, und der Verifier fordert ihn fortlaufend heraus, bis die Wahrscheinlichkeit einer Täuschung vernachlässigbar ist. Für die meisten Anwendungen ist das nicht ideal, da der Prover eine oder mehrere Antworten benötigt, bevor er den vollständigen Proof erzeugen kann. Dieser Aufbau bringt die folgenden Herausforderungen mit sich:

• Der Verifier könnte mit dem Prover zusammenarbeiten und ihm ermöglichen, Proofs zu fälschen
• Der Verifier könnte gefälschte Proofs erstellen
• Der Verifier muss seine geheimen Werte irgendwo speichern, wodurch sie anfällig für Leaks oder Angriffe sein könnten

Die Fiat-Shamir-Heuristik ist eine Methode, mit der aus einem interaktiven Wissensbeweis eine darauf basierende digitale Signatur erstellt wird. So lässt sich eine Tatsache öffentlich beweisen, ohne die zugrunde liegenden Informationen offenzulegen. Statt dass der Verifier dem Prover einen zufälligen Challenge-Wert sendet, kann der Prover diese digitale Signatur mithilfe einer Zufallsfunktion wie einer guten kryptografischen Hashfunktion selbst berechnen. Anstatt den Verifier also an 500 verschiedenen Stellen in die Berechnung schauen zu lassen, berechnet der Prover eine Merkle-Root der Berechnung, wählt anhand der Merkle-Root 500 Indizes pseudozufällig aus und stellt die 500 entsprechenden Merkle-Zweige der Daten bereit. Entscheidend ist, dass der Prover erst nach dem Commitment der Daten weiß, welche Zweige er offenlegen muss.

Aufmerksame Leser erkennen möglicherweise einen gravierenden Fehler bei der stichprobenartigen Prüfung von Berechnungen: Berechnungen sind von Natur aus fragil. Ein böswilliger Prover könnte mitten in der Berechnung ein einziges Bit umdrehen, ohne dass der Verifier es je bemerkt. Wie kann ein Verifier jedes einzelne Element der Berechnung prüfen, ohne alle Elemente einzeln anzusehen? Polynome.

Bevor wir über Polynome sprechen können, müssen wir jedoch einige mathematische Grundlagen verstehen.

Die Mathematik hinter Zero-Knowledge-Proofs

Dies soll keine ausführliche Einführung in die folgenden mathematischen Gebiete sein. Jeder dieser Abschnitte könnte einen eigenen Artikel füllen. Stattdessen erhältst du eine kurze Einführung, damit du die mathematischen Grundlagen hinter Zero-Knowledge-Proofs und ihre Funktionsweise auf hoher Ebene verstehen kannst.

Dieser Artikel führt dich außerdem in die korrekte mathematische Notation ein. Im folgenden Unterabschnitt zur Mengenlehre stellen wir beispielsweise die Symbole ∈, ∉ und ⊆ vor. Letztlich sind diese Symbole nur Platzhalter für etwas anderes. Zero-Knowledge-Proofs sind kein Anfängerthema. Daher sind die meisten Artikel darüber nicht einsteigerfreundlich. Sie erklären nicht, was diese Symbole bedeuten, und setzen voraus, dass Leser diese Notation verstehen. Wenn wir die Notation jetzt einführen, wirkt sie für alle weniger abschreckend, die tiefer in Zero-Knowledge-Proofs einsteigen möchten. Verliere dich nicht in der Notation. Bleib dran: Irgendwann siehst du in diesen Symbolen die zugrunde liegenden Konzepte statt irgendwelcher griechischer Buchstaben.

Mengenlehre

Die Mengenlehre ist ein Teilgebiet der Mathematik, das Sammlungen von Objekten untersucht. Eine Menge ist eine Sammlung unterschiedlicher Objekte. Diese unterschiedlichen Objekte werden als Elemente der Menge bezeichnet. Betrachten wir beispielsweise eine Sammlung von Früchten:

In der Mengenschreibweise schließen geschweifte Klammern eine Sammlung von Elementen ein und stellen damit eine Menge dar. So wissen wir, dass Apfel, Orange, Birne und Banane zur Menge gehören, etwas wie „Kartoffel“ jedoch nicht. Das Symbol ∈ kennzeichnet die Zugehörigkeit zu einer Menge und wird als „ist ein Element von“ gelesen. Entsprechend zeigt ∉ an, dass ein Element nicht zu einer bestimmten Menge gehört. Wir können also sagen:

Wir würden das so lesen: „Apfel ist ein Element der Menge Fruit und Kartoffel ist kein Element der Menge Fruit.“

Teilmengen

Mengen können auch aus anderen Mengen bestehen. Eine Teilmenge ist eine Menge, die ausschließlich Elemente einer anderen Menge enthält. Angenommen, wir hätten:

Dann können wir sagen, dass die Menge Citrus eine Teilmenge der größeren Menge AllFruits ist. Ebenso könnten wir mit unserer früheren Menge Fruit sagen, dass Fruit eine Teilmenge der größeren Menge AllFruit ist. In Mengenschreibweise schreiben wir:

Warum ist das wichtig?

Die Mengenlehre ist entscheidend, um Wertebereiche und Bedingungen zu verstehen. In den nächsten Abschnitten über Zahlentheorie und modulare Arithmetik untersuchen wir Zahlen innerhalb eines bestimmten Bereichs. Beispielsweise könnten wir eine Menge möglicher Werte für einen kryptografischen Schlüssel haben:

Hier definiert K den Bereich aller möglichen Schlüssel. Wir können unsere Zero-Knowledge-Proofs so gestalten, dass bestimmte Bedingungen für diese Menge gelten und nur bestimmte Werte gültig sind. Wir könnten beispielsweise festlegen, dass der Schlüssel eine Zahl zwischen 1 und 5 sein muss. 

Die Mengenlehre liefert damit die grundlegende Sprache, Werkzeuge und Notation, um Mengen möglicher Eingaben, Ausgaben und Zustände in kryptografischen Protokollen zu definieren und zu analysieren. Bei Zero-Knowledge-Proofs müssen wir häufig beweisen, dass ein Element zu einer bestimmten Menge oder einem bestimmten Bereich gehört, ohne das Element selbst offenzulegen.

Auf der Khan Academy findest du hervorragende Übungsaufgaben zur grundlegenden Mengenschreibweise.

Zahlentheorie

Die Zahlentheorie ist ein Teilgebiet der Mathematik, das ganze Zahlen und arithmetische Funktionen untersucht. Ganze Zahlen lassen sich als Menge vollständiger Zahlen definieren, die also keine Brüche sind. Dazu gehören positive und negative Zahlen sowie null. Formeller können wir die Menge der ganzen Zahlen so definieren:

Hier bezeichnet ℤ die Menge der ganzen Zahlen. Die Auslassungspunkte zeigen, dass die ganzen Zahlen von negativ unendlich bis positiv unendlich reichen. Beispielsweise ist 12 eine ganze Zahl, ebenso wie -1978649832794275.

Rationale Zahlen

Rationale Zahlen sind Zahlen, die wir als Bruch ganzer Zahlen ausdrücken können, wobei der Nenner, also die Zahl unter dem Bruchstrich beziehungsweise der Divisor, nicht null ist. Beispielsweise sind $(\frac{1}{2}), 74, (\frac{2}{3})$ alles rationale Zahlen. Formeller können wir rationale Zahlen als eine Menge von Zahlen definieren, die sich als Bruch pq ausdrücken lassen, wobei p der Zähler, q der Nenner und q ungleich 0 ist. Das Symbol ℚ bezeichnet die rationalen Zahlen. In Mengenschreibweise schreiben wir:‍

‍Das mag auf den ersten Blick abschreckend wirken, beschreibt aber genau den vorherigen Satz. Diesen seltsam aussehenden mathematischen Ausdruck würden wir so lesen: „Q ist die Menge aller Brüche p durch q, wobei p und q ganze Zahlen sind und q ungleich null ist.“ 

Reelle Zahlen

Reelle Zahlen umfassen sowohl rationale als auch irrationale Zahlen. Irrationale Zahlen lassen sich nicht als einfacher Bruch ausdrücken und haben unendliche, nicht periodische Dezimaldarstellungen. Beispielsweise sind Pi, also π, und $\sqrt{2}$ (also 1.4.1421…) irrationale Zahlen. Die Mengenschreibweise überspringen wir vorerst. Beachte aber, dass reelle Zahlen mit dem Symbol ℝ bezeichnet werden.

Warum ist das wichtig?

Die Zahlentheorie ist eng mit der Mengenlehre verbunden, da sie bestimmte Zahlenmengen wie die rationalen Zahlen untersucht. Diese Mengen dienen häufig als Grundlage für die Definition von Bereichen und Bedingungen in mathematischen und kryptografischen Problemen. 

Wir erkennen außerdem die Verbindung zwischen Zahlentheorie und Mengenlehre. Beispielsweise können wir sagen, dass die Menge aller ganzen Zahlen ℤ eine Teilmenge der rationalen Zahlen ℚ ist. Das zeigt sich in unserer obigen Definition der reellen Zahlen in Mengenschreibweise, wenn wir festlegen, dass Zähler und Nenner ganze Zahlen sind.

Modulare Arithmetik

Die modulare Arithmetik, auch als Uhrzeitarithmetik bezeichnet, ist ein System numerischer Operationen für ganze Zahlen. Dabei beginnen Zahlen nach Erreichen eines bestimmten Werts, des sogenannten Modulus, wieder von vorn. Statt mit einer unendlichen Menge von Zahlen arbeiten wir dabei mit den ersten n positiven Zahlen.

Uhren

Betrachte eine Analoguhr mit den Zahlen 1 bis 12. Ich finde es schrecklich, dass ich heutzutage klarstellen muss, dass sie Zeiger hat und nicht digital ist. Wenn es 11 Uhr wäre und wir die Uhrzeit in zwei Stunden wissen wollten, erhielten wir nicht 13 Uhr. Stattdessen beginnen wir wieder bei 1 Uhr. Das lässt sich als $11 + 2 \equiv 1 \pmod{12}$ ausdrücken. Der korrekte mathematische Ausdruck wäre hier $13 \bmod 12 = 1$. Programmierer kennen wahrscheinlich die Modulo-Operation in der Form $13 \% 12 = 1$.

Modulo-Operation

Wenn wir n mod k schreiben, meinen wir den Rest bei der Division von n durch k. Das wird als Modulo-Operation bezeichnet. Zum Beispiel:

• 25 mod 3 bedeutet, 25 durch 3 zu teilen. Der Rest ist 1, weil $25 = 8 \times 3 + 1$
• 15 mod 4 bedeutet, 15 durch 4 zu teilen. Der Rest ist 3, weil $15 = 3 \times 4 + 3$

In der modularen Arithmetik ist der Rest immer nicht negativ.

Warum ist das wichtig?

Modulare Arithmetik ist entscheidend, weil sie Einblicke in das Verhalten von Zahlen unter bestimmten Bedingungen bietet, was für die Kryptografie wertvoll ist. Sie bildet die Grundlage vieler kryptografischer Algorithmen und wird in der gesamten Informatik, im Ingenieurwesen und in allen Bereichen eingesetzt, die Daten sicher verarbeiten und verschlüsseln müssen.

Betrachte die Berechnung x + y = z. Angenommen, wir arbeiten mit einem endlichen Körper, der durch die Primzahl p = 17 definiert ist. Darauf gehen wir gleich näher ein. Stell ihn dir vorerst als die Menge aller ganzen Zahlen von 0 bis 16 vor, die bei 17 wieder von vorn beginnt. Die Berechnung in diesem Körper lautet dann (x + y) mod p = z. Wenn x = 12 und y = 15 ist, ergibt sich:‍

Durch die modulare Arithmetik können wir Berechnungen innerhalb eines überschaubaren Wertebereichs durchführen, der durch die Primzahl p definiert wird. Das ist besonders wichtig, weil Computer und Prozessoren nur begrenzten Speicherplatz haben. Deshalb arbeiten wir normalerweise mit Ganzzahlen fester Größe wie u32 oder u64. Modulare Arithmetik stellt sicher, dass unsere Werte innerhalb dieser Grenzen bleiben. Primzahlen sorgen zusätzlich für mehr Komplexität. Aus kryptografischer Sicht ist das entscheidend, weil es die Sicherheit erhöht und bestimmte mathematische Eigenschaften vorhersehbarer und zuverlässiger macht.

In zk-SNARKs wird modulare Arithmetik beispielsweise eingesetzt, damit berechnete Werte innerhalb bestimmter überschaubarer Grenzen bleiben. Außerdem lassen sich damit arithmetische Schaltkreise über einer bestimmten Zahlenmenge erstellen. So können wir Berechnungen ausdrücken und zugleich ihre effiziente Prüfung sicherstellen. Der Prover müsste hier beweisen, dass er diese Berechnung durchgeführt hat, ohne die Werte von x, y und z offenzulegen.

Für mehr praktische Erfahrung beim Lösen von Aufgaben zur modularen Arithmetik empfehle ich die Aufgabensammlung von Art of Problem Solving und Joseph Zollers Übungen zur modularen Arithmetik. 

Gruppentheorie

Die Gruppentheorie ist ein Teilgebiet der Mathematik, das algebraische Strukturen untersucht, die als Gruppen bezeichnet werden. Eine Gruppe ist eine Menge von Elementen mit einer Operation, die die folgenden sogenannten Gruppenaxiome erfüllt:

• Abgeschlossenheit – Das Ergebnis jeder arithmetischen Berechnung ist ein weiteres Element der Menge
• Assoziativität – Wenn dieselbe Operation auf drei oder mehr Elemente angewendet wird, spielt die Gruppierung der Elemente keine Rolle. Das Ergebnis bleibt gleich
• Neutrales Element – Es gibt ein Element, mit dem eine Operation zusammen mit jedem anderen Element durchgeführt werden kann, ohne dessen Wert zu verändern
• Inverses Element – Zu jedem Element gibt es ein Element, mit dem eine Operation durchgeführt werden kann, sodass das neutrale Element entsteht

Formal sind sie folgendermaßen definiert:

• Abgeschlossenheit – Wenn a und b Elemente der Gruppe sind, ist auch das Ergebnis der Operation, häufig als $a \times b$, $ab$, $a \circ b$, oder $ab$ bezeichnet, ein Element der Gruppe. Formal schreiben wir $\forall a, b \in G \mid a \circ b \in G$. Das können wir so lesen: „Für alle Werte der Elemente a und b in der Menge G liegt das Ergebnis der Operation zwischen a und b in G“
• Assoziativität – Wenn a, b und c Elemente der Gruppe sind, gilt (ab)c = a(cb). Formal schreiben wir $\forall a, b, c \in G \mid (a \circ b) \circ c = a \circ (b \circ c)$. Das können wir so lesen: „Für alle Werte der Elemente a, b und c in der Menge G ist die Operation von a und b, gefolgt von c, gleich der Operation von a, gefolgt von der Operation von b und c“
• Neutrales Element – Es existiert ein Element e in der Gruppe, sodass für jedes Element a der Gruppe die Operation $e \circ a = a \circ e = a$ gilt. Formal schreiben wir $\exists e \in G \mid \forall a \in G \mid e \circ a = a \circ e = a$. Das können wir so lesen: „Es existiert ein Element e in der Menge G, sodass für jedes Element a in der Menge G die Operation von e gefolgt von a gleich der Operation von a gefolgt von e ist, was wiederum gleich a ist“
• Inverses Element – Für jedes Element a der Gruppe existiert ein Element b in der Gruppe, sodass $a \circ b = b \circ a = e$ gilt, wobei e das neutrale Element ist. Formal schreiben wir $\forall a \in G \mid \exists b \in G \mid a \circ b = b \circ a = e$. Das können wir so lesen: „Für alle Werte der Elemente a in der Menge G existiert ein Element b in der Menge G, sodass die Operation von a gefolgt von b gleich der Operation von b gefolgt von a ist, was wiederum gleich dem neutralen Element ist“

Mit einem Beispiel können wir diesen mathematischen Fachjargon verständlicher machen. Betrachte die Menge der ganzen Zahlen mit der Addition. Diese Menge bildet eine Gruppe, weil sie alle vier Gruppenaxiome erfüllt:

• Abgeschlossenheit – Addierst du zwei ganze Zahlen, erhältst du eine weitere ganze Zahl
• Assoziativität – $(5 + 4) + 3 = 5 + (4 + 3)$
• Neutrales Element – Die Zahl null ist das neutrale Element, weil sich der Wert einer ganzen Zahl durch Addition von null nicht ändert. Zum Beispiel $7 + 0 = 0 + 7 = 7$
• Inverses Element – Das Inverse jeder ganzen Zahl ist ihr negatives Gegenstück, weil ihre Summe das neutrale Element ergibt. Zum Beispiel $5 + (-5) = 0$. Allgemein gilt $n + (-n) = 0$

Wir können das auch auf ein schwierigeres Beispiel ausweiten: die Menge der von null verschiedenen rationalen Zahlen $\mathbb{Q} = \left\{ \frac{a}{b} \mid a, b \in \mathbb{Z}, b \ne 0 \right\}$ mit der Multiplikation. Auch sie bildet eine Gruppe:

• Abgeschlossenheit – Die Multiplikation zweier von null verschiedener rationaler Zahlen ergibt eine von null verschiedene rationale Zahl
• Assoziativität – $ab \times cd \times ef = ab \times (cd \times ef)$
• Neutrales Element – Die Zahl 1 ist das neutrale Element, weil die Multiplikation einer von null verschiedenen rationalen Zahl mit eins ihren Wert nicht verändert. Zum Beispiel $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Inverses Element – Das Inverse jeder von null verschiedenen rationalen Zahl ist ihr Kehrwert, bei dem Zähler und Nenner vertauscht werden, weil das Ergebnis 1 und damit das neutrale Element ist. Zum Beispiel $\frac{3}{5} \times \frac{5}{3} = 1$

Untergruppen

Eine Untergruppe ist eine Gruppe innerhalb einer Gruppe. Wenn die Untergruppe H der Gruppe G eine Teilmenge von G sein soll, muss sie die folgenden Gruppenaxiome erfüllen:

• Abgeschlossenheit – Wenn a und b in H liegen, muss auch das Ergebnis der Operation zwischen beiden in H liegen
• Assoziativität – Dieses Axiom wird von der größeren Gruppe G übernommen 
• Neutrales Element – Das neutrale Element von G muss auch in H liegen 
• Inverses Element – Für jedes Element a in H muss es ein Element b ebenfalls in H geben, sodass ab und ba beide dem neutralen Element entsprechen

Das klassische Beispiel ist die Menge der geraden ganzen Zahlen mit der Addition als Untergruppe der Menge der ganzen Zahlen mit der Addition:

• Abgeschlossenheit – Die Addition zweier gerader ganzer Zahlen ergibt eine weitere gerade ganze Zahl
• Assoziativität – Dieses Axiom wird von den ganzen Zahlen übernommen. Zum Beispiel $2 + (4 + 6) = (2 + 4) + 6$
• Neutrales Element – Die Zahl null ist das neutrale Element, weil sich der Wert einer geraden ganzen Zahl durch Addition von null nicht ändert. Null gehört außerdem zur Menge der ganzen Zahlen
• Inverses Element – Das Inverse jeder geraden Zahl ist ebenfalls eine gerade Zahl. Das Inverse von 4 ist beispielsweise -4, weil $4 + (-4) = 0$ gilt und null das neutrale Element ist

Wir können das auf ein schwierigeres Beispiel anwenden. Betrachte die Menge aller von null verschiedenen rationalen Zahlen, also ℚ*, mit der Multiplikation. Wir können beweisen, dass ℚ* eine Untergruppe der Menge der von null verschiedenen reellen Zahlen, also ℝ*, mit der Multiplikation ist:

• Abgeschlossenheit – Wenn a und b von null verschiedene rationale Zahlen sind, ist ihr Produkt ab ebenfalls eine von null verschiedene Zahl. Zum Beispiel ist $\frac{1}{2} \times \frac{3}{4} = \frac{3}{8}$ eine von null verschiedene rationale Zahl
• Assoziativität – Die Multiplikation rationaler Zahlen ist assoziativ. Zum Beispiel $(\frac{1}{2} \times \frac{3}{4}) \times \frac{5}{6} = \frac{1}{2} \times (\frac{3}{4} \times \frac{5}{6})$
• Neutrales Element – Die Zahl 1 ist das neutrale Element, weil die Multiplikation einer von null verschiedenen rationalen Zahl mit 1 ihren Wert nicht verändert. Zum Beispiel $\frac{1}{2} \times 1 = 1 \times \frac{1}{2} = \frac{1}{2}$
• Inverses Element – Jede von null verschiedene rationale Zahl $a = \frac{p}{q}$ besitzt ein multiplikatives Inverses $a^{-1} = \frac{q}{p}$, das ebenfalls eine von null verschiedene rationale Zahl ist und bei der Multiplikation das neutrale Element ergibt. Sei beispielsweise a = $\frac{2}{3}$. Das Inverse ist $\frac{3}{2}$, weil $\frac{2}{3} \times \frac{3}{2} = 1$ gilt

Da ℚ* alle Gruppenaxiome erfüllt, bildet es eine Gruppe. Da ℚ* außerdem eine Teilmenge von ℝ* ist und dessen Eigenschaften übernimmt, können wir feststellen, dass ℚ* eine Untergruppe von ℝ* ist.

Warum ist das wichtig?

Gruppen bilden die Grundlage verschiedener mathematischer und kryptografischer Konzepte und Strukturen. Kryptosysteme wie RSA und die Kryptografie mit elliptischen Kurven stützen sich stark auf die Eigenschaften von Gruppen und ihren Operationen. Untergruppen helfen dabei, die Struktur größerer Gruppen anhand ihrer kleineren, überschaubareren Teilmengen zu verstehen. Gruppen liefern ein grundlegendes Modell für Symmetrien, Operationen und Transformationen. Das ist entscheidend für den nächsten Abschnitt über Körper.

Körper

Ein Körper ist eine Menge von Elementen, die die Körperaxiome für Addition und Multiplikation erfüllt und eine kommutative Divisionsalgebra bildet. Das bedeutet, dass eine Division außer durch null immer möglich ist. Die Körperaxiome werden üblicherweise als additive und multiplikative Paare dargestellt:

• Addition
  • Assoziativität: $(a + b) + c = a + (b + c)$
  • Kommutativität: $a + b = b + a$
  • Distributivität: $a(b + c) = ab + ac$
  • Neutrales Element: $a + 0 = 0 + a = a$
  • Inverses Element: $a + (-a) = 0$
• Multiplikation
  • Assoziativität: $(ab)c = a(bc)$
  • Kommutativität: $ab = ba$
  • Distributivität: $(a + b)c = ac + bc$
  • Neutrales Element: $(a + b)c = ac + bc$
  • Inverses Element: $a \times a^{-1} = a^{-1} \times a = 1, \text{ if } a \ne 0$

Endliche Körper und Generatoren

Ein endlicher Körper ist ein Körper mit einer begrenzten Menge von Elementen. Endliche Körper werden auch als Galois-Körper bezeichnet. Die Anzahl der Elemente heißt Ordnung oder Mächtigkeit des Körpers. Sie ist immer eine Primzahlpotenz. Das Praktische an endlichen Körpern ist, dass jede arithmetische Operation mit Elementen des Körpers wieder ein Element im Körper ergibt. Der Grund dafür ist, dass alle Operationen modulo der Ordnung des Körpers ausgeführt werden und Werte dadurch wieder von vorn beginnen.

Jeder endliche Körper hat einen Generator. Ein Generator kann durch Potenzierung alle Elemente des Körpers erzeugen. Wir können also den Generator nehmen und seinen Exponenten jeweils um eins erhöhen, bis wir alle Elemente des Körpers erhalten haben. Ein Generator ist somit ein Element des Körpers, das durch seine Potenzen jedes von null verschiedene Element des Körpers erzeugen kann.

Nehmen wir beispielsweise die Menge der ganzen Zahlen modulo p = 7 und den Körper $\mathbb{Z}_7 = \{0, 1, 2, 3, 4, 5, 6\}$. Wenn wir den Generator g von $\mathbb{Z}_7^*$ finden wollen, also der multiplikativen Gruppe der von null verschiedenen Elemente von $\mathbb{Z}_7$, müssen wir sicherstellen, dass g1, g2, g3 und so weiter alle von null verschiedenen Elemente des Körpers erzeugen können.

Prüfen wir, ob 3 ein Generator ist:

Die Potenzen von 3 erzeugen alle von null verschiedenen Elemente von $\mathbb{Z}_7$. Daher ist 3 ein Generator der multiplikativen Gruppe $\mathbb{Z}_7^*$.

Warum ist das wichtig?

Kryptografie ist eine Wissenschaft, die sich mit endlichen Mengen befasst. Dieses grundlegende Verständnis ist entscheidend für Themen wie das Problem des diskreten Logarithmus, Verschlüsselung, den Diffie-Hellman-Schlüsselaustausch und elliptische Kurven. Generatoren ermöglichen arithmetische Operationen auf verschlüsselten Polynomen, ohne diese zu entschlüsseln, also homomorphe Verschlüsselung. Das heißt: Wir können verschlüsselte Daten verarbeiten und dabei die zugrunde liegenden Werte vertraulich halten. Dieser Abschnitt ist entscheidend, um den Zero-Knowledge-Aspekt von Zero-Knowledge-Proofs zu verstehen.

Ich empfehle Bill’s Security Site mit einem interaktiven Beispiel zur Erzeugung endlicher Körper mit bestimmten Parametern sowie der zugrunde liegenden Theorie in Python. 

Funktionen

Eine Funktion ist ein Ausdruck, eine Regel oder ein Gesetz, das eine Beziehung zwischen zwei Variablen definiert: der unabhängigen und der abhängigen Variablen. Diese beiden Variablen werden oft als Ursache beziehungsweise Wirkung beschrieben. Die Beziehung wird häufig als y = f(x) notiert und „f von x“ gelesen. Für jeden Wert von x gibt es genau einen Wert von y. Das bedeutet, dass f(x) für dasselbe x nicht mehr als einen Wert haben kann.

Funktionen können entweder 1-zu-1 oder n-zu-1 sein, was häufig als Kardinalität bezeichnet wird. Das bedeutet, dass ein x-Wert genau einem y-Wert zugeordnet werden kann oder mehrere x-Werte demselben y-Wert zugeordnet werden können

Stell dir eine Gerade vor, die durch $y = 3x + 4$ definiert wird. Das ist eine lineare Funktion, bei der das Einsetzen eines Werts für x einen entsprechenden Wert für y ergibt. Zusammen bilden diese beiden Werte einen Punkt auf der Geraden. Wir können die Gleichung beispielsweise als $f(x) = 3x + 4$ umschreiben und für x = 1 auswerten. Das ergibt $f(1) = 7$. Funktionen können auch mehrere Variablen haben. Betrachte beispielsweise die Formel für den Flächeninhalt eines Dreiecks: $A = \frac{bh}{2}$. Hier ist A, also der Flächeninhalt, als Funktion von b, der Grundseite, und h, der Höhe, definiert.

Definitions- und Wertebereich

Der Definitionsbereich einer Funktion ist die Menge aller möglichen Eingabewerte, also der unabhängigen Variablen, die die Funktion akzeptieren kann. Der Wertebereich ist die Menge aller möglichen Ausgabewerte, also der abhängigen Variablen, die die Funktion erzeugen kann.

Für die Funktion $y = 2x + 2$ gilt:

• Der Definitionsbereich umfasst alle reellen Zahlen, weil jede Zahl von negativ unendlich bis positiv unendlich funktioniert. Zum Beispiel:
  • Wenn x = 2.5 ist, dann gilt $y = 2(2.5) + 2 = 7$ 
  • Wenn x = -9234525 ist, dann gilt $y = 2(-9234525) + 2 = -18469048$
• Der Wertebereich umfasst ebenfalls alle reellen Zahlen, weil sich jede Zahl von negativ unendlich bis positiv unendlich erzeugen lässt. Zum Beispiel:
  • Um y = -50 zu erhalten, lösen wir -50 = 2x + 2. Daraus folgt x = -26. 
  • Um y = 0 zu erhalten, lösen wir 0 = 2x + 2. Daraus folgt x = 0

Warum ist das wichtig?

Funktionen sind entscheidend, um Polynome zu verstehen. Polynome sind spezielle Funktionen mit Variablen, die in verschiedenen Potenzen auftreten, und den zugehörigen Koeffizienten. Sie sind grundlegende algebraische Strukturen und bilden die Basis für kryptografische Protokolle. Im nächsten Abschnitt untersuchen wir Polynome genauer und betrachten ihre Eigenschaften und Bedeutung für Zero-Knowledge-Proofs.

Für ein besseres Verständnis von Funktionen empfehle ich Paul’s Online Notes und die dortigen Übungsaufgaben.

Polynome

Ein Polynom ist eine Funktion aus mehreren Variablen und Koeffizienten, die ausschließlich Addition, Subtraktion, Multiplikation und die Potenzierung von Variablen mit nicht negativen ganzzahligen Exponenten verwendet. Polynome werden üblicherweise in dieser Form geschrieben:‍

Dabei sind $a_n x^n + a_{n-1} x^{n-1} + \ldots + a_1 x + a_0$ Koeffizienten und x ist die Variable. Die höchste Potenz der Variablen x mit einem von null verschiedenen Koeffizienten heißt Grad des Polynoms.

Polynome lassen sich als univariat, also mit einer einzelnen Variablen wie in der obigen Form, oder als multivariat, also mit mehreren Variablen, klassifizieren, zum Beispiel $P(x, y) = a_nx^ny^n + a_{n-1}x^{n-1}y^{n-1} + \cdots + a_1xy + a_0$. Sum-Check ist ein Beispiel für ein Protokoll, das multivariate Polynome verwendet. Meist benötigen Zero-Knowledge-Proofs jedoch nur eine einzelne Variable.

Polynome werden anhand ihres Grads üblicherweise so bezeichnet:

• Grad 0 – Konstantes Polynom ungleich null (z. B. $P(x) = 6$)
• Grad 1 – Linear (z. B. $P(x) = 2x - 7$)
• Grad 2 – Quadratisch (z. B. $P(x) = 8x^2 - 3x + 1$)
• Grad 3 – Kubisch (z. B. $P(x) = 3x^3 - 4x$)

Wenn wir zwei verschiedene Polynome mit einem Grad von höchstens $d$ haben, können sie sich an höchstens $d$ Punkten schneiden. Setzen wir beispielsweise eine lineare Funktion mit einer kubischen Funktion gleich, können sie sich bis zu dreimal schneiden. Diese Eigenschaft ergibt sich daraus, wie wir gemeinsame Punkte bestimmen. Um herauszufinden, wo sich zwei Polynome schneiden, setzen wir sie gleich. Im folgenden Unterabschnitt üben wir, die Nullstellen eines Polynoms zu bestimmen. Dabei suchen wir die Punkte, an denen ein bestimmtes Polynom die x-Achse schneidet. Der Fundamentalsatz der Algebra besagt, dass ein Polynom vom Grad $d$ höchstens $d$ Lösungen und damit höchstens $d$ gemeinsame Punkte haben kann.

Nullstellen von Polynomen 

Die Nullstellen eines Polynoms sind die Werte von x, für die das Polynom gleich null ist. Anders ausgedrückt: Wenn $P(x)$ ein Polynom ist, dann ist eine Nullstelle $r$ eine Lösung der Gleichung $P(r) = 0$. Um die Nullstellen zu bestimmen, müssen wir Polynome faktorisieren können. Beim Faktorisieren ermitteln wir, welche Faktoren miteinander multipliziert eine bestimmte Größe ergeben. Beispielsweise lässt sich 12 auf mehrere Arten faktorisieren:

Eine gängige Faktorisierungsmethode besteht darin, eine Zahl vollständig in positive Primfaktoren zu zerlegen. Beim Faktorisieren beginnst du am besten immer mit dem größten gemeinsamen Teiler (ggT) aller Terme. Zum Beispiel:

Im obigen Beispiel sind beide Terme, also 6x und 3, durch 3 teilbar. Ihr ggT ist daher 3. Die Faktoren sind somit 3 und $2x + 1$. Wir kehren das Distributivgesetz um: $3 \times 2x$ und $3 \times 1$. Beim Bestimmen der Nullstellen lösen wir nach x auf, wenn $P(x) = 0$ gilt.

Bei Polynomen mit zwei Termen ist die Faktorisierung unkompliziert. Noch einfacher ist sie bei einem gegebenen Graphen, denn die Nullstellen liegen dort, wo das Polynom die x-Achse schneidet. Ab drei oder mehr Graden kann es jedoch komplexer werden. Für eine ausführlichere Erklärung empfehle ich den Artikel Polynome faktorisieren – einfach erklärt. 

Um den restlichen Artikel zu verstehen, musst du nicht jede Feinheit der Faktorisierung verschiedener Polynome kennen. Für unsere Zwecke interessiert uns, wann ein Polynom einem anderen Wert entspricht. Hier geht es darum, wann ein Polynom gleich null ist. Später betrachten wir, wann ein Polynom einem anderen entspricht oder die Differenz zweier Polynome identisch null ist, also alle Koeffizienten null sind. Dazu prüfen wir, ob ein bestimmtes Polynom bestimmte Nullstellen hat.

Das Schwartz-Zippel-Lemma 

Das Schwartz-Zippel-Lemma ist ein probabilistisches Werkzeug, mit dem sich prüfen lässt, ob eine Polynomgleichung immer wahr ist. Dazu wertet es das Polynom an zufälligen Punkten aus und prüft, ob das Ergebnis null ist.

Stell dir eine komplexe Gleichung mit den Variablen $x_1, x_2, \ldots, x_n$ vor. Wenn diese Gleichung ein Polynom und nicht nur eine zufällige Ansammlung von Termen ist, hilft uns das Schwartz_Zippel-Lemma zu prüfen, ob sie für alle möglichen Werte dieser Variablen gilt.

So funktioniert es:

• Sei $P(x_1, x_2, \ldots, x_n)$ ein Polynom mit dem Gesamtgrad d, also der höchsten Summe der Exponenten in einem Term
• Wähle eine endliche Menge S aus dem Körper, ähnlich wie bei der Auswahl einer Zahlenmenge
• Wähle für jede Variable $x_1, x_2, \ldots, x_n$ zufällig Werte aus der Menge S

Das Lemma besagt, dass die Wahrscheinlichkeit, dass P an diesen zufällig gewählten Punkten null ist, höchstens $\frac{d}{S}$ beträgt. Ist das Polynom nicht null, ist es daher äußerst unwahrscheinlich, dass es rein zufällig wie null aussieht. Das ist besonders für Zero-Knowledge-Beweise nützlich, bei denen wir Polynomidentitäten effizient verifizieren müssen.

Lagrange-Interpolation

Die Lagrange-Interpolation ist eine Methode, um ein Polynom zu konstruieren, das durch eine bestimmte Menge von Punkten verläuft. Das Lagrange-Polynom ist das Polynom niedrigsten Grades, das durch jeden gegebenen Punkt verläuft. Für n Punkte lässt sich ein Polynom vom Grad n-1 erstellen, das durch alle Punkte verläuft. Liegen beispielsweise zwei Punkte in einer Ebene, können wir eine Gerade definieren, die durch beide Punkte verläuft. Bei drei Punkten in einer Ebene können wir ein quadratisches Polynom definieren, also $y = ax^2 + bx + c$, das durch alle Punkte verläuft. Und so weiter.

Warum ist das wichtig?

Polynome sind einzelne mathematische Objekte, die eine unbegrenzte Menge an Informationen enthalten können. Betrachte ein Polynom als Liste ganzer Zahlen, dann wird das offensichtlich. Eine einzige Gleichung zwischen Polynomen kann daher eine unbegrenzte Anzahl von Gleichungen zwischen Zahlen darstellen. Wer eine bestimmte Gleichung zwischen Polynomen verifizieren kann, verifiziert implizit alle möglichen Gleichungen gleichzeitig. So schützen wir nicht interaktive Beweise vor böswilligen Beweisführern und vermeiden, eine bestimmte Berechnung nur anhand zufälliger Stichproben prüfen zu müssen. 

Polynome besitzen außerdem mehrere Eigenschaften, die sie für die Erstellung von Beweisen nützlich machen:

• Sind genügend Punkte eines bestimmten Polynoms bekannt, lässt sich das gesamte Polynom rekonstruieren
• Eine kleine Änderung an der Eingabe eines Polynoms kann seine Ausgabe erheblich verändern, sodass sich Fehler leichter erkennen lassen
• Polynome können Fehler in Berechnungen erkennen und korrigieren, ähnlich wie Erasure Coding Daten fehlertolerant macht. Das ist entscheidend für die Funktionsweise von Turbine

Bei Zero-Knowledge-Beweisen geht es darum, bestimmte Berechnungen zu beweisen. Polynome sind dafür unschätzbar, weil wir sie mit gezielten Eigenschaften konstruieren können. Angenommen, du möchtest eine Berechnung oder eine Menge von Datenpunkten beweisen. Am einfachsten codierst du sie in einem Polynom und nutzt dessen Eigenschaften, um einen Beweis zu erstellen:

• Codiere die Daten in einem Polynom $P(x)$, sodass die Auswertung von $P(x)$ an bestimmten Punkten die ursprünglichen Daten oder das Ergebnis einer bestimmten Berechnung ergibt
• Erstelle ein Nebenbedingungspolynom $C(x)$, um sicherzustellen, dass das Polynom die vorgegebenen Kriterien erfüllt, etwa dass alle Werte innerhalb eines Bereichs liegen. Beispielsweise stellt $C(x) = (P(x) - 0)(P(x) - 1)$ sicher, dass $P(x)$ entweder 0 oder 1 ist
• Forme das Problem in den Beweis um, dass $P(x)$ bestimmte Bedingungen für deinen Datensatz oder deine Berechnung erfüllt
• Erstelle ein bekanntes Polynom $H(x)$, das ein Vielfaches von $P(x)$ ist und diese Bedingungen codiert
• Der Beweisführer bindet sich an Werte von $P(x)$ und zugehörigen Polynomen, indem er einen Merkle-Baum der Auswertungen erstellt und den Root-Hash an den Verifizierer sendet
• Der Verifizierer wählt zufällig einige Punkte aus und fordert vom Beweisführer die Werte von $P(x)$ und $C(x)$ an diesen Punkten an
• Der Verifizierer gleicht die bereitgestellten Werte mit dem gebundenen Root-Hash und den erwarteten Beziehungen zwischen den Polynomen ab

Die Größe des Polynoms spielt keine Rolle. Da wir das Polynomial Commitment verwenden, können wir Gleichungen zwischen Polynomen in kurzer Zeit verifizieren. So lassen sich Beweise äußerst kompakt und effizient erstellen. Fehler werden verstärkt, und mit Techniken wie der Fiat-Shamir-Heuristik können diese Beweise nicht interaktiv werden. Dadurch kann sie jeder ohne weitere Interaktion verifizieren. 

Um dein Verständnis zu vertiefen, empfehle ich die folgenden Übungsaufgaben:

• Übungsaufgaben zu Polynomen
• Übungsaufgaben zum Bestimmen der Nullstellen von Polynomen
• Polynome faktorisieren: Sehr schwierige Aufgaben mit Lösungen

Die Khan Academy bietet außerdem eine ausführliche Einheit zu Polynomausdrücken, Gleichungen und Funktionen.

Um Polynomial Commitments besser zu verstehen, müssen wir uns nun mit der Kryptografie hinter Zero-Knowledge-Beweisen befassen.

Die Kryptografie hinter Zero-Knowledge-Beweisen

Sehen wir uns symmetrische und asymmetrische Verschlüsselung an.

Symmetrische Verschlüsselung

Bei der symmetrischen Verschlüsselung wird derselbe Schlüssel verwendet, um Klartext zu verschlüsseln und Geheimtext zu entschlüsseln. Dieser Schlüssel wird häufig als geheimer oder privater Schlüssel bezeichnet, da er bei der Verwendung nur eines Schlüssels geheim bleiben muss. Das bedeutet jedoch auch, dass beide Parteien den geheimen Schlüssel austauschen müssen, bevor sie sicher kommunizieren können. Den geheimen Schlüssel sicher zu verwalten und zu verteilen, kann deshalb schwierig sein. Bei unsachgemäßer Handhabung kann er offengelegt werden. Trotz dieses Nachteils ist symmetrische Verschlüsselung schnell und effizient und benötigt weniger Rechenleistung und Speicher als andere Verschlüsselungsverfahren.

Zu den gängigen symmetrischen Verschlüsselungsalgorithmen gehören:

Advanced Encryption Standard (AES)

Der Advanced Encryption Standard (AES) ist eine Variante der Rijndael-Blockchiffre, die weltweit zur Sicherung von Daten eingesetzt wird. Er unterstützt Schlüssellängen von 128, 192 und 256 Bit.

ChaCha20

ChaCha20 ist eine moderne, effiziente Stromchiffre, die Daniel J. Bernstein entwickelt hat. Sie ist eine Variante der Stromchiffre Salsa20 und nutzt Add-Rotate-XOR-Operationen (ARX). Sie bildet einen 256-Bit-Schlüssel, eine 64-Bit-Nonce und einen 64-Bit-Zähler auf einen 512-Bit-Block des Schlüsselstroms ab. Dadurch kann ein Nutzer jede Position im Schlüsselstrom effizient und in konstanter Zeit ansteuern.

Symmetrische Verschlüsselung ist robust und effizient, erfordert aber eine sichere Methode zum Schlüsselaustausch. Eine solche Methode ist der Diffie-Hellman-Schlüsselaustausch. Damit können zwei Parteien über einen unsicheren Kanal sicher einen geheimen Schlüssel austauschen. Diese Methode basiert jedoch auf Prinzipien der asymmetrischen Verschlüsselung, die wir im nächsten Abschnitt behandeln.

Asymmetrische Verschlüsselung

Asymmetrische Verschlüsselung, auch Public-Key-Verschlüsselung genannt, verwendet ein Paar zusammengehöriger Schlüssel, also einen öffentlichen und einen privaten Schlüssel, um Informationen zu ver- und entschlüsseln. Der öffentliche Schlüssel wird frei geteilt, während der private Schlüssel geheim bleibt. Möchte ein Absender eine Nachricht verschlüsseln, verwendet er den öffentlichen Schlüssel des Empfängers. Nach dem Empfang entschlüsselt der Empfänger die Nachricht mit seinem zugehörigen privaten Schlüssel. Mit dem öffentlichen Schlüssel verschlüsselte Daten lassen sich nur mit dem privaten Schlüssel entschlüsseln. Asymmetrische Verschlüsselung ermöglicht daher eine sichere Kommunikation über unsichere Kanäle, da der Entschlüsselungsschlüssel nie weitergegeben wird.

Asymmetrische Verschlüsselung bietet ein hohes Sicherheitsniveau, weil der private Schlüssel nie geteilt wird. Sie vereinfacht außerdem die Schlüsselverteilung, da der öffentliche Schlüssel frei weitergegeben werden kann, und ermöglicht digitale Signaturen. Allerdings benötigt asymmetrische Verschlüsselung mehr Rechenleistung und ist langsamer als symmetrische Verschlüsselung. Auch die Verwaltung von Schlüsselpaaren kann komplex werden, besonders in Systemen mit vielen Nutzern und wenig intuitiven Schlüsselpaaren. 

Zu den gängigen asymmetrischen Verschlüsselungsalgorithmen gehören:

• Rivest-Shamir-Adleman (RSA) — eines der ältesten und am weitesten verbreiteten Public-Key-Kryptosysteme für die sichere Datenübertragung. Es wurde in den 1970er-Jahren entwickelt und basiert auf der praktischen Schwierigkeit, das Produkt zweier großer Primzahlen zu faktorisieren
• Elliptische-Kurven-Kryptografie (ECC) — ein Ansatz für Public-Key-Kryptografie, der auf der algebraischen Struktur elliptischer Kurven über endlichen Körpern basiert. Er bietet eine mit RSA vergleichbare Sicherheit, benötigt aber kürzere Schlüssel. Das beschleunigt Berechnungen und senkt den Speicherbedarf. Solana verwendet die elliptische Kurve Ed25519 zur Erzeugung seiner Schlüsselpaare

Digitale Signaturen

Digitale Signaturen sind ein zentraler Bestandteil der Public-Key-Kryptografie. Mit ihnen lassen sich die Authentizität und Integrität einer Nachricht, Software oder eines digitalen Dokuments verifizieren. Eine digitale Signatur wird mit dem privaten Schlüssel des Absenders erstellt und kann von jedem verifiziert werden, der Zugriff auf den zugehörigen öffentlichen Schlüssel hat. So wird sichergestellt, dass die Nachricht von einem legitimen Absender stammt und nicht verändert wurde.

Zu den gängigen Algorithmen für digitale Signaturen gehören:

• Digital Signature Algorithm (DSA) — ein Ansatz, der auf modularer Exponentiation, also einer Exponentiation über einem Modulus, und dem Problem des diskreten Logarithmus basiert
• Elliptic Curve Digital Signature Algorithm (ECDSA) — eine DSA-Variante, die mit elliptischer Kurvenkryptografie bei kürzeren Schlüsseln ein höheres Sicherheitsniveau bietet

Problem des diskreten Logarithmus

Beim Problem des diskreten Logarithmus muss der Exponent k in der Gleichung $g^k \equiv h \pmod{p}$ bestimmt werden, wobei gilt:

• g ist eine bekannte Basis, also ein Generator
• h ist ein bekanntes Ergebnis, also ein Element der Gruppe
• p ist eine Primzahl, also die Ordnung der Gruppe
• k ist der unbekannte Exponent, also der diskrete Logarithmus von h zur Basis g

Wenn du die Werte von g, h und p kennst, besteht das Problem des diskreten Logarithmus also darin, k zu bestimmen. Bei der Gleichung $2^k \equiv 9 \pmod{23}$ besteht das Ziel beispielsweise darin, k zu ermitteln.

Das Problem des diskreten Logarithmus gilt als schwer effizient lösbar, besonders bei großen Zahlen. Deshalb bildet es die Sicherheitsgrundlage verschiedener kryptografischer Systeme, darunter Solana, die ElGamal-Verschlüsselung, digitale Signaturalgorithmen wie DSA und ECDSA sowie der Diffie-Hellman-Schlüsselaustausch.

Diffie-Hellman-Schlüsselaustausch

Der Diffie-Hellman-Schlüsselaustausch ist eine Methode, um kryptografische Schlüssel sicher über einen öffentlichen Kanal auszutauschen.  Die einfachste und ursprüngliche Implementierung, also Finite Field Diffie-Hellman, funktioniert wie folgt:

• Alice und Bob einigen sich öffentlich auf zwei Zahlen: eine große Primzahl p, also den Modulus, und eine Basis g, also den Generator, die eine Primitivwurzel modulo p ist 
• Alice wählt eine geheime ganze Zahl a und sendet Bob anschließend $A \equiv g^a \pmod{p}$
• Bob wählt eine geheime ganze Zahl b und sendet Alice anschließend $B \equiv g^b \pmod{p}$
• Alice berechnet $s \equiv B^a \pmod{p}$ 
• Bob berechnet $s = A^b \pmod{p}$ 

Alice und Bob besitzen nun denselben geheimen Wert. Beide Berechnungen ergeben nämlich dasselbe Geheimnis s:

Dieses gemeinsame Geheimnis s kann anschließend als Schlüssel für symmetrische Verschlüsselung dienen, sodass Alice und Bob sicher kommunizieren können. Die Sicherheit des Diffie-Hellman-Schlüsselaustauschs beruht auf der Schwierigkeit des Problems des diskreten Logarithmus. Ohne die geheimen Werte a und b ist es für einen Lauscher rechnerisch nicht praktikabel, das gemeinsame Geheimnis abzuleiten. Dies wird als Einwegfunktion bezeichnet: Sie lässt sich relativ leicht berechnen, aber nur äußerst schwer umkehren.

Der Finite-Field-Diffie-Hellman-Schlüsselaustausch ist sicher und weit verbreitet, erfordert für ausreichende Sicherheit jedoch große Schlüssellängen. Würden Alice und Bob beispielsweise öffentlich den Modulus 23 wählen, ließe sich das Verfahren wesentlich leichter knacken, da n mod 23 nur 23 mögliche Ergebnisse hat. Das kann hohen Rechenaufwand verursachen und weniger effizient sein. Elliptische-Kurven-Kryptografie (ECC) bietet eine effizientere Alternative, da sie dasselbe Sicherheitsniveau mit deutlich kürzeren Schlüsseln und schnelleren Berechnungen erreicht.

Elliptische Kurven

Eine elliptische Kurve wird durch die Gleichung $y^2 = x^3 + ax + b$ definiert, wobei a und b Konstanten sind. Bei der elliptischen Kurvenkryptografie arbeitet man einfach mit Punkten auf einer bestimmten elliptischen Kurve. Diese Kurven besitzen mehrere einzigartige Eigenschaften, die sie für die Kryptografie nützlich machen. Zum Beispiel:

• Addition von Punkten — Sind zwei Punkte P und Q auf einer bestimmten elliptischen Kurve gegeben, liegt auch ihre Summe R = P + Q auf der Kurve. Preethi Kasireddys Artikel Ein verständlicher Leitfaden zur Kryptografie für Zero-Knowledge-Beweise erklärt anschaulich, wie Punkte auf einer elliptischen Kurve addiert werden
• Skalarmultiplikation — Bei einem Punkt P auf einer bestimmten elliptischen Kurve und einer ganzen Zahl k wird der Punkt P bei der Skalarmultiplikation k-mal zu sich selbst addiert. Dadurch entsteht ein weiterer Punkt, also kP, auf der Kurve. So werden öffentliche Schlüssel aus privaten Schlüsseln erzeugt
• Problem des diskreten Logarithmus — Das Problem des diskreten Logarithmus ist auf elliptischen Kurven wesentlich schwerer zu lösen als sein ganzzahliges Gegenstück. Sind die Punkte P und q = kP gegeben, ist es bei korrekt gewählten Kurvenparametern rechnerisch nicht praktikabel, k zu bestimmen. Elliptische Kurven bieten daher dieselbe Sicherheit wie traditionelle Systeme, benötigen aber wesentlich kürzere Schlüssel und sind dadurch effizienter

Mit unseren neuen Kenntnissen der Gruppentheorie können wir sagen, dass bestimmte Gleichungen elliptischer Kurven die Gruppenaxiome erfüllen:

• Je zwei Punkte lassen sich zu einem dritten Punkt addieren
• Die Reihenfolge, in der die beiden Punkte addiert werden, spielt keine Rolle
• Wenn mehr als zwei Punkte addiert werden, spielt die Reihenfolge ihrer Addition keine Rolle
• Es gibt ein neutrales Element, das heißt: Wird null zu einem beliebigen Punkt auf der Kurve addiert, bleibt der Punkt unverändert

Ich empfehle dir, Elliptische-Kurven-Kryptografie von Georgie Bumpus zu lesen, um diese Gruppenstruktur genauer zu erkunden. 

Elliptische Kurven bieten dasselbe Sicherheitsniveau wie andere traditionelle Kryptosysteme, etwa RSA, benötigen aber wesentlich kürzere Schlüssel. Ein 256-Bit-Schlüssel in ECC bietet beispielsweise eine vergleichbare Sicherheit wie ein 3072-Bit-Schlüssel in RSA. Das ist vorteilhaft, weil:

• Kürzere Schlüssel ermöglichen eine schnellere Ver- und Entschlüsselung
• Schlüssel und Zertifikate benötigen weniger Speicherplatz
• Kürzere Schlüssel reduzieren die übertragene Datenmenge. Das ist in Umgebungen mit begrenzter Bandbreite wie einer Blockchain von Vorteil

Montgomery-Kurven

Montgomery-Kurven sind elliptische Kurven, die über einem endlichen Körper durch die Gleichung $By^2 = x^3 + Ax^2 + x$ definiert werden. Dabei sind A und B Konstanten, B ist ungleich null und A ist weder -2 noch 2. Diese Kurven sind besonders, weil sich die Multiplikation auf elliptischen Kurven mit einer Montgomery-Leiter effizienter implementieren lässt. 

Eine Montgomery-Leiter nimmt im Wesentlichen einen Punkt P auf einer Montgomery-Kurve und einen Skalar k, initialisiert zwei Punkte von unendlich bis P und verarbeitet jedes Bit des Skalars k vom höchstwertigen Bit bis zum niedrigstwertigen Punkt. Die zentrale Idee besteht darin, zwei Punkte beizubehalten und sie unabhängig von den Bits des Skalars k mit einer konstanten Folge von Operationen zu aktualisieren.

Das ist aus mehreren Gründen wichtig:

• Sie ist resistent gegen Seitenkanalangriffe. Dabei handelt es sich um Angriffe, die zusätzliche Informationen aus der Implementierung oder dem Design eines bestimmten Protokolls oder Algorithmus ausnutzen. Das ist ein wirklich, wirklich nerdiges Thema, in das du unbedingt tiefer eintauchen solltest. Diese Angriffe reichen vom schwankenden Stromverbrauch der Hardware während der Berechnung bis hin zu austretender elektromagnetischer Strahlung
• Die y-Koordinate wird nicht benötigt, da sich die Skalarmultiplikation allein mit den x-Koordinaten ausführen lässt
• Sie arbeitet in konstanter Zeit. Die Dauer einer bestimmten Berechnung ist also unabhängig vom Eingabewert

Montgomery-Kurven werden häufig in kryptografischen Protokollen eingesetzt, etwa im X25519-Algorithmus für den Schlüsselaustausch, der die Montgomery-Form der Kurve Curve25519 verwendet. Dieser Algorithmus bildet die Grundlage moderner sicherer Kommunikation und wird unter anderem in verbreiteten Protokollen wie TLS implementiert. 

Edwards-Kurven

Edwards-Kurven sind elliptische Kurven, die durch die Gleichung $x^2 + y^2 = 1 + d x^2 y^2$ definiert werden, wobei d eine von null und 1 verschiedene Konstante ist.  

Diese Kurven sind aus folgenden Gründen wichtig:

• Effiziente Punktoperationen — Zwei Punkte lassen sich auf einer Edwards-Kurve effizienter addieren als auf anderen Formen elliptischer Kurven. Die Formeln für Punktaddition und Punktverdopplung sind einfacher und benötigen weniger Körperoperationen. Dadurch lassen sie sich schneller berechnen
• Einheitliche Additionsformel — Edwards-Kurven verwenden eine einheitliche Additionsformel. Dieselbe Formel kann also für die Punktaddition und die Punktverdopplung eingesetzt werden. Das verringert das Risiko von Implementierungsfehlern und erhöht die Sicherheit
• Vollständigkeit — Für bestimmte Werte von d sind Edwards-Kurven vollständig. Das bedeutet, dass das Additionsgesetz ohne Ausnahmen alle möglichen Eingaben abdeckt.
• Resistenz gegen Seitenkanalangriffe — Wie Montgomery-Kurven sind auch Edwards-Kurven dank ihrer einheitlichen und vorhersehbaren Operationsmuster resistent gegen Seitenkanalangriffe.

Eine weit verbreitete Edwards-Kurve ist Edwards25519, die durch die Gleichung $x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$ definiert wird. Diese Kurve ist für ihre effiziente Arithmetik und ihre 256-Bit-Schlüssellänge bekannt. Ihr Signaturverfahren wird in verschiedenen Sicherheitsprotokollen und Systemen implementiert, darunter Solana, OpenSSH und Tor. Monero verwendet Edwards25519 als Grundlage für die Erzeugung seiner Schlüsselpaare.

Warum ist das wichtig?

Elliptische Kurven sind wegen ihrer Effizienz und sicherheitssteigernden Eigenschaften für Zero-Knowledge-Beweise entscheidend. Wichtig: Mit elliptischen Kurven lassen sich kleinere und schnellere Beweise erstellen, was für jede praktische Implementierung unerlässlich ist. Wir analysieren das genauer, wenn wir über Entwicklungen rund um Zero-Knowledge sprechen. Kleine und schnelle Beweise sind in einer rechenintensiven Umgebung mit verschiedenen Einschränkungen für Accounts und Transaktionen jedoch entscheidend. Deshalb eignen sich Zero-Knowledge-Beweise für den Aufbau von Rollups: Man kann einen kompakten Beweis dafür erzeugen, dass alle Operationen auf einer L2 gültig sind, und ihn auf der L1 validieren.

Letztlich kannst du dir elliptische Kurven als Ersatz für modulare Arithmetik vorstellen. Bei elliptischen Kurven ist es wesentlich schwieriger, einen bestimmten Punkt zu ermitteln. Würden wir traditionelle modulare Arithmetik mit $g^a \bmod n$ verwenden, wäre g ein Generator, n eine große Primzahl und a der geheime Schlüssel. Wie wir beim Problem des diskreten Logarithmus gesehen haben, benötigst du eine sehr große Primzahl, um den geheimen Schlüssel zu schützen. Elliptische Kurven bieten mit kürzeren Schlüsseln eine effizientere Alternative. Sie erreichen dasselbe Sicherheitsniveau bei deutlich besserer Performance.

Zufälligkeit

Ohne Zufälligkeit, einen grundlegenden Bestandteil der Kryptografie, wäre alles andere in diesem Artikel bedeutungslos. Wie soll ein System sicher sein, wenn seine Werte vorhersehbar und verzerrt sind? Echte Zufälligkeit ist schwer zu erreichen, aber aus mehreren Gründen unverzichtbar:

• Schlüsselerzeugung — Kryptografische Schlüssel müssen zufällig erzeugt werden, damit sie unvorhersehbar und sicher sind
• Nonces und Salts — Nonces, also nur einmal verwendete Zahlen, und Salts, also vor dem Hashing zu Daten hinzugefügte Zufallswerte, verhindern Replay-Angriffe beziehungsweise schützen vor vorberechneten Angriffen
• Sichere Protokolle — Zufälligkeit sorgt für Fairness und Sicherheit und verhindert Vorhersagbarkeit sowie Muster, die Angreifer ausnutzen könnten

Die meisten Zufallszahlengeneratoren erzeugen keine Zufallszahl, die sich kryptografisch verifizieren lässt. Das macht sie manipulierbar und schränkt ihre Anwendungsfälle ein. Verifizierbare Zufallsfunktionen lösen dieses Problem.

Verifizierbare Zufallsfunktionen

Eine verifizierbare Zufallsfunktion (VRF) ist ein kryptografisches Primitiv, das eine zufällige Ausgabe und einen Beweis dafür erzeugt, dass diese Ausgabe aus einer bestimmten Eingabe korrekt generiert wurde. Eine VRF muss unvorhersehbar sein. Für jeden, der die geheime Eingabe nicht kennt, darf ihre Ausgabe also nicht von einem Zufallswert unterscheidbar sein. Ihre Sicherheit beruht auf der RSA-Annahme, dass $y = h^d \bmod n$ ohne Kenntnis des geheimen Exponenten d schwer zu berechnen ist, sowie auf der Sicherheit der Hashfunktion H. 

Eine VRF umfasst im Wesentlichen die folgenden Schritte:

• Schlüsselerzeugung — Der Nutzer erzeugt ein Paar RSA-Schlüssel: (e, n) als öffentlichen und (d, n) als privaten Schlüssel. Beim öffentlichen Schlüssel ist e der Exponent und n der Modulus. Beim privaten Schlüssel ist d der geheime Exponent
• Berechnung — Für eine Eingabe x berechnet der Nutzer die VRF-Ausgabe y und den Beweis π. Zuerst wird der Hash h = H(x) berechnet, wobei H eine kryptografische Hashfunktion ist. Anschließend wird $y = h^d \bmod n$ berechnet, also die RSA-Signatur des Hashs. Abschließend wird der Beweis π = (h, y) berechnet
• Verifizierung — Mit dem öffentlichen Schlüssel (e, n), der Eingabe x, der Ausgabe y und dem Beweis π = (h, y) kann jeder die Korrektheit der VRF-Ausgabe verifizieren. Dazu wird geprüft, ob der Hash h gleich $H(x)$ ist und ob $y^e \equiv h \pmod{n}$ gilt, um die RSA-Gleichung zu verifizieren‍

VRFs werden häufig in Konsensprotokollen eingesetzt, bei denen Zufälligkeit unvorhersehbar, aber verifizierbar sein muss. L1s wie Algorand, Cardano, Internet Computer und Polkadot verwenden VRFs in ihren Konsensmechanismen, um Blockproduzenten zufällig auszuwählen. Chainlink bietet Chainlink VRF als Abstraktionsschicht zwischen dem Nutzer und der Blockchain an, um nachweislich faire und verifizierbare Werte zu erzeugen. Auch Pyth Entropy bietet eine zuverlässige und sichere Quelle für Zufälligkeit.

Zeremonien und Trusted Setups

Kryptografische Zeremonien sind Protokolle oder Veranstaltungen, bei denen kritische kryptografische Berechnungen in einer sicheren, kontrollierten Umgebung ausgeführt werden. Es gibt verschiedene Arten kryptografischer Zeremonien:

• Zeremonien zur Schlüsselerzeugung — Dabei werden kryptografische Schlüssel erzeugt, um sicherzustellen, dass keine einzelne Instanz den Prozess der Schlüsselerzeugung kontrolliert
• Zeremonien zur Parametererzeugung — Dabei werden kryptografische Parameter erstellt, die mehrere Parteien verwenden
• Multi-Party-Computation-Zeremonien (MPC) — Dabei führen mehrere Parteien gemeinsam eine kryptografische Berechnung aus, damit keine einzelne Partei den Prozess kompromittieren kann

Eine Trusted-Setup-Zeremonie ist eine besondere Veranstaltung oder ein besonderer Prozess, bei dem die kryptografischen Parameter erzeugt werden, die ein kryptografisches Protokoll benötigt. In unserem Abschnitt über interaktive und nicht interaktive Zero-Knowledge-Beweise haben wir festgestellt, dass sich Beweisführer und Verifizierer im ersten Schritt eines Beweises auf einen zu verwendenden Wert einigen müssen. Bei einer Trusted-Setup-Zeremonie bringen mehrere Teilnehmer Zufälligkeit in das Setup ein, damit kein einzelner Teilnehmer den Prozess kontrolliert. Jeder Teilnehmer erzeugt einen Zufallswert, der mit den Werten der anderen Teilnehmer kombiniert wird. Die kombinierte Ausgabe bildet eine Menge von Parametern, denen alle vertrauen können. 

Dieser Prozess ist entscheidend, denn wenn alle Teilnehmer zusammenarbeiten würden, könnten sie das System brechen, indem sie einen Beweis für eine ungültige Behauptung erzeugen. Bereits ein einziger ehrlicher Teilnehmer gewährleistet jedoch die Sicherheit der Parameter. 

Zcash nutzte bekanntermaßen eine Trusted-Setup-Zeremonie, um die Datenschutzfunktionen der Chain zu starten. Auch Ethereum führte die KZG-Zeremonie durch, ein koordiniertes öffentliches Ritual, das eine kryptografische Grundlage für seine Skalierungsmaßnahmen wie EIP-4844 und Proto-Danksharding schaffen sollte. 

Einige Zero-Knowledge-Beweissysteme wie zk-STARKs benötigen kein Trusted Setup. Darauf gehen wir im zweiten Artikel genauer ein.

Fazit

In diesem Artikel haben wir die grundlegende Theorie, Mathematik und Kryptografie hinter Zero-Knowledge-Beweisen untersucht. Damit weißt du alles, was du brauchst, um die Frage zu beantworten, was Zero-Knowledge-Beweise sind. Nun können wir diese Erkenntnisse auf Netzwerke wie Solana anwenden und so zur allgemeinen Diskussion und Weiterentwicklung von Zero-Knowledge-Beweisen beitragen.

Wir setzen diese Analyse im zweiten und letzten Artikel unserer zweiteiligen Reihe über Zero-Knowledge-Beweise fort. Er trägt den passenden Titel Zero-Knowledge-Beweise: Ihre Anwendungen auf Solana. 

Wenn du bis hierher gelesen hast: Danke, anon! Trag unten deine E-Mail-Adresse ein, damit du keine Neuigkeiten rund um Solana verpasst. Möchtest du tiefer einsteigen? Entdecke die neuesten Artikel im Helius-Blog und setze deine Solana-Reise noch heute fort.

Weitere Ressourcen

• Gibt es echten Zufall?
• Elliptische Kurven — Computerphile
• Einführung in die NP-vollständige Komplexitätsklasse
• Probleme beim Schlüsselaustausch — Computerphile
• Kryptografie-Lerneinheit der Khan Academy
• Public-Key-Kryptografie — Computerphile
• Die Wissenskomplexität interaktiver Beweissysteme