a16z veröffentlicht Lattice Jolt: 3-mal schnellere Beweise und Schutz vor Quantenangriffen

Autor: a16z crypto

Übersetzung: Deep Tide TechFlow

Deep Tide Einführung: zkVM wurde immer wieder vorgeworfen, „Beweise zu langsam und zu groß“ zu erzeugen. a16z ersetzt diesmal elliptische Kurven durch gitterbasierte Kryptographie und macht die Beweiserstellung direkt dreimal schneller und drückt die Beweisgröße unter 100 KB. Dies ist derzeit die einzige post-quantenresistente Lösung, die bei der Geschwindigkeit traditionelle elliptische Kurven schlagen kann, mit direkten Auswirkungen auf die Kosten der On-Chain-Verifizierung und datenschutzfreundliche Anwendungen.

Heute veröffentlichen wir offiziell Lattice Jolt, die neueste Version unserer Open-Source-zkVM (Zero-Knowledge Virtual Machine). Jolt war bereits die schnellste und einfachste zkVM, und seine Architektur bleibt unverändert. Aber die zugrunde liegende Kryptographie wurde ausgetauscht: von elliptischen Kurven zu gitterbasierter Kryptographie. Diese eine Änderung bringt gleichzeitig drei Dinge:

• Jolt wird post-quantensicher.
• Die Geschwindigkeit von Prover und Verifier steigt um das 2-3-fache.
• Lattice Jolt hat die kürzesten Beweise aller post-quanten-zkVMs: derzeit unter 100 KB, mit weiterem Komprimierungspotenzial. Beweise müssen on-chain und über Netzwerke übertragen werden; je kleiner der Beweis, desto geringer die Verifizierungskosten.

Diese Eigenschaften decken alle Anwendungsfälle der zkVM ab. Derselbe Prover kann auf einer GPU Milliarden von CPU-Zyklen verarbeiten und auf einem Smartphone Millionen von Zyklen beweisen. In beiden Fällen schreiben Entwickler normale Programme, ohne Schaltkreise von Hand erstellen zu müssen, die Spezialwissen erfordern. Deshalb nennen wir Jolt einen „Allzweck-SNARK“.

Die größere Geschichte ist jedoch die Bedeutung von Lattice Jolt für das Design und die Einführung von SNARKs. Fast alle derzeit in Produktion befindlichen post-quanten-SNARKs basieren auf Hashes. Lattice Jolt beweist, dass gitterbasierte SNARKs schneller und kompakter sein können. Digitale Signaturen durchlaufen denselben Wandel: Hash-Verfahren sind die konservative Wahl, aber Gitterverfahren sind das, was die Welt in großem Maßstab einsetzt. Wir erwarten, dass SNARKs denselben Weg gehen werden; die zweite Hälfte dieses Blogbeitrags erklärt, warum.

Elliptische Kurven durch Gitter ersetzen

Jolts bisheriges Polynomial-Commitment-Schema hieß Dory und war die einzige Komponente des Systems, die auf elliptischer Kurvenkryptographie beruhte. Lattice Jolt ersetzt Dory durch Akita, ein völlig neues Polynomial-Commitment-Schema, das auf der Module-SIS-Gitterannahme basiert. Lattice Jolt stützt sich auf diese standardisierte, gut erforschte Annahme und zielt auf volle 128-Bit-Sicherheit ab.

Module-SIS und sein Bruder Module-LWE gehören zur selben Annahmenfamilie, auf die die digitale Infrastruktur der Welt derzeit migriert. Diese Annahmen untermauern nicht nur den Signaturstandard ML-DSA, sondern auch den Schlüsselaustauschstandard ML-KEM, der bereits das am weitesten verbreitete post-quanten-Primitiv weltweit ist.

Die Entwicklung und Implementierung von Akita wurde von Forschern und Ingenieuren bei LayerZero geleitet, unter Beteiligung von Forschern der Carnegie Mellon University, der University of Southern California sowie unserem Engineering- und Forschungsteam bei a16z crypto.

Warum Lattice Jolt schneller ist

Lattice Jolt ist nicht nur post-quantensicher, sondern auch schneller als die ersetzte Version mit elliptischen Kurven.

