Wie zeigt man, dass man eine Graphenfärbung kennt, ohne sie zu verraten? Ein Zero-Knowledge-Beweis macht das möglich. Der Autor erklärt das Konzept anhand der 3-Färbung von Graphen. Sein Interesse galt nicht Kryptowährungen, sondern einer Variante, die ein Freund ihm zeigte – sie basiert auf Graphentheorie und ist in wenigen Zeilen implementierbar.
Was ist ein Zero-Knowledge-Beweis?
Ein Zero-Knowledge-Beweis ist ein interaktives Protokoll. Zwei Parteien sind beteiligt: der Beweiser und der Verifizierer. Der Beweiser will den Verifizierer überzeugen, dass er eine Lösung für ein schwieriges Problem hat, ohne auch nur die kleinste Information darüber preiszugeben. Das klingt paradox, ist es aber nicht. Das Standardbeispiel ist die Drei-Färbung eines Graphen. Dabei bekommt jeder Knoten eine von drei Farben, und benachbarte Knoten dürfen nicht dieselbe Farbe haben. Ein Graph besteht aus Knoten und Kanten, die sie verbinden. Die 3-Färbung ist NP-vollständig: Es ist schwer, eine Färbung zu finden, aber leicht, sie zu prüfen – man geht alle Kanten durch und kontrolliert, ob die Endknoten unterschiedlich gefärbt sind. Diese Asymmetrie nutzen Zero-Knowledge-Beweise aus.
Das interaktive Protokoll für die 3-Färbung
Das Protokoll stammt von Goldreich, Micali und Wigderson. Es läuft in mehreren Runden ab, jede mit vier Schritten. Zuerst permutiert der Beweiser die drei Farben zufällig. Die Farben sind nur Platzhalter – wichtig ist nur, dass sie verschieden sind. Er wendet die Permutation auf seine ursprüngliche Färbung an, die damit gültig bleibt. Dann verschlüsselt er jede Farbe mit einem zufälligen Nonce und berechnet einen Hash. Die Hashes schickt er als ‚verschlossene Boxen‘ an den Verifizierer. Ohne Nonce sind die Hashes nicht umkehrbar, also erfährt der Verifizierer nichts. Der Verifizierer wählt zufällig eine Kante aus und teilt sie dem Beweiser mit. Dieser öffnet die zwei Boxen für die Endknoten und schickt Farben und Nonces. Der Verifizierer prüft zwei Dinge: Passen die Hashes zu den Werten, und sind die Farben verschieden? Wenn ja, ist die Runde erfolgreich. Wenn nein, bricht er ab – der Beweiser hat betrogen.
Man kann sich das wie versiegelte Umschläge vorstellen. Der Beweiser legt in jeden Umschlag eine Farbe und einen Geheimcode und klebt ihn zu. Der Verifizierer sieht nur die Umschläge. Er wählt eine Kante aus, also zwei verbundene Knoten, und der Beweiser öffnet die zwei Umschläge. So bekommt der Verifizierer nur die Information über diese eine Kante – und die ist korrekt, wenn der Beweiser eine gültige Färbung hat.
Warum viele Runden nötig sind
Eine einzelne Runde gibt nur geringe Sicherheit. Der Beweiser könnte eine Färbung haben, die nur auf einer Kante stimmt, und hoffen, dass diese nicht abgefragt wird. Deshalb wiederholt man das Protokoll viele Male. Der Autor gibt die Formel (1 – m^{-1})^(m^2) an, wobei m die Anzahl der Kanten ist. Je mehr Runden, desto kleiner die Chance für einen Betrüger. Bei 1000 Kanten liegt die Wahrscheinlichkeit nach 4600 Runden bei etwa einem Prozent, nach 10.000 Runden bei 0,0045 Prozent. Mit m² Runden, wie im Paper vorgeschlagen, ist sie praktisch null. Die Wiederholungen kosten Zeit, machen das Verfahren aber mathematisch wasserdicht – vorausgesetzt, die Zufallszahlen sind wirklich zufällig und die Hashfunktion kryptografisch stark.
Implementierung und praktische Überlegungen
Der Autor hat mit seinem Freund Chris eine Python-Implementierung geschrieben, die das Protokoll in einem Prozess nachbildet. Für das Verständnis reicht das, aber für echte Sicherheit sind Details wichtig. Man sollte nicht die eingebaute hash-Funktion verwenden, sondern eine kryptografische wie SHA-256. Die Nonces brauchen einen sicheren Zufallsgenerator, etwa aus dem secrets-Modul. Für reproduzierbare Tests kann man random.seed(0) setzen, aber in der Praxis wäre das fatal. Um die Trennung von Beweiser und Verifizierer zu zeigen, gibt es auch eine Netzwerk-Demo: Ein Server ist der Beweiser, ein Client der Verifizierer. So läuft die Kommunikation über echte Netzwerkpakete, was die Geheimhaltung besser demonstriert.
Von der Graphenfärbung zu anderen Problemen
Die Graphenfärbung ist kein theoretisches Spielzeug. Jedes NP-vollständige Problem lässt sich auf sie reduzieren. Eine Lösung für ein solches Problem kann man in eine 3-Färbung umwandeln und dann das Zero-Knowledge-Protokoll anwenden. Sudoku ist ein Beispiel: Ein gelöstes Sudoku lässt sich als Graphenfärbung interpretieren, und man könnte einen Zero-Knowledge-Beweis führen, ohne die Lösung zu zeigen. In der Praxis ist die Reduktion oft ineffizient. Bei der Primfaktorzerlegung würde der Graph zu groß, das Verfahren wird unpraktikabel. In der Praxis nutzt man andere Techniken, etwa elliptische Kurven, aber das Grundprinzip bleibt.
Grenzen und Einordnung
Der Autor interessiert sich nicht für Altersverifikation oder Blockchain. Ihm geht es um die theoretische Schönheit. Zero-Knowledge-Beweise sind ein Werkzeug der Kryptographie, das auf einfachen Ideen der Graphentheorie beruht. Die 3-Färbung ist ein lehrreiches Beispiel, weil sie das Prinzip zeigt, ohne tief in die Mathematik einzusteigen. Auch wenn die direkte Umsetzung für praktische Probleme zu aufwendig ist, zeigt das Beispiel, wie man mit einfachen Mitteln Vertrauen aufbaut – ohne Geheimnisse preiszugeben. Es verbindet Einfachheit und Tiefe und ist daher für jeden interessant, der verstehen will, wie moderne Kryptographie funktioniert.
Quelle: bernsteinbear.com
