Context și motivație

Înainte de a începe să vorbim despre îmbunătățirile aduse MPT, să vorbim mai întâi despre contextul pentru realizarea acestei cercetări.

Studiez pentru un doctorat și fac design de lanțuri publice. Pe lângă actualizarea de bază a consensului acestui lanț public: o dovadă utilă a muncii, o altă sarcină importantă este implementarea unui sistem de contract inteligent compatibil ETH. În prezent, am implementat o mașină virtuală bazată pe bytecode Python, am integrat-o într-un sistem de contract blockchain și, în mod surprinzător, am făcut-o compatibilă cu Ethereum RPC. Am folosit Python pentru a construi un contract inteligent care respectă standardul ERC20 pentru testare. Desigur, trebuie să implementăm un mecanism de date KV care poate transporta zeci de milioane de utilizatori la nivelul inferior de execuție a contractului (similar cu Mapping in Solidity. este folosit pentru a stoca fiecare Numărul de jetoane sub cont, pot exista sute de milioane de astfel de conturi).

În continuare, conținutul de lucru al designului lanțului public atinge în mod natural concepte precum MPT și trie. Ne-am referit la designul Ethereum, Threetrees, trie, MPT etc.

Găsiți blocaje

Din fericire, înainte de a fi gata să implementăm contractul inteligent pentru a apela MPT, am rulat brusc un program de benchmark arbore MPT simplu pe serverul AWS. După ce am încercat să folosim Trie și MPT pentru a introduce un volum de date de 100 milioane KV, am fost foarte surprinși să obținem rezultatul: performanța arborelui MPT a fost de fapt atât de scăzută.

Rulând următorul cod, observăm că: inserarea a 10 milioane de perechi cheie-valoare KV în Rocksdb durează câteva minute pentru Trie și câteva ore pentru MPT. Când creștem magnitudinea datelor de testare la 100 de milioane, funcția de inserare MPT durează câteva zile. Aceasta înseamnă că atunci când blockchain-ul folosește structura de date MPT pentru a rula contracte inteligente, viteza va fi, de asemenea, foarte limitată.

Experimentele au demonstrat că supraîncărcarea cauzată de utilizarea structurii de date MPT nu numai că va încetini viteza de execuție a contractelor inteligente, ci și va reduce viteza de sincronizare a nodurilor blockchain (chiar și atunci când lățimea de bandă este foarte suficientă, descărcarea datelor de la alte noduri și reconstruirea noduri, trebuie, de asemenea, să dureze câteva zile). Cu toate acestea, deoarece designul structurii de date a lui Ethereum este dificil de modificat, chiar dacă îl rescriem sau îl optimizăm cu un limbaj de programare „mai rapid”, dacă structura de date de bază nu este actualizată, blockchain-ul va fi dificil să depășească limitările de performanță.

test_mpt_write.py

test_mpt_write.py

Îmi amintesc și acum când am învățat prima dată să scriu cod, profesorii ne-au spus un principiu de bază, program = algoritm + structură de date. Dacă limităm structura datelor, atunci chiar dacă vom optimiza cu disperare algoritmul (care necesită adesea câțiva ani de eforturi academice și, în multe cazuri, este aproape imposibil de îmbunătățit), va fi dificil să depășim limitările de performanță ale actualului structură de date. Deci, un plan de îmbunătățire foarte academic, în căutarea unui algoritm de înlocuire MPT mai performant, cercetarea poate dura câțiva ani. Ca predecesor care lucrează în această direcție, Verkle Tree folosește metode polinomiale pentru a optimiza structura de date blockchain. Vom încerca câteva idei mai unice și simple.

Dacă folosim gândirea principiilor, nu putem folosi MPT? Dacă putem să ocolim MPT și să implementăm contracte inteligente direct pe Trie, nu va mai exista overhead cauzat de MPT (primul principiu al lui Ma Yilong, un lucru care nu există nu va avea o suprasarcină de performanță).

Ca preț, soluția noastră nou proiectată poate să nu fie direct compatibilă cu MPT-ul existent, dar, deoarece interfața Ethereum RPC nu este modificată, o mulțime de infrastructură Ethereum existentă poate fi reutilizată: cum ar fi Etherjs și MetaMask. Ocolirea MPT aparține optimizării structurii de date interne, care este o explorare gratuită a performanței blockchain.

