Scénář: Miranda Christ, Joseph Bonneau

Sestavil: Shenchao TechFlow

S tím, jak blockchain podporuje více uživatelů a častější transakce, roste množství informací (tj. „stav“), které validátoři ukládají za účelem ověření transakcí. Například v bitcoinu se stav skládá ze sady neutracených transakčních výstupů (UTXO). V Ethereu se stav skládá ze zůstatku na účtu každého účtu a kódu a úložiště každého smart kontraktu.

Jak blockchain roste s dostatečným počtem účtů nebo UTXO na podporu skutečných každodenních transakcí pro významnou část populace, tato zátěž úložiště se stane neovladatelnou, takže bude obtížné stát se validátorem a bude představovat hrozbu pro decentralizaci. Lákavým řešením je obrátit se na kryptografii, kde nám nástroje jako Merkle stromy a důkazy s nulovými znalostmi pomáhají dosáhnout věcí, které byly dříve nepředstavitelné.

To je přesně cíl „bezstavového blockchainu“. Ale i přes rozsáhlý výzkum na nich mají k praktickému využití ještě daleko. Ukazuje se však, že toto zpoždění ve vývoji je vlastní – propast mezi těmito konstrukcemi a praktičností nebude nikdy překlenuta. Naše nedávná práce ukazuje, že jakékoli bezstavové schéma blockchainu, bez ohledu na to, jak chytré, je neproveditelné bez dalších opatření pro řízení stavu. Jak však ukazujeme na konci tohoto článku, nepravděpodobnost tohoto výsledku by neměla být odrazující.

žádný stav

Dnes je stát velký, ale zvládnutelný. Například bitcoinové uzly uchovávají přibližně 7 GB dat a uzly Ethereum přibližně 650 GB dat. Úložná zátěž plného uzlu však roste zhruba lineárně s propustností řetězce (transakce za sekundu neboli TPS), což je dnes stále nepřijatelné. Se současnými návrhy se stát, který vyžaduje skutečnou podporu každodenních transakcí (desítky až stovky tisíc transakcí za sekundu), stane nezvládnutelným, což bude vyžadovat využití gigabajtů nebo dokonce petabajtů úložného prostoru.

To přimělo lidi hledat technické způsoby, jak výrazně snížit množství stavu vyžadovaného validátory. Je zásadní implementovat bezstavový blockchain, který by vyžadoval, aby validátoři ukládali pouze konstantní velikost stavu bez ohledu na propustnost transakcí (ve skutečnosti je tento termín nesprávné: stále existuje stav, jen dostatečně malý, aby byl praktický při jakákoli budoucí propustnost – obvykle konstantní velikost). Tento požadavek na nenáročné úložiště zjednoduší provoz uzlu validátoru optimisticky, každý bude moci provozovat uzel na svém telefonu. Protože zvýšení počtu ověřovatelů zvyšuje bezpečnost řetězce, je důležité snížit překážku vstupu pro ověřovatele.

Přestože proběhl značný výzkum bezstavových blockchainů (např. Todd, Buterin, Boneh et al. a Srinivasan et al.), stále mají k praktickému využití daleko a pokud je nám známo, žádný nebyl nasazen. Základním problémem všech známých bezstavových blockchainů je, že vyžadují, aby uživatelé ukládali další data nazývaná svědci, aby pomohli validátorům ověřit transakce týkající se jejich účtů. Tento svědek může být například důkaz o zahrnutí společnosti Merkle, který ukazuje, že účet a zůstatek uživatele jsou zahrnuty do globálního státního závazku. Když uživatelé provedou transakci, předají tohoto svědka validátoru, aby prokázali, že jejich účet má dostatečný zůstatek.

