Episode 242: Halo 2 with Daira Hopwood and Str4d

Transcript

[Music] welcome to xero 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 this week i dive into halo 2 with dara and strad 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 optimizations such as plonkish

arithmetization to take what was a breakthrough technology to a production-ready proving system before we start in i want to 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 zika hack discord if you want to 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 today's episode is sponsored by manta network menta is a privacy hub for web3 by leveraging zero knowledge proofs menta brings on-chain privacy to any crypto asset mantapay which is their first app allows users to privately swap crypto assets cross-chain is also hiring they're looking for skilled developers and engineers passionate about cryptography and passionate about bringing privacy protection services to all of web3 menta is 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's anna's episode on halo 2. [Music] so today i'm sitting here live with dara and strad both cryptographic engineers at the electric coin company welcome to the show lovely to be here yeah it's great to be here so dara this is your second time on the show we did an episode in where we talked about halo 1 i guess halo original i'm very excited with this episode to kind of continue on that and explore halo 2 and what's coming up

strad this is the first time you're on the show 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. did dk summit even know it was going to turn into this at that time it did not it zk summit 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 zk summit proposal into a proper zk summit i'm sorry for your loss what's wildest do you remember that first talk i mean high level yeah i was like i was where's waldo i was doing my

best to be like cool um 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 deepest snarks yeah and i'm just going right we've really like we've covered the full gamut i am sure they are gobsmacked but we do we needed that i mean at the time the knowledge about zero knowledge was quite like sparse there was maybe a few people in that crowd who were well-versed but it was wild to see zk summit like one after another and now i don't know if you know this but we're doing zk summit eight in berlin in september so the eighth edition but zk summit is not the only event

focused on this kind of tech the con is as well and we are actually recording this at zcon 3 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 sliced it together it was a lot of work it was really cool though it's a little snapshot into like the world um and what things were happening i'm going to add all of these to the show notes including the video from the first ck summit and i hope people will check that out yeah it was it was a good time it was the it was you know because 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 uh a lot of the wider ecosystem had been able to get together because prior to that it was most of the in-person events had been either just ecc themselves or ecc like hosting something 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 z cash addressed but also like zero knowledge focus conference that was like for the wider community um i mean there was also other things going on like the you know the zk proof's workshop and stuff which were more geared at like the theoreticians and the implementers and things directly but this was something like standardization yeah exactly but this was sort of like the first like zero knowledge is fun let's talk about it totally yeah i

remember it was in montreal and it was um in the middle of a heat wave and i hadn't realized that canada had heat waves but yeah it was it was really what one associates with them although i will correct you straight the um first ck summit actually happened before z-con zero so i think i'm so i've been kind of claiming the first a little i'll oh i'll give you that now you're at it you are the first talk at the first that is fair i will i will give you that it was different though because at the time the zk summit was also just partly zero knowledge focused and partly blockchain general yeah it was yeah it was it was a very um fruitful time in terms of like giving giving rise to some very awesome

um events to uh for the space so i want to hear a little i think it would be really great to introduce both of you a bit more to the audience dara 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 yeah um so i'm the lead author of the zcash protocol specification um i do a lot of work with uh on z cash d with core team um a lot of documentation and protocol design very cool and since we're going to be talking a lot about halo 2 what's the role there so i'm a co-author on the original halo paper i

invented discovered whatever developed the pasta curves so this this construction for kev cycles um that allows recursion in halo and hopefully will allow us to use recursion in zcash and we we have some other collaborations for example with filecoin and the ethereum foundation um that we're also developing recursion for those 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 math has always been there is it it is discovered and it and it's also a social construction like many things

okay strad tell us a little bit about your story and kind of like what led you to the work that you do today well i got bored one day um 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 um yeah it was in real world crypto 2014 um 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 dara and um zucco and i think nathan was there brian warner some some some very fun people um met them in person and actually also listened to matt green give the zero cash talk um and yeah didn't think anything more about cryptocurrency at the time um but yeah that was sort of the connection was made and then a couple years later when i was finishing my phd um yeah zuko approached me and asked me if he if i could um potentially put a little bit of my time towards um working on this uh cool new zero knowledge proof circuitry stuff 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

