ZK Whiteboard Sessions – Module Thirteen: Fast Recursion with Plonky2

Transcript

foreign [Music] welcome to another episode of the ZKA whiteboard series uh today I'm here with uh my friend co-worker um applied cryptographer extraordinaire William Bourgeois Williams studied math at epfl and then has been working on pocket photography and zero knowledge proof systems for a while he is in in my opinion one of the top applied cryptography engineers in the world so really happy to have William here to

talk about wonky too all right thanks um glad to be here um so yeah I'm gonna talk about plunky two uh which is the proving system we've developed at polygon zero um so what is planck 2. um so Planck 2 is a proving system based on Planck plus custom Gates yeah which is sometimes called turbo Planck um so that's the IOP and we then need a paranormal commitment scheme and for that we use fry so the the IOP is like the part of the

proving system that basically verifies that uh you know the the proof is that allows us to argue that some proof is valid and then the polynomial commitment scheme is what like encodes that yeah exactly yeah yeah because because we're like checking relations about polynomials and then Paul Newman scheme allows us to do that succinctly yeah exactly so this is the information theory of like writing a program inside a an arithmetic circuit for example and this is the crypto how to make it like succinct and verifiable [Music] um and and we built plunky two with one main goal in mind it's for fast recursion so we wanted to build the fastest um recursive proof system

but but not just fast recursion also very very fast uh proofs in general yeah no exactly yeah wanted to to build the fastest prover um that was also able to do recursion yeah um cool so what are recursive proofs when you talk about recursion like what what does that mean right yeah uh good questions so recursion is um a technique where you verify a proof inside another proof so in a proving system um you have two algorithms the prover uh p and the verifier V okay and this perfect system outputs a proof pi and then you want to produce another proof

um that's Pi is valid okay the easiest way to do so is just to um right the in a circuit okay so your proving system is based on arithmetization like r1cs or like Planck and if this aromatization is powerful enough you can write any kind of program in the circuit V is an example of a program so you can write V in inside the circuit and since V accepts if and only if the proof Pi is valid with high probability

if the proof system is sound then just writing V in a circuit should work for recursion yeah because so so the verifier is some computation we know that we can express that computation in a circuit and so we can have a proof that uh is valid if and only if the proof that it's verifying is about exactly yeah yeah you could also that would be a very bad idea you could also write P inside the circuit but yeah that's the that's why uh Zero Energy Buffs are so powerful is that you can verify them succinctly and then also like write them succinctly in a circuit okay cool so what are the current uh approaches to recursion how are people uh approaching

this problem right now so pre-plonky tip so a pre-plunky two um so pretty too like uh even pre-plunk let's say um we had proof system like proof systems like graph 16. um that's used sparring friendly elliptic curves okay so 16 uh uses analytic curve e uh which has base field fq okay uh and it's pairing friendly that just means it has some additional structure that you know gives this nice kind of nap that we that helps for exactly yeah um and

and then um the printing system uh uses this electric curve e over fq and there's another field that you can Define on this elliptic curve it's FP okay so without going too much into details P divides the order of the elliptic curve so the elliptic curve is a an Abilene Group which has an order and you take p a factor a prime factor of this order um and so you can work on FP which we call the scalar field so we have the base field and the scalar yeah base yeah the base field is where like the elliptic curve points are and then the scalar field has order equal to

the order of yeah the group exactly and then and then the magic of it is that you have an action of FP uh on E which takes a scalar X and the point p and where you get the so-called scalable multiplication x times P which belongs to the curve okay okay and so like this operation of scalar multiplication is fully uh fq operations even if x is in FP so what does this mean for the verifier right so um in a system like graph 16 or really

any proof system uh using elliptic curves the verifier v um we'll have to do operation in both uh p and fq so yeah I should mention that the proving system itself um is over FP okay so if it's either Planck or r1cs like the actual arithmetic circuit that you will build will be over FP so what I'm like writing my programs then so to speak or writing my statements and then