Na rozdíl od ukládání soukromých klíčů, které není třeba nikdy měnit, se tito svědci často mění, a to i u uživatelů, kteří aktivně neobchodují, což pro uživatele představuje nereálnou zátěž. Podobně si představte, že byste neustále sledovali všechny ostatní transakce kreditními kartami po celém světě a podle toho aktualizovali některá místní data pro svou vlastní kreditní kartu. Aby byl blockchain praktický, uživatelé musí mít možnost přejít do režimu offline a interagovat s blockchainem pouze při odesílání transakcí. V mnoha případech, jako jsou hardwarové peněženky, je aktualizace svědka nejen nepohodlná, ale nemožná.

To nás vede k položení přirozené výzkumné otázky: Můžeme vytvořit bezstavový blockchain, který nevyžaduje časté aktualizace svědků (nebo blockchain, který vyžaduje pouze zřídka aktualizované svědky)? Abychom na tuto otázku odpověděli, vyvinuli jsme nový teoretický rámec (systém odvolatelného důkazu), který zobecňuje bezstavové blockchainy. Pomocí tohoto rámce demonstrujeme nemožnost: kompromis mezi stručným globálním stavem a častými aktualizacemi svědků je ze své podstaty obtížné sladit. Naše důkazní technologie je informační teoretická, což znamená, že budoucí počítače nebudou dostatečně výkonné, aby tento problém vyřešily: propast mezi bezstavovou konstrukcí blockchainu a praktičností nebude nikdy překlenuta.

Pozadí našeho výzkumu

Abychom pomohli porozumět našim výsledkům nemožnosti, nejprve popíšeme přirozený, ale neefektivní způsob, jak vybudovat bezstavový blockchain pomocí stromů Merkle. Naším cílem je umožnit validátorům určit, zda je transakce odeslaná uživatelem platná – například zda má uživatel dostatečný zůstatek na účtu k provedení transakce. V bezstavovém blockchainovém schématu validátor ukládá stav konstantní velikosti. Když uživatelé provádějí transakci, musí do transakce zahrnout svědka. Validátoři mohou použít aktuální stav a páry (transakce, svědci) zadané uživatelem k ověření, zda má uživatel dostatečný zůstatek na účtu k provádění transakcí.

Nejprve vytvoříme Merkle strom, ve kterém je každý (ID účtu, zůstatek) pár (a, b) zahrnut jako listový uzel. Stav konstantní velikosti V uložený validátorem je kořenem tohoto stromu, který slouží jako závazek k sadě párů zůstatků účtů. Každý uživatel uchovává své svědectví jako důkaz o zařazení Merkle. Merkleův důkaz zahrnutí listu (a, b) se skládá z partnerských uzlů (v1,…,vk) podél cesty od tohoto listu ke kořeni stromu. Vzhledem k transakci na účtu a a nárokovanému zůstatku b může ověřovatel ověřit, že b je skutečně zůstatkem účtu a tím, že zkontroluje důkaz (v1,…,vk) z (a, b) s jeho aktuálním stavem V. Pokud ano, validátor transakci provede a musí odpovídajícím způsobem aktualizovat zůstatek na účtu. Výhodnou vlastností Merkleových stromů je to, že s ohledem na Merkleův důkaz o zadržování listu je snadné vypočítat kořen výsledku, když se tento list změní. Jinými slovy, validátor může snadno vypočítat aktualizovaný stav V', který zachycuje nový zůstatek na účtu a po provedení transakce.

Toto schéma Merkleho stromu má dvě hlavní nevýhody. Za prvé, ohlasy uživatelů jsou relativně velké a logaritmicky rostou s celkovým počtem účtů v systému. V ideálním případě by měly mít konstantní velikost a toho můžeme dosáhnout pomocí schémat, jako jsou akumulátory RSA.

