Farewell MPT, the 100-day smart contract blockchain optimization plan is complete.

Goodbye MPT 100-Day Smart Contract Blockchain Optimization Plan Successfully Implemented

Author: KJ

Dear friends of LXDAO, hello everyone!

This article is written by KJ, a member of the LXDAO expert team. It covers many aspects of blockchain underlying design. If readers have relevant knowledge, such as MPT (Merkle Patricia Trie), Trie (Prefix Tree or Dictionary Tree), and Ethereum EVM (Ethereum Virtual Machine), it will be even better.

Reading this article can enhance understanding of the mechanism of blockchain on-chain storage and optimization methods.

• Crypto Lawyer’s Perspective Why Most RWA Tokenization Cannot Be Achieved?
• Vitalik said he has never sold ETH for personal gain, we took stock of his personal and charitable wallets
• LLoreMs Building Decentralized On-Chain Narratives

Background and Motivation

Before discussing the improvements to MPT, let’s talk about the background of this research.

I am currently doing a Ph.D. and working on public chain design. Besides the core consensus upgrade, which is Proof of Useful Work, another important task is to implement a smart contract system compatible with ETH. We have already implemented a bytecode-based virtual machine in Python and integrated it into the contract system of a blockchain. Surprisingly, it is compatible with Ethereum RPC. We have built a smart contract that conforms to the ERC20 standard using Python for testing. Naturally, in the underlying execution of the contract, we need to implement a key-value data structure capable of accommodating tens of millions of users (similar to Mapping in Solidity, used to store the token balances of each account, which could be billions of accounts).

Next, the work of public chain design naturally reaches concepts such as MPT and Trie. We referred to Ethereum’s design with its three trees – Trie, MPT, etc. Here, I would like to thank Professor Xiaoyi of Peking University for his blockchain video, “16-ETH-State Tree Bilibili” Lecture 16. It helped us quickly understand this part of the knowledge.

Video link: https://www.bilibili.com/video/BV1Vt411X7JF?t=11.0

Discovering Bottlenecks

Fortunately, before we started implementing smart contract calls with MPT, we whimsically ran a simple MPT tree benchmark program on AWS’s servers. When we tried to insert one billion KV (key-value) data using Trie and MPT, we were surprised to find that the performance of the MPT tree was so low.

Running the code below, we observed that inserting ten million KV pairs into Rocksdb took minutes for Trie, while it took hours for MPT. When we increased the test data volume to one billion, the MPT insertion program took several days to run. This means that when blockchain uses the MPT data structure to run smart contracts, speed will be greatly limited.

The experiment proved that the overhead of using the MPT data structure not only slows down the execution speed of smart contracts but also reduces the synchronization speed of blockchain nodes (even when there is abundant bandwidth, it still takes several days to download data from other nodes and reconstruct the node). However, due to the difficulty of modifying Ethereum’s data structure design, even if we rewrite or optimize it in a “faster” programming language, if there are no updates to the underlying data structure, the blockchain will struggle to break through the performance limitations.

test_mpt_write.py

import mpt

import rocksdb

class DBWrap:

def __init__(self, db) -> None:

self.db = db

def __setitem__(self, key, value):

self.db.put(key, value)

def __getitem__(self, key):

return self.db.get(key)

conn = rocksdb.DB(‘mpt.db’, rocksdb.Options(create_if_missing=True))

storage = DBWrap(conn)

root_hash = conn.get(b’root_hash’)

print(‘Prev root_hash’, root_hash)

trie = mpt.MerkleLianGuaitriciaTrie(storage, root_hash)

start = 0

while True:

for i in range(start, start+10000):

k = str(i).zfill(32).encode(‘utf8’)

trie.update(k, k)

root_hash = trie.root_hash()

print(f”root_hash hex {root_hash.hex()}”)

print(start)

start += 10000

if start > 10000000:

break

test_mpt_write.py

import rocksdb

conn = rocksdb.DB(‘trie.db’, rocksdb.Options(create_if_missing=True))

start = 0

while True:

print(start)

for i in range(start, start+10000):

k = str(i).zfill(32).encode(‘utf8’)

conn.put(k, k)

start += 10000

if start > 10000000:

break‍

Link: https://gist.github.com/kernel1983/f746c1470376e422a8efe3ee6782901d