I'm trying to prove though I'll be using values yeah exactly your scalar values will all be like key elements of this scalar field FB all right but that sounds fine right because on a CPU like I have my really fast MacBook Air and I I know that my CPU can do uh operations in FP and fq like pretty efficiently so so what's what's the issue with the recursion yeah okay so yeah as Brandon said like there's no issue in general like rough 16 and like all um print system based on apt curves are totally fine uh the issue comes up when you try to do recursion Okay so we want to write V so we want to write the verifier inside a circuit

um and so as I wrote before we'll have to do operations over both FP and fq and so the issue for recursion is that if we stay on the same curve then FP apps are those are very cheap because this is the native field of the um proofing system but fq apps are very costly okay um just because it's uh the printing system itself is not not over

um fq so we have to do something called non-native arithmetic so there's there's been some improvements over the year but um but it's still very costly to do and so all and so you end up with a verifier circuit that's very large and and so it's costly because I I can't just express my fq values in FP because if I do a bunch of fq multiplications it will overflow at a different point exactly yeah okay so I have to express fq values as like I break it up into some number of Limbs and then through range checks to check exactly yeah sounds expensive it is so what so but

but there's a solution right that that uh existing proving systems use right there there's some like maybe not totally optimal yeah approach um exactly so there's something called two cycles of elliptic curves so in a two-cycle um you have your original curve e and and second curve e Prime um e Prime is defined with base field FP so the scalar field of E and has a scalar Shield fq okay which is the base field of e okay so you you basically switch the base and scalar field compared to e okay and what do you get by changing curves

by using e Prime so like if you instead select the proof Pi is over e but now if you write your verifier V over e Prime okay you're right verified in the circuit over a prime then the scalar field of e Prime is fq which is the base field of e so like all the fq ups will be very cheap okay so now fq is cheap and then um one issue that comes up immediately is that FP operation become expensive so like fpr version will have to be done non-natively so FP now becomes costly

but in general the verifier does a lot more operations over fq for example pairings are like very expensive fq operations and so you gain something by changing curves because now all the fq operation can be done basically for free okay cool so so the most expensive part of verifying the proof is now is like pretty cheap yeah and okay so that I mean that seems fine what's the what's the catch okay so um it is fine the biggest catch is if you want to use a pairing a proving system using pairings such as graph 16 or any Brewing System using kcg the kcg Paranormal commitment scheme

then we don't know any such Cycles so e and e Prime of bearing friendly so we want something like that okay if we want to have like graph 16 on both curves but the issue is that we don't know any such cycle with reasonable size okay so I think the the size of the the best known cycle is uh between seven and 800 bits okay which which is huge when you consider like your CPU is doing 64-bit operations and so you're doing like a

ton of field arithmetic exactly in that field so so yeah your operations become way too slow and actually I think you're much better just using something like graph 16 over a way a smaller curves and then do all the after operation like non-natively yeah yeah so that's an approach that's taken by like Aztec I think exactly yeah um so if you want to look those up those are like the m and T curves okay um and so that's the big issue with uh Cycles elliptic curve if you want to use um printing systems using pairings um if you

if you if you want to use a print system that doesn't use pairings but that's also based on elliptic curves um there's something called Halo Okay so um so one of the primary commitment scheme that works with elliptic curves and it's based on the discrete logarithm problem is uh the IPA based PCS so so what does IPA stand for uh in our product argument okay that's also known as a bullet or brutal proofs

um so that's also a paranormal commitment scheme um using elliptic curves it's based on the discrete log as I said so d-log as compared to graph 16 or kcg that are based on pairing related security assumptions and so the discrete log um means the discrete log problem means that you can use curves of size 256 bit okay that will give you 128 bits of security okay so so that's much cheaper than our 700 but exactly and much cheaper than the 400 bits you need if you actually want security with bearing friendly curves

um so one issue with IPA one very big issue with IPA based opener commitment scheme is that the verification is linear so linear in the size of your circuit okay which sounds terrible for recursion because as I said before recursion you want to write the verifier in a circuit if the very strike if the verifier is linear you will end up with a very large circuit which is bad for recursion um but this really nice technique called Halo gives away to make the make the verification logarithmic by using something called

