ZKPodcast: Halo with Sean Bowe and Daira Hopwood from ECC

Transcript

[Music] welcome to zero knowledge a podcast where we talk about the latest in zero knowledge research and a decentralized web the show is hosted by me Anna and me Fredrik so today we're sitting with Dara and Shawn from the ECC or the electric coin company welcome to the show hello good to be here I missed you and we have Frederick here hello hello and we've had Shawn on before but we've never had Darrin maybe we do quick intro

to Shawn and then dig into a little bit of your background era yeah I'm excited to be here yes so I work in research and engineering at the electric coin company so I've been doing a lot of the engineering of snart implementations and circuits and also research into more efficient protocol designs and new new start and according to my Twitter you're an alien who came to earth to for the zero knowledge proof science there's a lot of those actually and have what you Dara what's your what are you working on at ECC and maybe since is the first time you're on the show give us a little bit

more of a background on how you arrived at this space so I do protocol design and specification and documenting the protocol mainly unser engineering as well so I got interested in crypto and the subscription was in the 90s then I it was the maths that kept me here I love maths and it's great to be able to do cutting-edge maths very job not many people can do that had you studied cryptography or math in the past I did a degree in maths and computation but not really cryptography so that's self-taught and then I was working on

research in capability-based security so that's a security model where you use unforgeable reference these references to things to express security policies and there was a project called Tahoe le FS which is a distributed file store and zuko is involved with that so that's how I met Zuko and then I started working for least Authority which was a startup supposed to commercialize to our AFS and then from that I went on to see cash we've actually had Zuko on the show I think he was episode 50 we've also had Liz from least authority on the show as well and so I'll add those in the show notes if people want to find out a little bit

more about those projects so that was your route to the ECC was there I mean previously the C cash company at what point is sort of zero knowledge proof or that kind of snark research really enter into your world so Z cash was an association of zero cash and that paper had already been written that it uses sarah knowledge proofs so from the from the time I started that C cash we were all learning how to use Sarah knowledge proofs and which we all had to learn from scratch and that must have been a funny time to learn it because at the time and and this is to you to Shawn

like there must not have been very much documentation around this stuff there wasn't the kind of like educational resources that were starting to see emerge around it right a lot of it was folklore and learned a lot of it from each other yeah yeah there was just papers and working out from scratch really know when Z cash started did libs mark already exists and like was a thing that was considered stable and he'd like at Z cash just went with it or you know where did the Lib snark exist in relation to Z cash so there was already a prototype of Sarah cash that used live snark and we ended up rewriting all of

the code in that prototype for we still use live stock I see and then at some point down the road which we'll come to later I'm sure you rewrite lib snark as well and ended up being bellman yeah it's Sean beretta and rust when did you write bellman so I started working on them and you know before I even worked for the company and we talked about this a previous episode but it actually ended up being a little true lipsmack replacement only around 2017 or so even though it did start back a little earlier than that and we've we've now completely replaced live stock with common cool the last time i think we touched on ECC news was with you Sean

which was possibly almost a year ago I think it was a so maybe we can just talk about like what has happened since then and maybe what were your focuses like from that point onwards in the company so in early 2019 obviously I was a co-author of the sonic paper and so that was kind of my focus was actually instantiating practical universals trusted set ups and i thought that was a really good direction there were some other different directions like no trusted set ups it seemed like they were getting better and better and also these hybrid models like sharks which we can talk about later so there was a lot of

interesting things happening and I was sort of looking into new constructions and trying to see what the next thing after sonic was and meanwhile Dara was doing scalability research those kind of go hand in hand when it comes to Z cash because snark constructions are a really integral component of our scalability plans as far as we can tell they're very crucial for achieving performance that we need in practice yeah it's important to have the emphasis of writing a paper or preparing for a presentation to actually get research done in my

experience so in my case the emphasis for doing that initial scaling research was I had a presentation at C Conn Wong yeah so that's why I got done on time but I've since refined it I'm quite a bit this isn't the first time I've heard of a presentation driven develop I remember that talk at Zeke on one this was in Croatia and split croatia last summer and in that talk you had specifically highlighted this idea of like moving Z cash into it like a sharded system potentially so I'm wondering kind of like what I've always

been like a little bit curious about like how far that went like I as I understood it was like still very much proposal like kind of like research phase at that time what what kind of where did you go with that idea i'm--it's dollar proposal so we have a plan to deploy some kind of scaling solution by 2021 so that's the plan but there's a lot of work to do before then and there's a lot of detail and optimization and design choices to make and I'm curious to hear how this work came about in the first place because I remember talking to Zuko at I think SBC 2019 so that was well before that

presentation and I know like he's tweeted talking to a bunch of other community members and metallic and this and that and like I know he's been like going around trying to gather ideas for how we can scale Z cash I don't know like does that make it into the company and then gets like selected and percolated within the company or is it that really like a separate thing and it's you know the company researchers like yourself are coming up with their own proposals well we're always looking looking at what other people are doing at the etherion people have come up with some really interesting ideas recently in last few months even in the last week but even before that I think we'd

