Zero-Knowledge-Protokoll: Was Sie über zk-SNARK wissen sollten

Foto: Nomad Soul – shutterstock.com

Unter den Zero-Knowledge-Protokollen nimmt zk-SNARK (Zero-knowledge succinct non-interactive argument or knowledge) eine Sonderrolle ein – es ist das populärste. Weil Zero-Knowledge-Systeme die Art und Weise, wie Authentifizierung funktioniert, revolutionieren könnten, gewinnen sie zunehmend an Bedeutung, während sie sich stetig weiterentwickeln. Die Mathematik, die hinter diesen Systemen und Protokollen steht, ist zwar anspruchsvoll – die grundlegenden Ideen aber einfach zu verstehen.

Zero Knowledge – Definition

Zero Knowledge lässt sich allgemein als Versuch definieren, die kleinstmögliche Menge an Informationen zu verwenden, um eine Aussage zu überprüfen. Dabei geht es darum Be-, beziehungsweise Nachweise zu entwickeln, die die Übertragung zusätzlicher Daten unnötig machen.

Der Grundstein für Zero Knowledge wurde mit dem Forschungspapier “Knowledge Complexity of Interactive Proof Systems” (PDF), das in den 1980er Jahren in mehrfacher Auflage erschien. Die Abhandlung befasst sich grob gesagt damit, wie sich Wissen (Knowledge) “verhält”, wenn es Aussagen interagierender Systeme beweisen muss. Dabei baut die Arbeit der Wissenschaftler von MIT und University of Toronto auf dem Schaffen von Stephen Cook und seiner bahnbrechenden Publikation “The Completeness of Theorem Proving Procedures” (PDF) aus dem Jahr 1971 auf, die den Bereich der Komplexitätstheorie in der Informatik inspirierte. Cook versuchte, die Komplexität von Algorithmen explizit zu untersuchen und zu begrenzen.

Zero Knowledge und Authentifizierung

Eine Authentifizierung lässt sich als Beweis im oben genannten Sinne auffassen. Wenn Softwaresysteme miteinander kommunizieren und eine Partei eine Behauptung aufstellt, stellt sich die Frage, wie diese Behauptung gegenüber den anderen Parteien bewiesen werden kann. Zero Knowledge untersucht, wie das vonstatten geht und schlägt alternative Methoden vor. Ziel ist, damit die Wissenslecks zu reduzieren und so die Sicherheit des gesamten Systems zu verbessern.

Bei einem naiven Ansatz kann ein System zum Beispiel behaupten, ein Passwort zu kennen. Um den Beweis darüber zu erbringen, kann das Kennwort einfach übertragen werden. Zero-Knowledge-Protokolle versuchen hingegen, den Beweis mit einem Minimum an Wissen zu erbringen – ohne (in diesem Beispiel) das Passwort selbst zu offenbaren. Diese Zero-Knowledge-Proofs (Beweise) basieren auf Wahrscheinlichkeiten.

Interaktive Beweise erfordern einen ständigen Dialog zwischen Prüfer und Verifizierer. Jede korrekte Antwort erhöht das Vertrauen des Verifizierers in die Behauptung des Beweisführers (und verringert die Wahrscheinlichkeit, dass der Beweisführer lügt). Bei zk-SNARK liegt die Innovation nun darin, dass dieser Dialogprozess in einem sicheren Paket gekapselt ist, das einmal vom Beweisführer zum Verifizierer übermittelt werden kann. Letzterer kann danach mit dem Beweis selbst interagieren – es handelt sich also um nicht-interaktive Beweise.

Nicht-interaktive Proofs wurden erstmals 1988 im Rahmen der Forschungsarbeit “Non-interactive Zero-Knowledge” (PDF) demonstriert. In dieser Arbeit wurde die Möglichkeit aufgezeigt, Zero-Knowledge-Beweise in einem nicht-interaktiven Format zu kapseln. Im Jahr 2012 folgte dann das Forschungspapier “From Extractable Collision Resistance to Succinct Non-Interactive Arguments of Knowledge, and Back Again” (PDF), in dessen Rahmen SNARKs vorgestellt wurden. Diese Grundidee wird seither schrittweise verfeinert und umgesetzt.

zk-SNARK – Implementierungen

Betrachtet man die SNARK-Idee als konzeptionelle Spezifikation, ist die erste (fast) praktische Implementierung das 2013 vorgestellte Pinocchio-Protokoll (PDF). Es beschreibt ein Schema für öffentlich überprüfbare Berechnungen beschrieben, bei dem nicht vertrauenswürdige Rechenressourcen zur Bestätigung der Ausführung von Funktionen verwendet werden können. Diese Idee wurde in “Succinct Non-Interactive Zero Knowledge for a Von Neumann Architecture” (PDF) weiter ausgearbeitet.

Ein Blick in diese Arbeiten lässt zk-SNARK wie ein undurchdringliches, mathematisches Dickicht wirken. Und in der Tat stehen dahinter beeindruckende geistige Leistungen, die Diffie-Hellman-ähnliche, intuitive Sprünge beinhalten. Die Komplexität von zk-SNARK wird noch dadurch verstärkt, dass es eine Neuheit ist, an deren Theorie noch gearbeitet wird. Implementierungen sind dabei ein besonders aktiver Bereich, da die Grundlagen abstrahiert und dann in Bibliotheken verpackt werden, die auf spezifische Anwendungen und Anwendungsfälle ausgerichtet sind. Diese Use Cases tun sich auf, während zk-SNARK in freier Wildbahn mit funktionierenden Systemen getestet wird.

