The Amazing Sumcheck Protocol" by Jonathan Bootle

Transcript

hi everyone uh welcome to this L station with Jonathan B today who is going to present us the amazing St check protocol uh Jonathan is a researcher at IBM research Europe St uh he has had a PhD at UCL London uh his work is quite extensive uh he worked on lattices he work called group signature a long time ago uh he's one of the researcher that you should really look look at look for so feel free to stop him on Google Scholar or whatever other website you're using and yeah uh enjoy well thanks very much for the

introduction Rafael apart from the talking maybe um so yeah today um today the talk I'm going to give is called the amazing suck protocol um okay see if I can yep I can change slides and and so the goal of today's talk is I mean this is we'll we'll obviously go through um all these different terms in case anyone doesn't know them hopefully some people have a bit of familiarity but the goal of today's talk is to explain um like a low memory streaming version of bulletproofspeaking.com explaining some

kind of other protocol in terms of the Su Che protocol but hopefully along the way we're going to see some some cool features and um expose exactly what's amazing about the Su Che protocol um so yeah I hope you enjoy um it's any is there anyone that doesn't have sort of any any familiarity whatsoever like um uh for example are there people who don't know what bulletproof is uh for example I just saw someone nod but I don't know if it's a so it's a nod for yes you know about it I hope it's going to be fine anyway I'm I'm going to explain it so it's it's all good

okay so um The Talk The Su protocol and bullet proofs are protocols in the setting of interactive proofs and arguments um so in this setting of course we've got an instance X and we've got a language L and the idea of an interactive proof is for the prover to convince the verifier that an instance is in the language so they're both going to exchange messages and then at the end of the protocol the verifier is either going to accept if they were convinced that the instance is in the language or they're going to reject if they weren't convinced that the instance is in The Language by the appr and so from all interactive proofs

we want completeness so if the really is in the language the verifier should almost always accept and otherwise if it's not we have soundness and we want that the verifier should almost always reject so there's going to be no zero knowledge in any of the talk today or any of the protocols um but um all of the interactive proofs that we're coming up with will have succinctness property so we'll be dealing with proof systems where the proof size is much much less than the instance size and and um in some cases we'll be aiming for proof systems where the verifi work is much less than checking that the instan is in the language in in a naive way so the star of today's talk is the

sum check protocol and the instance for the Su protocol is a polinomial p over a finite field f um a value U let's call it like a Target value in the finite field and a subset h of the finite field and the language we're considering is basically we have instances in the language whenever a sum of evaluations of the polinomial over the subset H is equal to the Target value so um yeah summing up every variable over every different possible value in the the subset H um and that's the language that the sum Che protocol deals

with and so the Su protocols used like really all over the place so um I think I think it was first introduced in roughly like 1991 or 92 and then the motivation for using it at that time was to prove complexity theoretic results like um uh basically give interactive proofs that co-b languages um were satisfied or not and it was also used to construct various different pcps and other kinds of theoretical proof systems um and since then um maybe on the more practical side there are a ton of succinct proofs and arguments based on the the Su Che protocol and this is

like one family of arguments and it's almost like whenever whenever you have another family of um of su Che protocols that gets designed like another variant of the Su Che protocol like the Univar Su protocol gives you a new family of succinct arguments and likewise with the Su Che protocol variant for tensor codes instead of polinomial it gives you a new family of sixin arguments with with new properties um so it's really really nice um there are other people besides me who are fans of the sum Che protocol um Justin tler has this great blog post on the the unreasonable power of the Su Che protocol and uh actually in a way I was kind of motivated by by this blog

post um in giving this amazing some Che protocol talk and I suppose I want to talk about um different properties that were discovered um since Justin or well different properties that were explored more since Justin wrote his blog post so other good things about the Su protocol are well the fact that just got a Time optimal Prov um very very nice one of the few protocols that's like that um very strong soundness properties that means you can make it non-interactive using the fistic but with with real hash functions and not with random oracles um so that's very good and lastly um something that we're going to talk about

a lot today the fact that you can implement the Su Che protocol in small space so um with a pro that acts like a streaming algorithm and never has to keep too much of the the inputs the input X in the head at any one time and so the way that we're going to the way that we're going to go through this talk is by examining connections between the Su protocol and other protocols so one connection um that's going to be important is the connection to split and fold Protocols of which bulletproof is an example um so the first one of these was introduced in

2016 in the discrete logorithm setting um and this was used to give various different types of efficient interactive proofs based on the discrete logarithm assumption and then generalized to all kinds of other assumptions in cryptographic settings like pairings and unknown order groups like RSA groups or class groups and even Lattis based arguments and there are some unifying abstractions which which connect all these split and fold arguments together um but yeah essentially um bulletproof bulletproof was a really popular protocol um there were lots of different implementations um there were there were articles with with titles like this and um and it was