so i was roped in by the enticement of zero knowledge proofs i spent a lot of my initial years working on not that um i did a lot of the the base engineering for physique hd and um 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 going to do with um with darren and then yeah i i slowly wormed my way from that into the cryptography side um because i've just been able to be around so many amazing people um and learn from

them and and gain experience from them i have a very memorable experience of in early 2017 i was at um ccc so sorry the the congress event that ccc runs in uh hamburg leipzig leipzig well yeah maybe it was like that i think it was like no at the time was hamburg they've ended up they've actually um they're now back at humber because they've uh finished their renovations so i was there um and zuko was there and we were talking to someone and they're like oh zucker you should come to our thing and give a talk about how um 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 sounds like cool i'm going to give a talk about how

zero knowledge poofs work in three weeks types on the messenger sean how does zero knowledge proofs work and i proceeded to pester my colleague sean beau and iran troma who was one of the seven scientists and were both in the messenger you know for ecc uh for the next three weeks and wrote a talk and yeah that was a good way to learn quick yes the deadlines are so they they focus the mind so much very much um 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 uh v was very involved in the in the orchard protocol uh cryptographic design and implementation i just realized i just double checked

something you have been on the show before you were in the combo episode of econ zero 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 want to sort of direct us now towards halo are we here at zcon 3 we've i think i've seen two at least two talks focused on that maybe there was a couple more yeah my talk was on uh analysis of the shielded protocol yeah i gave a talk on um well hello too but focused on the performance aspects of it um and particularly around the elements of the halo 2 proving system and the the things that's built on and

also our implementation of it that help us to leverage the performance and build performance circuits and then my colleague ying tong gave a presentation on the ecosystem and what other people have been doing um with the with halo 2. 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 going to obviously put that in the show notes for anyone who wants to hear that but in this one i sort of want to revisit some of the concepts that we introduced in that episode and then talk about halo 2. i also am kind of doing this selfishly because

we're doing the zk whiteboard 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 that we could do some of these so and then you can tell me i want to understand what they are and then you can tell me how they all kind of weave together so one of them was the inner product argument i was very curious like what is an inner product argument so are you familiar with a dot product i am not excellent let's start there um so if you think of having a a vector are you familiar with a vector i am familiar with the vector linear

algebra cool so so if you take a vector and we take a pair of vectors um the dot product is where you take like each element in the vector pairwise so the first the first in each vector than the second each vector you multiply each of the pairs and then you add all of the um the resulting sums together and you end up with a single value at the end that represents the dot product of the vectors so like it would be the dot product argument or is that the dot product that's a dot product okay so then so the inner product is a generalization of the dot product where instead of it necessarily being um 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 um and there's a few other properties that must satisfy but it but precisely the action that is applied um can be different but overall you still end up with taking a vector of some values we'll call them scalars you take a vector of scalars and the inner product results in a single scalar by by some mechanism okay so then the inner product argument is a mechanism that we use 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 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 half of the polynomial uh separately and then we fold them together with um with some it gives 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 halve the length of the polynomial until you so like the number of coefficients in it until at the end you only have a single coefficient it's like a single

value left and that's every round you're doing that action exactly so at the end yeah yeah you the folding step like when you take the two the low and upper 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 n like it's an n degree probably maybe it's got n coefficients whatever you've done log n rounds because you've halved it each time and why though like why do you want that small smaller one so this ends up contributing to proof size so so each of those rounds um contributes um one element to the proof

um and so you you end up with this log n uh component to the proof if you're committing to vectors of size n but is that does that mean it's small you want it to be small like i guess that's the it's smaller okay 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 would increase by one because doubling adds like one extra layer to the um to this inner product argument okay so 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're um that you're committing to but exactly okay so it's it it helps you in in certain cases with certain efficiencies all right my next word polynomial iop okay so iop is an interactive oracle proof um so an interactive proof is where you have a protocol between approver and verifier and the approver is trying to convince um the verifier and 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 halo 2 it's and a fiat chamois transformation so uh fiat chamber 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 um an interactive oracle proof um so that the verifier doesn't have to read all of the previous messages so so we're trying to generate a more

efficient protocol by replacing these long messages between the approver and the verifier um 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 approver and that means that they can choose some position in the previous message and query that um so that's interactive oracle proofs um and then the polynomial to the front exactly um so if these messages are polynomials then we can we can instantiate the oracle using a