Druhé nevýhodě je těžší se vyhnout: pokaždé, když jiný uživatel provede transakci, změní se doklad o páru zůstatku účtu. Připomeňme, že důkaz listového uzlu se skládá z partnerských uzlů na cestě od tohoto listového uzlu ke kořenu stromu. Pokud se změní další listové uzly, změní se jeden z uzlů, což způsobí skutečné problémy. Většina uživatelů blockchainu chce pasivně držet své coiny v peněženkách a jít online pouze tehdy, když chtějí provádět transakce. V takovém bezstavovém blockchainu však uživatelé musí neustále sledovat transakce jiných lidí, aby měli informace o svědcích aktuální. Zatímco třetí strany mohou provádět toto monitorování jménem uživatelů, odchyluje se od standardního bezstavového blockchain modelu. Ve skutečnosti je to pro bezstavové blockchainy nepřekonatelná výzva, která klade na uživatele velkou zátěž.

Náš závěr: bezdomovectví je nemožné

Tento fenomén se netýká pouze této stromové struktury Merkle – všechna známá bezstavová blockchainová schémata vyžadují, aby uživatelé často aktualizovali své svědecké informace, jak zde ukazujeme. Přesněji ukazujeme, že počet uživatelů, kteří musí aktualizovat své svědecké informace, roste zhruba lineárně s celkovým počtem transakcí provedených všemi uživateli.

To znamená, že i když uživatelka Alice neprovádí žádné transakce, její informace o svědcích se možná bude muset změnit, protože ostatní uživatelé provádějí transakce. Dokud je kompaktní stav uložený validátorem příliš malý na zachycení úplného stavu (tj. množiny všech zůstatků účtů), zvětšení velikosti kompaktního stavu pomůže jen málo. Tento vztah uvedený níže jsme vykreslili na základě naší věty a počtu změn atestačních informací požadovaných za den pro blockchainy s různou propustností. Tyto grafy ukazují, kolikrát optimální bezstavový blockchain potřebuje změnit informace o svědcích. Zde se datový vesmír vztahuje k celkovému počtu účtů v modelu účtu nebo k celkovému počtu UTXO v modelu UTXO.

Jádrem našeho důkazu je informačně-teoretický argument. Základní princip informační teorie, formalizovaný Claudem Shannonem, je ten, že pokud Alice náhodně vybere objekt ze sady velikosti 2n a přeje si říct Bobovi, který objekt si vybrala, musí mu poslat alespoň n bitů. Pokud existuje bezstavové schéma blockchainu, kde uživatelé jen zřídka aktualizují informace o svědcích, může Alice říct Bobovi, který objekt si vybrala, za méně než n bitů, což je nemožné, jak ukázal Shannon. Proto takový bezstavový blockchain neexistuje.

Pro jednoduchost zde popíšeme důkaz trochu slabšího tvrzení: Neexistuje bezstavový blockchain, ve kterém uživatelé nikdy nepotřebují aktualizovat své atestační informace. Klíčové je, že Alice používá bezstavové schéma blockchainu ke kódování své zprávy, kterou má poslat Bobovi. Zpočátku Alice i Bob znají kompletní sadu párů zůstatků účtu pro všech n uživatelů. Předpokládá se, že každý účet má alespoň jednu minci. Alice a Bob také oba znají stručný stav V bezstavového blockchainu a svědkové wi pro všechny páry zůstatků účtu (ai, bi). Alice a Bob se také dohodnou na mapování mezi zprávami a sbírkami účtů. Alice si vybere sadu účtů A, která odpovídá jejímu sdělení, a poté z těchto účtů utratí coiny. Pomocí bezstavového blockchainu bude Bobovi komunikovat se svou vybranou sadou, ze které se o ní může dozvědět.

Kódování: Alice utratí jednu minci z každého účtu v A. Pomocí bezstavového schématu blockchainu Alice vypočítá aktualizovaný stav V' a odešle ho Bobovi.

Dekódování: Pro každé i Bob zkontroluje, zda je Verify(wi, (ai, bi)) pravdivé. Bob vypíše sadu účtů B tak, že Verify(wi, (ai, bi)) = false.

