Vitalik Buterin via de Vitalik Buterin-blog

Dit is een spiegel van het bericht op https://medium.com/@VitalikButerin/kwadratische-rekenkundige programma's-van-nul-tot-hero-f6d558cea649

Er is de laatste tijd veel belangstelling voor de technologie achter zk-SNARKs, en steeds meer mensen proberen te demystificeren iets dat velen ‘maanwiskunde’ zijn gaan noemen vanwege de waargenomen pure, niet te ontcijferen complexiteit. zk-SNARK's zijn inderdaad behoorlijk uitdagend om te begrijpen, vooral vanwege het grote aantal bewegende delen die moeten samenkomen om het geheel te laten werken, maar als we de technologie stukje bij beetje opsplitsen, wordt het begrijpen ervan eenvoudiger.

Het doel van dit bericht is niet om te dienen als een volledige introductie tot zk-SNARKs; het veronderstelt als achtergrondkennis dat (i) je weet wat zk-SNARKs zijn en wat ze doen, en (ii) voldoende wiskunde kent om te kunnen redeneren over zaken als polynomen (als de uitspraak �(�)+�(�) =(�+�)(�) , waarbij � en � polynomen zijn, lijkt natuurlijk en voor de hand liggend, dan zit je op het juiste niveau). Integendeel, de post graaft dieper in de machinerie achter de technologie en probeert de eerste helft van de pijplijn zo goed mogelijk uit te leggen, zoals getekend door zk-SNARK-onderzoeker Eran Tromer hier:

De stappen hier kunnen in twee helften worden opgesplitst. Ten eerste kunnen zk-SNARKs niet rechtstreeks op enig rekenprobleem worden toegepast; je moet het probleem eerder omzetten in de juiste ‘vorm’ waarin het probleem kan functioneren. De vorm wordt een ‘kwadratisch rekenprogramma’ (QAP) genoemd, en het transformeren van de code van een functie in een van deze programma’s is op zichzelf zeer niet triviaal. Naast het proces voor het converteren van de code van een functie naar een QAP is er nog een ander proces dat parallel kan worden uitgevoerd, zodat u, als u een invoer voor de code hebt, een overeenkomstige oplossing kunt creëren (soms “getuige” van de QAP genoemd). Hierna is er nog een tamelijk ingewikkeld proces voor het creëren van het daadwerkelijke ‘nulkennisbewijs’ voor deze getuige, en een afzonderlijk proces voor het verifiëren van een bewijs dat iemand anders aan u doorgeeft, maar dit zijn details die buiten het bestek van dit bericht vallen. .

Het voorbeeld dat we zullen kiezen is eenvoudig: bewijzen dat je de oplossing kent van een derdegraadsvergelijking: �3+�+5=35 (hint: het antwoord is 3). Dit probleem is zo eenvoudig dat de resulterende QAP niet zo groot zal zijn dat het intimiderend is, maar niet triviaal genoeg om te zien dat alle machines een rol spelen.

Laten we onze functie als volgt opschrijven:

def qeval(x):
    y = x**3
    return x + y + 5

De eenvoudige programmeertaal voor speciale doeleinden die we hier gebruiken ondersteunt elementaire rekenkunde (+, −, ⋅, /), exponentiatie van constante machten (�7 maar niet ��) en toewijzing van variabelen, wat krachtig genoeg is om theoretisch te kunnen doen elke berekening daarbinnen (zolang het aantal rekenstappen beperkt is; geen lussen toegestaan). Merk op dat modulo (%) en vergelijkingsoperatoren (<, >, ≤, ≥) NIET worden ondersteund, omdat er geen efficiënte manier is om modulo of vergelijking rechtstreeks uit te voeren in eindige cyclische groepenberekeningen (wees hier dankbaar voor; als er een manier was om een ​​van beide te doen, zou de elliptische curve-cryptografie sneller worden verbroken dan je kunt zeggen “binair zoeken” en “Chinese reststelling”).