Die Beschleunigung hat einen einfachen Grund. Elliptische Kurven zwingen Jolt, in einem 256-Bit-Körper zu arbeiten, während Gitterkryptographie dasselbe Sicherheitsniveau in einem 128-Bit-Körper erreicht. Die Hauptarbeit des Jolt-Provers besteht in der Multiplikation von Körperelementen (im Wesentlichen die Multiplikation sehr großer Zahlen). Wenn sich die Zahlengröße halbiert, wird jede Multiplikation um ein Vielfaches schneller.

Jolt mit Dory war bereits schnell: Unser letztes Leistungsupdate zeigte, dass Jolt auf einem Laptop etwa 700.000 RISC-V (RV64IMAC)-Zyklen pro Sekunde beweisen konnte. Spätere Optimierungen brachten die Kurvenversion von Jolt auf über eine Million Zyklen pro Sekunde.

Lattice Jolt beweist auf derselben Maschine über zwei Millionen Zyklen pro Sekunde.

In den letzten sechs Monaten haben wir nicht nur Akita entwickelt und in Jolt integriert, sondern auch die Jolt-Codebasis von Grund auf neu geschrieben. Jolt lief bereits gut auf GPUs, aber diese Neufassung macht die GPU-Implementierung einfacher zu bauen und zu optimieren.

Das erste Ergebnis ist eine Apple-Metal-Implementierung, die Apple-Hardware eine enorme Beschleunigung bringt. (Metal ist Apples Framework zur Ausführung von Code auf den in MacBooks und iPhones integrierten GPUs.)

• GPU-beschleunigtes Lattice Jolt beweist auf einem MacBook über 10 Millionen RV64IMAC-Zyklen pro Sekunde.
• Reines CPU-Lattice Jolt beweist auf derselben Maschine über 2 Millionen Zyklen pro Sekunde.
• Sogar die Kurvenversion von Jolt erreicht auf einem MacBook mit Metal jetzt etwa 4 Millionen Zyklen pro Sekunde.

Das heißt, eine einzige Veröffentlichung hat Jolt auf dem MacBook von etwa 1 Million Zyklen pro Sekunde (Kurvenversion, reine CPU) auf über 10 Millionen Zyklen pro Sekunde (Gitterversion, mit Metal) gesteigert.

Um diese Zahlen in Kontext zu setzen: Als wir vor vier Jahren erstmals über den Overhead von SNARK-Provern schrieben, war der Beweis einer Berechnung millionenfach teurer als ihre direkte Ausführung. Lattice Jolt reduziert diesen Overhead auf etwa das Zehntausendfache. Das ist noch nicht das Ende; es bleibt Spielraum für Optimierungen auf Engineering- und Protokollebene.

Die Beweisgröße ist ebenso wichtig wie die Prover-Geschwindigkeit. Mit unter 100 KB sind die Beweise von Lattice Jolt bereits deutlich kleiner als die anderer post-quanten-zkVMs, deren Beweise von über 200 KB bis etwa 600 KB oder mehr reichen.

Durch den Wechsel auf Gitter verbessert sich auch der ohnehin schon hervorragende Speicherverbrauch von Jolt weiter: Der Speicherbedarf des Provers sinkt von etwa 300 Byte pro Zyklus auf 200 Byte. Das bedeutet, dass man Millionen von RISC-V-Zyklen auf einem Smartphone beweisen kann.

Ein begleitendes Paper wird in Kürze veröffentlicht und Lattice Jolt um Zero-Knowledge-Eigenschaften erweitern, die für datenschutzfreundliche Anwendungen erforderlich sind.

Warum Gitter statt Hashes

Jahrelang konzentrierte sich die Aufmerksamkeit der SNARK-Community (und praktisch alle Produktionsimplementierungen) auf hashbasierte SNARKs als Weg zur Post-Quanten-Sicherheit.

Es gab jedoch auch eine kontinuierliche Forschungslinie zu Gitter-SNARKs und Gitter-Commitments, darunter LaBRADOR, Greyhound, LatticeFold, SuperNeo und Akitas direkter Vorgänger Hachi. Lattice Jolt baut auf dieser Forschung auf, bringt die Gitter-Commitment-Schicht in eine leistungsstarke zkVM-Architektur und beweist gleichzeitig, dass gitterbasierte SNARKs in Geschwindigkeit und Kompaktheit unübertroffen sind.

