ZK11: SCRIBE: Asymptotically Optimal Streaming SNARKs - Tushar Reddy Mopuri

Transcript

[Music] hi everyone I'm tar glad to be here thanks for coming um just a quick survey how many of you already know what snarks are perfect I might speed through those parts uh because the presentation is a bit on the longer side but if you feel like I'm ever going too fast please raise your hand and I will slow down um cool so today I'll be talking about scribe which uh is a snark in low memory environments we'll see what that means in a second uh let's start by revising what snarks are um they're in interactive protocol between aover and a verifier and the uh both of them share a

function f the prover has some public input X and some private input W the verifier only has the public input and the Prov hopes to convince the verifier that they know some W such that f ofx w equals 1 um and it does so by sending over a short proof that the verifier can verify in less time than it takes to compute the function itself the prover um unfortunately runs in more time than it takes to compute the function but hopefully not too much more um a few properties we look for are completeness which says whenever f of x w is indeed One V accepts uh knowledge soundness says whenever V does accept P must know some W such that f ofx w equals 1

succinctness says the proof is small uh snar are immensely useful tools in rollups private cryptocurrencies and a variety of other blockchain applications uh a barrier to adoption though has been highr overheads especially in terms of memory uh in fact existing snar provs require a prohibitive amount of memory that's linear in the size of the circuit here's a graph of the implementation of hyper blon a state-of-the-art uh linear Pro time snark um you'll notice that the plot stop stops for circuits uh of size large than 2 to the 24 uh Gates this is because the Prov ran out of memory so let's see what we can do about this um or let's see what

people have already tried to do about this uh one line of uh work to solve this problem has been streaming snarks in particular Gemini proposed the read only streaming model where the prover has much less working memory in fact logarithmic in the size of the circuit but has streaming access to the entire circuit which is stored somewhere in external storage let's say on a dis Drive um and it can stream through this potentially multiple times and perform computations in its smaller working memory uh but it does not have random access to the Circuit um this is what Gemini's performance looks like uh as you'll see the memory the working memory

requirements of the Prov scale only logarithmically with the size of the circuit um and the time looks nice but what that graph doesn't show is that as SYM totically uh the time requirements are order of n log Square n where n is the size of the circuit um in compar comparison the non-streaming Baseline prover would require both linear time but also linear working memory uh we ask the question can we do better um that is get the best of both worlds with small working memory logarithmic in the size of the circuit but still linear Pro time um this brings us to our first contribution uh we answer in the affirmative in the read right streaming model which is the relaxation of the

read only streaming model where the prover still has small working memory uh and read only access to the circuit but also has the ability to write out to the same external storage the disk or whatever and um it can still do so only sequentially and uh so it reads from the it can read um overall it can read from the stream it can perform computations in its small working memory it can write out things to the right stream it can switch freely between these two things and at any point it's also free to sort of go back and make multiple passes over either of these streams and most importantly it can swap a right stream that it's just written

down into a read stream um and why is this helpful um one this gives the snark uh approver the ability to sort of write out intermediate State onto a right stream and then go back and read from it um the only limitation here being that both the writing and the reading from this intermediate State have to be sequential and not random access um okay so those were that was the model does it help um yes it lets us construct scribe which is a streaming snark in particular a streaming version of hyper Blan um and this is our performance uh we get the best of both worlds it has linear Pro time and small logarithmic working

memory uh of course it requires a it requires stream sizes on external storage that are linear in the size of the circuit uh to do this we adapt the popular compiler uh in the non- streaming setting uh to the streaming setting where we take a streaming piop a polinomial uh interactive Oracle protocol for circuit satisfiability and a streaming uh for the rest of the dog whenever I say streaming I mean read write streaming uh so it also takes a streaming polinomial commitment scheme and it puts them together to build a snark um in particular we like I said turn the hyper blon Bop for circuit satisfiability uh into something that

works in the readr streaming model so what this piop requires is a streaming permutation check and a streaming zero check to construct these things we build a streaming a redr streaming version of the sum check protocol which sort of directly implies these two things if you don't know what any of these things mean uh I should go into detail about most of them over the rest of this talk um yes uh and as for streaming polinomial commitment schemes um we present a streaming version of the pstd 13 polinomial commitment scheme which is a multi-linear version of the popular kzg PC scheme and we also present streaming