cunoștințe pre-condiții

Rocksdb și Trie

Arborele dicționarului Trie este o structură de date arbore avansată menționată în manualele colegiului. În videoclipul profesorului Xiao, MPT este construit pe baza arborelui dicționarului Trie. Putem crede că mediul de implementare al lui Trie este în memorie.

Cu toate acestea, în ingineria noastră, nu putem folosi direct Trie pentru a implementa direct produsul, deoarece, de asemenea, trebuie să persistăm datele de pe hard disk. Acest pas necesită multă optimizare inginerească, așa că în general implementăm arborele MPT bazat pe Rocksdb.

Rocksdb este fork-ul open source al FB bazat pe leveldb și folosește LSMT în partea de jos (consultați lucrarea The log-structured merge-tree). Din punct de vedere abstract, ne putem gândi la Rocksdb ca la un arbore de dicționar optimizat și persistent.

Utilizarea de bază a Rocksdb este foarte simplă. Utilizează în principal trei operații de bază: Get put și interogare prin prefix Iterate.

mașină de stat

Mașina de stat este un instrument folosit adesea de oameni pentru a modela blockchain-urile. Este foarte simplu: adăugați o intrare la o stare originală pentru a obține o stare nouă.

Starea globală a Ethereum poate fi înțeleasă ca starea unei mașini de stat. De exemplu, în blocul 1, valorile KV ale tuturor contractelor inteligente sunt o stare globală. Toate tranzacțiile dintr-un bloc sunt executate de EVM ca o mașină de stat, cum ar fi un apel de contract Mint, face ca Balanța unui utilizator și variabilele Total ale contractului să se schimbe la 1000 în blocul 2.

Un concept de mașină de stări care este ușor de trecut cu vederea se numește funcția de tranziție a stării, care definește regulile de intrare Când intrarea este nerezonabilă, informațiile de intrare vor fi respinse. De exemplu, atunci când încercăm să transferăm o sumă negativă altcuiva, o astfel de tranzacție nu va fi executată (desigur, un contract inteligent cu probleme poate accepta o astfel de tranzacție. În ETH, funcția de tranziție a stării o poate executa automat printr-un Turing -limbaj complet).

Introducere în MPT

Poate ați auzit de cei trei arbori din Ethereum, și anume arborele de tranzacții, arborele de stare și arborele de primire. Toți sunt arbori MPT, al căror nume complet este Merkle Patricia Tries. Dintre acestea, arborele de stare este probabil cel mai bun caz de utilizare pentru utilizarea structurii de date MPT. Pentru detalii, vă rugăm să consultați explicația video a profesorului Xiao.

Arborele MPT se bazează pe structura de date Trie și poate calcula toate datele de stare într-un hash rădăcină precum un arbore Merkle și le poate plasa în antetul blocului Ethereum. Există trei hash-uri rădăcină de arbori MPT în antetul blocului Ethereum, pe care de obicei le numim trei arbori.

Este posibil să nu plasați rădăcina stării globale în antetul blocului? Da, tranzacțiile sunt plasate în blocuri Bitcoin, iar rădăcina Merkle a tranzacției este pusă în antetul blocului (se folosește un arbore Merkle, dar nu se folosește MPT). Dar Bitcoin nu are contracte inteligente precum Ethereum și nici nu are conceptul de stat global. Când Ethereum a proiectat inițial blockchain-ul cu contracte inteligente, a abandonat designul blocului 1 M al Bitcoin și UTXO, a ales structura de date MPT și modelul de cont și a folosit Gas pentru a rezolva problema timpului de nefuncționare, satisfăcând nevoile contractelor inteligente în timpul funcționării stat.

Deci, care este scopul utilizării MPT în Ethereum?

  1. Găsiți starea corespunzătoare a blockchain-ului prin rădăcina Merkle din antetul blocului.

  2. Economisiți spațiul ocupat de datele duplicate.

  3. Starea corectă poate fi verificată prin hash-ul rădăcină.

Primul punct este o cerință rigidă care trebuie citite în timpul executării EVM Dacă se utilizează un model de design similar cu Bitcoin UTXO, multe blocuri trebuie urmărite pentru a obține starea soldului contului unui anumit utilizator. Utilizarea MPT satisface foarte bine nevoile.