accumulation so it's an accumulation scheme okay and accumulation means the instead of verifying the whole proof in recursion they defer the verification until the end of the process and so so that means like I like I'm trying to do trying to generate or cursive proof and so I'll verify part of the proof in the circuit and then basically basically say like here's this other part that you have to check later and you have this like strong guarantee that this proof that I'm checking here is valid if and only if the the Deferred part like check yeah sort of passes exactly so like we

we would have um just like a graph like that uh that would be something called IVC incrementally verifiable computations okay let's add two more okay so each dot is a proof and each arrow is that recursion so this proof is a proof of this this is a proof of this this is a proof of this uh so instead of like being a foolproof this is like an accumulation step okay this is also an accumulation step and here if you're done with what you're trying to do with recursion here you actually verify okay and so this is logarithmic this is logarithmic 2 because it's the accumulation step and this will be

linear okay and so what you gain by that is that every time you want to do recursion you only pay your logarithmic cost and then at the end you have a linear cost but usually not we worry about that because you can verify it's natively you don't really need to do recursion on this one yeah so so this like all the checks around the CPU exactly yeah yeah you don't you don't need to like recurs on this yeah cool all right and um yeah so Halo uses um elliptic curves so you also needed to cycle um because you want to do all the I mean as I explained before like you want to do like all the fq

operations natively so actually you will have a two chains okay uh okay and I messed it up because actually what happens is that uh you will so this will be like e Prime this will be e and you will verify it like this yeah something like that okay so like you you switch curve every time you verify um all right so so so this is actually uh what plancky one uh was based on was Halo clock okay exactly so before blanket two there was just plonky

um it uses it used Halo so like the accumulation scheme defined in Halo also the IPA based for a number commitment scheme and the arithmetism arithmetization was very similar to what we have now in plunky two so like also turbo Planck and I think it's also um so Halo is also used by the ECC by Mina and by other teams so it's a really nice system but like we actually found a way to do recursion more efficiently with blocky2 so yeah so so maybe you could talk a little bit about some of the frustrations with uh and like complexities around uh this approach yeah um so I mean the first bad thing that I mentioned already is that the final

verification is linear um so let's say you want to verify it on ethereum that would be an issue like it would be quite costly to verify on the firm or any other at one um another frustration is just accumulation is a really nice idea in the fury uh in practice it's quite annoying to like always have to keep the accumulators um in your system um and then the Halo like in the Halo paper and the usual Halo implementations they also like differ some non-native arithmetic so so even with the accumulation step there's still some non-native arithmetic to do and they um found the technique to defer this non-native arithmetic but

that's one more thing you have to keep track of and in the implementation you you end up with like something very complex um and and yeah you're never you've never fully recursed like you've never fully proved all the proofs Until the End right because until the end you only accumulate right so like this proof is like this one it's basically useless without going all the way up yeah all right so blocky two so 22 um our solution uh to recursion and like to the problems in Halo was to just not use elliptic curves so instead of ellipticals we use something called fry okay so fry is something called a low

degree test that was built by stalker and that's usually used in Starks but you can actually modify fry to get a PCS printable commitment scheme okay that's what we need for Planck and Fry has a lot of benefits compared to elliptic curve based PCS first one is um that you don't have electric curves so so no non-native stuff okay so so we're just doing everything in FP exactly exactly so it proves you're an FB the so like there's only one field so that you could not even like think about

doing anything in another field like fry only uses one field and we do all the arithmetic in this field okay uh so as I explained before like this was the main pain points with um recursion on EC based system so like not having to deal with the native arithmetic is a real benefit uh another one that's very good for performance is we can use any field and in particular small fields so with ellipticals security assumptions you need large fields of at least 256 bits even larger for playing friendly curves so we fry you don't have any elliptic curves so you can use any field that you

want and small fields are in general faster than big fields that's just because our CPUs are doing arithmetic natively in 64-bits yeah so if we want to get really fast we sort of have to pay attention to what's really fast in Hardware exactly yeah and lastly um fry doesn't have a trusted setup and is a first quantum secure okay so no trusted setup that was already the case with Halo but it's not the case with graph 16 or kcg so that's always good to have and post Quantum