incorporated into a couple of different cryptocurrencies at least um and the the start of this connection between the Su Che protocol and bullet proofs is really to notice that bulletproof has a lot of useful properties split and fold arguments have lots of useful properties which are the same as the useful properties of the Su Che protocol so the Prov runs in linear time you can also Implement some of these algorithms with a small amount of space a streaming that doesn't use too much memory um yeah very very similar um very very similar types of protocols and

so just almost by accident um with some other people we we stumbled on this connection between the sum Che protocol and different types of um split and fold arguments um which you know previously appeared to be two different types of protocols and we managed to show that they were both instantiations of um a more General type of su protocol that we called Su check arguments and that was a joint work with alisandra kesa and Katarina saki so we kind of collected all the Su Che based things all the split and fold based techniques and tried to show that they were kind of the same

thing so this this kind of this kind of motivates the idea of of using Su to explain a certain type of of bulletproof protocol we wanted to look at um a streaming low memory version of bulletproofspeaking.com drink of water and see if anyone has uh questions about the stuff that I've I've talked about so far yeah I Cann not see any questions so

far uh I actually do have one myself uh yeah so among the some check uh among the some check arguments since I will use the generalization uh what do you think would be one of the most interesting paper recently and why one of the most interesting papers did you say yeah okay um let's see I think um okay well the the Su check arguments paper that I've linked here is the one that explains the concept and tries to bring some of these things together but if if we think about the most

interesting examples then um there's um there's a paper called Dory by Jonathan Lee and um there's also this dark paper by um Benedict buns and um benfish and Allan who whose C I won't attempt and these are these are interesting examples because they've got succinct verification and not all of the other some Che arguments have that that property so um I would say it's the ones with it's the split and fall techniques with Su synct verification that really stand out yeah uh I wanted to ask the question later but since you started talking about six verification one of the disadvantage for some check and proofy

that's the verification is is uh let's say a bit slower than all schemes and so I've started seeing more and more papers combin uh combining different uh PR schemes uh and so basically using one to create in proof linearly and using the other one to have a v verification on on on the first proof If you see oh yeah okay yeah so for instance I've seen uh combinations of cross 16 and uh stock uh and I'm pretty sure there's going to be some talk about this uh in the connect in few weeks and they have been uh I say blog post and so on about this and projects

working on this so do you think that this could also be done with some checks or have you seen examples of this being done more particularly um yeah yeah I believe so um I don't yeah I don't I don't see why not at all I guess um the some of the the nice some of the nice features of these um let me think i h yeah it's it's definitely I mean I think it's it's definitely possible um I I don't see any reason why you why you

wouldn't want to do it I guess um I guess I guess one of the things is like lots of the um lots of the interactive proof systems anyway um they already seem to have a lot of um they already seem to have a lot of some checks inside and also the accumulator based approaches they I'd say they also bear some some similarities so um I do think that there are these connections that are that that are being being exploited um you know particularly with some of the the folding schemes say they're very very Su check like in a way so maybe not exactly some check but definitely some some stuff that works on similar principles yeah yeah yeah yeah I don't see any other

questions so you can continue okay thanks yeah well um yes so talk about interactive proofs so um yeah feel free to to interact as as much as possible please ask questions it will be much more fun okay so um we've talked about the Su protocol and its connection to um split and fold protocols a bit um we wanted to explain properties of bulletproof so let's talk a bit about bulletproof and what it is and what exactly it does so in this case we have a commitment c um which is in a group G of prime order and we have a commitment key um which is used to commit to to

messages um differently from the sum Che protocol the Prov has got their own secret witness which is a message a and the the language here that we're trying to prove is that a is committed to using um using a pedest commitment and and the keyg so C can be written as like the scale products of the message a and the commitment key G so it was shown in uh in 2020 in this bhrs RRS paper that um there's a streaming algorithm to compute bullet proofs where the Prov uses a logarithmic amount of memory um apart from this other parameters of the proof are its

logarithmic communication cost between theover and the verifier and the fact that it has a logarithmic number of RS so this is roughly what bulletproof looks like and yeah it was a very very cool um very very cool paper in 2020 um with this uh with the streaming algorithm um and this this streaming fashion of computing the proof the motivation for coming up with these uh these streaming low memory algorithms for computing different proof systems it's based on the fact that you might have you might have um very large amounts of like big slow long-term memory and only small amounts of very very fast and short-term

memory so if you have say a witness in an instance for a proof stored on your your hard drive and then you have to load it up into some shorter term memory in order to computer proof well the extra the extra cost of computing the proof might just be too much there might be too much memory for your system and then you might not be able to continue Computing the proof on that basis um so there you could you can try and think of different ways to get around this you could you could run all of the the operations for your pro algorithm and save all the results into slow memory um but that would just be really slow and irritating um so maybe maybe a nicer thing to do is to imagine

that the witness and the instance for your proof system are stored in slow memory and you have aover that's operating in in a smaller amount of fast memory and they have streaming access to the the witness and the input and the instance um so they can read these they can access the elements sequentially and then they can make multiple passes over the witness and instance and then compute the proof on the Fly um and you won't get out of memory crashes when you try and compute your proof system so not all proofs actually have this property um for example gr6 uses polom multiplication which is done efficiently using fast for transforms