Do you remember when we first learned how to code, our teachers told us a basic principle, Program = Algorithm + Data Structure? If we limit ourselves to the data structure, even if we optimize the algorithm to the maximum (which often requires years of academic effort and in many cases can hardly be improved further), it is difficult to break through the performance limitations of the current data structure. So, a very academic solution is to look for a better performing MPT algorithm, which could take years to research. As pioneers in this field, Verkle Tree optimizes blockchain data structures using polynomial methods, while we will explore some more unique and simple ideas.

We approach it from first principles and ask: Can we do without MPT? If we can bypass MPT and implement smart contracts directly on the Trie, we can avoid the overhead of MPT (according to Ma Yilong’s first principle, something that doesn’t exist doesn’t incur performance overhead).

As a trade-off, our new design may not be directly compatible with the existing MPT, but because we don’t modify the Ethereum RPC interface, we can reuse many existing Ethereum infrastructures, such as Etherjs and MetaMask. Bypassing MPT is an optimization of internal data structures, which is a free exploration of blockchain performance.

Preliminary Knowledge

Rocksdb and Trie

Trie, a tree data structure mentioned in university textbooks, is a more advanced data structure. In Professor Xiao’s video, MPT is built on top of the Trie. We can consider Trie as implemented in memory.

However, in our engineering work, we cannot directly use Trie to implement products because we also need to persist data on the hard disk. This step involves many engineering optimizations, so we generally use Rocksdb to implement MPT trees.

Rocksdb is an open-source fork based on leveldb by Facebook. It uses the log-structured merge-tree (LSMT) as its underlying data structure. From an abstract perspective, we can think of Rocksdb as an optimized and persistent trie.

The basic usage of Rocksdb is very simple, mainly involving three basic operations: get, put, and prefix iterate.

State Machine

A state machine is a tool commonly used to model blockchains. It is very simple: adding an input to an original state produces a new state.

Ethereum’s global state can be understood as the state of a state machine. For example, in block 1, the key-value pairs of all smart contracts represent a global state, and all transactions in a block, executed by the Ethereum Virtual Machine (EVM), can be seen as inputs to the state machine. For instance, a Mint contract invocation changes a user’s balance and the contract’s total variable to 1000 in block 2.

One easily overlooked concept in state machines is the state transition function, which defines rules for inputs. When an input is not valid, the input is rejected. For example, when trying to transfer a negative amount of funds to someone else, the transaction will not be executed (of course, a smart contract with bugs can accept such transactions. In Ethereum, the state transition function can be customized using a Turing-complete language).

MPT Introduction

Maybe you have already heard of Ethereum’s three trees: the transaction tree, state tree, and receipt tree. They are all MPT trees, which stands for Merkle Patricia Tries. Among them, the state tree is perhaps the most suitable use case for MPT data structure. For more details, you can refer to Mr. Xiao’s video explanation.

MPT tree is built on top of the Trie data structure and, like a Merkle tree, it can compute a root hash from all state data and place it in the Ethereum block header. The Ethereum block header contains the root hashes of the three MPT trees, which are commonly referred to as the three trees.

Can we not include the root of the global state tree in the block header? Yes, in Bitcoin’s block, only the transactions are included, and the Merkle root of the transactions is placed in the block header (using the Merkle tree but not MPT). However, Bitcoin does not have smart contracts or the concept of a global state. When Ethereum was initially designed as a blockchain with smart contracts, it abandoned Bitcoin’s 1MB block design, the UTXO model, and instead chose the MPT data structure and account model. It also used Gas to solve the halting problem and met the requirements for global state in the execution of smart contracts.

So, what is the goal of using MPT in Ethereum?

1. To find the corresponding state of the blockchain through the Merkle root in the block header.
2. To save space occupied by duplicate data.
3. To verify the correctness of the state using the root hash.

The first point is that it is a rigid requirement. When executing the EVM, it needs to read various states. If a design pattern similar to Bitcoin UTXO is used, it is necessary to trace back many blocks to obtain the account balance state of a certain user. The use of MPT satisfies this requirement well.

The second point is that MPT saves space. The blockchain state can be seen as a huge dictionary. In each block, only a small part of the keys are updated, while the majority of keys remain unchanged. Using MPT trees, only the keys that need to be updated are updated, without duplicating the unchanged states in each block.

The third point is that the advantage of MPT is that using the root hash to access the state key has already completed the verification of the global state. This is also the main reason why it takes time to write the MPT tree. If MPT is not used, nodes can still verify the consistency of data during the synchronization of blocks.

