Pozadí a motivace

Než začneme mluvit o vylepšeních MPT, promluvme si nejprve o pozadí provádění tohoto výzkumu.

Studuji Ph.D. a dělám design veřejných řetězců. Kromě základního konsensuálního upgradu tohoto veřejného řetězce: užitečného důkazu o práci je dalším důležitým úkolem implementace systému inteligentních smluv kompatibilní s ETH. V současné době jsme implementovali virtuální stroj založený na bajtkódu Pythonu, integrovali jsme jej do blockchain smluvního systému a překvapivě jsme jej učinili kompatibilním s Ethereum RPC. Použili jsme Python k vybudování chytré smlouvy, která vyhovuje standardu ERC20 pro testování. Přirozeně potřebujeme implementovat KV datový mechanismus, který dokáže přenést desítky milionů uživatelů na nižší úrovni realizace smlouvy (podobně jako Mapping v Solidity, který). se používá k uložení každého Počet tokenů pod účtem, takových účtů mohou být stovky milionů).

Dále se pracovní náplň designu veřejných řetězců přirozeně dotýká pojmů jako MPT a trie. Odkazovali jsme na design Ethereum, Threetrees, trie, MPT atd.

Najděte úzká hrdla

Naštěstí, než jsme byli připraveni implementovat inteligentní smlouvu na volání MPT, jsme najednou na serveru AWS spustili jednoduchý program Benchmark stromu MPT. Po pokusu použít Trie a MPT k vložení datového objemu 100 milionů KV jsme byli velmi překvapeni výsledkem: výkon stromu MPT byl ve skutečnosti tak nízký.

Spuštěním následujícího kódu zjistíme, že: vložení 10 milionů párů klíč-hodnota KV do Rocksdb trvá několik minut pro Trie a několik hodin pro MPT. Když zvýšíme velikost testovacích dat na 100 milionů, zavádění MPT trvá několik dní, než se spustí. To znamená, že když blockchain používá datovou strukturu MPT ke spouštění chytrých kontraktů, rychlost bude také značně omezena.

Experimenty prokázaly, že režie způsobená používáním datové struktury MPT nejen zpomalí rychlost provádění chytrých kontraktů, ale také sníží rychlost synchronizace uzlů blockchainu (i když je šířka pásma velmi dostatečná, stahování dat z jiných uzlů a přestavba uzly, musí to také trvat několik dní). Avšak vzhledem k tomu, že návrh datové struktury Etherea je obtížné upravit, i když jej přepíšeme nebo optimalizujeme pomocí „rychlejšího“ programovacího jazyka, nebude-li základní datová struktura aktualizována, bude blockchain obtížné prolomit omezení výkonu.

  test_mpt_write.py

  test_mpt_write.py

Ještě si pamatuji, když jsem se poprvé naučil psát kód, učitelé nám řekli základní princip, program = algoritmus + datová struktura. Pokud omezíme datovou strukturu, pak i když zoufale optimalizujeme algoritmus (což často vyžaduje několik let akademického úsilí a v mnoha případech je téměř nemožné jej zlepšit), bude obtížné prolomit výkonnostní omezení současného datová struktura. Takže velmi akademický plán zlepšení, hledající lepší výkonový algoritmus náhrady MPT, výzkum může trvat několik let. Jako předchůdce pracující v tomto směru používá Verkle Tree polynomiální metody k optimalizaci datové struktury blockchainu. Vyzkoušíme některé unikátnější a jednodušší nápady.

Pokud použijeme myšlení prvních principů, nemůžeme použít MPT? Pokud dokážeme obejít MPT a implementovat chytré kontrakty přímo na Trie, již nebude existovat režie způsobená MPT (první princip Ma Yilong, věc, která neexistuje, nebude mít výkonnostní režii).

Naše nově navržené řešení nemusí být přímo kompatibilní se stávajícím MPT, ale protože rozhraní Ethereum RPC není upraveno, lze znovu použít mnoho existující infrastruktury Ethereum: například Etherjs a MetaMask. Vynechání MPT patří k optimalizaci interní datové struktury, což je bezplatné zkoumání výkonu blockchainu.

