zkStudyClub: PCD without zkSNARK with Pratyush Mishra (UC Berkeley) & Benedikt Bünz (Stanford)

Transcript

uh uh i'm alex um i'm uh hosting the zk study club today um anna is with us but she's um she's out and letting me take take the lead here so we are very lucky and fortunate to have pratyush mishra of university of california berkeley and benedict boone's from stanford university here presenting proof carrying data without succinct arguments so with that i'm going to pass it over to the speakers protrusion benedict thank you very much for being here guys and take it away awesome uh yeah hi everyone uh thanks for having us on yeah so today i'll be presenting a paper proof carrying data without succinct arguments this is joint work with my ex and co-authors

benedict alessandro william and nick benedict will also be presenting in a later part of the talk so this paper is online at this url and the code we have also implement we have an implementation and the code should be online soon as well okay so let's get started so yeah the primary motivation of this kind of work is to construct is to delegate some t-step non-deterministic computation right so let's say you're given some function f and some initial input and uh some final output what you want to do is to be able to check that there exists some intermediate inputs um z1 through zt minus one and some intermediate witnesses w zero

through w t minus one such that um uh f applied to the input at this step and the witness at the step up uh outputs the input for the next step so z i plus one right and this should hold for every time step t right so it's basically just a iterated application of f on z 0. okay so there's multiple ways to do this this perhaps simplest way is a monolithic proof right where i just produce a single proof for the competition which is f applied t times on z zero with w zero through w t minus one as witnesses right and what i check is that f apply t times uh gives z t right so i proved this and i got one small proof

now this is a simple approach but the problem is that you know it requires a large amount of proven memory so it's s times t where s is a space required to compute f and furthermore if you want to now produce a proof for you know additional p plus one step this requires redoing the entire proof from scratch you can't easily reuse most of the computation that you've already done right so to resolve this problem um people have developed this notion of incrementally verifiable computation or ivc um and the idea here is that you incrementally prove the correctness of each uh timestamp so you um at the zeroth time step the ivc prover p sub f it takes in z 0

and w 0 and then produces you know the next step input z1 along with the proof pi 1 which attests that f um applied to z zero and uh w zero gives out uh z one right and then at the next step at the first uh other i guess one step um the ibc prover takes in pi one and z one and uh checks that f is applied correctly but also that pi one is valid so basically at each step you check that the previous uh that the proof for the previous uh step is valid and you check that this steps computation is performed correctly and you can continue this indefinitely until you you know are satisfied okay um this is a useful notion uh it's

also been generalized to uh proof carrying data where you instead of just doing a single line graph you uh can prove the correctness of computations along any dag and this has many applications um particularly to in the blockchain space so one application is succinct blockchains where you know you prove the correctness of the transition function of your blockchain there are applications through constructing snacks which have low space complexity to constructing verifiable delay functions and even to improving the efficiency of byzantine agreement okay so because it seems like a useful primitive but how do we actually construct uh you know ivc or pcd and so far like the best constructions we know uh

you rely on snarks right where this snark is just a succinct non-attractive argument of knowledge so very short proof right so the original approach uh for constructing obviously from snacks relied on snacks with uh succinct verification which means that uh it's at most point logarithmic in the circuit size of the of the you know complexity of f for example this was recently relaxed to just require sublinear verification so even square root n for example could suffice and then building on ideas from halo or bgh19 we propose how to relax this further by constructing ivc from snacks where you don't have subliminal verification but only sublinear

accumulation i'll explain what accumulation is a little bit down the line so the question we want to ask and i wanted to ask in this work is you know it seems that snarks are essential but are they actually required for constructing ivc and in some sense the answer is yes because ivc does imply snacks so if you have a construction of ivc you can construct as i said the low complexity snacks from uh that ivc right but what we want to do is we want to ask whether we can construct ivc from something that's qualitative qualitatively weaker than snarks right maybe just a non-tractive argument of knowledge and any such construction i mean it

would be first of all interesting just because it will be a new kind of construction entirely but it could also have potentially better efficiency properties because you know snacks are still quite technically complex and getting them efficient requires a lot of work right so you could get maybe better efficiency properties um as well as maybe simpler constructions right so maybe you can do it with all the heavy machinery that snacks require right um so i'll let you know there's like a there is a simple a different construction of ivc but it has some limitations so i won't talk about it further here right okay so to summarize our results what we achieve in this paper is um we introduce a new uh cryptographic primitive called the split accumulation scheme

and we show that you can construct ivc from a zero knowledge non-attractive argument of knowledge no no succinctness as long as that uh non-traditional argument of knowledge or narc has a split accumulation scheme right uh and if you have zero knowledge then your ivc scheme also enhances your knowledge so there's a slight asterisk i'll get into multinationals as a little bit later but roughly we move the success from the narc to the accumulation scheme or one component specifically of the accumulation scheme right okay so that's a generic construction of ivc from these knocks with split accumulation but can we actually construct you know these knocks and what we do is we show

that assuming this discrete log and random oracle in the random oracle model there is a zikanak which has a split accumulation scheme for the r1cs relation where the accumulation verifier performs only a constant number of group scalar multiplications field operations and random oracle queries so looking down the line what this means is that the recursive circuit only contains of one you know constant number of all of these operations right and this is in contrast to bcms 20 and also halo where the complexity of all of these operations is logarithmic um where here n is the you know the size of your constraint system so yeah we get a big improvement uh

asymptotically and also as we'll see [Music] in practice uh in our implementation so theorem one uh only applies in a standard model which means that you know you can't have random oracles around anywhere but for theorem two we only know how to actually construct these things in the random oracle model uh i'll explain this in a little bit more detail right after this so i want to clarify that just like you know uh the notion introduced in pcms-20 uh split accumulation schemes have nothing to do with set accumulators uh rather they sort of accumulate the correctness or membership inside a relation in some sense okay uh yes we've implemented and

evaluated this i'll dive into this uh a few more details about this uh soon okay so to summarize our uh theorems right so what we prove is that if i give you a an arc and a split accumulation scheme for that mark then i can construct an ivc scheme um and then applying the theorem in b630 and this allows us to get uh zk snark so this is uh i mean it seems kind of counterintuitive right you start with a weak object like a narc and then you can apply this series of transformations and get out uh a snark right so i mean that person to me that's pretty cool but the problem with this you know i guess this picture is that we don't have to instantiate this in a standard model and theorem one only accepts things in

the standard model so what we have to do is to settle for heuristics [Music] right and so what we have to do is that we construct a you know a trivial a very simple a non-attractive argument of knowledge for r1cs right um and then we construct a split accumulation scheme for that argument of knowledge um in the random oracle model right and then we instantiate the random oracle heuristically uh and obtain uh this accumulation scheme the standard model so you can imagine just replacing your random oracle with poseidon or blake 2s or something right so we can't prove that it acts like a random article but it's probably good enough for our use for practical purposes right and then

now we can apply a theorem one to get um new ivc and pcd constructions of course heuristically but the heuristic is just in the instantiation of the random article everything else is provably secure from discrete logs okay so this is without a zero knowledge and then with zero knowledge it gets a little bit more complicated now both the narc and the accumulation scheme actually are in the random oracle model and then you have to instantiate the random oracle and the cool thing is that the zknark it's actually under under the hood just a sigma protocol right um and then we can apply standard feature mirror uh and then instantiate the random oracle to get out so hang on um just go over again how the

zk case um differs from the non-ck yeah that's a great question maybe i went through that too fast but in the non-zk case um you actually don't require any uh random oracles for the narc it's actually at some level you're sending the r1cs witness we'll see just in a little bit more detail um later on in the talk but there's no random oracle here so the only place around the market appears in the non-leaky construction is in the construction of the accumulation scheme and not in the construction of the narc okay the only place we need to we need to introduce the random oracle for the narc only to achieve zero knowledge um yeah so as we will see here so we

start off with sigma protocol which is your knowledge then we apply feature mirror in the random oracle model to get a a z knack for r1cs and then we have to instantiate the random oracle to get something in the standard model here but if you didn't care about your knowledge then we would just the narc itself would be entirely in the standard model and only the accumulation scheme being the wrong okay okay um okay so does that clarify the uh our contributions on the theoretical front are there any questions so far okay cool right okay so this is you know so it's nice to have like a simple