learned from Bitcoin and because Bitcoin had a huge political issue about how scaling should be done should the box size be increased and so on and we wanted to avoid some of the political strife that had cared for a Bitcoin by was thinking about this issue a lot Leigha in in the sort of the lifetime of the currency obviously bit kindness had years long ago one of the things that kept coming up this was back in late 2017 so you can kind of see why but anytime we pitch the cash to an exchange or to a new merchant or something like that one of the things that we heard

across the board was well what's your scalability plan and that's just it was a meaning back in 2017 but it became a reality for all the projects in the space and now everyone is expected to have some sort of long-term plan on scalability and that's why it's such a focus and in the etherium land and the in the Z cash land it's a little more complicated because we have to get scalability and privacy at the same time and not just mediocre privacy that's pretty easy and a lot of people have shown how to do that was with scale but we have to have the strong ledger indistinguishability property that underlies easy cash and that's a really

difficult bar to reach so a lot of this a lot of this started very early on in the Z cash project where we were pondering like where are we gonna go to appease everyone and make everyone know that we're taking this seriously and also what is realistic what can we actually deploy yeah I mean we've already made some scalability improvements we we started off with double the block size of Bitcoin and a quarter of the block spacing so that gives us an eight times capacity that's right from the beginning you mean that was right like right from the start like

in their actual like Genesis yeah I'm done okay and then more recently with the blossom upgrade we've half the block time again so that's 16 times relative to Bitcoin although they've they've introduced sacred which makes things more complicated for them these are of course constant factor improvements they had correspond with improvements we've made to the performance of for example or stark verifier and things like that that of all that we've been taking into account but the kind of scalability challenges that we need to address going forward or more architectural and also they affect the user interface pretty significantly so I guess I was just thinking like skate like scalability in the Z cash context

just a little bit different because you have this sort of scaling of the general blockchain but then you also have the speed-up of the snarks because if you want to be working in a like in a more shielded environment then you're gonna actually have to have faster Starks and faster snarks would on some level also mean faster blockchain which I guess you would that falls in the scaling category as well yeah faster user experience I suppose yeah yeah so so we made huge improvements with suppling and I I think actually the proving performance for making payments is quite acceptable on desktop at least maybe it needs further improvement on mobile and for Hardware wallets but the verification time is what determines so the network capacity

so this is for the snark specifically well it's not sun signatures because they're both significant we couldn't keep on doing of greats like blossom indefinitely because we would ended up a situation where if someone is doing a denial of service attack then they could just fill blocks with snarks and they would take too long to verify there's also I mean when you think about scaling in those terms you said Anna there's also diminishing returns - like the UX side of it right where as a user as long as it's less than a few seconds I don't really care anymore like it doesn't make a huge difference if it's two seconds or one second but the amount of engineering required to have this the

time again when it's at that threshold is huge yeah there's a lot of different time-related UX issues some of them are latency between you and the network latency between you and getting finality of your transactions so you know it's irrevocable they're like exact what the interaction between you and the recipient is and how many steps you take or how many rounds of interaction you take in most cases at zero but different architectures of payment designs can change how that works and there's different trade-offs and then there's also consumption and I mean if you want to receive payments privately it's

really hard to make it trade-off between not communicating directly with the sender to for privacy reasons or receiving an information and a broadcast network like a like Z cache is currently where every transaction is sent to every user and every user has to decrypt or attempt to decrypt each payment to see if it's actually for intended for them there's also the issue of how long it takes between when you've received a payment and when you're able to spend it again there are you touched on something I think is super important which is the political aspect and I wonder how you guys see that and in like scaling

charting these kinds of things where you know aetherium took the approach that this is just too hot to touch we're not going to be able to deploy anything to the existing network we have to create a whole new network and then figure out some way to bring the old users over eventually but that you know introduces a ton of complexity it's just in and of itself I'm actually fan of that style of migration personally because especially for the Z cache case because we built on top of Bitcoin so there's a lot of legacy cruft that we just want to burn down and starting from scratch is a really nice way to like make the right decisions from the first place it is really

contentious and Athenians case but there's a lot of other factors that are going into that I think than just just this strategy they're taking to migrate I I'm all in favor of burning the districts but that's a small talk reference so yeah the Bitcoin code base is terrible I I have returned into trouble with a Bitcoin developers for saying that but it is and the version that we forked from which was zero eleven - we've been able to do some refactorings and pull some stuff some improvements in software engineering practice from upstream but that's actually really difficult once the code base is diverged a lot you know

as someone who has worked on re-implementing Bitcoin even when you take a from scratch reimplementation you end up with something that isn't very good just because of the way things are designed like you there are bugs in Bitcoin and you have to replicate those bugs and it's yeah you get into weird territory that that's exactly right and there's also the fact that eventually we want to remove T addresses to remove the transparent parts of the protocol not just because of protocol complexity and potential security problems but because you get much better overall anonymity sass and privacy properties if everyone

