Twist and Shout: Fast, Simple Memory Arguments

Transcript

Hi everyone, welcome to today's A16Z crypto research seminar. Very pleased to introduce our very own Justin Thaylor who will be speaking about the global global premiere about Twist and Shout. >> Yeah. And so, uh, twist and shout is, uh, some work we posted online in January. And, uh, the engineering team here at A16Z along with our, uh, fantastic engineering interns the last couple months have been working on implementing it since then and they're just about done. So, this the opportunity to give this talk today is is timely. So, yeah, let me uh start at the beginning. So, this talk is about snarks. What is a snark? A snark is a cryptographic protocol that lets an untrusted prover uh prove it knows a

witness satisfying some property. Yeah. So uh for example, the prover might be claiming it knows the pre-image of some output value under a hash function like I know a w that hashes to this this Y. Okay. So the the trivial proof of that statement is to just hand the witness to the verifier. You know, in this example, the verifier could then evaluate the hash on the witness itself and confirm it indeed produces the claimed output, right? And so a snark is just a proof system that's nicer uh than the trivial one for the verifier, right? So the proof should be at least shorter than the witness, right? Because the trivial proof is just the witness. We want to do better than that. And checking the proof

ideally will be faster than directly checking the witness. All right? and that directly checking the witness today I'll typically call that native execution right that's like what if there was basically no proof or the trivial proof and you just sort of you know the do the statement with no proof machinery or anything like that so that's a snark um and just to have a a picture in your head of of how snarks might work imagine the following right so um imagine a developer uh who maybe knows nothing about snarks and how they work uh writes a computer program in their favorite programming language. And this computer program I call the witness checking procedure, right? It takes as input a purported witness and just checks that

the witness satisfies the claim property. So in the example from the previous slide, it would simply evaluate like the hash function on the the input to the program and spit out the the output. Okay. So uh the way snarks could work and uh increasingly are working is uh they go through a two-step process. So first you turn that computer program into something like a circuit you know and why a circuit is just because the snark machinery kind of applies directly to uh low-level operations like the gates of a circuit you know so they don't apply directly to high level computer programs but you can first take the computer program and turn it into something like a circuit and then the snark does apply directly to the circuit so the second step is to then run the

snark on the circuit right so think of this circuit as like implementing the computer program. And so if the prover uses a snark to prove it knows a satisfying assignment to the circuit, that's like the same as proving it knew an input that the computer program would have accepted. All right, so here's the picture, right? The developer just writes this highle computer program in Rust or something. Uh this is turned into something like a circuit. uh we call the compiler from the program to the circuit the front end and then some kind of proof system is applied so that the prover can proves it and knows uh satisfying assignment to the circuit that we call the back end. All right.

So, um, as far as, uh, Snark performance today, you know, high level, the verifiers tend to be good and the provers not so much, right? So, Snark verification generally is, um, at least non-trivial, right? Like the the proof really is shorter than the witness unless the witness is like really really really really tiny. Uh, and checking the proof is much faster than like directly checking the witness. That doesn't mean there isn't major variation in verifier costs, right? So, so some snarks have proof sizes under kilobyte and others have proof sizes in the hundreds of kilobytes, right? So, there's multiple orders of magnitude variation here, but even the expensive ones for the verifier like this is still potentially way way way shorter than the size of the witness. So, the prover cost is

generally kind of the limiting factor in in snark applicability these days. Um and so at least as of uh let's say a year ago or so um the prover generally does uh about a million times more work than native execution. Right? So proving it ran the computer program correctly involves like a million times more computational work than just running the computer program with no proof. Right? Now to be clear like this overhead this millionfold overhead like it's highly amendable to parallelization. So you can throw you know many many GPUs at it and kind of drive it down but still you know a mill millionfold overheads are limiting no matter how well they paralyze right and so um an application

that you know the blockchain community uh is highly interested in today is like proving Ethereum blocks and they want to do this for a few reasons it's good for interoperability of sort of different chains it's good for generally scaling up you know the amount of work the blockchain is processing without making the validators themselves have to do more work. But generally, if you want to if you want to prove an Ethereum block today, um in you know the time people really want the proof in um you're going to need many many dozens of GPUs um and you know Ethereum wants to 100x the amount of work that would need to get proved per block over the next few years, right? So um you know generally the amount of of work that's happening

in an Ethereum block is equivalent to like a fraction of a second maybe a quarter second or something on a laptop single threaded right so you know we're talking like I don't know as little as on the order of maybe milliseconds multi-threaded or something on a laptop and yet the provers is you know taking dozens of GPUs and you know if these things don't get faster multiply that by 100 or something. Yeah. So that's where we are today. So the prover is limiting and so the the main focus of this talk um is to make the prover faster, right? Um now I do think this millionfold overhead is is falling down to 100,000 or even like 10,000. I'd go so far as to say you know the work I want to tell you about today brings it well below 100,000 and uh hopefully you know we're not too

far off from getting down to like 10,000. Now, a a quick overview of of how Snark backends are designed um before I start talking about the the new work, this twist and shout stuff. Um so, these snark backends go through like kind of a three-stage design process. Um so, the the first thing you develop is a protocol called a polomial IOP. Okay, don't don't worry about what that is yet. I'll say more about what that is in a minute. Um and then the the second stage, you design a cryptographic protocol called a polomial commitment scheme. Again, I'll tell you soon what that means. And you can put these two things together and get a succinct interactive argument, right? Where the verifier and prover actually have a kind of back and forth. Um, but our snarks we

want to just be like non-interactive, meaning, you know, it's like a fixed proof you can post on a blockchain or something like that. And so to to make the succinct interactive argument non-interactive, uh, you apply something called the fiat shamir transformation. Um, and yeah, so those those are the three steps. Okay. Um, so what is a polomial IOP? It's kind of a a funny protocol. Um, but we'll, you know, it'll make a lot more sense as I go through the the details of this talk later. Uh, but the the prover's very first message in this protocol, um, specifies a polomial. All right? And I mean like the the sort of object you learned about maybe in in middle school or high school. uh like you know a plus bx plus cx^2 plus dx

cubed you know dot dot dot plus you know x to the n right that that is an example of a polomial and the prover's first message uh you know just sends that polomial to the verifier okay now you should think of the size of this polomial like the the degree um as big right so maybe it's as as big as the circuit that the prover is claiming to know a satisfying assignment for right so we don't actually want the verifier to like read all the coeicient of this polomial because that would you know the proof would be too long that would violate the succinctness. to sickness means short proofs and fast verifiers, right? So in a polinomial IOP, the verifier is not allowed to learn this polomial in full. Okay? Instead, the verifier is only going to be given what

we call query access to the polomial. This means it can evaluate it at say just one point. So it can it can later ask, hey, I want to know the polomial at this one point R, right? And and the verifier is then going to kind of be handed that evaluation and that's the only information the verifier can ever learn about this polomial. Okay. Um and so after the prover sends this polomial to the verifier then they just engage in a standard like conversation right and at the end of that conversation the verifier you know that you know queries the the first message this big polomial at a point and has to you know kind of accept the prover's claim as valid or rejected as invalid right okay so you know just to say a little bit more about what's going

on here uh right now so typically this polomial the prover sends in the first round typically encodes the witness that the prover claims to know and you know the the the intuition is for these verifiers to be really really fast, right? They they have to kind of um do spot checks, right? So the the provers claiming to have run this big computation correctly and to have not made a single mistake in the entire computation. It's huge. Verifier doesn't have time to, you know, look at that whole thing. So it's got to do a spot check. And so what that means is we need a method to blow up like tiny differences into big differences that are easily detectable. And so that that's where the word encode comes from like polomials are really good. Two