construction right this is a sigma protocol they're simple to analyze uh but you know sometimes in the quest of simplicity people in construction sacrifice uh efficiency right but what we show is that you know all our construction actually give better efficiency so in more detail we implemented pcd from both atomic aspect accumulation as part of the arc pct library which should these these updates should be available online soon this library already contained an implementation of the bctv approach which is recursion based on pairing friendly snarks like cross 16 right and the nice thing about having all these implemented in one library is that it allows us to compare the cost of pcd across all of these

different paradigms so far right so these paradigms namely being bctv which is cycles of pairing friendly curves which are rare um so you need to as a setup but then you get constant size recursive circuit and at the end constant size proofs as well as um succinct clarification right um the other so the then the other two approaches implemented are the ones based on accumulation so we have uh so-called atomic accumulation i'll explain what that is uh but this requires this is like the approach from halo and expanded on and from bcms20 and this requires cycles of standard curves but they have to be pairing for uh sorry fft friendly so they have to

have higher two added city right but you get nice benefits like transparent setup um uh and now the recursive circuit is slightly larger um and and the proof verification at the end is linear and finally we also have implementation of uh the schemes from this work and now this allows us to use uh cycles of standard curves so you don't have to have any two edicity requirement what this means is that you can use um cycles like the segp cycle so this could be useful for bitcoin applications right so there's a cycle involving sec-p so you can maybe do some recursive composition or regressively proof uh facts about um the sec uh

uh yeah operations over set p right and we still have transparent setup and now the recursive circuit is constant size and in particular it has as few as four scalar multiplications which is tiny and so we implemented this and we compared the cost of all of these uh different schemes and we found that our approach offers you know even lower recursive costs than taking the approach of bcd-14 over grout 16 right so even with pairing friendly circuit specific pre-processing snacks um our approach is as a smaller recursive circuit which a priori you wouldn't think would be the case now of course we pay for this there's no free lunch and you pay for this in terms of larger proof sizes

but there are ways to work around this for depending on your application okay um yeah so i'll cover again more detail about all of these things later on in the talk but guys want to stop and ask before we dive into the technical part of the talk if there's any questions um on any of the stuff i've talked about so far so so the proof sizes um they so you have a constant size recursive circuit and your proof size is linear in the size of the circuit um so technically i suppose your proof size is constant

but you would have to split up your application circuit so that it fit within the recursion um bound to take advantage of that is that right um oh good sorry okay so yeah yeah so basically the idea is that you split up our proof into a small part which is the only thing that goes into the recursive circuit and then a large part which does not go inside the recursive circuit but at the end to verify the proof you you need both of these components like the final proof um outside the circuit you when you want to verify the ivc proof you do need to have both of these components um yeah and that's basically how we work around

by like we don't put the linear portion inside the recursive circuit and that's how we get this constant size recursion how feasible would it be to do a proof at the end which was basically verifying the linear time part of the verification so it's it should be doing that using a succinct proof system it should be entirely possible in particular like so for example with the application to uh the amina application right when you have fixing blockchain at the end uh for the light client you want to send a small proof right for the state so far and then

you could you could for the for the final computation of the decider as we will see it's actually just checking a sort of multi-scale multiplication uh at a high level and that portion you can uh you should be able to do just um as part of a decider as part of like a inner product argument for example um okay and and yeah i think it might require a little bit more work um but it should be possible i mean so the i mean you have to kind of there's multiple roles even in pcb where um you definitely need the entire proof for the entire state in order to repeat like pcd or ivc

says one key property is that you're able to continue the computation right that like given a proof you're able to continue the computation and for that you need to see the entire proof but that's you know even if you use bctv right like if you use uh the cross 16 bc tv right you oftentimes are like the sorry the the succinct blockchains you need to know the provers they need to know the internal state of the blockchain anyway right there's uh you know some some state some account state and they need to know that in order to do something useful with it um and so in order to continue the computation to add a block say or to add a computation to that yes

you do need to know the proof if you just care about verifying it then you could outsource this decider uh using some other proof system um say like as patrice was saying you can do an inner product argument and to to make this like practically very efficient but you so suppose you you end up with a succinct proof then you can use that to bootstrap another instance of your scheme um so you wouldn't need the state from your scheme you're periodically you're compressing that state um that way right but then i think you would run into some so then at some

point you have a logarithmic size recursion circuit for example if you use you know the halo approach at some point you would have a logarithmic size recursive circuit somewhere in the middle which maybe it's fine like you just do it one time and then you continue the the proof strap using this constant size recursive circuit thereafter yeah it would only give you a constant factor improvement i guess depending on how many of those intermediate compressions you need right okay okay oh yeah thanks for the question um okay uh there are no other questions and i'll hop into the technical portion uh we'll start off with you know what the recent advances in ivc and pcd have been and namely i'll talk about how we've been constructing recursive

composition using atomic accumulation schemes so okay before we dive in what is ivc formally right so there's two parties approver and a verifier the prover it takes in the previous or the current state input and our corresponding witness and uh proof pi for the uh that attests to the correctness of the computation thus far and then it produces a new proof pi prime which ensures that f applied to z comma w results in z prime right um so yeah so this is what the prover does it produces a new proof which attests to the correctness of all the previous computation as well as the correctness of the current step and then the ivc verifier it takes um

uh it takes in the the final proof pi along with uh the initial input z and maybe the final output z zt and decides whether or not the proof is valid that you know it corresponds to a correct history of computation um and yeah so the idea with obviously that you can continue propagating this computation um over time so you can feed in z prime again into the prover and pi prime again to the prover along with the new w prime and then continue produce a new proof pi double prime and so on um right so properties we want our completeness which means that basically you can keep extending the chain so if the current proof is valid

then an honest prover can extend then can take that valid proof and then produce prove the correctness of the next step in the computation right um and for proof of knowledge um what we want is that uh if the verifier accepts a given input comma proof pair then we can extract from the from that from that adversary uh complete transcript of the computation so far so basically all the intermediate state we can extract it and it'll be it'll correspond to a valid uh sequence of our of computation steps okay um yeah the efficiency property we want is that the proof size should not

grow with the number of computation steps um right so this means that uh yeah it should be equal across the invocations of the approver all right okay so so that's ivc uh now we'll talk about the other key component of our of uh the stock which is a snack or in particular right so stocks are defined for for for particular relations in this uh i guess part of this talk will focus on uh the arithmetic circuit satisfiability relation and the idea here is that there is some indexer which takes in some public parameters and pre-processes them to be circuit-specific and it produces a

proving key and a verification key um the approver the approver gets the proven key and the verify gets the verification key and the approver can get can then take pk along with a public input x and a witness w and produce a proof um that you know x comma w satisfies c and the verify verify can take vk x and then pi and check if pi is actually a valid proof that there exists some w such that um c of x comma w is one so properties we want our completeness and adaptive proof of knowledge completeness just says that you know if i do have uh actual x comma w

such that uh it satisfies a circuit then i can produce a proof and proof of knowledge just says that i can you know if i accept the proof then there must be some underlying witness that i can extract optionally you might want sublinear proofs and sublinear verification which means that the proof size is much smaller than the size of the circuit and the verification time is much smaller than the time to compute c right and also zero knowledge which just means that the proof reveals no information about w except for the fact that um the circuit is satisfied okay so this is a whirlwind overview of ivc and arcs so let's see now how we can construct ivc from succinct nox or snarks right [Music]

so the construction is very simple so the ibc prover first invokes f to on the input zt uh to produce the next step output zt plus one and then it uh constructs a recursive circuit which contains f as well as a copy of the snark verifier v right um so this recursive circuit it checks that f was applied correctly namely that you know f of zt equals zt plus one and that the snark verifier accepted the previous step proof pi t right so checks these two computations and then the ivc prover it invokes the snark prover on this recursive circuit r to produce the next step proof pi t plus

one right so at a high level all that's not although although ibc prover does is that it uh constructs a snark proof which attests to the fact that the previous step competition uh the previous proof is valid and that this step computation is correct right okay the ivc verified then adjust invokes um it takes the final proof and the initial and final um outputs and checks that uh the corresponding proof is valid that pi t is valid it just invokes a stock verifier on that the properties you want are completeness right so completeness follows from this uh the completeness of the snark and soundness uh or proof of knowledge

rather it the basic ideas to you recursively extract the transcript using the snark knowledge soundness so you know step by step i go backwards in time extracting witnesses right and i can only do this like uh there's like some caveats i'm doing this and in particular you require the snack for pcd at least you require the snack to have a very strong um knowledge property um which i won't go into more detail here but you can see the paper for information about that okay okay so this construction is very simple but there's two caveats first of all it doesn't hold in the random oracle model due to non-black box use of the snark verifier right because you can't have oracles in your circuit right

and the efficiency is that you know so pi is just the size of the stock proof um and this it places restrictions on the kinds of snarks that we can use right so what is uh yeah what we need is because we're proving statements about the stock verifier then you know when the stock verify you express it as a circuit it must be sublinear in the size of r so a verifier for r must be sublinear in the size of r right so this means that you necessarily need to have sublinear verification for your snark which limits the kinds of snarks that we can use okay can you just go into a bit more detail about that um does not hold in random oracle model oh right because uh basically

you are instantiating the snark verifier right as the circuit and you're putting it inside this r so at that point there's no oracles anywhere right so you you can't have um oh yeah of course it's obvious right yeah um um right so yeah was i okay so yeah so we need to have this you know so what about snarks without sub-linear verification so this is where um halo and our pcms20 comes in and the idea here is to use this new primitive called an accumulation scheme in this paper we to differentiate it from stupid accumulation schemes we call

these atomic accumulation schemes um right so the idea here is that you have some sequence of queries q1 through qt right and uh what you want to check is that uh there is a for some predicate phi phi is satisfied on all of these queries q1 through qt right um so this file can be you know a variety of useful things it can be for example your snark verifier can be your pc uh evaluation proof checking algorithm uh and so on there's like probably a bunch of useful primitive predicates that you could have right now basically what you want to do is you want to check that um across time that you know the

sequence of queries satisfies the predicate at each time step right this is what you want to check and then an atomic accumulation scheme is a way to do that so uh the key object in this accumulation scheme is uh called an accumulator this is not a set accumulator just as a reminder just think of it as an opaque object for the time being right and then there's an algorithm called an accumulation prover which takes in an initial accumulator and a query for this time step and spits out a new cumulator which is which sort of accumulates both a0 and q1 and the idea is that you can continue this you know over all t time steps incrementally accumulating the

accumulators between steps right so at time step one then p will accumulate q two and a one and so on and so forth until at the end it'll you'll accumulate a t minus one and q t to get uh the final accommodator a t right okay so this is the accumulation prover there's two more algorithms the first is an accumulation verifier which checks that the accumulation at each step is performed correctly it just performs some cheap checks which to make sure that a1 is the correct accumulation of a0 and q1 right and you do this at every step again um checking that you know each new accumulator is a valid accumulation of q2

of the input at that step and the accumulator from the previous time right okay so let's say you've done this across t times steps at the end you have a decider algorithm which takes the final accumulator and checks that it's valid it doesn't take any of the past state it only gets the final accumulator and decides whether or not it is valid right and the property that we want is that you know if all of the verifiers that each step accept and the final decider accepts that it must be the case that the predicate would have accepted the conjunction of the predicate on all the inputs would that be true um right and okay so you might think

this is not particularly interesting but the key insight here is that the size of the accumulation verifier it must be much less of the cost of the accumulation verifier must be much less than the cost of the predicate fine so checking that the accumulation happened correctly is much cheaper than computing the predicate yourself and furthermore this accumulator does not grow with t right so which is why the decider is basically equal to the size of phi it's a roughly and it does not grow with the cost of uh or the depth of the number of things you've accumulated okay so any questions about this atomic

accumulation scheme this is sort of the um people thing that people might not be most familiar with at a high level the idea is that instead of checking the predicate at each step i basically keep accumulating the queries and performing some cheap checks on the accumulation and then at the end once i have the final accumulator i perform an expensive check which is equal to the cost of or roughly equal to the cost of the predicate and the savings are basically that you know t times the cost of v is much less a t times the cost of v plus t is much less than t times phi that's that's the efficiency gain that you that you make okay so there are no questions i'll go

on and we can see how we can construct ivc from atomic accumulation so note that this and this slide they're both uh part of the prior work pcms20 so yeah not part of this paper and and implicit in halo yes and uh yeah based off of the ideas in hilo yeah um right okay so so how do we do this how do we get this ivc construction so yeah there's two components a snark p comma v so the slack algorithms i'll denote in blue and the accumulation scheme algorithms and they'll be in this burnt orange or whatever okay so we have this knock and we have

an accumulation scheme p com pvd for for the predicate which is the snark verifier right so the predicate that we're accumulating is the stock verifier okay so now what the ivc prover does is it takes an ivc proof and for the previous step along with the input for this step now the ivc proof consists of a snug proof as well as um an accumulator right and so we want to get out you know the next input and the next ivc proof and we do that as follows we obviously first invoke f to compute z i plus one and then we invoke the ivc prover or sorry the accumulation prover which accumulates ai and the new input pi i along with zi and

produces a new accumulator ai plus one um you know just accumulation of pi i and ai right okay so this is how we get ai plus one and then to get out pi i plus one we construct a recursive circuit which contains inside it uh not the snark verifier but rather the accumulation verifier this bold v right and what this accumulation verify checks is that the accumulation at this step was performed correctly so it checks that ai plus one is the correct accumulation of pi i and ai right and uh so we have this recursive circuit which computes f and the accumulation verifier and then we invoke the stock prover on this recursive circuit

and get out our new proof pi i plus one which you know together with the ai plus one gives us our ivc proof for the next step right so the key thing to note here is that there is no snark verifier inside the recursive circuit only the accumulation verifier right so now what we've changed is that instead of having the snark verify we stop linear we need the accumulation verifier to be sublinear okay so that's the ibc approver the ibc verifier it just basically invokes uh the decider on the final accumulator and the snark verifier for the recursive circuit okay so as i said the recursive circuit no longer contains a snark verifier

which allows us to get rid of the succinctness requirement for this knock okay so completeness follows from the completeness of the snack and the accumulation scheme straightforwardly and soundness you still require the strong knowledge property on the stock because we still extract recursively from the snack proof but we only require a weaker soundness property on the accumulation scheme so we don't need to have any knowledge assumptions about the uh yeah about the accumulation scheme okay so that's the state of the art in terms of constructing um ivc construction so far right so we have ivc from snarks

recursive stocks and ivc from accumulation um okay so i guess before we dive in there so yeah so i was saying the cumulation verify must be sublinear which means that these proofs uh the ibc proof and in particular the snark and the accumulator must both be sublinear right yeah so this is a state-of-the-art um ivc from stocks and i received from snarks with accumulation atomic accumulation and what we do with this in this work is we introduce a new tool called split accumulation and we use that to make ivc cheaper so for i guess the next few slides it'll be benedict taking over so i'll stop sharing and benedict i guess can talk about those portions okay thank you let me see where there

um okay great you guys all see my screen and earlier before i get going uh maybe are there any questions to uh what produce just uh discussed regarding atomic accumulation before we dive into split accumulation oh right yeah definitely because split our work after this builds on the ibc construction so if they need any questions here the best to clarify them now by the way if anyone has questions feel free to type them in the chat too and i

can verbalize them okay it's it's worth noting by the way that in practice um you need to instantiate this using cycles of curves um and that makes things a little bit more complicated because you're you're basically alternating between two curves um at each step so right and in practice it seems like you would you better accumulate as one for each curve yes exactly um good point okay so i'll go on and talk about uh split accumulation now and uh in essence what we'll be able to do

is right is kind of the last point that producer made is that the accumulation verify must be sublinear so both the proof and the accumulator must actually be short they must not be efficiently verifiable or the the the like the accumulator must not be efficiently decidable and the proof must not be efficiently it does not need to be efficiently uh verifiable but these things need to be small and what we do now is we show how we can actually get rid of this requirement and this opens up you know sort of the whole idea of this this line of work that that started with halo is kind of you know you you you relax the requirement of the tools that you need