and it's well it's quite it's quite difficult I think or intensive there's a lot of work on developing fast foror transform algorithms which work without using too much memory so um so it's not it's not an easy problem to to design these these streaming provs or or low memory Pro algorithms so in this talk we'll think about AA algorithm which has say a logarithmic amount of memory in the length of its inputs and makes say like a logarithmic number of passes over the the witness and the instance and this all goes back to U

papers on streaming interactive proofs from 2011 so the reason I learned about this um this paper from 2020 on streaming bulletproofspeaking.com have found better circuits but to compute um a

proof that you've correctly evaluated one sh 526 hash um uses it used 30,000 constraints according to the this circuit computed in this 2014 paper and actually um the typical limit that you could get up to on one machine is say using Groth 16 proofs um or you know various other types of proof systems maybe you could compute proofs that you'd correctly evaluated a circuit with 33 million constraints or something like that 2 to the 25 um maybe a bit more depending on your computer but I don't expect it would be more than two to the 30 so the Milky Way is on there for

scale but we actually want to prove much more uh like a filecoin daily um at this link you can check and they say that they're Computing um well they're Computing proofs and they're proving stuff about rough L maybe 600 trillion um calculation steps um every day this is not using one proof this is like combining several different proofs together and aggregating them and composing them and so on um but we actually do want to we do want to be able to scale up our proof systems to prove things about extremely large statements otherwise um we're we're just going to crash and we're not going to be able to compute um useful proofs um so it's fun to come up with

proof systems that can handle these instance sizes and there are different ways of solving these memory problems one is just to try and use more machines so I think the previous cut off of that was around two billion constraints using 20 machines to compute gr6 proofs um another method which obviously scales massively you can just um you can just keep going and compute proofs for really really massive statements in these ways is to use things like folding schemes or accumulators or compose proofs together and give proofs that you've seen other proofs in order to to compress things and continue proving a statement in in many different steps um but one piece of work that I

was involved in um came up with uh came up with these streaming Pro algorithms and we were able to scale our system to prove something about um instances where n was equal to 2 to 37 or 100 billion um this wasn't based on bulletproof but it was really inspired and motivated by this 2020 paper um which showed that you could run bulletproof in in a in a streaming fashion with this low memory prover um and that's sort of how I got interested in this paper um but this paper BH rs20 it actually came out it actually came out and it was investigating these streaming properties before the paper

with this connection between the Su Che protocol and and all the split and F techniques was published so the reason I wanted to give the talk today was to kind of go back and revisit things and try and explain the results of this 2020 paper using um using this Su check connection to bulletproofspeaking.com I'll take a pause here again and and see if anyone wants to ask any questions but please do ask questions even the smallest question I'm sorry you're toid of the

speaker right now there's no question yet okay no problem but will come sure okay um so we so these are these are the different things we'll talk about we'll go into more details on what the Su protocol looks like how you compute the messages and stuff like that um maybe we'll talk about why it's secure um depending on how much time has elapsed we'll talk about inner product arguments based on the sum check protocol um because uh these are really directly analogous to to what goes on in in bullet proofs actually according to this Su connection um we'll talk a bit about why these things are space efficient can be

computed with streamings and then finally I'll try and convince you that bulletproof is really some check protocol in Disguise so I guess um yeah I may end up skipping the um the security section um in the interest of time but um I think yeah particularly the um the third section on inner product arguments and the last section where you where you see that um bulletproof is really a su Che protocol should be should be interesting or hopefully a bit unexpected if you've not seen them before so the suck protocol was introduced in 1992 we' talked about the the instance

for the protocol which is this this polinomial Target and subset and the language and what happens in the protocol is the Prov computes this polinomial q1 um which is based on taking the polinomial and almost Computing the target value except that the prover doesn't evaluate the first input argument for the polinomial they only sum up over the second value to the the last value and they just leave the first one free so they don't they almost compute you but not quite and then they send this polinomial to the verifier so the verifier finishes off the calculation of the target EU and then they pick a random value from the

finite field and send this back to the Prov and this has the effect that the proven verifier started off with a su check instance with the polinomial p and the target U and after the protocol we've essentially reduced to a new polinomial um P Prime which is like P but just evaluated at the randomness in the first input and the new Target value is q1 um evaluated at the randomness R1 so we've made progress here because we've reduced the number of variables of the polinomial by one and we've got this new instance which satisfies um this new Su check property and if we keep going and just

do more reductions then eventually after all these reductions we will have REM removed all the variables from the polinomial and the final instance that we have is just checking that well this this constant polinomial P to the L is equal to this constant um U to the L so the final instance is is basically just checking a polinomial evaluation just checking that P evaluated all these random points is equal to this um this single value so if the verifier had wanted to check the original language in a naive way then they might have had to evaluate the

