Sven Erik Matzen

Software Architect | Cloud & Security Expert | AI-enabled Solutions

Beweisen ohne zu verraten: Zero-Knowledge-Beweise von Ali Babas Höhle bis zu zk-SNARKs

🎧 Listen to this article

IT-Security · 2026-08-17

EU-Kennzeichnung: vollständig KI-generierter Inhalt Vollständig KI-generierter Artikel (ohne Vorabprüfung).

Der Aufhänger: Der Beweis, der nichts preisgibt

Stell dir vor, du willst jemandem beweisen, dass du ein Passwort kennst – aber du willst das Passwort selbst um keinen Preis verraten. Oder du willst einer Bank beweisen, dass dein Kontostand über zehntausend Euro liegt, ohne den genauen Betrag zu nennen. Oder du willst einem Onlinedienst beweisen, dass du volljährig bist, ohne dein Geburtsdatum, deinen Namen oder auch nur deinen Ausweis herzuzeigen. Auf den ersten Blick klingt das wie ein logischer Widerspruch: Ein Beweis ist doch gerade dazu da, Information zu übertragen. Wie soll man etwas beweisen, ohne dabei irgendetwas zu verraten?

Die verblüffende Antwort der modernen Kryptografie lautet: Es geht. Und zwar nicht ein bisschen, sondern in einem mathematisch präzisen, geradezu extremen Sinn. Ein Zero-Knowledge-Beweis (auf Deutsch: Null-Wissen-Beweis) ist ein Verfahren, mit dem eine Partei – die Beweisende, traditionell Peggy (von prover) genannt – eine andere Partei – die Prüfende, Victor (von verifier) – von der Wahrheit einer Aussage überzeugen kann, sodass Victor am Ende von der Wahrheit vollständig überzeugt ist, aber kein einziges Bit darüber hinaus erfährt. Nichts über das Passwort, nichts über den Kontostand, nichts, was er nicht ohnehin schon wusste. Der einzige Wissenszuwachs, den Victor davonträgt, ist die schlichte Tatsache: „Die Aussage ist wahr."

Diese Idee wurde 1985 von Shafi Goldwasser, Silvio Micali und Charles Rackoff in einer Arbeit mit dem sperrigen Titel The Knowledge Complexity of Interactive Proof-Systems eingeführt – einer Arbeit, die zunächst mehrfach von Konferenzen abgelehnt wurde und heute als eine der Gründungsurkunden der modernen theoretischen Kryptografie gilt. Goldwasser und Micali erhielten 2012 für diese und verwandte Arbeiten den Turing-Award, den „Nobelpreis der Informatik". Vier Jahrzehnte später ist aus dem abstrakten Gedankenexperiment eine Technologie geworden, die Milliarden von Euro in Kryptowährungen absichert, das Ethereum-Netzwerk skaliert und langsam Einzug in digitale Ausweise hält.

