Vitalik Buterin via Vitalik Buterins blogg
Detta är en spegel av inlägget kl https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-noll-to-hero-f6d558cea649
Det har funnits ett stort intresse på sistone för tekniken bakom zk-SNARKs, och folk blir allt fler försöker avmystifiera något som många har kommit att kalla "månematematik" på grund av dess upplevda ren och otydliga komplexitet. zk-SNARKs är verkligen ganska utmanande att förstå, särskilt på grund av det stora antalet rörliga delar som måste samlas för att det hela ska fungera, men om vi bryter ner tekniken bit för bit blir det enklare att förstå det.
Syftet med detta inlägg är inte att tjäna som en fullständig introduktion till zk-SNARKs; det förutsätter som bakgrundskunskap att (i) du vet vad zk-SNARK är och vad de gör, och (ii) kan tillräckligt med matematik för att kunna resonera om saker som polynom (om påståendet �(�)+�(�) =(�+�)(�) , där � och � är polynom, verkar naturligt och självklart för dig, då är du på rätt nivå). Snarare gräver inlägget djupare i maskineriet bakom tekniken och försöker förklara så bra som möjligt den första halvan av pipelinen, som ritats av zk-SNARK-forskaren Eran Tromer här:
Stegen här kan delas upp i två halvor. För det första kan zk-SNARK inte appliceras på något beräkningsproblem direkt; snarare måste du omvandla problemet till rätt "form" för att problemet ska opereras. Formen kallas för ett "kvadratiskt aritmetiskt program" (QAP), och att omvandla koden för en funktion till en av dessa är i sig mycket icke-trivialt. Tillsammans med processen för att konvertera koden för en funktion till en QAP finns en annan process som kan köras vid sidan av så att om du har en input till koden kan du skapa en motsvarande lösning (ibland kallad "vittne" till QAP). Efter detta finns det en annan ganska komplicerad process för att skapa det faktiska "noll kunskapsbeviset" för detta vittne, och en separat process för att verifiera ett bevis på att någon annan skickar vidare till dig, men det här är detaljer som ligger utanför räckvidden för det här inlägget .
Exemplet som vi kommer att välja är enkelt: att bevisa att du känner till lösningen till en kubikekvation: �3+�+5=35 (tips: svaret är 3). Detta problem är tillräckligt enkelt för att den resulterande QAP inte kommer att vara så stor att den är skrämmande, men icke-trivial nog att du kan se alla maskiner spela in.
Låt oss skriva ut vår funktion så här:
def qeval(x):
y = x**3
return x + y + 5Det enkla specialprogrammeringsspråket som vi använder här stöder grundläggande aritmetik (+, −, ⋅, /), konstanteffektexponentiering (�7 men inte ��) och variabeltilldelning, som är tillräckligt kraftfull för att du teoretiskt kan göra alla beräkningar inuti den (så länge antalet beräkningssteg är begränsat; inga loopar tillåtna). Observera att modulo (%) och jämförelseoperatorer (<, >, ≤, ≥) INTE stöds, eftersom det inte finns något effektivt sätt att göra modulo eller jämförelse direkt i finita cyklisk grupparitmetik (var tacksam för detta; om det fanns ett sätt för att göra endera, då skulle elliptisk kurvkryptografi brytas snabbare än du kan säga "binär sökning" och "kinesisk restsats").
Du kan utöka språket till modulo och jämförelser genom att tillhandahålla bituppdelningar (t.ex. 13=23+22+1) som hjälpingångar, bevisa att dessa uppdelningar är korrekta och göra matematiken i binära kretsar; i finita fältarithmetik är det också möjligt att göra likhetskontroller (==) och faktiskt lite lättare, men det är båda detaljer som vi inte kommer in på just nu. Vi kan utöka språket till att stödja villkor (t.ex. om �<5:�=7; annars: �=9) genom att konvertera dem till en aritmetisk form: �=7⋅(�<5)+9⋅(�≥5) ) Observera dock att båda "sökvägarna" för det villkorliga måste exekveras, och om du har många kapslade villkor kan detta leda till en stor mängd overhead.
Låt oss nu gå igenom denna process steg för steg. Om du vill göra detta själv för en kodbit, kan jag implementerade en kompilator här (endast i utbildningssyfte; inte redo att göra QAPs för verkliga zk-SNARKs ännu!).
plattas
Det första steget är en "tillplattande" procedur, där vi omvandlar den ursprungliga koden, som kan innehålla godtyckligt komplexa satser och uttryck, till en sekvens av satser som har två former: �=� (där � kan vara en variabel eller ett tal ) och �=� (��) � (där �� kan vara +, −, ⋅, / och � och � kan vara variabler, tal eller själva deluttryck). Du kan tänka på vart och ett av dessa påståenden som ungefär som logiska grindar i en krets. Resultatet av utjämningsprocessen för ovanstående kod är följande:
sym_1 = x * x
y = sym_1 * x
sym_2 = y + x
~out = sym_2 + 5Om du läser originalkoden och koden här kan du ganska enkelt se att de två är likvärdiga.
Portar till R1CS
Nu konverterar vi detta till något som kallas ett rank-1 constraint system (R1CS). En R1CS är en sekvens av grupper av tre vektorer (�, �, �), och lösningen till en R1CS är en vektor �, där � måste uppfylla ekvationen �.�⋅�.�−�.�=0, där � . representerar prickprodukten – i enklare termer, om vi "zippar ihop" � och �, multiplicerar de två värdena i samma positioner och sedan tar summan av dessa produkter, gör sedan samma sak med � och � och sedan � och � , då är det tredje resultatet lika med produkten av de två första resultaten. Detta är till exempel en nöjd R1CS:
Först tillhandahåller vi variabelmappningen som vi kommer att använda:
'~one', 'x', '~out', 'sym_1', 'y', 'sym_2'Lösningsvektorn kommer att bestå av tilldelningar för alla dessa variabler, i den ordningen.
Nu ger vi (�,�,�) trippeln för den första porten:
a = [0, 1, 0, 0, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 1, 0, 0]Du kan se att om lösningsvektorn innehåller 3 i den andra positionen och 9 i den fjärde positionen, så kommer, oavsett resten av innehållet i lösningsvektorn, punktproduktkontrollen att koka ner till 3⋅3=9, och så det går över. Om lösningsvektorn har −3 i den andra positionen och 9 i den fjärde positionen, kommer kontrollen också att passera; i själva verket, om lösningsvektorn har 7 i den andra positionen och 49 i den fjärde positionen så kommer den kontrollen fortfarande att passera - syftet med denna första kontroll är att verifiera överensstämmelsen hos in- och utgångarna från endast den första grinden.
Låt oss nu gå vidare till den andra porten:
a = [0, 0, 0, 1, 0, 0]
b = [0, 1, 0, 0, 0, 0]
c = [0, 0, 0, 0, 1, 0]I en liknande stil som den första produktkontrollen med prickar, här kontrollerar vi att ���1⋅�=�.
Nu, den tredje porten:
a = [0, 1, 0, 0, 1, 0]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 0, 0, 0, 1]Här är mönstret något annorlunda: det är att multiplicera det första elementet i lösningsvektorn med det andra elementet, sedan med det femte elementet, lägga till de två resultaten och kontrollera om summan är lika med det sjätte elementet. Eftersom det första elementet i lösningsvektorn alltid är ett, är detta bara en additionskontroll, som kontrollerar att utsignalen är lika med summan av de två ingångarna.
Till sist, den fjärde porten:
a = [5, 0, 0, 0, 0, 1]
b = [1, 0, 0, 0, 0, 0]
c = [0, 0, 1, 0, 0, 0]Här utvärderar vi den sista kontrollen, ~out =���2+5. Punktproduktkontrollen fungerar genom att ta det sjätte elementet i lösningsvektorn, lägga till fem gånger det första elementet (påminnelse: det första elementet är 1, så detta innebär faktiskt att man lägger till 5), och kontrollerar det mot det tredje elementet, vilket är där vi lagra utdatavariabeln.
Och där har vi vår R1CS med fyra begränsningar. Vittnet är helt enkelt tilldelningen av alla variabler, inklusive input, output och interna variabler:
[1, 3, 35, 9, 27, 30]Du kan beräkna detta själv genom att helt enkelt "exekvera" den tillplattade koden ovan, börja med ingångsvariabeltilldelningen �=3 och sätta in värdena för alla mellanliggande variabler och utdata när du beräknar dem.
Den kompletta R1CS sammansatt är:
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 till QAP
Nästa steg är att ta denna R1CS och konvertera den till QAP-form, som implementerar exakt samma logik förutom att använda polynom istället för punktprodukter. Vi gör detta enligt följande. Vi går 3från fyra grupper om tre vektorer med längden sex till sex grupper om tre grader-3 polynom, där vi utvärderar polynomen vid varje x-koordinat representerar en av begränsningarna. Det vill säga, om vi utvärderar polynomen vid �=1, får vi vår första uppsättning vektorer, om vi utvärderar polynomen vid �=2, får vi vår andra uppsättning vektorer, och så vidare.
Vi kan göra denna transformation med något som kallas a Lagrange interpolation. Problemet som en Lagrange-interpolation löser är detta: om du har en uppsättning punkter (dvs. (�,�) koordinatpar), då gör en Lagrange-interpolation på dessa punkter ett polynom som passerar genom alla dessa punkter. Vi gör detta genom att dekomponera problemet: för varje koordinat skapar vi ett polynom som har den önskade koordinaten vid den koordinaten och en koordinat på 0 vid alla andra koordinater vi är intresserade av, och sedan för att få den slutliga resultat lägger vi ihop alla polynomen.
Låt oss ta ett exempel. Antag att vi vill ha ett polynom som går genom (1,3),(2,2) och (3,4). Vi börjar med att göra ett polynom som går genom (1,3),(2,0) och (3,0). Som det visar sig är det lätt att göra ett polynom som "sticker ut" vid �=1 och är noll på de andra intressanta platserna; vi gör helt enkelt:
(x - 2) * (x - 3)Som ser ut så här:
(x - 2) * (x - 3) * 3 / ((1 - 2) * (1 - 3))Detta ger oss:
1.5 * x**2 - 7.5 * x + 9
1.5 * x**2 - 5.5 * x + 7
Låt oss nu använda Lagrange-interpolation för att transformera vår R1CS. Vad vi ska göra är att ta det första värdet ur varje vektor, använda Lagrange-interpolation för att göra ett polynom av det (där utvärdering av polynomet vid � ger dig det första värdet av den �e � vektorn), upprepa processen för det första värdet av varje � och � vektor, och upprepa sedan den processen för de andra värdena, de tredje värdena och så vidare. För enkelhetens skull ger jag svaren nu:
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]Koefficienterna är i stigande ordning, så det första polynomet ovan är faktiskt 0.833⋅�3—5⋅�2+9.166⋅�−5. Denna uppsättning polynom (plus ett Z-polynom som jag kommer att förklara senare) utgör parametrarna för just denna QAP-instans. Observera att allt arbete fram till denna punkt endast behöver göras en gång för varje funktion som du försöker använda zk-SNARKs för att verifiera; när QAP-parametrarna väl har genererats kan de återanvändas.
Låt oss försöka utvärdera alla dessa polynom vid �=1. Att utvärdera ett polynom vid �=1 innebär helt enkelt att lägga ihop alla koefficienter (som 1�=1 för alla �), så det är inte svårt. Vi får:
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
0Och se, vad vi har här är exakt samma som uppsättningen av tre vektorer för den första logiska grinden som vi skapade ovan.
Kontrollerar QAP
Vad är poängen med denna galna förvandling? Svaret är att istället för att kontrollera begränsningarna i R1CS individuellt, kan vi nu kontrollera alla begränsningar på samma gång genom att göra punktproduktkontrollen på polynomen.
Observera att det resulterande polynomet inte i sig behöver vara noll, och i de flesta fall kommer det faktiskt inte att vara det; det kan ha vilket beteende som helst vid de punkter som inte motsvarar några logiska grindar, så länge resultatet är noll vid alla punkter som do motsvara någon grind. För att kontrollera korrektheten utvärderar vi faktiskt inte polynomet �=�.�⋅�.�−�.� vid varje punkt som motsvarar en grind; istället dividerar vi � med ett annat polynom, �, och kontrollerar att � jämnt delar � – det vill säga divisionen �/� lämnar ingen rest.
� definieras som (�−1)⋅(�−2)⋅(�−3)... – det enklaste polynomet som är lika med noll i alla punkter som motsvarar logiska grindar. Det är ett elementärt faktum i algebra att vilken som helst polynom som är lika med noll vid alla dessa punkter måste vara en multipel av detta minimala polynom, och om ett polynom är en multipel av � så kommer dess utvärdering vid någon av dessa punkter att vara noll; denna likvärdighet gör vårt jobb mycket lättare.
Nu, låt oss faktiskt göra punktproduktkontrollen med polynomen ovan. Först, de mellanliggande polynomen:
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, det minimala polynomet �=(�−1)⋅(�−2)⋅(�−3)⋅(�−4):
Z = [24, -50, 35, -10, 1]Och om vi dividerar resultatet ovan med � får vi:
h = t / Z = [-3.666, 17.055, -3.444]Utan rester.
Och så har vi lösningen för QAP. Om vi försöker förfalska någon av variablerna i R1CS-lösningen som vi härleder den här QAP-lösningen från - säg, ställ in den sista till 31 istället för 30, då får vi ett polynom som inte klarar en av kontrollerna (i just det fallet skulle resultatet vid �=3 vara lika med −1 istället för 0), och � skulle dessutom inte vara en multipel av �; snarare skulle dividera �/� ge en återstod på [−5.0,8.833,−4.5,0.666].
Observera att ovanstående är en förenkling; "i den verkliga världen", addition, multiplikation, subtraktion och division kommer inte att ske med vanliga tal, utan snarare med ändliga fältelement - en spöklik sorts aritmetik som är självkonsekvent, så alla algebraiska lagar vi känner till och älskar fortfarande stämmer, men där alla svar är element i någon ändlig storlek, vanligtvis heltal inom intervallet från 0 till �−1 för vissa �. Till exempel, om �=13, då 1/2=7 (och 7⋅2=1), 3⋅5=2 och så vidare. Att använda finita fältaritmetik tar bort behovet av att oroa sig för avrundningsfel och låter systemet fungera bra med elliptiska kurvor, vilket slutar med att vara nödvändigt för resten av zk-SNARK-maskineriet som gör zk-SNARK-protokollet faktiskt säkert.
Speciellt tack till Eran Tromer för att han hjälpte till att förklara många detaljer om zk-SNARKs inre funktioner för mig.
- SEO-drivet innehåll och PR-distribution. Bli förstärkt idag.
- PlatoData.Network Vertical Generative Ai. Styrka dig själv. Tillgång här.
- PlatoAiStream. Web3 Intelligence. Kunskap förstärkt. Tillgång här.
- Platoesg. Kol, CleanTech, Energi, Miljö, Sol, Avfallshantering. Tillgång här.
- PlatoHealth. Biotech och kliniska prövningar Intelligence. Tillgång här.
- BlockOffsets. Modernisera miljökompensation ägande. Tillgång här.
- Källa: Platon Data Intelligence.