polinomial um many many times like as many points as there are in h to the L which could be really big so even if we think of a small thing like a small set like um H is equal to 01 then the size of H to the L is going to be 2 to the L so from a potentially really large number of evaluations down to just one for the verifier so that's the big advantage of of using this protocol and then if we look at the whole thing unrolled um then we have a kind of total description of the polinomial QI that the prover computes and then sends to the verifier sequentially um here are all the verifiers checks performed all together

and then the final instance that we get yeah essentially a polinomial evaluation so we know the verify mix is saving here and the proof size is not too big either if D is the the degree of P let's say the maximum individual degree in any individual variable then the total Communication in this proof is the number of variables time times the degree um up to constants and the original instance size had quite a lot of coefficients so the the the amount of communication in the Su Che protocol is much much less than the original polinomial and the verifier

makes a big saving um so this shows that the Su Che protocol is uh is really a succinct protocol okay so I think I'll skip this um well I was planning to skip this discussion of like the the security properties of the Su critical um but um maybe I'll just pause here have a drink of water and uh check whether anyone any anyone wants to want to see it uh yeah we actually have questions MH uh so once some would like to know uh what pral scheme and opening scheme we can use for the for the

game uh here you are only presenting the uh interactive version and so we wanted to know also if we could use to have non interactive version and finally what would be the verifier cost for using transformation for the proof composition for the proof comp um okay so firstly yes definitely you can apply the fistic to this protocol um actually um because of the properties because of the way the soundness proof of the

protocol goes um have a strong soundness property called round by round soundness and this makes it easier to analyze what happens with the fistic so even though the protocol has a non-constant number of rounds this round by round sence property gives you a a good Advantage when analyzing um what happens when you make the protocol non-interactive um I think for the for the second question um what commitment scheme might you use when you're using proof composition um let's see um to be honest I'm not too sure how to answer that question right off the bat um I might try and come back to it at the end or um if you send me an email or something I can try and give you a

better answer but um yeah nothing comes to my mind right now I thank you so much thank you so much for your answer okay so let me skip forward a bit I'm just going to pause and pause my screen share and Skip forward and we'll talk about how to do inner product arguments using the the Su check protocol um I have one question myself if you don't mind uh so here you are uh if I understand well you're doing if you can go back back to the previous slides you are doing PRS because you are checking uh you are evaluating each uh

variable one by one yeah so oops no worries uh so my question was uh would it make sense to at each r speal p into two pols of smaller sties like for ffts and so to evaluate uh several times at each run so that you would have a fewer number of runs but of course uh higher communication per run um I'm sorry could you could you explain the this the splitting idea just just once more yeah uh it's uh it's a bit like the same IDE for ffts uh and the K algorithm where you would uh uh

split P into two PO with odd and even TS of course P to be a of two uh and so you would have two pooms and four then eight and so on that you would evaluate at each run uh but you would be able to evaluate more variables per so you would have few ofun so you would have fewer run of communication uh but uh I guess memory wise would be more expensive because you would have more points to8 yeah yeah okay I think I understand a bit better now yeah I think you can do something like that so um so what H what's happening in this protocol is every so we have a sum that we want to check and every time when the pro

computes their polinomial Q they're removing one entry from the sum um now really this is a now really like in full generality this is a protocol where you have some expression involving like operators over many values and so um I think if you if you just stare at the expression for Q you could leave like two variables X1 and X2 free and some of the rest you could kind of strip off two operators at the same time if you wanted and then um and then change the verify checks accordingly um so there all yeah there are all kinds of variations on this this on this protocol if you want to reduce the number of rounds or or do things slightly differently you would end up with more

communication um if you if you did it the way that you said because um yeah you'd have at the moment we have like the q's have one variable and degree D you'd be sending yeah I guess you'd be sending um yeah they'd have maybe roughly D squ coefficients yeah but um I think it probably works than y okay so let's skip ahead a bit and talk about um space efficiency second just skipping skipping skipping through the

slides okay um so let's talk about how to do inner product arguments using the sum check protocol and this is going to be I guess this is going to be like directly analogous to the um the bulletproof protocol and discussion that we see a bit later on just in maybe a slightly friendlier setting so if we want to do inner product arguments using the sum protocol um now we're in the situation where the instance that we're considering will be

two commitments A and B and an output U um the prover has two vectors little a and little B which are supposed to be the messages inside the commitments and the pro wants to convince the verifier that A and B are really inside the commitments and they satisfy the correct scal of product relation so the sum protocol runs on polinomial so straight away if we imagine that we have pols available and think about polinomial commitment schemes we can imagine the polinomial commitment scheme involves like maybe some key generation but once you have a key you can commit to um a particular message polinomial we have some binding property which means

it's difficult to find two messages which give the same commitment but the most interesting thing about polinomial commitment schemes is an evaluation protocol another interactive proof so that if you have a key and a commitment to a particular polinomial and some inputs and outputs then the prover can convince the verifier that um that basically they know um they know a polinomial inside the commitment which satisfies the correct input and output relation so let's change the goal post slightly and imagine that we have polinomial commitments capital A and B to to the vectors A and B and we want to

