Původní název: "Exploring circle STARKs"
Napsal: Vitalik Buterin, spoluzakladatel Etherea
Sestavil: Chris, Techub News
Předpokladem pro pochopení tohoto článku je, že již rozumíte základním principům SNARKů a STARKů. Pokud s tím nejste obeznámeni, doporučuji vám přečíst si prvních několik částí tohoto článku, abyste porozuměli základům.
V posledních letech je trendem v návrhu protokolu STARK používat menší pole. Nejstarší produkční implementace STARKů používaly 256bitová pole, tj. modulo aritmetiku na velkých číslech (jako je 21888...95617), díky čemuž byly tyto protokoly kompatibilní se signaturami založenými na eliptických křivkách. Efektivita tohoto návrhu je však za normálních okolností poměrně nízká, zpracování a výpočet těchto velkých čísel nemá praktické využití a bude plýtvat velkým množstvím výpočetního výkonu, jako je zpracování X (představuje určité číslo) a zpracování čtyřnásobku X. , zpracování Vyžaduje se pouze jedna devítina času výpočtu. Aby tento problém vyřešili, STARKové se začali přesouvat do menších polí: nejprve Zlatovláska, poté Mersenne31 a BabyBear.
Tento posun zlepšil rychlost důkazu, například Starkware je schopen prokázat 620 000 hashů Poseidon2 za sekundu na notebooku M3. To znamená, že pokud jsme ochotni důvěřovat Poseidon2 jako hashovací funkci, můžeme vyřešit obtížný problém vývoje efektivního ZK-EVM. Jak tedy tyto technologie fungují? Jak se tyto důkazy staví na menších polích? Jak jsou tyto protokoly v porovnání s řešeními jako Binius? Tento článek prozkoumá tyto detaily a zaměří se konkrétně na schéma zvané Circle STARKs (implementované ve Starkware's stwo, Polygon's plonky3 a mé vlastní verzi v Pythonu), které mají jedinečnou vlastnost, že jsou kompatibilní s poli Mersenne31.
Časté problémy při práci s menšími matematickými obory
Velmi důležitým trikem při vytváření důkazů na bázi hash (nebo důkazů jakéhokoli druhu) je možnost nepřímo ověřit vlastnosti polynomu vyhodnocením polynomu v náhodných bodech. Tento přístup může značně zjednodušit proces důkazu, protože vyhodnocení v náhodných bodech je obvykle mnohem jednodušší než zabývat se celým polynomem.
Předpokládejme například, že systém důkazů vyžaduje, abyste vygenerovali závazek k polynomu A, který musí splňovat A^3 (x) + x - A (\omega*x) = x^N (velmi běžný v ZK -SNARK protokol proof typ). Protokol by vás mohl požádat, abyste vybrali náhodnou souřadnici ? a dokázali, že A (r) + r - A (\omega*r) = r^N. Pak postupujte zpětně k A (r) = c a dokážete, že Q = \frac {A - c}{X - r} je polynom.
Pokud předem znáte podrobnosti nebo vnitřní prvky protokolů, možná budete schopni najít způsoby, jak je obejít nebo hacknout. Konkrétní akce nebo metody, jak toho dosáhnout, mohou být uvedeny dále. Například, abyste splnili rovnici A (\omega * r), můžete nastavit A (r) na 0 a nechat A je přímka procházející těmito dvěma body.
Abychom těmto útokům zabránili, musíme zvolit r poté, co útočník poskytl A (Fiat-Shamir je technika používaná ke zvýšení zabezpečení protokolu nastavením určitých parametrů na nějakou hash hodnotu, aby se zabránilo útokům. Zvolte Parametry musí pocházet z dostatečně velké nastavit tak, aby útočník nemohl předvídat nebo uhodnout tyto parametry, čímž se zvyšuje bezpečnost systému.
V protokolech založených na eliptických křivkách a STARKech v období 2019 je problém jednoduchý: všechny naše matematické operace se provádějí na 256bitových číslech, takže můžeme zvolit r jako náhodné 256bitové číslo, takže . Ve STARKech na menších polích však narážíme na problém: na výběr jsou jen asi 2 miliardy možných hodnot r, takže útočníkovi, který chce zfalšovat důkaz, stačí zkusit 2 miliardykrát, což je hodně práce, ale pro odhodlaného útočníka je to stále možné!
Existují dvě řešení tohoto problému:
Proveďte více náhodných kontrol
pole rozšíření
Nejjednodušší a nejúčinnější způsob, jak provést více náhodných kontrol, je: místo kontroly na jedné souřadnici opakujte kontrolu na čtyřech náhodných souřadnicích. To je teoreticky možné, ale existují problémy s účinností. Pokud máte co do činění s polynomem stupně menšího než určitá hodnota a operujete na doméně určité velikosti, útočník může ve skutečnosti vytvořit škodlivý polynom, který v těchto místech vypadá normálně. Zda se jim podaří úspěšně prolomit protokol, je tedy pravděpodobnostní otázka, takže je třeba zvýšit počet kol kontrol, aby se zvýšila celková bezpečnost a zajistila se účinná obrana útočníků před útoky.
To vede k dalšímu řešení: rozšířená pole jsou jako komplexní čísla, ale jsou založena na konečných polích. Zavedeme novou hodnotu, označenou α\alphaα, a prohlásíme, že splňuje určitý vztah, například α2=nějaká hodnota\alpha^2 = \text {nějaká hodnota}α2=nějaká hodnota. Tímto způsobem vytváříme novou matematickou strukturu schopnou provádět složitější operace na konečných polích. V této rozšířené doméně se výpočet násobení stává násobením pomocí nové hodnoty α\alphaα. Nyní můžeme pracovat s páry hodnot v rozšířené doméně, nejen s jednotlivými čísly. Pokud například pracujeme na poli, jako je Mersenne nebo BabyBear, takové rozšíření nám umožňuje mít více hodnotových možností, čímž se zvyšuje bezpečnost. Pro další zvětšení velikosti pole můžeme opakovaně aplikovat stejnou techniku. Protože jsme již použili α\alphaα, musíme definovat novou hodnotu, která je v Mersenne31 reprezentována volbou α\alphaα tak, že α2=nějaká hodnota\alpha^2 = \text {nějaká hodnota}α2=nějaká hodnota.
Kód (můžete jej vylepšit pomocí Karatsuba)
Rozšířením domény nyní máme na výběr dostatek hodnot, které splňují naše bezpečnostní potřeby. Pokud máte co do činění s polynomy stupně menšího než ddd, poskytuje to 104 bitů zabezpečení na kolo. To znamená, že máme dostatečné zabezpečení. Je-li vyžadována vyšší úroveň zabezpečení, například 128 bitů, můžeme k protokolu přidat další výpočetní práci pro zvýšení zabezpečení.
Rozšířené domény se ve skutečnosti používají pouze v protokolech FRI (Fast Reed-Solomon Interactive) a dalších scénářích, které vyžadují náhodné lineární kombinace. Většina matematiky se stále provádí na základních polích, což jsou obvykle pole modulo ppp nebo qqq. Téměř všechna hašovaná data jsou také provedena na podkladových polích, takže jsou hašovány pouze čtyři bajty na hodnotu. Tím se využívá efektivita malých polí a zároveň umožňuje použití větších polí, když je potřeba vylepšení zabezpečení.
Pravidelné PÁ
Při stavbě SNARK nebo STARK je prvním krokem obvykle aritmetizace. Jedná se o převod jakéhokoli výpočetního problému na rovnici, kde některé z proměnných a koeficientů jsou polynomy. Konkrétně tato rovnice bude typicky vypadat jako P (X,Y,Z)=0P (X,Y,Z) = 0P (X,Y,Z)=0, kde P je polynom a Z je daný parametr a řešitel musí poskytnout hodnoty X a Y. Jakmile máte takovou rovnici, řešení této rovnice odpovídá řešení základního výpočetního problému.
Abyste dokázali, že máte řešení, musíte prokázat, že hodnoty, se kterými přicházíte, jsou skutečně legitimní polynomy (na rozdíl od zlomků nebo vypadají jako jeden polynom na některých místech a jako jiný polynom jinde atd.), A tyto polynomy mají určitý maximální stupeň. K tomu používáme stochastickou lineární kombinační techniku aplikovanou postupně:
Předpokládejme, že máte ohodnocení polynomu A a chcete dokázat, že jeho stupeň je menší než 2^{20}
Uvažujme polynom B (x^2) = A (x) + A (-x), C (x^2) = \frac {A (x) - A (-x)}{x}
D je náhodná lineární kombinace B a C, to znamená D=B+rCD = B + rCD=B+rC, kde r je náhodný koeficient.
V podstatě se stane, že B izoluje sudé koeficienty A a izoluje liché koeficienty. Vzhledem k B a C můžete obnovit původní polynom A: A (x) = B (x^2) + xC (x^2). Pokud je stupeň A skutečně menší než 2^{20}, pak stupně B a C budou stupněm A a stupněm A mínus 1, v tomto pořadí. Protože kombinace sudých a lichých členů nezvyšuje stupeň. Protože D je náhodná lineární kombinace B a C, stupeň D by měl být také stupněm A, což vám umožňuje použít stupeň D k ověření, že stupeň A splňuje požadavky.
Za prvé, FRI zjednodušuje proces verifikace tím, že redukuje problém dokazování polynomu se stupněm d na problém dokazování polynomu se stupněm d/2. Tento proces lze mnohokrát opakovat, čímž se problém pokaždé zjednoduší na polovinu.
FRI funguje tak, že tento proces zjednodušení opakuje. Pokud například začnete dokazováním, že stupeň polynomu je d, pomocí řady kroků nakonec dokážete, že stupeň polynomu je d/2. Po každém zjednodušení se stupeň výsledného polynomu postupně snižuje. Pokud výstup fáze nemá očekávaný polynomický stupeň, pak toto kolo kontrol selže. Pokud se někdo pokusí touto technikou protlačit polynom, který není stupně d, pak ve druhém kole výstupu jeho stupeň s určitou pravděpodobností nesplní očekávání a ve třetím kole bude spíše nekonzistentní, a nakonec Kontrola selže. Tento návrh může účinně detekovat a odmítnout vstup, který nesplňuje požadavky. Soubor dat pravděpodobně projde validací FRI, pokud se na většině míst rovná polynomu stupně d. Aby však útočník mohl sestavit takový soubor dat, potřebuje znát skutečné polynomy, takže i mírně chybný důkaz ukazuje, že dokazovač je schopen vygenerovat „skutečný“ důkaz.
Podívejme se blíže na to, co se zde děje, a na vlastnosti potřebné k tomu, aby to všechno fungovalo. V každém kroku snížíme stupeň polynomu na polovinu a také zmenšíme množinu bodů (množinu bodů, která nás zajímá) na polovinu. První z nich je klíčem ke správnému fungování protokolu FRI (Fast Reed-Solomon Interactive). Díky tomu algoritmu běží extrémně rychle: protože velikost každého kola je snížena na polovinu ve srovnání s předchozím kolem, celkové výpočetní náklady jsou O (N) místo O (N*log (N)).
Pro dosažení progresivní redukce domény se používá mapování dva ku jedné, tj. každý bod je mapován do jednoho ze dvou bodů. Toto mapování nám umožňuje zmenšit velikost datové sady na polovinu. Důležitou výhodou tohoto mapování dva ku jedné je, že je opakovatelné. To znamená, že když použijeme toto mapování, výsledná sada výsledků si zachová stále stejné vlastnosti. Předpokládejme, že začneme s multiplikativní podskupinou. Tato podskupina je množina S, kde každý prvek x má násobek 2x také v množině. Pokud odmocníte množinu S (tj. namapujete každý prvek x v množině na x^2), nová množina S^2 si zachová stejné vlastnosti. Tato operace nám umožňuje pokračovat ve snižování velikosti datové sady, dokud nakonec nezůstane pouze jedna hodnota. Zatímco teoreticky bychom mohli zmenšit soubor dat pouze na jednu hodnotu, v praxi se obvykle zastavíme před dosažením menšího souboru.
Tuto operaci si můžete představit jako proces natažení úsečky (například úsečky nebo oblouku) po obvodu kruhu tak, aby se po kružnici dvě otáčky otočily. Pokud je například bod na obvodu x stupňů, po této operaci se posune na 2x stupňů. Každý bod na kružnici od 0 do 179 stupňů má odpovídající bod od 180 do 359 stupňů a tyto dva body se budou shodovat. To znamená, že když mapujete bod od x stupňů do 2x stupňů, bude se shodovat s pozicí na x+180 stupňů. Tento proces lze opakovat. To znamená, že tuto operaci mapování můžete použít vícekrát, pokaždé, když přesunete body na kružnici do jejich nových pozic.
Aby byla technika mapování účinná, velikost původní multiplikativní podskupiny musí mít jako faktory velké mocniny 2. BabyBear je systém s určitým modulem tak, že jeho maximální multiplikativní podskupina obsahuje všechny nenulové hodnoty, takže velikost podskupiny je 2k−1 (kde k je počet číslic v modulu). Podskupiny této velikosti se dobře hodí pro výše uvedenou techniku, protože umožňuje účinné snížení stupně polynomu opakovanou aplikací operace mapování. V BabyBear můžete vybrat podskupinu o velikosti 2^k (nebo prostě použít celou sadu), pak použít metodu FRI pro postupné snížení stupně polynomu na 15 a na konci zkontrolovat stupeň polynomu. Tato metoda využívá vlastností modulu a velikosti multiplikativní podskupiny, díky čemuž je proces výpočtu velmi efektivní. Mersenne31 je další systém, jehož modul je nějaká hodnota taková, že velikost multiplikativní podskupiny je 2^31 - 1. V tomto případě má velikost multiplikativní podskupiny jako faktor pouze mocninu 2, což umožňuje její dělení 2 pouze jednou. Následné zpracování již není vhodné pro výše uvedené techniky, to znamená, že není možné použít FFT pro účinnou redukci polynomiálního stupně jako BabyBear.
Pole Mersenne31 se dobře hodí pro aritmetické operace na stávajících 32bitových operacích CPU/GPU. Díky svým modulovým vlastnostem (jako je 2^{31} - 1) lze mnoho operací dokončit pomocí efektivních bitových operací: pokud výsledek sečtení dvou čísel překročí modul, lze výsledek posunout operací modulu a snížit jej. do vhodného rozsahu. Přemístění je velmi efektivní operace. Při operacích násobení se ke zpracování výsledku používají speciální instrukce CPU (často nazývané instrukce posunu vysokého řádu). Tyto instrukce mohou efektivně vypočítat část násobení vyššího řádu, a tím zlepšit efektivitu operace. V doméně Mersenne31 jsou aritmetické operace přibližně 1,3krát rychlejší než v doméně BabyBear díky výše popsaným vlastnostem. Mersenne31 poskytuje vyšší výpočetní efektivitu. Pokud bude možné implementovat FRI v doméně Mersenne31, výrazně to zlepší výpočetní efektivitu a zefektivní aplikace FRI.
Zakroužkujte PÁ
To je na Kruhových STARKech to nejhezčí, protože s prvočíslem p můžete najít populaci velikosti p, která má podobné vlastnosti dva ku jedné. Tato populace se skládá ze všech bodů, které splňují určité podmínky, například množina bodů, kde x^2 mod p se rovná určité hodnotě.
Tyto body se řídí aditivním vzorem, který vám může připadat povědomý, pokud jste v poslední době dělali něco souvisejícího s trigonometrií nebo komplexním násobením.
(x_1, y_1) + (x_2, y_2) = (x_1x_2 - y_1y_2, x_1y_2 + x_2y_1)
Zdvojená forma je:
2 * (x, y) = (2x^2 - 1, 2xy)
Nyní se zaměřme na liché body na tomto kruhu:
Nejprve konvergujeme všechny body k přímce. Ekvivalentní forma vzorců B (x²) a C (x²), kterou používáme v běžném FRI, je:
f_0 (x) = \frac {F (x,y) + F (x,-y)}{2}
Pak můžeme provádět náhodné lineární kombinace, abychom získali jednorozměrný polynom P(x) definovaný přes podmnožinu x-čar:
Počínaje druhým kolem se mapování mění:
f_0 (2x^2-1) = \frac {F (x) + F (-x)}{2}
Toto mapování ve skutečnosti pokaždé zmenší velikost výše uvedené množiny na polovinu, děje se zde to, že každé x představuje dva body v určitém smyslu: (x, y) a (x, -y). A (x → 2x^2 - 1) je výše uvedené pravidlo zdvojení bodu. Proto převedeme x-ové souřadnice dvou protilehlých bodů na kružnici na x-ové souřadnice násobeného bodu.
Pokud například vezmeme druhou hodnotu na kruhu zprava, 2, a použijeme zobrazení 2 → 2 (2^2) - 1 = 7, dostaneme jako výsledek 7. Pokud se vrátíme k původní kružnici, (2, 11) je třetí bod zprava, takže se zdvojnásobí, že dostaneme šestý bod zprava, což je (7, 13).
To mohlo být provedeno ve dvou rozměrech, ale provoz v jednom rozměru činí proces efektivnější.
Zakroužkujte FFT
Algoritmus úzce související s FRI je FFT, který převádí n hodnocení polynomu stupně menšího než n na n koeficientů tohoto polynomu. Proces FFT je podobný FRI, kromě toho, že místo generování náhodných lineárních kombinací f_0 a f_1 v každém kroku na nich FFT rekurzivně provádí FFT poloviční velikosti a bere výstup FFT (f_0) jako sudé koeficienty. FFT (f_1) jako liché koeficienty.
Kruhové skupiny také podporují FFT, které jsou konstruovány podobným způsobem jako FRI. Klíčový rozdíl je však v tom, že Circle FFT (a Circle FRI) se zabývají objekty, které nejsou striktně polynomy. Místo toho jsou to, co se matematicky nazývá Riemann-Rochovy prostory: v tomto případě jsou polynomy modulo kruhové ( x^2 + y^2 - 1 = 0 ). To znamená, že jakýkoli násobek x^2 + y^2 - 1 považujeme za nulu. Jiný způsob, jak si to představit, je: povolíme pouze umocnění y: jakmile se objeví člen y^2, nahradíme jej 1 - x^2 .
To také znamená, že výstupy koeficientů pomocí Circle FFT nejsou monomiály jako běžné FRI (například pokud normální FRI výstupy [6, 2, 8, 3], pak víme, že to znamená P (x) = 3x^3 + 8x ^2 + 2x + 6). Naproti tomu koeficienty kruhové FFT jsou specifické pro kruhovou FFT bázi: {1, y, x, xy, 2x^2 - 1, 2x^2y - y, 2x^3 - x, 2x^3y - xy, 8x^4 – 8x^2 + 1...}
Dobrou zprávou je, že jako vývojář to můžete téměř úplně ignorovat. STARKs nikdy nevyžaduje, abyste znali koeficienty. Místo toho jednoduše uložíte polynom jako sadu vyhodnocených hodnot v konkrétní doméně. Jediným místem, kde musíte použít FFT, je provést nízkostupňové rozšíření (podobně jako Riemann-Rochovy prostory): zadaných N hodnot, generování k*N hodnot, vše na stejném polynomu. V tomto případě můžete ke generování koeficientů použít FFT, k těmto koeficientům připojit (k-1) n nul a pak použít inverzní FFT k získání větší sady vyhodnocených hodnot.
Kruhové FFT nejsou jediným speciálním typem FFT. Eliptické křivkyFFT jsou výkonnější, protože mohou pracovat na jakémkoli konečném poli (primární pole, binární pole atd.). ECFFT je však složitější a méně efektivní, takže protože můžeme použít kruhovou FFT na p = 2^{31}-1, rozhodli jsme se ji použít.
Odtud se ponoříme do některých obskurnějších detailů, díky kterým se implementace Circle STARK liší od běžných STARKů.
Kvocient
V protokolu STARK je běžnou operací provádění kvocientových operací na konkrétních bodech. Tyto body lze vybrat záměrně nebo náhodně. Chcete-li například dokázat, že P (x) = y, můžete to provést následujícím způsobem:
Vypočítejte podíl: Je-li daný polynom P (x) a konstanta y, vypočítejte podíl Q ={P - y}/{X - x}, kde X je zvolený bod.
Dokažte polynomy: Dokažte, že Q je polynom, nikoli zlomek. Tímto způsobem je dokázáno, že P (x)=y platí.
V protokolu DEEP-FRI jsou navíc body hodnocení náhodně vybírány, aby se snížil počet poboček Merkle, čímž se zlepšila bezpečnost a účinnost protokolu FRI.
Při práci s protokolem STARK skupiny kruhů, protože neexistuje žádná lineární funkce, která by mohla procházet jedním bodem, je třeba použít různé techniky, které nahradí tradiční metodu kvocientové operace. To často vyžaduje navrhování nových algoritmů využívajících jedinečné geometrické vlastnosti kruhových skupin.
V kruhové skupině můžete sestrojit tečnou funkci, která je tečnou k určitému bodu (P_x, P_y), ale tato funkce bude mít násobnost 2 přes bod, to znamená, že polynom se stane násobkem A lineární funkce, která musí splňují přísnější podmínky, než je pouze nula v tomto bodě. Výsledky hodnocení tedy nemůžete jen tak prokázat v jednom bodě. Jak se s tím tedy vypořádáme?
Museli jsme tuto výzvu přijmout a dokázat ji hodnocením ve dvou bodech, čímž jsme přidali fiktivní bod, na který jsme se nemuseli soustředit.
Přímková funkce: ax + by + c. Pokud z ní uděláte rovnici a přinutíte ji, aby se rovnala 0, možná ji poznáte jako čáru v tom, čemu se ve středoškolské matematice říká standardní forma.
Pokud máme polynom P, který se rovná y_1 v x_1 a y_2 v x_2, můžeme zvolit interpolační funkci L, která se rovná y_1 v x_1 a y_2 v x_2. To lze jednoduše vyjádřit jako L = \frac {y_2 - y_1}{x_2 - x_1} \cdot (x - x_1) + y_1.
Potom dokážeme, že P se rovná y_1 v x_1 a y_2 v x_2 odečtením L (činí P - L nulou v obou bodech) a L (tj. lineární funkce mezi x_2 - x_1) Vydělte L, abyste dokázali, že kvocient Q je a polynom.
Mizející polynomy
Ve STARKU vypadá polynomická rovnice, kterou se snažíte dokázat, obvykle jako C (P (x), P ({next} (x))) = Z (x) ⋅ H (x) , kde Z (x) je A polynom rovný nule v celé původní vyhodnocovací doméně. V běžném STARKu je tato funkce x^n - 1. V kruhové STARK je odpovídající funkce:
Z_1 (x, y) = y
Z_2 (x, y) = x
Z_{n+1}(x,y) = (2 * Z_n (x,y)^2) - 1
Všimněte si, že mizející polynom můžete odvodit z funkce skládání: v běžném STARK znovu použijete x → x^2 , zatímco v kruhovém STARK znovu použijete x → 2x^2 - 1 . V prvním kole to však uděláte jinak, protože první kolo je speciální.
Obrácené pořadí bitů
Ve STARKech se polynomy obvykle nevyhodnocují v „přirozeném“ pořadí (např. P (1), P (ω), P (ω2),…, P (ωn−1)), ale v tom, čemu říkám inverzní Uspořádané v obrácené pořadí bitů:
P (\omega^{\frac {3n}{8}})
Pokud nastavíme n=16 a zaměříme se pouze na to, na kterých mocninách ω vyhodnotíme, seznam vypadá takto:
{0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}
Toto třídění má klíčovou vlastnost, že hodnoty seskupené na začátku procesu hodnocení FRI se při třídění stanou sousedícími. Například první krok FRI skupin x a -x. V případě n = 16, ω^8 = -1, což znamená P (ω^i) ) a ( P (-ω^i) = P (ω^{i+8}) \). Jak vidíme, jsou to přesně ty dvojice těsně vedle sebe. Druhý krok FRI skupin P (ω^i), P (ω^{i+4}), P (ω^{i+8}) a P (ω^{i+12}). To je přesně to, co vidíme ve skupinách po čtyřech a tak dále. Díky tomu je FRI prostorově efektivnější, protože vám umožňuje poskytnout Merkleův důkaz pro hodnoty složené dohromady (nebo, pokud složíte k kol najednou, pro všechny hodnoty 2^k).
V kruhu STARKs je struktura skládání mírně odlišná: v prvním kroku spárujeme (x, y) s (x, -y) v dalším kroku spárujeme x s -x; s q a zvolte p a q tak, že Q^i (p) = -Q^i (q), kde Q^i je zobrazení, které se x → 2x^2-1krát opakuje. Pokud uvažujeme o bodech z hlediska jejich polohy na kružnici, pak to v každém kroku vypadá tak, že první bod je spárován s posledním bodem, druhý bod s druhým předposledním bodem a tak dále.
Abychom upravili obrácené pořadí bitů tak, aby odráželo tuto strukturu skládání, musíme obrátit každý bit kromě posledního bitu. Poslední bit si necháme a použijeme ho k rozhodnutí, zda přehodit ostatní bity.
Složení velikosti 16 v obráceném pořadí bitů je následující:
{0, 15, 8, 7, 4, 11, 12, 3, 2, 13, 10, 5, 6, 9, 14, 1}
Pokud se podíváte na kruh z předchozí části, uvidíte, že body 0, 15, 8 a 7 (proti směru hodinových ručiček zprava) jsou (x, y), (x, -y), (-x , - y) a (-x, y), což je přesně to, co potřebujeme.
účinnost
V Circle STARK (a obecně 31bitových primárních STARKech) jsou tyto protokoly velmi účinné. Výpočet ověřený v Circle STARK obvykle zahrnuje několik typů výpočtů:
1. Nativní aritmetika: používá se pro obchodní logiku, jako je počítání.
2. Nativní aritmetika: používá se v kryptografii, jako jsou hashovací funkce jako Poseidon.
3. Parametry vyhledávání: Obecná a efektivní metoda výpočtu, která implementuje různé výpočty čtením hodnot z tabulky.
Klíčovým měřítkem efektivity je, zda plně využíváte celý prostor k užitečné práci ve výpočetním trasování, nebo zda necháváte spoustu volného místa. V SNARKech pro velká pole je často spousta volného místa: obchodní logika a vyhledávací tabulky často zahrnují výpočty na malých číslech (tato čísla bývají menší než N, kde N je celkový počet kroků ve výpočtu, takže v praxe méně než 2^{25}), ale stále musíte zaplatit náklady na použití pole o velikosti 2^{256} bitů. Zde je velikost pole 2^{31}, takže promarněný prostor není velký. Nízká aritmetická složitost hash navržená pro SNARK (jako je Poseidon) plně využívá každý bit každého čísla ve stopě v jakémkoli poli.
Binius je lepší řešení než Circle STARK, protože umožňuje kombinovat pole různých velikostí, což vede k efektivnějšímu balení bitů. Binius také poskytuje možnost provádět 32bitové sčítání bez režie vyhledávacích tabulek. Tyto výhody však přicházejí (podle mého názoru) za cenu složitějšího konceptu, zatímco Circle STARK (a běžné STARK založené na BabyBear) jsou koncepčně mnohem jednodušší.
Závěr: Moje myšlenky na Circle STARKs
Kruhové STARKy nejsou pro vývojáře o nic složitější než STARKy. Během procesu implementace jsou tři výše uvedené problémy v zásadě rozdíly od konvenčních FRI. Přestože matematika za polynomy, na kterých Circle FRI pracuje, je velmi složitá a trvá nějakou dobu, než ji pochopíte a pochopíte, tato složitost je ve skutečnosti skryta natolik, že ji vývojáři přímo nepociťují.
Porozumění Circle FRI a Circle FFTs může být také vstupní branou k pochopení dalších speciálních FFT: zejména binárních doménových FFT, jako jsou ty, které používal Binius a dříve LibSTARK, ale také některých složitějších konstrukcí, jako jsou FFT eliptické křivky, tyto FFT Mapování -to-many lze dobře kombinovat s operacemi s body eliptickými křivkami.
V kombinaci s technologiemi Mersenne31, BabyBear a binárními doménovými technologiemi, jako je Binius, skutečně cítíme, že se blížíme k limitům účinnosti základní vrstvy STARKs. V tuto chvíli předpovídám, že směr optimalizace STARK se zaměří na následující body:
Aritmetizace hashovacích funkcí, podpisů atd. pro maximalizaci efektivity: Optimalizujte základní kryptografická primitiva, jako jsou hashovací funkce a digitální podpisy, do jejich nejúčinnějších forem, aby mohly dosáhnout optimálního výkonu při použití v nátiskech STARK. To znamená speciální optimalizace pro tato primitiva pro snížení výpočetní náročnosti a zvýšení efektivity.
Rekurzivní konstrukce umožňující větší paralelizaci: Rekurzivní konstrukce se týká rekurzivní aplikace procesu STARK proof na různé úrovně, čímž se zvyšují možnosti paralelního zpracování. Tímto způsobem lze efektivněji využívat výpočetní zdroje a urychlit proces dokazování.
Aritmetizace virtuálních strojů pro zlepšení zkušeností vývojářů: Aritmetizace virtuálních strojů umožňuje vývojářům vytvářet a spouštět výpočetní úlohy efektivněji a jednodušeji. To zahrnuje optimalizaci virtuálního stroje pro použití ve STARK proofs a zlepšení prostředí pro vývojáře při vytváření a testování chytrých kontraktů nebo jiných počítačových úloh.