Für jemanden wie Sven – Senior AI Engineer mit einem Standbein in der IT-Sicherheit – sind Zero-Knowledge-Beweise ein Musterbeispiel dafür, wie eine tiefe theoretische Einsicht (dass „Wissen" selbst quantifizierbar ist und man Beweise von Information entkoppeln kann) über Jahrzehnte zu handfester, milliardenschwerer Praxis reift. Dieser Artikel nimmt dich auf die ganze Strecke mit: von der intuitiven Höhle des Ali Baba über die drei mathematischen Eigenschaften, die einen Zero-Knowledge-Beweis definieren, und konkrete Protokolle, bis zu der explosionsartigen Entwicklung der zk-SNARKs und zk-STARKs, die seit rund zehn Jahren die Blockchain-Welt und darüber hinaus umkrempeln – und schließlich zu den Fallstricken, die man kennen muss, um sie nicht katastrophal falsch einzusetzen.

Teil 1: Was ein Beweis eigentlich leisten muss – die drei Eigenschaften

Bevor wir über Null Wissen reden, müssen wir klären, was ein interaktiver Beweis überhaupt ist – denn das ist die eigentliche begriffliche Neuerung von Goldwasser, Micali und Rackoff.

Der klassische, statische Beweisbegriff der Mathematik ist ein Text: eine Kette von Schlüssen, die man einmal aufschreibt und die jeder Prüfer schweigend nachlesen kann. Der interaktive Beweisbegriff ist etwas anderes – er ist ein Dialog. Peggy und Victor tauschen über mehrere Runden Nachrichten aus, und Victor darf dabei Zufall verwenden: Er würfelt und stellt Peggy Fragen, deren Ausgang sie nicht vorhersehen konnte. Am Ende entscheidet Victor, ob er überzeugt ist. Genau dieser Zufall und diese Interaktion sind der Hebel, der das scheinbar Unmögliche möglich macht.

Ein interaktives Beweissystem gilt als Zero-Knowledge-Beweis, wenn es drei Eigenschaften erfüllt, die man sich einprägen sollte, denn sie sind das Skelett des ganzen Feldes.

Die erste Eigenschaft ist die Vollständigkeit (completeness). Sie besagt: Wenn die Aussage wahr ist und beide Parteien sich an das Protokoll halten, dann wird Victor am Ende überzeugt. Ein ehrlicher Peggy, der wirklich das Geheimnis kennt, kann Victor also stets erfolgreich überzeugen. Das ist die selbstverständliche Mindestforderung – ein Beweissystem, das wahre Aussagen nicht durchgehen lässt, wäre nutzlos.

Die zweite Eigenschaft ist die Korrektheit oder Zuverlässigkeit (soundness). Sie ist die eigentlich schwierige Richtung: Wenn die Aussage falsch ist, dann kann kein noch so trickreicher, betrügerischer Peggy Victor überzeugen – außer mit verschwindend geringer Wahrscheinlichkeit. Hier kommt der Zufall ins Spiel. In einem einzelnen Durchgang mag ein Betrüger mit Glück durchkommen – etwa mit Wahrscheinlichkeit ein Halb, wenn Victor eine Ja/Nein-Frage stellt. Aber wiederholt man den Durchgang unabhängig oft, sinkt die Chance des Betrügers exponentiell: Bei zwanzig Wiederholungen liegt sie unter eins zu einer Million, bei vierzig unter eins zu einer Billion. Man kann die Fehlerwahrscheinlichkeit also beliebig klein „herunterschrauben", ohne sie je exakt auf null zu bringen. Diese statistische Sicherheit ist eine Grundsignatur des Feldes.

Die dritte Eigenschaft ist die eigentliche Pointe: Zero-Knowledge (Null Wissen). Sie besagt: Victor lernt aus dem gesamten Dialog nichts, was er nicht auch allein hätte ausrechnen können – außer der Tatsache, dass die Aussage wahr ist. Wie formalisiert man eine so schwer fassbare Idee wie „nichts lernen"? Der geniale Kunstgriff von Goldwasser, Micali und Rackoff heißt Simulator-Argument. Man fordert: Es muss ein effizientes Computerprogramm (den Simulator) geben, das – ohne das Geheimnis zu kennen – Gesprächsprotokolle erzeugen kann, die von echten Gesprächen zwischen Peggy und Victor ununterscheidbar sind. Die Logik dahinter ist bestechend: Wenn ein außenstehender Beobachter ein gefälschtes Protokoll (vom Simulator, ganz ohne Geheimnis erzeugt) nicht von einem echten (mit Geheimnis) unterscheiden kann, dann kann im echten Protokoll unmöglich Information über das Geheimnis stecken. Denn alles, was Victor sieht, hätte er sich auch selbst herbeisimulieren können. Das Gespräch ist, im wörtlichen Sinne, informationsleer.

Diese drei Eigenschaften – Vollständigkeit, Korrektheit, Null Wissen – sind das Gütesiegel. Fehlt die erste, ist der Beweis unbrauchbar; fehlt die zweite, ist er unsicher; fehlt die dritte, ist es zwar ein Beweis, aber eben kein Zero-Knowledge-Beweis. Halten wir das im Kopf, während wir in die berühmteste Veranschaulichung des Ganzen hinabsteigen.

Teil 2: Die Höhle des Ali Baba

Die schönste und meistzitierte Erklärung des Zero-Knowledge-Prinzips stammt aus einer wunderbar betitelten Arbeit von 1989: How to Explain Zero-Knowledge Protocols to Your Children von Jean-Jacques Quisquater, Louis Guillou und – als Ko-Autoren aufgeführt – ihren jeweiligen Kindern. Sie erzählt vom Ringhöhle des Ali Baba.

Stell dir eine kreisförmige Höhle vor mit einem einzigen Eingang. Kurz hinter dem Eingang gabelt sich der Gang in zwei Wege, einen linken (A) und einen rechten (B), die sich hinten im Kreis wieder treffen. An der hinteren Verbindungsstelle steht jedoch eine magische Tür, die nur mit einem geheimen Zauberwort geöffnet werden kann. Peggy behauptet, dieses Zauberwort zu kennen. Sie will es Victor beweisen – aber sie will das Wort selbst nicht verraten, und mehr noch: Sie will nicht einmal, dass irgendein zufällig vorbeikommender Zeuge überzeugt würde, denn ihr Wissen ist kostbar.

Das Protokoll läuft so ab. Victor wartet draußen, außer Sichtweite der Gabelung. Peggy betritt die Höhle und wählt heimlich einen der beiden Gänge, A oder B. Dann tritt Victor bis zur Gabelung vor und ruft laut, aus welchem Gang Peggy herauskommen soll – ebenfalls zufällig gewählt, sagen wir „B". Nun gibt es zwei Fälle. Kennt Peggy das Zauberwort, so kann sie immer aus dem verlangten Gang erscheinen: Steht sie schon in B, kommt sie einfach zurück; steht sie in A, geht sie durch die magische Tür und kommt in B heraus. Kennt sie das Wort nicht, so kann sie nur dann korrekt herauskommen, wenn sie zufällig von vornherein im richtigen Gang stand – also mit Wahrscheinlichkeit ein Halb.

Ein einziger Durchgang beweist wenig: Ein Schwindler hat eine Fifty-fifty-Chance. Aber wiederholt man das Spiel zwanzigmal, und Peggy kommt jedes Mal aus dem richtigen Gang, so müsste ein Betrüger zwanzigmal hintereinander richtig geraten haben – eine Chance von eins zu über einer Million. Ab einer bestimmten Zahl von Runden ist Victor rational vollständig überzeugt. Das ist die Korrektheit in Bildern: Betrug wird durch Wiederholung exponentiell unwahrscheinlich.

Und die Null-Wissen-Eigenschaft? Man erkennt sie an einem herrlichen Gedankenexperiment. Angenommen, Victor filmt das ganze Geschehen heimlich mit einer Kamera, um später einem Freund zu beweisen, dass Peggy das Wort kennt. Das Video zeigt: Peggy verschwindet, Victor ruft einen Gang, Peggy erscheint dort – zwanzigmal in Folge korrekt. Überzeugend? Für Victor selbst ja, denn er weiß, dass er die Gänge zufällig und unvorhersehbar gerufen hat. Aber der Freund, der das Video später sieht, ist mitnichten überzeugt. Denn Peggy und Victor hätten sich heimlich absprechen können: Victor ruft im Voraus vereinbarte Gänge, und Peggy stellt sich vorher hinein. Ein solches abgekartetes Video ist von einem echten nicht zu unterscheiden – es sieht exakt gleich aus. Genau das ist das Simulator-Argument in Anschauung: Man kann ein perfekt echt aussehendes „Beweisvideo" erzeugen, ohne das Wort zu kennen. Folglich steckt im Video keinerlei Information über das Wort. Das echte Protokoll überzeugt nur den, der die Zufallsrufe selbst kontrolliert hat, und ist für jeden Dritten wertlos – und gerade darin liegt seine Stärke: Es überträgt Überzeugung, aber kein übertragbares Wissen.

Die Höhle veranschaulicht damit alle drei Eigenschaften: Ein Wissender kommt immer durch (Vollständigkeit), ein Unwissender fliegt über viele Runden fast sicher auf (Korrektheit), und das aufgezeichnete Geschehen ist ohne Beteiligung selbst simulierbar und damit informationsleer (Null Wissen). Was in der Metapher noch wie ein Salonspiel wirkt, wird im nächsten Schritt zu echter Mathematik.

Teil 3: Ein echtes Protokoll – von quadratischen Resten zu Schnorr

Die Höhle ist eine Metapher. Damit daraus Kryptografie wird, braucht man ein mathematisches Problem, das die Rolle des „Zauberworts" spielt: etwas, das leicht zu prüfen, aber schwer zu erraten ist. Genau hier setzen die realen Protokolle an, und zwei davon lohnen einen genaueren Blick, weil sie zeigen, wie aus der Anschauung Zahlenmagie wird.

Das erste stützt sich auf ein zahlentheoretisches Problem, das schon Goldwasser, Micali und Rackoff in ihrer Originalarbeit als Beispiel nutzten: die quadratische Restheit. Zu einer großen zusammengesetzten Zahl n (Produkt zweier geheimer Primzahlen) heißt eine Zahl y ein quadratischer Rest modulo n, wenn es ein x gibt mit x² kongruent zu y (modulo n). Ohne die Primfaktoren von n zu kennen, ist es praktisch unmöglich zu entscheiden, ob ein gegebenes y ein solches Quadrat ist – dieses „Quadratische-Reste-Problem" gilt als hart. Peggy kennt eine Quadratwurzel x von y und will beweisen, dass y ein Quadrat ist, ohne x preiszugeben. Das Protokoll folgt exakt dem Höhlen-Rhythmus: Peggy schickt einen zufällig „geblendeten" Wert (ihr Commitment), Victor stellt eine unvorhersehbare Ja/Nein-Frage (die Challenge), Peggy antwortet, und die Antwort geht nur auf, wenn sie x wirklich kennt. Ein Betrüger kann höchstens eine der beiden möglichen Fragen im Voraus „vorbereiten" und fliegt bei der anderen mit Wahrscheinlichkeit ein Halb auf. Wiederholung drückt die Betrugschance beliebig tief. Dieses Commit–Challenge–Response-Muster – „festlegen, herausfordern, antworten" – ist das universelle Skelett fast aller interaktiven Zero-Knowledge-Protokolle. Aus ihm ging 1988 auch das effiziente Feige-Fiat-Shamir-Identifikationsverfahren hervor.

Das zweite, für die Praxis vielleicht wichtigste Protokoll ist das Schnorr-Protokoll (Claus-Peter Schnorr, 1989/1991). Es beweist Wissen eines diskreten Logarithmus: In einer geeigneten mathematischen Gruppe ist es leicht, aus einem geheimen Exponenten w den öffentlichen Wert g^w zu berechnen, aber praktisch unmöglich, aus g^w den Exponenten w zurückzugewinnen (das „Diskrete-Logarithmus-Problem", dieselbe Härte, auf der Diffie-Hellman und ECDSA ruhen). Peggy beweist, dass sie den geheimen Schlüssel w zum öffentlichen Schlüssel g^w kennt, ohne w zu nennen. Der Ablauf ist wieder Commit–Challenge–Response: Peggy wählt einen frischen Zufallswert r und sendet g^r (Commitment); Victor sendet eine zufällige Challenge c; Peggy antwortet mit s = r + c·w; Victor prüft eine einzige Gleichung, die genau dann aufgeht, wenn Peggy w kennt. Der Zufallswert r „verschleiert" w dabei perfekt – aus s allein lässt sich w nicht herausrechnen, denn r ist unbekannt. Das Schnorr-Protokoll ist so schlank und elegant, dass es bis heute das Herzstück unzähliger Identifikations- und Signaturverfahren bildet; die Schnorr-Signaturen etwa sind seit 2021 über das Taproot-Upgrade fester Bestandteil von Bitcoin.

Diese Protokolle heißen oft Sigma-Protokolle – wegen der drei Nachrichten, deren Verlauf grafisch an den Buchstaben Σ erinnert. Sie sind die Arbeitspferde der interaktiven Zero-Knowledge-Welt: mathematisch verstanden, effizient, und – wie wir gleich sehen – der Rohstoff, aus dem sich mit einem cleveren Trick nicht-interaktive Beweise und Signaturen schmieden lassen. Zuerst aber die vielleicht folgenreichste theoretische Einsicht des ganzen Feldes.

Teil 4: Alles in NP – warum sich jede Wahrheit beweisen lässt

Bis hierhin könnte man denken, Zero-Knowledge sei ein Nischentrick für ein paar handverlesene zahlentheoretische Probleme: quadratische Reste, diskrete Logarithmen. Der wahre Paukenschlag kam 1986/87 von Oded Goldreich, Silvio Micali und Avi Wigderson (kurz GMW). Ihr Ergebnis ist so grundlegend, dass es die Richtung des ganzen Feldes bestimmte: Für jede Aussage, deren Wahrheit sich überhaupt effizient überprüfen lässt – also für jede Aussage in der Komplexitätsklasse NP – existiert ein Zero-Knowledge-Beweis, sofern nur Einwegfunktionen existieren (eine Annahme, auf der ohnehin die gesamte praktische Kryptografie ruht).

Warum ist das so gewaltig? NP ist die Klasse aller Probleme, deren Lösung sich schnell prüfen lässt, wenn man sie vorgelegt bekommt – und das umfasst einen enormen Teil aller praktisch interessanten Aussagen: „Dieses Sudoku hat eine Lösung", „Dieser Stundenplan erfüllt alle Nebenbedingungen", „Diese Transaktion ist nach den Regeln gültig", „Ich kenne einen Schlüssel, der zu diesem Hashwert passt". GMW zeigten: All das – und alles andere in NP – lässt sich beweisen, ohne die Lösung selbst zu zeigen. Man kann die Existenz einer Sudoku-Lösung beweisen, ohne die Lösung zu verraten; man kann die Gültigkeit einer Transaktion beweisen, ohne Absender, Empfänger oder Betrag offenzulegen.

Der Beweis nutzt einen tiefen Satz der Komplexitätstheorie: Alle NP-Probleme sind ineinander übersetzbar (NP-Vollständigkeit). Es genügt daher, ein einziges NP-vollständiges Problem mit einem Zero-Knowledge-Beweis auszustatten – dann erbt jedes andere NP-Problem den Beweis durch Übersetzung. GMW wählten die Graph-3-Färbung: Gegeben ein Netz aus Knoten und Kanten, kann man die Knoten mit drei Farben so einfärben, dass keine zwei durch eine Kante verbundenen Knoten dieselbe Farbe tragen? Das ist NP-vollständig.

Das zugehörige Protokoll ist so anschaulich, dass es sich lohnt, es vorzustellen – und es ist im Grunde eine mathematisierte Höhle. Peggy kennt eine gültige 3-Färbung des Graphen. In jeder Runde tut sie dreierlei. Erstens permutiert sie die drei Farben zufällig (aus Rot-Grün-Blau wird etwa Blau-Rot-Grün), sodass die konkreten Farben keine Bedeutung tragen. Zweitens „versiegelt" sie die Farbe jedes Knotens in einer verschlossenen Schachtel – kryptografisch: in einem Commitment, das den Wert bindend festlegt, ihn aber verbirgt. Diese versiegelten Schachteln schickt sie an Victor. Drittens darf Victor nun eine einzige Kante auswählen und verlangen, dass Peggy nur die beiden Schachteln an ihren Enden öffnet. Peggy öffnet sie; Victor prüft, ob die beiden Farben verschieden sind. Sind sie es, hat Peggy diese eine Runde bestanden.

Man sieht sofort, wie die drei Eigenschaften zusammenspielen. Vollständigkeit: Ist der Graph wirklich korrekt gefärbt, sind die Enden jeder Kante stets verschieden gefärbt, Peggy besteht immer. Korrektheit: Ist der Graph nicht 3-färbbar, so muss mindestens eine Kante zwei gleichfarbige Enden haben; Victor trifft sie mit einer gewissen Mindestwahrscheinlichkeit (bei m Kanten mindestens eins zu m), und über genügend viele Runden fliegt der Betrug fast sicher auf. Null Wissen: Victor sieht pro Runde nur zwei verschiedene Farben an einer einzigen Kante – und weil Peggy die Farben jede Runde neu zufällig permutiert, ist das bloß „zwei zufällige verschiedene Farben aus dreien", eine Information, die Victor sich selbst hätte ausdenken können. Über die Gesamtfärbung erfährt er nichts. Wieder greift das Simulator-Argument: Man kann diese Zwei-Farben-Ausschnitte ohne jede Kenntnis der echten Färbung nachstellen.

Die Tragweite dieses Resultats kann man kaum überschätzen. GMW verwandelten Zero-Knowledge von einem Sammelsurium einzelner Tricks in ein universelles Werkzeug: Alles, was man effizient prüfen kann, kann man auch beweisen, ohne es zu zeigen. Damit war der Weg frei, Zero-Knowledge nicht mehr nur für „Ich kenne einen Schlüssel", sondern für beliebig komplexe Aussagen – ganze Berechnungen, ganze Programme – zu denken. Dieser Sprung sollte allerdings Jahrzehnte und einen zweiten Ideenschub brauchen, bis er praktisch wurde.

Teil 5: Vom Dialog zum Dokument – die Fiat-Shamir-Transformation

Alle bisher betrachteten Beweise haben einen praktischen Schönheitsfehler: Sie sind interaktiv. Peggy und Victor müssen live, hin und her, mehrere Runden miteinander sprechen. Für viele Anwendungen ist das untauglich. Eine digitale Signatur etwa muss ein Dokument sein, das man einmal erzeugt und das später jeder – auch ohne Rückfragen an den Signierer – prüfen kann. Eine Blockchain-Transaktion muss ohne Live-Dialog mit einem Prüfer gültig sein. Wie macht man aus einem Zwiegespräch ein für sich stehendes, nicht-interaktives Beweisdokument?

Die Antwort ist einer der elegantesten Kniffe der Kryptografie: die Fiat-Shamir-Transformation, 1986 von Amos Fiat und Adi Shamir eingeführt. Die Grundidee entspringt einer scharfen Beobachtung. Wofür braucht man Victor im interaktiven Protokoll eigentlich? Nur für eines: um an der richtigen Stelle eine unvorhersehbare Zufalls-Challenge zu liefern, die Peggy nicht im Voraus kennen und daher nicht vorab „präparieren" konnte. Genau diese Unvorhersehbarkeit ist der Kern der Korrektheit. Fiat und Shamir fragten: Kann Peggy sich diese Zufalls-Challenge nicht selbst erzeugen – auf eine Weise, die sie nicht manipulieren kann?

Die Lösung: Peggy ersetzt Victors Zufallsruf durch den Hashwert ihrer eigenen bisherigen Nachrichten. Statt zu warten, bis Victor eine Challenge c würfelt, berechnet Peggy c = H(Commitment) selbst, wobei H eine kryptografische Hashfunktion ist. Das Entscheidende: Weil eine gute Hashfunktion sich wie ein Zufallsorakel verhält – ihr Ergebnis ist praktisch unvorhersehbar und hängt chaotisch von der Eingabe ab –, kann Peggy die Challenge nicht zu ihren Gunsten wählen. Sie ist an ihr Commitment gebunden, bevor die Challenge feststeht, denn die Challenge ist ja gerade der Hash dieses Commitments. Damit ist Victor als lebender Zufallsgeber überflüssig geworden: Peggy erzeugt das gesamte Protokoll allein – Commitment, selbstgehashte Challenge, Response – und schreibt es als ein einziges Dokument nieder. Jeder kann dieses Dokument später prüfen, indem er nachrechnet, ob die Challenge wirklich der Hash des Commitments ist und ob die Response aufgeht. Aus dem Dialog ist ein Dokument geworden, aus dem interaktiven ein nicht-interaktiver Zero-Knowledge-Beweis (NIZK).

Der schönste Nebeneffekt fällt fast beiläufig ab: Bindet man in den Hash zusätzlich eine Nachricht ein – berechnet man also c = H(Commitment ‖ Nachricht) –, so ist der resultierende Beweis untrennbar an genau diese Nachricht gekettet. Und das ist nichts anderes als eine digitale Signatur. Wer den geheimen Schlüssel kennt, kann für jede Nachricht einen solchen Beweis erzeugen; wer ihn nicht kennt, kann es nicht. Auf genau diesem Wege entstehen die Schnorr-Signatur und die weit verbreitete EdDSA/Ed25519-Signatur, die heute SSH-Schlüssel, TLS-Zertifikate und Software-Signaturen absichert. Die Fiat-Shamir-Transformation ist damit eine der stillen Brücken zwischen der Theorie der Zero-Knowledge-Beweise und der alltäglichen Kryptografie, die in jedem Betriebssystem steckt.

Ein wichtiger Vorbehalt sei jedoch gleich genannt, denn er wird uns am Ende wieder begegnen: Die Fiat-Shamir-Transformation ist beweisbar sicher nur im sogenannten Zufallsorakel-Modell – einer idealisierten Annahme, dass die Hashfunktion sich perfekt wie ein Zufallsorakel verhält. Reale Hashfunktionen tun das nur näherungsweise. In der Praxis funktioniert die Konstruktion hervorragend, aber sie ist eine Heuristik, kein lückenloser mathematischer Beweis – und genau an dieser Nahtstelle sind schon spektakuläre Implementierungsfehler passiert.

Teil 6: Die Skalierungsrevolution – zk-SNARKs und zk-STARKs

Die GMW-Beweise für ganz NP hatten einen Haken, der sie jahrzehntelang praktisch nutzlos machte: Sie waren riesig und langsam. Um eine komplexe Aussage zu beweisen, musste man das zugehörige Problem in einen gewaltigen Graphen übersetzen und über viele Runden Unmengen von Commitments austauschen. Der Beweis konnte um Größenordnungen umfangreicher sein als die Aussage selbst. Für „Ich kenne einen Schlüssel" ging das; für „Diese komplette Berechnung mit Millionen von Schritten wurde korrekt ausgeführt" war es undenkbar.

Der Durchbruch, der Zero-Knowledge von einer akademischen Kuriosität in eine Milliardenindustrie verwandelte, kam mit einer neuen Klasse von Konstruktionen ab etwa 2012: den zk-SNARKs. Das Akronym steht für Zero-Knowledge Succinct Non-interactive ARgument of Knowledge – und jedes Wort darin ist ein Versprechen. Succinct („knapp") ist das Herzstück: Der Beweis ist winzig – oft nur wenige hundert Byte – und in Millisekunden prüfbar, und zwar völlig unabhängig davon, wie riesig und langwierig die zugrunde liegende Berechnung war. Man kann beweisen, dass ein Programm mit Milliarden Rechenschritten korrekt lief, und dieser Beweis ist ein paar hundert Byte groß und in Sekundenbruchteilen verifiziert. Diese Eigenschaft – ein konstant kleiner, blitzschnell prüfbarer Beweis für beliebig große Berechnungen – ist die eigentliche Revolution. Non-interactive heißt: es ist ein einziges Dokument, kein Dialog (per Fiat-Shamir-artigen Methoden). Argument of Knowledge heißt: Die Korrektheit gilt nur gegen Betrüger mit begrenzter Rechenleistung (ein „Argument" statt eines absoluten „Beweises"), und der Beweisende demonstriert echtes Wissen eines geheimen Eingangs (des Witness).

Der theoretische Boden dafür wurde 2012 unter anderem in einer Arbeit gelegt, an der der Berkeley-Professor Alessandro Chiesa beteiligt war; kurz darauf machte das Projekt Zcash (Start 2016) die Technologie berühmt. Zcash ist eine Kryptowährung, die zk-SNARKs nutzt, um Transaktionen vollständig zu verschleiern: Ein Beweis belegt, dass eine Transaktion nach allen Regeln gültig ist – der Absender besitzt die Münzen, gibt nicht mehr aus, als er hat, niemand fälscht Geld –, ohne Absender, Empfänger oder Betrag preiszugeben. Das ist die GMW-Vision von 1986, endlich praktisch: eine beliebig komplexe Gültigkeitsaussage, bewiesen ohne die geheimen Details.

Doch zk-SNARKs haben einen empfindlichen Preis: das Trusted Setup. Viele SNARK-Konstruktionen benötigen einmalig eine Zeremonie, in der geheime Zufallsparameter erzeugt werden, um die öffentlichen „Beweisschlüssel" zu bilden. Die dabei entstehenden geheimen Zwischenwerte müssen anschließend unwiderruflich vernichtet werden – man nennt sie treffend „toxic waste" (Giftmüll). Denn wer diese Werte behält, kann falsche Beweise fälschen, die jeder Prüfer akzeptiert – im Fall einer Währung: aus dem Nichts Geld schöpfen, ohne dass es je auffiele. Zcash begegnete dem mit aufwendigen Multi-Party-Zeremonien („The Ceremony"), bei denen viele unabhängige Teilnehmer je einen Bruchteil des Geheimnisses beisteuern und vernichten; solange auch nur ein Teilnehmer ehrlich seinen Anteil löscht, bleibt das System sicher. Dennoch ist das Trusted Setup eine Vertrauensannahme, die man lieber los wäre – ein Fremdkörper in einer Technologie, die eigentlich Vertrauen überflüssig machen soll.

Genau hier setzen die zk-STARKs an, 2018 von Eli Ben-Sasson und Kollegen eingeführt. Das „T" steht für Transparent: STARKs brauchen kein Trusted Setup und damit keinen Giftmüll. Ihre Beweise stützen sich allein auf Hashfunktionen und öffentlich bekannten Zufall. Das bringt zwei weitere strategische Vorteile. Erstens sind sie mutmaßlich post-quantum-sicher: Weil sie nur auf der Kollisionsresistenz von Hashfunktionen beruhen (und nicht auf Faktorisierung oder diskretem Logarithmus, die Shors Quantenalgorithmus bräche), gelten sie als resistent gegen künftige Quantencomputer. Zweitens skalieren sie noch besser für gigantische Berechnungen. Der Preis: STARK-Beweise sind deutlich größer als SNARK-Beweise – Größenordnung zehn bis hundert Kilobyte statt einiger hundert Byte. Es ist der klassische kryptografische Kompromiss: Man tauscht die unbequeme Vertrauensannahme des Setups und die Quantenanfälligkeit gegen einen größeren Beweis ein. Ich bin der Meinung, dass sich hier eine allgemeine Faustregel des Feldes zeigt, die Sven aus anderen Sicherheitsentscheidungen vertraut vorkommen dürfte: Man bekommt selten alles zugleich – Beweisgröße, Prüfgeschwindigkeit, Setup-Freiheit und Quantenresistenz stehen in Spannung, und welchen Punkt im Raum man wählt, ist eine Architektur-, keine reine Mathematikentscheidung.

Teil 7: Wohin die Beweise wandern – reale Anwendungen

Die Theorie ist elegant, doch der eigentliche Grund, warum Zero-Knowledge heute in aller Munde ist, liegt in einer Handvoll Anwendungen, die von der Nische in die Breite drängen.

Die erste und älteste ist die finanzielle Privatheit. Zcash war der Anfang; heute nutzt eine ganze Familie von Protokollen Zero-Knowledge, um Zahlungen vertraulich zu machen, ohne die Prüfbarkeit der Regeln aufzugeben. Der konzeptionelle Gewinn ist paradox schön: Ein öffentliches, für jeden einsehbares Register kann zugleich vollständig privat sein – jeder kann prüfen, dass alle Transaktionen gültig sind, aber niemand sieht ihren Inhalt.

Die zweite und wirtschaftlich derzeit wohl bedeutendste Anwendung ist die Skalierung von Blockchains durch sogenannte zk-Rollups. Das Problem: Ein Netzwerk wie Ethereum kann nur eine begrenzte Zahl von Transaktionen pro Sekunde verarbeiten, weil jeder Knoten jede Transaktion nachrechnen muss. Die Idee des zk-Rollups: Man bündelt Tausende von Transaktionen außerhalb der Hauptkette („off-chain"), führt sie dort aus und erzeugt einen einzigen zk-SNARK/STARK-Beweis, der belegt, dass die gesamte Stapelverarbeitung korrekt war. Nur dieser winzige Beweis (plus der neue Zustand) wird auf die Hauptkette geschrieben. Die Hauptkette muss nicht mehr tausende Transaktionen nachrechnen, sondern nur einen kleinen Beweis prüfen – in Millisekunden. Genau hier zahlt sich die Succinctness der SNARKs in barer Münze aus: Ein konstant kleiner Beweis steht für beliebig viel Rechenarbeit. zk-Rollups gehören zu den meistgehandelten Skalierungslösungen der Ethereum-Welt und verschieben Milliardenwerte.

Die dritte Anwendung berührt Sven vielleicht am unmittelbarsten, weil sie ins Feld von Identität und Datenschutz-Compliance reicht: der selektive Nachweis von Attributen. Ein Zero-Knowledge-Beweis kann belegen „Ich bin über 18", ohne das Geburtsdatum zu nennen; „Ich wohne in der EU", ohne die genaue Adresse; „Mein Gehalt liegt über der Kreditschwelle", ohne die Zahl. Diese Idee der datensparsamen Berechtigungsnachweise ist die technische Verkörperung des Datenschutzprinzips der Datenminimierung aus der DSGVO. Die im Aufbau befindliche europäische EUDI-Wallet (European Digital Identity Wallet) sieht Zero-Knowledge-artige Verfahren ausdrücklich vor, um genau solche selektiven, unverkettbaren Nachweise zu ermöglichen. Statt bei jeder Alterskontrolle einen vollständigen Ausweis herzuzeigen, legt man einen Beweis vor, der ausschließlich die eine relevante Tatsache belegt – nicht mehr.

Eine vierte, im Kryptosektor schmerzhaft aktuell gewordene Anwendung ist der Solvenznachweis (proof of solvency / proof of reserves). Nach spektakulären Zusammenbrüchen von Kryptobörsen wuchs der Wunsch, dass eine Börse beweisen kann: „Meine Reserven decken alle Kundeneinlagen" – ohne die vollständige Bilanz, die Kundenliste oder die genauen Beträge offenzulegen. Zero-Knowledge-Beweise erlauben genau diese Gratwanderung zwischen Transparenz und Vertraulichkeit.

Und die Grenze wandert weiter. Aktuelle Forschung überträgt Zero-Knowledge auf maschinelles Lernen (zkML): Man will beweisen können, dass ein bestimmtes KI-Modell eine bestimmte Ausgabe wirklich erzeugt hat – etwa dass eine Kreditentscheidung tatsächlich von dem geprüften Modell stammt –, ohne die geheimen Modellgewichte offenzulegen. Für Svens Berührungsfläche zwischen KI-Engineering und IT-Sicherheit ist das ein besonders reizvoller Ausblick: die Verifizierbarkeit einer KI-Berechnung, entkoppelt von der Preisgabe des Modells.

Teil 8: Die Fallstricke – wo Zero-Knowledge in der Praxis bricht

So mächtig die Technik ist, so gnadenlos bestraft sie Fehler in der Umsetzung – und die Geschichte der letzten Jahre ist reich an lehrreichen Unfällen. Wer Zero-Knowledge einsetzt, muss mindestens vier Klippen kennen.

Die erste und häufigste ist das schwache Fiat-Shamir. Erinnere dich: Die Sicherheit der nicht-interaktiven Transformation hängt daran, dass die selbstgehashte Challenge wirklich alle relevanten Werte umfasst – insbesondere das Commitment und die vollständige öffentliche Aussage. Vergisst ein Implementierer, einen dieser Werte in den Hash einzubeziehen (das sogenannte „weak Fiat-Shamir"), so entsteht ein Spielraum, in dem ein Angreifer die Aussage nachträglich zurechtbiegen kann, um zu einem gefälschten Beweis zu passen. Genau dieser Fehler wurde in den letzten Jahren in einer erschreckenden Zahl real eingesetzter Bibliotheken und Blockchain-Systeme gefunden – eine subtile Auslassung mit potenziell katastrophalen Folgen, weil sie die Korrektheit still aushebelt, ohne dass irgendetwas sichtbar bricht. Ich bin der Meinung, dass dies exemplarisch für eine tiefere Wahrheit der angewandten Kryptografie steht: Die gefährlichsten Fehler sind nicht die, bei denen etwas nicht funktioniert, sondern die, bei denen alles scheinbar funktioniert und nur die Sicherheitsgarantie heimlich verloren ging.

Die zweite Klippe ist das schon erwähnte Trusted Setup der SNARKs. Wird der „toxic waste" nicht zuverlässig vernichtet – oder war die Setup-Zeremonie kompromittiert –, kann der Inhaber der Geheimwerte beliebige falsche Beweise fälschen, und niemand würde es je bemerken, denn die Fälschungen sind mathematisch ununterscheidbar von echten Beweisen. Das ist eine besonders tückische Vertrauensannahme, weil ihr Bruch unsichtbar bleibt. Die Antwort der Praxis sind aufwendige Multi-Party-Zeremonien und, wo möglich, der Umstieg auf setup-freie Konstruktionen (STARKs oder neuere transparente SNARKs).

Die dritte Klippe ist die rechnerische statt absolute Sicherheit. Das „A" in SNARK – Argument – ist kein Zufall. Viele moderne Systeme sind nur gegen Angreifer mit begrenzter Rechenleistung sicher; ihre Korrektheit ruht auf denselben zahlentheoretischen Härteannahmen (diskreter Logarithmus, elliptische Kurven), die ein hinreichend großer Quantencomputer brechen würde. Wer langlebige Garantien braucht, muss die post-quantum-Frage von Anfang an mitdenken – ein weiterer Grund für das wachsende Interesse an den hash-basierten STARKs.

Die vierte, oft unterschätzte Klippe ist die schiere Komplexität der Systeme – halb im Scherz „moon math" genannt. Ein zk-SNARK-System besteht aus vielen Schichten: der Übersetzung des Problems in ein arithmetisches Schaltnetz („Circuit"), dem Polynom-Commitment-Verfahren, der Fiat-Shamir-Transformation, der konkreten Implementierung in endlicher Arithmetik. Jede Schicht kann Fehler bergen, und ein Fehler in einer davon – ein falsch modelliertes Constraint im Circuit, ein Off-by-one in der Feldarithmetik – kann die gesamte Sicherheitsgarantie aushebeln, während das System bei normalem Gebrauch tadellos zu funktionieren scheint. Genau deshalb sind formale Verifikation und spezialisierte Audits von Zero-Knowledge-Schaltkreisen zu einem eigenen, schnell wachsenden Teilgebiet der Sicherheitsforschung geworden. Für die Praxis heißt das: Zero-Knowledge ist keine Zutat, die man einfach „darüberstreut", sondern ein System, dessen Sicherheit nur so stark ist wie seine schwächste, subtilste Schicht.

Erkenntnis zum Mitnehmen

Der Kerngedanke des Zero-Knowledge-Beweises lässt sich in einem Satz fassen: Überzeugung und Information sind trennbar – man kann jemanden vollständig von der Wahrheit einer Aussage überzeugen, ohne ihm irgendetwas anderes als eben diese Wahrheit mitzuteilen. Was zunächst wie ein Paradox klingt, wird durch drei Zutaten möglich: Interaktion, Zufall und das Simulator-Argument, das „nichts lernen" mathematisch dingfest macht, indem es fordert, dass sich das ganze Gespräch ohne jede Geheimniskenntnis fälschen lässt.

Die eigentlich übertragbare Lehre steckt aber im Bogen von 1985 bis heute. Eine tiefe theoretische Frage – „Kann man Wissen quantifizieren und von Beweisen entkoppeln?" – führte über GMWs universelles „alles in NP", die Fiat-Shamir-Brücke zur Signatur und schließlich die succinct-Revolution der SNARKs und STARKs zu einer Technologie, die private Zahlungen, die Skalierung von Ethereum und datensparsame digitale Ausweise trägt. Für Svens Arbeit im Schnittfeld von IT-Sicherheit, Cloud und KI ist die praktisch wichtigste Botschaft vielleicht diese: Zero-Knowledge verschiebt die alte Sicherheitsfrage von „Wem muss ich vertrauen?" zu „Was kann ich beweisen?". Wo bisher ein System, eine Behörde oder ein Anbieter als vertrauenswürdig vorausgesetzt wurde, kann künftig ein kurzer Beweis diese Voraussetzung ersetzen – Vertrauen wird durch Verifizierbarkeit ablösbar. Zugleich mahnt die Geschichte der schwachen-Fiat-Shamir-Fehler zur Demut: Die Garantie ist nur so gut wie ihre subtilste Implementierungsschicht, und gerade weil ein gebrochenes Zero-Knowledge-System nach außen tadellos aussieht, ist Sorgfalt hier keine Kür, sondern die eigentliche Ingenieursleistung.

Reflexionsfrage

Zero-Knowledge trennt zwei Dinge, die wir intuitiv für untrennbar halten: jemanden zu überzeugen und ihm etwas zu verraten. Wo in deinen eigenen Systemen und Prozessen verlangst du heute noch die volle Preisgabe von Daten – den kompletten Ausweis, die ganze Bilanz, den exakten Wert –, obwohl in Wahrheit nur eine einzige abgeleitete Tatsache geprüft werden müsste („älter als 18", „genug Deckung", „innerhalb der Grenze")? Und was würde sich an deiner Architektur, deinen Datenschutz-Risiken und deinen Vertrauensannahmen ändern, wenn du diese Fragen konsequent als „Was muss ich beweisen?" statt als „Welche Daten muss ich sehen?" formulieren würdest?

Querverweise im Vault

Quellen

Hinweis: Dieser Artikel gibt den überprüfbaren, wissenschaftlich gesicherten Stand wieder. Wo eigene Einschätzungen einfließen, sind sie mit „Ich bin der Meinung, dass ..." gekennzeichnet.

← All articles