prove this um this scal of product relation so what we really need now is a way to go from this scal of product relation that we want to prove into something to do with pols and you know also a sum relation on pols because we've got the sum protocol that deals with exactly that kind of thing so what we need to be able to do is interpolate um interpolate A and B and consider the polinomial PA and PB with exactly the same coefficients as the vectors A and B and then we'll be able to get to um to like a proper polinomial

representation of this this Scala product so we can consider lran polinomial in in one variable and multivariate Lon polins as well and the point about these is that whenever X whenever you have a binary X which is equal to um the index I defining the L polinomial then the polinomial is going to Output one and otherwise it's going to Output zero which you can see kind of just by by direct calculation so if we have a particular vector and we consider the the entries eye of the vector in their binary

decomposition then we can get pols using these lran polins which uh which just exactly interpolate the um the vector v over the finite field and whenever you put in a particular binary input um which which is like the binary representation of index J then you get VJ as the the output so the gr polins are like they're not they're not too difficult they're not too bad to deal with um the reason I sort of display them here is to you know prepare you for a bit of General generalization later um where we deal with polins that might not be so familiar um the compan PO you would have

to use I guess ifs and so the cost would be super linear be login um so that's that's not the case actually um so because because they have this nice structure um so when let's see um I'll see if I can write on the screen I don't know if you'll be able to see me but um depending on the value of I you either get this term or this term when you want to evaluate a polom by like this um you can actually because because you have um X1 appearing in many different terms um you can sort of split

the sum according to whether the first bit is um the first bit of I is zero or one and then there's a nice sort of tree likee algorithm for computing this which takes linear time in the end um so this is actually much more efficient than if you're using univ L pols You' get you you'd probably get an N log in there oh perfect uh and I also had a question just before but I didn't have the time to ask it uh do you need any prop any specific properties for your skill such as someity the PO to be in for the addition or something else the the polinomial

commitment schemes yeah uh no you don't need you don't need anything um this is they're just used to prove that the evaluation is done in the end um now when we're not considering zero knowledge today if you wanted to add zero knowledge it would be easy to do that if the if the polinomial commitment schemes were homomorphic um yeah but yeah in this simple setting you don't need anything like that at all thank you okay so these pols have a value um D equal to one so the maximum degree in any variable is one and like a log n

number of variables if we want to interpolate something with n entries oh my annotations are still on the screen okay so if we want to give inner product arguments what we can do is use these polins to interpolate A and B and take the expression involving scal products observe that each entry of a vector is given by an evaluation of one of these interpolating pols and then if we take the product polinomial of the two evaluate that at any binary input we get the product of um an entry

of a with the corresponding entry of B and if we sum all these up this is the same as Computing the the scal product of A and B so we can rewrite the scaler product of A and B um equal to U as a sum of polinomial evaluations and then we have a protocol just for checking that so we can start by running the sum Che protocol on the product of PA and PB now at the end of the sum Che protocol what the verifier wants to do is check an evaluation of the polinomial at a random point so in this case the polinomial we will using is PA time PB this is actually hidden from the verifier since um since the verifier is

only seeing these polinomial commitments and not seeing pa and PB which only the prover knows so theover has to help the verifier out just a little bit by sending the evaluations of the polinomial to the verifier and then the verifier can do the final check in the sum check protocol and they can prove using the polinomial commitment scheme that these evaluations were done correctly with respect to the the commitments so as soon as you have um Pol polinomial commitments um you can prove lots of different types of algebraic expressions like as well as just inner products um just using the sum check protocol to reduce to something that you can then check using the um the evaluation protocols in the

polinomial commitment scheme and then the cost of this is fairly good um the degree of the polinomial p is two a constant and we've got log variables so we're going to get o of log n proof size from the sum check protocol sending like constant size pols over logarithmically many rounds plus like whatever the cost of the the evaluation proofs are okay um now we're going to return to this later and um the setting is going to be slightly different so is there any

is there any part of this which um which seems seems strange or like doesn't make sense it seems all good great okay so now let's talk about why the the Su Che protocol is is space efficient and um this will help us build up to a finale basically we're going to show that the sum Che protocol is space efficient and that there's a streaming method of computing that with a low memory prover then as soon as we see the bulletproofspeaking.com

so what we need to do in the sum check protocol um if you know something about um bullet proofs already then um you might see some you might see some connections or analogies here but um in the Su Che protocol um because we're reducing gradually to smaller and smaller pols where we just evaluate the polinomial that we start with say at um more and more random inputs then we need like we need to prove that it works for the first step of the Su protocol if we can compute if if there was a way to compute the first message in the sum check protocol using a small amount of memory and there was a way to generate the next