Bob úspěšně vypíše stejnou sadu, kterou vybrala Alice: B = A. Nejprve si všimněte, že pokud Alice utratí minci z účtu ai, svědci jejího starého zůstatku by již neměli být přijímáni - jinak by Alice mohla utratit dvojnásobek. Proto pro každý účet ai v A, Verify(wi, (ai, bi)) = false, Bob zahrne tento účet do B. Bob na druhou stranu nikdy nezahrne účty B, ze kterých Alice neutratila coiny, protože zůstatky těchto účtů zůstávají stejné a (připomeňme si uvolněné tvrzení, které chceme dokázat), jejich svědci se nikdy nemění. Proto se B přesně rovná A.

Nakonec náš rozpor vyřešíme výpočtem počtu číslic, které by Alice měla poslat Bobovi. Může si vybrat ze 2 n podmnožin, takže podle Shannonova zákona by měla Bobovi poslat alespoň n bitů. Odešle však pouze stav konstantní velikosti V', který je mnohem kratší než n bitů.

Přestože při popisu našeho důkazu používáme bezstavový blockchain, Alice a Bob mohou provádět podobně účinnou komunikaci pomocí řady dalších ověřených datových struktur, včetně akumulátorů, vektorových závazků a ověřených slovníků. Tento typ datové struktury formalizujeme pomocí nové abstrakce, kterou nazýváme odvolatelný důkazní systém.

dopad výsledků

Naše výsledky ukazují, že nemůžete „kryptograficky eliminovat stav“ a že neexistuje žádná kouzelná kulka pro schéma závazků, které nám umožní vybudovat bezstavový blockchain, kde uživatelé nikdy nebudou muset aktualizovat své svědky. Stav nezmizí, ale je odsunut od validátorů a podstrčen uživatelům ve formě častých aktualizací svědků.

Existují i ​​další slibná řešení, která se odchylují od přísného bezstavového blockchain modelu. Přirozenou relaxací tohoto modelu je umožnit třetí straně (ani uživateli ani validátorovi), aby byla odpovědná za uložení kompletního stavu. Tato třetí strana, nazývaná uzel atestační služby, používá úplný stav ke generování nejnovějších atestačních informací pro uživatele. Uživatelé pak mohou provádět transakce pomocí těchto svědeckých informací jako v běžném bezstavovém blockchainu, kde validátory stále ukládají pouze stručný stav. Motivační mechanismus tohoto systému, zejména to, jak uživatelé kompenzují uzly ověřených služeb, je zajímavým směrem otevřeného výzkumu.

Zatímco naše dosavadní diskuse se soustředila na L1 blockchainy, naše výsledky mají také důsledky pro L2 systémy, jako jsou Rollup servery. Souhrny (ať už Optimistické nebo ZK) obvykle ukládají velký státní příslib na L1 s malou hodnotou. Tento stav zahrnuje účet každého uživatele na L2. Chceme, aby tito uživatelé mohli vybírat prostředky přímo na L1 (bez součinnosti serverů L2) zveřejněním svědectví o aktuálním stavu účtu. Toto nastavení je také instancí odvolatelného systému důkazu v našem modelu. V podstatě se dá říci, že bezstavové blockchainy jsou již v praxi implementovány, a to formou L2 Rollup.

Bohužel to však znamená, že naše výsledky nemožnosti platí přímo. Uživatelův svědek souhrnného načtení se musí často měnit, jinak musí být téměř celý stav L2 zapsán do L1. Výsledkem je, že dnešní souhrny často předpokládají existenci výboru pro dostupnost dat (někdy nazývaného „validium“), podobného „uzlu důkazové služby“, který pomáhá uživatelům vypočítat nové atestační informace při přípravě na extrakci. Naše výsledky naznačují, že varování pro uživatele v dokumentaci Etherea: „Bez údajů o transakcích nemohou uživatelé spočítat důkazy Merkle k prokázání vlastnictví finančních prostředků a provádět výběry.“