polynomial commitment scheme basically which hand waving a little bit which actually leads me a little bit to the next term which i think we we do here 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 um 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 uh opening that that will satisfy that or one that can be found that is commitment yes that's a commitment scheme i have okay one little side question when you say open what are you doing uh you you're finding proof you're finding an input to the commitment okay the output is the small values that that you call the commitment okay there's this ambiguity in terminology sometimes you should really say commitment scheme

when you're talking about the algorithm okay and so a commitment is an output to that scheme the opening is the input okay cool so now a polynomial commitment scheme a polynomial commitment scheme is a commitment scheme two 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 cool and again this is like this would the commitment is smaller than accepting your checking or you're committing to are they commitment schemes would they where it's larger um i think the definition doesn't

require it to be smaller cool it's more useful for it to be smaller so there's two or three other terminology things i want to do but i think we actually do talk about these quite often on the show so one would be like recursion or cursive 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 halo does away with we don't actually need that anymore it's an mpc but yeah we've done full episodes on trusted setups i think we'll leave that one but recursive proofs why don't we define those okay so recursive proof you're checking a verification of another proof so so your circuit in the outer proof

has the verifier it's checking the verifier of some in a proof and it can check the verifications of multiple proofs so in general you form a tree or a directed acyclic 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 um the proof system then you're effectively checking all of the leaf proofs yeah yeah it's almost like a you're compressing can i mean maybe that's the wrong term but your like information is then being reduced into one small thing that's prov that proves all of it yes uh an interesting thing is that it doesn't have to be just one

party um creating this tree of proofs so um you can collaboratively form this tree and the parties that are generating the leaf proofs can know different things so that this is important in the case of um zcash or any private cryptocurrency because let's suppose that you had a cryptocurrency that that used recursive proofs pervasively then each of the transactions representing the leaves will be generated by some different sender and they would know different spending keys for example i've also i mean recursive proofs of recursion sometimes like i've also

understood it just like a proof of a proof of a so proof of little bit like it's more kind of in a line yeah that that's a special case which is also called incrementally verifiable computation obviously it's just a tree with a single branch and then done over and over and over again yeah or like i it's not i remember oh i see what you're saying okay because each one like as you go down the branch from like yes just imagine having a tree and then you cut off every branch except one yeah that's but you still have these stop points in that right yeah it's actually it's more like having like a it's like having a really unbalanced tree yeah or it's like the rope with the knots maybe is that is that what it

looks like leaves stapled to a pole okay our metaphor this is day three of z con 3 so we are and i 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 this basic building blocks i followed it all i'm very happy about that there are actually competing definitions of what ivc and pcd which is the the general case um stand for and we we've given basically one of them here um and i i didn't really understand the other one 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 well 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 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 cool before we go on to how these all work together i do want to 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 think is it in a completely different part of the math from recursion so what we did in halo was to find a way to do this verification that has to happen inside the recursive circuit um to do that in basically login steps rather than end steps so the

um the final verification of the inner product for the last proof that's done by something called the decider um and that costs linear time in the size of um the outer circuit um but the part of the circuit that you need to do the recursive verification is um a login so they are similar math in terms of uh like they're you're all dealing in polynomials here but they are different components of it i think in that 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 um 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 uh 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 okay so so i think i slightly misdescribed it before it's not that you're computing

um an in a product argument within the recursive proof it's that you're folding together two arguments um in such a way that if the input arguments were valid then the output arguments will be valid in some sense 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 inappropriate argument directly and in fact know 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 in a 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 input diagrams or the multi input arguments from the proofs you're checking into this new one you're just checking them in a way that means you have to produce a proof that itself has a separate inner product argument that it generates okay um that's a better way of describing it than i said it is day three yes it is we both gave our talks today 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 outcome but what was happening under the hood to allow 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 um verification circuit um in the outer circuit to do the recursion

and the only known way to do that efficiently was to use these cycles of curves um 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 um curves that are quite large um at least 800 bits but probably um larger for 128 bit security um probably about a thousand bits yeah the first time i remember this method of constructing a proof system from an iop and commitment scheme

