A note on the Stateless Ethereum initiative:
Research activity (understandably) slowed down in the second half of 2020 as all contributors adjusted to life on a strange timeline. But as the ecosystem gradually moves closer to Serenity and the Eth1/Eth2 merger, Stateless Ethereum work will become increasingly relevant and impactful. Expect a larger Stateless Ethereum year-end retrospective in the coming weeks.
Let’s go through the recap one more time: The ultimate goal of Stateless Ethereum is to remove the requirement of an Ethereum node to maintain a complete copy of the updated state at all times and to allow state changes to rely on a (much smaller) piece of data that proves that a particular transaction is performing a valid change. This solves a major problem for Ethereum; a problem that has so far only been pushed back by improving the client software: Growth of the state.
The Merkle proof needed for Stateless Ethereum is called a “witness” and it attests to a change of state by providing all the necessary information. unchanged intermediate hashes needed to arrive at a new valid state root. Witnesses are theoretically much smaller than the full state of Ethereum (which takes 6 hours at best to sync), but they still are. much bigger than a block (which must propagate to the entire network in just a few seconds). It is therefore essential to evaluate the size of witnesses to bring Stateless Ethereum to a minimum viable utility.
Much like the Ethereum state itself, much of the additional (digital) weight of witnesses comes from the code of smart contracts. If a transaction calls for a particular contract, the witness should by default include the contract bytecode. in its entirety with the witness. Code Merkelization is a general technique to reduce the load of smart contract code on witnesses, so that contract calls only need to include the bits of code they “touch” in order to prove their validity. validity. With this technique alone, we could see a substantial reduction in the number of witnesses, but there are many details to consider when dividing smart contract code into byte-sized chunks.
What is bytecode?
There are some tradeoffs to consider when splitting contract bytecode. The question we will eventually need to ask is “how big will the pieces of code be?” » – but for now, let’s look at real bytecode in a very simple smart contract, just 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 intended to run “inside” the EVM. Here you can see the same simple storage contract shown above, but respected in the 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 explained in a previous postThese opcode instructions are the basic operations of the EVM stack architecture. They define the simple storage contract, and all the functions it contains. You can find this contract as one of the examples of solidity contracts in the Remix the IDE (Note that the machine code above is an example of the storage.sol file after it has already been deployedand not the output of the Solidity compiler, which will have additional “startup” opcodes). If you unfocus your eyes and imagine a physical stack machine running step-by-step calculations on opcode cards, in the blur of the moving stack you can almost see the outlines of the functions defined in the Solidity contract.
Every time the contract receives a call message, this code executes in each Ethereum node validating new blocks on the network. In order to submit a valid transaction on Ethereum today, one requires a complete copy of the contract bytecode, as running this code from start to finish is the only way to obtain the (deterministic) exit state and associated hash .
Remember, stateless Ethereum aims to change this requirement. Let’s say all you want to do is call the function to recover() and nothing more. The logic describing this function is only a subset of the entire contract, and in this case the EVM only really needs two of the following: basic blocks opcode instructions 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 a witness provides the missing hashes of an intact state, a witness must also provide the missing hashes for unexecuted pieces of machine code, so a stateless client only requires the part of the contract that he executes. .
The code witness
Smart contracts in Ethereum are in the same place as externally held accounts: as leaf nodes in the huge single-root state trie. In many ways, contracts are no different from the external accounts that humans use. They have an address, can submit transactions, and hold a balance of Ether and any other tokens. But contract accounts are special because they must contain their own program logic (code) or a hash of it. Another Merkle-Patricia Trie associate, called the storageSort maintains any persistent variables or states that an active contract uses to go about its business during execution.
This visualization of cookies gives a good idea of the importance of code merklization in reducing the size of cookies. See this giant piece of colored squares and how much bigger it is than all the other elements in the trie? This is a single complete portion of smart contract bytecode.
Next to and slightly below are the persistent state chunks in the storageSortsuch as ERC20 balance mappings or ERC721 digital item ownership manifests. Since this is a sample witness and not a full state snapshot, these also consist mostly of intermediate hashes and only include changes that a stateless client would need to prove the next block.
Code merkleization aims to split this giant piece of code and replace the field codeHash in an Ethereum account with the root of another Merkle Trie, aptly named the codeSort.
Worth its weight in hashes
Let’s look at an example of this video from Ethereum Engineering Groupwhich analyzes some code slicing methods using a ERC20 token contract. Since most tokens you’ve heard of are made to the ERC-20 standard, this is a good real-world context for understanding code merkleization.
Because bytecode is long and unruly, let’s use a simple shortcut to replace four bytes of code (8 hexadecimal characters) with one . Or X character, the latter representing the bytecode required for the execution of a specific function (in the example, the ERC20.transfer() the function is used everywhere).
In the ERC20 example, by calling the transfer() the function uses a little less than half of the entire smart contract:
XXX.XXXXXXXXXXXXXXXXXX.......................................... .....................XXXXXX..................................... ............XXXXXXXXXXXX........................................ ........................XXX.................................XX.. ......................................................XXXXXXXXXX XXXXXXXXXXXXXXXXXX...............XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX.................................. .......................................................XXXXXXXXX XXXXXXXXXXXXXXXXXXXXXXXXXXXXX..................................X XXXXXXXX........................................................ ....
If we wanted to split this code into 64-byte chunks, only 19 of the 41 chunks would be needed to execute a stateless query. transfer() transaction, the rest of the required data coming from a witness.
|XXX.XXXXXXXXXXXX|XXXXXX..........|................|................ |................|.....XXXXXX.....|................|................ |............XXXX|XXXXXXXX........|................|................ |................|........XXX.....|................|............XX.. |................|................|................|......XXXXXXXXXX |XXXXXXXXXXXXXXXX|XX..............|.XXXXXXXXXXXXXXX|XXXXXXXXXXXXXXXX |XXXXXXXXXXXXXXXX|XXXXXXXXXXXXXX..|................|................ |................|................|................|.......XXXXXXXXX |XXXXXXXXXXXXXXXX|XXXXXXXXXXXXX...|................|...............X |XXXXXXXX........|................|................|................ |....
Compare this to 31 out of 81 chunks in a 32-byte chunking 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, it appears that smaller pieces are more effective than larger ones, because the almost empty pieces are less frequent. But here we need to remember that unused code also has a cost: every piece of unexecuted code is replaced by a hash of fixed size. Smaller pieces of code mean more hashes for unused code, and these hashes can be as long as 32 bytes each (or as small as 8 bytes). You might at this point exclaim “Wait! If the hash of pieces of code is a standard size of 32 bytes, how would it help to replace 32 bytes of code with 32 bytes of hash!?”.
Recall that the contract code is merkleizedwhich means that all hashes are linked together in the codeSort — the root hash we need to validate a block. In this structure, everything sequential unexecuted chunks only require a single hash, regardless of their number. That is, a hash can replace a potentially large member filled with hashes of sequential chunks on the merkleized code, provided that none of them are required for coded execution.
We need to collect additional data
The conclusion we reached is a bit disappointing: there is no theoretically “optimal” scheme for code merkleization. Design choices like fixing the size of code chunks and hashes depend on data collected from the “real world”. Each smart contract will be merkleized differently, so it is up to researchers to choose the format that provides the greatest efficiency gains for the activity observed on the mainnet. What does that mean, exactly?
One thing that might indicate the effectiveness of a code merkleization system Overhead merkleization costswhich answers the question “how much additional information beyond the executed code is included in this cookie?” »
We already have some promising resultscollected using a specially designed tool developed by Horacio Mijail of Consensys’ TeamX research team, which shows overheads as low as 25% — not bad at all!
In short, the data shows that, overall, smaller chunk sizes are more efficient than larger ones, especially if smaller hashes (8 bytes) are used. But these first figures are by no means exhaustive, because they only represent around a hundred recent blocks. If you are reading this and would like to contribute to the Stateless Ethereum initiative by collecting more code merkleization data, come introduce yourself on the ethresear.ch forums, or on the #code-merkleization channel on the Eth1x/2 research discord !
And as always, if you have any questions, comments, or requests related to “1.X Files” and Stateless Ethereum, DM or @gichiba on Twitter.
