Titlul original: „Cum să proiectați o schemă de recursivitate a dovezii rafinată” Autor original: Lin Yanxi, CTO al Fox Tech Meng Xuanji, om de știință șef al Fox Tech Cuvânt înainte: Aproape toate problemele întâlnite în melodiile zkRollup și zkEVM, printre ele sunt; probleme în esență algoritmice. Motivul principal pentru care accelerarea hardware ZKP este adesea menționată este că algoritmii actuali sunt în general lenți. Pentru a evita căderea în situația jenantă de „algoritmul nu este suficient, hardware-ul va compensa”, ar trebui să rezolvăm problema algoritmic. Proiectarea unei scheme rafinate de dovadă a recurenței este cheia pentru rezolvarea acestei probleme. Odată cu dezvoltarea continuă a contractelor inteligente, din ce în ce mai multe aplicații web3 apar treptat, iar volumul tranzacțiilor tradiționale Layer1, cum ar fi Ethereum, crește rapid și congestia poate apărea în orice moment. Cum să obțineți o eficiență mai mare, asigurând în același timp securitatea oferită de Layer 1 a devenit o problemă urgentă care trebuie rezolvată. Pentru Ethereum, zkRollup folosește algoritmul de demonstrare a cunoștințelor zero ca componentă de bază pentru a muta calcule costisitoare care trebuiau inițial efectuate pe Layer1 în afara lanțului și pentru a oferi dovada corectitudinii execuției lanțului. Piesa include în principal proiecte precum StarkWare, zkSync, Scroll și Fox Tech. De fapt, în proiectarea zkRollup, există cerințe foarte mari pentru eficiență: se speră ca valoarea dovezii transmise să fie suficient de mică, astfel încât să reducă sarcina de calcul a Layer1. Pentru a obține o lungime suficient de mică a probei, diverse proiecte zkRollup îmbunătățesc algoritmi și design-uri de arhitectură. De exemplu, Fox și-a dezvoltat propriul algoritm de demonstrare FOAKS bazat pe cel mai recent algoritm de demonstrare cu zero cunoștințe pentru a obține un timp optim de demonstrare și o lungime optimă. În plus, în stadiul verificării dovezii, cea mai banală metodă este de a genera liniar dovezi și de a le verifica secvențial. Pentru a îmbunătăți eficiența, primul lucru la care se gândește toată lumea este să împacheteze mai multe dovezi într-o singură dovadă, care este denumită în mod obișnuit agregare a dovezilor (Agregarea dovezilor). Intuitiv vorbind, verificarea dovezilor generate de zkEVM este un proces liniar, iar verificatorul (Verifier) ​​trebuie să verifice pe rând fiecare valoare a dovezii generată. Cu toate acestea, eficiența acestei metode de verificare este relativ scăzută, iar cheltuielile generale de comunicare sunt relativ mari.Să ne uităm mai întâi la un exemplu: Alice vrea să demonstreze lumii că a mers la Fox Park în perioada 1-7 a acestei luni. Pentru a face acest lucru, ea poate face o fotografie în parc cu ziarul din ziua respectivă în fiecare zi de la 1 la 7, iar pachetul cu aceste 7 fotografii va deveni o dovadă. Figura 1: Schema generală de agregare a dovezilor În exemplul de mai sus, punerea a 7 fotografii direct într-un plic este o agregare a dovezilor într-un sens intuitiv. Verificați prima dovadă, apoi a doua dovadă și dovezile ulterioare. Problema este că această abordare nu va schimba nici dimensiunea dovezii, nici timpul demonstrării. Are același efect ca și verificarea pe rând. Dacă doriți să obțineți compresia spațiului la nivel logaritmic, trebuie să utilizați dovada recursivă (Proof Recursion) menționată mai jos. Schema recursivă de demonstrare folosită de Halo2 și STARK Pentru a explica mai bine ce este o demonstrație recursivă, să revenim la exemplul de mai sus. Cele 7 fotografii ale lui Alice sunt de fapt 7 dovezi. Acum luați în considerare îmbinarea lor, astfel încât Alice să poată face fotografia de pe nr. 1, să facă fotografia cu ziarul nr. 2 pe nr. 2 și să facă fotografia cu nr. 2 și ziarul cu nr. 3 pe nr. 3 . fotografie. Prin analogie, Alice a făcut ultima fotografie pe 7 cu fotografia pe 6 și ziarul pe 7 Când alți prieteni văd ultima fotografie pe 7, pot verifica că între 1 și 7 Alice au mers toți în parc. . După cum puteți vedea, cele șapte fotografii de dovadă anterioare au fost comprimate într-una singură. O tehnică cheie în acest proces este „fotografiile care conțin fotografii”, ceea ce echivalează cu imbricarea recursivă a fotografiilor anterioare în fotografiile ulterioare. Acest lucru este diferit de a aduna multe fotografii împreună și apoi de a face o singură fotografie. Trucul de demonstrare recursiv al zkRollup poate reduce semnificativ dimensiunea probei. În mod specific, fiecare tranzacție va genera o dovadă. Presupunem că circuitul de calcul al tranzacției inițial este C0, P0 este dovada corectitudinii lui C0, V0 este procesul de calcul al verificării P0, iar dovezitorul (Prover) convertește, de asemenea, V0 în The corespunzătoare. circuitul este notat ca C0'. În acest moment, pentru procesul de calcul al probei C1 al unei alte tranzacții, circuitele lui C0’ și C1 pot fi îmbinate. în același timp se realizează corectitudinea unei tranzacții, adică se realizează compresia.Privind înapoi la procesul de mai sus, putem constata că principiul compresiei este de a converti procesul de verificare într-un circuit și apoi de a genera o „dovadă a dovezii”. Deci, din această perspectivă, este o operație care poate fi continuu recursivă , deci numită și o dovadă recursivă. Figura 2: Schema de dovezi recursive utilizată de Halo2 și Stark Schema de recursire a probelor utilizată de Halo2 și STARK poate genera dovezi în paralel și poate îmbina mai multe dovezi, astfel încât corectitudinea execuțiilor mai multor tranzacții să poată fi verificată în timp ce se verifică o valoare a probei poate comprima costul general de calcul și poate îmbunătăți foarte mult eficiența sistemului. Cu toate acestea, o astfel de optimizare rămâne încă la nivelul superior al algoritmului de demonstrare a cunoștințelor zero. Pentru a îmbunătăți în continuare eficiența, avem nevoie de optimizare și inovare de nivel inferior Algoritmul FOAKS proiectat de Fox face acest lucru prin aplicarea ideii recursive Am ajuns la acest punct. Schema de recursivitate dovedită folosită de FOAKS este un proiect zkRollup bazat pe zkEVM la Fox Tech. În sistemul său de demonstrare, folosește și tehnica demonstrației recursive, dar conotația este diferită de metoda recursivă menționată mai sus Principala diferență este că Fox folosește ideea recursiunii în interiorul unei dovezi. Pentru a exprima ideea de bază a dovezii recursive utilizate de Fox, care este reducerea continuă a problemei de demonstrat până când problema redusă este suficient de simplă, trebuie să dăm un alt exemplu. În exemplul de mai sus, Alice a făcut o fotografie pentru a demonstra că a mers la Fox Park într-o anumită zi, așa că Bob a prezentat diferite sugestii. El a crezut că problema de a dovedi că Alice a mers în parc se poate reduce la a demonstra că mobilul lui Alice. telefonul a mers în parc Iar demonstrarea acestei chestiuni se poate reduce la a demonstra că telefonul mobil al lui Alice se află în sfera parcului. Așadar, pentru a dovedi că Alice a fost în parc, trebuie doar să trimită o locație folosind telefonul ei în timp ce era în parc. În acest fel, dimensiunea dovezii se schimbă de la fotografia originală (o date cu dimensiuni foarte mari) la date tridimensionale (latitudine, longitudine și timp), economisind efectiv costuri. Acest exemplu nu este pe deplin potrivit, deoarece unii oameni ar putea pune la îndoială faptul că telefonul mobil al lui Alice a fost la Fox Park nu înseamnă că Alice însăși a fost acolo, dar în situații reale, acest proces de reducere este riguros din punct de vedere matematic.Mai exact, utilizarea dovezii recursive a lui Fox este recursiunea la nivel de circuit. Când efectuăm demonstrația de cunoștințe zero, vom scrie problema care trebuie demonstrată într-un circuit și apoi vom calcula câteva ecuații care trebuie îndeplinite prin circuit. În loc să arătăm că aceste ecuații sunt satisfăcute, scriem din nou aceste ecuații în circuite și așa mai departe, până când în cele din urmă ecuația pentru a demonstra că sunt satisfăcute devine suficient de simplă încât să o putem demonstra cu ușurință direct. Din acest proces putem vedea că a face acest lucru este mai aproape de sensul de „recursiune”. Este de menționat că nu toți algoritmii pot folosi această tehnică recursivă. Se presupune că fiecare recursivitate va transforma demonstrația cu o complexitate de O(n) într-o demonstrație a lui O(f(n)), iar calculul recursivului. procesul în sine Complexitatea este O(g(n)), apoi după o recursivitate complexitatea totală de calcul devine O1(n)=O(f(n))+O(g(n)), iar după două recursiuni devine O2 (n )=O(f(f(n)))+O(g(n))+O(g(f(n))), după trei ori este O3(n)=O(f(f( f(n)) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),... și așa mai departe. Prin urmare, numai atunci când f și g sunt două funcții corespunzătoare caracteristicilor algoritmului care satisfac Ok(n) pentru un anumit k. Figura 3: Schema de demonstrare recursivă utilizată de ZK-FOAKS în aplicațiile cu dovezi zero cunoștințe Una dintre chei, demonstrarea complexității va deveni din ce în ce mai importantă pe măsură ce lucrurile care trebuie demonstrate devin din ce în ce mai complexe, în special în scenariile de aplicații ZK gigantice precum zkEVM, complexitatea dovezii va afecta performanța. și performanța produsului. Experiența utilizatorului are un impact decisiv. Printre numeroasele metode de reducere a complexității probei finale, optimizarea algoritmului de bază este cea mai importantă Fox a conceput o schemă de demonstrare recursivă ingenioasă, bazată pe cei mai de ultimă oră, și a folosit această tehnologie pentru a crea cea mai potrivită soluție. pentru zkEVM Se așteaptă ca algoritmul ZK-FOAKS să devină lider de performanță în lumea zkRollup. Referințe https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 Acest articol este dintr-o trimitere și nu reprezintă punctele de vedere ale BlockBeats