předpokladem znalosti

Rocksdb a Trie

Slovníkový strom Trie je pokročilá stromová datová struktura zmíněná ve vysokoškolských učebnicích Ve videu učitele Xiao je MPT vytvořen na základě slovníkového stromu Trie. Můžeme si myslet, že implementační prostředí Trie je v paměti.

V našem inženýrství však nemůžeme přímo použít Trie k přímé implementaci produktu, protože také potřebujeme uchovat data na pevném disku Tento krok vyžaduje velkou optimalizaci inženýrství, takže obvykle implementujeme strom MPT založený na Rocksdb.

Rocksdb je open source fork FB založený na leveldb a ve spodní části používá LSMT (viz dokument The log-structured merge-tree). Z abstraktního hlediska můžeme Rocksdb považovat za optimalizovaný a trvalý slovníkový strom.

Základní použití Rocksdb je velmi jednoduché Používá především tři základní operace: Get put a dotaz podle prefixu Iterate.

státní stroj

Stavový stroj je nástroj, který lidé často používají k modelování blockchainů. Je to velmi jednoduché: přidáním vstupu do původního stavu získáte nový stav.

Globální stav Etherea lze chápat jako stav stavového automatu, například v bloku 1 jsou hodnoty KV všech smart kontraktů globálním stavem Všechny transakce v bloku jsou prováděny EVM a lze je pochopit jako stavový stroj, jako je volání smlouvy Mint, způsobí změnu zůstatku uživatele a proměnných Total smlouvy na 1000 v bloku 2.

Koncept stavového stroje, který lze snadno přehlédnout, se nazývá funkce přechodu stavu, která definuje vstupní pravidla, pokud je vstup nepřiměřený, vstupní informace bude odmítnuta. Když se například pokusíme převést zápornou částku někomu jinému, taková transakce nebude provedena (samozřejmě, zabugovaný smart kontrakt může takovou transakci přijmout. V ETH ji může funkce přechodu stavu automaticky provést prostřednictvím Turingova - úplná definice).

Úvod do MPT

Možná jste slyšeli o třech stromech v Ethereu, jmenovitě stromu transakcí, stromu stavu a stromu účtenek. Všechno jsou to stromy MPT, jejichž celé jméno je Merkle Patricia Tries. Mezi nimi je stavový strom pravděpodobně nejlepším případem použití datové struktury MPT. Podrobnosti najdete ve videu s vysvětlením učitele Xiao.

Strom MPT je založen na datové struktuře Trie a dokáže vypočítat všechna stavová data do kořenového hashe jako Merkle strom a vložit je do hlavičky bloku Ethereum. V hlavičce bloku Ethereum jsou tři kořenové hashe stromů MPT, které obvykle nazýváme tři stromy.

Je možné neumisťovat kořen globálního stavu do hlavičky bloku? Ano, to, co je umístěno v bitcoinovém bloku, je transakce a Merkle kořen transakce je vložen do hlavičky bloku (používá se strom Merkle, ale nepoužívá se MPT). Bitcoin ale nemá chytré kontrakty jako Ethereum, ani koncept globálního státu. Když Ethereum původně navrhovalo blockchain s chytrými kontrakty, opustilo 1M blokový design Bitcoinu a UTXO, zvolilo MPT datovou strukturu a model účtu a k vyřešení problému s výpadky použilo Gas, čímž uspokojilo potřeby chytrých kontraktů během provozu stát.

Jaký je tedy cíl používání MPT v Ethereu?

  1. Najděte odpovídající stav blockchainu přes kořen Merkle v hlavičce bloku.

  2. Ušetřete místo obsazené duplicitními daty.

  3. Správný stav lze ověřit přes root hash.

Prvním bodem je přísný požadavek Při provádění EVM je třeba číst různé stavy Pokud je použit návrhový vzor podobný bitcoinovému UTXO, je třeba zpětně vysledovat mnoho bloků, aby bylo možné získat stav účtu určitého uživatele. Použití MPT velmi dobře uspokojuje potřeby.

