💻 computer science

Protocols for Univariate Sumcheck

Dit artikel presenteert drie benaderingen voor univariate sumcheck over wortels van eenheid, die kunnen worden gecombineerd met bestaande protocollen zoals de multivariate sumcheck of Gemini, en waarbij optionele ronde-reducties mogelijk zijn zonder de lineaire bewijstijd te verliezen.

Oorspronkelijke auteurs: Malcom Mohamed

Gepubliceerd 2026-03-24

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Malcom Mohamed

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Kern: Het Rekenprobleem van de "Twee Werelden"

Stel je voor dat je een enorme hoeveelheid data hebt (bijvoorbeeld een lijst met alle transacties in een blockchain). Je wilt bewijzen aan een controleur (de "verifier") dat de som van al die data klopt, zonder dat je de hele lijst hoeft te tonen. Dat is de basis van moderne cryptografie (SNARKs).

Er zijn twee manieren om deze data te organiseren, alsof er twee verschillende talen zijn:

De Multilineaire Wereld: Hier wordt data gezien als een complex, veelzijdig raster (een 3D- of 4D-blok). Dit is erg efficiënt voor de rekenkracht van de bewijzer (de "prover"), maar het is een zware taal voor de controleur om te verstaan.
De Univariate Wereld: Hier wordt data gezien als één lange, rechte lijn (een simpele polynoom). Dit is heel makkelijk en snel voor de controleur om te checken, maar traditioneel was het erg duur en traag voor de bewijzer om de berekeningen te doen.

Het probleem: De onderzoekers wilden de snelheid van de "rechte lijn" (voor de controleur) combineren met de efficiëntie van het "raster" (voor de bewijzer). Tot nu toe was dat niet goed gelukt.

De Oplossing: Drie Nieuwe Manieren om de Werelden te Verbinden

De auteur presenteert drie nieuwe protocollen (regelspellen) om deze twee werelden te laten samenwerken. Laten we ze bekijken met een analogie uit het dagelijks leven: Het Sorteren van een Berg Brieven.

Stel je voor dat je een berg brieven hebt (de data) en je moet bewijzen dat de som van de postcodes op de brieven een bepaald getal is.

1. De "Vertaler" (Protocol 2)

Hoe het werkt: In plaats van de brieven zelf te herschrijven, sturen we een "vertaler" die de brieven van de "rechte lijn" (univariate) tijdelijk omzet naar het "raster" (multilinear).
De Analogie: Je hebt een lange rij brieven. Je gebruikt een machine die ze in één keer in een 3D-pakketje stopt. De bewijzer doet het zware rekenwerk in dat pakketje (wat heel snel gaat). Daarna wordt het resultaat weer vertaald naar de lange rij voor de controleur.
Voordeel: Het is snel voor de bewijzer en gebruikt bestaande, bewezen methoden. Het is als het gebruik van een tolk die twee talen perfect vertaalt zonder dat je zelf beide talen hoeft te leren.

2. De "Reparatie" van een Bestaand Concept (Protocol 3)

Hoe het werkt: Er was al een idee in de gemeenschap (van Drake, Gabizon en Meckler, oftewel DGM) om dit te doen, maar het had een foutje. De auteur heeft dit idee opgepakt, het gerepareerd en verbeterd.
De Analogie: Iemand had een blauwdruk voor een brug tussen twee eilanden, maar er zat een gat in de constructie. De auteur heeft het gat dichtgemetseld en de brug sterker gemaakt.
Nadeel: Hoewel het werkt, is het nog steeds een beetje rommelig en minder efficiënt dan de andere opties. Het is alsof je een oude auto repareert die wel rijdt, maar niet zo soepel loopt als een nieuwe.

3. De "Directe Route" (Protocol 4) – De Winnaar!

Hoe het werkt: Dit is de meest elegante oplossing. In plaats van eerst te vertalen of een oude brug te repareren, ontwerpt de auteur een nieuwe, directe weg die precies past bij de structuur van de data.
De Analogie: In plaats van de brieven eerst in een pakketje te stoppen en ze er weer uit te halen, of een oude brug te gebruiken, bouwt de auteur een lift die direct van de grond naar de top gaat.
Waarom het geweldig is:
- Het is lineair snel: Als je dubbel zoveel brieven hebt, duurt het precies twee keer zo lang (niet vier keer zo lang of nog erger).
- Het is zuinig: De bewijzer hoeft minder informatie te sturen.
- Het is flexibel: Je kunt de "lift" halverwege stoppen als je maar een klein stukje hoeft te bewijzen, wat tijd bespaart.

De "Ronde-Reductie": Het Versnellen van het Proces

Een belangrijk detail in het artikel is de mogelijkheid om het proces te versnellen door het aantal "rondes" (stappen in het gesprek tussen bewijzer en controleur) te verminderen.

