Anna Rose (00:00:05):
Welcome to zero knowledge. I'm your host, Anna Rose. In this podcast, we will be exploring the latest in zero knowledge research and the decentralized web, as well as new paradigms that promise to change the way we interact and transact online.

Anna Rose (00:00:27):
This week, I dive into Halo 2 with Daira and Str4d, two cryptographic engineers at the Electric Coin Company. We explore the new ideas that Halo had introduced and how Halo 2 built on these ideas. Adding optimization, such as Plonk-ish arithmetization to take what was a breakthrough technology to a production-ready proving system. Before we start in, I wanna suggest you check out the ZK whiteboard sessions, a new content series focused on ZK education. It consists of a series of videos that look at the building blocks of ZK. We already have six modules live. This would be a great place for you to learn about the topics we talk about in this episode, as well as give you the foundations to think about ZK research. I've added the link in the show notes. Be sure to check it out and do join the ZK Hack discord. If you wanna join study clubs or any other activity we have coming around the series. Also, if you're looking to work in the field of ZK, be sure to check out the ZK Jobs Board, there you find ZK focused jobs from top teams in the space. We're in the midst of getting a lot of new jobs added there at the moment with the run up to the ZK summit. So do check it out. Now, Tanya will share a little bit about this week's sponsor.

Tanya (00:01:37):
Today's episode is sponsored by Manta network. Manta is a privacy hub for web 3, by leveraging zero knowledge proofs Manta brings on chain privacy to any crypto asset. Manta Pay, which is their first app, allows users to privately swap crypto assets crosschain. Manta is also hiring they're looking for skill developers and engineers passionate about cryptography and passionate about bringing privacy protection services to all of web 3. Manta's remote first, backed by teams like Polychain, Binance and other industry leaders. Check out careers.manta.network to apply. So thanks again, Manta. Now here is Anna's episode on Halo 2.

Anna Rose (00:02:19):
So today I'm sitting here live with Daira and Str4d, both cryptographic engineers at the Electric Coin Company. Welcome to the show.

Daira (00:02:27):
Lovely to be here.

Str4d (00:02:28):
Yeah, it's great to be here.

Anna Rose (00:02:30):
So Daira, this is your second time on the show.

Daira (00:02:33):
That's right.

Anna Rose (00:02:33):
We did an episode in 2020 where we talked about halo1, I guess, Halo original I'm very excited with this episode to kind of continue on that and explore halo2 and what's coming up. Str4d this is the first time you're on the show.

Str4d (00:02:51):
Yeah, that's right.

Anna Rose (00:02:51):
But it's, it's not the first time we've had, we've been able to kind of work together. You were the first speaker at the first ZK Summit in March, 2018.

Str4d (00:03:01):
Did ZK summit even know it was gonna turn into this at that time?

Anna Rose (00:03:04):
It did not. It, it zkSummit zero knowledge summit was actually the conference around this podcast that we had named zero knowledge and Howard Wu, and yourself brought your friends, brought your knowledge and turned the zkSummit proposal into a proper zkSummit.

Str4d (00:03:22):
I am sorry for your loss.

Anna Rose (00:03:24):
What's wild is, do you remember that first talk? I mean, it was high level. Yeah. I, it was like, I was doing where's Waldo.

Str4d (00:03:31):
I was doing my best to be like, cool. I'm going to assume literally nothing and do the simplest explanation. I can to give an intuition and then Howard follows up with his talk and I'm like.

Anna Rose (00:03:43):
The deepest Snarks.

Str4d (00:03:45):
Yeah. And I'm just going, right. We've really like we've, we've covered the full gamut. I am sure they are gobsmacked,

Anna Rose (00:03:52):
But we do. We needed that. I mean, at the time, the knowledge about zero knowledge was quite,, like sparse. There's maybe a few people in that crowd who were well versed, but, and it was wild to see zkSummit, like one after another. And now I don't know if you know this, but we're doing zkSummit8 in Berlin in September. So the eighth edition, but zkSummit is not the only event focused on this kind of tech, Zcon is as well. And we are actually recording this at Zcon3, which is very cool to actually get to see everyone again in person. I did do an episode on Zcon0, which was like this combo episode. I think I interviewed something like 15 people and spliced it together. It was a lot of work it was really cool though. It's a little snapshot into like the world and what things were happening. I'm gonna add all of these to the show notes, including the video from the first zksummit. And I hope people will check that out.

Str4d (00:04:44):
Yeah, it was a, it was a good time. It was the, you know, cause the, the foundation had not long really sort of gotten off the, off the ground and it was sort of its first big event. And the first time really that a lot of the wider ecosystem had been, been able to get together. Cuz prior to that, it was, most of the in-person events had been either just ECC themselves or ECC, like hosting something in, in a place for a few people to, to come along. Like things were growing, but like this was sort of the first like major Zcash addressed, but also like zero knowledge focused conference that was like for the wider community. I mean there was also other things going on, like the, you know, the ZK proofs workshop and stuff, which were more geared at like the theoreticians and the implementers and things directly. But this was

Daira (00:05:31):
The standardization.

Str4d (00:05:32):
Yeah, exactly. But this was sort of like the first like zero knowledge is fun. Let's talk about it. Totally.

Daira (00:05:38):
Yeah. I remember it was in Montreal and it was in the middle of a heat wave and I hadn't realized that Canada had heat waves, but yeh it was, it was really hot.

Str4d (00:05:47):
It's not what one associates with them,

Anna Rose (00:05:49):
Although I will correct. You Str4d the first zkSummit actually happened before zcon0. So I think I'm so I've been kind of claiming the first a little

Str4d (00:06:00):
I'll, I'll I'll give you that.

Anna Rose (00:06:02):
No, you were at it, you were the first talk at the first

Str4d (00:06:04):
That that is fair. I will, I will, I will give you that.

Anna Rose (00:06:07):
It was different though. Cause at the time the zkSummit was also just partly zero knowledge focused and partly yeah, blockchain general.

Str4d (00:06:13):
Yeah, it was, yeah, it was, it was a very fruitful time in terms of like giving, giving rise to some very awesome events to for the space.

Anna Rose (00:06:25):
So I wanna hear a little, I think it would be really great to introduce both of you a bit more to the audience. Daira, you've already been on the show and we have heard on that episode kind of more of your backstory, but yeah. Say kind of who you are and what you work on at Electric Coin Company.

Daira (00:06:41):
Yeah. so I'm the lead author of the Zcash protocols specification. I do a lot of work with on Zcash dev with core team a lot of documentation and protocol design.

Anna Rose (00:06:55):
Very cool. And since we're gonna be talking a lot about halo2, what's the role there?

Daira (00:07:00):
So I'm a, co-author on the original halo paper. I sort of invented, discovered whatever developed the Pasta curves. So this, this construction for curve cycles that allows recursion in halo, hopefully will allow us to use recursion in Zcash. And we, we have some other collaborations, for example, with Filecoin and the Ethereum foundation that were also developing recursion for those.

Anna Rose (00:07:32):
You were sort of saying like, you might have discovered it's either developed or discovered, but discovered almost sounds like it like emerges. It's always been there. I like that.

Daira (00:07:41):
Math has always been there. It, it is discovered and it, and it's also a social construction, like many things

Anna Rose (00:07:48):
Okay Str4d tell us a little bit about your story and kind of like what led you to the work that you do today?

