Beweisbasierte Allzweckverarbeitung mit Magnetar

Überblick

• Eine neue Form der Berechnung. Zero-Knowledge-Beweise ermöglichen es Ihnen, eine Arbeit zu durchführen und neben dem Ergebnis ein kurzes Beweisdokument zu erhalten, das zeigt, dass das Programm korrekt ausgeführt wurde. Jeder kann das Beweisdokument in Millisekunden überprüfen, ohne das Programm erneut auszuführen, ohne den Ausführer des Programms zu vertrauen und ohne Daten zu benötigen, auf die das Programm ausgeführt wurde.
• Drei große Herausforderungen haben die breite Verbreitung behindert: die Beweise schnell genug zu erzeugen, sie für normale Programme ohne kryptografisches Wissen zugänglich zu machen, und sie auf einer Kryptographie zu basieren, die noch viele Jahrzehnte in Zukunft vertrauenswürdig bleibt.
• Der Magnetar hat große Fortschritte in allen drei Herausforderungen erzielt. Es zeigt, dass Programme, die in Rust, Go oder C geschrieben sind, im Durchschnitt 10 bis 39 Mal schneller laufen als die vorherigen schnellsten vergleichbaren Systeme. Die Sicherheit des Systems beruht ausschließlich auf standardmäßigen Hashfunktionen. Dies ist das neueste Ergebnis von mehr als einem Jahrzehnt an Forschungen am Microsoft Research, die darauf abzielen, Zero-Knowledge-Proofs praktisch zu machen.

Eine neue Form der Berechnung

Jeder Ergebnis, den ein Computer erzeugt, enthält eine implizite Frage: Hat das Programm wie behauptet funktioniert und korrekte Ausgaben ergeben? Heute erfordert die Beantwortung dieser Frage oft ein gewisses Maß an Vertrauen sowie Verifizierung. Wir vertrauen dem Operator, dem Anbieter, der Gegenpartei oder dem Agenten, und wir verlassen uns auf Verträge, Audits und Logs, um dieses Vertrauen zu begründen.

Zero-Knowledge-Beweise bieten eine grundlegend andere Herangehensweise bei der Ermittlung von Vertrauen. Ein Programm läuft und erzeugt zusammen mit seinem Ausgangswert ein kurzes Beweisstück, ein kryptografisches Zertifikat, das bestätigt, dass dieses Programm unter diesen Eingaben dieses Ergebnis ergeben hat. Das Beweisstück ist klein und schnell zu überprüfen. Jeder, der es erhält, kann das Ergebnis in Millisekunden bestätigen, ohne das Programm erneut auszuführen, und kann das Beweisstück an jede andere Person weitergeben, die dieselbe Gewissheit benötigt. Mit der Zero-Knowledge-Eigenschaft enthüllt die Beweisung auch nichts über Eingaben, die geheim gehalten werden sollten.

Das verändert, was Korrektheit im wirklichen Leben bedeutet. Ein Ergebnis muss nicht mehr aufgrund der Person, die es erstellt hat, vertraut werden. Es kann überprüft werden, weil es Beweise gibt. Ein KI-Agent, der im Namen einer Person handelt, könnte einen Beweis liefern, dass jede Aktion den vorgegebenen Regeln entspricht. Regulierten Finanzinstitutionen könnten beweisen, dass Transaktionen korrekt verarbeitet wurden, ohne ihre Transaktionen öffentlich zu machen. All das wird möglich, sobald das Erstellen eines Beweises so routine ist wie das Ausführen des Programms.

Drei große Herausforderungen

Zerkezahlungsbeweise wurden in den 1980er Jahren erfunden, und die Ideen hinter der Beweisführung der Programmausführung existieren seit fast ebenso langer Zeit. Was sie daran hindert, zu einem allgemeinen Werkzeug zu werden, sind drei Herausforderungen, die gleichzeitig unlösbar bleiben.

Effizienz. Die Erstellung einer Proof hat historisch gesehen Millionenmal mehr Rechenarbeit erfordert als das Ausführen des Programms selbst. Jahre der Forschung haben diesen Aufwand verringert, aber die schnellsten Systeme erreichen ihre Geschwindigkeit durch Kompromisse an anderen Stellen.

Allgemeichkeit und Nutzbarkeit. Viele Beweissysteme erfordern, dass Entwickler ihre Programme manuell als kryptografischen Kreislauf umschreiben müssen, was eine feste arithmetische Beschreibung dieser genauen Berechnung darstellt. Dies dauert Monate. Jede Änderung an der Anwendung bedeutet einen neuen Kreislauf, und die Übersetzung selbst ist eine häufige Quelle für Sicherheitsfehler. Eine allgemeine Alternative besteht darin, die Ausführung eines gewöhnlichen Prozessors zu beweisen, sodass jedes kompilierte Programm als geschrieben bewiesen werden kann. Bis vor kurzem kam diese Allgemeichkeit mit einem hohen Preis in Bezug auf Geschwindigkeit oder Sicherheit.

