Contesto e motivazione

Prima di iniziare a parlare dei miglioramenti a MPT, parliamo innanzitutto del background su cui si basa la conduzione di questa ricerca.

Sto studiando per un dottorato di ricerca e mi occupo di progettazione di catene pubbliche. Oltre all’aggiornamento fondamentale del consenso di questa catena pubblica: prova utile del lavoro, un altro compito importante è implementare un sistema di contratto intelligente compatibile con ETH. Attualmente abbiamo implementato una macchina virtuale basata sul bytecode Python, l'abbiamo integrata in un sistema contrattuale blockchain e, sorprendentemente, l'abbiamo resa compatibile con Ethereum RPC. Abbiamo utilizzato Python per creare un contratto intelligente conforme allo standard ERC20 per i test. Naturalmente, dobbiamo implementare un meccanismo di dati KV che possa trasportare decine di milioni di utenti al livello inferiore di esecuzione del contratto (simile a Mapping in Solidity, che. viene utilizzato per memorizzare ciascuno Il numero di token sotto l'account, potrebbero esserci centinaia di milioni di tali account).

Successivamente, il contenuto del lavoro di progettazione della catena pubblica tocca naturalmente concetti come MPT e trie. Abbiamo fatto riferimento al design di Ethereum, Threetrees, trie, MPT, ecc.

Trova i colli di bottiglia

Fortunatamente, prima che fossimo pronti a implementare il contratto intelligente per chiamare MPT, abbiamo improvvisamente eseguito un semplice programma di benchmark dell'albero MPT sul server AWS. Dopo aver provato a utilizzare Trie e MPT per inserire un volume di dati di 100 milioni di KV, siamo rimasti molto sorpresi dal risultato: le prestazioni dell'albero MPT erano in realtà così basse.

Eseguendo il seguente codice, osserviamo che: l'inserimento di 10 milioni di coppie chiave-valore KV in Rocksdb richiede alcuni minuti per Trie e alcune ore per MPT. Quando aumentiamo la grandezza dei dati di test a 100 milioni, l'inseritore MPT impiega diversi giorni per funzionare. Ciò significa che quando la blockchain utilizza la struttura dati MPT per eseguire contratti intelligenti, anche la velocità sarà notevolmente limitata.

Gli esperimenti hanno dimostrato che il sovraccarico causato dall'utilizzo della struttura dati MPT non solo rallenterà la velocità di esecuzione dei contratti intelligenti, ma ridurrà anche la velocità di sincronizzazione dei nodi blockchain (anche quando la larghezza di banda è molto sufficiente, scaricando dati da altri nodi e ricostruendo nodi, devono volerci anche diversi giorni). Tuttavia, poiché il design della struttura dati di Ethereum è difficile da modificare, anche se lo riscriviamo o ottimizziamo con un linguaggio di programmazione "più veloce", se la struttura dati sottostante non viene aggiornata, sarà difficile per la blockchain superare i limiti prestazionali.

test_mpt_write.py

test_mpt_write.py

Ricordo ancora quando ho imparato a scrivere codice per la prima volta, gli insegnanti ci hanno spiegato un principio di base, programma = algoritmo + struttura dati. Se limitiamo la struttura dei dati, anche se ottimizziamo disperatamente l’algoritmo (che spesso richiede diversi anni di sforzi accademici e in molti casi è quasi impossibile migliorare), sarà difficile superare i limiti prestazionali dell’attuale struttura dei dati. Quindi un piano di miglioramento molto accademico, alla ricerca di un algoritmo di sostituzione MPT più performante, la ricerca potrebbe richiedere diversi anni. Come predecessore che lavora in questa direzione, Verkle Tree utilizza metodi polinomiali per ottimizzare la struttura dei dati blockchain. Proveremo alcune idee più uniche e semplici.

Se usiamo il pensiero basato sui principi primi, non possiamo usare la MPT? Se riusciamo a bypassare MPT e implementare contratti intelligenti direttamente su Trie, non ci sarà più il sovraccarico causato da MPT (il primo principio di Ma Yilong, una cosa che non esiste non avrà un sovraccarico in termini di prestazioni).

Come prezzo, la nostra soluzione di nuova concezione potrebbe non essere direttamente compatibile con l'MPT esistente, ma poiché l'interfaccia RPC di Ethereum non viene modificata, molte infrastrutture Ethereum esistenti possono essere riutilizzate: come Etherjs e MetaMask. Bypassare MPT rientra nell'ottimizzazione della struttura dati interna, che è un'esplorazione gratuita delle prestazioni della blockchain.

conoscenza prerequisita

Rocksdb e Trie

L'albero del dizionario Trie è una struttura dati ad albero avanzata menzionata nei libri di testo universitari. Nel video dell'insegnante Xiao, MPT è costruito sulla base dell'albero del dizionario Trie. Possiamo pensare che l'ambiente di implementazione di Trie sia in memoria.

Tuttavia, nella nostra progettazione, non possiamo utilizzare direttamente Trie per implementare direttamente il prodotto, perché dobbiamo anche rendere persistenti i dati sul disco rigido. Questo passaggio richiede molta ottimizzazione ingegneristica, quindi generalmente implementiamo l'albero MPT basato su Rocksdb.

Rocksdb è il fork open source di FB basato su leveldb e utilizza LSMT nella parte inferiore (fare riferimento al documento The log-structured merge-tree). Da un punto di vista astratto possiamo pensare a Rocksdb come ad un albero di dizionario ottimizzato e persistente.

L'utilizzo di base di Rocksdb è molto semplice e utilizza principalmente tre operazioni di base: Get put e query tramite prefisso Iterate.

macchina statale

La macchina a stati è uno strumento spesso utilizzato dalle persone per modellare le blockchain. È molto semplice: aggiungi un input a uno stato originale per ottenere un nuovo stato.

Lo stato globale di Ethereum può essere inteso come lo stato di una macchina a stati. Ad esempio, nel blocco 1, i valori KV di tutti i contratti intelligenti sono uno stato globale. Tutte le transazioni in un blocco vengono eseguite da EVM e possono essere comprese come macchina a stati. L'input, come una chiamata al contratto Mint, fa sì che il saldo di un utente e le variabili totali del contratto cambino in 1000 nel blocco 2.

Un concetto di macchina a stati che viene facilmente trascurato è chiamato funzione di transizione di stato, che definisce le regole di input. Quando l'input è irragionevole, le informazioni di input verranno rifiutate. Ad esempio, quando proviamo a trasferire un importo negativo a qualcun altro, tale transazione non verrà eseguita (ovviamente, uno smart contract bacato può accettare tale transazione. In ETH, la funzione di transizione di stato può eseguirla automaticamente tramite un Turing -definizione completa).

Introduzione all'MPT

Forse hai sentito parlare dei tre alberi di Ethereum, vale a dire l'albero delle transazioni, l'albero degli stati e l'albero delle ricevute. Sono tutti alberi MPT, il cui nome completo è Merkle Patricia Tries. Tra questi, l'albero degli stati è probabilmente il miglior caso d'uso per l'utilizzo della struttura dati MPT. Per i dettagli, fare riferimento alla spiegazione video dell'insegnante Xiao.

L'albero MPT si basa sulla struttura dati Trie e può calcolare tutti i dati di stato in un hash root come un albero Merkle e inserirlo nell'intestazione del blocco Ethereum. Ci sono tre root hash degli alberi MPT nell'intestazione del blocco Ethereum, che solitamente chiamiamo tre alberi.

È possibile non inserire la radice dello stato globale nell'intestazione del blocco? Sì, ciò che viene inserito nel blocco Bitcoin è la transazione e la radice Merkle della transazione viene inserita nell'intestazione del blocco (viene utilizzato un albero Merkle, ma non viene utilizzato MPT). Ma Bitcoin non ha contratti intelligenti come Ethereum, né ha il concetto di stato globale. Quando Ethereum ha inizialmente progettato la blockchain con contratti intelligenti, ha abbandonato il design del blocco 1 M di Bitcoin e UTXO, ha scelto la struttura dei dati e il modello di account MPT e ha utilizzato Gas per risolvere il problema dei tempi di inattività, soddisfacendo le esigenze dei contratti intelligenti durante il funzionamento stato.

Quindi, qual è l’obiettivo dell’utilizzo di MPT in Ethereum?

  1. Trova lo stato corrispondente della blockchain attraverso la radice Merkle nell'intestazione del blocco.

  2. Risparmia spazio occupato da dati duplicati.

  3. Lo stato corretto può essere verificato tramite l'hash root.

Il primo punto è un requisito rigido. È necessario leggere vari stati durante l'esecuzione di EVM. Se viene utilizzato un modello di progettazione simile a Bitcoin UTXO, è necessario risalire a molti blocchi per ottenere lo stato del saldo del conto di un determinato utente. L'utilizzo di MPT soddisfa molto bene le esigenze.

Punto 2, MPT consente di risparmiare spazio e lo stato blockchain può essere considerato un enorme dizionario. In ogni blocco, solo una piccola parte delle chiavi viene aggiornata e la maggior parte delle chiavi mantiene ancora i valori originali. Utilizzando l'albero MPT, puoi aggiornare solo i valori chiave che devono essere aggiornati, senza copiare lo stato invariato in ciascun blocco.

Punto 3: Il vantaggio di MPT è che la verifica dello stato globale è stata completata utilizzando il valore della chiave di stato a cui si accede dall'hash root. Questo è anche il motivo principale per cui la scrittura dell'albero MPT richiede molto tempo. Se MPT non viene utilizzato, i nodi possono comunque verificare la coerenza dei dati durante la sincronizzazione dei blocchi.

Completando i punti 1 e 2 senza utilizzare MPT, possiamo aggirare il sovraccarico di MPT. Quindi dobbiamo progettare una soluzione basata su Trie (può essere inteso come Rocksdb) per archiviare i dati di stato della blockchain.

progetto

Progettiamo principalmente una soluzione basata su Trie per archiviare lo stato sulla catena. Secondo i primi principi, se non è presente una struttura dati MPT, non è richiesto alcun sovraccarico del sistema per eseguire MPT. Finché il sistema di contratto intelligente basato su Trie può essere implementato ed eseguito correttamente, significa che l’ottimizzazione è stata completata. In pratica, possiamo pensare a Rocksdb come a un Trie. Una comprensione più semplice è che si tratta di un database KV ad alte prestazioni.

Utilizza [globalstate as prefix_contract indirizzo_variabile nome_blocco altezza_blocco hash] come valore chiave del database KV, come nel seguente formato. Tra questi, 0x1 è l'indirizzo del contratto, Total è il nome della variabile, 1 è l'altezza del blocco e ABC1234 è il valore hash del blocco (verrà omesso in seguito)

stato_globale_0x1_totale_1_abc1234

In Ethereum Solidity, le variabili possono essere definite come Memoria, Archiviazione e Calldata. Ci concentriamo principalmente sul tipo di archiviazione perché verrà archiviato nello stato globale. Oltre alle variabili semplici, consideriamo anche la mappatura. Poiché l’ordine di grandezza degli utenti sulla blockchain è globale, ci sarà una mappatura KV estremamente ampia. Inoltre, tratteremo i tipi di dati come Array come semplici strutture dati e li memorizzeremo direttamente in Json in Rocksdb. Quando codifichiamo, dovremmo naturalmente stimare la grandezza dei dati valore nella struttura dati KV per scegliere un metodo di archiviazione appropriato.

Variabili dello stato di conservazione del contratto

Come possiamo raggiungere il primo e il secondo obiettivo di progettazione di MPT senza utilizzare MPT?

Supponiamo di avere una variabile Total nel contratto ERC20. Questa variabile cambierà solo quando il numero totale di token aumenta (Mint) o diminuisce (Burn), ma il valore di Total rimane quando l'utente A trasferisce denaro (Transfer) all'utente B. costante.

Per semplicità, supponiamo che l'indirizzo del contratto sia 0x1. Quando l'altezza del blocco è 1, il proprietario del contratto ha eseguito un Mint 2000. Sui blocchi con un'altezza compresa tra 2 e 8, l'utente ha effettuato più trasferimenti. L'altezza del blocco corrente è 9 .

A questo punto, dobbiamo solo interrogare il database per la chiave con il prefisso [globalstate_0x1_total_]. Sebbene il nostro ultimo blocco attuale sia 9, poiché la variabile Total non è cambiata nei blocchi 2-8, il primo risultato della query precedente sarà il valore di [globalstate_0x1_total_1], quindi troviamo l'ultimo valore della variabile Total, il Total variabile che è cambiata nel blocco 1.

A questo punto, viene generato un nuovo blocco. Supponiamo che l'utente esegua Mint altre due volte nel 9° blocco e nell'11° blocco. Qui troviamo una funzionalità di Rocksdb Se abbiamo la seguente chiave

stato_globale_0x1_totale_1  : 2000

stato_globale_0x1_totale_9 : 4000

stato_globale_0x1_totale_11 : 6000

Quindi il primo risultato della ricerca sarà sempre il blocco 1, non l'ultimo blocco 11. Poiché non abbiamo ancora trovato un parametro per modificare l'ordine dei risultati della ricerca nella documentazione di Rocksdb, abbiamo utilizzato un piccolo trucco, utilizzando un numero più grande come 100 per sottrarre l'altezza del blocco (in realtà sarà molto più grande) e riempirla con zeri, quindi gli ultimi blocchi verranno classificati per primi nei risultati della ricerca.

stato_globale_0x1_totale_089 : 6000

stato_globale_0x1_totale_091 : 4000

stato_globale_0x1_totale_099 : 2000

Tipo di mappatura dell'archiviazione

Come accennato in precedenza, la grandezza della chiave della struttura dei dati di Mapping può essere enorme, quindi è impossibile per noi convertire il dizionario Json di decine di migliaia di chiavi nel Mapping in una stringa. Altrimenti, il costo di aggiungere ed eliminare chiavi , o la modifica dei valori sarà molto alta.

Supponendo che l'indirizzo dell'utente sia 0x2, espandiamo leggermente il formato della chiave di archiviazione precedente:

[statoglobale_0x1_[saldo_0x2]_2] : 2000

Il precedente [nome variabile] qui è stato espanso in [nome variabile + Chiave del dizionario di mappatura]

I dati precedenti indicano che il saldo del saldo dell'utente 0x2 nell'altezza del blocco 2 è 2000. Se non sono presenti dati aggiornati per coprire il saldo corrente, i dati dell'utente nel blocco 2 rappresentano lo stato più recente.

stato_globale_0x1_bilanciamento_0x2_098 : 2000

stato_globale_0x1_totale_0x1_099 : 2000

Verifica blocco

Come la radice dell'albero Merkle, anche la radice dell'albero MPT rappresenta una verifica dello stato globale. Finché possiamo garantire la coerenza dei dati del blocco, se dobbiamo utilizzare MPT e scrivere Root nell'intestazione del blocco è una scelta di progettazione.

Abbiamo apportato alcuni miglioramenti alla progettazione del blocco in modo che l'intestazione del blocco contenga due corpi, uno è il blocco dati della transazione e l'altro è il blocco dati dell'aggiornamento dello stato.

Il blocco dati della transazione contiene l'hash di tutte le transazioni. I minatori o i nodi possono iniziare dallo stato globale di una certa altezza del blocco, eseguire tutte le transazioni nell'ordine indicato nel blocco dati della transazione e ottenere lo stato globale del blocco successivo. Se il volume delle transazioni è elevato, l’esecuzione parallela è improbabile (perché l’ordine delle transazioni verrà interrotto), quindi richiederebbe più tempo richiedere ai nodi di tutto il mondo di eseguire tutte le transazioni.

A tal fine, abbiamo progettato un blocco dati di aggiornamento dello stato, che include i valori chiave dello stato globale aggiornati dopo aver eseguito tutte le transazioni. Se si tratta di un nodo che si trova molti blocchi indietro, oltre a eseguire una macchina virtuale per eseguire tutte le transazioni, può anche aggiornare il contenuto del Body in base allo stato e inserire direttamente i valori chiave nel database per risparmiare potenza di calcolo e ridurre i tempi di sincronizzazione.

Naturalmente i valori chiave utilizzati per eseguire tutti gli aggiornamenti delle transazioni devono essere esattamente gli stessi del Diff contenuto nel blocco di aggiornamento dello stato, altrimenti questo nuovo blocco sarà illegale.

Supponiamo che ci siano 10.000 nodi nel mondo. Quando lanciamo un dado e impostiamo una probabilità dell'1% di eseguire una transazione, circa 100 nodi eseguiranno la transazione tra blocchi e altri nodi faranno affidamento sul contenuto dell'aggiornamento dello stato della connessione. blocco dati. Quindi quest'area Molti nodi nel sistema blockchain saranno in grado di salvare molte operazioni ripetute.

compiere

Dopo aver completato il progetto precedente, abbiamo immediatamente iniziato a implementare questa idea.

Innanzitutto, abbiamo integrato la VM Python nel sistema blockchain. Questa è una macchina virtuale Python implementata in Python, attualmente compatibile con il bytecode PY 3.10. Ci auguriamo che i contratti intelligenti possano utilizzare parte della sintassi di Python. Ad esempio, abbiamo solo bisogno di funzioni e non vogliamo che gli sviluppatori utilizzino Class, quindi attualmente non supportiamo completamente tutti i bytecode PY.

Per quanto riguarda il compilatore, Solidity deve sviluppare un compilatore dedicato per convertire il codice sorgente in bytecode EVM. Usando Python, puoi convertire facilmente il codice sorgente Python in bytecode PY con l'aiuto di questo eccellente linguaggio infrastrutturale con una storia di trent'anni. Gli utenti difficilmente noteranno il tempo di compilazione.

Il nostro repository di codici VM è il seguente. Tutti sono invitati a fornirci le proprie opinioni e a risolvere potenziali problemi di sicurezza:

Link: https://github.com/EcoPoW/python_stf_vm Nella seconda fase, abbiamo sviluppato una versione Python di ERC20 e il codice viene costantemente aggiornato. A differenza di Solidity, non utilizziamo parole chiave per identificare come vengono archiviate le variabili, tutte le variabili locali sono in memoria e utilizziamo le funzioni globali _get e _put per leggere e scrivere lo stato. Collegamento: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

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

Implementazione e miglioramento

Ci sono voluti circa due mesi dalla formulazione delle domande, alla progettazione e all'implementazione della codifica.

Dopo un'intera estate di progettazione + codifica effettiva, il nuovo sistema di contratto intelligente, che utilizza solo l'albero del dizionario Trie senza fare affidamento sulla struttura dati MPT, è pronto per essere eseguito (puoi provare a eseguire il nodo di test localmente tramite il clone Github). Bypassare lo storage smart contract basato su MPT significa che, con una larghezza di banda sufficiente, il tempo di sincronizzazione di un nodo con una dimensione di 100 milioni di KV può essere ridotto da diversi giorni a pochi minuti. Anche l’efficienza di esecuzione dei contratti intelligenti diventerà più veloce e una parte maggiore dei calcoli consumati dalla CPU verrà utilizzata per eseguire il bytecode anziché le operazioni di hash necessarie per costruire l’albero Merkle. Siamo stati fortunati perché, durante l'implementazione dei contratti intelligenti nel progetto, non abbiamo seguito direttamente il design "standard del settore", ma abbiamo prima provato l'ottimizzazione e la sottrazione e abbiamo ottenuto una blockchain del contratto intelligente con la "struttura dei dati" corretta. Perché a differenza dei prodotti Web2, che paragoniamo al cambio delle gomme mentre guidiamo un’auto, la blockchain Web3 è più simile al lancio di un razzo. È difficile apportare importanti miglioramenti strutturali a una blockchain funzionante, quindi possiamo solo migliorare il sistema “successivo” ed essere completamente preparati prima di andare online.

Al momento, la rete di test Testnet2 della blockchain BitPoW che abbiamo progettato è stata implementata. Tutti possono utilizzare MetaMask per connettersi a questa blockchain tramite RPC per testare e provare i trasferimenti ERC20 basati su Python VM. Allo stesso tempo, abbiamo ancora molto lavoro da fare e dobbiamo ancora fare affidamento sulla comunità per promuovere questa nuova infrastruttura blockchain.

Invitiamo tutti a conoscere e testare effettivamente l'implementazione di queste nuove tecnologie basate su concetti, inclusi test delle prestazioni dopo la rimozione di MPT e test di sicurezza di nuovi contratti intelligenti e nuove catene.

Riassumere

Finora abbiamo aggirato MPT e progettato una soluzione di storage di contratti intelligenti basata direttamente su Trie. Attualmente implementiamo questo miglioramento su una blockchain basata su Python VM come prova di fattibilità. Ci sono voluti circa tre mesi dalla scoperta del problema alla proposta di una soluzione e alla sua implementazione nel codice. Ma la cosa più importante di questo studio è che, come molte persone comuni, dopo aver appreso la conoscenza dell'MPT in classe, non è stata data ulteriore riflessione. migliorandolo. La soluzione non è complicata, ma richiede pratica e azione. La soluzione non è complicata, ma richiede pratica e azione. Solo pensando attivamente nella pratica possiamo trovare ispirazione e innovare ulteriormente. Sono molto grato a LXDAO per aver supportato questa ricerca e spero di incontrare più amici nella comunità interessati allo strato inferiore della blockchain. Il settore è ancora agli inizi e le infrastrutture sono lungi dall’essere mature. Ci auguriamo di promuovere la divulgazione della conoscenza alla base della blockchain in modo che più persone possano partecipare in prima linea all'innovazione tecnologica.