Authenticated Zero Knowledge Database

Ausgangslage

Zero Knowledge Virtual Machines (zkVMs) ermöglichen es, die Korrektheit der Ausführung von Programmcode zu beweisen, ohne dass die Eingaben in das Programm offengelegt werden müssen. Die Technologie hat sich in den letzten Jahren rasant entwickelt, wobei sie sich aktuell immer noch in einem frühen Entwicklungsstadium befindet. Im Internet finden sich vielerlei Beispiele für einfache Programme wie beispielsweise das Berechnen von Fibonacci Zahlen. Betreffend der Anwendung in komplexen Use Cases gibt es jedoch nur wenige Beispiele, und es sind noch viele Fragen offen.

Problemstellung

Das Ziel der Projektarbeit ist, verschiedene zkVMs anhand der gewählten Use Cases in Bezug auf deren Performance zu vergleichen. Im Rahmen der Projektarbeit soll hierzu eine einfache, zweckmässige Datenbank entwickelt werden, welche autorisierten Benutzern erlaubt, die Daten einzufügen, zu löschen und zu bearbeiten. Für die Interaktion mit der Datenbank sollen hierbei Beweise mittels einer zkVM generiert werden, um die Korrektheit der Ausführung zu beweisen.

Abfragen der Zero Knowledge Database
                            
                        

                            Die entwickelte Zero Knowledge Database (zkDB) erlaubt es, lesende Abfragen oder schreibende
                            Abfragen auszuführen und
                            für jede Operation einen Beweis zu generieren, welcher die Korrektheit der Operation
                            beweist. Hierbei wird im Resultat
                            der Abfrage so wenig Information wie möglich offengelegt. Beispielsweise bei der
                            Volljährigkeitsprüfung eines bestimmten
                            Benutzers antwortet die zkDB einzig mit «Ja» oder «Nein». Das konkrete Geburtsdatum des
                            Benutzers wird nicht
                            offengelegt. Die Client-Applikation kann die Antwort anhand des Beweises verifizieren,
                            welcher von der zkDB mit jedem Resultat mitgeliefert wird.

                        
Architektur
                            
                        

                            Bei der Architektur handelt es sich um ein Client-Server-Modell, bei welchem die zkDB als
                            Server agiert und bei welchem
                            der Client in Form einer CLI realisiert wurde. In beiden Applikationen kommt hierbei eine
                            zkVM zum Einsatz, wobei diese
                            in der Serverapplikation genutzt wird, um Beweise für die Korrektheit der Datenbankoperation
                            zu erzeugen, und im Client,
                            um diese Beweise zu verifizieren.
                        
Verifizierbarer Datenbank Zustand
                            
                        

                            Die Datenbank führt eine Aufzeichnung aller historischen Datenbankzustände, welche erlaubt,
                            den Zustand der Datenbank
                            fortlaufend zu verifizieren. Für den Übergang von einem Zustand zum nächsten muss vom Client
                            ein Beweis verifiziert
                            werden, welcher den korrekten Übergang des Zustands beweist. Das einzige vom Client
                            erbrachte Vertrauen, im Vertrauen
                            des Root-Users, welcher die Datenbank initialisiert hat.

                            Der Datenbankzustand besteht hierbei aus den Fingerabdrücken intern genutzter
                            authentifizierter Datenstrukturen sowie
                            aus Hash-Pointern zum vorherigen Zustand und zum Beweis des Zustandsübergangs.
                        

Ergebnisse

Die Arbeit evaluierte die beiden Zero Knowledge Virtual Machines SP1 und RISC0 anhand einer eigens entwickelten Zero Knowledge Database (zkDB) für Personendaten. Die zkDB ermöglicht es berechtigten Benutzern, Daten zu verwalten, und bietet zwei öffentliche, verifizierbare Abfragen zur Volljährigkeits- und Nationalitätsprüfung. Alle Abfragen und Zustandsänderungen werden durch kryptographische Beweise abgesichert, sodass Clients die Korrektheit nachvollziehen können, ohne sensible Daten offenzulegen.

Während dem die durch die zkDB generierten Beweise in der Regel in unter 100 Millisekunden verifiziert werden können, dauert die Erzeugung der Beweise deutlich länger. Bei lesenden Operationen auf der zkDB beträgt die Erzeugungszeit 15-30 Sekunden, während schreibende Operationen 1-2 Minuten in Anspruch nehmen. Besonders zeitintensiv ist hierbei die Signaturprüfung. Somit lässt sich sagen, dass zkVMs für Applikationen, welche den Anspruch haben, Abfragen innert weniger Sekunden oder sogar in Echtzeit zu beantworten, aktuell noch ungeeignet sind. Für Applikationen, welche hingegen einen hohen Wert auf die Verifizierbarkeit der Resultate oder die Vertraulichkeit der Informationen legen, ist der Einsatz von zkVMs trotz der langen Ausführungszeiten durchaus eine Option.

Technische Schlüsselbegriffe

Zero Knowledge ProofEin kryptographisches Verfahren, welches erlaubt dass eine Partei (Prover) eine anderen Partei (Verifier), davon zu überzeugen, dass sie eine geheime Information besitzt, ohne die Information an sich preiszugeben.
Zero Knowledge Virtual MachineEine virtuelle Machine, welche beim Ausführen von Berechnungen Beweise erzeugt. Anhand der erzeugten Beweise ist es möglich, die Korrektheit der Ausführung nachzuvollziehen, ohne dass die Eingaben offen gelegt werden müssen.
Authentifizierte Datenstrukturen Datenstrukturen, bei welchen für lesende oder schreibende Operationen ein kryptografischer Beweis erbracht wird, welches erlaubt die Korrektheit der Operation zu verifizieren.

Kunde

Projekt des Instituts für Mobile und Verteilte Systeme der FHNW

Studenten

Noé Brehm, Tobias Maier

Betreuer
Markus Knecht
Daniel Kröni