is when mary mallor um described it to me we were in london and we were at this meet-up which was very productive and i learned a lot about how proof systems really worked and the example that mary used was using kcg as the orcate commitments for the polynomial commitment scheme i think she was referring to sonic um or she might have been referring to some some predecessor if it's the london meetup that i remember this was the one that we went to ucl yes yeah that's the one that led to sonic right yes um this was a this was

actually an ecc meetup that we just you know um several of us well both dara and myself were based in the uk and we're like we want some some of our colleagues to come over and um and you know chat about some stuff and so we met up with sarah mary muller and several others at um uh at a meeting and you know one of the presentations given um i think the year was mary mala um and karen was that henry de valence i think 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 uh meeting and

mary gave a talk and sean and dara got very excited and so the next day they were not at the next meeting because they were over at ucl talking with uh with mary about proofs i think ariel was maybe with you as well uh i can't remember i i do remember that she explained um grot 16 to us oh jen scratch was sir oh hopefully i am so glad i missed it one thing you mentioned sonic 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 that's another one i can link to in the show yeah so so it was that um meet up and and talk that i think that's

what got sean talking with mary uh on this and that's um sean and mary are both co-authors on the sonic paper um so when it came to halo um the main reason that halo was built around a sonic style polynomial iop is because that's what we had to hand got it the the core innovation we were focused on was not the proving system per se it was the recursive accumulation technique and putting that figuring out a way to describe it so that other people would believe us that it worked yeah and the reviewers did not believe us

that it worked yeah it uh it was a very um busy week when when sean uh mr justin went i think i have an idea and um 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 going to 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 wow yeah we we did not expect this property that you can do the thing that you need to do inside the verification circuit in um 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 wasn't anything spectacularly innovative it was just the obvious way of doing it ended up being taking only logarithmic constraints 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 so brutal 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 second and 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 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 scalar field elements of that particular curve now in the context of a circuit it's sufficient 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 wrongfield arithmetic that are actually like somewhat more viable but it's still like it is definitely more costly to do wrongful arithmetic um and it can it can affect where your recursion threshold ends up 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 so we're essentially doing like three proofs worth of pieces in one at in any particular proof that isn't the initial one in the in the recursion um cycle you are generating a new proof that needs verification that proof is verifying the main body of the proof and it is also verifying the tail end deferred pieces of the proof before that wow is that was that a new technique or had anything like that been done before

uh that was a new technique with the original halo paper yeah and this was then the technique that was generalized and formalized in the um vcms20 yeah bcms-20 which um was the paper that um uh presented at uh z-con yesterday i think no um that was a newer paper he mentioned it both it was both there was there was a 21 paper as well uh but he mentioned he he discussed it um at his talk yesterday so there are there's a video to watch for that as well yeah that that talk was um well it was about the previous paper but it was also about um split accumulation yes which is a generalized thing that they then figured out on top of this idea

very nice yeah and it has to be said there are other ways of doing recursion so for example plonky 2 doesn't require this um deferred arithmetic because it's using um a fry based proof system so that doesn't require different fields you can use the same field all the way through what fry based proof system are they using it's similar to the one used in stock so i think it's deep frying okay i wanna ask now about the transition to halo 2 like this is a new like what is the difference between halo and halo 2 what's changing the main difference is the arithmetization

so after and roughly the same time as we published the halo paper it was snoctember which was this month that was absolutely spectacular in terms of um publication of of new ideas all of which turned out to combine really well with each other i think mccarra from hashcloaks may have coined that shout out so so after september it kind of became obvious eventually that planck style arithmetization allowed some optimizations that weren't possible in r1cs and so you had other proof systems

adopting this plunkish arithmetization for efficiency gains yeah is halo 2 plonk under the hood um you just said so go there plonk the paper yeah and plonk the arithmetization of two separate things okay so the plonk paper was a full proving system a proven protocol including an arithmetization the same way that r1cs was an arithmetization introduced in a 2013 paper um bcg tv and that i believe also had a um a proving system that was it was deploying that yes this was for