versions of several inner product argument based Pol nomial commitment schemes such as Dory HX Etc um okay so those were our theoretical contributions but did it give us anything in practice uh yes uh this is so we implemented our protocol in Rust using the artworks framework and evaluated over circuits of increasing size and we saw that we're four times faster than Gemini uh but unfortunately two times slower than hyperplan which is in the non-streaming model uh which is our Baseline essentially um so this is actually kind of an old graph and with more recent um implementation improvements we're actually only 15%

slower than hyper plun so like seven to eight times faster than Gemini and like we wanted the working memory requirements scale only logarithmically with increasing circuit size um and we in fact concretely require much less memory than Gemini so for this talk uh to keep it on time I'm only going to cover the streaming Su check protocol and the streaming version of the pst3 polinomial commitment scheme um but before we do that let's look at the recipe for snars for people who aren't super familiar with the p plus PC scheme idea um essentially the snark prover and the snark verifier work as follows the snark prover runs this

thing called a piop prover uh it simulates it internally and the pi so essentially the poop PR and the poop verifier would interact to convince uh the verifier of some circuit being satisfiable or a function being um evaluating to one on those inputs and the piop pro would do this by trying to send uh few polinomial to the uh piop verifier unfortunately these polinomial are usually very large so the snark prover commits to any polinomial that the piop pr wants to send over and sends these short commitments to the verifier and then the verifier replies with random challenges and the snark prover does this as many times as the piop pr would like to once this is done the poop

verifier would like to verify these polinomial at certain evaluation points unfortunately it can no longer do so itself because it only has commitments to these polinomial so the snark prover uh sort of simulates the uh verifi queries uh and then produces um polinomial commitment opening proofs as well as uh the opening values at these points and sends these over to the verifier the verifier checks that these proofs are valid and checks that the some appropriate relation holds between these claimed evaluation values and comes to a decision um since the verifier is public coin you can use the Fiat meis stic to turn this entire thing non-

interactive so um let's go back to talk outline uh let's start with the streaming sum check um so uh the sum check is the Foundation of all linear time snarks this is thanks to a linear time linear space construction due to Justin Taylor in 2013 um but what is the sum check it is again an interactive Bop between a prover and a verifier where the verifier has Oracle access to some polinomial p and the prover hopes to convince the verifier that the sum of the evaluations of this polinomial so the polinomial um the polinomial that we care about in this case is multi that is of degree at most one in each variable um and the

Prov hopes to convince the verifier that the sum of the evaluations of this polinomial over the Boolean hyper Cube are in fact equal to some claimed Point Sigma um and it wants to do this uh by having the verifier do much less work then evaluating the polinomial over the entire hyper Cube which would take 2 rais to the little n work where little n is the number of variables so how the prover does this is it sends over some po nomials and again the verifier replies with random challenges and they do this a couple of times in fact as many times as there are variables and luckily for us uh turns out in the sum check protocol the polinomial the prover sends over here um are univariate so they're small and you don't have to

commit to them you can send them out in the open um so this leads to the Natural question uh the fact that this is such a foundational U primitive uh leads to the question can we achieve l your time in a readon streaming setting using only logarithmic memory uh people have tried and most attempts have been unsatisfactory uh in particular ct1 and bc22 which is Gemini require only logarithmic memory but take more than linear time something like order of n log end time um blendy which is concurrent work uh requires a little more than logarithm logarithmic memory but it's still sublinear uh but it runs

in linear time which is great uh so in progress is a we're trying to prove a lower Bound for readon streaming provs that says you can't hope to do much better and so blend is optimal in the readon setting and this leads to the question can we do better perhaps using read right streams we answer in the affirmative and we construct uh logarithmic space linear time sum check in the read WR streaming model um so before we jump into that let's do some multi-linear polinomial warmup uh consider a multilinear polinomial p of xal ax + B uh notice that P evaluated at 0 is equal to B P evaluated at 1 is equal to a plus b but equivalently uh B

the coefficient B is equal to P evaluated at zero and the coefficient a is equal to P evaluated at 1 minus P evaluated at Zer um what this means is that a multilinear polinomial can be represented equivalently by its coefficients or by its evaluations over the Boolean hyper Cube uh in particular a multi variate multi-linear polinomial let's say a three uh something with three variables can be represented by a table of size 8 uh in particular Pi in this table is the evaluation of P at i1 I2 I3 where i1 I2 I3 are the binary decomposition of I uh how does the sum check prover Works work so we're looking at

