zkEVM #06 - Devconnect AMS'22

[Music] okay sorry for this um yeah okay so merkel patricia tree mpt i will just start with how with the json that is returned by a get proof call it basically it contains two proofs one is account proof and the other one is storage proof so uh in the account proof there are some rlp streams uh each one of them is a branch or extension node but extension node is just a special case of a branch uh so and each of these branches each each of these rows is a branch and uh which contains 16 children uh basically hashes of these children so there are 16 sub streams each of 32 uh length and um the so for example the second one uh if you has the second row uh you get one of the values in in the first row and uh one of the and it's at the position from one of the uh 0 to 15 and this position is determined by the account address so the account address is once it is hashed it is uh 32 bytes uh long and then this is converted into nibbles so each byte is two nibbles um from 0 to 1 to 15 value and this nibbles determine the positions of the uh elements in in their parent elements so the but the last one the last row is account leaf which contains this information here balance code hash nuns and the root of a storage tree uh and then the situation is is similar in storage proof do we again have some branches like this is uh the root branching storage tree and it's it's only one in this case uh and this is storage leaf which contains uh key and value in this case value is one the key is what is um so um the in this case for example there are there's only one nibble used uh because there's only one branch and the remaining 63 nibble cells are stored in in a in a leaf so the the general idea of the of the circuit is um we put each branch into 16 rows uh and uh then uh each of these 16 uh the the hash of these 16 rows is computing there's no it should be a bit colored but it's it's not the blocks are not clearly seen here but uh so for example um yeah this is one block and the hash of this block uh in 16 rows needs to be at the proper position in the in the parent branch and this position is given by by nibbles so um yeah in in the circuit we we actually have uh two two proofs in parallel so um on the la on the left side there is a proof a kind of a of a read operation so what was the state before the storage modification and on the right side there is a uh state or the proof uh for the for the state after the storage operation so this is a proof of one storage operation uh for for for a storage modification at some particular key uh and um this key is the same for for both of these two parallel proofs and the circuit makes sure that uh both proofs are the same in most of the rows except at the rows um which are given by these nibbles so there is an additional column called a modified node uh so that means the position of the children in in this branch and the so these two proofs differ differ at at these rows um yeah and once once uh we arrived to the uh to the uh account leave the hash of the account leaf is computed and checked to be uh in the apparent branch and when we move to the storage tree um the hash of the root branch needs to be we check that it's in the account leave so that's that's the basic idea but uh yeah if we zoom in a bit uh into the branch block this is this is uh a block of one branch it actually contains uh 19 rows not 16 because there's an additional uh data so for example in br branchini there are some uh nlp metabytes like this uh 249 this is this specifies uh the length of the of the branch and it's it's sometimes these uh metabytes are of length three and sometimes of length two so there's some some branching needed to uh to correctly check uh the things um so the uh the branch is put into 16 rows so this this the first two for example are not empty here the the third one is empty it only has this 128 value which is some specifics of the rlp encoding and in in case when this is not a regular branch but an extension node there are two additional rows um which i'll cover uh just in a second so so usually uh in when when there's a regular branch uh this the the render linear combination of these bytes is computed and then a lookup is made uh into ketchup circuit uh to to check whether this error c corresponds to the lc of of this uh hash in this case at the position 15 but in the extension note case it's a bit different in this case uh we need to check that the extension node is kind of a branch where the path is a bit longer to to to arrive to the branch so there are some additional nibbles and these nibbles are stored here and then the hash of the this branch is stored here so there are constraints to check that uh the hash of this branch is stored here and then we compute the lc the random linear combination of this extension node and then this is checked that the hash of this needs to be in the in the branch above um yeah but but uh that's not these are not the only constraints it needs to be that need to be checked uh this uh parent thing uh it also needs to be checked that uh the storage modification happens at the correct uh address and at the correct key um so what is uh the circuit is computing the uh lc of the nibbles uh and then this llc of the address for example is compared to the address let's check to beat the correct one but it's it makes it a bit difficult because um these are nibbles not bytes and we are computing random linear combination of bytes uh so sometimes this nibble need needs to be computed by by uh 16 and and the multiplication factor and sometimes with uh by it needs to be multiplied by one uh and if there would be only regular branches this would be uh easier because then this uh would be just alternating so once you need to multiply by 16 and once you need to multiply by one but there if there is some extension noting between extension node have some additional nibbles and when it has an odd uh number of nibbles uh this uh alternation is uh broken so there needs to be some additional branching for for the constraints um yeah and when we arrived to the to the leaf then this um so we were computing the the lc of the nibbles so like like this way from the from this branch from the first two branches we get this value and then the remaining nibbles are stored here and we continue computing the erlc but it's again some branching is needed because these nibbles the remaining nibbles are stored here in um in a compressed format and this format depends uh on how many on whether there are odd or 11 or or or even number of nibbles um uh yeah this is this shows how the yeah the storage leaf it it takes two rows um for the c pro for the left proof and and two rows for the right proof uh and yeah one of the things that that need to be checked is uh so some um sometimes this is the the the length of the nibbles is um it uh varies so uh and because we are computing the erlc of this of leaf we need to make sure that uh after uh the uh length is uh after the specified length of this stream is uh finished uh then there are really zeros uh after this uh position yeah and then there are quite some uh special cases so for example um sometimes uh when an ev any new value is added to the to the tree uh an existing cliff is uh replaced by a branch so for example in this case uh we have some some leaf which is uh the the erp is here and it's inside this branch zero but after a new value is added uh this leaf is replaced on the right side by a branch so here another branch appears um yeah and the circuit just uses some placeholder values at this side and the constraints then are goes like this uh the storage on the right the the leaf on the right side needs to be checked uh the hash of the leaf needs to be checked to be here at the proper position and then the hash of this branch needs to be at this position where the branch was inserted but on the right side the hash of this leaf needs to go one level above so needs to be there in branch zero and there are some further constraints in these cases uh so for example it needs to be checked that in this branch there are only two leaves uh okay uh one at the yeah one one leaf that was uh added by this new value and one leaf that was uh previously uh in the brand zero and and that was replaced by uh by by branch um yeah and also it needs to be checked that um this new leaf the the leaf that drifted from branch zero to to this branch one has the same value as the leaf on the left side so for this reason there is an additional uh row where this uh information about this drifting leaf is given um yeah and another special case is um when there was no uh value specified at some key uh the get proof returns just branches so there is no leave uh and in this case again there is just some holder some place holder values are used and it needs to be checked that at this position it just empty row in the branch um yeah and analogously it there are cases uh when we are close to the account leave so for example if there is um no uh uh no branch or if if there is just uh a leaf in the um uh in in the if there is only one level in the storage tree so there is no branch then again um oh no yeah it's it's if you if you are in the first level we are not comparing uh we are not checking the hashes to be in the parent branch but in the account leave so for this some additional branch branching is needed and uh yeah that's that's a similar case so uh yeah that would be [Music] you