Ethereum's execution transaction performance bottleneck

Preface

This paper describes the performance analysis of Ethereum's consortium chain, but it actually refers to Ethereum. The performance here does not refer to the performance of the entire blockchain network, but refers to the performance of a single node. The same analysis can analyze any Ethereum system altcoin (modified from eth fork), Ethereum system alliance chain (such as our company's fisco-bcos or Xunlei's Xunlei chain, etc.)

Then, this article will involve some basic Eth knowledge, but some parts are still a bit difficult to understand without systematic learning. I guess, my subsequent articles will slowly start to update the knowledge content of the Ethereum system, and this article will Focus on the performance analysis of Ethereum. At the same time, because of the structure of Ethereum and the flaws of the leveldb adopted by Ethereum for random reads and writes, if multi-chain/side-chain technologies are not considered, as the amount of data increases, I am concerned about the future performance of Ethereum.

This article was first published in my own knowledge column.

If you need to reprint, you need to obtain consent and indicate the source!

The core that affects the performance of Ethereum

In the Bitcoin system, when analyzing the problem of low Bitcoin tps, we never consider the time for Bitcoin to execute scripts, mainly because the scripts of btc are non-state (UTXO model) and are very short. (Not Turing complete). Compared with 10 minutes of block generation and network synchronization time, this time is too short under the limit of 1M block size. Ethereum is a state model, and it was proposed from the beginning with the characteristics of Turing completeness. Contracts can be very complicated to write.

In our company's performance test, as the transaction volume increases, the performance of the Ethereum execution contract declines very quickly. If it is adjusted to a block of 1s, the proportion of this time will be very huge (for the alliance chain), even for the Ethereum public chain of 15s a block, the impact of this increase in the proportion of time has become a complete one compared to btc. A factor that cannot be ignored.

The main reason for the length of time the Ethereum EVM takes to execute the contract is that in addition to the time-consuming normal calculations, in fact, another piece of time-consuming is spent on "status reading", which corresponds to IO.

Ethereum uses the "World State" (World State) to record the changes of the Ethereum state. Due to this unique data structure, as the recorded transaction volume increases, every time a specific value is read, a visit is generated. The number of times of the database will increase by log(n), and these accesses are discrete and random. In the face of such a large number of discrete random reads, leveldb has very low performance, so as the transaction volume increases, The execution speed of the transaction (contract) will become slower and slower, and the calculation method of the slow rate will be given later.

The reason for the slow execution rate is related to the "world state".

Ethereum's state of the world
This article does not specifically introduce the composition and operating mechanism of the world state. This content will be a separate article in the future. After all, this is the core of the management state of Ethereum. Here first introduce the knowledge needed to discuss the article.

The essence of Ethereum is a state machine transition triggered by a transaction, but the "snapshot" of all transitions of this state machine is recorded by the "world state" tree, so that any snapshot can be backtracked. The implementation of this world state tree is essentially similar to the implementation of git. Readers who understand the principles of git do not need to read this paragraph.

The data structure used by Ethereum to implement the world state tree is called "the modified Merkle Patricia tree (trie)" (hereinafter referred to as MPT). The detailed implementation method and the steps of adding or subtracting nodes will not be introduced here. Let’s take a macro perspective. Look at this tree:

We intercept the tree starting from block2, assuming that we are in the state corresponding to block2 (that is, the snapshot at the time of block2) corresponding to the state tree as shown in the figure above. In the implementation of Ethereum, the state of contracts and accounts (the account system of Ethereum will be introduced in a later article) is stored in the upper layer of the world state-State Trie (implemented by MPT), that is, the contract and account are both upper-level states The leaf node of the tree. For each contract, a storage tree implemented by MPT will also be hung under the contract. Storage Trie is used to store the historical state of the contract's data changes.

And we pay attention to the nature of the MPT tree (that is, the principle of git). For example, we only look at the StateTrie in the upper half. When the data of the leaf node is updated, it is actually equivalent to inserting a new node, and then this new node arrives The series of paths of the root node all regenerate new nodes, and the new nodes generated will contain the "references" of the previous nodes, so that the newly generated increments can find unmodified nodes through these references. The specific implementation and design are not described in this article, just understand that every time a new state is changed, new nodes need to be generated from the leaf to the root of the tree. The same is true for the lower-level StorageTrie. At the same time, it should be noted that for Ethereum, if the lower-level storagetrie is moved, it will not only cause the update of the storage tree of the current contract, but also cause the update of this contract node, resulting in the same for the upper StateTrie. Update.

So the problem is very simple, because as the transaction volume increases, the tree will definitely become larger and larger, so you only need to figure out the relationship between the number of times the tree is updated (inserted) and the height of the tree, and because every time The update needs to go from the leaves to the root of the tree, then you can use the transaction volume to estimate the number of times the tree is updated, infer the approximate height of the world state tree at this time, and estimate the number of new nodes, thereby inferring performance/storage related information.

Note: The term estimation is used here because it is difficult to predict which contracts will be called and how large the transaction volume will be in the Ethereum public chain. Therefore, it is impossible to accurately obtain more accurate figures. In the alliance chain, these two aspects can basically be estimated, so this inference is much more accurate and more useful. This is also the reason why my paper is aimed at consortium chains, but for public chains, getting a rough estimate is enough
MPT and PATRICIA trie (Patricia tree)
MPT is essentially a new data structure generated by combining hash and Patricia tree. Here, I strongly condemn the analogy of Ethereum's MPT as the Merkel Tree and Bitcoin's Merkel Tree in other popular science articles. . There is a huge gap between the two data structures, and it is misleading to say so directly.

Patricia tree is a compressed prefix tree. Because the traditional prefix tree has a node for each character, there is a lot of space waste, so a data structure that compresses nodes with only continuous single characters into the same node is proposed, which is the patricia tree. Because the MPT tree is actually the Patricia tree after removing the hash attribute, our problem here is the relationship between the number n of data inserted in the random insertion of the Patricia tree and the expected (average) or maximum value of the tree height, but the MPT ratio Patricia trie considers other things in the process of node generation, but it has nothing to do with the height of the tree.

In fact, the randomness of node compression caused by the randomness of insertion cannot accurately predict the height of the tree like traditional data structures such as binary trees. When I first thought about it, I reduced the problem to a problem of "inserting a string randomly into a string set, and finding the longest common prefix length between this newly inserted string and the set of existing strings" (the specific reason should be discussed The data structure of MPT can be known). Fortunately, after searching many papers, some predecessors have carried out in-depth discussions on this issue. Among them, a series of papers from 1985 to 1999, led by Pittel Based on the relationship between the number of random insertions and tree height, such as "Asymptotical growth of a class of random trees", "On the height of PATRICIA search tree", etc., followed by an article "Universal" published by Luc Devroye in 2005 "Asymptotics for Random Tries and PATRICIA Trees" summarized many previous articles and put forward some key conclusions. My basis here comes from this paper.

In this paper, the author summarized and proposed for the binary Patricia tree, its tree height expectations, the relationship between the maximum tree height and the number of insertions is:

In fact, if you only care about the performance of Ethereum, if you have understood the above things, then you can make predictions by inferring yourself. However, below, I will put forward some conclusions on the Ethereum alliance chain, and give some results of our test. From these results, the efficiency of the Ethereum public chain can be roughly predicted