and then in the end you get kind of much better and much easier ivc pcd from it so we're really like trying to relax what we need to get out you know the super powerful thing in the end which is ibc uh pcd so what is split accumulation and in particular split accumulation for relations so now let's consider we are always talking about these these predicates and now let's consider that we have a relation and for this relation we have an input q and this input can be split into a small instance and then a large witness and the relation

accepts if there uh exists a witness for uh an input so we have an an exists relation here and let's say we have a bunch of these and then we want to design an accumulation system saying that all of these uh output one right so that for all i they exist these witnesses they exist these qws and again think of the witnesses as being large and the instances of being short and but yeah we want that all of them are equal to one evaluation and what we're going to do now is we're going to build an accumulator

for this uh accumulation for these relations so what we'll do is you know it looks very similar as as before we have approver and the prover gets it in as input both the instance and the witness and outputs the proof uh proof one and then um in fact what we'll do is we'll also split the accumulator so this is kind of we're doing two things at once we're splitting the the um the the relation input into an instance and a witness but we can do kind of you know the similar thing to the accumulator where we say the accumulator really consists of an instance this is witness and now the difference

is that the accumulation verifier here again denoted by a small box because it needs to be very efficient it only needs to receive his input the accumulation instance the query instance and then the the proof that is created by the program so the prover has access to everything it has let to a large accumulator um and the the relation the witness here but the verifier only has uh access to these the the black things which are very small and the the whole scheme is is you know it looks uh

it's still an accumulation scheme so we still have this idea that we go from one accumulator and um uh query here to a new accumulator so we accumulate you know this old accumulator and then this input to the relation into a new accumulator and at the end there exists a decider and the decider gets to read the accumulator so the decider decides uh in the end and it gets to read the entire argument and the property that we want for the accumulation scheme is that if the decider accepts and all of the intermediate verifier the accumulation verifier

accepts well then this implies that uh computationally it implies that uh all of uh this this this statement here below holds so that all of the relations are uh evaluate one okay so uh the the the key difference here right is that we just simply this is why we call it split accumulation because we simply split our predicate and we split our accumulator into a short part and a large part and then the verifier only needs to access the short parts so the um and still you know what should hold is similar properties as

as before with uh accumulation we want that the cost of the verifier is much cheaper than the cost of the relation and that the accumulator the entire accumulator does not grow with the number of accumulations so now we've you know this is a this is a more general accumulation scheme right you can it's easy to see that that atomic accumulation is just a sub-category of this in spa and in particular the one where the witnesses are empty but it turns out that even from this more general accumulation we can still construct ivc so how does that work so now let's assume one second um if you're if you're writing on the

slides and i don't think we can see it ah okay but you can see my pointer right yes yeah i'm just doing pointer um but [Music] now let's consider let's say if i'm a v is a uh let p comma v now be a narc so what is an arc well it's a non-interactive argument of knowledge so it's similar to the snark but we completely drop the succinctness requirement so there's no requirement anymore that the proof is short or efficiently verifiable and of course any snark is also an arc but it's not a requirement anymore and then we have our

split accumulation scheme and the for what relation in particular well the relation says that we take this input some some public input for this for the knight the accumulation instance and then also the proof instance and the proof witness so what we do is we take the narc the narc has a proof and this proof may be long so what we should be able to do is we should be able to split the proof into a short part here and then a long part pi w and that the the relation that we are trying to accumulate

is just simply the narc verifier so uh where the narc verifier gets his input the accumulation instance and then z and also the entire proof okay so yeah we need to split so the way that we now construct ivc from this is that um we have our ibc booth iii and then um we put this into the you know we create uh we have our narc proverb and now what is the recirc what is the recursive circuit that the narc prover implements

well it simply implements the accumulation verifier right it it again does does this is similar to how we constructed ivc from atomic accumulation where oh sorry my screen see you next time you guys uh you guys didn't do anything anymore right oh my i can't see anything i think my powerpoint just crashed give me one second no problem um does anyone have any questions at this point if so uh perfect time to

ask every time exactly okay um how do i start again show your screen [Music] okay but i think i mainly also lost my uh ipad but um okay so any questions you guys see my screen again right yeah we can see it so so in practice um how small can these small parts of the explanation be

um well so so both in theory and in practice right like in in practice we want the small part of the accumulator to be as small as possible why because the accumulation verifier needs to read it so it like it's a lower bound on how large the accumulation verifies in theory what is sort of the smallest um you know possible size that still allows us to construct i mean see well it's just basically anything that is sublinear right any any uh as long as the accumulation instance and the the proof you know if we can sort of split off

the as a part that is sub-linear in the um in the size of the circuit that the narc verifier is checking well then we are able to construct ivc from it it just leads to a much larger recursion threshold right this is similar to we can actually construct ivc from this is what caused the cos20 showed is that we can construct ivc from any snark that is sublinear and here now basically the only question is whether the accumulation verifier is sublinear in the size of the relation that it's proving does that make sense so what i was

trying to get at is for your concrete scheme that that's in the paper um oh it's like four group elements four group elements okay i think cool i think we have a powerful obviously it's like four but like uh not for well we'll see in a second we're constructing you know uh um four group elements you know like for we're constructing accumulation directly for r1cs and for that you need uh i think it's you have four group elements might even be three well we can see in a second we can count so so it's comparable to the size of a gross 16 uh cross 16 proof right but there's no you know cycles of yeah there's no pairings yeah

it's also even stronger because it's not one everything is just in the 255 bit group so there's no g2 anywhere yeah 1024 bits okay thanks and okay so uh now we want to construct ivc from it and what we do is we simply create a recursive circuit or we we create the the narc prover proves that the accumulation verifier was correctly and then uh this creates uh you know this creates a new proof which you then again feed into the narc prover and this is the same kind of recursive construction and then in the end the deciders the the ivc verifier simply runs the

decider and uh runs the um uh the verifier and i'm sorry this was the so this is the this is the old accumulation construction and what we need to be careful here with is that of course you know we split up at every point here we want to split up our proof into the large part and the small part such that the accumulation verifier does not need to read the entire proof right it only needs to read the short part of the proof and this is what allows us to use an arc instead of a snark so what do we need in order to prove soundness of this construction

well in order to prove soundness we require that the narc itself is extractable right because in the end you know you have this this only this one narc verifier which verifies the final proof and what we want to do from this is we want to extract all of the previous proofs that were constructed and additionally we need that our accumulation scheme also now this is a new property that we didn't have before we needed to be extractable as well so we need that even though the accumulation verifier only reads the short part of the accumulator um we now need that you know we can

extract the accumulation witness um from whenever you know we have an an adversary that can convince a decider and uh an accumulation verifier so from these strong soundness properties for both the narc and the accumulation scheme we can prove soundness for the entire ivc construction and and then the efficiency importantly is is roughly the size of this recursive circuit or it is dominated or yeah it's dominated by the size of the recursive circuit and but importantly right as i've already

mentioned it's independent of the size of the proof witness so this can be really as large as we want it to be and the um accumulator accumulation witness and then so how how difficult is it to get this extra um knowledge property um it's not i mean it really depends on the construction i mean i think that sort of any atomic accumulation scheme like uh uh already like it had it trivially has this knowledge property right

because there's no knowledge right like there's nothing you know that i need to extract basically there's just say soundness you know there we just say yes the the uh you know this is this was kind of the implication that i showed on the first slide and and now they there are these hidden parts that we need to say right it's in there exists witnesses so we need to somehow extract these witnesses um that's kind of sad okay and then how do we do it in practice for our schemes well this is where fiat chamier and the the random oracle heuristic comes in so under the hood these are interactive protocols which we know how to or we yeah basically we show actually that they

have the knowledge property in the random oracle prop in the random oracle model and then the problem is that we need to instantiate them in the standard model so this is where heuristic comes in but we show that they have exactly the knowledge property that is required in the random oracle model so we proved this formally so we say that we can construct ivc pcd from a split accumulation scheme and in particular what this means is that if we have a narc and then we have a split accumulation scheme for this narc verifier then we get ivc pcd and the cool thing again there's no sub linearity that is required

v itself so the accumulation verified this is really what we care about like when you design one of these things what you care about is the size or is the the the efficiency of the accumulation verifier and this must be sublinear and we'll see we're highly efficient on that and then i said the narc and the accumulation scheme must have strong knowledge properties and we also prove that a lot of properties are kind of transfer over so for example if you want your pcd to be zero knowledge well then you need to actually require that both the narc and the accumulation scheme are zero knowledge and we also say that we also show that