secure secure any improving system based on elliptic curves or at least a discrete logarithm is not possibly obscure but fry is so that's a benefit like if you care about this stuff in 50 years when you get a picture exactly 50 will still be there all right so that's why we use fry um then as I mentioned at the beginning we use turboblanc which is which is basically the the main arithmetization that like new proving systems use because it's so powerful um so yeah plus custom Gates very powerful arithmetization much more powerful than r1cs and so since we want to do recursion we want to write the verifier

in the circuit so we need like an automatization that makes it easy to write complex operations like a fry verifier um and that's basically it um okay so let me talk in more details about this small field um so we have a lot of choice we can choose any field um and so um we can take any Prime okay and look at FP and so how do you find P what's the best P well um we found that there's this Prime found by our colleague Hamish

that he named the Goldilocks field or Goldilocks Prime let's say Goldilocks field uh FP okay this Prime is really good okay first benefit of this problem is that it fits in 64-bits so so one element can fit in a word and exactly so that's pretty easy to see the prime P itself fits in 64 bits so like any element smaller than the prime fits also in 64 bits um so that's like one of the main reasons it's so fast uh 64-bit arithmetic is done natively on CPUs

um so that makes computations in this field very fast uh out of the box and that and then the special form of these problems like it's not any random Prime um if you write it in binary for example like it has some a nice structure and the structure makes it easy to do like for example reductions so reductions of 128 bit integer but p is quite cheap okay why do we need to do 128 bit integers mod P well if we have x times y with X and Y 64 bits

then we get a 128 bits integer so like this means that multiplication module B is fast because you multiply them in to 128 bits integer and then you do reduction module p um and then there's some cool features there's like a ton of cool features uh when the like is that ml ad of 32-bits integers uh doesn't overflow so the these two are more for like speed on the hardware side so like making uh operations reproving really

really fast this is more for uh optimization on the constraint side so like in in our programs or statements that we're trying to prove uh we'll do a lot of 32-bit uh arithmetic and so this just allows us to express that with fewer constraints yeah exactly yeah um so yeah if I'm all this x times y plus Z and so like if x y and z are 32-bit integers then you can compute that the result is more than P all right so that's the Golden Ox field that's uh one of the main reason uh funky2 is so fast um so I I think we found that there was

like a 40x Improvement or something from um moving from a 256-bit uh yeah field to go relax I I could be misremember but there's a there's a really substantial uh so who who tried like with a large field uh I think Daniel okay um but like on because no no well no no just in uh in terms of field or like measuring performance of like field operations yeah that makes sense yeah so so not a perfect comparison but you can yeah um

cool and I I guess another nice property is that if you want to do um fpga or GPU implementations of clock E2 it's much easier um with the Goldilocks field because uh yeah it I guess it takes up less space on on the trip yep um should we continue yeah yeah okay so um so let me talk a bit more about the automatization so um there's a lot of flavors of Turbo Planck it's very you can really choose like to do it how you want to like there's like a basic structure but then you can be like creative on how you do custom Gates so we do it this way so first we have constants

so okay let me start from the beginning so we're gonna look at a row of the trace okay so in Planck you have a trace which is basically a table or a matrix um and your constraint works but you're like your gate works on a row of the table so how does a row look in Monkey 2 it starts with a bunch of constants and then we have two types of wire x0 to XV let's say and then y zero y w okay so those are constants um what does it mean to be constants uh

it means that there are parts of the secret description okay it's not part of the witness this uh these constants are committed to in the verifier key so the verifier has access to this information it's part of the secret description um and then you can you can choose how many concerns you want and then these concerns are used in the gate to define the constraints um those are what we call routable wires and those are advice wires okay so this is actually the witness part of the table and we've split it into okay so in

traditional Planck all the wires are routable so you can have copy constraints between any two wires in the table basically enforcing that uh Gates like the kids sort of shared the same value yeah exactly so the wires to to different kits table uh we can say like okay this this one is the same as this one we add a copy constraint okay uh but this is not free uh in the proving system um in plunk there's a something called the permutation arguments to enforce these copy constraints uh and this is I mean this is not for free you have to