Das sollte nicht überraschen. Wie bereits erwähnt, hat sich dasselbe Muster bei digitalen Signaturen bereits abgespielt.

Kryptographen haben Signaturen auf der Grundlage vieler Annahmen konstruiert. Hash-Signaturen gelten allgemein als die konservativste Wahl: Ihre Sicherheitsannahmen sind einfach und alt. Aber die Welt setzt hauptsächlich auf Gittersignaturen, weil sie kürzer und schneller sind:

• ML-DSA-Signaturen sind etwa einige KB groß.
• Die von NIST standardisierte Hash-Alternative SLH-DSA ist um ein Vielfaches größer.
• Für Verschlüsselung und Schlüsselaustausch ist die Lage noch eindeutiger: Es gibt überhaupt keine Hash-Option (es ist bewiesen, dass dies unmöglich ist), und die Post-Quanten-Bereitstellung basiert überwiegend auf Gittern. ML-KEM (der wichtigste Schlüsselaustauschstandard, den NIST 2024 festgelegt hat) wird bereits standardmäßig in gängigen Browsern und Messaging-Apps eingesetzt und in einer großen Zahl von TLS-Verbindungen im Internet verwendet.

Die Analogie zwischen SNARKs und Signaturen ist nicht oberflächlich. Eine digitale Signatur ist im Wesentlichen ein Wissensbeweis des privaten Schlüssels für eine autorisierte Nachricht. SNARKs erweitern dieses Paradigma von einer schmalen Aussage auf beliebige Berechnungen. Es wäre daher seltsam, wenn sich die langfristige kryptographische Landschaft der SNARKs völlig von der der Signaturen und Verschlüsselung unterscheiden würde.

Hier gilt es auch ein Missverständnis zu klären: Hash-SNARKs werden oft als konservative Post-Quanten-Wahl bezeichnet, weil „sie nur auf Hash-Funktionen beruhen“. Das stimmt nur, wenn die zugrunde liegende Hash-Funktion nicht-algebraisch ist.

Heutzutage stützen sich die meisten hashbasierten SNARK-Implementierungen auf SNARK-freundliche algebraische Hash-Konstruktionen (wie Poseidon), um die korrekte Auswertung des Hashes kostengünstig zu beweisen. Dies ist besonders wichtig für Rekursion (hier bedeutet Rekursion, zu beweisen, dass man einen gültigen SNARK-Beweis besitzt). Diese Konstruktionen haben mehr Struktur als Standard-Hash-Funktionen, und ihre Kryptoanalyse ist noch nicht ausgereift.

Kurz gesagt, wir haben kein Vertrauen in die Sicherheit algebraischer Hash-Funktionen. Dennoch werden sie heute in Produktions-SNARK-Systemen weit verbreitet eingesetzt. (Es gibt jedoch ein positives Signal: Die Ethereum Foundation hat kürzlich angekündigt, sie nicht mehr zu verwenden.)

Algebraische Hashes sind nicht die einzige versteckte Annahme in eingesetzten hashbasierten SNARKs: Viele Systeme haben in der Vergangenheit spekulative Proximity-Gap-Schranken verwendet, um konkrete Sicherheitsniveaus festzulegen, anstatt vollständig bewiesene Schranken zu nutzen. Einige der als am stärksten geltenden Schranken erwiesen sich später als falsch.

Selbst wenn man die oben genannten spekulativen hashbasierten SNARKs vermeidet, liegt ihr Sicherheitsziel oft unter 128 Bit, weil volle 128-Bit-Sicherheit erhebliche Leistungseinbußen mit sich bringt. Warum? Hashbasierte SNARKs können in einem 128-Bit-Körper keine 128-Bit-Sicherheit erreichen, weil ihr Soundness-Fehler mit n/|F| skaliert, wobei n ungefähr die Größe der bewiesenen Aussage und |F| die Körpergröße ist. Daher verliert man beim Beweis einer Aussage mit einer Milliarde Schritten in einem 128-Bit-Körper etwa 30 Bit Sicherheit, sodass man unter 100 Bit fällt. Im Gegensatz dazu skaliert der Soundness-Fehler von Lattice Jolt mit log(n)/|F| und behält im selben Körper nahezu die volle 128-Bit-Sicherheit (der kleine log(n)-Verlust kann mit Standardtechniken ausgeglichen werden).