Bod 2, MPT šetří místo a stav blockchainu lze považovat za obrovský slovník. V každém bloku se aktualizuje jen malá část klíčů a většina klíčů si stále zachovává své původní hodnoty. Pomocí stromu MPT můžete aktualizovat pouze hodnoty klíčů, které je třeba aktualizovat, bez kopírování nezměněného stavu v každém bloku.

Bod 3: Výhodou MPT je, že ověření globálního stavu bylo dokončeno pomocí hodnoty klíče stavu, ke které přistupuje kořenový hash. To je také hlavní důvod, proč je psaní MPT stromu časově náročné. Pokud není použito MPT, uzly mohou stále ověřovat konzistenci dat během synchronizace bloku.

Dokončením bodů 1 a 2 bez použití MPT můžeme obejít režii MPT. Potřebujeme tedy navrhnout řešení založené na Trie (lze chápat jako Rocksdb) pro ukládání stavových dat blockchainu.

design

Navrhujeme především řešení založené na Trie pro ukládání stavu v řetězci. Podle prvních zásad, pokud neexistuje žádná datová struktura MPT, není pro provoz MPT vyžadována žádná systémová režie. Dokud lze systém inteligentních smluv založený na Trie implementovat a správně fungovat, znamená to, že optimalizace byla dokončena. V praxi můžeme Rocksdb považovat za Trie. Jednodušší chápání je, že jde o vysoce výkonnou KV databázi.

Použijte [globalstate as prefix_contract address_variable name_block height_block hash] jako klíčovou hodnotu databáze KV, například v následujícím formátu. Mezi nimi je 0x1 adresa smlouvy, Total je název proměnné, 1 je výška bloku a ABC1234 je hodnota hash bloku (bude vynechána později)

globalstate_0x1_total_1_abc1234

V Ethereum Solidity lze definovat proměnné jako Memory, Storage a Calldata. Zaměřujeme se hlavně na typ Storage, protože bude uložen v globálním stavu. Kromě jednoduchých proměnných uvažujeme také o mapování Protože řádová velikost uživatelů na blockchainu je globální, dojde k extrémně velkému mapování KV. Kromě toho budeme s datovými typy, jako je Array, zacházet jako s jednoduchými datovými strukturami a přímo je ukládat do Json v Rocksdb. Když kódujeme, měli bychom přirozeně odhadnout velikost hodnotových dat v datové struktuře KV, abychom zvolili vhodnou metodu ukládání.

Proměnné stavu uložení smlouvy

Jak můžeme dosáhnout prvního a druhého cíle návrhu MPT bez použití MPT?

Předpokládejme, že máme ve smlouvě ERC20 proměnnou Total. Tato proměnná se změní pouze tehdy, když se celkový počet tokenů zvýší (Mint) nebo sníží (Burn), ale hodnota Total zůstane, když uživatel A převede peníze (Transfer) uživateli B. konstantní.

Pro zjednodušení předpokládejme, že adresa smlouvy je 0x1, když je výška bloku 1, vlastník smlouvy provedl Mint 2000. Na blocích s výškou 2-8 uživatel provedl více převodů .

V tomto okamžiku potřebujeme pouze dotaz v databázi na klíč s předponou [globalstate_0x1_total_]. Přestože náš aktuální poslední blok je 9, protože proměnná Total se v blocích 2–8 nezměnila, prvním výsledkem výše uvedeného dotazu bude hodnota [globalstate_0x1_total_1], takže najdeme nejnovější hodnotu proměnné Total , Total proměnná, která se změnila v bloku 1.

V tomto okamžiku se vygeneruje nový blok Předpokládejme, že uživatel provede Mint ještě dvakrát v bloku 9 a bloku 11. Zde najdeme funkci Rocksdb, pokud máme následující klíč

globalstate_0x1_total_1  : 2000

globalstate_0x1_total_9  : 4000

globalstate_0x1_total_11: 6000