Punctul 2, MPT economisește spațiu, iar starea blockchain poate fi privită ca un dicționar imens. În fiecare bloc, doar o mică parte a cheilor este actualizată, iar majoritatea cheilor își păstrează în continuare valorile inițiale. Folosind arborele MPT, puteți actualiza doar valorile cheie care trebuie actualizate, fără a copia starea neschimbată în fiecare bloc.

Punctul 3: Avantajul MPT este că verificarea stării globale a fost finalizată folosind valoarea cheii de stat accesată de hash-ul rădăcină. Acesta este, de asemenea, principalul motiv pentru care scrierea arborelui MPT necesită timp. Dacă nu este utilizat MPT, nodurile pot verifica în continuare consistența datelor în timpul sincronizării blocurilor.

Prin completarea punctelor 1 și 2 fără a folosi MPT, putem ocoli suprasarcina MPT. Deci, trebuie să proiectăm o soluție bazată pe Trie (poate fi înțeles ca Rocksdb) pentru a stoca datele de stare ale blockchain-ului.

proiecta

În principal, proiectăm o soluție bazată pe Trie pentru a stoca starea în lanț. Conform primelor principii, dacă nu există o structură de date MPT, nu este necesar să ruleze MPT. Atâta timp cât sistemul de contract inteligent bazat pe Trie poate fi implementat și rulat corect, înseamnă că optimizarea a fost finalizată. În practică, ne putem gândi la Rocksdb ca un Trie. O înțelegere mai simplă este că este o bază de date KV de înaltă performanță.

Utilizați [globalstate as prefix_contract address_variable name_block height_block hash] ca valoare cheie a bazei de date KV, cum ar fi următorul format. Printre acestea, 0x1 este adresa contractului, Total este numele variabilei, 1 este înălțimea blocului și ABC1234 este valoarea hash a blocului (va fi omisă mai târziu)

globalstate_0x1_total_1_abc1234

În Ethereum Solidity, variabilele pot fi definite ca Memory, Storage și Calldata. Ne concentrăm în principal pe tipul de stocare, deoarece va fi stocat în stare globală. Pe lângă variabilele simple, luăm în considerare și Cartografierea Deoarece ordinea de mărime a utilizatorilor pe blockchain este globală, va exista mapare KV extrem de mare. În plus, vom trata tipuri de date precum Array ca structuri de date simple și le vom stoca direct în Json în Rocksdb. Când codificăm, ar trebui să estimăm în mod natural magnitudinea datelor de valoare din structura datelor KV pentru a alege o metodă de stocare adecvată.

Variabilele de stare de stocare a contractului

Cum putem atinge primul și al doilea obiectiv de proiectare ale MPT fără a folosi MPT?

Să presupunem că avem o variabilă Total în contractul ERC20. Această variabilă se va schimba numai atunci când numărul total de Token-uri crește (Mint) sau scade (Burn), dar valoarea Totalului rămâne atunci când utilizatorul A transferă bani (Transfer) către utilizatorul B. constant.

Pentru simplitate, presupuneți că adresa contractului este 0x1 Când înălțimea blocului este 1, proprietarul contractului a efectuat un Mint 2000. Pe blocurile cu o înălțime de 2-8, utilizatorul a efectuat transferuri multiple inaltimea este de 9 .

În acest moment, trebuie doar să interogăm baza de date pentru Cheia prefixată cu [globalstate_0x1_total_]. Deși cel mai recent bloc al nostru actual este 9, deoarece variabila Total nu s-a modificat în blocurile 2-8, primul rezultat al interogării de mai sus va fi valoarea [globalstate_0x1_total_1], așa că am găsit cea mai recentă valoare a variabilei Total, Total variabilă care s-a modificat în blocul 1.

În acest moment, este generat un nou bloc. Să presupunem că utilizatorul mai efectuează Mint de două ori în al 9-lea bloc și al 11-lea. Aici găsim o caracteristică a Rocksdb Dacă avem următoarea cheie

globalstate_0x1_total_1 : 2000

globalstate_0x1_total_9 : 4000

globalstate_0x1_total_11: 6000