Die Anwendungsfälle und die Softwaresysteme, die sie unterstützen, sind hier von übergeordnetem Interesse. Zunächst jedoch ein Einblick in die Funktionsweise des Zero-Knowledge-Protokolls – ohne dabei zu tief in Mathematik abzutauchen.

zk-SNARK – Funktionsweise

zk-SNARK prüft im Grunde genommen, ob eine Berechnung stattgefunden hat. Dazu wird die ursprüngliche Berechnung (zum Beispiel eine Funktion) durch eine Reihe mathematischer Transformationen in einem ganz bestimmten Format ausgedrückt. Dieses endgültige Format ist das eigentliche zk-SNARK-Format, das verwendet werden kann, um zu beweisen, dass die Berechnung mit dem gegebenen Input stattgefunden hat (der Input wird von zk-SNARK als “Zeuge” bezeichnet, weil er verwendet werden kann, um zu beweisen, dass die Berechnung mit diesem Argument stattgefunden hat). Zu dieser Anordnung sind zwei Bemerkungen angebracht:

1. erfordert die Anordnung für viele Anwendungen, wie etwa den Besitznachweis eines Passworts, dass die gewünschte Behauptung zunächst in ein funktionales Äquivalent umgewandelt wird. Im Falle eines Passworts kann dieses zum Beispiel im Klartext durch einen Hashing-Algorithmus laufen. Dann muss nur noch bewiesen werden, dass der Hash-Algorithmus mit dem Passwort verglichen wurde, was dem Besitznachweis des Passworts gleichkommt.

2. eröffnet die Art der überprüfbaren Berechnungen ein neues Modell der Datenverarbeitung, das über die einfache Authentifizierung von Aussagen hinausgeht. Dieses Modell ermöglicht die Auslagerung von Berechnungen an die Ressourcen Dritter, selbst in einer Trustless-Umgebung, da die Ressource die Ausführung kryptografisch nachweisen kann.

Das hat erhebliche Auswirkungen auf Blockchains, denn anstatt Transaktionen durch die Übertragung der tatsächlichen Informationen zu verifizieren, können sie zk-SNARKs verwenden, um nur den Beweis zu übertragen. Das MINA-Protokoll ist ein Beispiel für eine Blockchain, die dieses Konzept verfolgt. Berechnungen auf diese Weise auszulagern, kann auch außerhalb der Blockchain Anwendung finden, indem eine Art Marktplatz für Berechnungen geschaffen wird. Dazu sind keine vertrauenswürdigen Drittorganisationen erforderlich (heute in der Regel Cloud-Anbieter verschiedener Art).

Die Transformationen, die SNARK verwendet, nachdem die Aussage als Funktion formuliert wurde, folgen diesem allgemeinen Muster (aus Vitalik Buterins Papier zur quadratischen Arithmetik): die ursprüngliche Berechnung -> algebraischer Schaltkreis -> Rank 1 Constraint System (R1CS) -> quadratisches arithmetisches Programm (QAP) -> lineares PCP -> linearer interaktiver Proof -> zkSNARK. Eine leicht verständliche Darstellung des gesamten Prozesses finden Sie in “The Why and How of zk-SNARK” (PDF). Eine weitere gute Quelle für zk-SNARK und Zero Knowledge im Allgemeinen ist dieser Blog.

Der entscheidende Trick von zk-SNARK besteht darin, die Berechnung in eine polynomiale Form zu bringen. In diesem Format kann die Berechnung bewiesen werden, indem man nach Punkten auf dem Graphen der Polynome sucht. Das heißt: Die Lösungen des Polynoms (und nicht das Polynom selbst) werden dazu verwendet, zu überprüfen, ob der Beweisführende tatsächlich im Besitz des Proofs ist. Der erste Teil der Transformationen ist also für die Umwandlung einer Funktion in eine mathematische Form verantwortlich (algebraischer Schaltkreis -> R1CS), dann für die Umwandlung in ein Polynom (QAP), dann die Umwandlung in eine Form, die effizient überprüfbar ist (linearer PCP -> linearer interaktiver Beweis) und schließlich für eine übertragbare Form: den SNARK selbst. Das ist heute der Hauptansatz, um Zero-Knowledge-Proofs in einer nicht-interaktiven Form zu kapseln.

zk-SNARK – Use Cases

Neben dem Potenzial, Blockchains für verifizierbare Berechnungen einzusetzen, können zk-SNARKs eine Authentifizierung im Stil von Zero Knowledge unterstützen – sowohl in Bezug auf die Bereitstellung von Anmeldedaten als auch im weiteren Sinne für die Erstellung von Aussagen. Zum Beispiel die Behauptung, dass der Benutzer ein Bankkonto über einen bestimmten Betrag besitzt (dies würde eine Interaktion mit der Bank als Drittpartei erfordern).

Durch die Verwendung von zk-SNARKs ist eine Art anonyme Authentifizierung möglich: Der Benutzer kann nachweisen, dass er zum Zugriff auf eine Ressource berechtigt ist und zwar einfach aufgrund einer Tatsache, die er besitzt und nicht aufgrund seiner Identität. Ein solcher Mechanismus erhöht die Systemsicherheit, indem er den Umfang des Wissens, das bei Authentifizierungsaktivitäten ausgetauscht wird, begrenzt.

Schließlich ist es möglich, mit zk-SNARK vollständig anonyme Zahlungssysteme zu implementieren. Eine Transaktion kann fortgesetzt werden, indem verfügbare Gelder überprüft werden, sichergestellt wird, dass sie auf einem Treuhandkonto liegen, die Lieferung von Waren überprüft wird und der Vertrag abgeschlossen wird – ohne dass dabei die Identität einer der beiden Parteien preisgegeben wird. (fm)

Dieser Beitrag basiert auf einem Artikel unserer US-Schwesterpublikation CSO Online.