Die Evaluierung von Hash-Funktionen bestimmt in modernen Zero-Knowledge-Beweis-Systemen – insbesondere im Kontext von Ethereum-Post-Quanten-Roadmaps und zkEVM-Architekturen – die Prover-Laufzeit. Der neu vorgestellte Ragged Multi-Instance GKR (kurz Ragged-GKR) reduziert die Laufzeit und den Speicherbedarf erheblich, indem er mehrere ungleich große Poseidon2b-Hash-Regionen ohne physisches Max-Padding aggregiert. Der Ansatz liefert messbare Verbesserungen bei Prover- und Verifier-Zeit, Transkriptgröße und physischer Zeilenanzahl, ohne die kryptographische Sicherheit zu beeinträchtigen.

Grundlagen des GKR-Protokolls und Sumcheck über binären Turmfeldern

Das GKR-Protokoll, benannt nach Goldwasser, Kalai & Rothblum (2008), erweitert das klassische Sumcheck-Protokoll, um geschichtete arithmetische Schaltkreise mit logarithmischer Komplexität in Bezug auf die Schaltkreistiefe zu verifizieren. In Systemen wie FROST-GKR und Binius kommen binäre Turmfelder (GF(2 ¹²⁸ ) bzw. GF(2 ²⁵⁶ )) zum Einsatz. Diese Felder lassen sich dank nativer SIMD-Befehle (AVX2, VPCLMULQDQ, PMULL) äußerst effizient auf Standard-CPUs verarbeiten.

• GKR-Verifikationskomplexität: O(d log S) (d = Tiefe, S = Größe) – Quelle: Goldwasser et al., 2008.
• Reduktion der Constraint-Sumchecks in FROST-GKR von 472 auf 2 (2026) durch Bündelung von Poseidon2b-Schaltkreisen in einen globalen Trace.

Diese mathematischen Grundlagen erklären, warum das Zusammenfassen mehrerer GKR-Walks die Transkriptgröße drastisch reduziert und SIMD-Instruktionen optimal ausnutzt.

Ragged Multi-Instance GKR: Konzept und mathematische Eleganz

Der Kern des Ragged-GKR-Ansatzes liegt in der Kombination aus klassischer GKR-Schaltkreisreduktion und einer impliziten Polynomevaluierung auf dem booleschen Hyperkubus. Für jede Region a mit Boolean-Breite wₐ wird ein Selektorpolynom definiert:

χₐ(x) = ∏_{j = wₐ}^{W-1} (1 + x_j)

Hierbei ist W die maximale Breite über alle Regionen. In Charakteristik 2 (binäre Turmfelder) entspricht das Selektor-Polynom 1 + x_j; in ungeraden Charakteristiken müsste es zu 1 - x_j geändert werden, was die Feld-Arithmetik und den Grad des Sumchecks beeinflusst.

Durch das implizite Selektor-Polynom werden unvollständige Dimensionen algebraisch ausgeblendet, ohne physische Witness-Zeilen zu erzeugen. Das Sumcheck-Protokoll faltet die tatsächlich vorhandenen Koordinaten regulär und führt die restlichen Dimensionen über reine Selektor-Aktualisierungen fort. Dadurch bleibt die lineare Prover-Komplexität proportional zur echten Witness-Größe und nicht zur ungünstigsten Max-Dimension.

Performance-Resultate

Die Benchmark-Ergebnisse (Intel Core i7-1365U, 12-Thread, 2026) vergleichen drei Varianten: neun unabhängige native-Width-Walks, ein physisch max-gepaddeter Walk und den impliziten Ragged-Walk.

• Prover-Medianzeit: 10,83 s (Ragged) vs. 17,61 s (unabhängig) – Faktor 1,63 schneller; vs. 43,50 s (physisches Padding) – Faktor 4,02 schneller.
• Verifier-Medianzeit: 0,80 s (Ragged) vs. 4,90 s (unabhängig) – Faktor 6,11 schneller.
• Algebraisches Transkript: 363 264 Byte (Ragged) vs. 2 272 512 Byte (unabhängig) – um den Faktor 6,26 kleiner.
• Physische Witness-Zeilen: 360 448 Zeilen (Ragged) vs. 1 179 648 Zeilen (max-Padding) – Reduktion um das 3,27-fache.
• Peak-Arbeitsspeicher: 450 MiB (Ragged) vs. 163 MiB (unabhängig) vs. 1,32 GiB (max-Padding).