If we complete the first and second points without using MPT, we can bypass the overhead of MPT. So we need to design a solution based on Trie (which can be understood as Rocksdb) to store the state data of the blockchain.

Design

We mainly design a solution based on Trie to store the state on the chain. According to first principles, if there is no MPT data structure, there is no system overhead required to run MPT. As long as the smart contract system based on Trie can be implemented and run correctly, it means that the optimization has been completed. In practice, we can treat Rocksdb as a Trie, or more simply, a high-performance KV database.

We use [globalstate as prefix_contract address_variable name_block height_block hash] as the key-value pair of the KV database, for example in the following format. Where 0x1 is the contract address, Total is the variable name, 1 is the block height, and ABC1234 is the block hash (which will be omitted later).

globalstate_0x1_total_1_abc1234

In Ethereum Solidity, variables can be defined as Memory, Storage, and Calldata. We mainly focus on Storage type because it will be stored in the global state. In addition to simple variables, we also consider Mapping, as the number of users on the blockchain is on a global scale, so there will be large KV mappings. Besides, data types like Array, we will treat them as simple data structures and store them directly as Json in Rocksdb. When encoding, we should naturally estimate the order of magnitude of the Value data in the KV data structure in order to choose an appropriate storage method.

Contract Storage State Variables

If we do not use MPT, how can we achieve the design goals of the first and second points of MPT?

Assuming we have a variable Total in the ERC20 contract, this variable only changes when the total quantity of tokens increases (Mint) or decreases (Burn), but remains the same when a transfer (Transfer) occurs from user A to user B.

For simplicity, let’s assume the contract address is 0x1. At block height 1, the contract’s Owner performed a Mint of 2000 tokens. From block height 2-8, there were multiple transfers between users, and now the current block height is 9.

At this point, we only need to query the keys with the prefix [globalstate_0x1_total_]. Although our current latest block is 9, since the Total variable did not change from block 2 to 8, the first result of the above query will be the value of [globalstate_0x1_total_1]. So we have found the latest value of the Total variable, which changed at block 1.

At this time, a new block is generated, assuming the user has performed two Mints in block 9 and block 11. Here we find a feature of Rocksdb. If we have the following keys:

globalstate_0x1_total_1: 2000

globalstate_0x1_total_9: 4000

globalstate_0x1_total_11: 6000

Then the first result of the search is always block 1, not the latest block 11. Because we haven’t found a parameter to change the order of search results from the Rocksdb documentation, we used a trick and subtracted the block height from a larger number like 100 (actually much larger) and padded it with zeroes. This way, the latest block will be at the front of the search results.

globalstate_0x1_total_089: 6000

globalstate_0x1_total_091: 4000

globalstate_0x1_total_099: 2000

Storing Mapping Types

As mentioned earlier, the number of keys in a Mapping data structure can be massive, so it is not feasible to serialize tens of thousands of keys into a single string. Otherwise, the cost of adding, deleting, or modifying keys’ values would be terrifying.

Assuming the user’s address is 0x2, let’s slightly expand the previous storage key format:

[globalstate_0x1_[balance_0x2]_2]: 2000

Here, the previous [variable name] is expanded to [variable name + Mapping dictionary key]

The above data represents that the user 0x2 has a balance of 2000 at block height 2. If there is no updated data to overwrite the current balance, then the data at block 2 represents the latest state.

globalstate_0x1_balance_0x2_098: 2000

globalstate_0x1_total_0x1_099: 2000

Verifying Blocks

Similar to the Merkle tree root, the MPT tree root represents a verification of the global state. As long as we can ensure the consistency of block data, it is a design choice whether to use MPT and include the Root in the block header.

We made some improvements in block design by including two bodies in the block header: one for transaction data and another for state update data.

The transaction data block contains the hashes of all transactions, and miners or nodes can start with the global state at a specific block height and execute all transactions in the order given by the transaction data block, resulting in the global state of the next block. If there are a large number of transactions, and execution is not likely to be parallel (as it would disrupt the order of transactions), requiring all nodes in the world to execute all transactions would be time-consuming.

Therefore, we designed the state update data block, which includes the updated global state key-value pairs after running all transactions. If a node is significantly behind in blocks, it can also directly insert key-value pairs into the database based on the content of the state update body, in order to save computing power and reduce synchronization time.