um so we just looked that up by the way we didn't we didn't remember it um so a little edit in there yeah so the plonk paper deployed a particular arithmetization then there were several other papers that built on it um turbo plonk i think was one name um i've heard ultra plonk i don't know if that's ever made it into a paper or if it's just one there is no ultra punch paper but i think ultra plunk is a is a term that's um that uh was used for like a particular instantiation there are a lot of different things that have been used with the name plonk in it i may have misheard this in my interview

with aztec but i thought i heard octo plunk but i don't know that's the thing yeah i don't know specifically it's i think it's with eight advice columns something like that 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 i go into a significant amount of detail

about these in the talk i gave this morning at zeecon 3. in terms of how to leverage this extra flexibility um for performance so the main difference i think between plank and r1cs is that planck gives more flexibility in the polynomial constraints that it's enforcing so for r1cs you're just enforcing a set of quadratic constraints um so a times b equals c where a b and c are linear combinations so for planck 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 defined

custom gates for everything i do i think it was fine i i honestly think that the the ability to define custom constraints is like the one of the hidden superpowers of the plonk arithmetization 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 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 yes but do you also use techniques like lookup tables yes so they come from um so yeah the original paper didn't have lookup tables it's newer yep later ones did so we so

have the halo 2 proofing 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 plot papers i believe to define um global equality constraints that was in the original problem that was in the original paper okay so both of these are built around the idea of a permutation argument um 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 of the 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 um these cells in disparate polynomials all of these um values represented by components these polynomials are in fact required to be the same and the lookup argument gets a little more uh interesting but it relies on the same kind of thing under the hood we were inspired by the pluck-up paper but we actually use a different argument than the one in that

paper i think partly because i didn't fully understand the pluck of paper at the time um do you understand now because um yeah as is often the case um if you know that something is possible then you can do it in any of several ways cool um and we chose a way for engineering reasons that that was a little bit more compatible with the rest of halo 2. yeah um it is like it's slightly i think less efficient for certain usages of lookup tables i believe the way that lookup works you end up you end up using like the polynomials used in the lookup tables once uh across all of the lookups whereas i think in in the way that we've defined ours you end up using the same

polynomial um if you do if you use like a sub component of a lookup table in multiple lookups um 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 integers like from zero through to like you know ten bit integers um so away to two to the ten minus one and for each of uh those values in your table you then have like an elliptic curve point uh x and y coordinates so we use this for um since amir our particular hash function that's optimized for this kind of thing but you then also happen to have a list of numbers from zero to two to the t minus

one and you can use sub sections of that term column to also do range constraints where you can say that something can be say a ten 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 going to be a valid 10 bit number but yeah the the way that we do it it means that we end up using that that 10-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 when you incorporated these techniques of plonk was it easy was it like halos 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 so um a big chunk of work is just understanding the original system um well enough to be able to adapt it okay um no it's it's not easy and did you have to start again kind of we did yes um but we were going to do that anyway i think so the original halo implementation that we published along with the paper um as i mentioned we wrote this all in a week hackathon style we are not really a fan of productionizing things that we write in a week fair there was certain liberties we took with

the api and so on uh in order to get a demo working a proof of concept working um but at the same time we had come off a multi-year development process uh for the bellman crate which is the the rust prover library that sean started writing that we've then since um we then used for the sapling protocol it's also now used for sprout um and which is an r1cs based proving implementation that implements uh yeah r1cs and then grout 16 under underneath um and we had learned a lot from both the original sprout circuit and and the libraries it was built with we then learned some built on that in

bellman and so we were taking the api uh 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 uh 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 i i think actually we underestimated the complexity of the api that was needed to handle plunkish arithmetization especially especially some of the abstractions that we built on top like regions gadgets chips which are described in strad's talk as

econ 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 um building on the halo 2 crates and they seem to be having a lot of success cool yeah the the end result of what we've sort of ended up with um is that we have so we have the plonk style arithmetization that we use we with quality constraints and our lookup argument similar to vlookup and then that gets boiled down into a series of polynomials per the way that planck arithmetization works once you have those polynomials