Normaal: Je moet misschien 1000 stappen doen om het bewijs te leveren.
Met de nieuwe methode: Je kunt de eerste 900 stappen in één grote sprong doen en de laatste 100 stappen in één simpele check.
De Analogie: Stel je moet een berg beklimmen.
- Oude methode: Je loopt elke tree op (1000 stappen).
- Nieuwe methode: Je neemt een helikopter naar de top (1 stap) of je gebruikt een kabelbaan die je in 10 grote sprongen naar boven brengt.
- Het artikel laat zien dat je dit kunt doen zonder dat de bewijzer zwaarder hoeft te werken. Je kunt de "berg" zelfs in $\sqrt{m}$ (wortel uit het aantal brieven) stappen beklimmen in plaats van $m$ stappen.

Samenvatting voor de Leek

Dit artikel lost een groot probleem op in de wereld van digitale privacy en beveiliging. Het laat zien hoe we complexe data (zoals transacties in een blockchain) kunnen verifiëren:

Sneller: De computer die het bewijs maakt (de prover) doet minder zware arbeid.
Minder data: Er moet minder informatie over het internet worden gestuurd.
Flexibeler: Het bewijs kan in minder stappen worden geleverd.

De auteur heeft drie manieren bedacht, maar Protocol 4 (de "Directe Route") is de beste. Het is als het vinden van een nieuwe, snellere weg door een stad die eerder alleen via omwegen bereikbaar was. Hierdoor kunnen toekomstige systemen (zoals privacy-betalingen of digitale identiteiten) veel sneller en goedkoper werken.

Kortom: De auteur heeft de "vertaler" en de "reparateur" overbodig gemaakt door een super-efficiënte lift te bouwen die de twee werelden van cryptografie direct en snel met elkaar verbindt.

Titel: Protocols for Univariate Sumcheck

Auteur: Malcom Mohamed
Context: Cryptografie, Zero-Knowledge Proofs (SNARKs), Polynomial Interactive Oracle Proofs (PIOPs).

1. Het Probleem

In moderne Zero-Knowledge Proof-systemen (SNARKs) worden gegevens vaak geëncodeerd als polynomen. Er bestaan twee hoofdarchitecturen:

Multilineaire systemen: Gebruiken multilineaire extensies (mlex) van data. Hier is de standaard "multivariate sumcheck"-protocol (LFKN) zeer efficiënt voor de bewijzer (prover), maar vereist veel rondes en bandbreedte.
Univariate systemen: Gebruiken univariate extensies (unex) over wortels van eenheid. De standaard univariate sumcheck (zoals in Aurora) is zeer efficiënt voor de verifieerder (slechts 1 ronde), maar de bewijzer heeft vaak een hogere complexiteit (quasilineair of slechter).

De kernvraag: Is het mogelijk om een univariate sumcheck-protocol te construeren dat de bewijzer-efficiëntie van multilineaire systemen bereikt (lineaire tijd), terwijl het de verifieerder-efficiëntie van univariate systemen behoudt?

Bestaande "adapters" die multilineaire polynomen vertalen naar univariate polynomen (om multilineaire technieken te gebruiken) hebben vaak een hoge overhead of vereisen complexe basis-translaties. Daarnaast was er een gerucht over een lineaire tijd univariate sumcheck gebaseerd op het "Gemini"-protocol (Drake, Gabizon, Meckler - DGM), maar deze was niet publiek gedocumenteerd en bleek later foutief te zijn.

2. Methodologie en Aanpak

De auteur presenteert drie kandidaat-protocollen om univariate sumcheck over wortels van eenheid aan te pakken. De aanpak combineert nieuwe reducties met bestaande protocollen zoals Gemini en Aurora.

A. Protocol 2: Reductie van `mlex` naar `unex` (Square Evaluation Folding)

Dit protocol fungeert als een adapter. Het stelt de verifieerder in staat om een claim over een multilineaire extensie (mlex[v]) te verifiëren, gegeven alleen toegang tot de univariate extensie (unex[v]).

Techniek: Het protocol gebruikt een "square decomposition". Een polynoom $f$ wordt opgesplitst in een "vierkante" component ( $f_{sq}$ ) en een "niet-vierkante" component ( $f_{no}$ ) gebaseerd op de even en oneven coëfficiënten.
Werking: De bewijzer stuurt orakels voor deze componenten. De verifieerder controleert via een veralgemeende Lagrange-interpolatieformule of deze componenten consistent zijn met de oorspronkelijke polynoom.
Resultaat: Dit maakt het mogelijk om de standaard multilineaire sumcheck (LFKN) direct toe te passen op univariate data, met lineaire tijd voor de bewijzer ( $O(2^m)$ ).

B. Protocol 3: Gecorrigeerde DGM (Domain Identity)

Dit protocol is een herziening van het DGM-protocol (Drake et al.) voor domein-identiteit (bewijzen dat $P(w_i) = h(w_i)$ voor alle $i$ ).