pay your cost for that and we realize that we don't need to be able to have copy constraints between any two wires we can just restrict the number of wires that can be used in this permutation argument um and then the wires that cannot be in the copy constraints we call them advice wires and those are used for intermediate computations okay so let me give you like a very simple example uh if you want to compute x to the 16 in a gate the easiest way to do so is maybe like to compute x to the four and and then say that's equal to Y and then compute y to the four okay

so why you don't need y That's like an intermediate computation and so you don't need to Route it and so you would put y in the advice wires but and then you would set your like some other routable wire to yeah yeah exactly so like this one this is the result that you want uh and this would be routable uh but the intermediate computation you don't need it in the permutation argument um all right and so how are those uh constants and wires related uh they need to satisfy appointment constraints okay uh the constraint is that this is

equal to zero p is a polynomial okay and and that's the custom part right so when we say we have custom Gates uh that's P we change p in between every gate uh P could be like defining narithmetic operation or hash function something like that okay and so and so the cool thing is that it's very um you can you can increase the width so you can increase or decrease the width of the table okay um to have like more wires per row and be

being able to do like more um operations and like more arithmetic on every row and you can also increase the degree of P and those those like those two are increases will get you like more expressiveness so this is kind of in contrast to something like r1cs where you have like very like low degree constraints exactly so like r1cs is basically just like quadratic um type constraints uh here we can like be very creative we can um have PB or polynomial a very high degree paranormal so of course it's not for free um if you increase the width if you increase the size of the proof uh and if

you increase the degree you will also uh in some sense increase the size of the proof so it's not for free but you you can play with those two parameters um to get like the size of the circuits that that that's better for you yeah cool um yeah let me just give like uh what we use in uh funky 2 as a default for recursion so we use a 135 um wires so that's the width of the table and the degree of P the maximum degree of P is nine okay so that's pretty uh higher degree compared to something like r1cs as we said which is of degree two and so does using fry allow us to

because that that's a way wider table than than like other uh like implementations does using cry allow us to kind of like have sort of more degrees of freedom with with respect to how we yeah yeah yeah yeah for sure so like uh the first thing I can say about that is that um so usually increasing the width of the table um is pretty expensive in ec-based systems because you have your you have your table and then you need to commit to each column okay and so like you have your each column will become a paranormal commitment so that will be like an

elliptical point and IPA based PCs For example or even kcg so if you have 135 columns you will need 135 points as a commitment uh it's a huge proof to us right so that's a huge proof size it's still smaller than 22 but still but then also the verification becomes expensive because you have to do something called the MSM in the verification of this type of systems and so like this MSM of like 135 curve points will be quite expensive so in plunky 2 we don't need that because um the commitment how do we actually

commit uh to paranormals we can do that in a batched way so like we can commit to uh p 0 to like P and 145 so let's call this like PN and the way we do that is that we have a miracle tree um whose leaf or the evaluations of all these paranormals at like a subgroup element so let me write it and and to be clear these polynomials are interpolated polynomials from each like corresponding to each yeah exactly so that would be like just one root

of miracle so instead of having like uh 135 curve points we just have like 256 bits just like one one root of a Merkel tree so like we already gained a lot um just by using fry that way um of course it's not for free because like when you open this Merkel tree you will have to open like all the columns so like we still get like an increase in proof size but um yeah um and so there's um two parameters in Freud that we can use to like tune the performance of The

Proving system those are called the rate let's call it two to the row so it's often it's a power of two and the number of queries okay let's call it Q so that this is actually my favorite thing about fries this uh because there's this cool space time yeah right yeah so how does that work so so these two parameters are related okay so they're related by the equation um Lambda which is your security um the security of the the fry protocol is actually a row times Q

Plus a constant let's call it G it's um it's using grinding okay so I don't think we'll get into that but basically you can set this guy to like I don't know 16 and uh and then you do some grinding in your protocol which is basically free okay um but so like if we ignore this grinding part then we have like basically a row and QR inversely proportional so like if you increase one you have to decrease the order okay and so what happens if you actually decrease rows for example regular rate decrease the rate okay if you decrease the rate you have to increase the number