is using show that yeah well I didn't know that that was actually the plan to like eventually remove the transparent I always I always thought there was like strong encouragement to use the shield at accounts so I'm not I think perhaps plan might be too strong a word for it I know that as engineers are pretty keen on that approach there's a there's a lot of political considerations like for example just the fact that there's so many people are using tatters currently it's an interesting on-ramp to the actual currency it be it's completely speculative but I'm pretty confident that Heather not existed theaters there would be a lot less Z at or usage for surely because of the accessibility so

there's an advantage to them I think what we want over the long term isn't necessarily getting rid of T adders well I guess we do want to get rid of T adders for architectural reasons and simplicity reasons but what we want is for transparency to be an explicit decision from the user in the form of things like payment disclosures and feeling keys and other other tools like that but that privacy should be an easy thing to get by default it's also the the issue that we can't do some of the things that Bitcoin does in z:k Schnucks so we probably can't support Bitcoin script in TK snacks we wouldn't want to

live yeah in fact the full generality of Bitcoin script isn't really being used on the c cash network people are using Elizabeth multi-sig in fact I think over 95% of the script usage is just multi-sig so people are not using more complicated things and if we support shielded one T 6 and that will replace that functionality so what does this scaling situation look like today then so we do have a tentative plan for a scaling proposal and then so dara'a been working on and there's a lot of actually there are very few open questions left but a lot of work ahead to address them yeah I've also been looking at other

scalability proposals that have a privacy component there's a account based anonymous roll-up been proposed for cerium and that has some interesting ideas so instead of we're in Z cash all funds are held in notes and there's no distinction between and the notes that you hold yourself and the notes that you're transferring to some other party in the account based on anonymous roll up those are distinguished and you have money orders which are how you send funds to another party and that has some advantages so you can because you know that a money order is going to be redeemed fairly quickly you can reduce

the size of the accumulator that you use for that so we we may actually end up taking some of those ideas and combining them with my proposal there's another so that would fit in quite well with an idea that we've had called liberated payments and that might not be the final name of it which is you you just send a message to someone and they have all of the information needed to to use that payment and you can send that message over existing communication channels like a signal or telegram or whatever so sorta you just mentioned sort of the zk roll-up model and i and i could understand that there's like more

of a architectural component that you're thinking of using but like z cash doesn't currently allow for smart contract writing so it can't do like can it do kind of this off off chain and then like batching like you know bringing these sort of validity proofs on chain is that something that's actually possible with a z cash you take so model or is that like yes so assyria makes it easier to experiment with these things because you can write them in smart contracts but if you have a specific design that you want to implement then you don't need smart contracts you can just bake it into protocol i forget about that yeah that's

true yeah yeah you have control over the client you could definitely like decide yeah and and supporting smart contracts makes everything a lot more complicated you yeah it's what scalability and privacy and smart contracts at the same time and we only really know how to do two of those things so from the scaling sort of set up that we've just made giving a little bit of background on why scaling is important and like what ideas had already been floated through your work on this i understand that like the concept the the sort of halo proposal was born and i'm really curious how those things link together so maybe you can tell us a little bit about like the

origin story of halo and yeah a little bit about what it is yes so last year we were in the midst of this scalability design discussion we were thinking about ways to achieve more efficient recursive snarks so this is something that code is doing you've had previous episodes talking about this the episode with Isaac in the episode with the authors of fractal and at the time last year there was only one known way or actually realized the way of achieving recursive snarks and

this is actually a very significant component of our scalability plans and so unfortunately that way of doing recursive snart's is really inefficient it required these cycles of pairing friendly elliptic curves and they were really gigantic curves that were not not very efficient and used large fields so I had this negative impact on the user experience when you use the elliptic curve points as like King material and things like that so we wanted to find a more efficient way to do recursion and so I think it's econ one we were talking about these various ways to get more

efficient carrying friendly cycles or to do these new designs of arrangements of curves but we didn't really get anywhere it's interesting to look at exactly why there's only one construction of pairing friendly cycles and that's because pairing friendly curves are a very small subset of elliptic curves that could otherwise be used for cryptography and you have to construct them with the the field size according to this polynomial and then the order of the elliptic curve is another polynomial and you have to make those match up between the two and curves in the cycle and that's the thing

that is difficult to do and there's only one known construction that does that and but if you remove the restriction that one or both of the curves appearing friendly then it becomes much easier so I think after Z Khan I thought why not just use BN curve cycles and there's this interesting insight where as long as one of the curves is pairing friendly and you can build a succinct proving system on top of the pairing friendly curve it doesn't matter if the other curves proving system is to state or not and that gives us the flexibility to build recursive snart's using a cycle like a BN curve cycle

where one of the terms is pairing friendly and the other isn't what's a BN Curt what what did you just say BN they're Breton area curves these are the curves that they deployed in a cerium and they it was also the curve that we initially launched does he catch with one of one of these type one of these curves in this family of curves and you can build different cycles depending on what exactly you're doing or what your requirements are so I posted this idea in our github by the way our github is just like a treasure trove of ideas Darren I love to post our ideas as soon as possible on there yeah well usually to preempt patent trolls if they show up claim they came up with an