Str4d (00:07:53):
Well, I got bored one day and ended up doing network privacy on the side of my regular day job, which wasn't a job. It was being a student and going through the, the university pipeline, you know bachelor's, master's PhD. And that was, that was the track I was on. And then at some point I think it was yeah, it was in real world crypto 2014 was sort of the first like in person event I'd gone to, after having spent a lot of time sort of online in the privacy space and that's actually where I met Daira and ZKO and I think Nathan was there, Brian Warner, some, some, some very fun people. Yeah. Met them in person and actually also listened to Matt Green, give the zero cash talk. Nice. And yeah, didn't think anything more about cryptocurrency at the time. But yeah, that was sort of, the connection was made. And then a couple years later when I was finishing my PhD yeah, Zooko approached me and asked me if he, if I could potentially put a little bit of my time towards working on this cool new zero knowledge proof circuitry stuff.

Anna Rose (00:09:05):
Yeah. And what, what would you say? Like what, what are you focused on what's your day to day? What kind of projects are you mostly looking at?

Str4d (00:09:12):
So I was roped in by the enticement of zero knowledge proofs. I spent a lot of my initial years working on, not that, I did a lot of the, the base engineering for, for Zcash and and just like general engineering with the other, with the rest of core team on, you know, the wallet and the, and the base layer. You know, I, I implemented the proof of work system after, you know, figuring things out in terms of what we're gonna do with with Daira and, and then, yeah, I, I slowly wormed my way from that, into the cryptography side because I've just been able to be around so many amazing people and learn from them and, and gain experience from them. I have a very memorable experience of in early 2017, I was at CCC. So sorry, the, the Congress event that CCC runs in Hamburg Leipzig, Leipzig yeah,

Anna Rose (00:10:11):
Maybe it was there that year.

Str4d (00:10:12):
I think it was Leipzig no, at the time it was Hamburg. They've ended Leipzig they've actually ah, they're now back at Hamburg because they've finished the renovations. Oh cool. So I was there and Zooko was there and we were talking to someone and they're like, oh, Zooko, you should come to our thing and give a talk about how zero knowledge proofs work, how Zcash works. And he was like, oh no, that's okay. I'm I'm a bit too busy and I'm there going? Sure. I'll do it. Nice. It was so I was like, cool, I'm going to give a talk about how zero knowedge proofs work in three weeks types on the messenger. Sean, how does zero knowledge proofs work and I proceeded to pester my colleague, Sean Bowe and Eran Tromer who was one of the seven scientists and were both in the messenger, you know, for a, for ECC for the next three weeks. Wow. And wrote a talk and yeah, that was...

Anna Rose (00:10:57):
A good way to learn quick.

Str4d (00:10:58):
Yes.

Daira (00:11:00):
Deadlines are so they, they focus the mind so much.

Str4d (00:11:03):
Very much very important. Yeah. So since then, yeah, I've done more with sapling. Like I, I helped more with the sapling protocol and, and doing bits of design there and was very involved in the, in the Orchard protocol. Cool. Cryptographic design and implementation.

Anna Rose (00:11:19):
I just realized, I just double checked something. You have been on the show before you are in the combo episode of Zcon0. And I just was, I just opened it in the browser and was like, oh, so small correction, but I, I I'm happy you shared with us a little bit more. I think those were quite short back then. So I wanna sort of direct us now towards halo. Are we here at Zcon3 we've I think I've seen two, at least two talks focused on that. Maybe there was a couple more yeah.

Daira (00:11:48):
My talk was on analysis of the shielded protocol

Anna Rose (00:11:51):
Okay

Str4d (00:11:51):
I gave a talk on well halo2, but focused on the performance aspects of it. And particularly around the elements of the halo2 proving system and the, the things that's built on and also our implementation of it that help us to leverage the performance and, and build performance circuits. And then my colleague Ying Tong gave a presentation on the ecosystem and what other people have been doing with the, with halo2.

Anna Rose (00:12:20):
Yeah, very cool. I want to in the start of this, like, because we've done an episode that did talk about that initial Halo kind of breakthrough and the history kind of leading up to halo, I'm gonna obviously put that in the show notes for anyone who wants to hear that. But in this one, I sort of wanna revisit some of the concepts that we introduced in that episode. And then talk about halo2. I also am kind of doing this selfishly because we're doing the zWhiteboard series where we're kind of covering a lot of basic building blocks. I'm not the host I'm watching Brendan host. And I realize that I'm missing some kind of general vocabulary sometimes to follow exactly what is being said. So I was hoping, yeah, we could do some of these. So, and then you can tell me, I, I wanna understand what they are and then you can tell me how they all kind of weave together in halo. So one of them was the inner product argument. I was very curious, like what is an inner product argument?

Str4d (00:13:18):
So are you familiar with a dot product?

Anna Rose (00:13:20):
I am not

Str4d (00:13:21):
Excellent. Let's start there. Um so if you think of having a, a vector, are you familiar with a vector?

Anna Rose (00:13:28):
I am familiar with a vector. Excellent. Like Algebra.

Str4d (00:13:30):
Cool. So, so if you, if you take a vector we take a pair of vectors. The dot product is where you take like each element in the vector pair wise. So the first, the first in each vector and the second each vector, you multiply each of the pairs and then you add all of the the resulting sums together. Okay. And you end up with a single value at the end that represents the dot product of the vectors.

Anna Rose (00:13:58):
So like it, would it be the dot product argument or is that the dot product?

Str4d (00:14:02):
That's the dot product.

Anna Rose (00:14:03):
Okay. That's the output. So then, so the inner product is a generalization of the dot product where instead of it necessarily being like you multiply the two terms together and then add them, it can be more general than that. It just has to satisfy some properties such that, you know, if you, if you take the inner product of say vectors, U and W, it must be equal to the inner product of vectors W and U. Okay. and there's a few other properties that it must satisfy, but it, but precisely the action that is applied can be different. But overall, you still end up with taking a vector of some values. We'll call them scalers. You take a vector of scalers and the inner product results in a single scaler by, by some mechanism. Okay. So then the inner product argument is a mechanism that we use.

Str4d (00:14:51):
We, we use it to take some large polynomial. So we encode our circuit via some mechanism into a polynomial. And we want to digest that down into a single representative of, you know, a commitment to that polynomial. So what we do is we take the polynomial, we split it into a lower half and an upper half, and then we, we can then commit to the lower and upper halfs of the polynomial separately. And then we fold them together with with some, I believe it's a random challenge that gets involved. And so then you repeat this as a sort of like a tree. And so you can think of at each step, you have the length of the polynomial until you, you, so like the number of coefficients in it until at the end, you only have a single coefficient. It's like single value lift and that's.

Anna Rose (00:15:39):
And so every round you're doing that action.

Str4d (00:15:41):
Yes, exactly. So at the end, yeah. Yeah. You, the folding step. Like you take the two, the low enough halves and you fold them together. That's the inner product step, as I understand it. So at the end you've taken something, let's say your polynomial has, like it's an n-degree polynomial, it's got n-coefficients, whatever you've done 'log n rounds' because you've halved it each time.

Anna Rose (00:16:07):
And why, though, like, why do you want that small, that smaller one?

Daira (00:16:10):
So this ends up contributing to proof size. So, so each of those rounds contributes one element to the proof. And so you you end up with this log(n) component to the proof if you're committing to vectors of size n.

Anna Rose (00:16:28):
But is the, does that mean it's small? You want it to be small? Like, I guess that's the

Str4d (00:16:32):
It's smaller. Okay. Yeah. So what we're trying to achieve with something like this is, you know, what the purpose of having this is that, you know, you have a proof that is sublinear in the size of the circuit. Like if you double the size of the circuit, the size of this part of the proof does not double in size. Oh, interesting. It, it, it would increase by one because doubling adds like one extra layer to the to this inner product argument. Okay. So it's, it's a way to just like, commit to something larger in the space of something smaller. It is, it still grows with the size of the polynomial that you are committing to, but exactly. Okay.

Anna Rose (00:17:12):
Cool.

Str4d (00:17:13):
It helps you in, in certain cases with certain efficiencies.

