ZK13: Twist and Shout: The Next Era of Jolt - Michael Zhu

Transcript

[Music] Hi everyone, I'm Michael. I'm a research engineer at A16Z crypto and today I'll be talking about twist and shout uh two new memory checking techniques authored by Shrimasetti and Justin Thaylor and how they fit into the Jolt uh road map. Um oh I realize I don't have the clicker. Okay. Are you looking for the clicker? Yep. Sorry. Cable. Um, some quick disclosures I'm obligated to include here. Uh, yeah. So, what is Jolt? Uh, fortunately, I was preceded by two other talks about uh, ZKVM. So, I don't have to explain what that is, but

what sets Jolt apart from its peers is is that it's uniquely designed around sum check and lookup arguments. Hence the uh, backy just one lookup table. Um, this makes Jolt fast and relatively simple. It achieves state-of-the-art performance on CPU and we have GPU acceleration in progress and by minimizing the amount of low-level circuit code that's written um it makes it easier to audit and formally verify. Uh so to make the simplicity point concrete uh so this is basically all the verifier needs to know for the risk 5 less than instruction. Um put another way you can kind of think of this as the uh marginal audit surface of one instruction in Jolt. As you can see,

it's just a handful of lines of regular Rust. No low-level circuitry uh required. Pictorially, this is roughly what the Jolt architecture looks like. So, in the center, we have this small R1CS instance, which we prove using Spartan, and it serves as sort of the glue between the other components in Jolt. So, we perform lookups into the bite code, uh fetching each instruction based on the current program counter. uh we prove that using uh the lasso lookup argument currently. Similarly, we do instruct instruction execution using lookups and for read write memory uh we use the spice memory checking argument.

Um so we use that for both registers and uh loads and stores to RAM. So now with twist and shout this highle architecture remains the same. We're just swapping out uh spice for twist as the memory checking argument and lasso for shout as the lookup argument. Um in a bit more detail, what are twist and shout? So twist is a new readr memory checking uh technique while shout is a new readonly memory checking technique or also known as a lookup argument. Uh what makes them unique is that they don't require any permutation checks. So that means no grand products, no read solen fingerprinting, uh no

multi-et hashing required. Um all you need is some check. They use large but sparse polinomials leveraging the fact that zeros are basically free for the prover as long as you use an elliptic curve-based commitment scheme. And this results in a faster prover and shorter proofs. Uh we'll see some preliminary performance numbers uh in a later slide. Um at a more philosophical level uh we see that this um with twist and shout the prover cost profile kind of starts to converge towards more hardware-like performance characteristics. Specifically we see that register accesses are faster to prove than RAM accesses and that uh memory accesses are also faster with

more memory locality. So now I'm going to give a very high level sketch of what I see as the key insight of shout the so-called meth method of one hot addressing. So here we have a uh lookup table val um and for each access we're going to represent the query as this one hot vector. So if three is the element being accessed we have a one at that index and zero is everywhere else. Here RA A stands for read address, RV stands for read value which contains the uh the lookup output at each step. So in the next step we're accessing this eight and then that one and then this one. And so with these RA and RV

polinomials we have this very nice sum checkable expression here which conceptually all it's saying is that the value read at time step t is given by uh the index that was accessed and the value of the lookup table at that index. Uh and this is nice because ra is extremely uh efficient to commit to given that it's all uh zeros and ones. Uh in fact you're only committing to one bit per cycle basically. uh and also this sum check is uh efficiently provable using some techniques described in the twist and shout paper. Uh one caveat here is that we still need to prove that ra is indeed uh one hot. Uh but for that I'll again

defer the details to the paper. Now for a highle uh sketch of twist or rather the key inside of twist which is the method of increments. So now instead of a static lookup table val we have uh val which can be both read from and written to. So you can think of these as like eight registers uh initialized to all zeros here. And so every time we write to one of these registers we're going to represent that as um instead of the right value they increment or delta. So here we're uh incrementing that register by eight. And then at the next cycle, we're going to increment this other register by three. And then we're going to decrement that eight by two, giving

us six in that register. And once again, this gives us a very nice uh sum check expression here. Conceptually, all this is saying is uh the value in register K at time step t is given by uh the sum of the increments for that res register up to that time step t. So here the LT polinomial is basically just the multilinear extension encoding that bit of pseudo code uh which is if t prime is less than t it's one otherwise it's zero. Uh so for an example here val of 52 um is just the sum of those two increments and um similarly val of 33 is