idea but sedara is really good about taking your ideas and making sure they have a vision I usually treat them as well yeah so this this was an interesting starting point because I thought okay we could we can make recursion but how efficient will it be and I thought it at first using this style of recursion that it'll be really slow but I thought okay let's let's implement it anyway just for fun just to say we did it and in the process of doing that so I teamed up with with Jeff Craig strat and Darrow and we started working on an implementation and of this style of recursion and we realized that

we could make it much more efficient as we were implementing it as we're optimizing it we were discovering like fundamental tricks that we could use to improve the performance in practice and one of those tricks was this thing that we refer to in the Halo papers nested amortization and that'd be the best name for whatever it is whatever this trick is doing but essentially it's like a protocol between the proving system on one curve and the proving system on the other which is really interesting it allows us to sidestep this requirement of doing these expensive operations to verify the proofs that on

the proving system that isn't on the parent friendly curve so it allows us to massively improve the performance of recursion in that context and then we can take it even further by not using any pairings and getting a fully recursive proof without using a trusted setup at all but like the sonics paper was out that was out at the beginning of 2019 and that also has this you know Universal trusted setup so that's where it's like allowing more people to join but in this case you it sounds like you started in on a very different problem and like did you take anything from Sonics like I always thought of like Sonic's is the

first step towards their trusted set up but this sounds like it's coming from a very different place yeah there's this so the halo papist so the halo construction is built on top of this primitive called the inner product argument which is used it's from a paper that precedes bulletproof but it's used in bulletproof sand a lot of people call it just refer to it as the bulletproof scheme or whatever but I don't think that's a fair description of it but hey so you can use this inner product argument to build a polynomial commitment scheme and actually this is what was done in in sonic sonic took this old polynomial commitment scheme from 2010 this Perry and based one and

used it to build a universal snart and so kind of from that starting point it's like a simple way of getting of starting to build a proving system that it's a way that plunk and all these other recent snarks build on top of just this simple univariate polynomial commitment scheme so this inner product argument actually had this structure that we kind of accidentally discovered where you could do this that we did in Sainik where you could check a lot of proofs at one at the cost of just checking one and this was the one of the fundamental components of

this nested amorous amortization strategy that we used actually make recursion possible in fact so bullet proofs sonic and halo have another thing in common which is that they use the same circuit or thematize asian so you have multiplication constraints and linear constraints which separate unlike in our 1cs systems it actually gives you most of the advantages of our wants yes because you could still do linear constraints very concisely yeah so actually when we posted the halo preprint publicly this was just a couple

days I think or something like that after the plunk paper was published and so and this was before I think the marlin paper was published so there was that I mean in September there's a lot of papers and so but halo isn't really like on the inside of halo it uses Sonic's proving system but it can be just swapped out for any of these newer things that are built on poem intermittence games like Marlin or clunker Splunk or whatever all these other name can you go back to the this nested amortization amortization how like what is the amortization part like what is that first of all what does that

word mean in this context well so when you are usually checking a bunch of proofs let's say you have 10 proofs and you want to check them you pay some fixed cost per proof okay and something that we introduced in the sonic paper was this idea of sustain this after amortization where you paid you you pay you okay so you allow a third-party helper we called it to created a proof that all of them all of the proofs are correct and some batch of proofs and some fixed batch and

that proved itself costs the same to check as all of the individual proofs and so that allowed us to sort of cheat and say okay after amortization we achieved something like succinct us and then obviously in the sonic paper we went on to actually show that we could get full sustainers per proof and in a really expensive way that was improved upon by it Blanc and Marlin but it turns out that this this strategy of compressing the verification time using a third-party helper to create that like a what we call min vise string it turns out that this fundamental tool allows us to sidestep even the need for sustained

us so this nested amortization strategy uses this in the following way so rather than checking a proof completely which is something that's expensive to do and the proving system can't do it because our inner product argument is very expensive it's linear time to check we allow the prover to build an advice string to convince the circuit that the proof is correct and then we take a bits of that advice string out as public inputs to the circuit so that the verifier of that proof has to check that advise string and then it happens again

we combine these two advice strings together in the next version of the cycle using another one of these advice strings and we just keep doing this as we recurse as we bounce between the curves and then eventually on the outside of the circuit you check the advice string to see if it's correct I'm something that that might not be quite obvious from the paper is that this doesn't have to be a linear train of proofs it can be a tree of proofs is that is when you say a tree of proofs are you talk like is this like a Oracle tree style thing or is this like are you talking about like a is this the recursion

sickness that is this tree yeah the the structure of their occasion can be a tree I see yeah this is in practice this is what you would do this is what Koda does for example it's the only thing that really makes sense so you're proving everything at the leaves but the leaves can be constructed by people who know different things which is very useful I mean I just remember doing a study club on Sonic's and like there was all these optimizations that you had kind of come up with so what what are the optimizations for halo that you're working on yeah there are a lot of them actually so one of the the interesting ones is and that we make use of a an enter morph is Aman the the curves that we use so it's actually similar to the

sec p25 6k one curve in Bitcoin they also use exactly the center morphism and basically allows you to do multiplications on the curve more quickly this has been known for a long time and there's a there's a patented version of it but the version we use you don't take a random scalar and then decompose that into the operations that you want to use with the end of morphism you do it the other way around so you you start with some random bits so say you need a challenge which is 128 bits as long as you multiply by some scalar that has 128 bits and Trippi you're fine