if they are post quantum secure then so is the pcd the particular scheme that i'll show is actually not post quantum secure but you know if you had a narc and an accumulation scheme that is where quantum secure you would get a quantum secure pcd and uh yeah so we make non-blackbook use of the verifier so again you know the standard uh kind of heuristics that you need to do uh we also need to apply here so because this does not hold in the random article so has there been any work on seeing how to apply fry based polynomial commitments to this yeah i mean i think you know the the

recent uh we we also have an accumulation scheme for uh so the yes there has been some work but i don't know exactly uh what the state is i mean i think in general you know there was this uh there was a recent we have a we have also in this paper some in the split accumulation scheme for kind of a uh a polynomial commitment scheme that just needs additive homomorphism and there was a very similar result by uh um it's called halo infinite was i think the name of the paper and they show that you know it even suffices if your

polynomial commitment scheme is not linear so it doesn't have additive homomorphism but there's kind of this what do they call it like like a homomorphism check protocol so as long as you apply this homomorphism check protocol then you can uh do the the accumulation and they also show this for that something like this exac this for fry so that would be the place to look okay um but i want to show you something you know now even if anything before was i don't know maybe two too uh sort of too theoretical or too in in on on the formal side then i

beg you to now pay attention again because i'll present a split accumulation scheme for r1cs and it's going to be extremely simple and i hope that your takeaway is wow this is really simple but what you have to remember is that all of the machinery that we talked about before and that we built allows us to take this extremely simple protocol and then construct something as powerful as ivc and pcd from it and in particular i'll show you the special case for ivc but we can also do this for pcd so what we'll do is we'll design the split accumulation scheme for r1cs so to recall what is r1cs or rank 1 constraint systems

so what we have is three different matrices a b and c and a vector x over a field and this defines an instance or abc defines kind of the circuit and x defines the public input to the circuit and this is the probably the most common language that is used to describe arithmetic circuits both in in theory and also in a lot of practical implementations they use exactly this this r1cs and what we need to show to to show that the circuit is satisfied you need to show that there exists a secret vector w such that for the concatenation of x and

w a z hat a mark product bz equals cz so this is the element wise or hadamard product and as i already said is you can you can take an arithmetic circuit and very easily there's a pretty straightforward transformation to construct these matrices a b and c from it and then the public inputs can be uh transf become the the vector x so uh yeah it gives you a really good balance between structure and x uh between structure and expressivity and x is really important because it defines

the the public inputs but for simplicity we will simply we will ignore it in the future but just be you know be aware that that we can uh actually make this uh work even if we don't ignore x so uh any questions regarding r1cs or is everybody familiar with it here okay so right we all we want to show is this this this element wise product uh a z cert bz is equal to cd and um what we can do is now i want to present to you a non-interactive proof of knowledge for r1cs and the non-detective proof of knowledge it's you know

years of research have gone into it uh how how do you construct it well the proverb just simply sends z to the verifier this is a non-interactive proof of knowledge for r1cs right because what can the verifier do the verifier just says that well it just simply checks whether a z times bz is equal to cz right this is a completely trivial protocol um but it is a non-interactive proof of knowledge right it's a it's a proof that the prover in fact knows z because he sent and it is non-attractive because there's only one message there's no succinctness of course and we'll actually do

use something a tiny bit more complicated but all that we'll do is we'll commit to azbz and cz so we'll use a vector commitment like a paterson commitment and commit to ca cb and cz and then the verifier additionally checks that these commitments are correct and why do we use these commitments well they will allow us to accumulate proofs right these are these are linearly homomorphic commitments right so if i add them um i have some linear right so for example if i added c a plus c b i would get a commitment to a z plus b z and and

uh this will allow us to accumulate proofs so this is the the the trivial non-interactive proof of knowledge or narc right uh there's no the the uh the the a in ark just says that uh there's there could be computational assumptions here there's not even a computational assumption so really it's it's a non-interactive proof of knowledge but this is going to be the basis for our accumulation scheme and in particular we want to accumulate now this narc verifier so we want to accumulate these checks on the right side and build an accumulation scheme for it so here is the the kind of the first attempt right and here we have on the right we have the the narc verify

so let's say our uh right we have our proof um and our proof consists of these commitments and the witness and the way that we split up the proof here now you can see it very nicely that there's a short part to the proof name these commitments these are just three group elements and then there's a large part of the proof um which is the uh which is z the the actual witness to the relation that we're trying to prove okay so uh again here's the verifier and now we like our first attempt is to construct an accumulator and let's

assume that the accumulator does exactly kind of has the same form as the proof so again we can split it into these commitments here and then an accumulator witness which we'll call y and then the decider will kind of mirror exactly what the accumulation verifier does okay so it checks that a y circuit b y is equal to c y and then the commitments are that the commitments are all correct so now we're going to try to accumulate basically these two things so what we want to do is we want to take these two things and ideally at the end we have a new accumulator a prime

which has the same form as a and um yeah and we'll have a simple protocol for accumulating it so uh what is the the you know the first attempt to do this is we simply take a linear combination right everything in this proof and in the accumulator is linear right these are group elements um so we can there's a linear operation defined on them and it's a vector of field elements so there's also a linear operation defined on them so what if we just take a random linear combination so here we have a challenge beta this will be generated through a random oracle or

if you want to think of it interactively by the accumulation verifier but in the end uh yeah we have have this random challenge beta and then we just take this linear combination between the accumulator and uh the proof and uh so now what is uh so what does like now let's look at um kind of what we get out of this so let's look at each of the commitments so c a and c a prime right m is just placeholder for a b and c so we take c a plus let me actually get a pen here um okay so we take c a plus beta c c or c a prime plus beta c a

and now we evaluate what this is well this is a times y plus beta y and this is exactly equal to a plus well you know this is uh the right we take the linear combination between uh y plus beta z right so this is exactly what we get here so this here is equal to [Music] y okay now i'm writing with my mousepad which doesn't work very well but uh actually let's go theta z um okay i'll stop doing that

um so you so uh it's it's easy to see that this work exactly works out right you know the our the commitments in accumulator prime are exactly what we need to be uh what they need to be for c a c b or ca primes here uh yeah or the yeah for cacv and cc okay so this kind of linear check we successfully accumulated and then there's this other property right which the verify and the decider check namely that a y plus uh or that a times you know our

accumulation witness circ b our accumulation witness is supposed to be equal to c times our accumulation witness so let's expand on what a times our accumulation witness is well our accumulation witness again y plus beta z so we get a y plus um beta times uh so sorry we get a y circ b y plus beta times a y circ uh b z plus um b squared right this is you know this is actually like the first two terms

are the ones that we really care about right a y circ b y which is exactly the same check that we had done in uh for the proof so by the narc verify and then we have beta squared times a z circ bz and then we have two cross terms here right yeah there a question okay right so we have uh you know kind of the the checks that we care about here are the first check and then with the beta squared uh coefficient we have uh uh the check that was done by the decider sorry by the verifier and this is done by the decider and then we have a couple of cross terms here so this is exactly you know if we look at

our matrix here right this is c y plus beta squared times cz plus beta times junk but unfortunately this isn't quite exactly what we got from the accumulation right so what we got from the accumulation was c times a prime witness which is c times y plus beta c times z so we're almost there right we would have liked the beta squared term here and then we have also this junk term here so uh this didn't quite work but you know we're almost there and not too far off so any questions regarding this or i guess we'll you want to see the solution yes please

and so the solution is that in the accumulator we actually need an additional element so we'll have our commitments to z a z b z c and then we need this additional commitment to the hadamard product okay so this is this rc circ or cl and so how does it work now so now the in the the decider so the verified still does exactly the same thing and then the uh decider still checks that c a prime c b prime and c c prime are the correct commitments to a y b y and c y but now we have this additional

commitment so this is not the accumulator now is not an r1cs instance in fact right we we just have this uh additional commitment which says that okay this should be a commitment to a y circ by right there's no requirement now anymore that for y uh that y is an r1cs instance so that a y cert b y is equal to c y but as it will turn out this is actually enough so how does our accumulation scheme work now well we still get our challenge beta but we'll have this additional element c proof c pi and c pi