the first round here so how does F3 and then R3 look right so how does that first round work the sum check approver would like to well first it has to send over that polinomial F3 of x to do so it computes a sum of all the elements of this table with even indices and a sum of all the elements with odd indices and it sends these over to the verifier this is essentially the first po polinomial that it wants to send over um and then it receives the first random challenge R3

from the verifier and then it performs this fold step where internally it needs to compute this new table of half the size that sort of folds p in half and how it does this is by folding pairs of things together in particular these pairs are adjacent elements um and you don't really have to know where that exact folding equation came from all you need to know is to turn this streaming um all you need know is that like we fold things that are side by side together so this is very streaming friendly uh in particular this is how it's done by the prover say you start off with this table for p uh the prover first has to compute the sums so it starts with running even and odd sums both instantiated to zero and then it Cycles through the read stream for the

table and anytime it reads an even indest element it adds it to the running even sum any time it reads an odd indest element it adds it to the odd sum and does this all through the table and then sends these final sums to the verifier and then it receives the first random Challenge from the verifier and now it's left to fold this table using this new challenge how it does this is it reads a pair of elements and then it computes the appropriate folding and writes it out onto a right stream for the new folded table que and it does this all through the table and now it switches to reading from this table it just wrote out and it's ready to do the next step where it needs to compute sums over this smaller table and then then fold it

further right um so the streaming Su check I just presented was just for multilinear polinomial but we show in our paper that this generalizes to sums of products of multi-linear polinomial so P can be any polinomial that can be represented as the sums of products of smaller multi-linear polinomial um this is important because our piop required some checks over polinomial of exactly this form um and I believe the readon streaming setting doesn't generalize quite as neatly we also present a pre-processing variant where you can move all the right streams to a pre-processing step where you start with the table for p and then you pre-process it using right stream

and you have this new thing that you've written out that's much longer but then you begin and then you turn that into a read stream and then you begin to interact with the verifier um using the challenges and stuff and you only require read streams in the interactive uh part of this whole thing um and again to go over our efficiency the sum check the streaming sum check prover required linear time logarithmic memory but linear streams so that was the streaming sum check now let's look at the streaming version of the pst3 protocol uh also um I think it's important to note that like I said the streaming Su check implies the things we really require which are streaming

permutation checks and streaming zero checks and we show in our paper that we can easily build those two things using the streaming sum check while preserving the aforementioned ASM totic complexities right so streaming polinomial commitment schemes uh I won't be going over the setup uh for PST one because it doesn't have to be streaming but also two just to keep the stock on time uh but again we're going to uh treat a polinomial as a multi-linear polinomial as it's evaluation over the bullan hyper Cube so think of it as a table um the first thing the Prov needs to do while committing to something is also interpret the commitment key as a table of group elements and the

polinomial is a table of field elements and you essentially compute an MSM of these uh this group Vector with respect to the field Vector to obtain your commitment um this is this can also be thought of as an inner product argument between these two things and we well I don't show this in the stock uh perhaps if I finish early I can come back and like cycle through those slides but this can be done with just read streams where you can think of having a read stream for CK up here and the read stream for p and then you sort of the prover Cycles through the entire thing reading one from each at a time and adds the product to a running sum and you have the commitment at the end of the whole thing what does pstd open look like um well for starters what is it trying to do

it's trying to uh just to revise pstd open has some commitment to a p and it has an evaluation point Point Z and it's trying to convince the verifier that P the P inside CP is in fact evaluating to Y at the point Z how it does this is much like kg uh it computes a bunch of witness polinomial such well kg is univariate so it's a single witness polinomial here you have as many witness polinomial as the number of variables but you have to compute Qi of X such that P of x minus y is equal to the sum of Qi of x * X IUS z uh it then commits to these witness polinomial which we've seen is easy and sends these commitments over to the

verifier how do we compute these qis um so let's start by decomposing P since p is multi-linear it is of degree at most one and X1 and you can split it up into these two polinomial um G and H where H is essentially like factoring out the things that have X1 all the monomals that have X1 in them now we can add and subtract this term Z1 1 * H minus Z1 * H and we see that the left side turns into some remainder polinomial R1 but the right side looks kind of exactly like we needed it to which is X1 minus Z1 time something so H is exactly what we wanted q1 to be uh and we recurse on R1 to obtain Q2 all the way up to