I'm not sufficient for the security of the scheme so you just take the random bits and you plug this plug them into this algorithm that at each step it either subtracts the base point or adds the base point or it subtracts the base point with the endomorphism applied or it adds the base point with the endomorphism applied and that's four possibilities so using what two random bits of each step what does endomorphisms so it's a mapping basically oh oh it's like a morphism like what do you call it an why is it endomorphism that um because it's mapping onto the same structure oh so it's a nothing from a structure unto

itself and it's a nothing that preserves the group operation so this means that it's equivalent to a particular multiplication so multiplication by some scalar you're the fun episode exactly try to reference that episode in our episode with metallic and I completely lost all the terms and I ended up saying that you look for an elliptic curve of unknown order which probably doesn't make sense at all and what I actually wanted to say is unknown and a morphism

ring and I thought you were corrected on Twitter yeah which is great so what was that like you just sort of said this you you didn't you didn't necessarily start on this path with like a very clear goal it was more like you started to explore something and you started to tease at it and that's where you found out that there'd be this potential for for this protocol and I'm I guess when when I heard that I was wondering if like that is that how like the ECC usually works is that it do you have sort of the freedom just like explore in certain directions even though they might seem super inefficient and like how would you how would you make a choice to do that because you only have limited amount of time I think this is like a new thing

for us I think most of our previous advances and improvements we've had we've just thought of them but in this case it was unintended to actually run into these discoveries and it's kind of made me think that it's a good practice for other people to try if you see something and someone tells you oh that's gonna be too inefficient try implementing it and then see what kind of clever ideas you can come up with and the more experience I guess you have in engineering and design of protocols the more likely you are to run into some new improvements it was also really important there were three of us

bouncing ideas off each other because I don't think we would have found these things even if there were just two of us and the three of you you're all engineers yes yeah most primarily so you're not necessarily like you would you would you also fall in the research camp I think so I think we all have contributed to like very novel ideas I think this part partly just because we the first people to actually deploy start so we managed to kind of run on this untrodden ground so but yeah yeah we fall into the research camp I think that's Malley as well as for sure so

you're sort of like the hybrid researcher engineers who have gotten together to try to like to look at problems that everybody told you were impossible to make more efficient I think you do have to have that engineering experience and to know what direction to head in because you have a lot of protocols whether it doesn't look as though the experience of what can be if it implemented efficiently as guided the designers the protocol so that's very important yeah I think I think in two ways I've experienced this in the past in one way were like years ago when I think it was Ian Myers was telling me hey why don't we use Petersen hashes inside of sapling which is a different

kind of hash function for the Merkel tree because in our original launch of Z cache we used shot 256 for the Merkel train it was really slow and he told me oh all you really need to use is Peterson hatches but won't those be really inefficient in a certain there's like a disconnect between what some researchers think is efficient and what is truly possible and so I was able to immediately go no you just make a curve and then over this field that would be super efficient so just the fact that Ian didn't have that experience playing around with snart's meant that he thought something was impossible on the flip side from an engineering perspective I've for a long time I've

been looking at problems that I don't have an engineer a research background in I look at the problem I say why don't we do this and actually this is the thing that happened four years at the ECC where I'd say why don't we just do it like this and the researcher probably Arielle or someone else would say I don't know if I can prove that secure and then they would go and prove it secure a few weeks later but there's this tendency to like stay with the within the safe boundaries of research and only like peek out at certain little spots but from the engineering perspective you can kind of like totally flip the script and and I think this is just part of just being outside of core

research and formalization where you can just flip the script and try something totally outlandish and definitely stressed out the cryptographers and the people writing proofs but come up with something really really more efficient or groundbreaking in the process and that's happened many times as well that's so interesting to hear it from that from that side because I feel like on this podcast we've had so many conversations where it's a researcher will propose something and the engineers are like no way it's gonna be impossible to like I feel like I've heard the other version of that where the researchers have the big green field ideas in the mplet and the implementers are like yo this is gonna be super complicated we do that as well as engineers were very

desperate to get performance when we've hit all of the possible things that we could think of to get performance out of something so then we have to sort of take the wheel a little bit on the research end and stretch things out and make people uncomfortable but it's been worth it yeah that there are all of these new algebraic hashes which haven't really had enough curse analysis yet and the as engineers were really it would be great to have hashes that are really efficient in stock circuits and so these please more Krypton I suppose find that interesting in in the zero knowledge proof space combined with the blockchain space now how quick this cycle is from

research to actually being in production somewhere and it's slightly scary as you say like a lot of these concepts really don't have enough analysis but there are so people out there super gung-ho and just like oh yeah this proof was invented last week let's nope into production somewhere yeah you can put it into production somewhere you just can't necessarily put it in production with a currency that billion dollar market cap or whatever it is that's actually what I consider production I've said this before I think production really means a year you're deciding to tell people hey I'm willing to risk my money on this I'm really I think you should be willing to risk your money on this I think that this works

