Protocols for Univariate Sumcheck

1. Problemstellung und Motivation

In der Welt der SNARKs (Succinct Non-Interactive Arguments of Knowledge) werden Daten typischerweise als Polynome kodiert. Es gibt zwei Hauptansätze zur Darstellung dieser Daten:

1. Multilineare Erweiterungen (mlex): Daten werden als multilineare Polynome über dem Booleschen Hyperwürfel kodiert.
2. Univariate Erweiterungen (unex): Daten werden als univariate Polynome über Einheitswurzeln (Roots of Unity) kodiert.

Das zentrale Problem liegt in der Effizienz des Sumcheck-Protokolls, einem Kernbaustein für die Verifizierung von Summen über Polynome:

• Das multivariate Sumcheck-Protokoll (LFKN) ist für den Prover sehr effizient (lineare Laufzeit in der Anzahl der Variablen), erfordert aber viele Runden ($m$ Runden für $m$ Variablen) und ist verifizierungsintensiv.
• Das standardmäßige univariate Sumcheck-Protokoll (z. B. Aurora) benötigt nur eine Runde und ist verifizierungsfreundlich, hat aber oft eine schlechtere Prover-Effizienz oder ist nicht direkt auf lineare Laufzeit skalierbar.

Bisherige Ansätze („Adaptors"), um multivariate Techniken auf univariate Polynome anzuwenden (z. B. Gemini), waren entweder nicht linear in der Laufzeit oder erforderten aufwendige Basis-Übersetzungen (Koeffizienten zu Werten und zurück). Die Frage war: Gibt es ein univariates Sumcheck-Protokoll, das die Prover-Effizienz des multivariaten Protokolls erreicht, ohne die Vorteile der Univariate-Domäne (wenige Runden, geringe Bandbreite) zu verlieren?

2. Methodik und Kernbeiträge

Der Autor stellt drei neue Ansätze vor, die alle darauf abzielen, univariate Sumcheck-Aufgaben mit linearer Prover-Laufzeit ($O(m)$ oder $O(2^m)$ im Kontext der Polynomgröße) zu lösen.

A. Reduktion von mlex zu unex (Abschnitt 3)

Dieser Ansatz ermöglicht die Anwendung des standardmäßigen multivariaten Sumcheck-Protokolls auf univariate Orakel.

• Methode: Ein rekursives „Square Evaluation Folding". Das Protokoll nutzt eine Zerlegung des univariaten Polynoms $f$ in einen „quadratischen" Teil ($f_{sq}$) und einen „nicht-quadratischen" Teil ($f_{no}$), basierend auf der Eigenschaft $f(x) = f_{ev}(x^2) + x f_{od}(x^2)$.
• Funktionsweise: Der Prover sendet Orakel für diese Teile. Der Verifizierer prüft die Konsistenz mittels einer verallgemeinerten Lagrange-Interpolationsformel an einem zufälligen Punkt. Dies erlaubt es, die Auswertung eines multilinearen Polynoms $mlex[v]$ über ein univariates Orakel $unex[v]$ zu beweisen.
• Vorteil: Im Vergleich zu früheren Methoden (wie Kernel-Interpolation oder Quotienten-Ansätzen) ist dies linear in der Prover-Laufzeit und vermeidet Basis-Übersetzungen.

B. Direkte univariate Sumcheck-Protokolle (Abschnitt 4)

Der Autor analysiert und korrigiert existierende Ideen (insbesondere das DGM-Protokoll von Drake, Gabizon und Meckler) und entwickelt zwei direkte Reduktionen auf das Gemini-Protokoll.

1. Korrigiertes DGM-Protokoll (Protocol 3):

   • Das ursprüngliche DGM-Protokoll enthielt einen Fehler in der Grad-Prüfung und der Konsistenz der Polynome.
   • Der Autor korrigiert dies durch eine explizite Interpolation und Grad-Checks, die sicherstellen, dass die Polynome korrekt gefaltet werden.
   • Dies reduziert die Domain-Identität auf das Gemini-Protokoll, ist jedoch weniger effizient als der direkte Ansatz.

2. Direkte Reduktion (Protocol 4):

   • Dies ist der effizienteste und einfachste Ansatz.
   • Idee: Nutzung der Identität $f(w^i) = \text{mlin}[f](w^i, w^{2i}, \dots, w^{2^{m-1}i})$. Das univariate Polynom wird direkt als multilineares Polynom interpretiert, wobei die Eingaben die Potenzen der Einheitswurzel sind.
   • Ablauf: Das Protokoll führt einen klassischen multivariaten Sumcheck durch, wobei die „Variablen" durch die Potenzen $w^i$ ersetzt werden. Nach $m$ Runden bleibt eine Auswertungsbehauptung für ein multilineares Polynom übrig, die direkt mit Gemini verifiziert wird.
   • Effizienz: Die Prover-Laufzeit ist $O(\binom{d+q}{q} d 2^m)$, was der Effizienz des standardmäßigen multivariaten Sumchecks entspricht, aber direkt auf univariate Daten angewendet wird.

C. Rundenreduktion (Round Reduction)

Ein wichtiger Beitrag ist die Möglichkeit, die Anzahl der Runden von $m$ auf $O(\log m)$ oder sogar $O(\sqrt{m})$ zu reduzieren, während die lineare Prover-Laufzeit erhalten bleibt.

• Mechanismus: Das Protokoll wird nach $k$ Runden gestoppt. Die verbleibende Behauptung ist ein kleineres univariates Sumcheck-Problem, das mit einem einstufigen Protokoll (wie Aurora) gelöst wird.
• Besonderheit: Im Gegensatz zu früheren Arbeiten (z. B. HybridPlonk) ist dieser Übergang nahtlos und erfordert keine zusätzlichen Basis-Übersetzungen.
• Optimierung: Durch eine Verallgemeinerung der Kronecker-Substitution (Abschnitt 4.3, Remark 4) kann die Anzahl der Runden auf $O(\sqrt{m})$ gesenkt werden, indem die Variablen in Blöcken gefaltet werden.

3. Ergebnisse und Leistungsdaten

Die Ergebnisse werden in Tabelle 2 des Papers zusammengefasst und im Vergleich zum Standard-Aurora-Ansatz bewertet:

• Prover-Laufzeit: Alle vorgeschlagenen Protokolle erreichen eine lineare Laufzeit in Bezug auf die Polynomgröße ($O(2^m)$), was ein Durchbruch für univariate Systeme ist.
• Runden:
  • Standard-Ansatz: $m$ Runden.
  • Mit Rundenreduktion: $O(\log m)$ Runden (mit Aurora als Abschluss) oder $O(\sqrt{m})$ Runden (mit der verallgemeinerten Faltung).
• Kommunikation:
  • Protocol 4 (Direkte Reduktion) ist in der Kommunikation effizienter als die Kombination aus multivariatem Sumcheck + Adapter (Protocol 2), da Gemini weniger Orakel sendet.
• Soundness: Die Fehlerwahrscheinlichkeit ist vernachlässigbar klein ($O(d \cdot m / |\mathbb{F}|)$).

4. Bedeutung und Implikationen

• Schließen der Lücke: Das Paper schließt die Kluft zwischen univariaten und multivariaten SNARK-Systemen. Es zeigt, dass univariate Systeme (die oft als verifizierungsfreundlicher gelten) nun die Prover-Effizienz multivariater Systeme erreichen können.
• Praktische Anwendbarkeit: Da viele moderne SNARKs (wie Plonk, Halo2, etc.) univariate Polynome verwenden, können diese Protokolle direkt integriert werden, um die Prover-Zeiten drastisch zu verkürzen.
• Flexibilität: Die Unterstützung für Rundenreduktionen ermöglicht es, den Trade-off zwischen Kommunikationskosten (Runden) und Verifizierungszeit flexibel zu gestalten, ohne die lineare Prover-Effizienz zu opfern.
• Korrektur bestehender Literatur: Das Paper identifiziert und korrigiert Fehler im DGM-Protokoll und liefert eine solide, implementierbare Basis für zukünftige Forschung und Implementierungen (z. B. in Gemini-basierten Systemen).

Fazit: Malcom Mohamed präsentiert eine Reihe von Protokollen, die univariate Sumcheck-Aufgaben mit der Effizienz multivariater Methoden lösen. Durch die direkte Reduktion auf Gemini und die nahtlose Integration von Rundenreduktionen bietet diese Arbeit einen neuen Standard für effiziente, skalierbare und verifizierungsfreundliche Zero-Knowledge-Beweise.