polinomial in the sum check instance so this P Prime where X1 was evaluated at R1 um if we could stream that based on the initial polinomial then we could do something recursive so if we have a low memory algorithm for reducing one step we can combine it with the same algorithm to get low memory algorithms for producing the next steps so first let's show that we can produce um uh like witness pols or um pols for the sum check and we can reduce the instance in a low memory fashion given that we only have access to the the original input um which is in this case a vector a and like um I guess also a vector B but I'll just show the case um the case for a

here so if we if we kind of evaluate things and look at um look at what we get in the end when we evaluate this uh interpolating polinomial for a um in the first input argument um we basically get a sum of N minus two things and we've collapsed pairs of values together so we've collapsed say like a z and A1 together by taking a linear combination with R1 and we've collapsed A2 and A3 together and um a four and A5 together and so on and so forth so given access to a stream like a sequence of elements of the vector a um we need to be able to compute the the

coefficients of this polinomial and so obviously we can um if we have access to a as a sequence of elements the calculation that we want to do just looks like this and if we want to reduce further rounds in the sum protocol then we just need to collapse those together as well and then at some point at the end of the protocol we will have collapsed everything down to a single value um so this is how you compute like reduced instances for the sum check and if you want to stream these you just need to do everything given sequential access to the the entries of a so um you can take the first two entries compress those into something you could

take the next two entries compress those to get a stream of um of the vector a prime um so you can do this in a linear amount of time a constant amount of memory and just one pass over the the input a and similarly for collapsing um the next instance down to get um to get the next polinomial for the sum protocol and so when we add all this up like overall just for compressing the instances of the sum protocol in a l memory way um we're going get something which is overall a linear amount of time

a logarithmic amount of memory needed and just one pass over the um over the input Vector a and then when we actually want to put this into the um the Scala product argument so we have access to inputs a like now we know that we can always stream pols um P sub A and P subb evaluated at some different input arguments in a low memory fashion um so we can generate streams like that um and we want to compute a polinomial which looks like this so um like a sum of sum of different uh

polinomial evaluations in all the later input arguments so we can sort of we can actually um we can actually compute this uh incrementally so if we want to compute q1 in in an evaluation basis um maybe not in terms of coefficients we could compute q1 um evaluated at various different various different points um we could um we could sort of we could use the um evaluations of PA and PB which are just the same as the entries of the vectors A and B and we could sort of we could do some some operations on those and sort

of incrementally compute um the polinomial q1 um using a few elements of the sum at a time so just gradually building up to that and Computing it in an incremental way um we've also seen from the previous slide that we can get um like uh new compressed input vectors um a prime and B Prime um which are like the instance for the the next round of the sum check protocol we can stream though we can generate streams of those based on streams of A and B so s of similarly we can like incrementally compute the next message in the protocol from the streams of a prime and B Prime and and so on and so forth until we get to the end of the protocol so to generate reduced um

reduced polinomial where we've partially evaluated from the inputs A and B that takes over one time over log in memory and over one passes from the previous slide and over the course of the protocol we want to compute the first instance the second instance and then finally the the log nth instance and incrementally Computing these these Qi polinomial from um these reduced instances is again a linear amount of time um and a constant amount of memory here and passes so if we total this up we get um we get a streaming Prov algorithm for computing all the messages in this protocol and it uses o n log end time a logarithmic amount of

memory at any point and it makes a logarithmic number of passes over over the inputs to the protocol so there one pass for every round of the well over one passes maybe for every round of the subject protocol so yes how's how's all this so far no complaints so far unfortunately okay I see that um I see

that we're coming up to the end of the hour um it will go a little bit over that but um yeah we're almost at the uh let's say the punch line or the um the payoff where we can get some some streaming properties of bulletproof basically for free so um yeah we may take uh 10 minutes or maybe 15 longer past the hour I think but uh not too long yep don't need to worry about this yeah okay so um it's a it's a proud moment where I can try and convince you that bulletproof is is actually just equivalent to a very strange type of some check protocol and then we get all these space and streaming properties for free so let's consider the original um

bulletproof's method um in the original um let's say the original source of of of this type of protocol the prover wants to convince the verifier that they have a message which opens uh commitment so this inner product relation and the protocol proceeds by splitting the message a into a left part and a right part Computing some some cross terms where the left and right parts of the the messages and commitments are combined just um left to right and right to left sending these commitments to the verifier and then the verifier responds with a random field element as a challenge and so this has the effect of

um reducing the instance just like in the sum Che protocol we've reduced the message to um a linear combination of the left part and the right part which is only half the length of the original and we've reduced to a new instance as well so the new instance which um should be C Prime is uh is a combination of the the minus commitment and the original commitment and the plus commitment and we've got a new commitment key which is also half the length um because it's the left and right combined as as well and these are supposed to satisfy um a new inner product relation so the

Bullet proofs protocol is for reducing problems about Computing these pedicon commitments to problems of half the length and if you do that over and over and over again you eventually get a commitment which is which is sort of trivial it's just a group element where you've only committed to a one element message and then at that point the approver could easily send it to the verifier and um and the verifier could just um could just check so this is a big saving over sending all the elements of the original message a because we've only sent two elements um in every round and it takes log n rounds to to half the length of the message down to just the constant and in

