EVM Bytecode Merklization

Transcript

so hey my name is C no thanks Piper for the shoutout so I want to motivate the talk by showing a diagram that Alex C generated as you know from the previous talk for for stateless clients you need to send a witness alongside with the block and I just have part of one of these witnesses and like you can see the tree structure here like you can see the hashes the nodes and whatever and this big block here is a code block like this is a contract code so you need to send contract codes with like any contract

that you use in a transaction needs to be sent in a in a stateless block and as you can see the of the size they can be quite big and this is what will be attacking so I will be going into the weeds we'll see some of the quirks of the EVM and by the end like if you follow you can just jump in and start attacking the problem yourself if you are interested and I will also share some data that we got from some of the main yet blocks that show that the approach we will be taking here will cut down on the size of the stateless blocks somewhat so stateless blocks are big the witnesses that you need to send include

all of the accounts of of the tree structure like all of the all of the storage items and all of the contract code I won't go into the like the info of stateless because we already talked about that but I will show you some data from from to a girl like from Igor and Alexei that was generated recently these are from some of the most recent blogs and like the Blut on top is an average of how much these block witnesses like wait basically so you can that should be megabytes re so it's on

the order of one eight hundred kilobytes to 1.5 megabytes and the brown line here is the hashes that you need to send for the local proofs which is right now the biggest contributor to to the block block size and the next one is contract code which is around one third of the whole witness size and after you you already realized that a possible change that we'll be doing in the stateless roadmap is to change the tree structure from a hex route to a tree to a binary tree and that would reduce the number of

hashes that you will need to send by almost a third and then contract code will be become the biggest contributor to witness size so if we can reduce that we'll be reducing the overall witness size and one reason why this would matter to adaptive developers is because if we don't do this then you would need to pay gas for every byte of a contract that you're invoking so let's say you're invoking a contract that weighs 24 kilobytes that's a maximum size for now you would need to let's say pay 72,000 guests and if the contract is smaller than somewhat smaller but you the

crucial point is that any contract that your transaction invokes you would need to pay gas per byte of the total amount of contract size so the intuition here is that a transaction only invokes part of the contract codes let's say you have your interaction within ERC 20 token you only want to call the approve function which is a small part of the whole code we why do we need to send the whole contract code when we are only using one function of it so so what we want to try here is to only send the parts of the code that are

necessary to execute the transaction and some some proofs that that prove their validity and we do this by like chunking the code and creating a Merkel tree out of these chunks and during like a block transmission we send only the necessary chunks and their proofs so imagine we have a miner and somebody it wants to create a contract like this is an imaginary bytecode that somebody is is creating

we so the minor this is the runtime by a bytecode not the in it goes by the way the minor as of now it does a single pass over the over the bytecode to to check for jump tests if you know what they are so jump tests are the valley locations in in evm bytecode where you can jump to it already does a pass over the bytecode to determine this like during the same pass what we would be doing is we distinguish what we call basic blocks and these are these are blocks of the code that don't contain

any control for change like there's no jumps no return no stop so whenever we come come upon one of these up codes we stop the block and we start a new one and the correct the main characteristic of these blocks is that either a block starts at the first byte of the byte byte code or the first byte or the first opcode is a jump test this is this is crucial as we will see later on and later on we we don't want to have too small chunks I will explain why later so so therefore we kind of merge

these these basic blocks together to get a minimal like a minimum size and in this in this diagram this minimum size is 32 as you can see here so so this byte code let's say the minor did a pass and determined that these are the four basic blocks all of them start with jump tests now as you might know the the etherium state contains like of a tree this is the tree it's not an accurate picture like we have the hexer a tree and so on and just like yeah it's a tree and in the leaves you have the accounts which have these

fields like state road balance noms and and and code hash so the important thing is that contracts like you store the hash of a contract code in the leaf of the state tree but what we'll be changing here is that instead of storing the code hash what we do is we make a tree out of the chunk so these are the four terms of our byte code we make a miracle tree out of it the keys of these chunks are the first byte of like so like this oh shoot sorry yeah this is like this is the index of the first byte

of this chunk for it to is the first index of the other chunk and we'll use that to to store the chunks like we use those as as keys and we restore the root of this Merkle tree in the in the account and so the contract is now deployed it's on on the chain and a user comes and wants to to use this contract by sending a TransAm transaction to it so what when the miner wants to include the transaction it's it has to execute it and while executing it it keeps track of which chunks in the in the contract have