q1 uh but how do we do this when we're dealing with tables so we start with a table for p and we notice that if you evaluate if you you know plug in x x 1 equal 0 in this equation you see that P of 0 and some other points is equal to G at those other points that is the left half of the table for p is in fact equal to the table for G similarly if you plug in a one you see that the right half of the table for p is equal to the left well is equal to the table for G plus the table for H but as we just saw the table for G is the left half of the table for p so the right half of P equals the left half of p plus the table for H

so we can just assign the table for G to be the left half of P the table for H to be the right half minus the left half and again uh just to remind you that's q1 and we compute the remainder to be G Plus Z1 * H how do we do this in a streaming setting we start with a table for p and we have to start by comput of by pulling out the left half so we stream through the left half write it out to some right stream that's supposed to represent G and then we stream through the right half and write it out to a right stream that holds the right half of P we switch the right half to a read stream now we have a read stream for the right half and a read stream for the left half which is also G um and we

read through th those two things to compute a difference and we write them out and now we have a table for H uh all we're left to do is computer table for R so we switched to reading from this table for H as well and then we have the random CH well the evaluation point in memory uh we have these two tables for g& H and it's pretty straightforward so again you read one thing at a time you compute the appropriate function you write it out and you keep going and you're done so putting everything together uh we just saw scribe which was a streaming version of the hyper blon snark and we achieved the following ASM totic

complexity uh linear time logarithmic space but there's no free launch and we required access to some external storage let's say a drive that uh has linear amount of memory and this can sometimes be expensive depending on the setting you're in um also I think I should note here that um the streaming setting is interesting because it's useful in any sort of situation where you have disparity between two kinds of memory something where you have a lot of memory but it's slow and something where you don't have too much memory but it's very fast to compute over like uh GPU uh GPU memory versus CPU memory perhaps even

GPU General memory versus GPU cache memory and then like we just saw uh CPU ram versus dis um yep and again um and here is the size of the circuit and this is what our tables look like again and I think that's it uh thank you for listening our paper will be online soon [Applause] okay we have uh by the we're going to take everything four minutes uh Beyond schedule because uh we started late but so any we have time for questions that's uh uh So like um as you great talk by the

way so uh is there a uh like in the scope of construction uh to sort of uh sort of combined streaming model with the old sound Che model where you can do partly streaming and stop like it's basically doing blendy with the protocol uh do you think that like there's scope for doing it like that uh you want to do that uh specifically in a GPU setting uh because I can optimize for streams of cash for instance but there can be like many many chunks and you can also sort of do parallel processing when you have multiple devices and uh you might want to sort of decide on the fight you know what you want to sort of stream this

part or you want to decide a priority that I will chunk my big instance like uh you have a uh like a machine learning model which you representing the inference in terms of some gkr circuits and you are actually doing gkr Gates and you may want to do them separately on different devices I mean it can arise in different complicated device settings so yeah um yeah so you can do that actually um another thing I should clarify from a theoretical point of view is this streaming we just presented is sequential because right right I'm asking more like can you can you take a chunks inad offf just a sequential OB you can in fact do chunks um actually

I'm just going to present something real quick um so for starters um remember I promised to come back to the commitment um here's what it looks like you have a stream for the commitment key and a stream for the polinomial and you cycle through them and you keep Computing this running sum but in fact in practice we batch these to apply fast msms we read constant chunks at a time and we use a fast MSM algorithm on those small constant chunks you can do all of these things and the streaming model is sequential

essentially because in practice if you know your access patterns you can do things like prefetching and batching um it can be any sort of well again you can sort of Shuffle things around but any sort of predetermined U access fashion U pattern should be uh is optimal in practice uh this is just the easiest one to argue about um so yes I think the answer is yes uh as long as your access to the EXP is the to the slope thing is predictable you can always still perform computations in the slow one as well if you need to that is here you would see it as you write out a right stream and then you perform some computation on the right stream as well but that's like that has different constants or it's slower or whatever and

then you can like come back and forth oh this is great because in GPU exactly you know where the data is all the time so you can precisely predict the mapping of the uh data so thank you