the end what we get is a verifier time which is logarithmic just for doing all the calculations on the C's and um we get a linear verifier cost for for computing this final commitment key CH so this is what bulletproof looks like and now I'm going to show you a different thing um which is which is which solves the same problem but is based on the the Su check protocol okay so if we've got a pedison commitment we know that a pedison commitment is is sum of products and I've been writing um C equals a * G so

I've been writing this pedison commitment as as a scalar product so this is a scalar product of a field element vector and a group element Vector now we've we've already seen that the sum Che protocol can give us things for reasoning about scal products over well Scala products of two vectors over finite Fields so um maybe maybe someone can give me guess as to um what we should try and do to give a proof um related to these pedison commitments since we know they're based on scale products so some like someone from the audience uh give give me a hint

otherwise um Rafael is gonna have to do all the work here please anyone eray do you want to say something yeah the answer is always some check indeed so I want to say about sorry I want to say about Peterson commitments but uh

it's not important too much uh I I want to say yeah some Che okay yeah of course it is um the whole talk is about how amazing the S protocol is um obviously it's amazing enough to to deal with this situation too um now the difference is here um I guess that should be a capital G but um instead of thinking about pols and interpolation over finite Fields um now we've got this Scala product which is defined with a field element vector and a group element Vector we just need to think about um defining pols over over groups and a polinomial that can interpolate the commitment scheme over

the group and so like as soon as you can reconcile with the idea of defining polinomial that work over over a group of prime order then you can just you can just run the same kind of sum check protocol as before and this is almost this is almost the same as what we've seen but it's not quite the same and the reason is that with the original scal of products protocol um the um so the prover the prover knew the vectors A and B and then was evaluating both of those polins for the for the verifier and sending the evaluations this time the verifier knows the commitment key for thems as it's

part of the instance so um the verifier can evaluate the the group element part of this polinomial at the end of the sum check and they only need the Prov to help them with the the a part in fact it's important for the the soundness of this protocol that the prover evaluates the a part but the verifier if actually actually evaluates the um the G part for themselves so the proof size is um well okay we've done a sum check with the quadratic polinomial quadratic polinomial um in one variable have um have three coefficients so um initially it looks like the proof size here is is three log

n um there is a way to optimize it down to two and get something with the same communication complexity as um the bullet proofs protocol for the previous slide and the cheap operations from the verifier um the Logan operations when you compute the new C values and bullet proofs correspond to all the the sum check verifier checks the expensive operation for the verifier from the previous thing where they were folding up the commitment key smaller and smaller that corresponds to an operation where they evaluate um this interpolating polinomial in the the commitment scheme so all the costs everything the communication corresponds really exactly to what was going on in the the bulletproof

protocol and uh we discovered this kind of by accident and um up to a change of basis we um we discussed this in in our paper on some check arguments and just in case anyone's nervous about the idea of pols over a group then really everything's much the same as before except um well when we want to evaluate a polinomial over a group um the evaluation points are always field elements so these LR pooms that I'm going to draw a circle around um when you valate those at field elements you just get field elements and if you multiply those by group elements um then we're just going to have scal multiplication between group and field

elements so um so it's really fine to Define polins over groups like this um nothing goes wrong and um and the protocol just um just just works out fine so let's see so I had some slides on the um the soundness of this protocol which I'm going to skip I'm just going to explain what kind of soundness guarantee it satisfies because with the Su check protocol um the original one um with the classic sum Che protocol the prover and the verifier both know the polinomial P um so we've got a soundus question does p sum up to give the target value or

does it not um but it doesn't make sense to ask those kinds of questions pedison commitments because any group element actually has an opening as a pedison commitment in fact there are lots of different messages um lots of different message vectors which will produce a particular pedest commitment from a certain key um so there's no point asking if the instance is not in the language it's it's always in the language because there are always messages that open a commitment so we need to consider a knowledge soundness notion where we have a knowledge extractor that um given access to certain protocol transcripts um is able to um to extract uh a valid message opening to the the

commitment so I'm just going to pause here and um skip the rest of the sness argument um and then um then we'll kind of finish up and summarize skip skip skip okay so given this um given this connection between uh Su Che and bulletproof it's really easy to design different variants of the the bulletproof protocol now and to see where different types of work come from so if I were to build up a correspondence the polinomial we used in

the protocol just now um interpolates with l polinomial the one and it has um has the the set zero and one used in the sum check um and we compute the scal of product in in this kind of fashion whereas in the original papers that introduce split andf techniques leading up to bulletproofspeaking.com reverse order um and then the coefficients of the polinomial in the sum check come out to be exactly this C plus and C minus from the the