of queries okay increase q and what you get by doing that is much faster proofs so faster proving times but sorry larger proofs just because I have to send you if you're the verifier I have to send you all the data to verify each query exactly yeah so like each query is actually like you have to open the miracle Tree by sending local proofs and so you will have just to send like more local proofs Okay and like inversely if you um

increase here the rate and decrease the number of queries you get um slower proofs okay but um smaller proofs Okay so and that's something that's important um for plunky 2 because fry in general give you gives you like very large proofs much larger in general than um then that proving system based on elliptic curves so having this option of like paying the trade-off between uh space and time so like if you have like very

beefy Hardware um to the computer proof you can just increase the rate to get smaller proofs in the end and this I mean to me this is sort of the beauty of plank E2 right because before we didn't have efficient recursion for fry and so you basically had to choose like if you were building a ZK roll-up or something and posting proofs to ethereum you had to choose uh somewhere some point in this spectrum where your proofs couldn't be too big that they wouldn't be able to fit in a block but they couldn't also be too slow or else you'd just get killed on on proving time yeah so so with blocky 2 we can

um for like the expensive part we can make that really really fast because we don't really care about proof size at that point and then we can recurse and like we end up maybe you're going to talk about this but but we end up with um like a really small circuit that's sort of our like recursion threshold and it's cheaper to make that a small proof right yeah yeah yeah yeah yeah exactly so like um the way I presented it like um you you could think that you have to choose do you know one or the other but like actually using recursion as Brandon said you don't have teachers you can do faster proofs when you don't care about the proving size and then once you care for example when you want to push to L1

you just increase the rate use recursion to compress the original proofs and then you you get like a small proof yeah so good yeah good okay so let me give you an example of a custom gate in plunky two I'm going to take one of the simplest gate it's the one we call arithmetic Base gate okay so there is also an arithmetic gate but it works um in the extension field so I will not get

into that but like in clunky 2 we sometimes work in a extension field of the Golden Ox field um so this one is for like base field operations the operations on the Goldilocks field Okay and like the goal of this gate is to do computations like x times y plus Z equals W okay um and we can actually use some constants here So like um C 0 times x number y plus C1 times Z equals W okay that's the kind of operation we want to do um often so like why do we need this constants well it makes things easy for

example if we just want to do like x times y equals w we just set c0 to 1 and C one to zero um so you can see like how having this constants is like helpful to do like basic arithmetic operations Okay so if we go back to our custom Gates design we have the constants those are like easy it's c0 and C1 again then we have routed wires we will have X y

Z and W okay so they all need to be routed there is no intermediate computation here it's like a degree two constraint okay so the constraint is very simple it's w minus C1 X Y minus C 0 x y minus C1 Z okay so that's a degree two polynomial we don't need any intermediate operations like all the wires are rotable okay um and now

what's cool is that we have a white table and here we only use like four wires so it's a bit wasteful so what we've implemented in funky 2 is that we actually stack operations of this kind in a single row Okay so here I will have the first operation and then what happens is that I can also stuck on the side another one of these operations okay uh okay and then I continue so like here I have four wires my uh the number of routed wires that we use

by default in pronky 2 is 80. so I can actually put like 20 such operations in just one row uh which is like very good compared to something like original Planck so in original Planck um there wasn't any custom Gates there was like just one gate which looked a lot like this one okay and so in in original Planck you can do like one operation per row okay and we can do 80. we can do 20. so like it's basically a 20 times Improvement in the length of the trace it's not for free but since we need um such a white table for Poseidon for the the hash functions we use we can use

that also for like arithmetic operation so like arithmetic operations are basically free in plan Q2 very cool so um another optimization uh other optimizations we use to make the this verifier circuit smaller and um is on Merkel trees okay so like the um so like in fry fry basically commits to paranormals using Merkle tree so like and then you do a lot of Merkel proof verification so we need to make that fast to improve plan Q2 we use a bunch of optimizations for that um first one is one we call Miracle caps