Anna Rose (00:17:16):
All right. My next word, Polynomial IOP.

Daira (00:17:20):
Okay. So IOP is an interactive Oracle proof. So an interactive proof is where you have a protocol between a prover and a verifier. And the prover is trying to convince the verifier, that they know a witness for some statement. And if you have an interactive proof, then you can convert that into a non-interactive SNARK in this case by, well, in the case of halo2 and a Fiat-Shamir transformation. Um so Fiat-Shamir is just where the verifier would normally send random challenges. And instead of having interactive communication with the verifier, you just have a hash function generate those challenges based on the previous transcript. So that's an interactive proof an interactive Oracle proof. So the, the verifier doesn't have to read all of the previous messages. So, so we're trying to generate some more efficient protocol by replacing these long messages between the prover and the verifier with shorter commitments. And so this model before we've done that optimization, we say that the verifier has Oracle access to the messages sent by the prover. And that means that they can choose some position in the provers message and query that. So that's interactive Oracle proofs and then

Anna Rose (00:18:59):
Add polynomial to the front.

Daira (00:19:01):
Exactly. so if these messages are polynomials, then we can, we can instantiate the Oracle using a polynomial commitment scheme, basically

Daira (00:19:14):
And hand waving a little bit

Anna Rose (00:19:15):
Which actually leads me a little bit to the next term, which I think we, we do hear quite often is the polynomial commitment scheme. That's one that I think we've, I believe we have Justin Drake did like a four/three part series on polynomial commitments as a video in the study club. And I can link to that as well, but let's refresh what's the polynomial commitment scheme

Daira (00:19:36):
In a commitment scheme, you're trying to produce some small value that commits to a larger value. And it has these properties called binding and hiding. The important one for, for our purposes is binding. And that says that you can't open the commitment in two different ways. So the verifier can given a purported opening, they can check that it corresponds to the commitment, and there's only one possible opening that that will satisfy that or one that can be found.

Anna Rose (00:20:11):
That is commitment.

Daira (00:20:13):
Yes. That's a commitment scheme.

Anna Rose (00:20:15):
I have one. Okay. One little side question. When you say 'open', what are you doing?

Daira (00:20:20):
You, you are finding, are you like, you're finding an input to the commitment.

Anna Rose (00:20:26):
Okay.

Daira (00:20:27):
The output is the small values that, that you call a commitment.

Anna Rose (00:20:31):
Okay.

Daira (00:20:31):
There's this ambiguity in terminology. Sometimes you should really say commitment scheme when you're talking about the algorithm. And so a commitment is an output to that scheme. The opening is the input.

Anna Rose (00:20:43):
Okay, cool. So now a polynomial commitment scheme.

Daira (00:20:47):
A polynomial commitment scheme is a commitment scheme to polynomials. And it also has this extra property that you can check an evaluation of the polynomial. So you can ask for the polynomial to be evaluated at a given point and check consistency with the commitment.

Anna Rose (00:21:05):
Cool. And again, this is like, this would, the commitment is smaller than

Daira (00:21:10):
Yes, exactly.

Anna Rose (00:21:10):
The thing you're checking or you're committing to

Str4d (00:21:14):
Are there commitment schemes where the, where it's larger?

Daira (00:21:17):
I think the definition doesn't require it to be smaller.

Str4d (00:21:21):
Cool. It's, it's more useful for it to be smaller

Anna Rose (00:21:25):
So there's two or three other terminology things I wanna do, but I think we actually do talk about these quite often on the show. So one would be like recursion or recursive proofs, and the other would be the trusted setup. I think trusted setup. We can just point to the episodes. We can say that is the thing that halo2 does away with. We don't actually need that anymore. It's an MPC, but yet we've done full episodes on trusted setups. I think we'll leave that one, but recursive proofs, why don't we define those?

Daira (00:21:53):
Okay. So recursive proof, you are checking a verification of another proof. So, so your circuit and the outer proof has the verifier checking the verifier of some inner proof. And it can track the verifications of multiple proofs. In general, you form a tree or a directed/dissected graph of things that you're proving, and then they can all go up to a single proof at the top. And if you check that proof and you believe in the knowledge soundness of the the proof system, then you're effectively tracking all of the leaf proofs.

Anna Rose (00:22:34):
Yeah. Yeah. It's almost like a, you are compressing, I mean, maybe it's the wrong term, but you're like information is then being reduced into one small thing. That's proof that proves all of it.

Daira (00:22:43):
Yes. an interesting thing is that it doesn't have to be just one party creating this tree of proofs. So you can collaboratively form this tree and the parties that are generating relief, proofs can know different things. So that this is important in the case of Zcash or any private cryptocurrency, because let's suppose that you had cryptocurrency that, that used recursive proofs pervasively, then each of the transactions representing the leaves would be generated by some different sender. And they would know different spending keys, for example. Mm.

Anna Rose (00:23:26):
I've also, I mean, recursive proofs or recursion sometimes, like I've also understood it just like a proof of a proof of a proof of a proof. Yep. So like it's a little bit, like, it's more kind of in a line.

Daira (00:23:38):
Yeah. That that's a special case, which is also called incrementally verifiable computation.

Anna Rose (00:23:44):
I see. Okay.

Str4d (00:23:45):
It's just a tree with a single branch

Anna Rose (00:23:47):
Like, and then done over and over and over again.

Str4d (00:23:50):
Yeah. Or, or like, I, it's not

Anna Rose (00:23:53):
I really like it. I see what you're saying. Single branch, because each one, like as you go down the branch from like each

Str4d (00:23:58):
Imagine having a tree and then you cut off every branch except one. Yeah. That's

Anna Rose (00:24:02):
But you still have these stop points in that, right?

Str4d (00:24:06):
Yeah. It's, it's actually, it's more like having like a, a it's

Anna Rose (00:24:09):
Like having a rope?

Str4d (00:24:09):
Really unbalanced tree.

Anna Rose (00:24:11):
Yeah. Or it's like the rope with the knots maybe is that, is that what it looks like?

Str4d (00:24:14):
Leaves stapled to a pole

Anna Rose (00:24:17):
Okay. Our metaphor, this is day three of Zcon3. So we are, and I really appreciate you kind of going over some of these definitions. I, I followed that, I think because I'm currently kind of doing a re-study of a lot of these basic building blocks, the, I, I followed it all. I'm very happy about that.

Daira (00:24:36):
There are actually competing definitions of what IVC and PCD, which is the, the general case stand for. And we we've given basically one of them here. And I, I didn't really understand the other one

Str4d (00:24:52):
At the end of the day, the core takeaway with it is that what you're trying to do with recursion or with a recursive proof is to reduce the size of what you need to verify. So, if you think of having like two of your main proofs, while you have to verify two proofs, and if you can use recursion to combine them into a single proof, then as long as the proof that you create to do that is smaller, like, more efficient to verify, than the two individual proofs were, then you have recursion. Got it. And actually that's, what's referred to as the recursion threshold so there's a concept of needing a certain size of circuit to be able to verify another circuit and for different schemes, the, the recursion threshold point can be at different sizes.

Anna Rose (00:25:44):
Cool. Before, we go on to how these all work together, I do wanna just compare something because the inner product argument, you also had sort of reduced it to something or you, you had as far as I could tell you folded into the, is it in a completely different part of the math from recursion?

Daira (00:26:02):
So what we did in halo was to find a way to do this verification that has to happen inside the recursive circuit to do that in basically log end steps rather than end steps. So the the final verification of the inner product for the last proof that's done by something called the decider. And that costs linear time in the size of the outer circuit. But the part of the circuit that you need to do the recursive verification is our log end.