Je kunt de taal uitbreiden naar modulo en vergelijkingen door bitdecomposities (bijv. 13=23+22+1) aan te bieden als hulpinvoer, de juistheid van die decomposities te bewijzen en de berekeningen uit te voeren in binaire circuits; bij eindige-veldberekeningen is het uitvoeren van gelijkheidscontroles (==) ook mogelijk en in feite een beetje eenvoudiger, maar dit zijn beide details waar we nu niet op ingaan. We kunnen de taal uitbreiden om conditionele waarden te ondersteunen (bijv. if �<5:�=7; else: �=9) door ze om te zetten in een rekenkundige vorm: �=7⋅(�<5)+9⋅(�≥5 ) Houd er echter rekening mee dat beide “paden” van de voorwaardelijke waarde moeten worden uitgevoerd, en als u veel geneste voorwaardelijke waarden heeft, kan dit tot een grote hoeveelheid overhead leiden.

Laten we dit proces nu stap voor stap doorlopen. Als je dit voor een stukje code zelf wilt doen, I heb hier een compiler geïmplementeerd (Alleen voor educatieve doeleinden; nog niet klaar voor het maken van QAP's voor echte zk-SNARK's!).

Het afvlakken

De eerste stap is een “afvlakking”-procedure, waarbij we de originele code, die willekeurig complexe uitspraken en uitdrukkingen kan bevatten, omzetten in een reeks uitspraken die twee vormen hebben: �=� (waarbij � een variabele of een getal kan zijn). ) en �=� (��) � (waarbij �� +, −, ⋅, / kan zijn en � en � variabelen, getallen of zelf subexpressies kunnen zijn). Je kunt elk van deze uitspraken beschouwen als een soort logische poorten in een circuit. Het resultaat van het afvlakkingsproces voor de bovenstaande code is als volgt:

sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5

Als je de originele code en de code hier leest, kun je vrij gemakkelijk zien dat de twee gelijkwaardig zijn.

Poorten naar R1CS

Nu zetten we dit om in iets dat een rang-1-beperkingssysteem (R1CS) wordt genoemd. Een R1CS is een reeks van groepen van drie vectoren (�, �, �), en de oplossing voor een R1CS is een vector �, waarbij � moet voldoen aan de vergelijking �.�⋅�.�−�.�=0, waarbij . vertegenwoordigt het puntproduct – in eenvoudiger bewoordingen, als we � en � aan elkaar ritsen, de twee waarden op dezelfde posities vermenigvuldigen, en dan de som van deze producten nemen, en dan hetzelfde doen met � en � en dan � en � , dan is het derde resultaat gelijk aan het product van de eerste twee resultaten. Dit is bijvoorbeeld een tevreden R1CS:

Maar in plaats van slechts één beperking te hebben, zullen we veel beperkingen hebben: één voor elke logische poort. Er is een standaardmanier om een ​​logische poort om te zetten in een (�,�,�) triple, afhankelijk van wat de bewerking is (+, −, ⋅ of /) en of de argumenten variabelen of getallen zijn. De lengte van elke vector is gelijk aan het totale aantal variabelen in het systeem, inclusief een dummyvariabele ~één bij de eerste index die het getal 1 vertegenwoordigt, de invoervariabelen, een dummyvariabele ~out die de uitvoer vertegenwoordigt, en vervolgens alle variabelen. tussenliggende variabelen (���1 en ���2 hierboven); de vectoren zullen over het algemeen erg schaars zijn en vullen alleen de slots in die overeenkomen met de variabelen die worden beïnvloed door een bepaalde logische poort.

Eerst geven we de variabelentoewijzing die we zullen gebruiken:

'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'

De oplossingsvector zal bestaan ​​uit toewijzingen voor al deze variabelen, in die volgorde.

Nu geven we het (�,�,�) triple voor de eerste poort:

a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]

Je kunt zien dat als de oplossingsvector 3 op de tweede positie bevat, en 9 op de vierde positie, de puntproductcontrole, ongeacht de rest van de inhoud van de oplossingsvector, neerkomt op 3⋅3=9, en dus het zal overgaan. Als de oplossingsvector −3 op de tweede positie en 9 op de vierde positie heeft, is de controle ook geslaagd; in feite, als de oplossingsvector 7 op de tweede positie heeft en 49 op de vierde positie, zal die controle nog steeds slagen - het doel van deze eerste controle is om de consistentie van de invoer en uitvoer van alleen de eerste poort te verifiëren.

Laten we nu verder gaan met de tweede poort:

a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]