different polomials that are not the same polomial. Um so that you know even if they disagree on one point that means they have to disagree on many points. And so yeah this polomial is like taking a witness and then sort of encoding it so that tiny differences between two witnesses blow up into easily detectable differences. And so then this uh step two of this protocol after the prover has sent the polomial what the prover is typically doing is proving that the witness encoded in the polomial is a valid one. So that that's the yes. So so step one is like I send you the encoding of the witness. You're not going to read the whole thing. You the verifier. Uh step two is I'm going to prove that the witness I sent you is actually valid.

Right. And then at the very end of step two it's like the verifier only has to turns out evaluate the encoding of the witness at one one point. Okay, that's polinomial IOP. Uh, okay. And so what is a polomial commitment scheme? Oh, so let me just mention in in general there are two classes of polomial IOPS. Uh, one class uses univariate polomials and the other uses what are called multilinear or multivariate polomials and generally speaking uh the first class is really good for verifier costs and the second class is really good for prover costs. Okay. Okay. And so naturally since my focus today is on prover time, I will be looking at multivaried polomials through throughout this talk. All right. Um now while while the the verifier costs for

the multivaried polomials are higher than the ones on unary polinomials, they're still not not that high, right? We're talking on the order of a handful of kilobytes to a few dozen kilobytes, right? So it's like you you should really only in my view be using univaried polomials if you want you know like really really tiny proofs under a kilobyte and you're willing to tolerate what's called a trusted setup and other than in that setting um you you should be targeting the multivaried polomials and and by the end of the talk hopefully I'll make a convincing case for that. >> So like in the blockchain setting what do you think is a good heristic limit on how big a proof is okay? Yeah. So the blockchain setting there there's differences uh in application because sometimes the proofs don't really have to go on chain. So like the way

Ethereum's planning on bringing in snarks into the L1 itself um the proofs won't go on chain. And then um you know I'd say several dozen kilobytes is no problem at all. uh if the proofs are going on chain now we can have a debate like what how much are we really willing to let our blockchain validators do because you know every proof has to be verified by every validator out there. Yeah. So I think it depends is my is my answer. Yeah. Yeah. >> I'm just curious can you smoothly interpolate between the one and two? >> I think you can there and there are various ways you could do it right. So you could like uh so so the >> depends on the alphabet you're using to encode the witness.

>> Yeah. And I'd also say like um so one way to do it and there there are whole papers on this but that the idea is very simple these multivaried things there's sort of one round of interaction per variable until you fiat shame right and so uh and and as you go through the interaction the instance size of like the remaining problem uh falls and falls and falls right so you could run like a few rounds of the interactive multivariate thing until the problem is small enough that you're not worried about prover time anymore and then do everything else with univariate And people have looked at stuff like that.

But I generally hope that, you know, logarithmic size proofs, you know, in the long run are going to be fine, right? Like we'll be proving like huge things and it'll all get condensed into, you know, 50 kilobytes. And, you know, if you if you got enough stuffed into the 50 kilobytes, 50 kilobytes should be fine and we shouldn't really worry about going lower than that. >> 50 kilobytes is huge, >> right? >> You know, it depends what what context we're talking about. Yeah. So, um, okay, good. And, um, okay. What is a polinomial commitment scheme? It's sort of exactly what you want to turn a polomial IOP into a succinct argument, right? And the idea is in a polomial commitment scheme like rather than sending this big polomial to the verifier, the prover just cryptographically commits to that polomial, right? And so this commitment

is typically just like I don't know 32 bytes or something. And so even though the prover only sent the 32 bytes, it's almost as if it sent the whole polomial in the sense that once the verifier gets the commitment, the prover can't change its mind about what the polomial kind of inside the commitment is. Um and then later when the verifier of the in the PIOP needs to evaluate the committed polinomial at a point. The polomial commitment scheme has to sort of let the prover give the evaluation and prove the evaluation the prover is giving is the right one. Yeah. Okay. And so you know high level there are several classes of polomial commitment schemes. Uh the first two classes here use you know the cryptography used is elliptic curve groups cryptographic groups. All right. Um the

next class uh the cryptography used is just like cryptographic hash functions. And the final class uh which is still maturing is lises. Okay. And I'll I'll say some more about you know kind of what properties of different commitment schemes are important for the particular snarks you know um I'm sort of advocating for today. Uh but yeah so there different um highle point here is just that there's a whole range of commitment schemes. They each have kind of different trade-offs between uh prover time you know proof size um verifier time and uh what kind of cryptography uh sort of the security is based on. All right. So, what what's this is sort of the end of my general overview of snark design and now I'll tell you about the specific twist and

shout work. Um, so I'll tell you kind of what twist and shout are you know what what's interesting about them and I think you know one of our main motivations for designing this twist and shout protocols uh were to include them in uh something called ZKVMs and one ZKVM called Jolt in particular. So I'll explain that. Um Twist and Shout a major benefit of them is they make really efficient something called a streaming prover. So I'll explain all the stuff. So this is like the the results like the takeaways and then finally uh if there's time I will actually tell you how twist and shout work like under the hood.

Yeah. And then then before I I get into all that let me just tell you what to expect. So you know in terms of the key technical takeaways like what I want snark designers to take out of this talk uh are the following points. So you know the first sort of is is the main point I want to make kind of every time I've ever given a talk in in my whole career which is the the key to designing fast provers uh for snarks is the something called the sum protocol okay and this is meaning multivaried polomials and using a lot of interaction in your polomial IOP and and you know that that all comes together in this beautiful result from the uh 1990 or so called the sunre protocol on top of that however uh slightly more subtle point is not all uses of the sum protocol are the same.

Like there are some you know uh you know kind of level one uses and then some like you know level three uses of the sum protocol. And in particular um in order to get the simplest and fastest snarks uh you should be using the sum protocol in a way that exploits repeated structure in in whatever you know statement the prover is proving whenever that repeated structure exists. Okay. And what the intuition here is like if I want to prove I ran a simple procedure many many many times. Okay, that is significantly easier than proving I ran some like totally unstructured procedure of the same size. Okay, and we really really need to be exploiting this to have fast and simple snarks. Okay, so

these are the two most high level takeaways. And then in terms of how we actually exploit the repeated structure. So this is a very low-level takeaway that might not make much sense until I I actually explain how twist and shout work. But uh one should embrace sparse polomials. Okay. What I mean here is like they might have say very high degree but almost all the coefficients are zero. You know the key if you're using highderee sparse polomials is to make sure the prover just never pays for the zeros. Okay. So this means you have to you know snarks have a polomial IOP and a polinomial commitment scheme. So you need to choose a commitment scheme where the prover just doesn't pay to commit to those zeros and then you need to choose a polomial IOP where the

provers you know in the work it's doing to get the polomial IOP messages for for those zeros. Okay. And um it turns out like the the best commitment schemes for committing to a lot of zeros are elliptic curve based commitment schemes and naturally the best uh polomial IOPS for avoiding paying for these zeros are some check based ones. So I will and and the combination is is especially powerful uh like all you know kind of the prevailing pre-twist and shout approach to snark design is like oh we have a a high degree sparse polomial well I can't you know I if you embrace the sparity you'll have to pay for the zeros that turns out not to be right so instead what you try to do is kind of reduce the sparse thing to a I call it a

dense thing like a lowderee thing you get rid of the zeros right and I'm saying don't get rid of them leave them there but never pay for Okay. >> And so pay here is running time of the prover when they compute the commitment or evaluate the committed to polomial >> and yeah and and on top of that when they prove that the witness encoded by the polomial is a valid one. So there's sort of three state. Yeah. There's commit there's prove the committed thing is valid and then there's reveal the one requested evaluation of the committed polinomial. All three. Yeah. Uh this may be a bit out out of scope like this raises the question for me like do we have cryptography in which like the complexity of the com like the length of the resulting commitment scheme depends on the complexity of the state statement