Str4d (00:26:43):
So they are similar math in terms of like they you're all dealing in polynomials here, but they are different components of it. I think in that, you know, what you're trying to build with the circuit itself and, and recursion itself is the inner product is a component of the proving system. Okay. so it is something that you then need to run as part of the verifier, which then comes to how to do that efficiently. But it is not, it is not part of the recursive proof itself. There's no requirement for an inner product argument in recursion. It just so happens that the way in which the halo technique does, it requires the use of inner product argument to, to work. But there are other approaches to recursion schemes that, that aren't bound to the inner product argument.

Daira (00:27:39):
So, so I think I slightly mis-described it before. It's not that you are computing. And in a product argument within the recursive proof it's that you are folding together two arguments in such a way that if the input arguments were valid, then the output arguments will be valid in some sense.

Str4d (00:28:01):
Yeah, actually it's, it's interesting to look at because you might initially think that, oh, well the inner product argument itself is folding and well, if you fold the two together, do you just end up with an inner product argument directly? And in fact, no, the process of doing the folding, like the way in which we check the inner product arguments and collaboratively itself is then checked in a proof that then has a completely separate inner product argument. So it's, you, you do have this reduction step from two to one, but it's not that you're reducing the two inner product arguments or the multi inner product arguments from the proofs, you're checking into this new one, you are just checking them in a way that means you have to produce a proof that itself has an, a separate inner product argument that it generates.

Anna Rose (00:28:49):
Okay.

Daira (00:28:50):
That's a better way of describing it than I said.

Anna Rose (00:28:53):
It is day three of...

Str4d (00:28:56):
Yes, it is. We both gave our talks today.

Anna Rose (00:28:59):
Okay. So now halo original halo came like kind of on the scene and what did it bring, like what was the big innovation that it brought? And I think some of the words we just defined will pop up in that. So, I mean, I think we can say there was no trusted setup. That's great. That's sort of the, the outcome, but what it was happening under the hood to allow that?

Daira (00:29:21):
So, so I think it was the, the innovation was the combination of being able to do recursive proofs without a trusted setup because the only known way to do recursive proofs at that point was to use these more heavyweight arguments where you were, you had the whole verification circuit in the outer circuit to do the recursion. And the only known way to do that efficiently was to use these cycles of curves that are both pairing friendly. There's only one known construction that allows you to do that. It's called an MNT4 MNT6 cycle. And it requires curves that are quite large at least 800 bits, but probably larger for 128-bit security. Probably about a thousand bits.

Str4d (00:30:22):
Yeah. 

Daira (00:30:24):
First time I remember this method of constructing a proof system from an IOP and commitment scheme is when Mary Maller,described it to me,we were in London,and we were at this, this meetup, which is very productive and I learned a lot about how proof systems really worked and the example that,Mary used was using,KCG,or Katé, as the commitments for the polynomial commitment scheme. Uand I think she was referring to Sonic,or she might have been referring to some, some predecessor.

Str4d (00:31:07):
If it's the London meetup that I remember, this was the one that we went to UCL, was it? Yes. Yeah. That's the one that led to Sonic.

Daira (00:31:15):
Right? Yeah. Yes.

Str4d (00:31:16):
This was a, this was actually an ECC meetup that we just, you know several of us, well, both Daira and myself were based in the UK. And we were like, we want some, some of our colleagues to come over and and you know, chat about some stuff. And so we met up with you know, Mary Maller and several others at at, at a meeting and, you know, one of the presentations given I think, yeah, it was Mary Maller. And I can't remember.

Daira (00:31:42):
Was that Henry de Valence,

Str4d (00:31:44):
I think you might have been I'm I think Sarah Meiklejohn was there as well with something, but I think that was a different presentation. I don't think it was Mary's one. I can't quite remember. So we had this meeting and Mary gave a talk and Sean and Daira got very excited and the next day they were not at the next meeting because they were over at UCL talking with with Mary about proofs. I think Ariel was maybe with you as well.

Daira (00:32:15):
I can't remember. I, I do remember that she explained Groth16 to us. Oh, Jens Groth was there.

Str4d (00:32:22):
Oh, lovely, amazing. I'm so glad I missed it. Amazing.

Anna Rose (00:32:26):
One thing you mentioned Sonics. So that was a predecessor paper. We actually had Mary on the show, I think about a month or two ago where we talked about that, paper and sort of the lead up to that's another one I can link to in the show notes.

Str4d (00:32:38):
Yeah. So, so it was that meet up and, and talk that, I think that's what got Sean talking with Mary on this and that's Sean and Mary are both co-authors on the Sonic paper.

Anna Rose (00:32:49):
Cool.

Str4d (00:32:50):
Um so then when it came to halo the main reason that halo was built around a, the Sonic style polynomial IP is because that's what we had to hand.

Anna Rose (00:33:00):
Got it.

Str4d (00:33:01):
With the, the core innovation we were focused on was not the proving system per se. It was the recursive accumulation technique.

Anna Rose (00:33:12):
Cool.

Str4d (00:33:12):
Um and putting that, figuring out a way to describe it so that other people would believe us, that it worked.

Daira (00:33:21):
Yeah. and the reviewers did not believe us that it worked

Str4d (00:33:25):
Yeah. It it was a very busy week when, when Sean messaged us and went, I think I have an idea. And I had actually, I'd flown to New York to, for something else. I think I was, I was doing something for ECC, and then I was gonna meet up with some friends. And instead I spent all of that week in my hotel room, as we were writing code to try and prove that we could actually get this to work.

Anna Rose (00:33:52):
Wow.

Daira (00:33:54):
Yeah. We, we did not expect this property that you can do the thing that you need to do inside the verification circuit in logarithmic number of constraints. So Sean just posted this problem and it was on slack. I think he posted this problem and asked us how to do it efficiently. And, and I came up with a way of doing it efficiently. It, it, it wasn't anything spectacularly innovative. It was just the obvious way of doing it. Ended up being taking only logarithmic constraints.

Anna Rose (00:34:27):
Cool. In Halo, how was the inner product argument? You kind of talked about that combination. Was it in the halo work for the first time that you were finding that combination of the inner product argument and the recursion?

Daira (00:34:40):
So bootle proofs and bulletproofs already existed. And so we, we knew that that was a potential route to getting a transparent proving system with this discovery that you could do, the thing that you needed to do in the recursive circuit in logarithmic time. Then our previous plan had been to use pairings for part of the proof system. So, so initially we were thinking that we would use this thing called half pairing cycles. That's where you have an efficient pairing on one curve of the cycle. And the, the other part is just an ordinary curve. And then you use that to get round the cycle efficiently. And then we realized because of this discovery that we didn't need to do that, we could use even smaller curves and we could make everything fully transparent.

Str4d (00:35:33):
Yeah. So the way that then the inner product argument came into it is that fundamentally, what we end up doing with Halo is this concept of deferring work. So if you look at what a verifier has to do to verify an inner product argument, there are components of that work that require operations on group elements of a particular elliptic curve. And there are operations that have to be done on the scale of field elements of that particular curve. Now, in the context of a circuit it's efficient to do one or the other, but at the time it was not efficient to do both. Now in recent years, people have figured out ways to do wrong field arithmetic that are actually like somewhat more viable, but it's still like, it is definitely more costly to do wrong field arithmetic. And it can, it can affect where your recursion threshold ends up.

Str4d (00:36:34):
And the end result of this was that you could take and of this recursion system was that you could split the inner product argument verification, logic into pieces that we could just do straight away in the main verification circuit, and then some deferred arithmetic that you would commit to in the first verification. And you would take it out of the circuit as as a private witness and then bring it back in to the next proof in the cycle where you are verifying the proof you just created and also verifying the remaining components of the previous proof.

Anna Rose (00:37:16):
Interesting.