Pak bude prvním výsledkem hledání vždy blok 1, nikoli poslední blok 11. Protože jsme zatím nenašli parametr pro změnu pořadí výsledků vyhledávání z dokumentace Rocksdb, použili jsme malý trik, pomocí většího čísla, například 100, odečtěte výšku bloku (ve skutečnosti bude mnohem větší) a doplňte jej s nulami, takže nejnovější bloky budou ve výsledcích vyhledávání zařazeny na první místo.

globalstate_0x1_total_089 : 6000

globalstate_0x1_total_091 : 4000

globalstate_0x1_total_099: 2000

Typ mapování úložiště

Jak jsme již zmínili dříve, velikost klíče v datové struktuře mapování může být masivní, takže je nemožné převést slovník Json s desítkami tisíc klíčů v mapování na řetězec. Jinak budou náklady na přidávání a odstraňování klíčů nebo úprava hodnot bude velmi vysoká.

Za předpokladu, že adresa uživatele je 0x2, mírně rozšiřujeme předchozí formát klíče úložiště:

[globalstate_0x1_[balance_0x2]_2]: 2000

Předchozí [název proměnné] zde byl rozšířen na [název proměnné + klíč slovníku mapování]

Výše uvedená data představují, že zůstatek zůstatku uživatele 0x2 ve výšce bloku 2 je 2000. Pokud neexistují žádná aktualizovaná data pokrývající aktuální zůstatek, pak data uživatele v bloku 2 představují nejnovější stav.

globalstate_0x1_balance_0x2_098: 2000

globalstate_0x1_total_0x1_099: 2000

Ověřte blokování

Stejně jako kořen stromu Merkle i kořen stromu MPT představuje ověření globálního stavu. Pokud dokážeme zajistit konzistenci dat bloku, zda musíme použít MPT a zapsat kořen do hlavičky bloku, je návrhová volba.

Provedli jsme určitá vylepšení v návrhu bloku, takže hlavička bloku obsahuje dvě těla, jedno je blok dat transakce a druhé je blok dat aktualizace stavu.

Blok dat transakce obsahuje hash všech transakcí Minery nebo uzly mohou začít z globálního stavu určité výšky bloku, provést všechny transakce v pořadí uvedeném v bloku dat transakce a získat globální stav dalšího bloku. Pokud je objem transakcí velký, paralelní provádění je nepravděpodobné (protože pořadí transakcí bude narušeno), takže by bylo časově náročnější vyžadovat, aby všechny transakce prováděly uzly po celém světě.

Za tímto účelem jsme navrhli blok dat aktualizace stavu, který obsahuje aktualizované hodnoty klíče globálního stavu po spuštění všech transakcí. Pokud se jedná o uzel, který je o mnoho bloků pozadu, kromě toho, že spouští virtuální stroj pro provádění všech transakcí, může také aktualizovat obsah těla podle stavu a přímo vkládat klíčové hodnoty do databáze pro úsporu výpočetního výkonu a zkrátit čas synchronizace.

Hodnoty klíče používané k provádění všech aktualizací transakcí musí být samozřejmě přesně stejné jako rozdíl obsažený v bloku aktualizace stavu, jinak bude tento nový blok nelegální.

Předpokládejme, že na světě je 10 000 uzlů, když hodíme kostkou a nastavíme 1% pravděpodobnost provedení transakce, asi 100 uzlů provede transakci napříč bloky a ostatní uzly se budou spoléhat na obsah aktualizace stavu připojení. datový blok Pak tato oblast Mnoho uzlů v blockchainovém systému bude moci ušetřit spoustu opakovaných operací.

splnit

Po dokončení předchozího návrhu jsme tento nápad okamžitě začali realizovat.

Nejprve jsme integrovali Python VM do blockchainového systému. Toto je virtuální stroj Python implementovaný v Pythonu, který je v současné době kompatibilní s bytecode PY 3.10. Doufáme, že chytré smlouvy mohou používat část syntaxe Pythonu, například potřebujeme pouze funkce a nechceme, aby vývojáři používali Class, takže v současné době plně nepodporujeme všechny bajtové kódy PY.