and you can use this in practice that's what production is a lot of stuff isn't in production just because it's on maintenance areum it's in production because if there's people people's lives might depend on it those finances don't privacy so pulling this discussion back a little bit to implementation and when you're actually like sitting down to write code how do you go about implementing this because you like we've weaved in and out of what this is and talking about how you arrived here trying to solve some other problems and discovering things along the way maybe we can take a step back up reiterate what is halo and then dive into like what does an implementation that

actually look like today so the idea of the inhaler was to try to implement a really inefficient recursive snark using one of these DN curve cycles that we talked about and we knew it was going to be inefficient and then we probably need like a cluster of computers in order to even create like a proof we thought it'd be interesting and fun so we went on to implement it and then while we were trying to optimize one of the computations that we have to perform in inside of the construction we were able to like realize that it had some

structures and really smooth structure to it and tying the same to these techniques that came out in the sonic paper we were able to cheat a little bit we it felt like a cheat at the time it almost didn't really even feel like it was something that would work but it led to a theoretical improvement a an asymptotic improvement in the construction which is something you don't usually see when you're implementing pie-in-the-sky research stuff usually you get little constant factor improvements in your code or you make multiplication faster for a field element or you whatever you make it a little bit faster but we somehow while implementing this come up with a cheat that let us

massively speed up beyond what was we believe at the time theoretically possible in that setting and so that was really an exciting and of turning plane and it led to us starting to explore you know how can we do this without these BN curve cycles can we avoid them entirely and just use normal curve cycles and not use any trusted setup and that was really a huge thing for us because at ECC we we want to get rid of trusted set ups we've been working hard to make them more trustworthy with things like sonic and so on but getting rid of them is kind of ideal for us or getting rid of the stronger one at first it wasn't quite obvious whether the the care

cycles we were looking for we're gonna be coming in off because ideally you want to care that whether Prime has a large and tortoise at ease this is a way of making fast Fourier transforms more efficient there wasn't obvious that we could construct pairs of curves forming a cycle where both of them have this high to olicity it actually it turned out to be quite easy and the very common and you just pick a random prime and it almost just falls off so that I kind of wanted to find halo and like some pretty like simple terms so halo is using recursive snarks it is a trustless setup it is like and we've actually talked a little bit about how there's these two

sides to this some of these constructions so there's like the sides that clunk and Marlin work on and then there's the sides that halo and SuperSonics work on and they can be used like supersonic could be used with Marlin and Halo could be used with plonk like you're kind of able to connect Lego block that I don't know if that's right term but what else can we define hallo in like maybe some other simple terms so before before I do that I just want to point out how this is kind of a fundamental problem with when we say oh just used plunk or we just casually refer to these names there's a lot more nuance to that because when I say plunk

I could be talking about the the underlying construction inside of plunk built over a particular polynomial commitment scheme I could even be referring to a particular curve or something like that or I could be referring to a particular trusted setup that was used to instantiate plot so I'd be talking about a lot of different things and in Halos the same way halo is a combination of at least like half a dozen different techniques some more important than others that actually allows us to get to the recursion so the fundamental trick is this nested amortization strategy where you continually compress the computations so

that you don't actually have to perform them in the circuit you crumb them outside the circuit and that allows you to a lot of the circuits to converge to a finite size and you get recursion then there's the fact that we're using a polynomial commitment scheme a specific one that we have extracted out of the inner product argument and kind of modified a little bit to instantiate something like sonic or plunk or Marlins fundamental primitive on top of that polynomial commitment scheme and then use it yeah in this nested amortization strategy but that's where you could potentially replace them right that's where like the replacement could could live okay yeah totally and on top of

that the polynomial commitment scheme has this trick that we noticed where you could actually do the amortization so that this amortization argument call it where you kind of combine these this advice string sort of thing so the combination of those those ideas the kerbs cycles the used to this and a morphism trick to really speed things up and a bunch of other things are kind of just a combat just all combined and mushed together and we call it halo that I I'm sure that adds to the confusion because the next iteration of this someone will say use halo oh but I don't want to use sonic I

want to use plunk and that's just a confusing conversation that there's a lot of confusion and nuance to the way that we describe these this is actually really nice to hear that describe because it's all like tools and tricks to get it into a state where recursion is better where you can recurse easier fat what it what does it do to the recursion so the fundamental challenge underlying recursion let's say that you took bulletproof and you said okay I want to create a recursive proof using bullet grips well this means that you need to take the bulletproof verifier and make a circuit out of it and put that circuit into your bulletproof proving system but the circuit for checking the proof

itself scales linearly or more in the size of the circuit that it's checking and so as a result it blows up in size and you can't actually get recursion it doesn't or you don't get arbitrary depth recursion out of this so you need some way to do not perform that linear time operation and that that's sort of what the nested amortization strategy is about it's about cheating and not doing it saying okay there's two instances of me claiming I did it I'm gonna have a proof that I did those two instances and that proof takes as much time to check as the original two and then instead of doing this I'll shuffle it up to the