Str4d (00:37:16):
So we're essentially doing like three proofs worth of pieces in, in, at once there's in, in any particular proof that isn't the initial one in the, in the recursion cycle, you are generating a new proof that needs verification, that proof is verifying the main body of a proof. And it is also verifying the tail end, deferred pieces of the proof before that.

Anna Rose (00:37:38):
Wow. Is that, was that a new technique or had anything like that been done before?

Daira (00:37:43):
That was a new technique with the original Halo paper.

Str4d (00:37:45):
Yeah. And this was then the technique that was generalized and formalized in the

Daira (00:37:52):
BCMS 20.

Str4d (00:37:53):
Yeah, BCMS 20, which was the paper that Pratyush presented at Zcon3 yesterday, I think,

Daira (00:38:00):
No that was a newer paper.

Str4d (00:38:04):
He presented both, he mentioned both.

Daira (00:38:05):
It was both, yes.

Str4d (00:38:05):
There was a, there was a '21 paper as well. But he, he mention he, he discussed it at his talk yesterday. So there are, there's a video to watch for that as well.

Anna Rose (00:38:14):
Nice.

New Speaker (00:38:14):
Yeah, that, that talk was well, it was about the previous paper, but it was also about split accumulation.

Str4d (00:38:22):
Yes. Which is a thing that they then figured out on top of this idea.

Anna Rose (00:38:26):
Very nice.

Daira (00:38:26):
And it has to be said there are other ways of doing recursion. So for example, Plonky 2 doesn't require this deferred arithmetic because it's using a fry based proof system. So that doesn't require different fields. You can use the same field all the way through.

Anna Rose (00:38:46):
What fry based proof system are they using?

Daira (00:38:48):
It's similar to the one used in STARKs. So I think it's Deep FRI.

Anna Rose (00:38:53):
Okay. I wanna ask now about the transition to halo2, like this is a new, like, what is the difference between halo and halo2 what's changing?

Daira (00:39:04):
The main difference is the arithmetization. So after, and, and roughly the same time as we published the halo paper, it was SNARKtember, which was this month, that was absolutely spectacular in terms of publication of, of new ideas, all of which turned out to combine really well with each other.

Anna Rose (00:39:29):
I think Mikerah from Hashcloak may have coined that by the way, shoutout for that.

Daira (00:39:35):
So, so after SNARKtember, it kind of became obvious eventually that Plonk style arithmetization allowed some optimizations that weren't possible in R1CS. And so you had other proof systems adopting this Plonk-ish arithmetization for efficiency gains.

Str4d (00:39:57):
Yeah.

Anna Rose (00:39:58):
Is halo2 Plonk under the hood?

Daira (00:40:02):
Um, no.

Str4d (00:40:02):
No.

Anna Rose (00:40:02):
You just said Plonk-ish, so let's go there.

Str4d (00:40:06):
Plonk the paper. And Plonk the arithmetization are two separate things. Okay. So the PLONK paper was a full proving system, a proven protocol, including arithmetization the same way that R1CS was an arithmetization introduced in a 2013 paper BC GTV. And that, I believe also had a proving system that was, it was deploying that this was for.

Daira (00:40:35):
We, we just looked that up by the way. We didn't, we didn't remember it. We had to look it up.

Str4d (00:40:39):
Yes. Um so

Anna Rose (00:40:42):
Little edit in there. Yeah. Yeah.

Str4d (00:40:44):
So the Plonk paper deployed a part, a particular arithmetization then there were several other papers that built on it. Turbo Plonk, I think was one name. I've heard ultra Plonk. I don't know if that's ever made it into a paper or if it's just one,

Daira (00:41:01):
There is no ultra Plonk paper that's,

Str4d (00:41:03):
But I think UltraPlonk is a, is a term that's that was used for like a particular instantiation. There are a lot of different things that have been used

Anna Rose (00:41:11):
With the name Plonk in it. I, I may have misheard this in my interview with Aztec, but I thought I heard Octo-Plonk, but I don't know if that's sounds real.

Str4d (00:41:21):
It rings a bell.

Daira (00:41:21):
A bell. That's the thing.

Str4d (00:41:23):
Yeah. I dunno specifically.

Daira (00:41:24):
Oh, it's it's I think it's with eight advice columns, something like that.

Str4d (00:41:28):
That I don't even know what I expected.Oh, cool. So the really neat thing from the Plonk paper was this Plonk-style arithmetization where, which essentially increased, ridiculously increased the number of degrees of freedom that you have in taking your protocol, the protocol that you're trying to make a circuit about and turning it into a circuit representable form.

Anna Rose (00:41:55):
Mm.

Str4d (00:41:55):
Um I go into a significant amount of detail about these in the talk I gave this morning at Zcon3.

Anna Rose (00:42:03):
Cool.

Str4d (00:42:03):
Uh in terms of how to leverage this extra flexibility for performance.

Daira (00:42:08):
So the main difference, I think, between Plonk and R1CS is that Plonk gives more flexibility in the polynomial constraints that it's enforcing. So, for R1CS, you're just enforcing a set of quadratic constraints. So A times B equals C where A, B and C are linear combinations. So for Plonk, you can specify these things called custom gates. They can equate almost an arbitrary polynomial with some limitation on the degree bound for efficiency, to zero. And so you can use these custom gates to implement things that are very common in a particular circuit. So, so for example, suppose your circuit like the Orchard circuit consists of a bunch of poseidon hashes and some elliptic curve arithmetic, you can define custom gates for each of those and they can be very efficient. And then the things that you only use a little bit of in your circuit, you don't need to worry so much about using custom gates for those. Although in the case of Orchard, we, we went completely overboard and define custom gates for everything.

Anna Rose (00:43:26):
Whoa

Str4d (00:43:26):
I think it was fine. I, I, I honestly think that the, the ability to define custom constraints is like the, one of the hidden superpowers of the Plonk arithmatization. And it was, it was not at all clear to me when I first saw the Plonk paper that this was a thing it could do. And the moment I realized that it was like, wow, this is incredible.

Anna Rose (00:43:46):
That's so cool. So what you've described though, you're, you're saying it's not the Plonk as described in that white paper. It's taking techniques.

Str4d (00:43:54):
Yes.

Anna Rose (00:43:55):
But do you also use techniques like lookup tables?

Str4d (00:43:57):
Yes. So they come from so yeah, the original Plonk paper didn't have lookup tables.

Anna Rose (00:44:02):
Yeah. That's newer.

Str4d (00:44:03):
Yep. Some later ones did. So we, so the halo2 proving system does also bake in the ability to create lookup tables. And similarly it bakes in the ability, which was another thing described in one of the Plonk papers, I believe to define global equality constraints.

Daira (00:44:23):
That was in the original paper.

Str4d (00:44:25):
That was in the original paper. Okay. So both of these are built around the idea of a, a permutation argument where you take some, say you have a, one of your columns that you've defined as going to be, say in an equality constraint, and you generate some sort of representative of it and you then take the column where it's going to end up and you generate a representative of that. And you show that these two are permutations of one another. I.E. they have the same values in them, but just in a different order. And that allows you to basically constrain that, like all of these these cells in disparate polynomials, all of these yeah. Values represented by components of these polynomials are in fact required to be the same.

Anna Rose (00:45:17):
Cool.

Str4d (00:45:17):
And the lookup argument gets a little more interesting. It relies on the same kind of thing under the hood.

Daira (00:45:24):
We were inspired by the plookup paper, but we actually use a different argument than the one in that paper, I think partly because I didn't fully understand the plookup paper at the time. 

Anna Rose (00:45:35):
Do you understand now because you did it another way?

Daira (00:45:36):
Um yeah. As is often the case if you know that something is possible, then you can do it in any of several ways.

Anna Rose (00:45:46):
Cool.

Daira (00:45:46):
Um and, and we chose a way for engineering reasons that that was a little bit more compatible with the rest of halo2.