Sicherheit. Eine Überzeugung ist nur so stark wie die darunterliegende Kryptografie. Viele Überzeugungssysteme basieren auf Elliptikkurven, die von einem ausreichend leistungsfähigen Quantencomputer gebrochen werden können. Microsoft behebt dieses Problem mit seinem Quantum Safe Programm, das seine Produkte und Dienstleistungen in post-quantitative Kryptografie versetzt – ein Ziel, das es kürzlich auf 2029 vorverlegt hat. Post-quantitative Überzeugungssysteme existieren bereits, doch einige basieren auf latticebasierten Annahmen, und die meisten auf neuen kryptografischen Funktionen, die entwickelt wurden, um die Kosten der Beweisführung zu reduzieren. Diese neuen kryptografischen Funktionen haben nicht die jahrzehntelange Prüfung erfahren, die der heutigen Internet-Kryptografie zuteil wird, und einige basieren auf mathematischen Vermutungen über Fehlerkorrekturcodes, die noch nicht bewiesen sind. Sie haben ihre Geschwindigkeit auf starken Annahmen beruhen lassen.

Podcast-Serie

Die Form der kommenden Dinge

Teilen Sie sich mit Doug Burger von Microsoft und Gästen die grundlegenden Wahrheiten über Künstliche Intelligenz und wie diese die Zukunft verändern wird.

Mehr als ein Jahrzehnt an Arbeit

Seit mehr als einem Jahrzehnt arbeitet Microsoft Research daran, Zero-Knowledge-Proofs und verifizierbare Computing praktisch zu machen. Die frühe Forschung verfolgte zwei Ansätze, die beide nur für kleine Programme praktikabel waren. Der erste (öffnet in neuem Tab) (öffnet in neuem Tab) ermöglicht es einem Verifier, eine lange Berechnung durch ein kurzes Gespräch mit dem Prover mittels einer Technik namens das Summenprüfungsprotokoll (öffnet in neuem Tab) zu überprüfen, doch dies galt nur für Berechnungen mit einer bestimmten strukturierten Schichtung. Der zweite (öffnet in neuem Tab) (öffnet in neuem Tab) verwendete Elliptische-Kurven-Kryptografie, um sehr kleine Beweise für fast alle Berechnungen zu erstellen. Doch dies erfordert eine einmalige vertrauenswürdige Einrichtung, die geheime Informationen beinhaltet, die, falls verloren gehen, es jedem ermöglichen könnten, Beweise zu fälschen. Dieser Ansatz ist auch anfällig für Quantencomputer.

Im Jahr 2019 kehrte ein neues Zero-Knowledge-Proof-System namens Spartan zum Ansatz der Summenprüfung zurück und machte ihn für allgemeine Programme ohne vertrauenswürdige Einrichtungen nutzbar. Spartan kann außerdem mit verschiedenen kryptografischen Bausteinen instanziiert werden. Diese Flexibilität ermöglichte später, dass das Proof-System allein auf Hashfunktionen basiert. Eine Reihe von Ergebnissen füllte anschließend die verbleibenden Punkte aus:

• Phalanx (öffnet sich in neuem Tab), im Jahr 2021, zeigte, wie man durch Wiederholungen ausnutzen kann – beispielsweise wenn ein Prozessor jeden Schritt mit demselben Instruktionszyklus ausführt – um Berechnungen um eine Größenordnung schneller als Spartan zu machen. Die Beschreibung des Prozessors von Magnetar basiert auf dieser Idee.
• Nova (öffnet in neuem Tab), HyperNova (öffnet in neuem Tab), NeutronNova (öffnet in neuem Tab), Neo und SuperNeo (öffnet in neuem Tab) zeigten, dass es praktisch ist, Spartan frühzeitig zu stoppen und die Teilergebnisse zusammenzufassen, um Berechnungen jeglicher Größe zu einem deutlich geringeren Kostenaufwand zu beweisen.
• Brakedown (öffnet sich in neuem Tab) führte im Jahr 2021 ein schnelles, hash-basiertes Commit-System ein und kombinierte es mit Spartan, wodurch die erste Spartan-Variante entstand, deren Sicherheit auf standardmäßigen Hashfunktionen beruht.
• Spice (öffnet in neuem Tab), Lasso (öffnet in neuem Tab), Nebula (öffnet in neuem Tab) und anschließend Twist and Shout (öffnet in neuem Tab) machten die Speicheroperationen im Kern eines allgemein verwendbaren Prozessors kostengünstig, und Jolt (öffnet in neuem Tab) zeigte, dass ihre Kombination mit Spartan effizient die Ausführung eines vollständigen Prozessors bewiesen werden kann.
• Anfangs dieses Jahr Vega (öffnet in neuem Tab) wandte diese Methode auf die digitale Identität an und bewieste Fakten aus einer Regierungsbescheinigung in unter einem Zehntel von einer Sekunde.
• Vor kurzem hat BinarySpartan (öffnet sich in neuem Tab) Spartan in binäre Bereiche gebracht, wo die Logik eines Prozessors und standardisierte Hash-Funktionen effizient ausgedrückt werden können. BinarySpartan verwendet auch Ligerito (öffnet sich in neuem Tab), ein Brakedown-Stil-Commit-Schema mit viel kürzeren Beweisen, sowie Ring-Switching (öffnet sich in neuem Tab), das es ermöglicht, auf Vektoren von Bits zu committen.