Atunci primul rezultat al căutării va fi întotdeauna blocul 1, nu ultimul bloc 11. Deoarece nu am găsit încă un parametru care să schimbe ordinea rezultatelor căutării din documentația Rocksdb, am folosit un mic truc, folosind un număr mai mare, cum ar fi 100, pentru a scădea înălțimea blocului (de fapt va fi mult mai mare) și a o tape. cu zerouri, deci Cele mai recente blocuri vor fi clasate pe primul loc în rezultatele căutării.

globalstate_0x1_total_089 : 6000

globalstate_0x1_total_091: 4000

globalstate_0x1_total_099: 2000

Tipul de mapare a stocării

După cum am menționat mai devreme, magnitudinea cheii a structurii de date Mapping poate fi masivă, așa că este imposibil pentru noi să convertim dicționarul Json de zeci de mii de chei din Mapping într-un șir. În caz contrar, costul adăugării, ștergerii cheilor , sau modificarea Valorilor va fi foarte înfricoșătoare.

Presupunând că adresa utilizatorului este 0x2, extindem ușor formatul anterior al cheii de stocare:

[globalstate_0x1_[balance_0x2]_2]: 2000

[Numele variabilei] anterior aici a fost extins la [numele variabilei + Cheia dicționarului de cartografiere]

Datele de mai sus reprezintă că soldul de sold al utilizatorului 0x2 în înălțimea blocului 2 este 2000. Dacă nu există date actualizate pentru a acoperi soldul curent, atunci datele utilizatorului din blocul 2 reprezintă cea mai recentă stare.

globalstate_0x1_balance_0x2_098: 2000

globalstate_0x1_total_0x1_099: 2000

Verificați blocarea

La fel ca rădăcina arborelui Merkle, rădăcina arborelui MPT reprezintă, de asemenea, o verificare a stării globale. Atâta timp cât putem asigura coerența datelor blocului, dacă trebuie să folosim MPT și să scriem Root în antetul blocului este o alegere de proiectare.

Am adus câteva îmbunătățiri în designul blocului, astfel încât antetul blocului să conțină două corpuri, unul este blocul de date privind tranzacția, iar celălalt este blocul de date de actualizare a stării.

Blocul de date de tranzacție conține hash-ul tuturor tranzacțiilor Minerii sau nodurile pot începe de la starea globală a unei anumite înălțimi de bloc, pot executa toate tranzacțiile în ordinea dată în blocul de date ale tranzacției și pot obține starea globală a blocului următor. Dacă volumul tranzacțiilor este mare, execuția paralelă este puțin probabilă (deoarece ordinea tranzacțiilor va fi perturbată), deci va fi mai consumatoare de timp să solicite nodurilor din întreaga lume să execute toate tranzacțiile.

În acest scop, am proiectat un bloc de date de actualizare a stării, care include valorile cheie de stat globale actualizate după rularea tuturor tranzacțiilor. Dacă este un nod care se află cu multe blocuri în urmă, pe lângă rularea unei mașini virtuale pentru a executa toate tranzacțiile, poate actualiza și conținutul Corpului în funcție de stare și poate introduce direct valorile cheie în baza de date pentru a economisi puterea de calcul și scurtează timpul de sincronizare.

Desigur, valorile cheie utilizate pentru a efectua toate actualizările tranzacțiilor trebuie să fie exact aceleași cu Dif-ul conținut în blocul de actualizare a stării, altfel acest nou bloc va fi ilegal.

Să presupunem că există 10.000 de noduri în lume Când aruncăm un zar și stabilim o probabilitate de 1% pentru a executa o tranzacție, aproximativ 100 de noduri vor executa tranzacția încrucișată, iar alte noduri se vor baza pe conținutul actualizării stării conexiunii. bloc de date Apoi această zonă Multe noduri din sistemul blockchain vor putea salva o mulțime de operațiuni repetate.

realiza

După finalizarea designului anterior, am început imediat să implementăm această idee.

În primul rând, am integrat VM-ul Python în sistemul blockchain. Aceasta este o mașină virtuală Python implementată în Python, care este în prezent compatibilă cu PY 3.10 bytecode. Sperăm că contractele inteligente pot folosi o parte din sintaxa lui Python. De exemplu, avem nevoie doar de funcții și nu dorim ca dezvoltatorii să folosească Class, așa că în prezent nu acceptăm pe deplin toate codurile PY.