Str4d (00:45:53):
Yeah. it is like it's slightly, I think, less efficient for certain usages of lookup tables. I believe the way that plookup works, you end up, you end up using like the polynomials used in the lookup tables once across all of the lookups. Whereas I think in, in the way that we've defined ours, you end up using the same polynomial. If you do, if you use like a sub component of a lookup table in multiple lookups so for instance, the reason you might want to do this is if you, and in fact we do this in Orchard If you have say a lookup table that you have, you have a list of intages, like from 0 through to like, you know, 10-bit integers. So we'll weight it 2 to the 10 minus 1. And for each of those values in your table, you then have like an elliptic curve point X and Y coordinates.

Str4d (00:46:42):
So we use this for Sinsemilla, the particular hash function that's optimized for this kind of thing. But you then also happen to have a list of numbers from 0 to the 10 minus 1. And you can use subsections of thatcolumn to also do range constraints, where you can say that something can be, say a 10-bit value by checking. It exists in that column, which is that, and that column has been baked into the circuit. So, you know, it's always gonna be a valid ten-bit number, but yet the, the way that we do it, it means that we end up using that, that ten-bit column, I think, twice inside, which is slightly less efficient, but it ends up sort of simpler to, to implement in the back end and, and reason about, yeah.

Anna Rose (00:47:24):
When you incorporated these techniques of Plonk, was it easy? Was it like halo is great, we're just gonna switch out a little something over here and it's gonna work just fine. Or what, what does that work look like when you decide to change that or yeah. Incorporate these types of techniques?

Daira (00:47:43):
So, so a big chunk of work is just understanding the original system well, enough to be able to adapt it.

Anna Rose (00:47:51):
Okay.

Daira (00:47:53):
Um no, it's, it's not easy. And

Anna Rose (00:47:55):
Did you have to start again, kind of?

Str4d (00:47:58):
We did. Yes. but we were going to do that anyway, I think, right. So the original halo implementation that we published along with the paper as I mentioned, we wrote this all in a week.

Anna Rose (00:48:11):
Hackathon style.

Str4d (00:48:13):
We are not really a fan of productionizing things that we write in a week

Anna Rose (00:48:17):
Fair.

Str4d (00:48:18):
There were certain liberties we took with the API and so on in order to get a demo, working a proof of concept working. But at the same time we had come off a multi-year development process for the bellman crate, which is the, the rust proof library that Sean started writing that we've then since we then used for the sapling protocol and it's also now used for sprout and which is an R1CS based proving implementation that implements yeah, R1CS and then Groth16 underneath. And we had learned a lot from both the original sprout circuit and and the libraries that was built with we then learned some built on that in bellman. And so we were taking the API designs and techniques and like for safety and, and performance circuit building that we learned from that. And we wanted to take those and apply them with the halo technique and Plonk as the component, and sort of, you know, mix them all together and build a, a proving system that was designed from the ground up to work with these components.

Daira (00:49:26):
I, I think actually we underestimated the complexity of the API that was needed to handle Plonkish arithmetization.

Str4d (00:49:34):
Absolutely.

Daira (00:49:34):
Especially some of the obstructions that we built on top, like regions, gadgets, chips which are described in Str4d's talk at Zcon 3. So yes, we, we very much underestimated that, but I'm very happy with how it's turned out now. We've got multiple groups building on the halo2 crates and they seem to be having a lot of success.

Anna Rose (00:50:00):
Cool.

Str4d (00:50:00):
Yeah. The, the end result of what we've sort of ended up with is that we have, so we have the Plonk style arithmetization that we use we with quality constraints and our lookup argument similar to plookup. And then that gets boiled down into a series of polynomials per the way that Plonk arithmetization works. Once you have those polynomials, then it transitions into sort of a more traditional, I mean, the, how, how long have people considered this traditional? How, how long does it have to be before? Before we consider it folklore but the, but a similar technique to many other proving systems of taking, so we take the polynomial, we want to constrain that, that grand polynomial, that, that contains all of our circuit to be zero. So we do so by proving that you can divide it by a target polynomial and show that there is no remainder that's, that's traditional, traditional way.

Str4d (00:51:02):
That's done for like Groth16 proofs to this. I forget precise details.

Anna Rose (00:51:08):
It's called a Vanishing Point.

Str4d (00:51:09):
It's a Vanishing Argument. Yes. That we use here. I forget specifically the details of how ours is built. We had to do a few tricks here and there to make certain things work within degree bounds because there are limitations to the sizes of polynomials that we can work with in certain areas of the, of the proof. So we had to be a little careful in terms of how certain degree bounds of polynomials were lined up. And so if you think of how Plonk, like you can have a concept of like rows and columns for Plonk. And so you have the, the number of rows ties to the, the degree of that polynomial, and then the maximum degree of any of the custom constraints in your circuit. You multiply those two together, you end up with an extended degree, like a of degree, like, you know, number of rows times maximum degree approximately. And so you have to work in an extended domain to do computations over those polynomials, and it isn't always efficient to do that. So there are areas where the polynomial is sort of like broken up and adjusted to to sort of make the vanishing argument work.

Daira (00:52:16):
Yeah. And there was some difficulty in getting that to work properly with zero knowledge in such a way that we could prove zero knowledge rigorously.

Str4d (00:52:26):
Yeah. We had, we had one version of that. And then once the security proof for zero knowledge got to the point that it was like, okay we, we now know that, like, we are unable to prove that the thing we are doing here is secure. We went and did a slightly less efficient thing. In that part of the vanishing argument to make sure that we could ensure that the thing that we were going to deploy was preferably zero knowledge.

Daira (00:52:50):
It's, it's interesting that a zero knowledge bug it it's mainly a theoretical bug rather than something that is actually exploitable. A zero knowledge bug was found in the original Plonk paper and that affected quite a few implementations. That's all public now, so I'm not revealing any security flaws that aren't already known.

Str4d (00:53:13):
But that also there is like, there's a there's that comes also back to Plonk. The paper also had a proving system. And so implementing that proving system from the paper had that, whereas thing, whereas proofing systems that had the Plonk arithmetization, but had their own proofs under the hood was sort of, they were separate from that.

Anna Rose (00:53:31):
Are there any other innovations, highlights that you say Halo 2 is bringing to the table? Maybe optimizations. Techniques.

Str4d (00:53:40):
Yeah. I, the thing I like to select Halo 2 as I was, as we were describing before is like the actual components of it are independently reasonably well understood from a theoretical perspective. UI think the, the remaining piece,that was left after doing the vanishing argument is just,you have to take that and do some evaluations and then do an opening argument to show they're constrained. And then that ties into the inner product argument. At the end, those are all like, relatively understood on their own. But the thing that isn't well understood is how to actually use the Plonk arithmetizations efficiently. Uthey've been various people working with,with Plonk arithmetizations in, in the ecosystem and us coming into it and going, we have a strong need to be able to build very performant circuits. We have,very specific performance requirements that,that we need to meet.

Str4d (00:54:43):
And in particular here, we had an overarching desire for the performance of the circuit Orchard that we built with it to not be horribly worse than the existing sapling circuit that that was used because we wanted to be possible to, for people to migrate and, and still be able to use it the way that they use sapling. Yeah. And a lot of the, the work that it ended up happening sort of fell into a couple of main categories. The, the first one was just building all of the primitives because, you know, there were no gadgets that were, that were reusable in this way. You know, we had to build all the, the elliptic curve arithmetic gadgets were the worst, Ying Tong did absolutely amazing work. Building those.

Daira (00:55:32):
Really spectacular

Str4d (00:55:33):
Yeah, between those. And then, you know, we had things like Poseidon and, you know, the Merkle gadgets and, and smear on top of that.