Op dezelfde manier als bij de eerste puntproductcontrole controleren we hier dat ���1⋅�=�.

Nu de derde poort:

a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]

Hier is het patroon enigszins anders: het vermenigvuldigt het eerste element in de oplossingsvector met het tweede element en vervolgens met het vijfde element, telt de twee resultaten op en controleert of de som gelijk is aan het zesde element. Omdat het eerste element in de oplossingsvector altijd één is, is dit slechts een optellingscontrole, waarbij wordt gecontroleerd of de uitvoer gelijk is aan de som van de twee invoer.

Tenslotte de vierde poort:

a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]

Hier evalueren we de laatste controle, ~out =���2+5. De puntproductcontrole werkt door het zesde element in de oplossingsvector te nemen, vijf keer het eerste element toe te voegen (herinnering: het eerste element is 1, dus dit betekent feitelijk 5 optellen) en dit te vergelijken met het derde element, dat is waar we sla de uitvoervariabele op.

En daar hebben we onze R1CS met vier beperkingen. De getuige is eenvoudigweg de toewijzing aan alle variabelen, inclusief invoer-, uitvoer- en interne variabelen:

[1, 3, 35, 9, 27, 30]

U kunt dit zelf berekenen door eenvoudigweg de bovenstaande afgevlakte code uit te voeren, te beginnen met de toewijzing van de invoervariabele �=3, en de waarden van alle tussenvariabelen en de uitvoer in te voeren terwijl u ze berekent.

De volledige R1CS samengesteld is:

A
[0, 1, 0, 0, 0, 0]
[0, 0, 0, 1, 0, 0]
[0, 1, 0, 0, 1, 0]
[5, 0, 0, 0, 0, 1]

B
[0, 1, 0, 0, 0, 0]
[0, 1, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 0]

C
[0, 0, 0, 1, 0, 0]
[0, 0, 0, 0, 1, 0]
[0, 0, 0, 0, 0, 1]
[0, 0, 1, 0, 0, 0]

R1CS naar QAP

De volgende stap is het omzetten van deze R1CS in de QAP-vorm, die exact dezelfde logica implementeert, behalve het gebruik van polynomen in plaats van puntproducten. Dit doen wij als volgt. We gaan van vier groepen van drie vectoren met een lengte van zes naar zes groepen van drie graad-3 polynomen, waarbij het evalueren van de polynomen bij elke x-coördinaat vertegenwoordigt een van de beperkingen. Dat wil zeggen, als we de polynomen evalueren op �=1, dan krijgen we onze eerste set vectoren, als we de polynomen evalueren op �=2, dan krijgen we onze tweede set vectoren, enzovoort.

We kunnen deze transformatie uitvoeren met behulp van iets dat a wordt genoemd Lagrange-interpolatie. Het probleem dat een Lagrange-interpolatie oplost is dit: als je een reeks punten hebt (dat wil zeggen (�,�) coördinatenparen), dan levert het uitvoeren van een Lagrange-interpolatie op die punten je een polynoom op dat door al die punten gaat. We doen dit door het probleem te ontleden: voor elke �-coördinaat creëren we een polynoom met de gewenste �-coördinaat op die �-coördinaat en een �-coördinaat van 0 op alle andere �-coördinaten waarin we geïnteresseerd zijn, en dan krijgen we de uiteindelijke Als resultaat tellen we alle polynomen bij elkaar op.

Laten we een voorbeeld doen. Stel dat we een polynoom willen die door (1,3),(2,2) en (3,4) gaat. We beginnen met het maken van een polynoom die door (1,3),(2,0) en (3,0) gaat. Het blijkt dat het eenvoudig is om een ​​polynoom te maken dat “uitsteekt” bij �=1 en nul is op de andere interessante punten; wij doen gewoon:

(x - 2) * (x - 3)

Dat ziet er als volgt uit:

Nu hoeven we het alleen maar te ‘herschalen’ zodat de hoogte op x=1 goed is:

(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))

Dit geeft ons:

1.5 * x**2 - 7.5 * x + 9

We doen dan hetzelfde met de andere twee punten, en krijgen twee andere gelijksoortige polynomen, behalve dat ze “uitsteken” bij �=2 en �=3 in plaats van �=1. We tellen ze alle drie bij elkaar op en krijgen:

1.5 * x**2 - 5.5 * x + 7

Met precies de coördinaten die we willen. Het algoritme zoals hierboven beschreven kost �(�3) tijd, omdat er � punten zijn en elk punt �(�2) tijd nodig heeft om de polynomen met elkaar te vermenigvuldigen; met een beetje nadenken kan dit worden teruggebracht tot �(�2) tijd, en met veel meer nadenken, met behulp van snelle Fourier-transformatie-algoritmen en dergelijke, kan het zelfs nog verder worden teruggebracht — een cruciale optimalisatie wanneer functies worden gebruikt in zk -SNARK's hebben in de praktijk vaak vele duizenden poorten.

Laten we nu Lagrange-interpolatie gebruiken om onze R1CS te transformeren. Wat we gaan doen is de eerste waarde uit elke � vector halen, Lagrange-interpolatie gebruiken om daar een polynoom van te maken (waarbij het evalueren van de polynoom op � je de eerste waarde van de �de � vector oplevert), en herhaal het proces voor de eerste waarde van elke �- en �-vector, en herhaal dat proces vervolgens voor de tweede waarden, de derde, waarden, enzovoort. Voor het gemak zal ik nu de antwoorden geven:

A polynomials
[-5.0, 9.166, -5.0, 0.833]
[8.0, -11.333, 5.0, -0.666]
[0.0, 0.0, 0.0, 0.0]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]
[-1.0, 1.833, -1.0, 0.166]

B polynomials
[3.0, -5.166, 2.5, -0.333]
[-2.0, 5.166, -2.5, 0.333]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]

C polynomials
[0.0, 0.0, 0.0, 0.0]
[0.0, 0.0, 0.0, 0.0]
[-1.0, 1.833, -1.0, 0.166]
[4.0, -4.333, 1.5, -0.166]
[-6.0, 9.5, -4.0, 0.5]
[4.0, -7.0, 3.5, -0.5]

De coëfficiënten zijn in oplopende volgorde, dus de eerste polynoom hierboven is eigenlijk 0.833⋅�3—5⋅�2+9.166⋅�−5. Deze reeks polynomen (plus een Z-polynoom die ik later zal uitleggen) vormen de parameters voor dit specifieke QAP-exemplaar. Houd er rekening mee dat al het werk tot nu toe slechts één keer hoeft te worden gedaan voor elke functie die u met zk-SNARKs probeert te verifiëren; Zodra de QAP-parameters zijn gegenereerd, kunnen ze opnieuw worden gebruikt.

Laten we proberen al deze polynomen te evalueren op �=1. Het evalueren van een polynoom op �=1 betekent eenvoudigweg het optellen van alle coëfficiënten (zoals 1�=1 voor alle �), dus het is niet moeilijk. We krijgen:

A results at x=1
0
1
0
0
0
0

B results at x=1
0
1
0
0
0
0

C results at x=1
0
0
0
1
0
0

En zie, wat we hier hebben is precies hetzelfde als de set van drie vectoren voor de eerste logische poort die we hierboven hebben gemaakt.

Het controleren van de QAP

Wat is nu het nut van deze gekke transformatie? Het antwoord is dat we nu de beperkingen in de R1CS afzonderlijk kunnen controleren, in plaats van ze afzonderlijk te controleren alle beperkingen tegelijk door de puntproductcontrole uit te voeren op de polynomen.

Omdat in dit geval de puntproductcontrole een reeks optellingen en vermenigvuldigingen van polynomen is, zal het resultaat zelf een polynoom zijn. Als de resulterende polynoom, geëvalueerd op elke �-coördinaat die we hierboven hebben gebruikt om een ​​logische poort weer te geven, gelijk is aan nul, betekent dit dat alle controles slagen; als de resulterende polynoom, geëvalueerd op ten minste één van de �-coördinaten die een logische poort vertegenwoordigen, een waarde oplevert die niet nul is, dan betekent dit dat de waarden die die logische poort in en uit gaan inconsistent zijn (dat wil zeggen: de poort is �=�⋅�� �1 maar de opgegeven waarden kunnen �=2,���1=2 en �=5 zijn).