okay so Miracle caps uh is um a version of Miracle Roots okay okay so like in the in the usual Merkel tree uh you have the leaves and just do Four Leaves okay and then you have the intermediate layer and then you have the root of the tree okay um and so you get on your run route but then you have to do like two um you have to go up two times in the market proof basically so I can record proof for this guy would be like um okay I'm not gonna perform this guy will be like this one

and then you go up and then this one okay so like your marker proof has two elements um what you can do is instead of giving the root you can just give oh you can just give um this as a root so this is the cap okay and this is the root so the Merkel cap will be larger than the Merkel root it will have two elements instead of one uh you the cap doesn't have to be at the first layer it could be like at any layer below the root um and then if you want to send the broker proof you let's say again for this Leaf

you just send this one okay you just send this element and then let's give them a name okay and then you have like a hash of X and Y you verify that this is equal to this guy okay and so you need to do like some arithmetic to know like which one of these or these uh you need to verify but that's quite easy to do um and what we gain by doing so that is also like kind of a space-time trade-off uh we save on the sides of the local proofs and then this verification here is actually pretty simple it's just like a random access in this list so the cap is a list of

hashes and we just do a random access on these hashes to verify a vocal proof cool um okay um now let me talk about something called Starkey so story so you will find Starkey on our GitHub alongside plunky 2. so story key is the stock equivalent of bronky 2. so Planck 2 is based on Planck but um but you can realize that Starks or more precisely the air

arithmetization okay is um kind of a subset of Planck okay so Planck is basically error plus um copy constraints and the permutation argument and custom Gates okay um and sometimes you don't need either of those okay so sometimes you um you don't need like hiccupcard switch and you don't need custom Gates one such example is for VM okay so in the VM um you have like the state of your VM in a row

uh so like that's the state that's like a row of your Trace okay and then you get the next state which is below it okay and what you want to verify is that the state transition is done correctly okay the VMware transition so so just to unpack this a little bit more because I I think it's a cool Insight like um if you think about what air is it's basically like the same like constraints repeated over and over again and uh each row has access to to like the adjacent row right exactly and so you're basically saying that clock is is basically like a bunch of Errors wired together where you can have Gates uh

that you know impose different constraints and uh you can have wires uh that connect them in arbitrary ways as opposed to just like values and adjacent rows can yeah yeah exactly so actually like in in some version versions of punk um you will not have access to the next state in the constraint um because you don't really need to since you have copy concerns uh but like um in turboplank for example like some people implementing elliptic curve operations in Turbo Planck do actually include the next state in the constraints to like do like incremental computations in Planck so Planck is very lucky you can customize it as much as you want you you can include the next

date or not but yeah if you include the next stage then error is like a subset of blocking um and so to go back to our VM example um so like I have the set I have the next set and then the only constraint I need is that the transition is done correctly okay so this is that um that's like the transition and then I will write a bunch of constraints to encode uh the transition the state transition and then and then you do the transition again and again and again like it never changes okay just just like your CPU it's like the same each cycle does something and yeah yeah exactly so like you don't need

custom Gates because you can just do the same transition on each row okay so that's the reason why um the best way to write VMS uh in a sec circuit is not with Planck but actually with Starks okay um and so that's the reason why we built turkey okay so uh we wanted to write code for a VM we will realize that plonky2 was a bit overkill for that pronky2 is built for recursion so you need to wire and you need a custom Gates we use extensively custom Gates but like plug it was overkill for the VM and so we um built store Key which is basically a Punky two removing all the clunk

specific stuff and it uses the same framework so like the same field same hash functions and so on and it's usually much faster than 20. one of the reason is um these transition constraints so in plonky 2 you have some restrictions on the degree of the constraints you cannot go too low okay most of the time you have to at least have degrees four because right okay but what you can do in W5 I should say in um in stocks is that you can have a degree free

uh constraints of degree free okay and what you get by having small degree concerned that is that you can get a rate of two okay um so as I explained before like having a small rate gives you fast proofs okay and so that's something we use like extensively in Starkey so a rate of two is basically the smallest rate you can have and so like we use the smallest rate possible to have like the fastest proof possible which is something we actually need because like VM computations are quite expensive if you have like a lot of Cycles so you actually really need to have like Fast