Pokud jde o kompilátor, Solidity potřebuje vyvinout specializovaný kompilátor, který převede zdrojový kód na bytecode EVM. Pomocí Pythonu můžete snadno převést zdrojový kód Pythonu na bajtový kód PY s pomocí tohoto vynikajícího infrastrukturního jazyka s třicetiletou historií.

Naše úložiště kódu VM je následující.

Odkaz: https://github.com/EcoPoW/python_stf_vm Ve druhém kroku jsme vyvinuli Python verzi ERC20 a kód je neustále aktualizován. Na rozdíl od Solidity nepoužíváme klíčová slova k identifikaci toho, jak jsou proměnné uloženy, všechny lokální proměnné jsou v paměti a ke čtení a zápisu stavu používáme globální funkce _get a _put. Odkaz: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

https://github.com/EcoPoW/BitPoW/blob/master/state.py

Implementace a zlepšování

Od vznesení otázek, přes návrh a implementaci kódování nám to trvalo asi dva měsíce.

Po celém létě designu + skutečného kódování je nový systém inteligentních smluv, který používá pouze slovníkový strom Trie, aniž by se spoléhal na datovou strukturu MPT, připraven ke spuštění (můžete zkusit spustit testovací uzel lokálně prostřednictvím klonu Github). Vynechání úložiště inteligentních smluv na bázi MPT znamená, že při dostatečné šířce pásma lze dobu synchronizace uzlu o velikosti 100 milionů KV zkrátit z několika dnů na několik minut. Efektivita provádění inteligentních kontraktů se také zrychlí a více výpočtů spotřebovaných CPU bude použito k provedení bajtkódu namísto hašovacích operací nutných k sestavení Merkleho stromu. Měli jsme štěstí, že jsme se při implementaci chytrých kontraktů v projektu neřídili přímo designem „průmyslového standardu“, místo toho jsme nejprve zkusili optimalizaci a odečítání a získali jsme blockchain smart kontraktu se správnou „datovou strukturou“. Protože na rozdíl od produktů Web2, které přirovnáváme k výměně pneumatik za jízdy autem, blockchain Web3 připomíná spíše raketový start. Je obtížné provést zásadní strukturální vylepšení běžícího blockchainu, takže můžeme vylepšit pouze „další“ systém a být plně připraveni, než půjdeme online.

V současné době je nasazena testovací síť BitPoW blockchainu BitPoW, kterou jsme navrhli, každý může použít MetaMask pro připojení k tomuto blockchainu přes RPC pro testování a vyzkoušet přenosy ERC20 založené na Python VM. Zároveň nás čeká ještě hodně práce a stále se musíme spolehnout na komunitu, že bude tuto novou blockchainovou infrastrukturu propagovat.

Vítáme každého, kdo se dozví a skutečně otestuje implementaci těchto nových technologií řízených koncepty, včetně testování výkonu po odstranění MPT a testování zabezpečení nových chytrých kontraktů a nových řetězců.

Shrnout

Doposud jsme obcházeli MPT a navrhli řešení smart contract storage přímo založené na Trie. V současné době implementujeme toto vylepšení na blockchainu založeném na Pythonu vm jako důkaz proveditelnosti. Od objevení problému až po navržení řešení a jeho implementaci do kódu nám to trvalo asi tři měsíce, ale důležitější na této studii je, že jako mnoho obyčejných lidí jsme se poté, co jsme se naučili MPT znalosti ze třídy, dále nezamýšleli. to zlepšit. Řešení není složité, ale vyžaduje cvik a akci. Řešení není složité, ale vyžaduje cvik a akci. Pouze aktivním myšlením v praxi můžeme nacházet inspiraci a dále inovovat. Jsem velmi vděčný LXDAO za podporu tohoto výzkumu a doufám, že potkám více přátel v komunitě, kteří se zajímají o spodní vrstvu blockchainu. Toto odvětví je ještě velmi brzy a infrastruktura není zdaleka vyspělá. Doufáme, že podpoříme popularizaci základních znalostí blockchainu, aby se více lidí mohlo zapojit do popředí technologických inovací.