will if you look back at the protocol before where we're not too far off c pi will exactly commit to all of these junk terms right the cross terms before and we can commit to them before knowing beta right these are fully determined before knowing beta we just don't know the beta term so we can commit to junk before knowing beta and this is exactly what we'll do so we'll create this element c pi which is the commitment to these cross terms and then exactly junk so then what we'll get is that our accumulator

is equal to a prime x and we still take exactly the same linear combinations between a prime and beta c a and b prime and beta c b and c prime and so on and for the witness we also take exactly the same linear combination but now we also have the c o prime element which will be uh the in fact exactly what it what we need it to be so it will be a times y prime sir b times y prime and what the verifier can now check is that c o prime is equal to co so the old accumulation uh the old

accumulator element plus beta squared times c c so this comes from the proof plus beta times the juncture so what the verifier checks is is you know that let's go back to the previous slide so it checks that you know exactly this relationship here this uh in the middle um so let me get my laser so that this thing here holds right so and it can do that over the commitments because we committed to everything beforehand right everything that that it needs to know is committed to beforehand namely co cc and then our proof

so this c pi becomes the accumulation proof um so are there any any questions regarding this program i need to stare off it for a bit okay um what i want to say is okay what we can do is right so we we we um so what does the accumulation verifier need to do well the accumulation verifier needs to compute a prime x which are these three steps and it also needs to compute co prime which uh for which it simply does this performs this check

so we can count the number of exponentiations that the accumulation verifier needs to do and so we have one here uh one here one here so two three uh four five and so it needs to do five uh scalar multiplications in this group in order to perform this there's an optimization where you can actually combine c a and c b into a single commitment and uh then you get from four to from five to four so you can actually even reduce it further you just take uh in the c o prime check you can just take beta common for the last two terms

um you take beta sagan you just take beta common for the last two terms and you've already computed beta c c right so then you just it's like even three i think scalar multiplications okay all the options we've even just got it down to three scalar multiplications and you know we can we can you know maybe even uh um you know use smaller challenges to optimize things and there's a bunch of tricks but you know in in in any case you have to really do it's it's it's uh what the accumulation verifier does is extremely trivial work and this is important again leading back to kind of the first part of the talk because all we put into the recursive

circuit is these this accumulation verify yeah so so these um challenges can be short is there a um a tight security proof um that tells you how short they can be and there there's a i mean well part of the security proof is heuristic because we have to but i i i don't want to say anything wrong i i uh um i do believe that it's possible to extract a fairly tight security proof um yeah because i know i know there's a recent proof of bulletproofs that was tight um

much tighter than i expected it would be um so you can maybe apply the same techniques um [Music] yeah to be honest i don't want to say anything wrong so so we haven't put a particular focus on making giving of tight security proof um but uh um yeah yeah so that that's what you would need to minimize the um the size of the challenges that is true yes and so uh so uh wait are there any sir i keep skipping ahead any more questions regarding this protocol so so i wonder by the way sorry for the

noise before uh phone uh bugs uh i i wonder uh this question may not make total sense because i uh if there's some sort of threshold where right this is this is super simple uh and right for a i guess for a really small r1cs uh this would be better than no maybe the verifier would be more for proverbially more efficient than kraut 16 or another uh is there like some approximate threshold where if the r1cs is small enough and i'm doing recursive proofs on this small r1cs then it's better to use this than uh you know the other stuff

and like the snarks the thing is that right like the key difference to say something like ross 16 and so on is that it it doesn't at all require ffts uh all right there's no no not a single fft inside um i i would i would assume that like to me it looks like it's it's always more efficient than gross 16 like or that at least the efficiency is kind of independent of the size in comparison to graph 16 and i mean what you get with uh but of course you know i mean do i believe that you could maybe do better or probably do better with the trusted setup

i mean yeah of course a trusted setup is always easier you know it's um but here we don't need a trusted setup we don't need ffts and and we get something pretty powerful so um oh yeah i'm saying i'm saying maybe for a small all right for small r1cs this would be yeah this would be saying this is nothing oh i don't think it has anything to do with small arch if like well small maybe if you right if you take you're saying prover it might be always better uh yeah i guess i guess so in terms of verifier then the question is uh well okay so so um i mean the narc itself is not very efficient because you need to send the entire right you need to send z

itself right so this is not an efficient like this is not a snark right it's it's just uh it's just an arc but the powerful thing is that this still suffices to construct um ivc from it and um yeah so yeah that's what i'm saying right if i understand if i followed correctly maybe right if you're doing ivc with this recursion with this the the verifier the communication complexity will be like like one z like if you're doing some recursive thing right at the very end basically yes if you're doing a long recursive computation at the end you will need to send one z and i think um purchase will talk about some implementation numbers but

that's on the order of what is it like uh at the recursion threshold it's like uh a megabyte for between yeah two and four megabytes at the end but then again we can compress that right and yeah sorry i just want to jump in there are many metrics one can look at right if you were asking about the prover then you know i guess we didn't try them head to head but i i would be surprised if there is any input size on which glass 16 is better for prover just because 16 is just as simple as it is is still more complicated than this thing there's also like g2 computations and ffts so this this is i

i would understand that this protocol is faster and you also have to use pairing groups which are larger exactly but there is that part so there's other metrics like for example the recursion threshold that one we measured and it is better than graph16 the main point where there is like an enormous difference is of course the proof size and the verifier time both are linear here and very soon they get huge in like in megabytes and maybe tens of megabytes if you you know get pretty big right hey we're 16 that doesn't happen and of course you can compress them away like on the side you know outside of the recursion but that is the the this is a tool that is completely made for recursion

and nothing else basically and and right the proof the final proof size and verifier time they they don't depend on the depth of the recursion right then key thing they don't depend on the depth right so so what i think what one interesting number is like what would be the r1cs size where you beat grout 16 slash marlin slash plonk in in everything also in improved size and verifier time right probably if you're keep keep recursing on a smaller one cs you'll you'll beat uh you'll beat the others and the snarks in all parameters maybe that's i don't know i it's really the question what all what you mean by what parameters but um i mean i mean verify your time improve size i mean yeah there's either you easily beat probably

no but because just reading a several megabyte proof is going to be expensive when the r1cs is large enough no i mean uh right so so to get it down to like something that is manageable so like let's get some concrete numbers if you want even like your rnc says a thousand constraints which is less than the cost of a scalar multiplication um then it's going to be like 32 times 1000 which is like 32 kilobytes just for a thousand constraint r1cs and that's already larger than uh planck over uh kcg modern over kcg planck uh any of these systems over um

these ipa-based uh polynomial commitments so i don't think it's like a point at which any reasonable point at which recursion will lead to give you like a smaller overall proof size compared to um planck or marlin or beni halo or any of these systems um i think it's more a matter of like when you you find your application then you can do some application specific tweaks to make sure that and at the end maybe you can compress it via the techniques that we were discussing earlier use some snark to prove that decider is correct at a high level mm-hmm but that's yeah maybe we can continue the the discussion on concrete numbers when when british uh will represent them in a little bit um um do just

just one more thing um so there might be scope here for to use a square root um proof size um system uh it's kind of a hybrid between this and the ipa based systems yeah so i mean i think that uh that's absolutely you know you can uh there's uh well the inner prior argument has different variants with um so yeah i mean i think sort of you know there's a lot of interesting things you could still sort of combine with this protocol in the end uh to to even make the final proof uh be smaller

but i think it also depends on the application whether you know that that is something you need to do or you don't need to do or um yeah but and i'm gonna continue now so i i guess you know what what i already mentioned uh kind of and i think i hope people realize is that we are able to write this allows us to construct ivc team from two you know uh very very simple protocols and there's no pcps linear pcbs iops and it's all right like all this fancy machinery not even ffts inside and uh what i think you know ariel is uh alluding to is that

this eye actually does you're right this does give us a snark in the end because an ivc gives us a snark so uh basically from really trivial stuff we you know if we go all the way through our machinery uh we actually get a very simple snack construction at the end and i think we were already you know discussing concrete parameters on this uh smart construction and yeah there's a major caveat that of course we have to you know do a recursive circuit on a random oracle so you have to like you know it's like right there there's a key difference between you know using a random oracle and and like using fiat chamia