În ceea ce privește compilatorul, Solidity trebuie să dezvolte un compilator dedicat pentru a converti codul sursă în bytecode EVM. Folosind Python, puteți converti cu ușurință codul sursă Python în bytecode PY cu ajutorul acestui excelent limbaj de infrastructură cu o istorie de treizeci de ani. Utilizatorii cu greu vor observa timpul de compilare.

Depozitul nostru de coduri VM este după cum urmează. Toată lumea este binevenită să ne ofere opiniile și să remedieze potențialele probleme de securitate:

Link: https://github.com/EcoPoW/python_stf_vm În al doilea pas, am dezvoltat o versiune Python a ERC20, iar codul este actualizat constant. Spre deosebire de Solidity, nu folosim cuvinte cheie pentru a identifica modul în care sunt stocate variabilele, toate variabilele locale sunt în memorie și folosim funcțiile globale _get și _put pentru a citi și scrie starea. Link: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

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

Implementare și îmbunătățire

Ne-a luat aproximativ două luni de la ridicarea întrebărilor, până la proiectarea și implementarea codificării.

După o vară întreagă de design + codare reală, noul sistem de contract inteligent, care folosește doar arborele de dicționar Trie fără a se baza pe structura de date MPT, este gata de rulare (puteți încerca să rulați nodul de testare local prin clona Github). Ocolirea stocării prin contract inteligent bazat pe MPT înseamnă că, cu o lățime de bandă suficientă, timpul de sincronizare al unui nod cu o dimensiune de 100 milioane KV poate fi redus de la câteva zile la câteva minute. Eficiența de execuție a contractelor inteligente va deveni, de asemenea, mai rapidă, iar mai multe dintre calculele consumate de CPU vor fi folosite pentru a executa bytecode, mai degrabă decât operațiunile hash necesare pentru a construi arborele Merkle. Am fost norocoși că atunci când am implementat contracte inteligente în proiect, nu am urmat direct designul „standard al industriei”, în schimb, am încercat mai întâi optimizarea și scăderea și am obținut un blockchain de contracte inteligente cu „structura de date” corectă. Pentru că, spre deosebire de produsele Web2, pe care le comparăm cu schimbarea anvelopelor în timpul conducerii unei mașini, blockchain-ul Web3 seamănă mai mult cu o lansare de rachetă. Este dificil să facem îmbunătățiri structurale majore unui blockchain care rulează, așa că putem doar să îmbunătățim sistemul „următorul” și să fim pe deplin pregătiți înainte de a intra online.

În prezent, rețeaua de testare Testnet 2 a blockchain-ului BitPoW pe care am proiectat-o ​​a fost implementată Toată lumea poate folosi MetaMask pentru a se conecta la acest blockchain prin RPC pentru a testa și a încerca transferurile ERC20 bazate pe Python VM. În același timp, mai avem încă multă muncă de făcut și trebuie să ne bazăm în continuare pe comunitate pentru a promova această nouă infrastructură blockchain.

Salutăm tuturor să învețe și să testeze efectiv implementarea acestor noi tehnologii bazate pe concept, inclusiv testarea performanței după eliminarea MPT și testarea de securitate a noilor contracte inteligente și a noilor lanțuri.

Rezuma

Până acum, am ocolit MPT și am proiectat o soluție inteligentă de stocare prin contract bazată direct pe Trie. În prezent, implementăm această îmbunătățire pe un blockchain bazat pe Python vm ca o dovadă a fezabilității. Ne-a luat aproximativ trei luni de la descoperirea problemei până la propunerea unei soluții și implementarea ei în cod Dar lucrul mai important despre acest studiu este că, la fel ca mulți oameni obișnuiți, după ce am învățat cunoștințele MPT de la clasă, nu sa mai gândit. imbunatatindu-l. Soluția nu este complicată, dar necesită practică și acțiune. Soluția nu este complicată, dar necesită practică și acțiune. Numai gândind activ în practică putem găsi inspirație și inova în continuare. Sunt foarte recunoscător LXDAO pentru sprijinul acestei cercetări și sper să întâlnesc mai mulți prieteni din comunitate care sunt interesați de stratul inferior al blockchain-ului. Industria este încă foarte devreme, iar infrastructura este departe de a fi matură. Sperăm să promovăm popularizarea cunoștințelor de bază ale blockchain-ului, astfel încât mai mulți oameni să poată participa în fruntea inovației tehnologice.