prover for VM proofs cool all right so um maybe as a last thing about blanket 2 is like how do we combine all of this together like Starkey plunky 2 and in the zika roll-up context okay so in Ezekiel rollup you have transactions you have a bunch of transactions [Music] Okay so um and you have these transactions and

you want to prove uh the valid execution of all the transactions so this would be like ethereum yeah ethereum transactions um any kind of VM but like for us it would be like uh evm transactions um and so you want to prove that in the execution of this on these transactions uh the first thing you could try is just like patch all these transactions together and have like a big proof that all these transaction transactions are valid okay so in practice you will not have like just four transactions you will have maybe I don't know 100 or uh or more uh and so you'll end up with like a really large circuit uh to do that that wouldn't be practical so that's where you actually use recursion

okay so instead of like proving all the transactions together you batch them okay let's patch them um so actually first thing you would do is actually prove them before batching them so we actually prove them using using star key exactly so like these are VM proofs as I said before VM proofs are very fast using stocks so here we use star key and a low rates okay so like to prove the evm evm transactions for example you will need a lot of cycle and a lot of compute power so like you want to make it as fast as possible and so you use a rate

okay so you have your stocky proofs um and then what you do is you recursively verify them to a new proof okay so this is using recursion and this is using plonky2 okay plonky2 is built for recursion uh it can recursively verify a Starkey proof so here we use star key uh plunky 2 sorry to aggregate to approve okay and now we're compressing like the number of proofs uh final step we aggregate these two proofs okay so this is using plonky two

um and also real rate okay we also want like these proofs to be very fast because like as I said like let's say we have uh 256 uh based transactions then here we would have like 128 proofs to generate okay so we still want it to be fast so that we can parallelize it as well okay and then this last proof we will actually we will also use cronky too for recursion and then we use a high rate okay why do we use a high rate well this proof will be pushed

to L1 okay so here um we have to be careful about the cost of verification like the gas cost if we push to ethereum okay so we want a high rate to make the proof smaller and cheaper to verify um and here at this step we only have like one proof to generate so we can just like have a variable from machine to generate it we don't need to parallelize it um and another cool optimization is that this proof we will not do recursion on it because it will push it to L1 and it will be like natively verified on that one and so we can actually use the hash function inside of Poseidon so

the reason we use Poseidon is for recursion but actually Poseidon is much slower than something like ketchak so we can use ketchup to make provision generation faster and also to make proof verification cheaper on L1 since you have like native catch up codes on ethereum for example cool and and we I guess you you could write that in kzg if you really wanted to go crazy with exactly it's like yeah so like if the verification is still too expensive um on ethereum like it gets too much gas for example and you realize that verifying Grove 16 or pronk and case EG

proof is cheaper you can always recurse on this one using uh graph 16 let's say cool and that's funky too I guess that's funkyo yeah yeah I I think it's cool because it's not um you know we didn't invent a new PCS uh or like an IOP but it I I think um I I was personally like sort of skeptical when when like pocket 2 was being discussed because at that time I think it took like 10 minutes to like the fractal was an implementation for Christopher fry and the proving time was crazy um but I think like the core Insight

um in plunky 2 is like there are so many ways that you can optimize proving systems especially with Thrive because it just opens up like small fields and different hash functions and um and so I I think it's like really like a like a amazing achievement and and applied cryptography engineering which I think is really cool yeah that's I mean that's yeah the beauty of funky too is like how customizable it is and like I guess like you can see it in this last diagram like we have like old steps all the all the steps in recursion we use different parameters to like optimize for what you want in in the given layer yeah yeah and and that I mean we we've seen like really insane uh results for

um using a super low rate for Starkey right like like 150 ketchak um uh hashes per second on like a MacBook Air which I think it took multiple minutes to do one uh ketchup uh hash um and so yeah I think I mean I'm obviously really biased I I I think that your work like oh really opens up the design space for um for for zkp so cool congratulations thank you thanks everyone thank you [Music]