and in a protocol like uh say bulletproofs or marlin or plonk or whatever and here where we actually have to implement the random oracle then within the circuit but uh at least we only have to do there's only one cray and you know there's obviously an interesting theoretical question of week if we can even get rid of that query you know using uh collision intractable hashes or some other fancy tools you know and it's um it's not going to be easy but it's certainly not out of the question anymore um and that would be a really interesting theoretical result so the other thing is that you know that

i want to quickly talk about and i'll try to go a little bit faster now because we're nearing kind of the end is uh zero knowledge so uh if we have a zk what we need for zero knowledge is we need a z k arc for r1cs so basically what we'll do for that is we'll con struct you saw the super simple scheme which was just a an arc and and basically we will turn that you know in order to get zero knowledge it it becomes a sigma protocol so there's a very simple sigma protocol it's like what you would think of if you said like you know if you gave as a homework uh to a grad school student you know designed me a sigma protocol for r1cs

this is basically what we use and and then we also make our accumulation scheme we also need to make that zero knowledge and so create a zk split accumulation scheme for the zknike and the ideas that we use for that are are yeah we use a hiding vector commitment of course and then uh we basically get in order to get this zk split accumulation we kind of have to also accumulate a random accumulator in addition um to a and uh so this actually makes our scheme a little

bit more complex because the underlying arc is more com complex and then the split accumulation scheme also needs to be zero knowledge and um so yeah we will you know this is um makes you know the zero knowledge still possible and we also still have this specialized uh specialized protocol for right so you know if you look at the previous protocol it was only a protocol for accumulating one accumulator and one one predicate input and yeah we can make this also zero knowledge in in a specialized protocol we also apply this for the general case

right so so far as i said we accumulated one proof and one accumulator into one new community prime and if we want to achieve full pcd we need to require we need to accumulate n proofs and end accumulators into one accumulator and it turns out you know in in the past whenever we've you know all of the previous accumulation protocols that we looked at they fairly trivially generalized here this is actually not the case um so if we just try to extend the naive approach we we get messy cross terms but we can build um a two-round accumulation scheme for hadamard products and um to be honest i'll

i'll skip over this it's it's an idea that is very similar to something that was used in uh say uh the in a product argument paper and bulletproofs and sonic and we use we use a similar idea and uh for building a general accumulation scheme for hadamard products so um yeah i i want to now head over uh hand over to patricia again who will talk about the accumulation and yeah by the way all of this this kind of new stuff it's uh not quite online yet so the paper in general talking about split accumulation is online uh this this protocol for r1cs is something that we

recently added and i think we'll put out the paper uh well hopefully this week or otherwise ali will be very mad at us but um no uh we'll put it out very very shortly and now uh produce can talk about it it's not gonna be a new paper or a no it will be the same paper it will just be an update let me print and okay we'll tweet about it to let you guys know so uh yeah i'll stop sharing now um to talk about so pictures can talk about the amazing work they've done on on implementing all of this yeah so i'll try to keep it quick because i know we're over time um so let me share my screen

okay so where were we powerpoint okay right so yeah we implemented i mean so you know this is a very simple scheme by pleasing theoretically but also we wanted to test how efficient it is in practice so we implemented a general framework for proof carrying data which contains not only uh which contains a lot of as i mentioned earlier all the three different paradigms that are used in practice today so uh first we know this is not part of our work but from a you know pre-existing implementation in this framework we have the recursion via sub-linear verification which requires um uh you know implementing a generic interface for

snarks so our our pcd library is entirely generic so you just give it for example a snark and it'll spit out pcd based on recursion vs subliminal verification it's a bcp14 right and to then so into the generic interface for a snark we plug in various components for example we have a regression based on the marlin uh universal setup snark we have also implementation uh yeah we also have recursion vehicle 16 and so on right so this is not part of uh you know this work but um part of another you know part of prior work i guess then in terms of like in past part of this work we implemented both of the accumulation

um uh both of the you know recursion constructions based on accumulation and and on atomic accumulation as well as with accumulation so in terms of for for atomic accumulation we defined a sort of a generic accumulation scheme interface um and into this interface we plugged in uh our you know various constructions of uh accumulation schemes right um so for snarks for polynomial commitments and then constructions for the various uh pc schemes that people use such as kcg as well as the inner part argument one right and the nice thing about our recursion uh you know our construction is that it's again generic so

if i just give you a snack with atomic accumulation any snack any atomic accumulation but that's not um you know you can just plug it in and have a construction so it's like very modular so you know in the future somebody develops even more efficient schemes and it's easy to plug in and update and you know run it and get better numbers and then we also implemented the schemes from this work so uh within this accumulation scheme api we made sure that we can handle split accumulation um and then we have a implemented in that our narc as well as accumulation scheme for that knock as well as accumulation scheme a split accumulation for a very simple polynomial commitment um and together like this is all based on top of various cycles of curves

but together this basically gives us a comprehensive framework for using pcd via any paradigm that you might you know care for and this is all we hope to make it online soon at uh as part of the artworks ecosystem this is at arc pct um the this snark interface is part of oxnard and uh something wrong with the spacing there but this is in a soon to be online library for accumulation schemes accumulation right so yeah the benefit of this is that as i said we can easily compare all of these different uh instantiations for efficiency and um yeah with the application for ivc we

decided to perform this evaluation what we found was that you know so if you take the bctv14 construction with the state-of-the-art pairing based knock kraut 16 uh you know once you add in all the overheads of hashing and so on and so forth um for the ivc case uh the recursion threshold is somewhere closer to like 250 000 constraints this is um partially just because uh you know there is overhead just beyond the snark verifier but also because we're using the mnt46753 cycle right which is 753 bits and uh you know once you have scalar multiplications of that size inside your circle it's not cheap um

right so the yeah the benefits of this you know at the end you get like a very small um snark and it's generally efficient to compute the proof but these pairing friendly cycles the mit cycle is quite expensive right okay so then we also implemented the bcms20 uh slash halo approach right and this is not the you know without the optimizations that uh the halo folks have been doing um so it's somewhat i guess upper bound on the cost um yeah so the nice thing is that they don't have any pairing so that reduces the complexity you have medium-sized proofs you know they're not as small as crop 16 proofs but they're you know at most a few kilobytes and you

can use standard uh i guess fft friendly cycles of curves but yeah but the downside is that now your recursive cost is quite large um it's larger than grout 16. yeah which can affect applications because in the end your verification time is linear right so what in this work we when we implemented our simple narc and again this is like the generic protocol with uh you know which supports arbitrary parity so n uh proofs n and um all the accumulators uh for ivc you can even you can reduce this even further i'm sure um so you get like a very low recursion threshold uh but the problem is that now you have at the end large proofs but maybe that's okay for application and as

yeah probably as you can mitigate it in various ways but the takeaway is that now you don't have to work with um you know pairing unfriendly appearing friendly cycles you can just use standard curves even like set p uh base cycles right um and you get a cheaper recursive circuit [Music] and you know at the end a simple protocol which is you know there's a lot of when you want to implement a snark you have to take into account a lot of things but with implementing our protocol it's really a matter of you know everything together fits into less than 2500 lines um i'm confused about something because the um so for the halo paper uh which

um is we've optimized since then the halo paper had 17k constraints for the recursion threshold if i remember correct oh no it was 2 to 17 wasn't it yeah yeah yeah so this is this is our 16. sorry yes i i got that wrong um yeah hello will be much less than that right so i think this is for our implementation in r1cs of the key mission verifier we've not done a lot of optimizations like none of the uh glv based optimizations or you know special sampling of challenges or any of that um i see okay yeah that sounds about right then yeah so

that's why like we have a relatively large costumes okay this is also for so yeah the thing to note here is that um there's not only like a you know a difference at for some certain number of constraints but also as uh a different as you know increase the number or the size of the competition that you're checking right so this thing will grow logarithmically so this is for like a circuit of size um you know if your the circuit that you're accumulating is of size one million constraints right and but for the bctv approach and for our approach this cost doesn't change as you vary the size of the circuit of the competition at each step right so you can probably shrink this further and you'll see like benefits as you in decrease the