the sum of those three increments. Right? So everyone's favorite topic performance. Um so with the caveat that these numbers are based on some preliminary uh benchmarking in a still work in progress branch in the Jolt repo. Um specifically this uh branch does not yet integrate a polinomial commitment scheme. So we're just comparing some checks to some checks here. So some checks before twist and shout and some checks after twist and shout. Um so we can expect these numbers to shift around a little bit but um this is giving a rough uh idea of what to expect in terms of proof size.

We see that the jolt proofs go from about 240 kilobytes down to 45 kilobytes which is a 5.3x reduction. Uh prover time the big headline number here is is that instruction execution lookups get 7.3 times faster using shout instead of lasso. uh we see a about uh 2.6x reduction in prover time for readwrite memory and bite code lookups and sort of incidentally we got a 2.2x speed up on Spartan. Uh this is due to the fact that we were able to eliminate some of the R1cs inputs and constraints uh when moving to twist and shout. And the Jolt prover also uses

about 3.3 times less memory at peak. Um and all this is with uh more optimizations still in progress. So what's next for Jolt after twist and shout? Um the main thing on our minds is streaming which is a method of uh controlling prover memory usage without relying on uh snark recursion. Um so currently the Jolt prover uh uses memory that scales linearly with the length of the execution trace being proven. And um other ZKVMs as you may have just seen in in the previous talks address this using continuations um which is basically breaking the trace into chunks or shards proving each shard and then recursively proving those.

We're pursuing an alternative approach uh based on streaming algorithms. Um in the interest of time I'm going to zoom through this a little bit. So this is roughly what continuations look like. Um, and compare that to streaming where we're going to make a sort of streaming pass over the execution trace or rather multiple passes uh generating the trace sort of on the fly. Um, so that we only have to keep a small portion of the trace in memory at any given point. Um, and there are some ways to speed this up. uh for example we can take some checkpoints of the VM state on the first serial pass in generating the

trace and then in subsequent passes we can uh generate the trace in parallel. Um so the benefits of the streaming approach uh first and foremost is simplicity and security. So no snark recursion means that there's no need to implement the verifier as a circuit. Uh there's no need to introduce some sort of recursion VM or other proof system. And um also the security of snark recursion is thought to be on sort of shakier theoretical footing than non-recursive snarks. In terms of performance, we avoid the uh potentially costly snark recursion step. And also uh specifically for twist and shout, we expect the prover to to perform best on larger

trace lengths. So we don't necessarily want to break the trace into small shards as we would do with continuations. Um and finally, while we're excited about this streaming approach, we acknowledge that there are certain benefits of the continuations approach as well. So it's important to note that um streaming is also complimentary with continuations. So eventually we hope to get the best of both worlds. And that's all I have. Thank you. And um happy to take [Applause] questions. And I've got the mic if anyone would like to ask Michael a question. Do we have any questions for Michael? All

right. In lasso, it was required that it was MLE structured and decomposible. Do you know if in the new work it still needs both of those things or Sorry, I missed part of that question. Yeah. So in the original lasso paper or the original Joel paper, the arguments you were doing need to be MLE structured and also decomposible. If there weren't those two things, you couldn't use it anymore. Um with this newer work, do you know if you still need both of those things or is this just one? Like can you not have the decomposability property? Yeah, so the the lookup tables still need to be MLE structured. Um and there's also a notion of decomposibility similar but not exactly the same as AASO. It's this uh something called prefix suffix decomposability which is described in actually not the twist and

shout paper but um a different paper proving CPU executions in small space. Awesome. Do we have any more questions? One more. Great. You had mentioned there's some advantages to twist and shout if this uh system is instantiated over an elliptic curve based commitment scheme. Uh to to what extent could you apply these to a non-homorphic commitment scheme to a non homorphic commitment? Yeah. Okay. So the main property out of um elliptic curve based commitment schemes that we need uh well one of the main properties is is

that zeros are free to commit to. So as you can see like the RA polinomial here is mostly zeros. Um so that's the main one. In terms of uh homorphism I I think you could get away without um just we we're actually not committing to that many polinomials total. I think it's something on on the order of like 16 or 18. Um so you know you'd be paying like that constant factor of overhead on the um proofs. But yeah, currently we're just looking at using um elliptic curve based commitment schemes. Awesome. Uh we have time for one more question if anyone else has a question. All right, let's give Michael

a hand. Oh.