I want to commit to like like sure you're saying commit to zeros here is free say I wanted to commit to something which is a bit more complicated than zero but not quite is it almost free >> so we do have like these we do have commitment schemes now and you know sort of this line of work that that twist and shout are a part of sparked a out of this uh where committing to small non-zero values is still cheaper than committing to like big values. Um and then another we also have actually pretty old results like one way to avoid committing to lots of zeros is to just kind of write down where the nonzeros are and commit to that. And so that's actually an old way to like avoid paying for the zeros, but that has overheads, right? And so this is saying like don't

don't even do that. Just embrace the zeros. just don't don't pay for them. Okay. All right. And and yeah, this is very in the weeds and will make more sense later. Yeah. Okay. So those are the takeaways to expect. But now let me start telling you about shout. So shout is an example with what I call a batch evaluation argument. Um so here's the setting. So consider you know some function f. Uh let's say it takes two inputs x and y. Say they're each a b bit value. So think of B as as maybe uh 32, right? Like so m maybe F is like the prim a primitive instruction of a simple CPU, right? So if it's a 32-bit word CPU, then you know any primitive

instruction sort of takes two 32-bit inputs. Yeah. um and say that the provers is committed to you know uh t triples and the claim is that like the third element of each triple is this f evaluated at the first two elements of the triple for all of these triples you know think of this t the number triple as like a billion or something billion or trillion you know some huge number all right so this is batch evaluation I'm like claiming I the prover correctly evaluated an f at a billion different inputs okay so So the standard way of proving the statement is through circuits, right? So we would let C be a circuit computing F. We would lay you know T copies of C sort of side by

side and you know that would be a circuit computing all T copies of F and we would just prove prove that circuit. Okay. Now if you there are sort of two problems with this. So one is circuits are complicated and generally I like to avoid them if possible that you know there's a lot less surface area for bugs and things if you can just cut out the circuits. But on the performance side um yeah this is still pretty expensive. So the the fastest prover snarks we have for for circuit uh evaluation uh the prover does uh six field multiplications per gate. Okay just don't worry about you know what is a field multiplication and how expensive is a field multiplication.

You know, these snark provers is like the the simplest thing they ever do is field field operations, finite field operations. And the fastest snarks we have for circuits, it's it's about six field operations on the proverate. And you know, they're kind getting even to that is probably not not possible in general. Uh but that's kind of a lower bound on the prover cost in in any circuit based approach. Okay. Um so it turns out you can do better. Okay. As long as the size of your batch is sort of not too small. All right. Uh not too small probably means in practice at least several thousand and up. Certainly in the billions is is plenty uh to do better than this. So the idea in a batch evaluation argument is the prover will pay some kind of fixed

cost. By fixed I mean it's independent of the batch size. Okay. And then that fixed cost gets sort of amortized over the entire batch. And so there's a per evaluation cost um and and the fixed cost right and you know the intuition is you know w with the the circuit approaches they don't have any fixed cost okay but by paying some fixed cost we can lower the per evaluation cost right so as long as you set the fixed cost sort of low enough that it's much lower than the per evaluation cost you know times the number of evaluations that you know you've strictly gained from this right so it's a nameization thing right?

>> What is K? >> Sorry. So K is um >> there it is. Okay. >> Yeah, here's K. >> Got it. >> Yeah. So K is the size of the entire input space to F, right? And you might think, well, K is huge. You know, if if F takes 232 inputs, K is 2 64. You can't pay a cost of 2 to 64. And my response to that is no worries. Uh we can actually in shouts um and I'll explain a small caveat here in a second. We can have the fixed cost be a small power of K. Right? Right? So imagine like if K is 2 to 64, imagine this little C is four and then this is 2 to the 16, you know, that's way under a million. And if you have, you know, millions of copies of F, you know, who cares about a fixed cost

that's way under a million >> because, you know, it's it's dominated by the yeah the >> just on the previous slide, you you were talking about that if you just view it as a circuit, you pay the cost of six field multiplications per gate, but I know there was previous work on on data parallel circuits and some check. Yeah. What do those prior works give you? >> Yeah. So, um generally they give you um a constant factor improvement improver time. >> Oh, that's it. >> I thought there was a log maybe, but >> yeah. Uh if you're very naive um about things, um there would be a stuff would be even slower and you would actually pay a log factor in t if you're very naive. And the data parallel stuff

got rid of the log factor in T. And then if you look at the state-of-the-art stuff, the data parallel stuff for circuits is just saving you a constant. Now it's a meaningful constant. But even after that constant, you can still do better with with this stuff with the batch of values. >> Okay. >> So think of C is maybe I don't know square root of B or something like that or >> um yeah. So like in in in Jolt today, I haven't told you what Jolt is, but K would be 2 to 64. And actually, we might set C as high as eight even. Okay. Uh but no, I take that back. We set C to be four. We said two before. So, so that makes the fixed cost like 2 to 16, but in in like jolt, you'd be thinking of t as you know a billion or something.

Okay. Okay. And so, um to be clear, you cannot hope to get sublinear cost in K if f is like arbitrarily complicated. Okay. But if f has some structure to it, you can hope to get cost sublinear in K. And indeed like for everything you know I any particular function that's relevant to to this Jolt project I'll tell you about shortly uh you you can you can have C be like for whatever you want.

>> I mean for you f is literally just like primitive instructions some isa right so it's all and plus >> yeah these highly structured things. Yeah. Yeah. That's right. >> Okay. Yeah. >> Can one hope to get the sublinear dependence on t? >> No. No. Um yeah the pro I mean you just literally forget the proof you know just evaluating ft times takes times at least t yeah uh you could hope to have the prover just like evaluate ft times and do like a low order amount of work to prove um this does not achieve that okay uh I will actually give an example if I have time that does achieve something like that but it's not going through this it is related though okay all right yeah so um here's an example that is relevant to

jolt I just mentioned it. So K is 2 to the 64. T might be a billion. You should think of T as like the number of cycles you're running a CPU cycles your computer program takes to run. And then we would set set C equals 4. And so the the per evaluation cost for the prover here is basically um equivalent to like the fastest circuit based provers applied to something like a 10 gate circuit, right? And basically the point is 10 gate circuits can't really do anything other than like 10 field mult 10 finite field multiplications right so if you're doing anything that's not itself field multiplications you're going to do better by using this batch evaluation argument

okay plus you get the simplicity benefits of there being no circuit anywhere question about this >> actually I don't want to jump ahead too much but I'm curious like can you pay that setup cost once and for all and then I repeatedly prove you stuff you know every Okay. >> No. Uh well I So can you um >> I mean I mean basically like you know you have t being really large but but I'm proving you the first hundred things today and the next hundred things tomorrow. >> I see. Um so shout wouldn't give you that. I'm trying to think about other batch evaluation arguments. Um, so there there is a okay there there's some batch evaluation arguments that would push all the fixed cost into a

trusted setup phase like a uh yeah um and but then concretely the per evaluation cost is actually worse than the circuit evaluation stuff. So I would say >> your technique >> for our technique that that wouldn't work. Yeah. You got to prove everything all at once. Yeah. And so to go back to the performance speed up from skipping the circuits. So if you did take just like risk if f was just like risk five instructions I should think of that as maybe like hundreds of gates if I converted it to >> language. Yeah. Typically the way people would do this is uh they like commit to the individual bit like the 64 bits of the input and then once the bits are committed you know it's pretty easy like bitwise end would just be maybe you know

um 32 gates. Uh, but remember it's it's six field operations per gate plus it's a it's a bunch of field operations to commit to the individual bits and you add all that up and it's way more than than what I wrote here on the slide for the shout prover. Yeah. Okay. Um, okay. So intuitively what's going on here? So one I you know I I kind of already indicated that we have an economy of scale here where you know if you pay some fixed cost to like build a factory then the per co you know per product you know per item cost goes down right in ter if you pay a fixed cost it should buy you something in terms of the lower per per item cost right so uh yeah there's an economy of scale here uh but another source of intuition is the

following um the shout prover in these these batch evaluation argument prover it's not proving how it evaluated F. With circuits, the prover is proving it correctly evaluated the circuit gate by gate. That's a prescribed way of evaluating f. So the circuits are like tying the prover hands tighter. You know, the more tightly you tie the honest provers's hands, the longer it's going to take to find its way to a proof. So that's the other piece of intuition. So just a slightly different perspective on batch evaluation arguments. Um we can consider a readonly memory uh that just stores the entire evaluation table of this f, right? And then evaluations of f are just lookups into this readon memory. So people normally call batch evaluations lookup arguments. I think that's actually

confusing, right? At least in certain context, right? In the ZKVM context, they're really batch evaluation arguments, but both perspectives are useful. So I just want so here from the from the read only memory perspective, the fixed cost is in terms of the memory size. It doesn't depend on the number of reads into the memory. And then we have a per read cost. So it's just different view different terminology. All right. And so this is the terminology and view to take to compare to to twist. So we we talked about shout. So twist is a generalization of shout to readwrite memory. Okay. And and very high level you know you know imagine we have a CPU that is you know every CPU cycle let's say it does one read from from memory

from like RAM and and then one write right to memory. Okay. And so a snark for read write memory is just uh the point is to prove that the values returned by the read operations are the correct ones. Okay, what that means is right if at cycle I I read like memory cell K right the value returned by that read operation should be the value most recently written to that cell to cell K. So that's what I mean by correct read values. Yeah. And so Twist is a snark that lets you do that. the prover kind of commits to you know all of the the read and write operations and then proves that the the read operation the read values are correct.

So shout was sort of like stateless, right? It was like if you see the same f, the same xi, the same yi, it's going to be the same zi. >> Yes. >> Whereas here like zi might be different if there was a >> exactly story. >> Exactly. Yeah. Sort of like the evaluations of f are changing over time if you will. >> Yeah. >> Okay. So um yeah, maybe I'll maybe I'll skip this. You know, there's these these are some cost of twist, but I mean the point is twist is a generalization of shout to readwrite memory. Concretely, we're seeing that the the twist prover is s, you know, like maybe three-ish times faster than previous arguments for rewrite memory, um, while having significantly shorter proofs. Or if you compare twist to prior work that had the

same size proofs as twist, it's like well over an order magnitude faster. So you either win kind of a little on both proof size and prover time or a a ton on prover time while leaving proof size the same as prior work. Okay. Uh there's another major benefit to both twist and shout uh which is this streaming prover thing I briefly mentioned on the talk outline. Roughly this means that uh the prover memory usage like you know the number of gigabytes of space you need to run the prover can be kept bounded with twist and shout uh in a much nicer way than how people typically control the prover memory usage and I'll say a little bit more about that soon. Okay questions >> are you are you going to say a little bit about the ideas behind twist or

>> yes okay >> if I have time anyway. Yeah. Um, >> I guess just a high level. Is it like kind of just like shout plus a trick or is it like an equal amount of extra work >> to do to do? >> Oh, I no twist is definitely more expensive. Um, you know, per operation. >> I also mean intellectual work. >> Yeah. Yeah. In terms of how complicated the protocol is. Well, I mean one one way of putting it is like shout is just one application of sum check and twist is like three. So maybe that indicates it's like three times more complicated. But um yeah, I mean I'd say there's like two two important ideas in Twist that aren't in in shout. So let me talk about ZKVMs um and and how Twist and Shout, you know, are relevant. Um and then, you

know, if I still have time, I have no idea how much time has passed. I'm doing okay. I'll give you I I'll dive into the weeds of of how they work. So ZKVMs are snarks that let a prover prove it correctly ran a computer program like cycle by cycle by cycle. So what what do virtual machine is basically like a simple CPU? Yeah. And uh what what do CPUs do? They repeatedly call like fetch decode execute and they do like reads and writes to memory. Yeah. I mean this is like you know kind of day one of computer architecture. This is what CPUs do. And a ZKVM is just letting a prover correctly ran a CPU like a computer program specified as like machine code for that CPU, you know, step by step by step. Okay, so you know this is like one

way to realize the picture I had at the start of the talk of like the developer writes in whatever a computer program or whatever high level language it wants, right? One could then you know use like an off-the-shelf compiler to compile that computer program to you know machine code for your favorite CPU and then you can uh you know you're apply the the snark prover uh to prove it ran that computer program correctly uh for that CPU. Okay. And the the main challenges here are approver overhead and also these are like just very complicated protocols and so they're definitely still rife with bugs and so simplicity is a major concern here. This you know no matter how simple how much progress we make in

simplicity here there's there's still going to be a major concern about bugs. So we we better make them as simple as we can. All right. So two big trends in ZKVM design right now. um one is a focus on a particular uh CPU architecture called Risk 5. Um why why Risk 5? So um so so Risk 5 was designed outside of the Snark community. It's it's an open- source architecture from the computer architecture community. Uh it's kind of the simplest architecture that the computer architecture community has actually, you know, designed and and pushed out into deployment. And by some miracle, it's actually pretty friendly for snark proving. Okay. And I'd say, well, why is it friendly to snark? This

is a controversial statement, by the way. A lot of people don't agree with me, but for every primitive risk 5 instruction is directly amendable to to shout, for example, right? So um you know the people who designed risk 5 were not trying to make every primitive instruction you know provable with one application of a batch evaluation argument but they succeeded in doing that anyway by by accident. Okay. Um and generally if we you know it's it's kind of the simplest uh ISA that was not designed specifically to be snark friendly. And that fact is important because there's all this tooling for it that already exists that we can now make use of if we design our snarks to prove this ISA and not some some other one that was, you know, designed specific to

snarks. Okay. Uh so so that's one trend. And so the the ZKVMs I want to tell you about today, they they focus on risk 5. Again, there's nothing that special about risk 5 other than these these two points right here. Um and then I've already talked about a focus on on proving Ethereum blocks. And the main thing I want to reason I bring that up is um I I want to mention this this billion cycle counts that I kind of already brought up in in the context of shout where is that coming from? It's because proving one Ethereum block today that's about roughly equivalent to a billion risk five cycles. Okay. So just have that cycle count in mind uh as I present you know kind of numbers in the rest of the talk.

>> The native computation is a billion cycles. >> Yes. Yes. Yeah. So if you want to prove Ethereum blocks with a risk 5 ZKVM, you'll want the prover to prove about a billion cycles. Yeah. Okay. So what what is Jolt? >> Just one thing I want to get straight in my mind like the um well first of all when you say that it's ZK friendly, you just mean that the entire you know CPU can be implemented in a small number of gates. >> Well, so there sort of no not really gates but I mean um I mean many things. One of which is uh in order to prove correct ex execution of each primitive instruction you you can directly remember I said the shout the shout prover to get this k to the one over c for c greater than one needs some structure in in f well all the risk five

primitive instructions have that structure >> I see >> uh okay because my my next question was also something um when you look at proving correctness of an instruction you don't want to reveal what instruction was executed so aren't your inputs actually much larger than 64 bits >> so so firstly for forget about ZK for now. Um but um so I'll say that >> maybe that's the answer. Maybe that's what the answer. >> Well, but I you can make you know these risk 5 ZKVMs uh Jolt in particular Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z Z ZK without much fuss as well. So um I there's not like a big head.

>> So maybe the way to think about it is you could just add ZK on at the end to most of these snarks. >> Yeah. Yeah. You just Yeah. Exactly. Yeah. Okay. So, so Jolt is a ZKVN that's sort of uniquely designed around the sum check protocol being like the main workhorse of the proof machinery and batch evaluation arguments rather than circuits to simplify things and speed things up. Okay, so this makes it uh significantly uh simpler than other ZKVMs. Now this is of course a little bit subjective but you you know you can look at metrics like lines of code and you know Jolt Jolt is significantly you know simpler by those metrics. We'll also see, you know, Jolt gets rid of the need for recursion in a way that other other ZKVMs, you know, need to use recursion.

And I think snark rec snark recursion means proving, you know, proofs. I think that's a major surface area for complications and bugs. Um, and and we're, you know, uh, I assert I claim we have state-of-the-art uh, performance on on CPUs right now by by a lot. Um, and this claim will be made, you know, more precise and concrete as the implementation is is fully finished. So you know take it with whatever grain of salt you'd like at at the moment. Um okay so the main uh insight or philosophy behind Jolt is that VM execution any VM but risk 5 for example is sort of the epitome of repeated structure and computation right you're the VM is just doing fetch decode execute over and over and over again right and

outside of that it's just doing reads and writes to memory and that's also you know repeat it's doing the same thing over and over and over again and so we should be exploiting that and so using batch evaluation arguments and and you know twist that's exactly what what we're trying to do and so that that makes us both um simpler and faster than than alternatives. All right. So, how does Jolt work at a high level? Well, CPUs generally have four components, right? So, you have readwrite memory. So, that's RAM and and registers. You have the program bite code. That's just telling you what program you're running.

>> Can you give us some intuition why a circuit-based approach cannot take advantage of repeated subcircuits? >> So, you can, but you'll still be more and you should, but you'll still be more expensive than the batch evaluation argument. And the intuition there is uh I had a slide I would say one is the circuit based approaches don't pay like a fixed cost um that gets amortized over all the evaluations. Uh they sort of have the same cost per gate whether it's you know one copy or or many copies. Um yeah wave my hands there a little bit.

And then secondly um there is uh the you know the circuits the provers is proving it evaluated the function you care about in a particular way going gate by gate through a circuit. There's the verifier doesn't care. The verifier just wants the right output. It doesn't care how the prover went from the input to the output. So maybe that's the best piece of intuition is uh there's no need to force the prover to go gate bygate through the circuit. All the circuit based things do. Okay. So yeah. So the the computer program is you know specified by what's called bte code that kind of tells you every cycle like what is the next thing the computer program has to do and then you know once it figures out what's the next thing it has to do it does the thing right it like executes that instruction so this is

CPUs and so jolt mirrors the CPUs right and so we prove you know RAM and registers with twist right and we prove the other stuff with shout and now it's kind of nice we have both perspectives on batch evaluation versus look lookups come in right uh you know reads into bite code that's lookups that's read only memory naturally primitive instruction execution that's batch evaluation right it's the same 20 primitive instructions like a billion times so it's kind of nice you need both perspectives to design jolt okay so that that's jolt and then you do need to make sure right like batch evaluation you have a you know the prover is committed to all of the inputs in in the batch and they're just completely independent And

there's no enforcement of relationships between the inputs. So like how do you make sure that shout is fed the right inputs to the primitive instructions. Uh there is a circuit does come up. We can't completely get rid of circuits. Our circuit is you know what we call R1CS. The details don't matter. Uh but and we do apply a snark for circuits to that. Okay. Now that snark for this this circuit has repeated structure and we do exploit the repeated structure and we get like a 2x speed up by exploiting the repeated structure. roughly this is >> that's the part that has consistency across the four different components.

>> Yeah. >> Okay. >> Yeah. Yeah. So you can either think of this as sort of the glue between the four different components or alternatively you could think of this as doing like the real work but assuming like every read to memory returns the right value but then it it lets twist do that check and you know assuming every primitive instruction outputs the right value but it lets shout do that check. So yeah, you can either think of this as kind of weak and just the glue or you could think of it as doing the real work but like offloading a whole bunch of other checks to you know these co-processors or whatever. Yeah, and just about this circuit. So we have it down to like 26 constraints per risk five cycle you know it's like 26 gates in a circuit or something and it's the

same 26 gates per cycle, right? So we exploit all that repeated structure to the max in our in our circuit you know component. Okay. So, and and and just highlighting simplicity here, right? Like other ZKVMs like for every primitive instruction, they will write a circuit implementing that primitive instruction and the verifier needs to know that circuit and if there's any bug in the circuit, security is potentially out the window. Right? In in Jolt, the only thing the verifier needs to know about each primitive instruction is I haven't introduced what this means yet, but uh it needs to know just how to evaluate the multilinear extension of that function. And so here is one of the more complicated risk five primitive instructions like set less than unsign and there's no you know this is the entire description of the function as

far as the jolt verifier is concerned right this is you know orders of magnitude simpler than writing down a circuit for this thing okay so I think that you know forget performance I would I would advocate for these batch evaluation arguments on the simplicity side alone okay so the implementation of twist and shot within jolt is almost complete previously we were using other you know arguments for read only memory and read write memory called lasso and spice. Um with twist and shout uh we you know the the proofs you know will be about 50 kilobytes and you could bring this lower at the cost of a little bit extra prover time.

And I I expect the prover will be proving about a million risk five cycles per second on like a high-end laptop that's like parallelized. So if you don't paralyze it, I'd say it's like probably you know 10x faster parallelized on the laptop than unparalleled. Okay. Okay. Now to be clear this number and again it's expected number we'll see in you know a few days if it holds up but you know have a lot of confidence it's in the right ballpark at least this number is if you're proving like a million cycle 100 million cycles and up and the jolt is like it's about economies of scale right the more cycles you prove the faster you can prove each cycle okay so I think for small statements um jolt will still be state-of-the-art but it won't be as fast as a million cycles per second or

whatever it might be two 2x slower or something like So could you connect that back a while ago? You talked about how this is like easily amendable to parallelization and so you could chop it up but bunch of GPUs. So is there some tension there between >> kind of needing a lower bound on >> I don't no I don't think there's a tension you're worried that like the fixed cost can't be parallelized or something. >> No, I'm just saying like can here can you only parallelize to a certain extent because like at the base case of your parallelization you have this lower bound on how long you need the computation to be. >> Oh I see. Um no. So typically the computations run natively uh you actually run that sequentially just because we don't know how to paralyze arbitrary computation and then once you have that once you're done that run

everything else is sort of proving and all of that is maximally paralyzable more or less. >> Got it. >> So you're saying like the Yeah. So the VM computation is sequential and that you can chop up as much as you want and then the prover computation on each >> thing can be highly paralyzed including in this right. >> Yes. Yes. Okay. >> Yeah. So, you know, there might because our techniques are so different than the existing ZKVMs, uh, you know, we might run into some headaches that other people don't, but you know, broadly speaking, all of these ZKVMs are massively parallelizable. Um, and that's why I I generally focus when I try to design fast on just total prover work because we'll be able to paralyze that work roughly equally no matter how we do things. Okay. And coming to total prover

work, right? Remember I said like you know a year ago it was typically a millionfold extra work for the prover okay so I'm predicting you know soon expectations in red just because the implementation not quite done uh that the total job prover work will be about 40,000x so you know 20 times less than a million right and there are actually two ways to see that this is reasonable so one is if you know a laptop today runs at like four billion cycles per like four gigahertz like that's what you know your MacBook runs at that's its clock speed. And so if the Joel prover can prove 100,000 cycles per second single threaded, well that ratio 4 billion to 100,000 is like 40,000.

Yeah, it's like if you're spending 40,000 CPU cycles to prove one risk five cycle, right? And then analytically you can just like count the number of field multiplications that Joel prover does per cycle comes out to about 500 or so. And we know that each field multiplication in the fields we use is about 80 CPU cycles. Lo and behold, oh look, it matches up exactly 40,000 fold cycle, 40,000 cycles to prove one five cycle. So we've been guided this whole time by cycle counts. And you know, a lot of the community for some reason thinks you just can't predict how these snark provers will perform until you build it and run it. And this has been the exact opposite of our experience.

Like cycle counts have, you know, remarkably accurately predicted prover performance to date. But one other thing that's interesting here is when you say 500 field multiplications per cycle, I mean you're part of that is you're asserting it's basically workload independent, right? It doesn't matter what program it is that you're proving correct that >> that's right. There's there is some variation between workloads in prover time but it's not much. It's not much. So something like like twist gets uh more efficient per memory access if the accesses are local. Uh but it's not like 10x more efficient. it's, you know, 2x and and then twist is only, you know, a relatively small component of jolts and also you the cycles that don't access memory, you don't pay anything. And so

you add that all up and it's like all these variations are tiny. Yeah. >> I'm just out of curiosity, where does the 256 bit requirement come in? >> Yeah, that's because we're using these elliptic curve commitment schemes today and so we're stuck with 256-bit fields. Yeah. Yeah. And maybe I can say, you know um hashing based commitment schemes have a reputation as being much faster than curve-based ones. That reputation is largely due to the fact that you don't need a 256-bit field. Uh, and indeed like one operation in like a 31 bit field might be 30 to 100 times faster than one operation 256-bit field. But if you use the right techniques, all of this, you know, you can do like

literally 10,000 times fewer field operations over the bigger field. And that more than offsets the 30 to 100x slowdown of each field field up, you know, but future directions for Jolt is to try to reduce this 256 bits by moving away from lipic curs. And then we'll just get get even faster, right? I just quickly say I actually expect that that jolt as a ZKVM will will be faster for the prover than popular snarks for circuits applied to like hand optimized circuits not all snarks for circuits but some of the popular ones they tend to be popular the verifier costs are low means the prover cost is pretty high so if you you know yeah so I'm comparing kind of the slowest prover circuits to Jolt which

has no circuits or whatever this will still surprise people right and roughly so you Look at like plank which is a popular snark for circuits and the plank prover does something like 800 field operations per gate in the circuit right the jolt prover is doing like about the same number of field operations same order magnitude per risk five cycle okay right so you know um unless your computation is is literally already a circuit uh there's no overhead to kind of turning it into a circuit you're probably going to be better off using jolt perhaps perhaps by quite a lot, right? Um, you know, you would think basically one gate of a circuit is much simpler than one risk five cycle and yet the prover time uh is about the

same between jolt and and some of the circuit based snarks. So this will come as a surprise to to many people. You think hand optimized circuits, well that goes handinhand with speed, right? Because you're making the circuit nice and small through through hard hard work, hard labor. uh but in fact the repeated structure in the VM execution can be leveraged to more than offset the um uh you know all of the work that goes into optimizing these circuits, right? And so yeah, the the intuition is uh you know repeated leveraging repeated structure uh more than offsets the overhead that comes from imposing the repeated structure, right? The VM abstraction imposes repeated structure.

Yes, that's extra work. The prover is proving it did, but it's highly structured extra work and so you don't actually pay that much for it. All right. Um, yeah. So, I'm running out of time. So, maybe let me just mention that the way snarks control prover memory today is they'll it's like you you cannot directly prove a billion cycles all at once, right? Your prover will need like many terabytes of space. Okay? So, what people will do is they will take the billion cycles and they'll break it up into smaller pieces. and they'll prove each piece kind of se independently, right? So now you have one proof per piece, right? And like your prover space wasn't that big because the prover dealt with kind of one or two pieces at a

time, right? But now you have a lot of proofs. So what you do is you pro you know you aggre you recursively aggregate the proofs. So you spit out a final proof that's attesting to knowledge of the individual proofs. Okay. Um, I mean this works, but it introduces a lot of overhead and it's like very complicated because proving you know a proof means taking a snark verifier which is a pretty complicated procedure and it turning that into a circuit and then proving you know a satisfying assignment to that circuit. It's all very complicated and quite a bit of overhead I think and so um I mean just in in a sentence uh you know twist and shout unlock the ability to keep the prover space under control without doing this you know breaking things up into pieces

and applying you know proofs of proofs okay and I I won't I won't say too much about why other than twist and shout exploits sparse polomials and fast proving for sparse polomials like go somehow magically goes hand in and with um what we call the streaming prover that small space proving without without recursion okay it's a little difficult to say exactly why um so I won't that just uh but I do think this is a big unlock for snark simplicity as well as just for like security we don't actually understand pro the security of proofs of proofs very well I do want to say a little bit about how twist and shot work so uh one thing I want to say is just these curve-based commitment schemes they have free commitments to

zeros okay this is important. This is how you commit to to sparse polomials quickly. And typically the curve based commitment schemes if you're committing to you know like think of these these xis as coefficients of your polomial. Okay. And typically the commitment is taking a bunch of group elements and raising them you know the i one to the power x i and then sort of you know munching them all together. All right. The point is if x i is zero it literally doesn't change this group product. So the prover can just filter the zeros out. All right. So that's kind of an amazing thing the you know to commit to a giant vector where you only pay for the non-zeros. All right. So we do have some curve based commitments where you know you don't pay for the zeros. The verifier costs are very nice. Uh it's

transparent if you you know uh don't worry about what that means you know and and computing the evaluation proofs is is also very fast. Okay. So kind of everything you you might want you kind of really don't pay much for zeros anywhere. That's kind of the point here. So that's the that's the background on commitment schemes. quickly tell you some background on the sum protocol you know on the polinomial IOP side so if I give you any function whose domain is uh 01 to the L so domain is bits several L bits there is a unique uh multilinear polomial that means degree one in each variable uh that extends the the function uh over the boolean domain so what here's the picture here's the function

over the boolean domain here's the evaluation table of multi-linear extension polomial right so if I you know the polomial I can evaluate anywhere in the whole field right and so it's kind of that's why they say extension you're extending the domain from the boolean domain to the the whole field and this polomial has degree one in each variable okay so it's it's nice and low degree okay um so the sum protocol is sort of a magical technique you know I certainly don't have time to tell you how it works today that lets the verifier force the prover to sum up many evaluations of a single multivaried polomial.

Okay, so you know we're summing we want to sum up, you know, G's evaluations over all boolean inputs, right? The verifier could sort of do this work on its own by evaluating G at each of the two to the L boolean inputs and just, you know, summing up the results, but the sum protocol forces the prover to do that work for the verifier. And as far as the verifier is concerned, the verifier just winds up evaluating G at a single point, right? Right. So from the verifier's perspective, it reduces like 2 to the L evaluations of G to a single evaluation of G. Um and you know generally speaking we you know it depends on structure in in G. But typically we can make the provers's time proportional to the number of non-zero terms in the sum right. So if I'm

computing the sum it's like the zeros don't change the sum. I don't I don't have to pay any attention to the zero terms. And we can kind of keep that property round by round over the course of the protocol. So the prover just never pays for the zero terms. Okay. So that's why sumche protocol is the key tool to prove sparse polomials that you know statements about them quickly. Okay. Um so shout is almost identical to an old interactive proof for a problem called counting triangles uh from 2013 paper. So I'm just going to I'm going to run through this protocol super fast and then I'm going to run through shout equally fast and then I'll then I'll maybe call it. Okay. Okay, so counting triangles um kind of a funny problem not not you know too relevant in the cryptographic context but somehow shows

the right techniques. All right. So the input is the adjacy matrix of a graph. Right? So the jith entry of this matrix is telling you like is vertex I in your graph connected to vertex J in your graph. Right? Think like friends on Facebook. You know is John friends with Tim or not? Right? That's what um the entries of A are telling you. And the goal is to sum up over all you know like triples of vertices in the graph of uh you know are are all three vertices in the triple connected to each other. Right? Kabir, John and Tim all pair-wise friends. Yeah. Okay. Um and so yeah, but this is this is the same as uh you know sorry rather than summing over triples you can sum over pairs. So this three

should be a two. That's a typo. Um and you can ask you know is is the square of the adjacency matrix have that entry equal to one and also the unsquared adjacency matrix has a one there. Right? So that's like uh you know a a squar of of J is is is counting the number of mutual friends I and J have in common and then if I and J are also friends then you've counted triangles. Yeah, here's the protocol for it. So you know we we view a uh as a function over the boolean domain and I did have I thought I had a picture of this before may no it's a yeah so you know if this is our our matrix now now this is not a boolean valued matrix but don't worry about it.

You know, we just think of this as the evaluation table of a function over the boolean domain, right? So like uh you know the the the first entry of the matrix is just the evaluation at the all zeros input. The next entry of the matrix is you know all zeros but end in a one, right? It's just an you know we interpret the matrix as the evaluation table of this function. This function has a unique multilinear extension polomial which I you know I denote with a a tilda over it. And um we're going to we're going to look at the polomial G. Okay, which is a product of two multi-linear extensions. So so one one term in the product is just the multi-linear extension of the input matrix. Okay, and the other term is the multilinear extension of the squared input matrix. So now if we apply the sum

check protocol to sum up G's evaluations, that's actually giving us the number of triangles. Right? This sum is the same as this sum, right? Right? We're just summing over all entries of, you know, all pairs J of of a squig time AI. Now here, here's why, you know, we care about extensions, right? If you this sum like the extensions are defined over the whole field, but sum check just sums them over the boolean hyper cube, which is where we have control of their values. Okay. Okay. So, so you know that's almost the whole protocol. Okay.

But at the end of the sum check protocol the verifier has to evaluate the polomial being summed at a at one point. Now that requires evaluating both you know the modular extension of a at that point and of a the mont extension of a squ. Okay. Now the evaluation of a because that's just like the input to the problem. Actually the verifier can get that on its own let's say fast enough you know as fast as you can hope. Okay. Uh so the interesting thing is this a squ you know the verifier doesn't know a^ squ right the verifier is only handed a and computing a squ is as hard as just counting the number triangles in the graph directly so we cannot possibly have the verifier evaluate its multilinear extension at a point. It's

it just doesn't know a^ squ much less a squ multiar extension in order to evaluate it at a point. So the solution is to use a second invocation of the sum protocol to force the prover to to give this evaluation to the verifier. Okay. Um, so here's just a fact. This was observed in a paper mine from 2013. Um, the evaluation of a squared multi-linear extension at a point has this nice expression. Okay. And this is this is pretty easy to see. It's it's uh you just check that the right hand side is multilinear in in R1 and R2. The point we're evaluating a squ extension at. and you confirm that um you know if R1 and R2 live in the Boolean hyper cube the

left hand side and right hand side agree with each other and those two facts together tell you that they're actually the same polomial because the hyper cube is an interpolating set for multilinear polomials right any two multiar polinomials that agree over the hyper cube agree they're the same polomial I know I'm moving very fast here but so in order to get the verifier a squ at at this point we just apply the sum protocol a second time okay and at the end of that sum protocol the verifier just has to evaluate a twiddle at at two points and that you know now we're good now we're done okay so that that is the protocol for counting triangles and I call this super efficient I think I mentioned at some point you would so the prover here once it knows a squ right it actually does uh a linear amount of

extra work to prove a square you know that everything is correct and that extra work is you know linear we don't think you anyone can comput a square in linear time so that's actually the best you can hope for is a low order amount of of extra work to prove things. You almost can never do it. This is one of the few examples you can. All right, I know I moved super fast through that, but that is uh counting triangles. And I think there's there's one the the main reason I I presented this other than we'll see extreme similarities to um shout is this a squ thing is interesting. Um I I call this well we this is now called a virtual polomial.

So this notion has kind of been around for years but was recently coined by uh Diamond and Posen. This is a polomial that we can kind of the verifier can kind of act like you know it has access to this query access to this polomial even though it it doesn't really. It's like when it needs to get the evaluation of this polomial it's just going to invoke some check again to reduce you know that evaluation to an evaluation of something it does have access to. So it's virtual. It's like it the verifier pretends it has access even though it doesn't and then it's okay.

All right. So shout remember with shout um I'll use the perspective of you know uh reads read reads into a readon memory. So the the provers is committed to t uh addresses and uh wants to prove that a bunch of you know that that each read returns an associated value. Wants to prove the values are correct. And a little a little bit a thing that's a little funny here is within shout these addresses are committed in what's called one hot format. Okay. So that means if the memory has size capital K right each address is actually a length K vector and that length K vector has exactly one one at the at at at the location that's

being read right. Um so in general if we're doing you know t reads into into the memory then you know the uh you know we have this function ra for read address that takes as input like an address and which read operation we're talking about. So J is like the read operation you know the cycle and k is like the address. So ra kj spits out one if the j operation does a read to address k spits out zero otherwise. >> Okay. I should think of K as like two to the capital B like >> Yeah. Yeah. For Yeah. Think of capital K as 2 to 64 or something. Yeah. Okay. So this RA thing it's it's huge, right?

Like if we're doing a billion reads into memory size 2 to the 64. RA sort of has size like 2 to the 94 or something, right? Because it's K it's size K* T. K is 2 to 64. T is like 2 to the 30, right? RA is huge, but it's very sparse, right? because uh for every you know one of the t values of J there's only one associated one entry. Okay. So we can commit to t quickly with the right commitment sche to to ra quickly with the right commitment scheme because the right commitment schemes only pay for the non non-zeros. Now of course I'm I'm waving the the the size two to the 94 does come in somewhere but not in commitment time. It comes in elsewhere. Uh so let's just let's just ignore that and just say you know

committing's fast. Okay. Now here's where we get uh to to similarity with the um counting triangles protocol. Um the point of shout is well it virtualizes RV right so it's like RV is this polomial that like the jolt verifier is ultimately going to want to evaluate at a random point but um you know it doesn't know RV so how's it going to get the evaluation? And so we you know the the point of shout is just to give the verifier that evaluation. Okay. And so um we can we can write you know the arth read value as just this sum. And this this looks you know exactly like the matrix multiplication sum right. It's uh you know the the result of the ar operation is you you

sum over all memory addresses of is the R3 operation hitting that memory address. RA will spit out one if yes and zero if no. and and you know if if yes tell me what the the value stored at that memory cell is right and so you know this holds sort of for every you know relevant value of R and therefore it holds over the whole field you know because the right hand side is multilinear and two multilinear things that are yeah so so all shout is is you know when the verifier wants the read values multiar extension at a random point you just apply some check to compute this quantity Okay, another way of saying it is like

matrix multiplication and and and shout it's both they're both just about like repeated inner products, right? Matrix multiplication is like each entry of the product matrix is an inner product of you know two vectors in the input matrix. And similarly here you know each each read value the J the result of the J read value is just an inner product between you know the J array vector and the memory right so re repeated inner products you know leverage the repeated structure you're done okay that's that's the point all right so um that's basically shouts uh let me just see I'm going to wrap up here now you know so the prover committed to this RA thing you know huge

but sparse so that was all fast. Uh we can't trust the prover to you know make sure RA is one hot and so we do have to check that. Okay. And um you know RA has size K * T. And so that's K * T constraints. And you might be worried that um we can't allow the prover to have runtime proportional to K* T. We really want runtime like order T. And so uh despite the fact that there are k* t constraints, the fact that ra is so sparse means we never pay for you know anything but the t you know the t constraints that aren't just every you know ra kj is zero. Um so I'll I'll skip you know the

details since I'm way over time but basically in shout the prover commits to RA computes the sum check messages in in sort of this you know core sum check also there's a separate sum check to prove the committed thing is one hot um and finally produces the evaluation proof okay and you know I sort of you know the commitment is fast because you only pay for the nonzeros these uh two sum check things are fast because you only pay for the non-zeros and then the evaluation proof proof is uh basically fast because Dory has fast evaluation proofs and you kind of just evaluate the polomial and the prover doesn't do too much else extra work. the fact that uh now that's a little bit of a lie and that's a that's one reason you know Jolt

gets kind of faster for bigger cycle counts right it's like uh Dory itself sort of similar to to shout kind of has a sizable fixed cost if you will it's kind of slow at small instance sizes the evaluation proofs but as you get to bigger and bigger instance sizes the evaluation proofs get kind of cheaper and cheaper as a fraction of the total prover work so yeah so I'm lot you know I'm waving my hands a little bit here But basically this evaluation proof is is also very fast and the the the bigger the the you know number of lookups we're proving the the faster the evaluation proof. Okay. So that yeah that's it and uh again the the main takeaways are um embrace the sparity.

Some check will ensure you never pay for the zeros and the right commitment schemes will also ensure you never pay for the zero. So together you never pay for the zeros and you never got hurt by the sparity. And once you embrace the spar, you know, the commit to RA, which is big but sparse, it everything is easy then, right? The point of RA um was to to make, you know, each each correctness check just an inner product, nice and low degree, and you know, all this stuff. So your life is easy for snarks when everything is sparse. You just have to figure out how to not pay for the zeros. And this is how you don't pay for the zeros. So, okay, I'll I'll stop here. Thanks for letting me go over um

and if you have any questions, feel free to ask. >> So, the original point of this counting triangles thing was just to go from cubic to quadratic if you have like a prover to help you out basically or >> Yeah. Um that's right. I mean, the verifier could just solve it the problem on its own in matrix multiplication time. Um yeah, another benefit though um is if you care >> that's your paper the counting triangles one or >> Yeah. Yeah. or the mation multiplication protocol. Yeah. Yeah. That's uh yeah 2013 paper. Um another motivation there was um the verifier in the interactive proof can be streaming can process the

input in like a single pass um whereas you cannot exactly count the triangles without uh a prover without explicitly storing the whole input >> that's in the semi-streaming model or >> I think you can't you just literally need all the edges to store them all. Um yeah so that that was another motivation. Yeah. Yeah. That's it. >> 12 years later. >> Yeah. It's funny. We Yeah. So we, you know, this paper was sort of looking at very simple problems that arise like in the streaming literature or like very very very simple circuits just to I don't know have something simple and concrete to look at. Uh and then all of these very simple things turned to be

turned out to be at the very core of snark proving. It's like the you know snarks reduced these wildly complicated statements like I ran a VM for T cycles to just like repeated inner products and so by studying the simplest possible problems well actually that was all we needed to design the the snarks in the end. >> Is there like a lot of work on like problems that we know that require either a lot of passes or a lot of memory but now that you go to the proofer verifier setting you can have a verifier which is only like one pass. >> Yeah. I mean in general you can kind of take like any interactive proof or snark and the verifier is just like directly streaming.

>> Oh wow. Okay. >> Now if you but you know there's this a lot of papers on this topic and but no one's ever really cared that much but you know I I like the topic. So I'll add if you want to study in very fine grain way like how many rounds do you need versus how much space does a streaming verifier need? Well now there's like very interesting questions. Actually, that's I developed a lot of intuition personally for the Sunche protocol by just looking at those, you know, trade-off questions in the streaming setting. >> In your overview slide, you had registers and RAM and that's just because that's how risk 5 works, right? >> Yeah. So, we could have everything together in one memory checking instance. Um, now twist is like especially fast for tiny memories. I sort of skipped over this slide. Um, and

so the original reason we separated, you know, one twist instance for registers and one for RAM is because there's only 32 registers and we're like twist proving is going to be so fast for that. You know, I I haven't thought carefully about whether it would be almost as fast if we combined them. But I think there are almost no downsides to separating them. So >> So you basically mirror the what's happening in the in the CPU, right? That you want something fast, small, and then the RAMs that are >> Yeah. Yeah. It's a it's sort of it's an interesting point um you make the parallels between kind of the way people have designed CPUs and the way you would want to design a CPU to prove its execution quickly is almost miraculously deep right like all of these things that

seem like they shouldn't match up in fact they do now there are still gaps right like you know um I think a register access in a real CPU is maybe I don't know 200 times faster than an access to RAM or something and we don't have a 200 100fold gap in proving time but we do have a significant gap. By the way before Twist there was like no G. It's like you know tiny memory you don't benefit at all from it. So over time the cost profiles of snark provers and the cost profiles of CPUs have converged a lot. They're not the same. Uh yeah >> so it could be that there's like an optimal compiler that's better for snarks.

>> Exactly. And so my take in general over time has been if we try to optimize the VMs for snark proving now we'll actually do the opposite because the snarks have not finished getting better. >> Okay. And moreover as they get better they convert get closer in cost profile to real CPUs but they're never going to match. And so at some point we probably should stop uh you know using the existing compilers and optimize them to the snarks. The worry is you do it too soon. We might be getting to that point.

I don't know. Um you know my preference in general is simplicity and that you know not introducing more surface area for bugs over squeezing out every last bit of performance. So I don't it's it's not out of the question that we never should change the compilers for CPUs. Um even though we actually care about snark proving not CPU execution that's that is still a possibility. >> Yeah. In the context of general uh batch evaluation you mentioned that like batch evaluation tightens the hands of the prover less than circuits. >> Does this have any security implications?

>> Yeah it's an interesting question. Uh no I mean at least not in um the current context for using these things. It's just, you know, the verifier does not care how the prover figured out what the output of of, you know, risk 5 primitive instruction was as long as it spits out the the right output. And in a sense, you know, the the VMs themselves, you know, the primitive instruction means you just magically get handed the right output or something, right? Like uh um so there's no security implications because the, you know, security only cares about that the output is right. Um you could imag you know you could imagine other contexts where you you do really really really want the prover to go from input to output um in a prescribed way. You know there's also a

meta question right like uh the ZKVM right why when we use shout we're not prescribing each cycle how the prover goes you know from input to primitive instruction to output but we are prescribing that the prover does evaluate the VM cycle by cycle by cycle right and of course like these things people are doing like pre they call pre-ompiles I won't I won't ramble too long about it those are efforts to avoid that and to go outside of the VM abstraction and yeah I mean in some sense they're they're moving uh you know spiritually more towards shout they're tying the prover's hands less tightly by letting it uh not do the cycle by cycle VM thing but the way they're letting the prover go outside of the VM abstraction today goes through circuits right so you're sort of you

know out of the fryer into the frying pan you're tireing your the prover's hands in a different way okay so yeah good question I'll separate all right thank you