then it transitions into sort of a more um traditional i mean the how how long have people consider this traditional how how long does it have to be before uh before we consider it uh folklore um 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 contains all of our circuit to be zero so we do so by proving that you can divide it by a target polynomial um and show that there is no remainder that's that's the traditional way that's done for like grout 16 proofs do this um i forget it's precisely the vanishing point 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 trickeries here and there to make um certain things work within degree bounds um 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 or polynomials were lined up and so if you think of how plonk like you can have a concept of like rows and columns for planck 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 um maximum degree approximately and so you have to work in an extended domain to do computations of 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 um to sort of make the vanishing argument work 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 yeah we had we had one version of that and then once the security proof um physiology got to the point it was like okay um

we we now know that like we are unable to prove that the thing we're doing here is secure we went and did a slightly less efficient thing um in that part of the vanishing argument to make sure that we could ensure that the thing that we were going to deploy was probably um zero knowledge it's interesting that um a zero knowledge bug um it's mainly a theoretical bug rather than something that is actually exploitable a zero knowledge bug was found in the original planck paper and that affected quite a few implementations um that's all public now so i'm not revealing any security flaws that aren't already known but that also there is like there's uh there's that comes also back to planck

the paper also had a proving system and so implementing that proving system from the paper had that warriors 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 are there any other innovations highlights that you say halo 2 is bringing to the table maybe optimizations techniques um i the thing i like to so like halo 2 as i was as we're describing before is like the actual components of it are independently reasonably well understood from a theoretical perspective i think the the remaining piece um

that was left after doing the vanishing argument is just um you have to take that and do some evaluations and then do an opening argument to sure 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 arithmetization efficiently they've been various people working with um 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 um very specific performance requirements that

uh that we need to meet and in particular here we had an overarching desire for the performance of um the circuit orchard that we built with it to not be horribly worse than the existing sapling um circuit that uh that was used because we want it to be possible to for people to migrate and and still be able to use it the way they use sapling yeah and a lot of the the work that 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 um that were that were reusable in this way um and we had to build all the the elliptic curve arithmetic uh gadgets were the

worst yingtong did absolutely amazing work um yes building those really spectacular yeah and yeah between those and then you know you had things like poseidon and you know the merkel gadgets and smear on top of that 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 um and you know coming up with figuring out

okay what kinds of things are we repeating what kinds of abstractions can we build to um to make this easier to work with and so like as dara alluded to earlier um 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 um we we define a small like bounded rectangle within that where we say okay in this region um the relative offsets that you can use with like um plonk constraints you know custom constraints they're guaranteed to be preserved because one of the things that you have

with plonk is that your your constraints are effectively two-dimensional unlike r1cs where you they they are minimally interacting with each other and so enabling you know the use of that for low-level packing um 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 um but by introducing that concept we could then start doing automated optimizations uh on over the yeah 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 toolchain world and also the um the cpu architecture design like designing silicon chips or fpgas world um both of them sort of feed their way into like circuit design is almost both of them at once and 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 so anything that transforms sort of one expression of a program or a statement into another expression is a compiler okay so is it

in the building thinking like the way you're developing it that you're using this compiler tool no what we're building is the compiler tool to be used within within well it's in intermediate so the thing that we're building is you know the proving system i 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 trend 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 so if you need to use a certain amount of rows and columns how do you use the 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 uh 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 halo 2 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 um 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 belt cause you mentioned bellman is it still bellman it is 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 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 dear cells on our team there's also there are a lot of dsls so you might want to see if there's any out there yeah we probably want to reuse the dsl yeah we certainly have people who would very much like to build deer cells no i said have the time to do so um yeah so as i was saying for 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 um but the the input doesn't have to be a text file it can be calls 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 yeah like right now the the situation is that you can't actually do it this fully at runtime 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 uh

which columns are being used by which sub components which uh chips used within gadgets and so on terminology that uh that uh we also sort of like came up with some other abstractions um 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 so strad 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 different rows of the circuit and so what you end up with in a circuit especially like orchard that has lots of different um custom constraints is you end up with lots of these binary selectors um and so we have this um optimization originally i tried to do this optimization manually and then we decided it didn't that didn't make sense we could do a better job doing it automatically where you

combine several selectors into a single column and then you reconstruct the original selectors by interpolation from the the compressed selector cool and that reduces your proof size because you have fewer columns there's other ones we've discussed and had things thought about over time but uh that we haven't got implemented yet so there's more fun that can be had in the future like halo 2 it's comparable i guess than to plonky two how do those kind of match up um so i guess um halo 2 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 planky 2 is 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 plunky too and there's also potentially interesting like um cooperation that can occur between these so you saw a bit in the in the r1cs era as we can call it now is it over uh yes there's still a lot of grass 16 out

