Introduction: Merkelization of EVM bytecode
Editor's Note: This article comes fromUnitimes（ID：Uni-times）Editor's Note: This article comes from
Abstract: A stateless client needs to send the smart contract code called in the block as part of the block witness. Contract code is the second largest contributor to stateless block bandwidth overhead. Code merkleization is believed to help reduce this overhead. This article explains in detail how we split the contract code into blocks, Merkleize these blocks (author note: refers to making these blocks form a Merkle tree) and transmit only the blocks necessary for transaction execution. Based on experiments done with recent mainnet blocks, we can see that this approach saves code transfers by 40-60% in total.
secondary title
Stateless blocks are large
Under the stateless model, (at least some) nodes do not need to store state, and rely on other nodes (such as miners) to package in blocks all necessary state (including contract code) and Merkle proofs proving the validity of these states. This means much greater network bandwidth than before. Alexey Akhunov and the turbo-geth[5] team have been doing experiments to measure the block witness size of historical mainnet blocks. Below are the measurements for the last 50,000 blocks. The red line tracks the amount of contract code that needs to be sent in a stateless block, which is the second largest source of block witness size. If Ethereum migrated from the current hex trie to a binary trie, the hash portion of these witnesses would be reduced by ~3x, making the contract code the main source of witness size.
Data from github[6]. Graph showing stateless block witness composition for 50,000 recent mainnet blocks. These values are moving averages over a window of 128 blocks.
secondary title
No need to send the full code
To see exactly how this works, let's imagine a new contract being deployed. We scan the contract code and identify the basic block [7] (see algorithm [8]) (author's note, a basic block can be understood as a piece of code executed sequentially). Note that the client only needs to scan the code once for JUMPDEST analysis, so no high overhead is introduced. These basic blocks have two characteristics:
image description
A basic block of imaginary bytecode
Each basic block either starts at index 0 or at JUMPDEST. This is to allow stateless clients to safely perform JUMPDEST analysis (more on this later).
Each basic block does not change the control flow (eg no JUMP). So we can be sure that once we start executing a basic block, either it will run to the end or it will run out of gas. We assume this solution will be more efficient, but haven't tested its alternatives for comparison.
For efficiency, adjacent basic blocks are merged until each basic block has a minimum length of 128 bytes (this is a configurable parameter). They are then inserted into the trie, using the index of its first byte as the key. The client eventually stores the root of this trie in the newly created account that records the contract. As shown below, the code trie actually becomes a subtree of the state trie (similar to the storage trie).
Let's test this by submitting a transaction that calls the contract. Miners execute transactions and mark the blocks touched during execution (blocks 1 and 3 in this case). When publishing a block, the miner will include the proof of the state of the contract account and the turbo proof of touching the code block [9].
image description
After receiving the block, the stateless client can verify that the contract is part of the state and has the correct properties: balance, nonce value, state root, and code root. It can then validate the code block and its key against the code root. The above information is enough for the client to reconstruct part of the bytecode from these blocks and leave other blocks empty. It is worth noting that according to the block splitting algorithm we employ, the client knows that every block (except the first one) starts with JUMPDEST, so it can safely perform the jump.
secondary title
experiment
experiment
secondary title
where to go
where to go
As you may recall, the minimum length of each block is a configurable parameter (set it to 128 bytes above). Modifying this parameter has two opposing effects on the size of the block witness. For example, reducing to 32 bytes makes the block granularity finer, thereby reducing the total amount of code that needs to be sent. But at the same time, the depth of the trie tree is also increased, which eventually leads to an increase in the number of hashes required for proof. The next step will be to conduct a more thorough analysis of the minimum block size setting to see if there is a most space-efficient value. Regardless of the value of the minimum block size, switching from a hexadecimal trie to a binary trie reduces the hash required for proofs by 1/4 (see here [11]), further reducing the size of block witnesses. size.
For this prototype, we chose to split the code into basic blocks, but various other splitting algorithms exist, some simpler and some more complex. The easiest way is to divide the code into fixed-size blocks (such as every 32 bytes for a block). Currently, the only issues with this solution revolve around the PUSH data and JUMPDEST analysis.
Expanding on this basis: if we split the bytecode at arbitrary boundaries, the operands of the PUSH opcode and other multibyte opcodes introduced in the future could be mistaken for JUMPDEST (0x5b) by clients receiving the block. As shown below, a client with complete code can learn that JUMP is invalid (since 0x5b is an operand of PUSH1) and stop execution. However, a client that receives blocks 6 and 8 but not block 7 will jump to location 41, which parses the contract differently. We will briefly mention schemes that avoid this problem and support arbitrary bounds later.
To solve this problem, Martin Holst Swende proposed to add a metadata to each block, specifying how many bytes of the header are the operands of PUSH. The verifier can then skip these bytes during JUMPDEST analysis. Another avenue that Alexey is exploring is disabling dynamic jumps in the EVM (at least for contracts that wish to merkleize their code), allowing us to analyze jumps statically in one pass at deployment time rather than at each during code execution. Alex Beregszaszi proposed that the use of contract control flow graphs can better guide Merkelization. Meanwhile, Christian Reitweissner proposed a proof-of-execution scheme in which a Merkleized DAG is created from the control flow graph of the contract. I can't objectively evaluate his thinking in this article, and hope he can explain more in the future.
The results may show only negligible gains in efficiency for different segmentation algorithms. In this case, the simplest algorithm will be the wisest choice. The good news is that we have at least one algorithm that, on early data, seems to significantly reduce the amount of code transferred in stateless blocks.
Original link:
Original link:
Reference link:
