Vitalik Buterin via Vitalik Buterins blogg

Detta är en spegel av inlägget kl https://medium.com/@VitalikButerin/zk-snarks-under-huven-b33151a013f6

Detta är den tredje delen av en serie artiklar som förklarar hur tekniken bakom zk-SNARKs fungerar; de tidigare artiklarna om kvadratiska aritmetiska program och elliptiska kurvpar är obligatorisk läsning, och den här artikeln kommer att anta kunskap om båda begreppen. Grundläggande kunskap om vad zk-SNARK är och vad de gör förutsätts också. Se även Christian Reitwiessners artikel här för ytterligare en teknisk introduktion.

I de tidigare artiklarna introducerade vi det kvadratiska aritmetiska programmet, ett sätt att representera alla beräkningsproblem med en polynomekvation som är mycket mer mottaglig för olika former av matematiska knep. Vi introducerade också elliptiska kurvpar, som tillåter en mycket begränsad form av envägs homomorf kryptering som låter dig göra jämställdhetskontroll. Nu ska vi börja där vi slutade och använda elliptiska kurvpar, tillsammans med några andra matematiska knep, för att tillåta en provare att bevisa att de vet en lösning för en viss QAP utan att avslöja något annat om verklig lösning.

Den här artikeln kommer att fokusera på Pinocchio protokoll av Parno, Gentry, Howell och Raykova från 2013 (ofta kallad PGHR13); det finns några varianter av den grundläggande mekanismen, så ett zk-SNARK-schema implementerat i praktiken kan fungera något annorlunda, men de grundläggande principerna kommer i allmänhet att förbli desamma.

Till att börja med, låt oss gå in på det nyckelkryptografiska antagandet som ligger till grund för säkerheten för den mekanism som vi kommer att använda: *kunskap om-exponent* antagande.

I grund och botten, om du får ett par poäng � och �, där �⋅�=�, och du får en poäng �, så är det inte möjligt att komma på �⋅� om inte � "härstammar" från � på något sätt att du vet. Detta kan tyckas intuitivt uppenbart, men detta antagande kan faktiskt inte härledas från något annat antagande (t.ex. diskret loghårdhet) som vi vanligtvis använder när vi bevisar säkerheten för elliptiska kurvor-baserade protokoll, och därför vilar zk-SNARKs faktiskt på en något skakigare grund än elliptisk kurvkryptografi mer allmänt - även om den fortfarande är tillräckligt robust för att de flesta kryptografer är okej med det.

Låt oss nu gå in på hur detta kan användas. Tänkte att ett par punkter (�,�) faller från himlen, där �⋅�=�, men ingen vet vad värdet på � är. Anta nu att jag kommer på ett par punkter (�,�) där �⋅�=�. Sedan innebär KoE-antagandet att det enda sättet jag kunde ha gjort det paret poäng var genom att ta � och � och multiplicera båda med någon faktor r som jag personligen känner. Observera också att tack vare magin med elliptiska kurvpar, kontrollera att �=�⋅� kräver faktiskt inte att veta � – istället kan du helt enkelt kontrollera om �(�,�)=�(�,�).

Låt oss göra något mer intressant. Antag att vi har tio par punkter som faller från himlen: (�1,�1),(�2,�2)...(�10,�10). I alla fall ��⋅�=��. Anta att jag sedan ger dig ett par punkter (�,�) där �⋅�=�. Vad vet du nu? Du vet att � är någon linjär kombination �1⋅�1+�2⋅�2+…+�10⋅�10, där jag känner till koefficienterna �1,�2…�10. Det vill säga, det enda sättet att komma fram till ett sådant par av punkter (�,�) är att ta några multiplar av �1,�2…�10 och lägga ihop dem och göra samma beräkning med �1,�2... �10.

Observera att, givet en specifik uppsättning av �1…�10 poäng som du kanske vill kontrollera linjära kombinationer för, kan du faktiskt inte skapa de medföljande �1…�10 poäng utan att veta vad � är, och om du vet vad � är då kan du skapa ett par (�,�) där �⋅�=� för vad � du vill, utan att bry dig om att skapa en linjär kombination. För att detta ska fungera är det därför absolut nödvändigt att den som skapar dessa poäng är pålitlig och faktiskt raderar � när de skapat de tio poängen. Det är härifrån konceptet med en "trusted setup" kommer.

Kom ihåg att lösningen till en QAP är en uppsättning polynom (�,�,�) så att �(�)⋅�(�)−�(�)=�(�)⋅�(�), där:

• � är en linjär kombination av en uppsättning polynom {�1…��}
• � är den linjära kombinationen av {�1…��} med samma koefficienter
• � är en linjär kombination av {�1…��} med samma koefficienter

Mängderna {�1…��},{�1…��} och {�1…��} och polynomet � är en del av problemformuleringen.