you know as you add more optimizations and this will also get lower but i think uh no matter what you do like you'll not end up with like a constant number of scalar multiplications uh and field operations i think this will always be this might become eventually possibly slightly cheaper than this i i don't have any uh guarantees there but i feel like it will always be more expensive than this approach and a lot of the optimizations that you can apply to uh for the 440 numbers also apply for the 65 number right yeah yes so the relative cost will sort of remain uh yeah in this argument that there is the same the exact same infrastructure underlying

the second and the third column so whatever optimizations apply to the orange they apply to the green so in particular you know if you want to delay scalar multiplications you could do it in the left you could interact right if you want to improve uh you know the constraints or you know group arithmetic it will affect the same way the left and the right uh so i mean you you can argue that the reason this that 440 k is so large is that it's a million constraint circuit did you say so if you were to split that circuit up and use recursion then um it would be much less so it would be uh

120 something thousand probably at the recursion threshold nice i think so the cost unfortunately it grows logarithmically so even if you split it in half then it still we end up with like something closer to like 400k constraints for the recursion uh for the cost of accumulation right but we did actually implement it for the halo paper and at the recursion threshold it was 2 to the 17 constraints right so i'm sure that a lot of there's quite a few optimizations that we can do i think i mean it's it's only a constant factor difference so i guess yeah um i mean i mean there are like differences in terms of like what constrained language you're using and so on um but i guess the takeaway from this

slide is not that you know uh the atomic accumulation approach is always going to be more expensive but rather just that there is a both asymptotic difference as well as i think the point is that um the recursive costs yeah they both use the same kinds of operations and if you optimize one then the other one can also usually benefit from those that's true and by the way planck is very friendly to the kind of things you need in recursion right yeah especially for uh certain scalar multiplications become very much more efficient um so uh yeah i just want to understand a little so this this 250k it's like it's no no accumulation

schemes it's like the cost of doing a pairing inside the circuit that's the 250k yes and the 440 yes so what so that's uh what yeah what what can you can you say just remind me what what what's being done in these 440 constraints like more or less checking the or accumulating the inner product argument so there's like login rounds of uh i guess interactions and login scale multiplications of log and scalar multiplications and those log in non-native field operations and so on oh but but they're non if they're non-native is i thought isn't this with this half pair something site there oh no this

this is not with a half this is like with a standard like pasta cycle um oh but it's still a cycle so why uh because in the end you do have to do some sort of scalar field operations right um uh in a sense that it's it's worth pointing out that you get a factor of two just from using the endomorphism optimization yeah so we don't have that optimization that should like half the cost of the scalar multiplications but then again that would also apply for this case um all right right there's something sorry what the patent for it expired or something yes yes last september or so yeah and then you get so is this for full length scalers or

um we try to keep it as short as possible wherever we can so 128 that's where possible okay so that's including the 128. yes so so do do you know more or less the relative call right because in this 440 i guess there's three uh that there's the scalar multiplications and i guess there's this hashing to get like random challenges uh do do you remember more or less the the one and this four four yeah yeah the breakdown is dominated by um so yeah so you have like yeah i think it's just dominated by the scalar multiplications and a little bit by the

random oracle stuff and there's a actually no the random oracle stuff is not that large it's mostly due to the non-native basically when you're doing the inner product argument there's they're doing operations both both over the base field of the constraint system so the the constraint system field right and this is um and you your the cycle allows you to make sure the curve arithmetic is efficient right but that you also have to do at least in our implementation you have to do some work with the scalar field off the curve who's arithmetic you're checking um ah okay so so the halo implementation completely avoided that yeah yeah so if you yes so we didn't implement like you know this delayed arithmetic

and delayed on intervals and so on that makes that that explains why it's um so large compared to our implementation okay it's also um the 65k is um also using that well it's also it's it's also the general pace protocol so what i presented was the special case protocol um for for ivc um where you can get down to i guess as participants saying three scalar multiplications this is the kind of general case protocol with n equals one uh m equals one and that is not quite as efficient so that's probably twice or like that's probably seven or eight scalar multiplication so um so in that 65k

you are using um non-native fields arithmetic as yes yeah how much of it so how how much of the 65k is that um i haven't done a breakdown yet but i would estimate it's probably close to at least 30 40 of the cost um okay yeah interesting and i think um yeah that's i think so so that's something where planck even if you don't use the deferred stuff then um it's something where planck uh helps because you can use lookups for that yeah um yeah i mean for to be able to use splunk i guess you have to move away

from r1cs and then oh maybe yeah you'd have to find a plunk equivalent of the um at the simple um knot yeah but uh i guess the the thing is you know moving away from ffts it does you know for example like the the the pluck-up stuff you know a turbo plunk uh that kind of stuff you know that that really does rely on polynomials it seems like um so there's downsides obviously i'm not sure so at first sight it seems to um depend on having the cyclic multiplicative subgroup but um i think it doesn't actually rely

on that okay well in the end it's a permutation argument though i mean yeah but you you don't have to do the permutation argument on the full subgroup right right only what permutation arguments at least like the most efficient way to do them right we we don't have any polynomials in here right like so it's um i don't know like uh you know i think obviously i think my the main point the only point that i wanted to make is that if you we kind of said like one of the main goals of this paper was was to say think like what is the debt simplest thing with the lease requirement that still allows us to do ivc um and and i think we've gone pretty far down that road

but obviously if you relax that back again and say like okay now maybe i don't care about maybe i'm okay with using ffts maybe i'm okay with you know using some things and you would hope that you would get better because uh otherwise you're doing something wrong yeah and actually in the current version of the paper we do have a narc which relies on fft so instead of using the harder mud product instead of accumulating hard amount product we just check it via you know the standard um strategy for snarks right um with the quotient polynomial and the vanishing polynomial um and so that one doesn't require the yeah any of that you know any of this yeah it doesn't require

yeah it doesn't require any of this machinery so we just replace it with a couple of small non-native arithmetic uh multiplications so that that also further lowers the cost for example well i think one thing that could be very interesting is if you could manage to get something you know that's like this is very simple uh and say just verify your proof size and verifier cost say n over login right if you could get some really not as maybe even you know somewhere in the middle between as simple as this and you know and then you know if you're doing recursion then then you know do

that thing for the original proof and then you know then recursively prove that with a snark uh right and then you'll you'll get you know maybe like even practical dish linear time because the right the the the recursive proof will be with ffts but on an over login thing so uh so that's i think maybe an interesting question here like is there something almost you know as simple as this but that you know does get you down a little like to prove size n over login and verify time and overlap right i mean the question is like um do we do we do we want that or do we just want to you know

what we can also always do and what we've talked about is uh just the only case where really the proof size matters is is at the very end um and you know we know that we can sort of just outsource that uh or you know like maybe it's just sufficient to outsource the verifier instead like at the end give a snark that um you know that that final verification check is correct and then um you might be able to get the best of both worlds but um yeah but no i mean all very good good questions and interesting answers certainly a lot yeah but just sorry so just to like

is it because i'm not sure so say i don't i don't really use recursion i just want to sort of aggregate uh login proofs or t proofs is the like is the verification time and proof size then oh but is the like is the aggregation cost like gonna be uh like the proof size plus t or is it gonna be like proof size times t like the the cost to sort of verify the the aggregation if i mean at the end uh yeah i uh maybe i'm not saying like say it's not exactly required i just give

you an advanced uh t proofs of size n right and they want you to do it or whatever so it's going to be linear in the number of proofs because you have to read the proofs but remi you can do this with halo already um there's a there's an efficient aggregation so if you do recursion there so you can just do a recursion to do the accumulation verifier um with for the t size thing and then at the end you only have um it'll be t plus uh size of r1cs um [Music] just a little bit um so that you could you could do that just do one step of recursion and that's efficient and

that's sufficient so so actually for orchard which is the next version of zcash we're using aggregation for halo proofs even though we're not using recursion and and that's that's just to reduce implementation complexity and autism complexity so that does work out very well in practice and uh guys thank you i'm i've actually got to jump in here because we're a little bit overtime um but uh this is a fascinating conversation and and uh incredible work so thank you so just a couple things before we include i'm actually just let me just wrap up and just finish the last slide or in the last line thanks and the paper is um yeah it's online it's like a older version as

benedict said um we will have an update uh hopefully just within the next week with these new protocols as well as more details about evaluation and implementation and hopefully more optimizations as well so thank you everyone thank you guys