Der Ragged-Walk erzeugt ein Transkript, das in Größe und Verifikationszeit deutlich effizienter ist, während er gleichzeitig den physischen Speicherbedarf auf ein praktikables Niveau reduziert – ein entscheidender Kompromiss für rechenintensive Aggregationsaufgaben im Konsensbereich.

Relevanz für Ethereums Post-Quanten-Roadmap und leanVM

Im Rahmen der Ethereum-Post-Quanten-Roadmap (Strawmap) sollen konsensrelevante BLS-Signaturen durch hash-basierte Post-Quanten-Signaturen ersetzt werden. Bei der rekursiven Aggregation solcher Beweise in Umgebungen wie leanVM dominieren Poseidon- und Poseidon2-Hashes die Rechenlast. Benchmarks zeigen, dass Poseidon2-Merkle-Hashing bis zu 58 % der GPU-Zeit in modernen ZK-Prover-Implementierungen (WHIR, Apple Silicon) ausmacht (2024).

Durch die Reduktion der Transkriptgröße und die Beschleunigung von Prover- und Verifier-Phasen ermöglicht Ragged-GKR eine speicherschonende Batching-Strategie, die exakt zu den Anforderungen der Post-Quanten-Migration passt. Die Methode ist zudem allgemein anwendbar, weil sie nicht an die Poseidon2b-Permutation gebunden ist, sondern das Batching ungleicher Instanz-Domänen unterstützt.

Risiken und Gegenüberstellungen

• Höherer Peak-Arbeitsspeicherbedarf: Die simultane Ragged-Aggregation benötigt etwa 450 MiB, während sequenzielle unabhängige Walks nur 163 MiB benötigen. Auf stark speicherbeschränkten Clients kann dies ein kritischer Faktor sein.
• Spezifische Bindung an Charakteristik 2: Der Selektor nutzt die Formel 1 + x_j. Bei einer Migration zu Primfeldern (z. B. Goldilocks oder KoalaBear) muss das Selektor-Polynom zu 1 - x_j angepasst werden, was die Feld-Arithmetik und den Grad des Sumchecks beeinflusst.

Häufig gestellte Fragen (FAQ)

Was unterscheidet ‚Ragged GKR‘ von herkömmlichem Max-Padding?Beim physischen Max-Padding werden kleinere Datenblöcke künstlich mit Null-Zeilen auf die Größe der größten Region (2^W) aufgefüllt, was Speicher und Prover-Laufzeit aufbläht. Ragged GKR verwendet stattdessen ein implizites Selektor-Polynom χ(x)=∏(1+x_j), das unvollständige Dimensionen algebraisch ausblendet, ohne physische Witness-Zeilen zu erzeugen.Warum gewinnt die Nutzung von binären Turmfeldern an Bedeutung?Binäre Turmfelder über GF(2 ¹²⁸ ) ermöglichen die Ausnutzung von bitweisen SIMD-Instruktionen moderner Prozessoren (AVX2, VPCLMULQDQ, ARM NEON). Dadurch lassen sich Sumcheck-Operationen und Hash-Evaluierungen mit deutlich höherer Durchsatzrate berechnen als in klassischen Primfeldern.

Fazit

Der Ragged Multi-Instance GKR stellt einen bedeutenden Fortschritt für die Optimierung von Zero-Knowledge-Beweisen dar. Durch das implizite Selektor-Polynom wird das aufwändige physische Padding vermieden, was zu einer 6-fach kleineren Transkriptgröße, einer 6-fach schnelleren Verifikation und einer bis zu 4-fach schnelleren Prover-Zeit führt. Gleichzeitig bleibt der Speicherbedarf im akzeptablen Bereich, selbst wenn er im Vergleich zu rein sequenziellen Walks höher ist. Im Kontext von Ethereums Post-Quanten-Roadmap und der leanVM-Architektur ist Ragged-GKR besonders relevant, weil es die dominierenden Poseidon-Hash-Kosten adressiert und damit einen praktischen Weg zur effizienten, speicherschonenden Aggregation von Post-Quantum-Beweisen bietet.