bulletproof's protocol or at least the 2016 version of the the protocol so the actual bulletproof protocol proves things about combined commitments where you have a single group element committing to A and B and the scale of product and with the Su Che view it's really easy to see what you should do to come up with a split and fold protocol for this type of commitment um you should just have one polinomial that produces the first Scala product add it to one polinomial that produces the second scal of product and then we have like a third component which produces the scaler product of of A and B so if I messed around with the polinomial bases and the set H enough I

would be able to recover the um the original bulletproof paper as a type of su check all the messages would be the same and everything like that just we have written the protocol in a different form and similarly if I want to come up with a polinomial commitment scheme the evaluation of a polinomial whose coefficients are a vector a um well the evaluation is equal to the scalar product of a and an expansion of all the the input values into various different types of monomials so I could come up with a polinomial commitment scheme by running a sum check like one to produce the the commitment and one to produce the the polinomial

evaluation and and basically since the Su Che protocol has these amazing streaming properties um any of these protocols that that we produce um as some checks um different for different types of commitments different types of proofs of knowledge of openings of commitments they're all going to have the same kind of uh memory efficient and space efficient properties um so this was proved kind of from scratch in in this bhr rs20 paper but um given the Su check connection you can sort of see it um straight away and it explains their results in in a different way and you can extend this to lots of other different types of um commitment schemes under different types of

cryptographic assumptions um which we do in the paper so including based on L assumptions okay so I just summarized the stuff that we've seen um we've we've seen what the sum check protocol is we've seen some inner product arguments how they can be computed in a space efficient way finally we've seen that bulletproof is a very particular type of sun check the polinomial happen to be on groups instead of fields but that's it and thus it's going to inherit all these nice space efficiency properties um basically because the original sum check has them and I think some really nice extensions

of this come with applying the same techniques to different families of su protocols or different types of split and fold protocols for example we saw that the scal of product protocol had um uh a low memory Prov algorithm but for different varieties of sum check like the Su check for tensor codes um we don't really know a whole lot about the the streaming properties of these protocols and actually it's hard to encode using some of these error correcting codes in a streaming fashion so it would be really cool to have some low memory protocols um based on these subject variants as well this would give us some some time optimal low memory proofs um based on error correcting

codes they would work something like fry proofs or stars but with um let's say ASM totically more efficient error correting codes and another way to go would be to try and show that um techniques used to make the protocol non-interactive um without relying on the random Oracle model um extend to split and full techniques like bulletproof so maybe using the sun check connection there's there's a way to do that so I guess uh I guess going back to um back to the start of this talk um I wanted to try and convince you that the Su Che protocol is really amazing and hopefully I've done it because at the

time when we came up with these discrete logarithms split and fault arguments we had no idea that they were anything to do with the Su Che protocol at all um it was a really surprising fact that we discovered almost by accident and then still there were other papers coming out like this space efficient one or other papers proving properties of these split and fold arguments and then some of them have turned out to be really closely connected to the properties of the the Su parol so it's sort of amazing that um we kind of rediscovered that protocol in in a different format and I hope I've managed to convince you that this is um at least a little bit surprising and amazing uh thank you very much

thanks sorry thanks Jan for this talk it was great I actually I at least think that that the some Che protocol is awesome uh I can see a few people clapping here and there I like to ask if any participant have any final questions for Jan is it all it's okay I'm reading it so yeah is it the split and fall the Su checks or is it that both these classes of protocols follow a divide and conquer Paradigm um good question so I think the sum Che one the sorry the split and fold ones most of

the protocols that most of the protocols that we've seen using the split andf techniques um you can you can interpolate you can basically interpolate the different messages in those protocols um you can you can almost always do this kind of interpolation and then get a su check interpretation of the same protocol um so i' so so far I guess I haven't seen I I guess I guess using interpolation you can sort of interpret most split and fold protocols in that way I think what's really interesting is if you do get divide and conquer protocols which are which are less algebraic that you can't do that interpolation thing on and

you can't see them as as pols or codes so so far most of the ones I've seen um they they can be like they can be turned into some checks whereas the divide and conquer class is sort of broader and it doesn't have to be based on this on this algebra related to to polinomial evaluation um so I think an example where you can see that is um so abam kopali um is one of the authors and I think the other one is Brian poo and they have a paper on uh tensor reductions and um I think those those tensor reductions are maybe U maybe an even broader class so um yeah if you're interested in um different protocols um and how they fit into the framework I

think it would be interesting to find a divide and conquer protocol which is a tensor reduction but which is not expressible as some sort of su check protocol fry maybe ah I think I think um you could probably Express fry as a as a sum check because again it's very it's very algebraic I mean I think some parts of the verifier check you would have to interpret differently but ultimately the the folding procedure is is very very similar so um I I don't think it would be exactly the same maybe not such a neat correspondence as as for bulletproofspeaking.com don't see any of

the question and actually I have to think to a few things you said before I can ask the question myself uh and it will be offline for sure uh so thanks lotan for this talk it was amazing and yeah uh I guess we can say have a good day and to you see you later hopefully yeah