Anna Rose (00:00:27): This week I chat with Ariel Gabizon. Ariel walks me through his SNARK trilogy concept, starting with Jens Groth work in 2010, and moving through all of the different chapters of the history of SNARKs. He highlights what he sees as the key moments and breakthroughs of the last 10 years and while the exact boundaries of the three chapters are kind of defined as we went, it was a really interesting way to think about the history of SNARKs. I also welcome you to share the way you would break down the SNARK trilogy, especially if it's different from the way that we did it. We wrap up on his new work around, look up tables, and then chat about 1 emerging research streams that have folding schemes and sum-check protocols. Now, before we kick off, I do want to direct you to the ZK Jobs board. There you'll find jobs from top teams working in ZK. So if you're looking for your next job opportunity, be sure to check it out. And if you're a team looking to find great talent, be sure to add your job to the jobs board as well. I've added the link in the show notes now. Tanya will share a little bit about this week's sponsor Tanya (00:01:29): Anoma’s first fractal instance, Namada, is launching soon! Namada is a proof-of-stake L1 for interchain asset-agnostic privacy. Namada natively interoperates with fast-finality chains via IBC and with Ethereum via a trustless two-way bridge. For privacy, Namada deploys an upgraded version of the multi-asset shielded pool (MASP) circuit that allows all assets (fungible and non-fungible) to share a common shielded set – this removes the size limits of the anonymity set and provides the best privacy guarantees possible for every user in the multichain.The MASP circuit's latest update enables shielded set rewards directly in the shielded set, a novel feature that funds privacy as a public good. Follow Namada on twitter @namada for more information and join the community on Discord discord.gg/namada. Thanks again Anoma Anna Rose (00:02:22): Today, I'm here with Ariel Gabizon. Welcome back to the show, Ariel. Ariel Gabizon (00:02:27): Thank you. Yeah, so nice being here, 3 times! In this exclusive club of the 3-timers. Anna Rose (00:02:34): The 3 timers. Ariel Gabizon (00:02:35): Yeah. Anna Rose (00:02:35): Actually, I was just thinking before we started, the last time we got to record in person was in Split, Croatia, and here we are just down the coastline in Montenegro. It's kind of funny, we only seem to record in the Balkans in person. I don't know what's up. We've seen each other at conferences and stuff, but yeah Ariel Gabizon (00:02:54): Whenever there's a pandemic ending meet again in the Balkans. Anna Rose (00:02:57): There you go. Ariel Gabizon (00:02:58): Record another episode Anna Rose (00:02:59): But yeah, so it's great to actually get a chance to do this in person once again. And I know we had spoken a few weeks ago at the zkSummit, just afterwards, you were telling me that you were working on this like new generation of pairing-based protocols, and it would be a really good time to have you back on. And so that's what we're going to talk about today. Ariel Gabizon (00:03:19): Yeah, absolutely. So I have this sort of cheesy Star Wars metaphor Anna Rose (00:03:25): Okay. Ariel Gabizon (00:03:25): Or analogy, or I don't know the difference between metaphors and analogies. Anna Rose (00:03:30): Okay. Ariel Gabizon (00:03:31): Of the last decade or so of pairing-based SNARKs. Anna Rose (00:03:35): So, so this is the history all the way to the new work that you're doing. Ariel Gabizon (00:03:40): The history of pairing-based SNARKs all the way to the new work that I'm working on now. Anna Rose (00:03:46): Does it have a name the new one? Or is this still like untitled? Ariel Gabizon (00:03:51): Well, I'm going to title it, but let me okay. Let me title, let me start Anna Rose (00:03:55): We don't want to give it away. Okay. Okay. Ariel Gabizon (00:03:56): I have just wait a few minutes. Anna Rose (00:03:56): Yeah. Ariel Gabizon (00:03:56): So here's how I've been describing it lately. The pairing-based SNARKs trilogy. So the first chapter that began in 2010, a new hope. Just for SNARKs, not for like life or humankind or anything. Anna Rose (00:03:56): Okay. Ariel Gabizon (00:03:56): Was started by Jens Groth in 2010 in this paper where he was saying look, we have these wonderful things called pairings and back then SNARKs were exclusively constructed by these relatively complicated things called PCPs. These very powerful, complicated things that, you know, tangent that's what led to Starkware. Anna Rose (00:03:56): Oh. Ariel Gabizon (00:03:56): And he was saying, look, we have these really cool things called pairings, and if we use them, we can get SNARKs with constant proof length that we like very much. We can not use the random Oracle model something practitioners don't care about but theoreticians liked very much, and like an anecdote that Jens Groth tells that this, this paper was rejected three or four times from conferences. Anna Rose (00:05:14): But this is not the Groth16 paper? Ariel Gabizon (00:05:18): Right. This is not, I'll Anna Rose (00:05:19): Okay. This is the Groth10? Ariel Gabizon (00:05:21): This is the Groth10. Anna Rose (00:05:22): Okay. I don't think I know this one. Ariel Gabizon (00:05:23): So Jens, he's both the starter and the finisher of this first chapter. Anna Rose (00:05:31): Interesting. Ariel Gabizon (00:05:31): So basically this chapter started with Groth10. The reason by the way, this paper, I think was not accepted first. It uses this powerful cryptographic assumption, the deep power knowledge-of-exponent that then people were like uncomfortable with. But now we're just using all the time, we're using even something stronger. The Algebraic Group Model, which is actually a strengthening of the deep power of exponent. Anna Rose (00:05:58): Were they scared of it because they didn't know if it was secure? Or was it just like novel? Ariel Gabizon (00:06:03): I mean, right. That's a matter of I think both. Right? Anna Rose (00:06:08): Okay. Ariel Gabizon (00:06:09): It was both novel and like pretty much all crypto assumptions. We don't know if it's secure Anna Rose (00:06:15): Until it gets broken. Ariel Gabizon (00:06:17): And well, here is a very good argument against these types of assumptions and also against the Algebraic Group Model. This assumption is what's called a non-falsifiable assumption. So a discreet log assumption you can demonstrate its false. You can like give an algorithm that computes discreet logs. These knowledge assumptions, there's no like, easy way to demonstrate even that they're false. They're standard cryptographic assumptions about show saying, you know, this thing is hard. You can't do it. Knowledge assumptions are more like saying you can do this, but the only way you can do it is like, in this way. So it's kind of harder to refute them. Anna Rose (00:07:08): Okay. Ariel Gabizon (00:07:08): Yeah, anyway but also from the practitioners side aside, Groth10 had quadratic proof length which made it not too practical. (00:07:19): But then the pivotal moment in this first chapter was the GGPR work that introduced QAPs that were then sort of recasted as R1CSs and this was really the pivotal moment because it was saying, yeah, using just pairings, no, not this heavy machinery of the PCPs and also no random oracles that theoreticians don't like we can get almost practical SNARKs. And the GGPR approach was refined first in the Pinocchio paper. Finally leading to the paper we all know and love Groth16. So, Jens Groth also started this chapter and ended it by giving the sort of the most optimized version of what you can do in the GGPR approach. So this was, this was very nice. Anna Rose (00:08:08): This is still book 1, right? Ariel Gabizon (00:08:11): This is chapter 1. Anna Rose (00:08:11): Chapter 1. Ariel Gabizon (00:08:12): Chapter 1, yes. Anna Rose (00:08:13): Yeah, I'm mixing up the mythologies here. Okay. The chapter one. Ariel Gabizon (00:08:17): What? Harry Potter? Anna Rose (00:08:18): Yeah. I think or something else. Ariel Gabizon (00:08:20): Yeah. If once we get to seven like chapters, like in 2040, I'll have a Harry Potter, Anna Rose (00:08:28): I would normally, so I actually, my story of all times is Buffy, so it'd actually be season one. But anyway. Ariel Gabizon (00:08:35): All right. Anna Rose (00:08:37): Different. Ariel Gabizon (00:08:37): So, season 1 Anna Rose (00:08:38): No, I think, we'll stick with yours. Chapter 1. Ariel Gabizon (00:08:42): This chapter, yeah. Anna Rose (00:08:43): Okay. So at the end of chapter one is Groth16. Ariel Gabizon (00:08:47): This is Groth16. Anna Rose (00:08:48): Tell me, let's summarize that. Like, this became, like the standard, every team that was going to be building with SNARKs would sort of tap into this. Would you say like, most libraries started to be built around this tooling? Ariel Gabizon (00:09:03): Well yes and no. I mean, one reason maybe why no, was that the time, you know, from Groth16 to when chapter 2 begin was not too large, but yes, Groth16, I guess it became a standard. Definitely but yeah, with a caveat that, you know, so right, there was this very annoying thing that you had to do a trusted setup per circuit. Anna Rose (00:09:32): Oh, yes. Ariel Gabizon (00:09:33): So this is the big thing that makes protocols from this first chapter not totally convenient to use in practice. So you have to like, really, right. It's like you want to, you're thinking of seeing a movie if it's easy, you knows, just go see it, even if it's not great. But you really have to want to use SNARKs. You're only going to use Groth16 if you are really sure. You want to do it. It's not like I don't have, you know, other plans because doing the trusted set up per circuit is a huge right. It's a huge logistical nightmare, Anna Rose (00:10:08): Which, and this in a way also maybe explains like going to a project you used to be part of Zcash, when like the one SNARK the trusted setup would happen, and then that was the SNARK that you were going to be using until another trusted setup would happen, so that you could deploy a new one. Right. It was such a monumental feat to get one of these things launched that you could only do that, I don't know, once a year. Twice a year. You couldn't do it like, all the time Ariel Gabizon (00:10:37): Yeah. If you want to encourage, like committed monogamous relationships with SNARKs, the trusted setup per circuit has, maybe it has, it's not like I feel like, you know, changing this constraint today, I don't feel like this circuit fits me anymore. Like, yeah, Anna Rose (00:10:53): No, you're committed. You've really, you're in it Ariel Gabizon (00:10:55): You've really committed a few months in advance to the last like, little equation. You're really like, yeah, this till death do us part, or and yes, but definitely people were looking for, you know something more convenient. And, you know, this leads us to the second chapter. The polynomial commitment scheme strikes back. So what this chapter sort of said is, well, pairings are great but if instead of trying to do everything with the pairing, we just limit our use of pairings to this one component, a polynomial commitment scheme, then suddenly we have a lot more flexibility. We can suddenly get a trusted setup that is universal. So one trusted setup per all circuits of a certain size bound, this was the largest thing. And a second thing that has become very, you know, big, is that this exactly gives us the ability to do custom gates. Whereas in the first chapter, we were confined to restricted to R1CS very inherently. The second chapter allows us to do custom gates basically. Anna Rose (00:12:20): Can't you do custom gates in R1CS, or is it just not a smart combination? Ariel Gabizon (00:12:27): Well, you know, I can give you any gate or a gate is basically usually an equation. So you could always break that equation to a sequence of R1CS equations. Anna Rose (00:12:38): Ah Ariel Gabizon (00:12:38): Right but sort of your unit of cost is how many R1CS equations is it going to take you to represent this equation? Anna Rose (00:12:48): So if you were to do something like, I mean, a custom gate in R1CS is kind of possible, but would be clunky and slow, and you'd have to do many layers, I guess. Like you only have the +'s and the x's, although I think you do, you also have only, what is it, add multiplication in addition in the polynomial commitment ones? Or do you have more, does like when you talk about custom gates, basically, I'm just wondering if it, like, what does it open up? Ariel Gabizon (00:13:15): Well, it's really, it's all about the constants. It's all about constants here. So the sort of the R1CS equation is always a sum x's a sum = a 3rd sum. Anna Rose (00:13:28): Okay. Ariel Gabizon (00:13:29): So, you know, for one thing, if I want to, I have now something of degree 3, like X times Y times Z equals W. I definitely cannot represent that in 1 R1CS equation. Anna Rose (00:13:46): Ah, I see Ariel Gabizon (00:13:46): Right. Because I only have degree 2 in R1CS, so I'm going to have to break it down to 2 equations. Anna Rose (00:13:56): But you moved, so instead though, you moved away from the R1CS model towards PLONKish arithmetization, is this what takes over kind of from it? Ariel Gabizon (00:14:06): Yeah. Anna Rose (00:14:06): I hope I'm not front running the story a little, oops. Ariel Gabizon (00:14:10): No and so PLONKish arithmetization is, yeah, is basically a big part of this second, the second chapter I think people use the term PLONKish arithmetization for a combination of custom gates and what's called lookups. Anna Rose (00:14:38): And did the original PLONK, because I'm thinking chapter 2, does it center around PLONK in a way? Ariel Gabizon (00:14:45): Well, I would say actually the, I mean, PLONK is a big part of chapter 2 and it has become, you know, maybe like Groth16 became the standard for chapter 1, PLONK became the standard for chapter 2. But I would say the like GGPR was the pivotal moment of chapter 1. I would say the Sonic paper was the pivotal moment of chapter 2. I mean, at least for me personally, you know, when I saw the Sonic paper, it opened my eyes. It was like, okay, we have suddenly a lot more flexibility here. Anna Rose (00:15:23): Yeah that idea of the single trusted setup, and then you wait for like, until you're ready to do another one to make any sort of changes. That was corrected a little bit by Sonic's, right? Ariel Gabizon (00:15:35): Yes. Anna Rose (00:15:36): All of a sudden you could adjust, you could update this universal circuits, you could do something without having to run a full trusted setup each time. Ariel Gabizon (00:15:45): Yeah. Yeah. So the SNARKs of this second generation of the second chapter, they have a setup that is, the setup is universal and updateable. So it's one trusted setup per all circuits of a certain size bound Anna Rose (00:16:02): Like a top bound? Ariel Gabizon (00:16:03): Like a top bound. Yeah. Anna Rose (00:16:04): Would you often, like, do you still have to do a trusted setup, but do you do it as as large as you could? Ariel Gabizon (00:16:08): Yeah. Anna Rose (00:16:08): So you could cover a lot of large? Ariel Gabizon (00:16:10): You choose a large size, and then after you've done that, you can make SNARKs for any circuit up to that size. Anna Rose (00:16:17): Got it. Right. Ariel Gabizon (00:16:18): As a side note, there is this work that maybe is sort of between these chapters. This GKMMM work. It was the first work with the universal and updateable SNARK, but it didn't fall into this template of a polynomial commitment scheme and a polynomial IOP, like the SNARKs of the second chapter. And this is really a tangent Anna Rose (00:16:41): This was like the bonus on the DVD right? Bonus special feature Ariel Gabizon (00:16:49): Yeah, you have to buy the extended edition, this was like chapter 1.5. Anna Rose (00:16:53): Okay. Ariel Gabizon (00:16:53): So this, it did give you a universal setup. It had some efficiency like problems, but there it was really a setup per circuit size rather than size bound. Anna Rose (00:17:03): I see. Ariel Gabizon (00:17:04): Yeah. But, but that's really a side note. Yeah. And also the second property of these setups that we have now is that they're also updateable meaning that say, okay, you don't trust anyone that's participated so far at any point, someone can just add their randomness sort of to the setup. Anna Rose (00:17:24): To the trusted setup. Although even in practice though, weren't the trusted setup still with the universal ones kind of gated like there was an end point? You would start the trusted setup and you would end the trusted setup before it launches right? Like when you talk about adding randomness after, like you could, but do most of these circuits actually allow that? Ariel Gabizon (00:17:45): Well, I think in most production projects, it's true that there has been an end point. It's more maybe hypothetical that, I mean, it's not like the projects that are in production now Anna Rose (00:17:59): They allow you to do it foever Ariel Gabizon (00:18:00): do it months, then once in two months, they are like we're adding this person to the yeah. There is one exception. There's really nice project Perpetual Powers of Tau that, I think Anna Rose (00:18:13): That's from the EF I think right? Ariel Gabizon (00:18:14): I think it's from the EF at Koh Wei Jie if I'm saying his name right. He was, I think the main Anna Rose (00:18:20): Although I understand that that's just like an ongoing trusted setup to always kind of spit out these, what is it, SRSs like these so that you can, if you are launching a project and want the trusted setup phenomenon, you can just use that right? Isn't it sort of like, it's meant to sort of almost like a public good for SNARK projects so that they don't have to run their own setups. That's what I've always understood that as. It's like ongoing forever. So you can just kind of click in. But I guess it probably is limited too. Like, it's whatever, like upper bound, it's set for itself and if your SNARK is higher, then you'd still have to run your own. Ariel Gabizon (00:18:57): Yeah, exactly. Yeah. I mean, they set a relatively high bound, like, it's I think it's 2 to the 27 which I don't know if there's any circuits in practice that maybe the Filecoin circuit is a little larger than theirs. Anna Rose (00:19:10): I think wasn't the Plumo one huge? Ariel Gabizon (00:19:12): Oh, Plumo. Anna Rose (00:19:12): I worked on that one. Ariel Gabizon (00:19:13): Oh, right. So you know Anna Rose (00:19:15): As far as I know, that was like a massive one Ariel Gabizon (00:19:17): Right, right. I don't know the size of that. Yeah. Maybe it exceeds the Anna Rose (00:19:21): But I'm not sure if Kobi was here, he could report. Ariel Gabizon (00:19:25): Yeah. Anna Rose (00:19:26): But, okay. So going from Sonics what's the next step in the movie? Ariel Gabizon (00:19:33): In chapter 2 or in chapter 3? Anna Rose (00:19:35): Chapter 2? Not chapter 3 yet. Ariel Gabizon (00:19:36): Okay. Anna Rose (00:19:37): Because like, is there anything between Sonics and PLONK? Ariel Gabizon (00:19:40): Is there anything in between? Anna Rose (00:19:42): Wasn't like Marlin kind of between Ariel Gabizon (00:19:44): I think PLONK and Marlin came out at a very similar time. Anna Rose (00:19:44): Okay. Ariel Gabizon (00:19:44): So, yeah so Sonic was the, I would say the pivotal moment of this chapter. Anna Rose (00:19:44): Yeah. But Sonic was a relatively comp, especially if you wanted a succinct verifier, like a fast verifier, Sonic was a relatively complicated and yeah. And basically a half a year later, I think, or eight months later than, you know, there was efforts to simplify it. And I think the main two papers that came out of us at similar time were PLONK and Marlin. Ariel Gabizon (00:19:44): Got it. I think, yeah, PLONK came out a month before on Eprint, maybe, but similar time. Anna Rose (00:20:28): Okay. They were both presented, I think at zkSummit4, I think that was when, that was the summer the SNARKtember Ariel Gabizon (00:20:35): SNARKtember Anna Rose (00:20:35): 2019 Ariel Gabizon (00:20:37): Yeah, yeah. I think Plonk, Marlin, Halo, Dark Anna Rose (00:20:41): Was Halo1 already. I think Halo1 was a little later, wasn't it? I thought that was like, just after it was a little, Ariel Gabizon (00:20:45): I mean, actually, I mean I think PLONK was first put on Eprint in August, but Anna Rose (00:20:45): Oh. Ariel Gabizon (00:20:45): But it is, you know, SNARKtember, we like to say it all happened in SNARKtember. Anna Rose (00:20:58): Okay, and then zkSummit was, I think in September or October of that year. So it was like right after, Ariel Gabizon (00:21:03): Oh, that was a good zkSummit. Anna Rose (00:21:05): It was a small one, but a great one, like kind of legend. It was at a coworking space. Ariel Gabizon (00:21:09): Quality, not quantity Anna Rose (00:21:11): Hundred people. Ariel Gabizon (00:21:12): 20 people in a basement. Anna Rose (00:21:14): Yeah, well, a hundred people. But yeah, it was pretty small. Ariel Gabizon (00:21:16): All right. Anna Rose (00:21:17): But, okay. So but I'm, now, I'm really curious, like, where does chapter 2 end? Because since, like, so you mentioned Sonic, PLONK, Marlin came out around the same time, but PLONK is very much, at least like a second beat in that movie. Like, the world changed a little bit when PLONK came out I think. Ariel Gabizon (00:21:37): Well, the I mean, where the analogies not perfect is that the chapters overlap. Anna Rose (00:21:43): Oh. Ariel Gabizon (00:21:43): And most people are, are still watching chapter 2. Anna Rose (00:21:47): Okay. Ariel Gabizon (00:21:47): Anh I'm saying to them, Hey, there's this really cool chapter 3 but they're not it's mostly just me and a few people Anna Rose (00:21:54): Okay. So chapter 2 maybe was broken into 2 parts because it was too long. Production said we need to cut it in two, let's say the part, wait, chapter 2, part 1 ends with the creation of PLONK. What happens after that? Ariel Gabizon (00:22:10): What happens after that? Anna Rose (00:22:12): Because you have the lookups, you mentioned the lookup stuff. PLONKish arithmetization has the custom gates, but also this lookup table. Ariel Gabizon (00:22:20): Yes. Anna Rose (00:22:21): And you're saying like PLONK 1, the paper was the introduction, the real kind of define more custom gates. Was that the big innovation? Ariel Gabizon (00:22:30): I would say it like this, the PLONK, the biggest simplification there was the permutation argument and also the arithmetization in PLONK based on selector polynomials, which by the way was not new. We were going to at some point get this whole, right, this whole subject of attribution. So the, the arithmetization of PLONK is simpler than it is in Sonic. It's not totally original. There are a lot of people attribute it to PLONK. It's this selector based arithmetization that it's already appears in this GKR paper called Interactive Proof for Muggles. One of the first sum-check papers I mean practical sum-check papers. The sum-check is from like 1990. Yeah. But the paper that, so sort of what happened was PLONK went back to this actually older arithmetization based on selector polynomials. So custom gates were not there explicitly. It was a little hinted, like in, it was slightly hinted how, oh, if you play around with these selectors, you can get like a bullion gate. You can get where selector polynomial, where like custom gates really like, were like explicitly like showed was in, in the Turbo-PLONK paper. Anna Rose (00:23:53): Ah Ariel Gabizon (00:23:53): It not, it's it was like officially a proposal to ZKProofs. So, but there, but you can think of it as a Turbo-PLONK paper. Anna Rose (00:24:03): Okay. Okay. Ariel Gabizon (00:24:04): Yeah. So that's where really the custom gates and their generality were yeah, were introduced. Anna Rose (00:24:09): And then you did the lookup stuff, though, the plookup, Ariel Gabizon (00:24:12): Right and half a year later we came we came with plookup. Yes. Anna Rose (00:24:18): Well, I want to continue with your analogy. Where do you want to go with the story? Ariel Gabizon (00:24:23): Well actually, I was going to go to chapter 3, but you saying that, you know, maybe does, is chapter 2 so long that do you need 2 parts Anna Rose (00:24:32): You need a 2.2 Ariel Gabizon (00:24:33): So I would say, wait, is the second one 2.0 and 2.1 Anna Rose (00:24:39): No, it's 2.1. Well, it's because it's like part 1. So it's chapter 2, part 1 ends with PLONK. Ariel Gabizon (00:24:47): Yes. Anna Rose (00:24:48): And then chapter 2, part 2. So chapter starts with all of the things that add to PLONK. Ariel Gabizon (00:24:54): So I would say I mean, these are not like Anna Rose (00:24:57): I don't know why I'm sort of like using this. I like this analogy. I'm going with it Ariel Gabizon (00:25:02): Let's spend 20 minutes talking if we should start counting from 0 or 1 Anna Rose (00:25:08): No we're going to do part 1, part 2, keep it like movie style Ariel Gabizon (00:25:11): And of course there's a lot of overlapping. because in a sense, chapter 2.2, as I'm going to define it now actually starts with Halo. That was already in SNARKtember. Anna Rose (00:25:21): Yes. Ariel Gabizon (00:25:21): But I would say chapter 2.2 is the whole subject of aggregation. Anna Rose (00:25:28): Okay Ariel Gabizon (00:25:29): The whole thing of like the classical SNARK scenario is you have 1 circuit, you're doing 1 proof for and you want to optimize that. You want to make the prover fast, the verifier fast, the proof small. But usually it looks like the real scenario is you have a lot of proofs of the same circuit. Anna Rose (00:25:54): Ah, all the same, but many of them Ariel Gabizon (00:25:56): All the same, but many of them. So right. So this can happen in a roll-up where you have a thousand, 10,000 client proofs, and now you want to prove that all these client proofs are correct. Maybe this sort of happens in like a, a recursively verified blockchain like Mina, where you're at every block, you're doing the same proof where the thing you're proving is a statement like Anna Rose (00:26:27): I proved the previous thing Ariel Gabizon (00:26:30): I proved the previous thing and the previous blocks are the, I checked that all the previous blocks, their proof was correct. I checked the proof of the current block. And here's like a, Anna Rose (00:26:42): A a new proof Ariel Gabizon (00:26:42): Here's a new proof Anna Rose (00:26:45): Yeah. So it's that's actually, when you say aggregation, I immediately thought like, how does that relate to recursion? Is recursion a form of aggregation? Or when you say aggregation, do you mean somewhere else there's aggregation happening? Ariel Gabizon (00:26:58): Well, I mean, I, by the word aggregation I mean, I don't know if it's the, maybe you could also look at a more general term like amortization but when I say aggregation, I just think okay. Of this scenario that what, we don't have 1 proof for 1 circuit. We have 10,000 proofs of one circuit. What's the best way to do that given that that's our task. Anna Rose (00:27:29): Yeah. And it could be through recursion, one after another or batching, and then recursive proof or these like newer ways of aggregating. Ariel Gabizon (00:27:40): Right, right and also part of the, part of the scenario here is we have usually as we have asymmetric resources, right? We have, for example, in a roll-up, we have weak client machines and one stronger machine that doesn't mind making more computation. Right. So, so then, you know, this scenario is a little different. And the, you know, the considerations are a little different. Yeah and I would say recursion is the most straightforward thing you can do in this scenario. So yeah. So recursion is saying, okay, do your proof and also like prove inside your proof that like the previous proofs were totally correct. But then especially in this context where you have maybe one stronger machine and many weaker machines, people started thinking, and I mean this happened before in simple scenarios, but maybe the paper that brought this most to like to highlight this was the Halo paper is like saying, well, I mean our end goal is to verify, say these 10,000 proofs, but maybe it's an overkill of doing 10,000 steps where in step i, I fully verify the i minus 1 proof, or the 1 to i minus 1 proofs. (00:29:12): Maybe we can, yeah, we can delay, you know, like if we look at the total work needed to verify these 10 thousand, because like straightforward, like straight vanilla recursion to verify 10,000 proofs and put that in one proof, you're doing a full verification inside a circuit 10,000 times. Anna Rose (00:29:34): Okay. Ariel Gabizon (00:29:35): So, yeah. So what I think Halo highlighted was saying, okay, if our end goal is to verify these 10,000 proofs, maybe there's a way to do that where the total work is smaller. Anna Rose (00:29:47): And did they just like hash them together? Like, could you just somehow combine them and not have to do each one? Ariel Gabizon (00:29:56): Well, so yeah. So exactly. So that's kind of what people are trying to do. Anna Rose (00:30:02): Maybe hashing is the wrong word here, but like, they combine them basically. Ariel Gabizon (00:30:06): Right? Right and here, yeah. So that's a basic idea. Can we just sort of combine somehow the proofs and delay the actual proving to an end stage where also hopefully a more powerful machine is doing whatever is needed in this end stage. Anna Rose (00:30:29): And here, I mean, the term that I think, and I don't know if it was in the original Halo paper, but I know like at least what's been emerging is it's, this is the folding, right? Ariel Gabizon (00:30:40): So Anna Rose (00:30:40): Or folding just another form of accumulation. Ariel Gabizon (00:30:44): So I myself, I'm not a hundred percent sure on the distinctions between the different terms when people define them formally but the terms that have been used for this kind of I guess I need to choose a word to use this kind of aggregation or amortization. People have used terms like accumulation, split accumulation, aggregation and folding. I'm not sure myself of the subtle subtleties of how people define these formally. I think of them as similar. Anna Rose (00:31:20): I think I will be doing an episode really soon, probably just on that, because I'm curious too. So just a teaser for a future one. We'll figure it out. Ariel Gabizon (00:31:29): Yeah. Well, here, I mean, this is a rabbit hole or rabbit hole is maybe not the word, but this is a long topic, including Nova. So I don't know if you want get into it now Anna Rose (00:31:41): No I want to talk about that later. Ariel Gabizon (00:31:42): Should we go to chapter 3? Anna Rose (00:31:43): Yeah. So I want to talk about that later because I mean, one of the things I tweeted this, like, I was watching Justin kind of like Nova pill you, and then I heard you got sum-check pilled but I think we should talk about that after, because I want to continue on this story that leads us to basically this new generation that you've been working on. Right? So the pairing-based protocols Ariel Gabizon (00:32:03): So chapter 3, the return of the pairing Anna Rose (00:32:06): Wait, had the pairing disappeared in chapter 2? Ariel Gabizon (00:32:10): Well, it wasn't totally disappeared, but it was exiled to the land of where you only do polynomial commitments and you're not allowed to be involved in anything else. Anna Rose (00:32:23): Okay. Ariel Gabizon (00:32:24): Because people are afraid that if they let the pairing get involved in something else, they'll lose the universal setup. So it was exiled to polynomial commitment land maybe. Anna Rose (00:32:36): Got it. Okay. So this is the return of the pairing. Ariel Gabizon (00:32:38): The return of the pairing. Anna Rose (00:32:39): Wow. Ariel Gabizon (00:32:40): So chapter 3 that, as I see it started with a work that was very, like it was significant for me to see it. it really shifted like what I've been doing in the last almost year this work called Caulk Anna Rose (00:32:55): Yes. Ariel Gabizon (00:32:56): And I'll say a few words about that, but in general, I would say this chapter is about finding a middle ground in terms of, okay, we don't have to do everything with a pairing because then, for example, we might lose the universality of the setup, which we really, that would be a total deal breaker. But I mean, maybe let's find a middle ground. Maybe there's things besides the polynomial commitment scheme where the pairing gives us leverage that we don't get from a generic polynomial commitment scheme. And Caulk was the first paper that yeah, that really highlighted this. So Anna Rose (00:33:41): We did actually, we did an episode with Mary and I know, I'm going to try to, I'll dig that up and add it in the show notes because I know that that was recorded after the Caulk paper. I'm pretty sure we talked about it in there too. But yeah, what was it in? So like, and I always think of Caulk in the lookup table lookup argument context. Ariel Gabizon (00:33:59): Yes. Anna Rose (00:33:59): Is that correct to do? Ariel Gabizon (00:34:01): That's totally correct. So yeah, so here yeah, we should talk a few minutes about lookups. So, so lookups yeah. As part of chapter 2 were have been very significant to SNARKs, right? Lookups say, well, instead of explicitly in the circuit computing or checking with a lot of equations, some relation between the two witnesses, let's just pre-compute a table of legal input output values, say of some function. And then just devise a protocol that can check that say two witness values, A B appear, appear as a pair is a tuple in this table. Anna Rose (00:34:41): Yeah. Ariel Gabizon (00:34:41): So this has been hugely impactful. Anna Rose (00:34:45): I guess what this did, and actually we also, we have a whiteboard sessions with Mary as well that I'm going to also put in the show notes where we talk about this. But it just, it seems to have made, like if you already have a lookup table, you know, you're looking for these tuples, you don't have to compute them, right? Is it instead of doing computation, you're saving time Ariel Gabizon (00:35:03): You're saving a lot of prover time. Anna Rose (00:35:05): Okay. Ariel Gabizon (00:35:05): Yes and I would recommend Mary gave a really good talk at this Bar llan Winter School about lookups. Anna Rose (00:35:16): I'll try to find that too Ariel Gabizon (00:35:19): Yeah so lookups are great but the lookup protocols we had, you paid a price. The price was essentially that you had to put the table in the circuit. Meaning if table had size T, your circuit would grow by T so Anna Rose (00:35:43): I found that, so like, I still can't get my head around how you put a lookup table into it. Like, but I've seen you write out these like formulas that have L as the lookup table sort of shoved into them. But yeah, I don't actually know what that's doing. Ariel Gabizon (00:36:00): Well, yeah, I mean, to give a little more detail. You do pre-compute the lookup table and you could say maybe what you put in the circuit is some randomized combination of the lookup table and the witness with randomness that was chosen by the verifier. Anna Rose (00:36:23): Okay. Ariel Gabizon (00:36:23): So that sort of helps the verifier make sure that the proofer is not cheating. Anna Rose (00:36:28): This sort of just proves that you're like using the correct lookup table in a way, right? Ariel Gabizon (00:36:32): Yeah this proves that the witness values that you claim are in the table are really in the table. Anna Rose (00:36:38): Or you might not have all of them in, is that what you're saying? Like you sort of pick a few of them. Ariel Gabizon (00:36:43): The main way the prover would cheat is he would say this pair of witness values A B is in the table whereas it's not Anna Rose (00:36:52): Yeah. Ariel Gabizon (00:36:53): That would be the main way. Like say it's a table for range proofs where you're checking that A is in some range, 0 to 2 to the 16 and A is actually 2 to the 100. Anna Rose (00:37:03): Okay. Ariel Gabizon (00:37:03): So yeah. So you want the prover not to be able to cheat by writing something that's not in the table. Anna Rose (00:37:09): But when you talk about how it gets what pre-compiled and then put in, are you putting in all of the values of the lookup table? Ariel Gabizon (00:37:17): Yes. Anna Rose (00:37:17): Okay. You are all of them. Ariel Gabizon (00:37:18): Exactly. Yeah. In the current, so in the first generation lookup protocols, which it's part of, it's part of the second chapter. Anna Rose (00:37:26): Yeah. So this is chapter 2, part 2. Ariel Gabizon (00:37:31): We'll lookup tables is part 1 Anna Rose (00:37:33): Okay. Ariel Gabizon (00:37:33): So this first generation of lookup protocols Anna Rose (00:37:37): We've just moved plookup, because I think it wasn't, but we're going to move plookup then into chapter 2, part 1. Ariel Gabizon (00:37:44): Yeah. Anna Rose (00:37:44): Okay. We're moving that in Ariel Gabizon (00:37:46): As in chapter. Yeah. Anna Rose (00:37:47): 2 part 1 Ariel Gabizon (00:37:48): It's in 2 part 1. Anna Rose (00:37:49): Got it. Ariel Gabizon (00:37:49): So the first generation of lookup protocols, Anna Rose (00:37:51): Someone should summarize this after. It's like we're brainstorming Ariel Gabizon (00:37:55): Someone should make chart Anna Rose (00:37:56): Exactly. Ariel Gabizon (00:37:57): Accompanying chart for the episode, I think. Good. Anna Rose (00:37:59): Like, yeah. Ariel Gabizon (00:38:01): Okay. Anna Rose (00:38:03): Yeah. So you're saying any, so plookups in chapter 2, part 1, but all of this sort of like new work into lookup tables would go into the second part of chapter 2. And Caulk would definitely be in part 2 of the chapter 2 Ariel Gabizon (00:38:17): No, Caulk is the start of chapter 3. Anna Rose (00:38:18): Oh, wow. Okay. Okay. Okay. It's that pivotal, so Ariel Gabizon (00:38:22): So as I was, as I was saying that the thing is you can only, if you use a table of a certain size, then your circuit is going to grow by that size in these algorithms like plookup. So if you want a circuit of size 2 to the 14 and you want to keep your circuit of that size, you're only going to use tables of like, size a little less than that. Anna Rose (00:38:46): Ah and if you can only use smaller lookup tables, I guess you can't put that much in, so you're not saving as much. Like you want to put more Ariel Gabizon (00:38:54): The larger tables you can use, the more prover computation you're going to save Anna Rose (00:38:58): Got it. Oh, interesting trade off there. Ariel Gabizon (00:39:02): Yeah. So, but this led to the very interesting question. Can I design a lookup protocol where the prover computation does not depend on the table size? Anna Rose (00:39:16): Okay. Ariel Gabizon (00:39:17): And this, this is what Caulk did Anna Rose (00:39:21): Wow. Ariel Gabizon (00:39:23): And almost, I mean, okay, they had a little dependence on table size that this paper Caulk+ removed completely. But basically this is, this is what Caulk did. It totally almost totally removed the dependence of prover computation on table size. Anna Rose (00:39:41): Nice. Ariel Gabizon (00:39:41): Which opens up the, the possibility of using much larger tables, Anna Rose (00:39:46): Which then would save more prover time? Ariel Gabizon (00:39:49): Save a lot more prover time. Yeah, exactly. Anna Rose (00:39:52): Yeah. And is this where your work starts then? Is this where you, you're kind of branching off then? Ariel Gabizon (00:39:57): Exactly. So I saw the, the Caulk paper come out like 10 months ago maybe. And yeah, that totally caught my attention. And so Caulk, so it made this big conceptual leap, but it was not totally practical. It was a little of a heavy protocol in terms of the exact like costs. And this led to this kind of fast sequence of papers improving Caulk. So I'll just say the names, it's not too important. It was Caulk+, Flookup, Baloo. Anna Rose (00:40:38): Oh yeah. Ariel Gabizon (00:40:38): And the last one currently in this series is a paper called CQ. I wrote with Liam Eagan and Dario Fiore. And I'm very excited about the CQ protocol because I think this is a truly practical protocol that allows you to use large tables. Anna Rose (00:40:59): Let's go into it. So this is, we're in chapter 3. This is today? Ariel Gabizon (00:41:02): Yes. We're in chapter 3. Anna Rose (00:41:03): Okay. So CQ like the letters? Ariel Gabizon (00:41:07): The letters CQ. Anna Rose (00:41:08): Okay. So just to position it though, is CQ a proving system? Ariel Gabizon (00:41:13): CQ is just a lookup protocol. Anna Rose (00:41:17): Okay. (00:41:17): But it can be easily integrated into a proving system like PLONK Ariel Gabizon (00:41:22): Right. So it follows the work of Caulk. I'm just trying to think like, what is it that you're actually doing then in CQ that allows for this like larger table inclusion, the lookup tables? (00:41:34): Well, I mean, the inherent reason why suddenly you can use much larger tables, you could say it already starts in Caulk. So the inherent reason why pairings are, are involved here is that right we have different polynomial commitments, we have FRI and we have, the three big ones, FRI, Bulletproofs, and KZG. So FRI is the, you could say the least homomorphic. Like if I have FRI commitment to F, FRI commitment to polynomial G, and I want to get the commitment to F plus G, there's no convenient way to do it Anna Rose (00:42:20): Because they're not similar? Is that why when you say homomorphic, do you mean like? Ariel Gabizon (00:42:24): So homomorphic, I mean that as opposed to FRI, if I look at Bulletproofs through KZG, so if I have a commitment to F commitment to G, now I want to get the commitment to F plus G. Anna Rose (00:42:39): It's easier. Ariel Gabizon (00:42:40): I just sum, I just sum them Anna Rose (00:42:43): Is that the definition? So it's funny, I've talked about fully homomorphic encryption. I've never actually defined homomorphic. Well, is it that you can, like is it the morphism is similar, like to change it is similar? Is that what it's kind of, I'm trying to actually get to the definition here, but Ariel Gabizon (00:42:59): So yeah homomorphic, okay. So also there's this sort of in terminology that is like a little fuzzy. So I guess you could for what I just said, that from the commitment F plus G, some people would call that additively homomorphic. But they'll just say homomorphic for short. And I think what happens is from the context, like you, you can infer, do they mean just additively homomorphic or they mean more like the sort of the word I guess homomorphic, it means that you can do operations in two different orders and it doesn't change the result. Okay. So right, one way to do, you can first sum the polynomials F and G, you have that operation of summing the polynomials, and then take the commitment and you're going to get the commitment of F plus G. Anna Rose (00:43:50): Okay. Ariel Gabizon (00:43:50): And we say like the Bulletproofs and KZG are additively homomorphic, or, you know, people for short will just say homomorphic because it means that if we do these operations in the different order, we'll get the same result. Anna Rose (00:44:04): Got it. Ariel Gabizon (00:44:04): But if we first take the commitment of F, so we first take the commitment and now we sum Anna Rose (00:44:10): It would be the same Ariel Gabizon (00:44:11): So we get the same result. Anna Rose (00:44:12): Yeah. Ariel Gabizon (00:44:12): So that's why we say that Bulletproofs and KZG are additively homomorphic because the commitment operation, it, you could say people will use the word commutes. You can with the addition, like you can do it before the addition or after the addition, and you'll get the same result. Anna Rose (00:44:30): Does the Caulk papers and all of the subsequent work rely on that, that it has additive homomorphism? Ariel Gabizon (00:44:37): So yeah. So the additive, this property of additive homomorphicity Anna Rose (00:44:46): I said homomorphism. I don't know if I'm right. Ariel Gabizon (00:44:48): The property of having, of being like additively homomorphic or the commitment is called, yeah, would be called in homomorphism. Yeah. Anna Rose (00:44:58): But it does need that like, so Ariel Gabizon (00:45:00): Definitely Anna Rose (00:45:00): So that cannot be used on Ariel Gabizon (00:45:04): The additive. Sometimes people will just call this the additivity of the commitment, right? Yeah. when they don't feel like Anna Rose (00:45:10): Trying to pronounce that word Ariel Gabizon (00:45:15): That's used in Caulk I mean that's like a base requirement, but it's used in Nova it's used yeah, the additive homomorphism, the homomorphicity the additivity is like crucial all over the place but the point is to get Caulk we're going to use something. So the additive property being additively homomorphic, that is also what Bulletproofs has Anna Rose (00:45:39): Okay. Ariel Gabizon (00:45:40): What KZG has is it has this, because of the pairing, it has sort of this partial multiplicative homomorphism. Anna Rose (00:45:51): Ah Ariel Gabizon (00:45:52): Without fancy terms, because maybe I'm not getting the fancy terms right either. Anna Rose (00:45:57): It allows you to, what you just said about adding, you can do with multiplying partially Ariel Gabizon (00:46:02): Okay. So what it allows you to be concrete, what it allows you to do, say, now I give you commitments to four polynomials, F1 F2 G1 G2, KZG commitments. And now I ask you, is the product of the Fs equal to the products of the Gs is like F1 times F2 equal to G1 times G2. So with KZG you can do that check, directly from the commitments. Anna Rose (00:46:33): But why is it partially then? Is it, because it has to be F with F and G with G, but not F with G Ariel Gabizon (00:46:39): It's partially because I can check if F1 times F2 is equal to G1 times G2, but I cannot actually compute the commitment to F1 times F2. So I have a way to check if they're equal. Oh, but I can't actually compute the commitment to F1 times F2. Anna Rose (00:47:05): Okay. So, but even with that, how does that relate to the lookup tables? Like why is that that, how does that relate to why is that good? Ariel Gabizon (00:47:13): So okay, so here we come to Caulk. So why is that good? So this turns out to be extremely powerful. Anna Rose (00:47:23): Okay. Ariel Gabizon (00:47:23): And to give a little detail on it, a big component of trying to work with big lookup tables. If you look at protocols like Caulk and CQ is that, or a big part of SNARKs is you're a lot of times in situations where you want to prove that one polynomial divides another polynomial. Anna Rose (00:47:47): Okay? Ariel Gabizon (00:47:47): That's all over the place. Now the standard way you do this is you compute the quotient, what's called the quotient polynomial meaning simply the second polynomial divided by the first. So you just compute it, compute this polynomial, then you compute its commitment and then you open all these 3 at a random point in check that the first times the quotient equals the second. (00:48:12): The thing is in Caulk when we're trying to use a big table, this created a situation where this quotient had huge degree. So to actually compute it would be sort of like having to put the big table in the circuit in terms of the prover cost. But it turned out in Caulk that sometimes we have quotient where computing the polynomial is expensive, but actually computing its commitment can be if you do, if you did the right pre-processing, computing its commitment can be much cheaper than computing the polynomial itself. Anna Rose (00:48:48): Okay. Ariel Gabizon (00:48:49): So now we're in this situation where we can cheaply compute just the commitment of this quotient and then the question is, okay, does this help us? And yeah, it does because exactly, because of what we said that we can compare products directly from the commitments in KZG Anna Rose (00:49:07): But you don't have to compute them, you don't actually have to compute them. You just have to prove that they're the same or something. Ariel Gabizon (00:49:13): Yeah. Yeah. Anna Rose (00:49:15): I don't know if you're doing the same like, because you had talked about the F1 times F2 times G1 times G2. That would just be the same. You just prove that they're same but not know what they are. Ariel Gabizon (00:49:24): Yeah. I prove that they're the same without the thing here to be totally precise. The thing, I don't know, I sort of, I don't know what F2 is. Anna Rose (00:49:35): Okay. Ariel Gabizon (00:49:35): I know I don't have F2 in my hand. I only have the commitment of F2 in my hand because it's much cheaper to just compute the commitment of F2 than F2 itself. Anna Rose (00:49:46): Okay. Ariel Gabizon (00:49:47): And Anna Rose (00:49:48): Do you have to make then assumptions of correctness? Like does this, like, in that probabilistic, like is it correct or not? Are you just sort of, does it lower the probability that the lookup table is being used correctly in any way? Ariel Gabizon (00:50:01): It doesn't lower it, but what is here in, you know, used very heavily, and this is and this is true you know, for all the SNARKs based on KZG to actually conclude that the checks we're doing imply that these products of polynomials are equal, we're heavily using this, this strong cryptographic assumption, the Algebraic Group Model. So we heavily rely on that, but no, but it doesn't like given that we rely on that anyway, anytime we're using KZG it doesn't reduce the probability that compared to say plookup that the lookup is correct. Anna Rose (00:50:36): I have sort of a side question here. I wanted to ask for a while, which is when you listed the three polynomial commitments schemes, I think FRI, Bulletproof, KZG, does FRI ever use lookup tables? Or is it just you'd never, you can't? Ariel Gabizon (00:50:52): Yeah, so definitely, so Polygon Hermez for example, and others probably too. Yeah, they use FRI with lookup tables. The reason they can do this is lookup arguments like plookup, they can work with a generic polynomial commitment. Anna Rose (00:51:10): Okay. Because they don't rely on this additional additive homomorphism. Ariel Gabizon (00:51:15): Yes. They don't rely on it. Okay. Plookup just needs a polynomial commitment. Anna Rose (00:51:20): Got It. So they're doing some part of this lookup table work. They can use part of it, but at some point like Caulk they wouldn't be able to go that far with FRI at this point. Ariel Gabizon (00:51:29): Exactly so yeah, so the additive actually places where the additive homomorphism is used. You can even places where it is used, you can you can sometimes get around it with losing a little efficiency but the Anna Rose (00:51:45): multiplicative Ariel Gabizon (00:51:45): The multiplicative Anna Rose (00:51:46): Is the bit you couldn't do Ariel Gabizon (00:51:47): Yeah. So this was also an interesting fork in the road in Caulk in the sense that like we had these few years in chapter 2 where, you know, you could pick and replace your polynomial commitment scheme as you wanted. And here was the first protocol where KZG only allowed Anna Rose (00:52:09): Okay and Bulletproof's also not allowed. Ariel Gabizon (00:52:11): Also not allowed because only when you have KZG is based on pairing and it's only the only one that has this multiplicative property. Anna Rose (00:52:18): Interesting Ariel Gabizon (00:52:18): Of course, an interesting research question is come up with, with new PCS that have this multiplicative ability Anna Rose (00:52:26): So we sort of mentioned the accumulations and this like aggregation. Does the lookup table impact that? Because it feels like a different part, right? Ariel Gabizon (00:52:39): It is. Yeah exactly. At least I view it as pretty orthogonal, Anna Rose (00:52:45): Like modular almost? Ariel Gabizon (00:52:46): Yeah, it's pretty modular. Anna Rose (00:52:47): Okay. Ariel Gabizon (00:52:47): Like you'll have your lookup component and you'll have your aggregation accumulation folding component. Anna Rose (00:52:54): Got it. Ariel Gabizon (00:52:54): And usually they're pretty like independent of each other. Anna Rose (00:52:57): Do you think then, so in this story, are we like chapter 3 so far the chapter 3 that has been described is the lookup table component. But in chapter 3, do you think there are other, like is there an accumulation side that's still being told, like that story of which accumulation scheme or folding scheme or whatever wins? Is that unfolding? Because we're in chapter 3, right? Ariel Gabizon (00:53:24): I mean we're in both chapter 2.2 because people are, you know, with the excitement around Nova people are working very hard on improving aggregation. Anna Rose (00:53:34): Okay. Ariel Gabizon (00:53:34): And they're only using the additive homomorphism. Anna Rose (00:53:37): Oh. Ariel Gabizon (00:53:37): So it's fine, so we're both in chapter 2.2 and chapter 3. Anna Rose (00:53:42): Okay. That's exciting though. But that's what I'm wondering then, like, is there a fold over on the folding side into chapter 3 eventually? Ariel Gabizon (00:53:49): Well, that, I mean that's something honestly I haven't looked into. Is there a KZG specific like folding that is more efficient than you can only get? I haven't actually researched that. That's a good question Anna Rose (00:54:04): And does Nova or the sum-check based stuff, do they work with KZG already? Are they just using that or? Ariel Gabizon (00:54:12): Yeah Anna Rose (00:54:13): They could use it. Ariel Gabizon (00:54:14): They could. So, yeah the Nova style stuff, it only, it needs an additive. It crucially needs an additive homomorphism, not the multiplicative property. Anna Rose (00:54:24): Cool. Ariel Gabizon (00:54:25): Yeah. Anna Rose (00:54:26): Well I love this story that you just shared and I do actually welcome people to parse a little bit because like, I think there's a very clear narrative despite a few of our like side bonus episode explorations or special features, explorations. I'm so dating myself by referring to DVD bonus stuff Ariel Gabizon (00:54:47): I hope people haven't got too lost with all the overlapping 2.2 and 3 Anna Rose (00:54:53): I don't know, I think it's cool, but I now, I mean, so this, you know, we are now like chapter 3 is on, like maybe we can go back into the CQ work and is the CQ work finished and is, and where is it going and what's it for right now? Ariel Gabizon (00:55:11): The CQ work is basically finished. Of course. It's always like nice to keep trying to optimize, save a little proof size or verify work here and there, but I think it's very practical, the form it's in. So my attention, a lot of my attention has shifted to trying to get it used (00:55:30): And I think where it might have a lot of impact is better SNARKs for nasty functions. So we talk a lot about hash SNARK friendly functions. I like the nasty functions, not because I don't like friendly things, but I think that's where maybe CQ will sort of shine most. Anna Rose (00:55:54): What's an example of this? Ariel Gabizon (00:55:54): So Keccak is a really good example, right? So Keccak is definitely not a SNARK friendly function. It does a lot of crazy bid operations and it's you know, it's heavily used, right? The Ethereum mainnet it stores data in trees based on Keccak Anna Rose (00:56:15): Okay? Ariel Gabizon (00:56:16): Right here we get into the types, right? There's now people are calling there's type 1 zkEVM and type 3 zkEVM. I don't know what type 2 zkEVM is Anna Rose (00:56:26): There's a 2.52 but Ariel Gabizon (00:56:28): There's a 2.52? Anna Rose (00:56:29): No, there's a 2.5 as well. Ariel Gabizon (00:56:35): I'm glad we're not the only one with all theses Anna Rose (00:56:38): No, yeah, there's definitely some additions on that one. Ariel Gabizon (00:56:42): Okay. Anna Rose (00:56:42): But you're saying, so it's in that context. So like in the roll-up context, it might actually be interesting Ariel Gabizon (00:56:46): Well in the zkEVM context, for example, when, when you want to do what's called a type 1 zkEVM. So you want to like fully simulate, fully validate what's going on in mainnet because the state in Ethereum is stored in trees with Keccak, you have to end up doing a lot of Keccak in your circuit. Also what what Axiom is trying to do now that allow you to sort of access historic Ethereum data in your smart contracts that ends up like proving this historical data is correct. Like a lot of their cost is Anna Rose (00:57:26): These are all nasty functions Ariel Gabizon (00:57:28): Well, the Keccak is the nasty function. SNARK-wise. Anna Rose (00:57:33): Why would CQ be useful for a nasty function then? Is it because you use lookup tables more efficiently? Ariel Gabizon (00:57:40): It's not, it's just because usually when you have nasty functions in the sense of a lot of bitwise operations rather than like field operations that's where lookups make the biggest difference. And the bigger table you have, the more efficiency you gain you can get and CQ you simply allows you to use bigger tables. Anna Rose (00:58:05): Cool. Has this been implemented, is that sort of like your current, like when you're saying like you're looking to find uses, is it like you're kind of like, hey teams, do you want to try using this and implementing it, or are you going to implement it? Ariel Gabizon (00:58:20): So I mean hopefully I'll write a few lines of code at least. But yeah, I am trying to collaborate with better coders than me. So what was really nice is Andrija from the Geometry team. He implemented CQ pretty much the night the paper came out. Anna Rose (00:58:44): Wow, that must be so exciting to see. Ariel Gabizon (00:58:46): Yeah so he implemented over, it's over Arkworks and I mean, I'm interested and I think also he and other people from Geometry and maybe other teams are trying to get CQ into Halo 2. I mean, right here is a side note, right? There's this whole interesting subject of what like, sort of SNARK library, like PLONKish library will end up sort of dominating like Polygon Hermez and Jordi's PIL language looks really nice but, so I'm wondering how things will converge, but right now it seems like all the massive developers is around Halo 2. Anna Rose (00:59:31): Yeah. Yeah. (00:59:33): Actually, yeah, the way that sort of mindshare circles around some of these ideas is so fascinating. It's like, I think it has, there's certain groups that will champion certain proving systems and then you'll get tooling being developed really quickly and it's sort of fascinating to see like which ones are picked up and which ones are picked up less. Ariel Gabizon (00:59:55): Yeah. Anna Rose (00:59:55): And I mean, looking back to that SNARKtember, at that time, you were also seeing that, because there was all these proving systems coming out all at once. And I think when we can now look back and say like, PLONK kind of like dominated that, but it's hard to, when you look now like here in Montenegro and where like Justin and all these folks are here, Nova's the talk of the town which is sort of a continuation on Halo, but not Halo exactly right. Ariel Gabizon (01:00:22): Yeah, I mean, I would say it's in this general theme of aggregation accumulation, but I wouldn't say it's directly connected to Halo Anna Rose (01:00:30): Yeah but right now Halo 2 Ariel Gabizon (01:00:33): But I'd like to say a word now that I mean just before we get into that, yeah, there was, what, what was interesting, I remember being at zkSummit7 and there was this maybe convergence on PLONK as a proving system, but I really remember then feeling like there were 15 different PLONK implementations and there were zero convergence on that. And there were potentially a lot of like, duplicate efforts and you know a years past maybe more or less, and it seems like on the library side there is maybe some convergence on Halo 2. Though I'm interested to see what will happen with that. Anna Rose (01:01:10): Yeah. I want to talk before we sign off on some other works just floating around. So we've mentioned Nova, and I know you had some, when I first brought it up or when Justin first brought it up to you, you were like, ah, this already already exists. I know this from before. So I wanted to talk a little bit about sort of your thoughts on Nova and then some of the competing models, or I don't know if they're completely competing, but these other sort of streams of research happening. So let's start on the Nova side. Has your mind been changed? Are you Nova-pilled? Ariel Gabizon (01:01:46): I'm Anna Rose (01:01:47): Semi-Nova-pilled? Ariel Gabizon (01:01:48): I'm not sure what I am because I was Nova-pilled a few days ago. Very successfully, but then Zac from Aztec, sum-check-pilled me. And now you encountered and now I don't know if I'm just back to normal or Anna Rose (01:02:07): One pill makes you higher. One pill brings you down. Ariel Gabizon (01:02:10): Yeah. So I don't know if like yeah, exactly. Yeah. Anna Rose (01:02:15): Okay. So but this is something interesting, like Nova, the paper came out almost a year ago, I think and for me at least, it's really just popping up more recently in what people are talking about in our channels and stuff like that. But you mentioned when Justin was at least trying to Nova-pill you that there was another paper, an earlier paper that you thought this was like kind of directly taken from. Talk a bit about that maybe. Ariel Gabizon (01:02:42): Right. So let me yeah, say a few words about what I think are the basic ideas here, right? So we say we want to aggregate or fold claims and then only like do one proof at the end. Yeah. Let me get just a little technical. So to be concrete, say the claim we want to prove is A times B is equal to C, right? So the simple sort of, the simple aggregation that is in the sense already happening in a lot of code bases is say, and now say, I have a lot of these claims, so I want to prove A1 B1 equals C1, A2 B2 equals C2, and so forth. The simple aggregation is say, actually the all the Bs are the same. So it's A1 B equals C1 A2 B equals C2 and so forth. (01:03:39): And actually this is sort of a situation that that sometimes comes up. In that case, there's something very simple I can do, I can take what's called a random linear combination of all the, A's I can take a random linear combination of all the C's, and then I can just check is the random linear combination of the A times the B equal to the same random linear combination of the Cs. So this is a common idea. It happens in the Halo 2 aggregation and the code already. But now the question is, all right, what if the Bs are different? It's like A1 B1 equals C1 A2 B2 equals C2 and the Bs are different. So the naive thing you could try is, all right, let's try the same thing. Let's check is the random linear combination of the A times the random linear combination of the B equal to the random linear combination of the C. And this doesn't totally work because when this random linear combination of the A times the random linear combination of the B is, except the terms we want, like A1 times B2 and A2 times B2, it's going to have a lot of these crossroads, it's going to have A1 times B2. Anna Rose (01:05:03): Oh, okay. Ariel Gabizon (01:05:04): So sort of the idea that was floating around in papers for a decade though, yeah, I'll say that I've been a champion of this one paper, a Bootle, Cerulli, Chaidos, Groth, Petit 'Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting' that this is the paper where this idea started. But then I saw that they actually, they say, oh, it's similar to some, some this Groth paper. Anna Rose (01:05:31): Even earlier? Ariel Gabizon (01:05:34): Again, the PLONK mutation comes from. So actually the attribution, I've been you know, arguing with people about attribution, but I see actually the attribution is a little complicated. maybe, yeah. But any, but the basic idea also in Nova and here is yeah, we're going to have a lot of these cross terms, but the thing is the cross term is going to be like something fixed times this randomness we chose for the random linear combination. And in fact, if we just let the prover, the fixed thing, just commit to it in advance and we choose the randomness later, even though we're letting him commit to something totally arbitary, this is what's called the error term or sometimes it's called the slack term in, in these papers, I think it's called the error term in the Nova paper. Even though we let the prover, like it's, you have an equation that the verifier is trying to check and you, and now we're letting the prover add a totally arbitrary error term to balance out this equation. So this seems like definitely the prover can cheat, but it turns out that since we're having him commit to this error term and only later multiplying it by the randomness, we chose for these combinations, the prover can't cheat. Anna Rose (01:06:45): Is it because you're multiplying it by randomness, it means the prover can never engineer it to be corrupted like because there's this like extra step they, like it wouldn't be able to figure it out beforehand. Ariel Gabizon (01:06:58): Yeah, because the randomness multiplies the error term and the error term was chosen without knowing the randomness. The prover can't engineer a fake proof. Anna Rose (01:07:09): Got it. That's a cool technique. But is that new to Nova or has that always been there in all of this work? Ariel Gabizon (01:07:15): So this was used in this Bootle et al paper, which attributes something similar to the Groth paper. And the Bulletproofs gave a paper, gave a much more simple form of this than the Bootle et al paper. And yeah. But the form in Nova is a little different, so yeah. Anna Rose (01:07:38): Okay. Yeah, as mentioned, I want to do a full episode on Nova, but just quickly kind of like what is the trick to Nova, what's it adding on those works maybe, or what's it doing different? Ariel Gabizon (01:07:50): Nova is adapting this technique to R1CS Anna Rose (01:07:54): Ah, and the other because the other ones were bulletproof more like, or nothing. I guess the previous work had not had a specific setting or like, Ariel Gabizon (01:08:05): Yeah. So Nova is adapting this this to R1CS Anna Rose (01:08:11): But then that's interesting is Halo R1CS, because remember we talked in chapter 2 that like we were kind of leaving a bit of the R1CS model behind weren't we to get the PLONKish arithmetization. Ariel Gabizon (01:08:24): Well, right. So that's why since people are using PLONKish arithmetization, that's why sort of after Nova people have adapted this technique Anna Rose (01:08:35): I see. Ariel Gabizon (01:08:36): To PLONKish arithmetization. And this is what's happening in Sangria Anna Rose (01:08:40): Or Supernova I think tries to as well. Maybe. Ariel Gabizon (01:08:43): I'm not totally sure Anna Rose (01:08:44): Yeah. Okay. We'll leave that one. But yeah. Interesting. Yeah, for sure in Sangria it is, yeah. Ariel Gabizon (01:08:48): Yeah. Anna Rose (01:08:49): Relaxed PLONK. Ariel Gabizon (01:08:51): Yeah. Anna Rose (01:08:52): That's what the word, that's where the name comes from. We had Nico on just recently. Ariel Gabizon (01:08:57): Yeah. Anna Rose (01:08:58): Okay. So that's interesting. So it's the implementation of this concept for R1CS. And now because it's been done, I guess there's this like, oh, can we also implement the same kinds of techniques further on? Ariel Gabizon (01:09:12): Yeah. So Nova has really brought into the, you know, general awareness, this idea that you can aggregate sort of arbitrary nonlinear equations. In for example, this A1 times B1 we're also A and B are, they're different every time. Anna Rose (01:09:32): You can start to do it because of this error addition. Just because it's just showing that the prover can't act maliciously. Ariel Gabizon (01:09:39): Yes, yes. Anna Rose (01:09:39): Interesting. Wow. What about the sum-check pill? Ariel Gabizon (01:09:45): So this is a really cool technique, but right, we have to, I think it's still to be figured out how much it exactly gives you versus other techniques. So there's a little this feeling that, oh, we don't have to prove anything. We just fold and we just prove in the end. But I mean, when you really get in down to the details, you have to, okay, what is the cost of this folding? And compare to the cost of the proving, right? That's what you're saving. So, yeah. So indeed, and, and that's what I've been thinking a lot these last few days because everybody here is talking about Nova. So really a few days ago where I was, I was Nova-pilled, I had, so there's this error term you have to compute (01:10:35): And I had this idea in my head that there's some FFT involved in computing this error term. And then we were, yeah, we were talking with Justin. Justin was like, no, there's no FFT involved. And I was like, of course, now how are else are you going to, and then I realized it was more efficient than I thought. Anna Rose (01:10:51): Okay. Ariel Gabizon (01:10:52): And yeah I was Nova-pilled to a degree but like when I sort of did a rough computation with myself, I sort of came to the feeling that for say, standard PLONK, like it would give you the cost of folding would be like 20% of the cost of the full proving. Anna Rose (01:11:14): I see. So it's the folding starts to, it's like, on the proving part, is that actually on the proving part, does it basically, does the folding add to the computation somehow? Ariel Gabizon (01:11:23): Right, exactly. So say we have like we want to prove a thousand PLONK proofs and we want to just fold them and just do one proof in the end and we want to use Sangria or, so what do you have to do for each instance? So you need to, the main thing is at least when your circuit is big, and then other costs become negligible, your main cost is exactly computing. Well, first of all, you do have to commit to what's called your witness polynomials that you do in a regular PLONK proof. And you also do, when you're just folding a PLONK statement, in both cases, you need to commit to the witness polynomials and then what is the additional thing you need to do when you're folding? You need to compute and commit to the error terms. Anna Rose (01:12:12): And that also requires something like that's taking some time or Ariel Gabizon (01:12:17): Yeah that requires some work. Anna Rose (01:12:20): Okay. Ariel Gabizon (01:12:21): So you're doing that work and what are you saving? So the main thing that you're saving, at least the main thing that you're saving that you can't save with simpler aggregation techniques is computing and committing to the quotient polynomial. So, because you don't need to compute the quotient polynomial and indeed like I found out a few days ago, you have no FFTs, so you saved all the FFTs, which can be sometimes like 50% of the roughly 50%. So you've saved 50%. Anna Rose (01:12:58): Cool. Ariel Gabizon (01:12:59): And also you've saved this part of committing to the quotient polynomial and sort of my estimate was with, you're going to go down to 20%, 25% of the work you did for full proofing. So that's a, it's going to be a 4x, 5x factor. It's pretty nice. What happened yesterday when I was sum-check pilled Anna Rose (01:13:21): We'll see which one sticks in the long run on here, but okay, Ariel Gabizon (01:13:25): Was that I understood from Zac that actually maybe if you simply because there, there's another big way to avoid FFTs Anna Rose (01:13:34): Ah Ariel Gabizon (01:13:34): And that this was very much highlighted in the HyperPlonk paper instead is to use the sum check protocol. The sum check protocol avoids all FFTs, like the folding does. Anna Rose (01:13:48): So it saves you that 50%? Ariel Gabizon (01:13:51): It saves you that 50% Anna Rose (01:13:53): And then you don't have to do the folding and then the Ariel Gabizon (01:13:57): And you do not have to commit to these error terms. Anna Rose (01:14:03): Okay. Is the error terms the most heavy more so than the folding, or is it the same thing? Ariel Gabizon (01:14:10): So when the circuit is large, there's other factors having to do with the folding when the circuit is large enough. So the computing the error term is I think the most significant cost. And there's here this other topic of the degree of your constraint. The degree of your gates. So for example, you know, Nova worked for R1CS, the degree of the constraint is only 2, but people sometimes, like using high degree gates degree, 5 degree, 6 degree, that's one thing that's highlighted in the HyperPlonk paper that it's very compatible with high degree gates. And the thing is, when you generalize Nova say sangria to high degree gates if you use degree D, constraints of degree D, you're going to have to commit to D -1 error terms. And that's sort of like the same time 2 that in irregular PLONK proof takes you to commit to the quotient polynomial. So it's like you've saved the FFT work, that 50%, but you haven't, maybe, especially if you're going to, you will want to use high degree gates. You haven't saved the commitment time because committing to these error terms is as expensive as coming to quotient. And here we come to the an important point isn't the sum-check approach. You both save the FFTs and there's not really something like that to commit to. Anna Rose (01:15:35): Is there any way to do both at the same time? Are they too different? Ariel Gabizon (01:15:39): So that's something that should be explored, and I think people are exploring it. I think it's called 'Hyper Nova', where they're trying to and yeah, and we still need to see where these things will land. And this also relates to the question, will people want to use high degree gates? Is it useful or not? Or is it not that big a deal to use to only gates of degree, 2 or 3? Anna Rose (01:16:03): Interesting. Ariel Gabizon (01:16:04): So there is a world after talking about this yesterday with Zac, I think there is a world where sum-check will sort of make Nova / Sangria type aggregation less of a big thing but Anna Rose (01:16:22): Or maybe they're used in combo. This is the writing of chapter 3 Ariel Gabizon (01:16:27): Well this I would say is chapter, this whole aggregation stuff, I would put it in chapter 2.2 because it doesn't rely on, on this KZG only multiplicative thing. Anna Rose (01:16:39): Yet Ariel Gabizon (01:16:41): Yet Anna Rose (01:16:42): All right. Ariel, thank you so much for coming on the show and sharing with us this journey through the chapters to today, and also your thoughts on some of this new stuff. It's definitely, you know, very exciting. And I want to as mentioned, do a Nova deep dive, maybe do a sum-check deep dive again. I mean we, so I know as far as I understand, Justin Thaler is like championing this as well. I don't know if we covered it that much in the episode I did with him this year, but yeah, it might be fun to explore it again. Ariel Gabizon (01:17:19): I guess sum-check, every time you think it's gone out of fashion. It's already, it's from the nineties, but it's coming back. Anna Rose (01:17:29): Rears it's head Ariel Gabizon (01:17:29): Yes Anna Rose (01:17:29): Nice. Thanks Ariel. Ariel Gabizon (01:17:30): Thanks Anna. Anna Rose (01:17:31): Thanks for coming on again. So I want to say thank you to the podcast team, Tanya, Henrik and Rachel, and to our listeners, thanks for listening.