Of course, the key-value pairs updated by executing all transactions and the diff contained in the state update block must be completely consistent, otherwise, this new block would be invalid.

Assuming there are 10,000 nodes in the world, when we roll the dice and set a probability of 1% to execute a transaction, approximately 100 nodes will execute block transactions, while other nodes will trust the updated data block content. In this way, many nodes in this blockchain system will be able to save a lot of repeated calculations.

Implementation

After completing the previous design, we immediately started implementing this idea.

First, we integrated the Python VM into the blockchain system. This is a Python virtual machine implemented in Python, which currently supports bytecode for PY 3.10. We hope that smart contracts can use some of Python’s syntax, such as only needing functions and not wanting developers to use classes, so we currently do not fully support all PY bytecode.

Regarding the compiler, Solidity requires a dedicated compiler to convert source code into EVM bytecode. Using Python, we can easily convert Python source code into PY bytecode with the help of this excellent infrastructure language with thirty years of history, and users can hardly feel the compilation time.

Our VM code repository is as follows, and we welcome everyone to give us suggestions and fix potential security issues:

Link: https://github.com/EcoPoW/python_stf_vm

In the second step, we developed a Python version of ERC20, and the code has been continuously updated. Unlike Solidity, we did not use keywords to identify the storage method of variables. All local variables are in memory, and we use the _get and _put global functions to read and write state.

Link: https://github.com/EcoPoW/BitPoW/blob/master/contract_erc20.py

Thanks to the Annotation feature provided by Python 3, we can convert the transaction data originally called from RPC into types that Python can accept, such as Uint256 and Uint8 directly converted into Python int. The output values of the function can also be automatically converted into ABI types accepted by RPC.

In the third step, we implemented the _get and _put functions, using the solution designed in this article to store the blockchain state data read and written by the Python VM during the operation of the blockchain. The reading and writing of state data will go through memory first. Only when the transaction is successfully executed, all modifications to the state will be summarized into state update data blocks and broadcasted to the entire blockchain network, along with the transaction data blocks and block headers processed by the consensus algorithm.

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

Implementation and Improvement

It took us about two months from problem identification, design, to coding implementation.

Through the design and actual coding throughout the summer, the new smart contract system, which relies solely on the Trie data structure instead of the MPT data structure, can now be implemented (you can try running a local test node by cloning it from GitHub). Bypassing the MPT-based smart contract storage means that, under conditions of sufficient bandwidth, the synchronization time for nodes with a size of one hundred million key-value pairs can be reduced from several days to a few minutes. The execution efficiency of smart contracts will also increase, with more CPU processing power dedicated to executing bytecode rather than the hash operations required for constructing Merkle trees. Luckily, when implementing smart contracts in engineering, we didn’t directly adopt the “industry standard” design. Instead, we tried optimization and subtraction first and ended up with a smart contract blockchain that has the correct “data structure”. Unlike Web2 products, which can be likened to changing tires while driving a car, Web3 blockchains are more like launching rockets. It’s difficult to make major structural improvements to a running blockchain, so we can only improve the “next” system and prepare thoroughly before going live.

Currently, the Testnet2 of our BitPoW blockchain design has been deployed, and everyone can connect to this blockchain using MetaMask through RPC for testing and try out ERC20 transfers based on the Python VM. At the same time, there is still a lot of work to be done, and we still need to rely on the community to drive this new blockchain infrastructure.

We welcome everyone to learn about and test these technology implementations driven by new concepts, including performance testing after removing MPT and security testing for new smart contracts and new chains.

Summary

So far, we have bypassed the MPT and designed a smart contract storage solution directly based on Trie. Currently, we have implemented this improvement on a Python VM-based blockchain as a proof of feasibility. From problem discovery to proposing a solution to implementing it in code, it took us about three months. But the more important aspect of this research is that, like many ordinary people before this, after learning about MPT knowledge in the classroom, we did not further consider improving it. The solution is not complex, but it requires practice and action.

The solution is not complex, but it requires practice and action. Actively thinking in practice is what leads to inspiration and further innovation.

Thank you very much to LXDAO for supporting this research, and we hope to meet more friends in the community who are interested in the underlying technology of blockchain. This industry is still in its early stages, and the infrastructure is far from mature. We hope to promote the popularization of knowledge about the underlying technology of blockchains and enable more people to participate in the forefront of technological innovation.

We will continue to update Blocking; if you have any questions or suggestions, please contact us!