Merk op dat de resulterende polynoom zelf niet nul hoeft te zijn, en dat in de meeste gevallen ook niet zal zijn; het kan elk gedrag vertonen op de punten die niet overeenkomen met logische poorten, zolang het resultaat maar nul is op alle punten die do corresponderen met een poort. Om de juistheid te controleren, evalueren we niet daadwerkelijk de polynoom �=�.�⋅�.�−�.� op elk punt dat overeenkomt met een poort; in plaats daarvan delen we � door een andere polynoom, �, en controleren we of � gelijkmatig verdeelt � – dat wil zeggen dat de deling �/� geen rest achterlaat.

� wordt gedefinieerd als (�−1)⋅(�−2)⋅(�−3)… – de eenvoudigste polynoom die gelijk is aan nul op alle punten die overeenkomen met logische poorten. Dat is een elementair feit van de algebra elke polynoom dat op al deze punten gelijk is aan nul moet een veelvoud zijn van dit minimale polynoom, en als een polynoom een ​​veelvoud is van � dan zal de evaluatie ervan op elk van deze punten nul zijn; deze gelijkwaardigheid maakt ons werk veel gemakkelijker.

Laten we nu de puntproductcontrole uitvoeren met de bovenstaande polynomen. Eerst de tussenpolynomen:

A . s = [43.0, -73.333, 38.5, -5.166]
B . s = [-3.0, 10.333, -5.0, 0.666]
C . s = [-41.0, 71.666, -24.5, 2.833]

Nu, �.�⋅�.�—�.�:

t = [-88.0, 592.666, -1063.777, 805.833, -294.777, 51.5, -3.444]

Nu geldt het minimale polynoom �=(�−1)⋅(�−2)⋅(�−3)⋅(�−4):

Z = [24, -50, 35, -10, 1]

En als we het bovenstaande resultaat delen door �, krijgen we:

h = t / Z = [-3.666, 17.055, -3.444]

Zonder rest.

En dus hebben we de oplossing voor de QAP. Als we proberen een van de variabelen in de R1CS-oplossing waar we deze QAP-oplossing van afleiden te falsificeren – bijvoorbeeld, stel de laatste in op 31 in plaats van 30, dan krijgen we een �-polynoom die niet voldoet aan een van de controles (in dat specifieke geval In dat geval zou het resultaat bij �=3 gelijk zijn aan −1 in plaats van 0), en bovendien zou � geen veelvoud zijn van �; het delen van �/� zou eerder een rest opleveren van [−5.0,8.833,−4.5,0.666].

Merk op dat het bovenstaande een vereenvoudiging is; “in de echte wereld” zal het optellen, vermenigvuldigen, aftrekken en delen niet gebeuren met reguliere getallen, maar eerder met eindige veldelementen – een griezelig soort rekenkunde die zelfconsistent is, dus alle algebraïsche wetten die we kennen en waar we nog steeds van houden geldt waar, maar waarbij alle antwoorden elementen zijn van een verzameling van eindige grootte, meestal gehele getallen binnen het bereik van 0 tot �−1 voor sommige �. Als bijvoorbeeld �=13, dan is 1/2=7 (en 7⋅2=1),3⋅5=2, enzovoort. Door het gebruik van eindige-veldberekeningen hoeft u zich geen zorgen te maken over afrondingsfouten en kan het systeem goed werken met elliptische krommen, die uiteindelijk nodig zijn voor de rest van de zk-SNARK-machinerie die het zk-SNARK-protocol daadwerkelijk veilig maakt.

Speciale dank aan Eran Tromer voor zijn hulp bij het uitleggen van veel details over de innerlijke werking van zk-SNARKs aan mij.

• Door SEO aangedreven content en PR-distributie. Word vandaag nog versterkt.
• PlatoData.Network Verticale generatieve AI. Versterk jezelf. Toegang hier.
• PlatoAiStream. Web3-intelligentie. Kennis versterkt. Toegang hier.
• PlatoESG. carbon, CleanTech, Energie, Milieu, Zonne, Afvalbeheer. Toegang hier.
• Plato Gezondheid. Intelligentie op het gebied van biotech en klinische proeven. Toegang hier.
• BlockOffsets. Eigendom voor milieucompensatie moderniseren. Toegang hier.
• Bron: Plato data-intelligentie.