been touched so let's say this specific transaction touches the first chunk and the third chunk of the of the contract so what it does is in addition to sending all of the accounts and storage items necessary for the transaction it also sends these two chunks as well as the like the hashes so all of the the rest of the merkel proof that that prove the validity and saudis this multi proof is included in the block now the block and the witness propagate across the

network and a stateless client that wants to to verify the block receives receives the transaction verifies the proof to make sure that it's the all the hashes match and then it can reconstruct the byte code because it knows the full length of the byte code and it knows the index of the spite of each a chunk and it leaves all the other chunks zero and it can do jump test analysis safely because it knows that every chunk starts with with a jump

test so so a sightless client can can receive only those parts that ever necessary and still execute a transaction safely now to to to test our intuition that transactions only use a small part of their contracts code they invoke we did some some experiments on on 50 main yet blocks and you can see that the blue lines here are how much code you would need to send for for a book block if you if you were to send the whole contract code and the red line here is how much

the chunks and the witness and witnesses you would have to send if you were to do mobilization and you can see that we would get like 40 to 60 percent saving if we were to do code mobilization and this has the consequence that if when we want to do gas route pricings you wouldn't need to pay for the like you wouldn't need to pay for the size of the contract that you're invoking you would only pay for how much of that contract you're using in the transaction now to work were to go from here we can we can experiment with a few things like the minimum size of these basic blocks

and we can we can use like in my experiment I use the hex or tree to to generate the proofs but we can use a binary tree which will reduce the proof hashes by by three times and something else that is also exciting that that others are experimenting with is not so I use like jump tests as a boundary between the chunks and to see why this this was this was important is because imagine you have despite code here and you divide it by arbitrary borders so like let's say we have a fixed size like

each hunk is 32 bytes it could happen that you have a push at the end of one chunk and the next chunk starts with a with a number that is exactly the same as up code jump test this way when the stateless client receives this proofs and the chunks it wouldn't know if this is a push data or a jump test so it could happen that they would execute the transaction differently from from clients that have the full code and in order to to fix this problem there are multiple ideas

one is to add some metadata to each on so that you would know how many of the first bytes are our data or up code or what what Alec C is pursuing is to validate validate the contract statically so so that before like during runtime you can be sure that every jump goes to a valid jump test so basically this would mean effectively like disabling dynamic jumps in EVM yeah that was it thank you questions so in your chart that compared the full

witness size to the chunked witness size is does that include like all like if the same contract is included multiple times does it include them merged into one proof or or how does that work so yeah this is this is in the whole block yeah we we these appliqué the contracts so if you if you're using the same contract multiple times in a block then you would only send it once does this have changes to sort of like

smart contract dev and compiler design things like that so the changes would be I mean you would need to again gas route pricing is a thing you would have to probably change the price of of coal and also any any other up code that users contract code like Xcode hash expertise Xcode call Ella like so these would be affected compilers could may be optimized for this by like if they if if they knew what is the chunking scheme they could localize their relevant like parts of

the code that are executed together they could put them close to one another so that in the in the miracle tree those chunks would be close and would share a lot of the proof this is some optimization that compilers could do when less question okay um so I'm not sure this is an issue but if so I the it's the miners who produced the proofs but I I if I send a transaction have to pay gasps relevant to how much code I will use sometimes I don't know that because which code will get touched is determined by what order the miners exclude the transaction just comment on

that so yeah during the like transaction execution you could only we could we could charge conservatively so we could consider the worst case and at the end of the transaction could maybe do a refund yeah I I think I think there in my current model we're not going to be increasing the gas cost of the specific operations like coal and toxic OData instead I would suggest to introduce a separate gas counter which only going to account for the increase in witness so we decouple that from the we don't have

to like mess about with the let's say making call dynamically dynamically cost you so unpredictable cost of coal no I don't think it's the right approach and I think we should in instead do the second counter where we are or as we go along through the transaction we account how much witness we've produced so far and and charging us and it has some other issues as well but yeah yeah as you say like these parts are still being specified like there is no specification this is just how I did it but of course yeah and we were discussing these things further at this weekend so thank you very much enough for you talk thank you

[Applause] you