Ironischerweise stützen sich einige Systeme, die als „konservative“ Post-Quanten-Wahl beworben werden, tatsächlich gleichzeitig auf algebraische Hash-Funktionen, spekulative Proximity-Gap-Schranken und Sicherheitsziele unter 128 Bit. Hashbasierte SNARKs sind daher zwar eine wichtige Richtung, aber nicht automatisch die risikoarme Option, für die viele sie halten.

Ein Jolt, drei Grundlagen: Kurven, Gitter und Hashes

Wir waren schon immer der Meinung, dass Jolt nicht an eine einzige kryptographische Grundlage gebunden sein sollte. Wir sollten ausgereifte und leistungsstarke SNARKs auf der Basis von Kurven, Hashes und Gittern haben. Unterschiedliche Annahmen und Leistungsmerkmale eignen sich für unterschiedliche Szenarien.

Wenn man jedoch digitale Signaturen als Referenz nimmt, werden gitterbasierte SNARKs die am weitesten verbreitete Post-Quanten-Wahl werden.

Jolt ist in diesem Wandel außergewöhnlich gut positioniert. Das ursprüngliche Jolt-Design nutzte Eigenschaften elliptischer Kurven, die für Commitments besonders nützlich sind, darunter schnelle Commitments für dünn besetzte Vektoren. Gitter-Commitments haben dieselbe Eigenschaft: Wenn die meisten Einträge eines Vektors null oder klein sind, ist das Commitment kostengünstig, und Jolt committet fast ausschließlich solche Vektoren. Diese Eigenschaft ermöglichte es uns, Dory durch Akita zu ersetzen, während der Rest von Jolt unverändert blieb.

Wir werden eine hashbasierte Version von Jolt bauen. Im Vergleich zu kurven- und gitterbasiertem Jolt ist die hashbasierte Version jedoch weniger speichereffizient, erzeugt größere Beweise und bringt verschiedene Komplexitätsprobleme mit sich. Das liegt daran, dass die vielversprechendsten hashbasierten SNARKs in binären Körpern arbeiten. Dieses Zahlensystem erleichtert den Beweis von Hash-Auswertungen, passt aber nicht zur Arithmetik der CPU. Diese Diskrepanz macht den Beweis gewöhnlicher CPU-Multiplikationen teuer. Dennoch sollte das Ökosystem unter jeder wichtigen Annahmenfamilie über zkVMs verfügen, genau wie im Bereich der digitalen Signaturen.

Allzweck-SNARK

Lattice Jolt erfüllt auf einen Schlag alle Anforderungen von Entwicklern an eine zkVM: post-quantensicher, transparent, schnell, kompakt und speichereffizient. Es bringt die Gitter-SNARK-Forschungslinie von LaBRADOR bis Hachi in eine produktionsreife zkVM, ohne dabei die Vorteile aufzugeben, die Jolt ursprünglich schnell gemacht haben.

Unser Ziel ist es nicht nur, die leistungsstärkste zkVM als Open Source für jedermann verfügbar zu machen, sondern auch die Notwendigkeit, SNARKs für bestimmte Anwendungen von Hand zu optimieren, weitgehend zu beseitigen. Das erfordert nicht, dass Jolt genauso schnell ist wie handoptimierte Prover. Das wäre ein unmögliches Ziel, so als würde man verlangen, dass eine CPU bei jeder Aufgabe mit speziellen ASICs mithalten kann. Es erfordert nur, dass Jolt schnell genug ist, um eine akzeptable Benutzererfahrung zu bieten.

Für „kleine“ Aussagen im Zusammenhang mit Client-seitigen Beweisen (wo handoptimierte Schaltkreise heute dominieren) ist das entscheidende Kriterium, Beweise auf einem Smartphone in etwa einer Sekunde oder weniger zu erzeugen. Jolt ist bereits nahe daran, dies zu erreichen, und zahlreiche Beschleunigungsansätze sind in Arbeit.

Das Zeitalter der Gitter-SNARKs ist angebrochen.