next layer and then keep doing that over and over and the trick is you never do the proving at the beginning that yeah you never do inside the circuit you never do this operation that takes linear time you always cheat and compress it probabilistically and then expend and bring it up to the next layer and so this is what I mean by when I say that the necessary authorization strategy allows us to achieve recursion by achieve recursion I mean it actually allows the circuit that is in this construction to actually converge to a finite size but because if it required this linear time operation it could never converge to a finite size it would

blow up as you continually nest and that's why you can't build recursion with Ola proofs but you can if you use this trick and use the polynomial commitment scheme you build some sort of proving system on top of that so any proving system that you're trying to use this technique with has to be compatible with the tank oh by the way back when I was talking about the Toyota city and constructing pairs of curves with I to elicit e I said something that was slightly wrong I said that you could use a just use a random prime but actually you have to use this thing called the complex multiplication equation but if

you look in the paper it's explained actually if you look in the github repos where as a code to generate the curve says it's i'm darris slash tweedle that explains up cool I want to ask a question based on something that was mentioned very briefly at the very beginning and that is like what is a shark and how does that relate to halo yes so shark is this sort of hybrid construction I'm really excited about it I like these this is not our idea it's an idea from the artists version and essentially what it is is it's a snark where you can check in two different ways you can either check it in what's

called a prudent manner in which you pay a lot of time to verify the proof with respect to the circuit but it's nothing underlying it you can also check it in an optimistic way in which it verifies very quickly and the optimistic way depends on the trusted setup but if the trusted setup is subverted you can obviously cheat on the optimistic verification but you can't cheat on the prudent verification and this is a cool model because it means you get the fast speed when you care about latency but you also get to detect when the trusted setup is compromised so essentially it's it's a superior version of no trusted setup and there's no there's no real argument

against it I can think of where the typical people who complain about trusted setups would have a problem with that I think but what is that how does it relate to halo so I think that halo has some future in this department there's potential to have a really attrition verifier I mean halo proofs themselves I haven't really talked about the performance that they're really small they're the smallest recursive proofs but they aren't super fast to verify at least alone and batches they're pretty quick to verify but alone they're not super fast to verify in the trusted in the no trusted set up mode and so I think that having kind of a hybrid model allows you to get the

performance that people want out of recursive snarks I think it performs well enough in practice that it could be used just the way it is but I think for people that really want good performance this is sort of this hybrid model is a good direction and there's obviously this other direction where this is what code is doing and we actually proposed this this is kind of originally how halo came about which was using these be n curves cycles where on one side you of the trust is set up and on the other side you don't and in this setting you get if you combine the techniques we use in halo you get some really good performance and that's that's why you hurdle Issac talking about this a lot in

a previous episode so so that that's an interesting direction for projects that don't mind trust incentives I it might actually be worth talking about the concrete performance of halo I mean you can see this in the paper but when we talk about small proofs the proof size that you need for occasion is about 3.5 kilobytes and it's that strictly draw logarithmic so if you wanted a larger circuit it's it's logarithmic in the second size and then the verifier time so for two to the seventeen circuit it's about one second on using 16 threads so it's quite practical at least for some applications immediately it's not as though the

linear time means that it's impractical because you only need to verify one thing it's it's not as though you would have to pay one second per transaction you're paying one second to verify a whole tree of transactions I want to understand a little bit why are we seeing this explosion of new protocols and like how do polynomial commitments have anything to do with this so what this idea of splitting a stock scheme into a polynomial commitment part and a specialization part and a kind of information through ethically secure protocol does it allows you to iterate

on those independently that is why we're seeing so much progress recently we we can have different sets of researchers working on those two parts independently you can mix and match around the two I think that's a that's a good answer for like the practical side of why we're seeing an explosion I think that there's also some of the some other factors that go into it which is just the fundamental fundamental nature of polynomials at their core are like this algebraic object that lets us manipulate a lot of different things at the same time at anytime you have something like that for example of Peterson commitment or whatever it's a very useful tool in

cartography so polynomial commitments are like a fundamental tool that allows us to operate on a lot of information at the same time which is why you see it used in things like an accumulator like this new construction that metallic was talking about because you can operate over all the information and demonstrate consistency and correctness internally polynomials also have structure that you can manipulate individual pieces and that's kind of combining those two really gives you the flexibility to build all sorts of things like snarks and anything else and it's it's also what allows you to have sickness this prophecy called the Schwarz ziffel lever which basically

allows you to prove that when two polynomials are equal just by making a small number of checks so all snarks are based on that I like that idea that you just presented though where by kind of looking closer at this polynomial commitment idea or you're able to actually break apart the snark into these different places that you could start optimizing on and then you could have these dedicated researchers focused on that and that's maybe why what we're seeing like we've had interviews with a lot of different protocol developers on their protocol and you see a lot of a lot of parts are very similar and then like maybe one part will be you know that will be where the optimization

that's the the part of the entire protocol that they've decided to like focus in on in the case of halo how to polynomial like where the polynomial commitments what are they doing there they're acting the same way as they do in any other of the recent snarks so they're just a method for us to build a start and the current theoretical direction that snarks are taking is to have polynomial commitments at the core because they're a really simple algebraic structure that describes exactly what's going on in a in a sark in these like interactive Oracle proofs and so on but by the way who should we

