Burden of Proof: Code Merklization
Notes on the Stateless Ethereum initiative:
Research activity slowed down (understandably) in the second half of 2020 as all contributors adjusted to life on strange schedules. However, as the ecosystem moves closer to Serenity and the Eth1/Eth2 merger, Stateless Ethereum work will become increasingly relevant and influential. Expect to see a more substantial year-end stateless Ethereum retrospective in the coming weeks.
Let me summarize again. The ultimate goal of stateless Ethereum is Requirements Ethereum nodes that allow state changes by maintaining a full copy of the updated state tree at all times and instead relying on (much smaller) pieces of data to prove that a particular transaction is making a valid change. This solves a major problem with Ethereum. This is a problem that has been exacerbated by improvements to the client software so far. country growth.
The Merkle proof required for Stateless Ethereum is called a ‘witness’ and provides all the information to prove the state change. unchanged An intermediate hash is needed to reach the new valid state root. The witness is theoretically much smaller than the entire Ethereum state (taking at most 6 hours to synchronize), but still. much bigger It is not a block (which must be propagated to the entire network in just a few seconds). Therefore, increasing the size of witnesses is paramount to making Stateless Ethereum a minimum viable utility.
Like the Ethereum state itself, the additional (digital) weight of the witness comes from the smart contract code. If a transaction calls a specific contract, the witness must contain the contract bytecode by default. overall With witnesses. Code Merkelization is a common technique to reduce the smart contract code burden on witnesses, so that contract invocations only need to contain bits of code that are ‘touched’ to prove validity. While this technique alone can see a significant reduction in witnesses, there are many details to consider when splitting smart contract code into byte-sized chunks.
What is bytecode?
There are several pros and cons to consider when splitting contract bytecode. The question we ultimately have to ask is, “How big will the chunk of code be?” – But for now, let’s look at the actual bytecode of a very simple smart contract to understand what it is.
pragma solidity >=0.4.22 <0.7.0; contract Storage uint256 number; function store(uint256 num) public number = num; function retrieve() public view returns (uint256) return number;
When this simple storage contract is compiled, it turns into machine code that runs ‘inside’ the EVM. Here we see the same simple storage contract as shown above, but compliant with individual EVM instructions (opcodes).
PUSH1 0x80 PUSH1 0x40 MSTORE CALLVALUE DUP1 ISZERO PUSH1 0xF JUMPI PUSH1 0x0 DUP1 REVERT JUMPDEST POP PUSH1 0x4 CALLDATASIZE LT PUSH1 0x32 JUMPI PUSH1 0x0 CALLDATALOAD PUSH1 0xE0 SHR DUP1 PUSH4 0x2E64CEC1 EQ PUSH1 0x37 JUMPI DUP1 PUSH4 0x6057361D EQ PUSH1 0x53 JUMPI JUMPDEST PUSH1 0x0 DUP1 REVERT JUMPDEST PUSH1 0x3D PUSH1 0x7E JUMP JUMPDEST PUSH1 0x40 MLOAD DUP1 DUP3 DUP2 MSTORE PUSH1 0x20 ADD SWAP2 POP POP PUSH1 0x40 MLOAD DUP1 SWAP2 SUB SWAP1 RETURN JUMPDEST PUSH1 0x7C PUSH1 0x4 DUP1 CALLDATASIZE SUB PUSH1 0x20 DUP2 LT ISZERO PUSH1 0x67 JUMPI PUSH1 0x0 DUP1 REVERT JUMPDEST DUP2 ADD SWAP1 DUP1 DUP1 CALLDATALOAD SWAP1 PUSH1 0x20 ADD SWAP1 SWAP3 SWAP2 SWAP1 POP POP POP PUSH1 0x87 JUMP JUMPDEST STOP JUMPDEST PUSH1 0x0 DUP1 SLOAD SWAP1 POP SWAP1 JUMP JUMPDEST DUP1 PUSH1 0x0 DUP2 SWAP1 SSTORE POP POP JUMP INVALID LOG2 PUSH5 0x6970667358 0x22 SLT KECCAK256 DUP13 PUSH7 0x1368BFFE1FF61A 0x29 0x4C CALLER 0x1F 0x5C DUP8 PUSH18 0xA3F10C9539C716CF2DF6E04FC192E3906473 PUSH16 0x6C634300060600330000000000000000
as described previous post, these opcode instructions are the fundamental operations of the EVM stack architecture. It defines a simple storage contract and all the functionality it contains. This contract can be found as one of the following Solidity contract examples: IDE Remix (For reference, the above machine code is an example of Storage.sol. After it has already been distributed, which is not the output of the Solidity compiler with additional ‘bootstrapping’ opcodes. If you unfocus your eyes and imagine a physical stack machine moving along with the step-by-step calculations of the opcode cards, you can almost see an outline of the functionality deployed in the Solidity contract in the blur of the moving stack.
Whenever a contract receives a message call, this code is executed within every Ethereum node validating new blocks on the network. Currently, submitting a valid transaction on Ethereum requires a full copy of the contract bytecode. Because running that code from start to finish is the only way to get the (deterministic) output state and associated hashes.
Remember that stateless Ethereum aims to change this requirement. Let’s say all you want to do is call a function. search() And nothing more. The logic that describes that functionality is just a subset of the full contract, in which case the EVM really only needs two contracts. basic block Opcode instruction to return the desired value:
PUSH1 0x0 DUP1 SLOAD SWAP1 POP SWAP1 JUMP, JUMPDEST PUSH1 0x40 MLOAD DUP1 DUP3 DUP2 MSTORE PUSH1 0x20 ADD SWAP2 POP POP PUSH1 0x40 MLOAD DUP1 SWAP2 SUB SWAP1 RETURN
In the stateless paradigm, just as the witness provides missing hashes of the untouched state, the witness must also provide missing hashes for unexecuted pieces of machine code so that stateless clients only require parts of the contract that are being executed. .
witness of the code
Smart contracts on Ethereum exist in the same place as externally owned accounts: as leaf nodes in a huge, single-root state tree. Contracts are in many ways no different from externally owned accounts used by humans. They have addresses, can submit transactions, and can hold balances in Ether and other tokens. However, contract accounts are special because they must contain their own program logic (code) or corresponding hashes. Another related Merkle-Patricia Trie is storage tree An active contract maintains variable or persistent state that it uses to conduct business during execution.
This witness visualization highlights how important code merkleization is in reducing witness size. Look at the huge mass of colored squares. And how much bigger is it than all the other elements of the tri? This is a single complete delivery of smart contract bytecode.
Next to it and slightly below it is a piece of permanent state. storage tree, such as ERC20 balance mapping or ERC721 digital item ownership manifesting. Since this is an example of a witness rather than a full state snapshot, these too are mostly made of intermediate hashes and contain only the changes needed for the stateless client to prove the next block.
Code merkleization aims to split huge chunks of code and replace fields. code hash From an Ethereum account with the root of another Merkle Trie codeTrie.
value of hash
Let’s look at the following example: This Ethereum Engineering Group videoLet’s analyze a chunk of code in some ways using: ERC20 token contract. This is a good real-world situation for understanding code merkleization, since many of the tokens you have heard of are created according to the ERC-20 standard.
Because bytecodes are long and unwieldy, we’ll use a simple abbreviation that replaces 4 bytes of code (8 hexadecimal characters) with one of the following: . or X character, the latter representing the bytecode required to execute a particular function (in the example ERC20.transfer() functions are used throughout).
In the ERC20 example move() The function uses less than half of the entire smart contract.
XXX.XXXXXXXXXXXXXXXXXX.......................................... .....................XXXXXX..................................... ............XXXXXXXXXXXX........................................ ........................XXX.................................XX.. ......................................................XXXXXXXXXX XXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.................................. .......................................................XXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXX..................................X XXXXXXXX........................................................ ....
If we were to split that code into 64-byte chunks, only 19 of the 41 chunks would be required for stateless execution. move() The remaining required data comes from witnesses.
|XXX.XXXXXXXXXXXX|XXXXXX..........|................|................ |................|.....XXXXXX.....|................|................ |............XXXX|XXXXXXXX........|................|................ |................|........XXX.....|................|............XX.. |................|................|................|......XXXXXXXXXX |XXXXXXXXXXXXXXXX|XX..............|.XXXXXXXXXXXXXXX|XXXXXXXXXXXXXXXX |XXXXXXXXXXXXXXXX|XXXXXXXXXXXXXX..|................|................ |................|................|................|.......XXXXXXXXX |XXXXXXXXXXXXXXXX|XXXXXXXXXXXXX...|................|...............X |XXXXXXXX........|................|................|................ |....
Compare this to 31 of the 81 chunks in the 32-byte chunk scheme.
|XXX.XXXX|XXXXXXXX|XXXXXX..|........|........|........|........|........ |........|........|.....XXX|XXX.....|........|........|........|........ |........|....XXXX|XXXXXXXX|........|........|........|........|........ |........|........|........|XXX.....|........|........|........|....XX.. |........|........|........|........|........|........|......XX|XXXXXXXX |XXXXXXXX|XXXXXXXX|XX......|........|.XXXXXXX|XXXXXXXX|XXXXXXXX|XXXXXXXX |XXXXXXXX|XXXXXXXX|XXXXXXXX|XXXXXX..|........|........|........|........ |........|........|........|........|........|........|.......X|XXXXXXXX |XXXXXXXX|XXXXXXXX|XXXXXXXX|XXXXX...|........|........|........|.......X |XXXXXXXX|........|........|........|........|........|........|........ |....
On the surface, smaller chunks appear to be more efficient than larger chunks. Mostly empty Chunks are less frequent. However, it is important to remember here that even unused code costs money. Each unexecuted chunk of code is replaced with the hash of: fixed size. The smaller the code chunks, the more hashes there are for unused code, and those hashes can be up to 32 bytes each (or as little as 8 bytes). At this point, you might be exclaiming, “Wait a minute! If the hash of a chunk of code is the standard size of 32 bytes, how does replacing 32-byte code with a 32-byte hash help!?”
The contract code is: merkleizedThis means that all hashes are linked together. codeTrie — Root hash needed to validate the block. In that structure, what sequential An unexecuted chunk only needs one hash, no matter how many hashes there are. That is, a single hash can take the place of a potentially large portion of a Merkleized code tree full of sequential chunk hashes, as long as none of them are required for coded execution.
Additional data needs to be collected
The conclusion we build up to is a bit of a twist. There is no theoretically ‘optimal’ scheme for code Merkleization. Design choices such as modifying code chunks and hash sizes Relies on data collected about the ‘real world’. Since every smart contract is Merkleized differently, the burden is on the researcher to choose the format that provides the greatest efficiency gains for observed mainnet activity. What exactly does that mean?
One thing that can indicate how efficient a code Merkleization scheme is: Merkization overheadIt answers the question, “How much additional information beyond the code executed is included in this witness?”
We already Some promising resultsCollected using specially designed tools Developed by Horacio Mijail of the Consensys TeamX research team, this product has an overhead of as little as 25%. Not bad at all!
That is, the data shows that smaller chunk sizes are generally more efficient than larger chunk sizes, especially when using smaller hashes (8 bytes). However, these initial figures are by no means comprehensive as they represent only about 100 recent blocks. If you’re reading this and interested in contributing to the stateless Ethereum initiative by collecting more substantive code merkleization data, introduce yourself on the ethresear.ch forum or in the #code-merkleization channel on the Eth1x/2 research discord!
And as always, if you have any questions, feedback, or requests related to “The 1.X Files” and Stateless Ethereum, please DM me or tweet me @gichiba.