there i mean you can build a um plunk a plunk arithmetization that that hooks into growth 16 if you really want to 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 vira frontend that you could then pass that to a back-end tool to do the do the final proving and i could in definitely see something similar happening happening here for example if you know if i've not looked at plonky 2's um 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 halo 2 as a as a back end that could then run through our optimization pass similarly vice versa or vice versa and you could even i could even see a thing where halo 2 proving logic is split into 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

asterisk asterisk we really you know have to be careful in the optimizations we implement um representation of the circuit and then take that and port that over to say plonky2 or some other system for final production of the proof that you care about wow so this would enable different teams to sort of like work on the things that they are good at and and leverage you know um leverage the other work that is being done in a in a more modular way i love that idea i want to 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 the new shielded protocol the new shielded protocol and the last one was sapling that's right and that one if i

remember correctly sapling was the introduction of graph 16 yes and so is this replacing that part then is halo 2 instead of so so some history um remember that the proof system that we originally used for sprout called bc2v14 um had a soundless floor um so so we could have fixed just that soundless flaw but instead we decided to to move to grout 16 partly for efficiency reasons as well and sean re-implemented the sprout circuit on grout 16. so both sprout and sapling now use that and then when we move to orchard and then when we've introduced orchard

um that's using halo 2 and the previous um shielded protocols are still using growth 16. oh okay so you're using both yes oh interesting 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 um trustless proving system there is it because like is it the way it's built you can't switch that over without losing somehow the balances so growth 16 needs pairing friendly curves and so it's more efficient to keep sprouting sapling using

grout 16 on the job job curve and bls12381 sprout doesn't actually use any elliptic curve arithmetic at all it uses um it's inefficient everywhere yeah exactly but implementing the sapling shielded protocol on halo 2 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 grout 16 and um bls 12 381 and does each does each upgrade have its own pool like is there still a sprout and a sapling and oh wow okay i didn't realize it was yeah the you could in fact have more the more than one pool if you really wanted to um

nathan gave a talk where he proposed that idea um and has done in the past um but for now what we currently have is each shielded protocol has its own um pool of shielded pools so if you want to move funds from one shielded protocol to a different shielded protocol you have to first 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 um 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 the previous pools um design plus then you get some insulation um between the two yeah you can completely change the cryptography if you want to as we have done for orchard yeah one way to think about orchard is that like if you understand sapling you understand orchard um 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 dara said um implementing sapling with its existing curves on top of uh

the new curves would be inefficient so we want to just do the sapling protocol rather than the sapling pool in the new curves and that's what gives rise to orchard 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 it's mainly just cleaning up things like the key structure to strengthen the properties that we have from viewing keys some optimizations like using a commitment scheme to generate ivk from a full viewing key instead of a hash and things like that 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 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 like does it have higher capacity what's uh why do an upgrade uh so it it's future proofing basically because we we know that we will um 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 um something that was um implemented for um bitcoin in segwit uh we've taken a slightly different design approach but the the effect is the same there were a few things that users would notice about orchard itself um for certain kinds of transactions orchard proving is faster um for 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 uh spins and outputs so well for efficiency purposes effectively you could you could add a bunch of outputs um with a few spins and you can tell that like it is few spins many outputs rather than many spends few outputs with orchard going back to an action model similar to what sprout had now if you want to pay too 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 spin side is more efficient effectively overall um in orchard cool i want to say thank you so much for doing this dive into halo 2. dara knows this i've been trying to get this episode to happen for i think almost eight months 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 it's been a pleasure yeah i'm very happy to ramble 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 it's been a pleasure to do that and um to do this podcast with you yes and 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 um 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 uh and more

developer tooling for people to figure out what's going on when they're doing so and the next step is definitely higher level languages oh yes which we somehow keep avoiding ourselves but [Laughter] cool well thank you so much i want to say thank you to the zcon 3 folks for letting us have this room to be able to record this episode i want to say thank you to the zk podcast team tanya rachel and henrik and to our listeners thanks for listening you