attribute the this idea of splitting snoc into these two pieces too because I know it's implicit on a lot of earlier papers but it really became clear with sonic I think it was that mary mala yes like I think sonic was the first scheme to actually break up like this protocol from the polynomial commitment scheme and then it was formalized later on in different ways by Marilyn and fraktur Marlin and supersonic and so on so yeah it was it was introduced by the sonic paper I think but yeah like you said it was implicit in previous instructions given all of these

protocols that have come out what would you say is actually a comparable protocol to Halo so halo is more than just a proving system like clunker Marlin it's also a just a recursive proving system so it supports recursion and it's kind of inherent in its design we I mean we can extract out the proving system underlying Halo into its own thing but the recursion is a little bit more than that so the only thing that's really comparable to right currently is something like fractal and fractal obviously as this it's post quantum secure and it's also it also has this property of stew sickness where the the

verifier actually takes poly logarithmic time to execute depending on the underlying circuit that it's checking and halo we don't have that strictly speaking the actual cost of checking the halo they're fully recursive proved although it doesn't depend on the depth of the recursion it does depend on the size of the circuit and although you can sort of bootstrap this into creating a snark and that's where you get the comparison between that and supersonic which would allow halo to be more efficient version of a little smaller proof sizes compared to supersonic but halos proof sizes are the fully

recursive proofs and just in the recursive setting are much smaller than fractals so that's that's kind of the overall comparison and I guess it's more useful to kind of talk about directions so how much further can we stretch the halo approach to improve things versus how much further we can stretch the fractal approach and I think they both have about the same as same amount of wiggle room that I can tell and just guessing so I'm not really sure which approach is going to end up being the best in the long run so it's the interesting next couple years I guess the other axis you can compare systems along is that the cryptographic

assumptions that they depend on so halo depends only on discrete log like assumptions and it's proven securing the algebraic group model something like supersonic for example requires I'm groups of unknown order which is another level of complexity in cryptography that ant analysis and then you have all of that then you have all of the pairing based protocols hello it definitely isn't proven secure in the other group model though I'm sure it is yeah what's in store for halo we kind of we started talking a little bit about like where ECC is at and like this focus on scaling halo has now been at least like has it been implemented it's been described

where are you at with it yeah we definitely we've implemented halo and a very efficient version of halo we want to get that out publicly as soon as we can but also just getting a really robust implementation that could actually be used in a product seems like an interesting direction to go and also there's just stripping out the internal piece of halo where it uses sonic and replacing it with something like clock or turbo clock or all these other new really efficient proving systems that are built on polynomial commitments doing that in combination with more clever optimization work that I'm sure there's plenty of more to go I think

that massive improvements the performance can go from there just on the implementation side alone and then on the research side of course trying to figure out how to make it more efficient theoretically using new tricks but where where would it live like so you say you release it does it just live as a library or are you gonna implement it into something and would it be like in the next upgrade or would this require like doing one of these like eath - new new setups and migrations so that the scaling proposal that I described it Z com1 and there's a video of the owl saddam seek a proof event that can directly use halo and the I

don't think there's any the theoretical research needed to make that proposal work it's just design and engineering but is that being brought into the next upgrade or is that it existing as a standalone project that would need migration towards we don't have any concrete plans currently I'd say that it would likely you look like a prototype before it would end up being deployed yeah I would definitely be deployed on a test at first yeah whether or not we would use like a giant migration approach like aetherium that's how I would intuitively prefer to do it but I don't think we've made a decision on that kind of but you would need that

that's actually the question I have here's like you can't use halo in an upgrade you'd have to create you'd have to deploy it as a Genesis as a new necessarily but well use our existing protocol as is like the the payment addresses that people use today would not be the same yeah yeah future with halo at least as far as we understand but this all depends on if we use halo like for example a fractal you have to be so efficient that it didn't just in terms of proof size we might not use halo and we might use practical instead or something like that in which case we could probably come up with a way to avoid having to do a change in addresses

then there's also other political discussions and there's a lot up in the air we have no idea so so yeah remember that we have done an upgrade of all of the cryptography or most of the cryptography in C cache once before we've done suppling and I was pretty successful so I did don't underestimate our own ingenuity in figuring out how to make this work I will make it work somehow so I want to say thank you both for being here and for kind of going on this journey with us through halo through like kind of where it comes from and a little bit about where it's going it does sound like given that you know given that this is pretty new research

I guess there's going to be a lot of discussion and debate and kind of more research in the meantime yeah we have two upgrades in the pipeline want to to let more things be done in shielded way and to support this I'm saying called fly client and local mountain ranges I won't go into detail about that and then there's another upgrade which I will be adding the and the new Z cash Development Fund and maybe some other minor things at the same time but no any major change in the cryptography would be at least a year

later than that so we're talking about 2021 alright it's been a great conversation and so much to dig into and I hope to have both of you back some time thank you very much for joining we'd like that thanks for having us and to our listeners thanks for listening thanks for listening [Music]