Probleem met DGM: Het originele DGM-protocol bevatte een fout in de graad-controle en de consistentie-checks, waardoor het onveilig was.
Oplossing: De auteur introduceert een gecorrigeerde versie die expliciete graad-checks en consistentie-checks tussen de even/oneven delen en de oorspronkelijke polynoom implementeert.
Resultaat: Het reduceert een univariate sumcheck-claim naar een multilineaire evaluatieclaim (die vervolgens met Gemini kan worden opgelost). Dit protocol is echter minder efficiënt dan Protocol 4.

C. Protocol 4: Directe Univariate Sumcheck (De "Beste" Oplossing)

Dit is het meest efficiënte protocol en de hoofdbijdrage van het artikel.

Techniek: Het maakt direct gebruik van de relatie tussen univariate polynomen en multilineaire polynomen via de inverse Kronecker-substitutie. De auteur toont aan dat het evalueren van een univariate polynoom op wortels van eenheid equivalent is aan het evalueren van een multilineaire polynoom op specifieke punten.
Werking: Het protocol past de logica van de standaard multilineaire sumcheck direct toe op de univariate context. In elke ronde reduceert de bewijzer de claim naar een kleinere univariate som, totdat er een multilineaire evaluatie overblijft die met Gemini kan worden verifieerd.
Efficiëntie: De bewijzer werkt in strikt lineaire tijd ( $O(d^2 2^m)$ ), wat vergelijkbaar is met de beste multilineaire protocollen, maar dan voor univariate data.

3. Belangrijkste Bijdragen

Lineaire Tijd Univariate Sumcheck: Het artikel levert het eerste publieke, correcte en efficiënte protocol voor univariate sumcheck met lineaire tijd voor de bewijzer, gebaseerd op het Gemini-protocol.
Correctie van DGM: Het identificeert en corrigeert een fundamentele fout in het voorgestelde DGM-protocol, en toont aan dat een aangepaste versie een geval is van de gezochte lineaire tijd sumcheck.
Nieuwe Adapter (Protocol 2): Een efficiënte methode om multilineaire sumcheck toe te passen op univariate data zonder de overhead van basis-translatie (in tegenstelling tot eerdere methoden zoals HybridPlonk).
Ronde-reductie (Round Reduction): Alle protocollen ondersteunen natuurlijke ronde-reductie. Door de sumcheck vroegtijdig te stoppen na $k$ $k$ rondes, kan de resterende claim worden opgelost met een snelle single-round protocol (zoals Aurora).
- Dit resulteert in protocollen met $O(\log m)$ rondes of zelfs $O(\sqrt{m})$ rondes (via een veralgemeende aanpak in sectie 4.3), terwijl de bewijzer-tijd lineair blijft.

4. Resultaten en Prestaties

De prestaties worden vergeleken met de standaard Aurora-protocol in Tabel 2 van het artikel:

Bewijzer Tijd: Alle voorgestelde protocollen bereiken lineaire tijd ( $O(2^m)$ ) voor de bewijzer, wat een verbetering is ten opzichte van de quasilineaire tijd van eerdere univariate adapters.
Rondes:
- Standaard uitvoering: $m$ rondes (vergelijkbaar met multilineaire sumcheck).
- Met ronde-reductie: Kan worden gereduceerd tot $\log(m)$ rondes (combinatie met Aurora) of $O(\sqrt{m})$ rondes (via de veralgemeende aanpak).
Communicatie: Protocol 4 (Directe reductie) is het meest efficiënt. Het vereist minder orakels en veld-elementen dan Protocol 3 of de combinatie van LFKN met de adapter uit Protocol 2.
Gemini Integratie: Alle protocollen eindigen in een claim die kan worden verifieerd met het Gemini-protocol, wat de verifieerder-efficiëntie behoudt.

5. Betekenis en Impact

Dit artikel sluit een belangrijke kloof in het landschap van SNARKs:

Unificatie: Het maakt het mogelijk om de bewijzer-efficiëntie van multilineaire systemen te combineren met de verifieerder-efficiëntie (bandbreedte en rondes) van univariate systemen.
Toepasbaarheid: Bestaande univariate SNARK-implementaties (zoals die die Aurora gebruiken) kunnen nu worden geoptimaliseerd om de bewijzer-tijd drastisch te verkorten zonder de verifieerder te belasten.
Veiligheid: Door de fouten in het DGM-protocol te identificeren en te corrigeren, biedt het artikel een veilig fundament voor toekomstige ontwikkelingen in dit domein.

Kortom, het artikel bewijst dat "lineaire tijd univariate sumcheck" generiek haalbaar is door een geschikte reductie en adapter te combineren, waardoor de prestaties van univariate systemen nu gelijk kunnen zijn aan die van multilineaire systemen.