zkEVM #04 - Devconnect AMS'22

[Music] okay uh welcome cece to talk about kajak thank you barry iran uh and uh i introduced uh how we do the question circuit and um i was supposed to present this with carlos but he had a feeling unwell so he's part two um so the uh the first thing we have to handle is the permutation part and uh the permutation has a lot of bit-wise operation so we use the base conversion trick and to get a sense of how the operation we need to do in a the permutation remember that cat chart is organized the input into a state of 25 lands and each land is a 64-bits data and then there are like different operations uh theta rho and c pi some and they they need to do like actual operations on different lengths they need to do a bit rotations uh on single length and sometimes when you do slightly more complicated bitwise operations um like four lens or uh always some other constants so uh naively uh you you kind of want to like um uh do a pure lookout approach for example we have a here b here there are all uh lens and and i have a subscription too for a binary and and we can uh but like look up uh if you have a polynomial degree of uh 2-16 then you can only like look up like eight bits uh xor to the eight bits that all the possibility of a b two a bits and then you can uh split in uh split a into eight groups b into x groups and do add lookups and then add the results together that's uh how uh not naively you you perform a bitwise operation on two lens but this is uh really in efficient so we use this uh spa space approach um so spa space is instead of using the binary base we use like a base 13 and then ai and bi is still bits and then we can add a and b together this is just one addition in the circuit but then we will get this thing and we then have to find another injective mapping to map this arithmetic sum into the bitwise operation result so uh the flow looks like this the left hand uh the left uh dotted arrow is a bit wise operation lookup which is inefficient so instead we convert that binary input into the spa space and then we have a sparse base input and then we do a chip arithmetic operations on the spot on input on the smart space and then we get the output then we convert the sparse base output into the binary output so there's a general general rule of thumbs and but there are some limitations for example the base size cannot be like arbitrary big um so we we are operating on bn curve so you know two uh you only have two 54 bits and so as that means your your base cannot be like greater than 15 and also the larger base you use the less less chunks you can look up at a time so uh it might cause some like inefficiency in the base conversion um so uh i try to like uh printed some result of like uh if you use uh 2-16 and look up with five chunks the largest space you can use is nine but if you look at four chunks uh the largest base you can use is 15 uh so these are the examples and the uh the injective mapping is that um let's say you have a abcd there are uh four bits and then you need to perform and uh you need to perform a complicated uh bitwise operation like a x or negative b and c and x or d and you get the output bits but you'll find that a arithmetic [Music] linear combination of abcd and you get the arithmetic sum of this value and but that that parameter must satisfy the probability that um like for example if uh the output is three three always map to one three always map to one so we always map to one like you cannot have the same value here but map to two different like one or zero so if you can find this uh this mapping this uh this mapping then you can convert the output in a spar base into the uh into the binary output so that's a general tricks in the in a permutation uh i didn't show that detail of the rotation and and here comes the difficult part in the circuit implementation i um callous made this awesome diagram um so at the um at the middle of circuit everything works fine like with the um with the spa base but like at the end of circuit we have some branching uh and that branching uh we we took some time to figure out how to do that branching so we need to um [Music] at the end of uh a permutation we need to determine uh if this this is uh this state is the final output or do we need to take extra input and continue the next round of permutation so uh if this is the end then we go the left-hand side we need to input a flag and check is either a zero or one so it's affect consistency and then uh on the left hand side we have a l type b9 it's an operation that adds a round constant to the length and uh that run constant we need to convert it to the base nine and and then uh we we add it to the state and then run the base conversion to convert it from base nitro base two and then uh we get the output state and ana oh wait oh this is right and this is left okay and all right oh this is right this is that okay on the right hand side and we have to absorb the input to the output state and then we convert it from base 9 to base 13 and then we um we added uh iota um the run constant at the uh at the end of this stat because uh uh for uh because we're reusing the the previous uh ax or like b and c and d we use that d for the next input and iota but then um and then we we get the output state b13 and then we we need to use that flag to multiply the output and add it together to determine the real output state yeah here is a just a flake consistency gauge to check either the flag is zero or one and here is the mixing gate um to combine the result from the both branch into the same output and here is how we um like the circuit is determined at the compilation time and let's say you have um but like when um with in in the real use case you might have the input that require like um to catch if and some input requires three catch if like it's um it's it's determined at probing time and how do we do that we use the state machine approach um so we defined two different states absorbed and finalized and if you um if you have like for example the first um first hashing job has uh 140 bytes and you need to catch if to process that um so you can assign the first uh first state to absorb and second state to finalize and and then we have the second hash job that has uh 372 bytes and it needs a three three hrf to complete the hash job and then you can assign the first two to absorb and the last one is finalized so take away here is once we define the uh rule of the state transition so we can have the fixed circuit that takes uh the arbitrary input with the text arbitrary input and also we have the padding chips that would we take the last input we actually take the input and and pass through the padding chip it uh to determine if it needs needs padding or not and we take that uh input to the uh permutation chip and to get a intermediate uh state here and then for the uh for the next round of catcher f um uh suppose this is this is the finalized state and we need to add a padding and then we also this preset we need to take the previous intermediate state and combine it to with the new input to the permutation and get the final output states and oh there was a there was a part hiding on the top of the slides um wait do i have a way to access it oh okay probably not so here we have three columns we have um uh input rlc uh and input lens and the output so these three columns uh can be consumed by other circuit they can look up the uh hash input to the hash output so that's how like we we use the ketchup circuit in the harder circuit uh yeah i think that but okay i get qa or something it's like it's the end of tonight um so i think that yeah for a round yeah so the red number is uh 10k um because you it determines on the the one operation that used most of the rows and which is the rotation bit rotation uh part and so we have to perform a bit rotation for um 25 lens and each lens takes a 17 rows of lookup and then we have uh 24 rounds of permutations in cachif so that's that's the 10k transformer okay thank you [Music] you