Jeder dieser Schritte löste einen Teil des Problems. Der Magnetar ist der Ort, an dem die Teile zusammenkommen.

Magnetar

Magnetar ist eine zero-knowledge-Virtuallinie oder zkVM, und es macht gleichzeitig große Fortschritte in allen drei Herausforderungen.

Es ist allgemeinverwendbar. Magnetar beweist die Ausführung von RISC-V, einer offenen Prozessorarchitektur mit erfahrenen Kompressoren für alle gängigen Programmiersprachen. Ein Entwickler schreibt ein Programm in Rust, Go oder C, kompiliert es wie gewohnt und Magnetar beweist die Ausführung genau so, wie es geschrieben ist. Betrachten Sie, was das praktisch bedeutet: Eine Unternehmensstrategie, ein Datenpfad oder ein Interpreter für die Ethereum Virtual Machine (EVM) sind schließlich nur Programme – und die Ingenieure, die sie bereits betreuen, können ihre Ausführung genau so beweisen, wie es vorgesehen ist. Dadurch wird das Beweisen nicht mehr eine spezialisierte Tätigkeit sein.

Es ist schneller als die vorherigen Systeme derselben Klasse. Magnetar zeigt eine Geschwindigkeit von 7,2 bis 8,7 Millionen Prozessoranweisungen pro Sekunde auf einem Laptop. In 15 Benchmark-Programmen – von kryptografischen Hashschenken bis zu Token-Übertragungen innerhalb eines kleinen EVM-Interpreters – ist es im Durchschnitt 10 bis 39 Mal schneller als die schnellsten existierenden zkVMs auf derselben Maschine, und mehr als 300 Mal schneller als zwei andere Systeme bei einem Token-Übertragungs-Benchmark. Ein optimiertes Magnetar erreicht 9,5–12,8 Millionen Zyklen pro Sekunde, was die hier berichtete Geschwindigkeitssteigerung um etwa 1,3× erhöht. Seine Beweise werden in etwa 12 Millisekunden abgeschlossen.

Seine Sicherheit beruht auf Standardkryptografie. Magnetar verwendet eine Standard-Hashfunktion wie SHA-256 oder SHA-3 – dieselben Prinzipien, die bereits alle Organisationenssysteme schützen. Es werden keine Elliptikkurven, keine Lattice, keine speziellen Hashfunktionen, keine vertrauenswürdige Einrichtungen und keine unbeweisten Annahmen bezüglich Fehlerkorrekturcodes verwendet. Hashfunktionen sind die am besten erforschten Prinzipien im kryptografischen Toolkit und bilden die Grundlage der stateless-hashbasierten Signatur, die von NIST als eigene konservative post-quantum-Option standardisiert wurde. Für ein System, das in den kommenden Jahrzehnten immer noch vertrauenswürdig sein muss, entfernt die Verwendung nur von Standard-Hashfunktionen eine kryptografische Migration aus dem Plan.

Die gleiche Designentscheidung bringt eine zweite Vorteile mit sich. Die Überprüfung einer Magnetar-Beweisführung besteht hauptsächlich darin, standardisierte Hashfunktionen und binäre Feldrechnungen zu bewerten – genau die Operationen, die Magnetar effizient bewiesen kann. Die Verifizierung einer Beweisführung ist daher eine gewöhnliche Aufgabe für ihn. Dadurch kann Magnetar Berechnungen jeder Größe beweisen, indem er sie in Teile aufteilt und anschließend zusammenführt. Zudem ermöglicht dies es Magnetar, auch langfristige Systeme wie Ledger oder Blockchain zu beweisen.

Der technische Artikel enthalten das vollständige Design, die Sicherheitsanalyse und die Messungen.

Blick in die Zukunft

Magnetar bringt Zero-Knowledge-Beweise und verifizierbare Computing auf eine Stufe, auf der sie auf der Kryptografie basieren können, der Organisationen bereits vertrauen – und zu einer Geschwindigkeit, die für Ingenieure, die normale Code schreiben, nutzbar ist. Magnetar ermöglicht eine Zukunft, in der kryptografische Beweise ein Routineprodukt der Berechnung sind. Wir erwarten, dass Technologieführer aufhören werden zu fragen… Ob Beweise für die Ausführung praktisch sind und konzentrieren sich stattdessen auf die Ergebnisse würden Sie bevorzugen es, zu überprüfen, anstatt Vertrauen einzugehen.

Wenn Sie interessiert sind, zu erfahren, wie Zero-Knowledge-Beweise Ihren Anwendungsfall unterstützen können, würden wir gerne von Ihnen hören (öffnet sich in einem neuen Tab).