Men i de flesta verkliga fall är �,� och � extremt stora; för något med många tusen kretsgrindar som en hashfunktion kan polynomen (och faktorerna för de linjära kombinationerna) ha många tusen termer. Därför, istället för att låta bevisaren tillhandahålla de linjära kombinationerna direkt, kommer vi att använda tricket som vi introducerade ovan för att få beviset att bevisa att de tillhandahåller något som är en linjär kombination, men utan att avslöja något annat.

Du kanske har märkt att tricket ovan fungerar på elliptiska kurvpunkter, inte polynom. Därför, vad som faktiskt händer är att vi lägger till följande värden till den betrodda inställningen:

• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• .
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• .
• �⋅�1(�),�⋅�1(�)⋅��
• �⋅�2(�),�⋅�2(�)⋅��
• .

Du kan tänka på t som en "hemlig punkt" där polynomet utvärderas. � är en "generator" (någon slumpmässig elliptisk kurvpunkt som anges som en del av protokollet) och �,��,�� och �� är "giftigt avfall", siffror som absolut måste raderas till varje pris, eller annars den som har dem kommer att kunna göra falska bevis. Nu, om någon ger dig ett par poäng �, � så att �⋅��=� (påminnelse: vi behöver inte �� kontrollera detta, eftersom vi kan göra en parningskontroll), då vet du att vad de ger dig är en linjär kombination av �� polynom utvärderade till �.

Så långt måste bevisaren ge:

• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��
• ��=�⋅�(�),��′=�⋅�(�)⋅��

Observera att provaren faktiskt inte behöver veta (och borde inte veta!) �,��,�� eller �� för att beräkna dessa värden; snarare bör provaren kunna beräkna dessa värden bara från de punkter som vi lägger till i den betrodda inställningen.

Nästa steg är att se till att alla tre linjära kombinationer har samma koefficienter. Detta kan vi göra genom att lägga till ytterligare en uppsättning värden till den betrodda inställningen: �⋅(��(�)+��(�)+��(�))⋅�, där � är ett annat tal som bör anses vara "giftigt" waste” och kasseras så snart den betrodda installationen är klar. Vi kan sedan låta provaren skapa en linjär kombination med dessa värden med samma koefficienter och använda samma parningstrick som ovan för att verifiera att detta värde stämmer överens med det angivna �+�+�.

Slutligen måste vi bevisa att �⋅�−�=�⋅�. Vi gör detta igen med en parningskontroll:

�(��,��)/�(��,�)?=�(�ℎ,�⋅�(�))

Där �ℎ=�⋅�(�). Om kopplingen mellan denna ekvation och �⋅�−�=�⋅� inte är meningsfull för dig, gå tillbaka och läs artikel om parningar.

Vi såg ovan hur man konverterar �,� och � till elliptiska kurvpunkter; � är bara generatorn (dvs. den elliptiska kurvans ekvivalent med nummer ett). Vi kan lägga till �⋅�(�) till den betrodda inställningen. � är svårare; � är bara ett polynom och vi förutspår väldigt lite i förväg om vad dess koefficienter kommer att vara för varje enskild QAP-lösning. Därför måste vi lägga till ännu mer data till den betrodda installationen; specifikt sekvensen:

�,�⋅�,�⋅�2,�⋅�3,�⋅�4….

I Zcash Trusted setup går sekvensen här upp till cirka 2 miljoner; det här är hur många krafter av � du behöver för att se till att du alltid kommer att kunna beräkna �(�), åtminstone för den specifika QAP-instans som de bryr sig om. Och med det kan provaren tillhandahålla all information för verifieraren att göra den sista kontrollen.

Det finns ytterligare en detalj som vi måste diskutera. För det mesta vill vi inte bara bevisa abstrakt att det finns någon lösning för något specifikt problem; snarare vill vi bevisa antingen riktigheten av någon specifik lösning (t.ex. bevisa att om du tar ordet "ko" och SHA3 hash det en miljon gånger så börjar slutresultatet med 0x73064fe5), eller att det finns en lösning om du begränsar några av parametrarna. Till exempel, i en instansiering av kryptovaluta där transaktionsbelopp och kontosaldon är krypterade, vill du bevisa att du känner till någon dekrypteringsnyckel k så att:

1. decrypt(old_balance, k) >= decrypt(tx_value, k)
2. decrypt(old_balance, k) - decrypt(tx_value, k) = decrypt(new_balance, k)

Den krypterade old_balance, tx_value och new_balance bör specificeras offentligt, eftersom det är de specifika värden som vi vill verifiera vid just den tidpunkten; endast dekrypteringsnyckeln ska döljas. Vissa små modifieringar av protokollet behövs för att skapa en "anpassad verifieringsnyckel" som motsvarar någon specifik begränsning av ingångarna.

Nu, låt oss ta ett steg tillbaka lite. Först och främst, här är verifieringsalgoritmen i sin helhet, med tillstånd av ben Sasson, Tromer, Virza och Chiesa:

Den första raden behandlar parametrisering; i huvudsak kan du tänka på dess funktion som att skapa en "anpassad verifieringsnyckel" för det specifika fallet av problemet där några av argumenten anges. Den andra raden är den linjära kombinationskontrollen för �,� och �; den tredje raden är kontrollen av att de linjära kombinationerna har samma koefficienter, och den fjärde raden är produktkontrollen �⋅�−�=�⋅�.

Sammantaget är verifieringsprocessen några elliptiska kurvmultiplikationer (en för varje "offentlig" ingångsvariabel), och fem parningskontroller, varav en inkluderar en extra parningsmultiplikation. Beviset innehåller åtta elliptiska kurvpunkter: ett par punkter vardera för �(�),�(�) och �(�), en punkt �� för �⋅(�(�)+�(�)+�(� )), och en punkt �ℎ för �(�). Sju av dessa punkter är på ��-kurvan (32 byte vardera, eftersom du kan komprimera �-koordinaten till en enda bit), och i Zcash-implementeringen är en punkt (��) på den tvinnade kurvan i ��2 (64 byte), så den totala storleken på beviset är ~288 byte.

De två beräkningsmässigt svåraste delarna av att skapa ett bevis är:

• Dela (�⋅�−�)/� för att få � (algoritmer baserade på Snabb Fourier-transform kan göra detta på subkvadratisk tid, men det är fortfarande ganska beräkningsintensivt)
• Att göra den elliptiska kurvan multiplikationer och tillägg för att skapa värdena �(�),�(�),�(�) och �(�) och deras motsvarande par

Den grundläggande anledningen till att det är så svårt att skapa ett bevis är det faktum att det som var en enda binär logisk grind i den ursprungliga beräkningen förvandlas till en operation som måste bearbetas kryptografiskt genom elliptiska kurvoperationer om vi gör ett noll-kunskapsbevis av det . Detta faktum, tillsammans med superlinjäriteten hos snabba Fourier-transformationer, innebär att bevisskapandet tar ~20–40 sekunder för en Zcash-transaktion.

En annan mycket viktig fråga är: kan vi försöka göra den pålitliga installationen lite... mindre förtroendekrävande? Tyvärr kan vi inte göra det helt tillitslöst; KoE-antagandet i sig utesluter att man skapar oberoende par (��,��⋅�) utan att veta vad � är. Vi kan dock öka säkerheten avsevärt genom att använda �-of-� flerpartsberäkning – det vill säga att konstruera den pålitliga installationen mellan � parter på ett sådant sätt att så länge som minst en av deltagarna raderade sitt giftiga avfall så är du okej .

För att få en känsla för hur du skulle göra detta, här är en enkel algoritm för att ta en befintlig uppsättning (�,�⋅�,�⋅�2,�⋅�3...) och "lägga till" din egen hemlighet så att du behöver både din hemlighet och den tidigare hemligheten (eller tidigare uppsättning hemligheter) för att fuska.

Utgångsuppsättningen är helt enkelt:

�,(�⋅�)⋅�,(�⋅�2)⋅�2,(�⋅�3)⋅�3...

Observera att du kan producera denna uppsättning genom att bara känna till den ursprungliga uppsättningen och s, och den nya uppsättningen fungerar på samma sätt som den gamla uppsättningen, förutom att nu använda �⋅� som "giftigt avfall" istället för �. Så länge du och personen (eller personerna) som skapade den tidigare uppsättningen inte både misslyckas med att ta bort ditt giftiga avfall och senare samarbetar, är uppsättningen "säker".

Att göra detta för den fullständiga betrodda installationen är ganska lite svårare, eftersom det finns flera värden inblandade, och algoritmen måste göras mellan parterna i flera omgångar. Det är ett område för aktiv forskning för att se om flerpartsberäkningsalgoritmen kan förenklas ytterligare och fås att kräva färre rundor eller göras mer parallelliserbar, eftersom ju mer du kan göra det desto fler parter blir det möjligt att inkludera i den betrodda installationsproceduren . Det är rimligt att se varför en pålitlig installation mellan sex deltagare som alla känner och arbetar med varandra kan göra vissa människor obekväma, men en pålitlig installation med tusentals deltagare skulle nästan inte kunna skiljas från inget förtroende alls – och om du verkligen är paranoid , kan du komma in och delta i installationsproceduren själv och vara säker på att du personligen har raderat ditt värde.

Ett annat område av aktiv forskning är användningen av andra tillvägagångssätt som inte använder parningar och samma betrodda uppsättningsparadigm för att uppnå samma mål; ser Eli ben Sassons senaste presentation för ett alternativ (men varnas, det är minst lika matematiskt komplicerat som SNARKs är!)

Särskilt tack till Ariel Gabizon och Christian Reitwiessner för recensionen.

• 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.