Str4d (00:55:40):
And like, there was a lot of that low level work to do at the same time as we were building those, we were looking at the kinds of things we were building and going, well, that looks awful. How can we make this better? And so doing sort of, and we were using the development of our circuit as sort of a, a feedback loop for developing the APIs to use, to develop the circuit and you know, coming up with, you know, figuring out, okay, what kinds of things are we repeating? What kinds of abstractions can we build to to make this easier to work with? And so likeas Daira alluded to earlier, one of the core things that we introduced was this, this concept of a region. So if you think of Plonk the table as a whole, like, you know, your full circuit defined there we, we define a small, like bounded rectangle within that, where we say, okay, in this region the relative offsets that you can use with like PLONK constraints, you know, custom constraints, they're guaranteed to be preserved.

Str4d (00:56:49):
Because one of the things that you have with Plonk is that your, your constraints are effectively two dimensional, unlike R1CS where you, you know, they they're minimally interacting with each other. And so enabling, you know, the use of that for, for low little packing you can do that within, within this definition of region and you can do that in the, in the API, in a relatively straightforward way. But by introducing that concept, we could then start doing automated optimizations over the, you know, around that. And start building that. So it was a lot of the work went into starting to try and build the, the tool chains for doing these like automated, almost like a compiler pass. And there's definitely a lot of influence on our API design and thinking that has come from both the regular, like compiler tool chain world, and also the the CPU architecture design, like designing Silicon chips or FPGA's world. Both of them sort of feed their way into like circuit design is almost both of them at once.

Anna Rose (00:57:55):
Weird though. Wait, when you say this the way you're using the word compiler, is this using it just in the building of the system or is this in the act in the activity that's happening while it's proving?

Daira (00:58:07):
So anything that transforms sort one expression of a program or a statement into another expression is a compiler.

Anna Rose (00:58:17):
Okay. So is it in the building thinking like the way you're developing it, that you're using this compiler tool?

Str4d (00:58:24):
No. What we are building is the compiler tool.

Anna Rose (00:58:27):
To be used within the protocol.

Str4d (00:58:29):
Within the within well it's in intermediate. So the thing that we are building is, you know, the proving system, i.e. The actual physical, like binary that, that grinds and generates the proofs. You know, you give it a circuit, you give it some implementation of a, of a circuit and you need to go from that circuit into a form that, that you can make with proofs. And that, and that's the compiler, that's the compilation step effectively. Now we don't actually have explicit like compiler passes yet. It's figuring out basically where these optimizations can fit and how you can work with them. Because sort of the, what we really started from was actually looking more at like the FPGA side of things and going, okay, this is really an area optimization problem, because like, you know, if the ideal is to have as few rows and as few columns as possible.

Str4d (00:59:18):
So if you need to use a certain amount of rows and columns, how do you use use them most efficiently? And that packing problem is where you start going, looking at these optimizations and doing like potentially multiple rounds of run a thing, see how it packs learn something about the circuit, you know, try something else. We at the moment only have some very relatively simple optimization passes implemented because they were sufficient for what we needed for our use for the Orchard circuit. But the general idea that we're sort of trying to, trying to bring about here in at least the halo2 tool chain is that both you can choose how you want to build your circuits in terms of the efficiencies you want to have while also not having to do most of that optimization work yourself. And so we can start reusing the learnings that, you know, we and other circuit developers have have accumulated over the years. 

Anna Rose (01:00:16):
Do you actually, just, this is a bit of an aside, but do you have, like, have you created a new DSL for any of this or are using bell? Cause you mentioned Bellman, is it still Bellman or it is

Str4d (01:00:26):
Still the Bellman like API. So we do not have a DS. Well, we don't have a DSL. We have a series of rust APIs that can be used to build circuits. Okay. So that is actually one of the things we would very much like to have. We just don't have anyone who has the time to build DSL on our team.

Anna Rose (01:00:45):
There's also, there are a lot of DSL, so you might wanna see if there's any out there.

Daira (01:00:49):
Yeah. We, we probably want to reuse a DSL,

Str4d (01:00:52):
Someone else to out. We certainly have people who would very much like to build DSL note. I said, have the time to do so. Um yeah,

Daira (01:01:01):
The, so as I was saying before, the traditional notion of a compiler, you have a text file that has a program in some language and you run it through the compiler and you produce a binary. But the, the input doesn't have to be a text file. It can be caused to an API and the output doesn't have to be a binary. It can be some in memory, data structure that you're using for your proof system.

Str4d (01:01:28):
Yeah. Like right now the, the situation is that you can't actually do it this fully at run time because we made some simplifications again, to try and a little bit limit the complexity of Plonk because there is so much that you can do with it. So there were a few things that we required circuit developers to configure by hand namely the number of columns and then which columns are being used by which sub components, which chips used within gadgets. And so on terminology that that we also sort of like came up with some other abstractions to sort of, again, help help with configurability. But one of the next things we want to do is enable those to be configured at runtime. So then we can both start doing wider range, optimizations, horizontal optimizations in addition to vertical, and be able to take in circuit definitions from outside the process, for example from an intermediate language that some other DSL has produced.

Daira (01:02:29):
So Str4d mentioned what we call floor planning, which is moving around regions to pack them tightly into fewer rows and columns. There's also something called selector combining. So selectors are what you use to turn on or off particular custom gates at, at different rows of the second. And so what you end up with in a circuit, especially like Orchard that has lots of different custom constraints is you end up with lots of, of these binary selectors. And so we have this optimization originally. I tried to do this optimization manually, and then we decided didn't that didn't make sense. We could do a better job doing it automatically where you combined several selectors into a single column, and then you reconstruct the original selectors by interpolation from the, the compress selector. Cool. And that reduces your proof size because you have fewer columns,

Str4d (01:03:33):
These other ones we've discussed and had it thinks, thought about over time, but that we haven't got implemented yet. Okay. So there's more fun that can be had in the future,

Anna Rose (01:03:42):
Lik halo2 it's comparable, I guess, then, to Plonky 2, how do those kind of match up?

Daira (01:03:49):
So I guess halo2 produces smaller proofs and Plonky 2 has a faster approver. I haven't actually compared them rigorously. So I don't want to make two strong statements about it. I'm really enthusiastic that we have some competition between proof systems and Plonky 2 are also able to do recursion. It's simpler in some ways because it doesn't require the deferred arithmetic and it's post quantum secure. So even if you have this trade off with proof size there are applications for which you would definitely want to use, um Plonky 2.

Anna Rose (01:04:27):
Cool.

Str4d (01:04:28):
And there's also potentially interesting, like cooperation that can occur between these. So you saw a bit in the, in the R1CS era as we can call it now,

Anna Rose (01:04:38):
Is it over?

Str4d (01:04:40):
Uh.

Daira (01:04:40):
Yes

Anna Rose (01:04:40):
There's still a lot of Groth16 out there.

Str4d (01:04:43):
I mean, you can build a Plonk, Plonk arithmetization that, that hooks into Groth16, if you really want to. Um we saw a lot of work being done to say, like, take your DSL and use it to compile that down to some, you know, some encoding of R1CS, you know, via front end that you could then pass that to a backend tool to do the, to the final proving. And I could definitely see something similar happening happening here. For example, if, you know, if I've not looked at Plonky 2's APIs, but if people preferred programming in those versus ours, you could imagine though, they, if they wanted to produce our kinds of proofs, that Plonky 2 might be able to, you know, run through, take things through its API and generate some intermediate representation that then gets passed across to the halo2 as a, as a backend that could then run through our optimization pass. Similarly,

Daira (01:05:39):
Or vice versa

