Původní název: "How to design an exquisite proof recursion scheme" Původní autor: Lin Yanxi, CTO společnosti Fox Tech; Meng Xuanji, hlavní vědec společnosti Fox Tech Předmluva: Téměř všechny problémy, se kterými se setkáváme ve stopách zkRollup a zkEVM, mezi nimi jsou v podstatě algoritmické problémy. Hlavním důvodem, proč je hardwarová akcelerace ZKP často zmiňována, je to, že současné algoritmy jsou obecně pomalé. Abychom se nedostali do trapné situace „algoritmus nestačí, hardware to vynahradí“, měli bychom problém řešit algoritmicky. Klíčem k vyřešení tohoto problému je navržení vynikajícího schématu důkazu opakování. S neustálým rozvojem chytrých kontraktů postupně vychází stále více webových3 aplikací a objem transakcí tradiční vrstvy 1, jako je Ethereum, rychle roste a kdykoli může dojít k přetížení. Jak dosáhnout vyšší efektivity a zároveň zajistit bezpečnost, kterou poskytuje vrstva 1, se stalo naléhavým problémem, který je třeba vyřešit. Pro Ethereum používá zkRollup algoritmus důkazu s nulovými znalostmi jako základní komponent pro přesun drahých výpočtů, které je původně třeba provést na vrstvě 1 mimo řetězec, a poskytnout důkaz o správnosti provádění řetězci. Track zahrnuje především projekty jako StarkWare, zkSync, Scroll a Fox Tech. Ve skutečnosti jsou při návrhu zkRollup kladeny velmi vysoké požadavky na účinnost: doufáme, že předložená hodnota důkazu je dostatečně malá, aby se snížila výpočetní zátěž vrstvy 1. Aby bylo možné získat dostatečně malou délku důkazu, různé projekty zkRollup vylepšují algoritmy a návrhy architektury, například Fox vyvinul svůj vlastní důkazní algoritmus FOAKS založený na nejnovějším algoritmu důkazu s nulovými znalostmi, aby získal optimální dobu důkazu a délku důkazu. Navíc ve fázi ověřování důkazu je nejtriviálnější metodou lineární generování důkazů a jejich postupné ověřování. Aby se zlepšila efektivita, první věc, kterou každého napadne, je sbalit více důkazů do jednoho důkazu, což se běžně nazývá agregace důkazů (Proof Aggregation). Intuitivně řečeno, ověřování důkazů generovaných zkEVM je lineární proces a ověřovatel (Verifier) ​​musí postupně ověřit každou vygenerovanou hodnotu důkazu. Účinnost této ověřovací metody je však relativně nízká a komunikační režie relativně velká.Pro scénář zkRollup znamená vyšší režie na straně ověřovatele více výpočtů na vrstvě Layer1, což také povede k vyšším poplatkům za plyn.Nejprve se podívejme na příklad: Alice chce světu dokázat, že šla do Fox Parku od 1. do 7. tohoto měsíce. K tomu se může každý den od 1. do 7. dne vyfotit v parku s denními novinami a balíček těchto 7 fotografií se stane důkazem. Obrázek 1: Obecné schéma agregace důkazů. Ve výše uvedeném příkladu je vložení 7 fotografií přímo do obálky agregací důkazů v intuitivním smyslu. Ve skutečných situacích to odpovídá propojení různých důkazů dohromady a jejich lineárnímu ověřování v pořadí, tj. Ověřte první důkaz, pak druhý důkaz a další důkazy. Problém je v tom, že tento přístup nezmění velikost důkazu ani čas důkazu, má stejný účinek jako dokazování a ověřování jeden po druhém. Pokud chcete dosáhnout komprese logaritmického prostoru na úrovni, musíte použít rekurzivní důkaz (Proof Recursion) uvedený níže. Důkazové rekurzivní schéma používané Halo2 a STARK Abychom lépe vysvětlili, co je rekurzivní důkaz, vraťme se k výše uvedenému příkladu. Aliciných 7 fotek je vlastně 7 důkazů. Nyní zvažte jejich sloučení, aby Alice mohla vyfotit na č. 1, vyfotit se s novinami č. 2 na č. 2 a vyfotit č. 2 a novinami č. 3 na č. 3 fotografie. Analogicky Alice vyfotila poslední fotku 7. s fotkou 6. a novinami 7. Když ostatní kamarádi uvidí poslední fotku 7., mohou si ověřit, že mezi 1. a 7. Alice šli všichni do parku . Jak vidíte, předchozích sedm důkazových fotografií bylo zkomprimováno do jedné. Klíčovou technikou v tomto procesu jsou "fotografie obsahující fotografie", což je ekvivalentní rekurzivnímu vnořování předchozích fotografií do následujících fotografií. To je něco jiného, ​​než když poskládáte mnoho fotek dohromady a pak uděláte jednu fotku. Rekurzivní nátiskový trik zkRollup může výrazně snížit velikost nátisku. Konkrétně každá transakce vygeneruje důkaz. Předpokládáme, že původní obvod výpočtu transakce je C0, P0 je důkaz správnosti C0, V0 je proces výpočtu ověření P0 a dokazovatel (Prover) také převede V0 na odpovídající obvod je označen jako C0'. V tomto okamžiku pro proces výpočtu důkazu C1 jiné transakce mohou být obvody C0' a C1 sloučeny. Tímto způsobem, jakmile je ověřen důkaz správnosti P1 sloučeného obvodu, je to ekvivalentní ověření výše uvedených dvou na Současně je dosaženo správnosti transakce, to znamená komprese.Když se podíváme zpět na výše uvedený proces, můžeme zjistit, že principem komprese je převést proces verifikace a důkazu na obvod a poté vygenerovat „důkaz důkazu“. Takže z tohoto pohledu je to operace, která může být nepřetržitě rekurzivní, takže se také nazývá rekurzivní důkaz. Obrázek 2: Schéma rekurzivního důkazu používané Halo2 a Stark Schéma Proof Recursion používané Halo2 a STARK může generovat důkazy paralelně a sloučit více důkazů, takže správnost provedení více transakcí může být ověřena při ověření jedné hodnoty důkazu. může snížit režii výpočtu a výrazně zlepšit efektivitu systému. Taková optimalizace však stále zůstává na úrovni nad konkrétním algoritmem důkazu s nulovými znalostmi. Abychom dále zlepšili efektivitu, potřebujeme optimalizaci a inovaci na nižší úrovni. Algoritmus FOAKS navržený společností Fox to dělá aplikací rekurzivní myšlenky uvnitř důkazu Dostal jsem se do tohoto bodu. Osvědčené schéma rekurze používané FOAKS je projekt zkRollup založený na zkEVM ve Fox Tech. Ve svém důkazním systému také používá techniku ​​rekurzivního důkazu, ale konotace je odlišná od výše uvedené rekurzivní metody. Hlavní rozdíl je v tom, že Fox používá myšlenku rekurze uvnitř důkazu. Abychom vyjádřili základní myšlenku rekurzivního důkazu používaného Foxem, kterým je neustále redukovat problém, který má být dokázán, dokud není redukovaný problém dostatečně jednoduchý, musíme uvést další příklad. Ve výše uvedeném příkladu Alice pořídila fotografii, aby dokázala, že šla do Fox Parku v určitý den, takže Bob předložil různé návrhy. Věřil, že problém dokázat, že Alice šla do parku, lze zredukovat na prokázání, že Alicin mobil Telefon šel do parku. A dokazování této záležitosti lze zredukovat na prokázání, že se Aliciin mobilní telefon nachází v areálu parku. Takže, aby dokázala, že Alice byla v parku, stačí poslat polohu pomocí telefonu, když byla v parku. Tímto způsobem se velikost nátisku změní z původní fotografie (velmi velkorozměrná data) na 3rozměrná data (zeměpisná šířka, délka a čas), což efektivně šetří náklady. Tento příklad není zcela vhodný, protože někteří lidé mohou pochybovat o tom, že skutečnost, že Alicin mobilní telefon byl ve Fox Parku, neznamená, že tam byla sama Alice, ale ve skutečných situacích je tento proces redukce matematicky přísný.Konkrétně použití Foxova rekurzivního důkazu je rekurze na úrovni obvodu. Když provádíme důkaz s nulovými znalostmi, zapíšeme problém, který má být dokázán, do obvodu a poté vypočítáme nějaké rovnice, které je třeba obvodem splnit. Místo abychom ukázali, že jsou tyto rovnice splněny, zapíšeme tyto rovnice znovu do obvodů a tak dále, dokud se nakonec rovnice k prokázání, že jsou splněny, nestane natolik jednoduchou, že ji můžeme snadno dokázat přímo. Z tohoto procesu můžeme vidět, že tak učinit je blíže významu „rekurze“. Za zmínku stojí, že ne všechny algoritmy mohou používat tuto rekurzivní techniku. Předpokládá se, že každá rekurze změní důkaz o složitosti O(n) na důkaz O(f(n)) a výpočet rekurzivní samotný proces Složitost je O(g(n)), poté se po jedné rekurzi celková výpočetní složitost stane O1(n)=O(f(n))+O(g(n)) a po dvou rekurzích se stane O2 (n )=O(f(f(n)))+O(g(n))+O(g(f(n))), po třech případech je to O3(n)=O(f(f( f(n)) )))+O(g(n))+O(g(f(n)))+O(g(f(f(n)))),..., a tak dále. Tedy pouze když f a g jsou dvě funkce odpovídající charakteristikám algoritmu, které splňují Ok(n) pro určité k. Obrázek 3: Schéma rekurzivního důkazu používané ZK-FOAKS Závěr Složitost důkazu byla vždy nejdůležitější v aplikacích důkazů s nulovými znalostmi. Jedním z klíčů je dokazování složitosti bude stále důležitější, protože věci, které je třeba dokázat, budou stále složitější, zejména v obřích scénářích aplikací ZK, jako je zkEVM, bude složitost důkazu ovlivňovat výkon a výkon produktu Rozhodující vliv má uživatelská zkušenost. Mezi mnoha metodami ke snížení složitosti konečného důkazu je nejdůležitější optimalizace základního algoritmu Fox navrhl vynikající rekurzivní schéma důkazu založené na nejmodernějších algoritmech a použil tuto technologii k vytvoření řešení, které je nejvhodnější pro zkEVM. Očekává se, že algoritmus ZK-FOAKS se stane lídrem ve výkonu ve světě zkRollup. Reference https://blog.csdn.net/weixin_44383880/article/details/126338813 https://blog.csdn.net/freedomhero/article/details/126727033 Tento článek pochází z příspěvku a nereprezentuje názory BlockBeats