Str4d (01:05:40):
Or vice versa. And you could even, I could even see a thing where halo2 proving logic is split to three, where you have the ability at, like you have our current rust APIs and you have either a layer just below that, or maybe at the same layer that lets you take an arbitrary circuit definitions. You then have our optimization logic that we have, which goes from the circuit that the user has to find to the circuit intended to be equivalent asterisks asterisks. We really, you know, have to be careful in the optimizations. We implement representation of the circuit and then take that and port that over to say Plonky 2 or some other system for final production of the proof that you care about.

Anna Rose (01:06:20):
Wow.

Str4d (01:06:20):
So this would enable different teams to sort of like work on the things that they are good at and, and leverage, you know leverage the other work that is being done in a, in a more modular way.

Anna Rose (01:06:32):
I love that idea. I wanna wrap up on Orchard. So you've mentioned it a few times, but we haven't really talked about what that is doing. I mean, this is the upgrade.

Str4d (01:06:43):
Hmm.

Daira (01:06:43):
The new shielded protocol for 16.

Anna Rose (01:06:44):
The new shielded protocol and the last one was sapling.

Str4d (01:06:47):
That's right.

Anna Rose (01:06:48):
And that one, if I remember correctly, sapling was the introduction of Groth16. Yes. So we is this replacing that part then is halo2, instead of.

Daira (01:07:00):
So, so some history remember that the proof system that we originally used for sprout called BCTV 14 had a soundless floor so, so we could have fixed just that soundless floor, but instead we decided to to move to Groth16 partly for efficiency reasons as well. And Sean, reimplemented the sprout circuit on Groth16. So both sprout and sapling now use that. And then when we moved to Orchard and then when we've introduced Orchard that's using halo2 and the, the previous show the protocols are still using Groth16.

Anna Rose (01:07:40):
Yeah. Oh, okay. So you're using both. Oh, interesting.

Str4d (01:07:43):
Yes. Yes.Yeah. So if you, if you want to interact with the Zcash protocol without involving pairings and the, the parameters and, and whatever, then you can just interact with the, the new orchard pool and you are only relying on the trustless proving system. There

Anna Rose (01:07:59):
You, is it because like, is it the way it's built, you can't switch that over without losing somehow the balances.

Daira (01:08:05):
So Groth16 needs pairing friendly curves. And so it's more efficient to keep sprout and sapling using Groth16 on the job job curve and BLS 12381, sprout doesn't actually use any elliptic curve arithmetic at all. It uses

Str4d (01:08:25):
It's, inefficient everywhere.

Daira (01:08:27):
Yeah, exactly. But implementing the sapling show the protocol on halo2 using the Pasta curves, that would be inefficient because that would require you to do wrong field arithmetic. So that's why we've stuck with Groth16 and BLS 12381.

Anna Rose (01:08:45):
And does each, does each upgrade have its own pool? Like is there still a sprout and sapling and oh, wow. Okay. I didn't realize it was

Str4d (01:08:52):
Yeah. The, you could in fact have more, more than one pool if you really wanted to Nathan gave a talk where he proposed that idea and has done in the past. But for now, what we currently have is each shielded protocol has its own pool or shielded pool. So if you want to move funds from one shielded protocol to a different shielded protocol, you have to first, you, you do them separately. You take it out of one, still within a single transaction, but you take it out of one pool and then put it into the other one by making two proofs, one from each. This has a couple of benefits, which is that we don't have to change the old pool's logic at all to be aware of the new pool and the new pool's design doesn't have to take on any baggage protocol, you know, tech debt debt from the original, no, the previous pool's design plus then you get some insulation between the two.

Daira (01:09:49):
Yeah. You, you can completely change the cryptography if you want to, as, as we have done for Orchard.

Str4d (01:09:53):
Yeah. One way to think about orchard is that like, if you understand sapling, you understand Orchard Orchard is essentially what if we implement the sapling protocol, but we change the root of spend authority to be a recursion friendly curve, almost every design decision that in which sapling and Orchard differ is a result of that decision, as Daira said implementing sapling with its existing curves on top of the new curves would be inefficient. So we wanted to just do the sapling protocol rather than the sapling pool in the new curves. And that's what gives rise to Orchard.

Daira (01:10:32):
I, I mean, we started with that idea, but we couldn't resist making a few design changes just for cleaning up things that we, that I think we did wrong in sapling. Um it, it's mainly just cleaning up things like the key structure to strengthen the properties that we have from viewing keys. And some optimizations like using a commitment scheme to generate IVK from a full viewing key instead of a hash things like that. We, we also paid a lot of attention to maintaining the privacy properties of the protocol against a quantum adversary who doesn't know the addresses

Anna Rose (01:11:16):
Is Orchard, like, is there a benefit to this upgrade in terms of performance? Or is there like something else that's happening that the users may notice or that the, like, does it have higher capacity? What's why do an upgrade?

Daira (01:11:30):
So it it's future proofing basically because we, we know that we will want to use recursion. And so we wanted to switch to curves that would support that. There are other things that we've introduced in the NU5 upgrade sort of in parallel with Orchard, for example, unified addresses, which allow you to specify an address from more than one pool. That looks like a single address to a user and also a new transaction version V5 transactions which have non malleable transaction IDs. So this is something that wasimplemented for Bitcoin in Segwit we've taken a slightly different design approach, but the, the effect is the same.

Str4d (01:12:17):
There are a few things that users would notice about Orchard itself. For certain kinds of transactions, Orchard proving is faster. The other kinds it is slower because we, one of the things we did was we, we moved to the model where you make a single proof like a single action, which is for both an input and an output. So one of the things we had done in Sapling was separated them so that you could make cheaper output proofs more easily, but the cost of that was then that you, you, you didn't have arity hiding between spends and outputs. So well for efficiency purposes effectively, you could, you could add a bunch of outputs with a few spins and you can tell that, like, it is few spins, many outputs rather than many spins, few outputs with Orchard, going back to an action model, similar to what sprout had. Now if you want to pay to many outputs, you could also have feasibly had many inputs. So it gives us a bit more arity hiding compared to to sapling proofs. And as far as the spin proofs go, the, the spends side is more efficient effectively, overall in Orchard.

Anna Rose (01:13:24):
Cool. I wanna say, thank you so much for doing this dive into halo2. Daira knows this. I've been trying to get this episode to happen for all, I think almost eight months. Yep. So I really, really am so happy that we've gotten a chance to sit down and dive into it. I'm definitely leaving with a much, much better understanding of sort of the challenges of doing these kinds of changes. Even though it sounds like just put Plonkish stuff in technique. Yay. But actually so much work has to go into it and, yeah. Thanks for sharing so much about the work you've been doing and thanks for doing the work. I guess.

Daira (01:14:02):
It's been a pleasure.

Str4d (01:14:02):
Yeah. I'm very happy to ramble.

Anna Rose (01:14:04):
Cool.

Daira (01:14:05):
It's been, it's been a pleasure both to, to implement new fun cryptography, although it took us a long, a long time longer than we thought. Mm. It's been a pleasure to do that. And to, to do this podcast with you.

Str4d (01:14:20):
Yes. And I'm, I'm very excited for more people to learn about it and, and the stuff that that has been done there because I want more people to be doing this kind of thing in their own improving systems and implementations. You know, yeah. More efficiencies, you know, more optimizations that, that people don't have to do by hand because doing things by hand is very error prone and and more developer tooling for people to figure out what's going on when they're doing so.

Daira (01:14:45):
And the next step is definitely higher level languages.

Str4d (01:14:48):
Oh, yes. Which we somehow keep avoiding ourselves. But

Anna Rose (01:14:53):
Cool. Well, thank you so much. I wanna say thank you to the Zcon 3 folks for letting us have this room to be able to record this episode. I wanna say thank you to the ZK podcast team, Tanya, Rachel, and Henrik, and to our listeners. Thanks for listening.