00:06: Anna Rose: 


Welcome to Zero Knowledge, a podcast where we talk about the latest in zero knowledge research and the decentralized web. The show is hosted by me, Anna.


00:18: Fredrik:


And me, Fredrik.


00:26: Anna Rose:  


So today we're sitting with Daira and Sean from the ECC or the Electric Coin Company. Welcome to the show.


00:34: Daira Hopwood:


Hello. Good to be here.


00:35: Sean Bowe:


Hi, nice to be here.


00:36: Anna Rose:


And we have Fredrik here.


00:38: Fredrik:


Hello, hello. We've had Sean on before, but we've never had Daira on. Maybe we do a quick intro to Sean and then dig into a little bit of your background, Daira.


00:50: Daira Hopwood:


Yeah, I'm excited to be here.


00:52: Sean Bowe:


So I work in research and engineering at the Electric Coin Company. So I've been doing a lot of the engineering of SNARK implementations and circuits and also research into more efficient protocol designs and new SNARK research.


01:12: Fredrik:


And according to my Twitter, you're an alien who came to Earth to forward the zero-knowledge-proof science.


01:18: Sean Bowe:


There's a lot of those actually.


01:22: Anna Rose:


And how about you, Daira? What are you working on at ECC? And maybe since it's the first time that you're on the show, give us a little bit more of a background on how you arrived at this space.


01:33: Daira Hopwood:


So I do protocol design and specification and documenting the protocol mainly, and some engineering as well. So I got interested in crypto and the sort of crypto wars in the 90s. Then it was the maths that kept me here. I love maths and it's great to be able to do cutting edge maths for a job. Not many people can do that.


02:00: Anna Rose:


Have you studied cryptography or math in the past?


02:05: Daira Hopwood:


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 references to things to express security policies. And there was a project called Tahoe-LAFS, which is a distributed file store. And Zooko was involved with that. So that's how I met Zooko, and then I started working for Least Authority, which was a startup supposed to commercialize Tahoe-LAFS. And then from that, I went on to Zcash.


02:47: Anna Rose:


We've actually had Zooko 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 Zcash company. At what point did sort of zero knowledge proofs or that kind of SNARK research really enter into your world?


03:15: Daira Hopwood:


So Zcash was an association with Zerocash, and that paper had already been written that uses zero knowledge proofs. So from the time I started at Zcash, we were all learning how to use zero knowledge proofs, which we all had to learn from scratch.


03:36: Anna Rose:


And that must have been a funny time to learn it because at the time, and this is to you too, Sean, like there must not have been very much documentation around this stuff. There wasn't the kind of educational resources that we're starting to see emerge around it.


03:48: Sean Bowe:


Right. A lot of it was folklore and we learned a lot of it from each other. Yeah.


03:54: Daira Hopwood:


There was just papers and working out from scratch really.


03:58: Anna Rose:


Wow.


03:59: Fredrik:


When Zcash started, did libsnark already exist and like, was a thing that was considered stable and you like at Zcash just went with it or, you know, where did libsnark exist in relation to Zcash.


04:18: Daira Hopwood:


So there was already a prototype of Zerocash that used libsnark. And we ended up rewriting all of the code in that prototype, but we still use libsnark.


04:29: Fredrik:


I see. And then at some point down the road, which we'll come to later I'm sure, you rewrite libsnark as well.


04:36: Sean Bowe:


That ended up being Bellman.


04:37: Daira Hopwood:


Yeah. So Sean read that in Rust. When did you write Bellman?


04:42: Sean Bowe:


So I started working on Bellman before I even worked for the company. And we talked about this in the previous episode, but it actually ended up being a true libsnark replacement only around 2017 or so. Even though it did start back a little earlier than that. 


05:00: Daira Hopwood:


And we've now completely replaced libsnark with Bellman.


05:04: Anna Rose:


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? So maybe we can just talk about what has happened since then, and maybe what were your focuses from that point onwards in the company?


05:27: Sean Bowe:


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 universal trusted setups and I thought that was a really good direction. There were some other different directions like no trusted setups, 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, Daira was doing scalability research. And those kind of go hand in hand when it comes to Zcash 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.


06:31: Daira Hopwood:


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 Zcon1. So that's why that got done on time. But I've since refined it quite a bit.


06:58: Fredrik:


This isn't the first time I've heard of a presentation-driven development.


07:03: Anna Rose:


I remember that talk at Zcon1. This was in Croatia, in Split, Croatia, last summer. And in that talk, you had specifically highlighted this idea of moving Zcash into a sharded system, potentially. So I'm wondering kind of like what... I've always been a little bit curious about how far that went? As I understood, it was still very much proposal kind of research phase at that time. Where did you go with that idea?


07:38: Daira Hopwood:


It's still a 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. There's a lot of detail and optimization and design choices to make.


07:56: Fredrik:


I'm curious to hear how this work came about in the first place, because I remember talking to Zooko at I think SPC 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 I know he's been going around trying to gather ideas for how we can scale Zcash. I don't know, like, does that make it into the company and then gets selected and percolated within the company? Or is it that really like a separate thing and it's the company researchers like yourself are coming up with their own proposals?


08:39: Daira Hopwood:


Well, we're always looking at what other people are doing. The Ethereum people have come up with some really interesting ideas recently in the last few months, even in the last week. But, even before that, I think we'd learned from Bitcoin, because Bitcoin had a huge political issue about how scaling should be done, should the block size be increased and so on. And we wanted to avoid some of the political strife that occurred for Bitcoin by thinking about this issue a lot earlier. In the sort of the lifetime of the currency, obviously, Bitcoin has had a few years longer.


09:23: Sean Bowe:


One of the things that kept coming up, and this was back in like 2017, so you can kind of see why, but anytime we pitched Zcash 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 meme 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 in the Ethereum land. In the Zcash 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 with scale, but we have to have the strong ledger and distinguishability property that underlies Zcash. And that's a really difficult bar to reach.


So a lot of this started very early on in the Zcash project. 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?


10:42: Daira Hopwood:


Yeah, I mean, we've already made some scalability improvements. We started off with double the block size of Bitcoin and a quarter of the block spacing. So that gave us an eight times capacity. 


10:59: Anna Rose:


That's right from the beginning, you mean? That was right... Like right from the start, like in the actual genesis of it.


11:06: Daira Hopwood:


Yeah. And then, and then more recently with the Blossom upgrade, we've halved the block time again. So that's 16 times relative to Bitcoin, although they've introduced SegWit, which makes things more complicated for them.


11:21: Sean Bowe:


These are, of course, constant factor improvements that correspond with improvements we've made to the performance of, for example, our SNARK verifier and things like that, that we've been taking into account. But the kind of scalability challenges that we need to address going forward are more architectural, and also they affect the user interface pretty significantly. So.


11:43: Anna Rose:


I guess I was just thinking like scalability in the Zcash context is 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 going to actually have to have faster SNARKs and faster SNARKs would on some level also mean faster blockchain, which I guess you would... That falls in the scaling category as well.


12:09: Daira Hopwood:


Yeah.


12:10: Fredrik:


Faster user experience, I suppose.


12:13: Daira Hopwood:


Yeah, so we made huge improvements with Sapling. And 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 the network capacity. So...


12:37: Anna Rose:


This is for the SNARKs specifically. Yeah.


12:40: Daira Hopwood:


Well, SNARKs and signatures, because they're both significant. We couldn't keep on doing upgrades like Blossom indefinitely because we would end up in 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.


12:58: Fredrik:


There's also, I mean, when you think about scaling in those terms that you said, Anna, there's also diminishing returns to like the UX side of it, right? Whereas 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.


13:25: Sean Bowe:


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 transaction, so you know it's irrevocable. They're like exactly what the interaction between you and the recipient is and how many steps you take or how many rounds of interaction you take. And most cases it's 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 wanna receive payments privately, it's really hard to make a trade-off between not communicating directly with the sender for privacy reasons or receiving your information in a broadcast network like Zcash 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 intended for them.


14:30: Daira Hopwood:


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.


14:37: Fredrik:


Daira, you touched on something I think is super important, which is the political aspect. And I wonder how you guys see that in like scaling, sharding, these kinds of things where, you know, Ethereum 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 introduces a ton of complexity just in and of itself.


15:08: Sean Bowe:


I'm actually a huge fan of that style of migration personally because especially for the Zcash case, because we built on top of Bitcoin, so there's a lot of legacy cruft that we just wanna burn down. And starting from scratch is a really nice way to make the right decisions from the first place. It is really contentious in Ethereum's case, but there's a lot of other factors that are going into that, I think, than just this strategy they're taking to migrate.


15:40: Daira Hopwood:


I'm all in favor of burning the disk facts, but that's a small talk reference. So yeah, the Bitcoin codebase is terrible. I hope I don't get into trouble with the Bitcoin developers for saying that, but it is. Especially the version that we forked from, which was 0.11.2. 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 codebase is diverged a lot.


16:14: Fredrik:


I mean, as someone who's worked on re-implementing Bitcoin, even when you take it from scratch re-implementation, you end up with something that isn't very good just because of the way things are designed. Like there are bugs in Bitcoin and you have to replicate those bugs. And it's... Yeah, you get into weird territory.


16:38: Daira Hopwood:


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 a much better overall anonymity set and privacy properties is everyone is using shielded.


17:00: Anna Rose:


Wow, I didn't know that that was actually the plan to eventually remove the transparent. I always thought there was strong encouragement to use the shielded accounts.


17:10: Daira Hopwood:


So I'm not... I think perhaps plan might be too strong a word for it. I know that us engineers are pretty keen on that approach.


17:19: Sean Bowe:


There's a lot of political considerations, like for example, just the fact that there's so many people are using T-addresses currently. It's an interesting on-ramp to the actual currency. It'd be, it's completely speculative, but I'm pretty confident that had there not existed T-addresses, there would be a lot less Z-addresses usage.


17:40: Anna Rose:


For sure.


17:40: Sean Bowe:


Simply 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-addresses. Well, I guess we do want to get rid of T-addresses 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.


18:12: Anna Rose:


Got it.


18:13: Daira Hopwood:


There's also the issue that we can't do some of the things that Bitcoin does in zkSNARKs. So we probably can't support Bitcoin script in zkSNARKs.


18:25: Sean Bowe:


And we wouldn't want to.


18:27: Daira Hopwood:


Yeah, in fact, the full generality of Bitcoin script isn't really being used on the Zcash network. People are using a little bit of multisig. In fact, I think over 95% of the script usage is just multisig. So people are not using more complicated things, and if we support Shielded multisig, then that will replace that functionality.


18:51: Fredrik:


So what does this scaling situation look like today then?


18:55: Sean Bowe:


So we do have tentative plan for a scaling proposal and that's what Daira has 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. 


19:08: Daira Hopwood:


Yeah. I've also been looking at other scalability proposals that have a privacy component. There's an account-based anonymous rollup that's been proposed for Ethereum. That has some interesting ideas. So instead of, we're in Zcash, all funds are held in notes, and there's no distinction between the notes that you hold yourself and the notes that you're transferring to some other party. In an account-based anonymous rollup, 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.


19:58:


So 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, that might not be the final name of it, which is you just send a message to someone and they have all of the information needed to use that payment. And you can send that message over to existing communication channels like a Signal or Telegram or whatever.


20:30: Anna Rose:


So you just mentioned sort of the ZK rollup model and I could understand that there's more of a kind of architectural component that you're thinking of using, but Zcash doesn't currently allow for smart contract writing, so it can't do... Can it do this off-chain and then like batching... Like bringing these sort of validity proofs on-chain? Is that something that's actually possible with a Zcash UTXO model or is that like...?


21:00: Daira Hopwood:


Yeah, so Ethereum 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 the protocol.


21:16: Anna Rose:


I forget about that. Yeah, that's true. You have control over the client. You could definitely decide.


21:24: Daira Hopwood:


Yeah, and supporting smart contracts makes everything a lot more complicated. You have to support scalability and privacy and smart contracts at the same time, and we only really know how to do two of those things.


21:39: Anna Rose:


So from the scaling sort of setup 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 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 the origin story of Halo and... Yeah, a little bit about what it is.


22:06: Sean Bowe:


Yeah, 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 Coda is doing. You've had previous episodes talking about this, the episode with Izaak and the episode with the authors of Fractal. And at the time last year, there was only one known way or actually realized 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 SNARKs is really inefficient. It required these cycles of pairing-friendly elliptic curves, and they were really gigantic curves that were not very efficient and used large fields, so it had this negative impact on the user experience when you use the elliptic curve points as like keying material and things like that. So we wanted to find a more efficient way to do recursion. And so I think at Zcon1 we were talking about these various ways to get more efficient pairing-friendly cycles or to do these new designs of arrangements of curves but we didn't really get anywhere.


23:40: Daira Hopwood:


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 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 curves in the cycle. And that's the thing that is difficult to do and there's only one known construction that does that. But if you remove the restriction that one or both of the curves are pairing friendly then it becomes much easier.


24:26: Sean Bowe:


So I think after Zcon, I thought why not just use BN curve cycles. And there was 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 curve's proving system is succinct or not. And that gives us the flexibility to build recursive SNARKs using a cycle like a BN curve cycle where one of the curves is pairing friendly and the other isn't.


25:01: Anna Rose:


What's a BN curve? What did you just say? BN?


25:05: Sean Bowe:


They're Barreto-Naehrig curves. These are the curves that they deployed in Ethereum. And it was also the curve that we initially launched Zcash with. 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 on our GitHub. By the way, our GitHub is just like a treasure trove of ideas. Daira and I love to post our ideas as soon as possible on there. Usually to preempt patent trolls if they show up and claim that they came up with an idea. So, Daira is really good about taking your ideas and making sure they end up on GitHub eventually.


25:45: Daira Hopwood:


I usually tweet them as well. 


25:47: Sean Bowe:


Yeah. So, this was an interesting starting point because I thought, okay, we can make recursion but how efficient will it be? And I thought at first using this style of recursion that it would be really slow. But I thought, okay, 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 Jack Grigg and Daira, and we started working on an implementation of this style of recursion. And we realized that we could make it much more efficient as we were implementing it. As we were optimizing it, we were discovering fundamental tricks that we could use to improve the performance and practice.


26:36:


And one of those tricks was this thing that we refer to in the Halo paper as nested amortization. It might not 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 because it allows us to sidestep this requirement of doing these expensive operations to verify the proof on the proving system that isn't on the pairing-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.


27:30: Anna Rose:


But like the Sonics paper was out, that was out at the beginning of 2019, and that also has this universal trusted setup. So that's where it's like allowing more people to join. But in this case, 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, Sonics is the first step towards no trusted setup, but this sounds like it's coming from a very different place.


27:57: Sean Bowe:


Yeah, there is this... So the Halo paper... 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 Bulletproofs, but it's used in Bulletproofs. And a lot of people call it, just refer to it as the Bulletproofs 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 Sonic. Sonic took this old polynomial commitment scheme 2010, this pairing-based one and used it to build a universal SNARK. So kind of from that starting point, it's like a simple way of getting... Starting to build a proving system, and it's a way that Plonk and all these other recent SNARKs build on top of just this simple univariate polynomial commitment scheme.


28:58:


So, this inner product argument actually had this structure that we kind of accidentally discovered where you could do this trick that we did in Sonic, where you could check a lot of proofs at the cost of just checking one. And this was one of the fundamental components of this nested amortization strategy that we used to actually make recursion possible.


29:26: Daira Hopwood:


In fact, so Bulletproofs, Sonic and Halo have another thing in common which is that they use the same circuit arithmetization. So you have multiplication constraints and linear constraints which are separate unlike in R1CS systems. It actually gives you most of the advantages of R1CS because you can still do linear constraints very concisely. 


29:56: Sean Bowe:


Yeah, so actually when we posted the Halo preprint publicly, this was just a couple days, I think, or something like that after the Plonk paper was published. And this was before, I think, the Marlin paper was published. So there was... I mean, in September, there was a lot of papers coming out.


30:17: Anna Rose:


Yeah, I remember.


30:19: Sean Bowe:


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 polynomial commitment schemes, like Marlin or Plonk or SHPLONK or whatever, all these other new constructions are called.


30:37: Anna Rose:


Can you go back to this nested amortization? Amortization? Like, what is the amortization part? Like, what does that... First of all, what does that word mean in this context?


30:48: Sean Bowe:


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.


31:02: Anna Rose:


Okay.


31:03: Sean Bowe:


And something that we introduced in the Sonic paper was this idea of succinctness after amortization, where you pay... Okay, so you allow a third party helper, we called it, to create a proof that all of the proofs are correct in some batch of proofs and some fixed batch, and that proof itself costs the same to check as all of the individual proofs. And so it allowed us to sort of cheat and say, okay, after amortization we achieved something like succinctness. And then obviously, in the Sonic paper we went on to actually show that we could get full succinctness per proof in a really expensive way that was improved upon by Plonk and Marlin. 


31:55:


But it turns out that this strategy of compressing the verification time using a third-party helper to create what we call an advice string, it turns out that this fundamental tool allows us to sidestep even the need for succinctness. 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 bits of that advice string out as public inputs to the circuit so that the verifier of that proof has to check that advice 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 then 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.


33:18: Daira Hopwood:


Something that might not be quite obvious from the paper is that this doesn't have to be a linear chain of proofs. It can be a tree of proofs.


33:28: Anna Rose:


When you say a tree of proofs, are you talking... Is this like a Merkle tree style thing? Or is this like, are you talking about like a... Is this the recursiveness that is this tree?


33:39: Daira Hopwood:


Yeah, the structure of the recursion can be a tree.


33:42: Anna Rose:


I see.


33:43: Sean Bowe:


Yeah, in practice, this is what you would do. This is what Coda does, for example. It's the only thing that really makes sense.


33:50: Daira Hopwood:


So you're proving everything at the leaves, but the leaves can be constructed by people who know different things, which is very useful.


33:57: Anna Rose:


I mean, I just remember doing a study club on Sonics and like there was all these optimizations that you had kind of come up with. So what are the optimizations for Halo that you're working on?


34:09: Daira Hopwood:


Yeah, there are a lot of them actually. So one of the interesting ones is that we make use of an endomorphism on the curves that we use. So it's actually similar to the Secp256k1 curve in Bitcoin. They also use exactly this endomorphism and basically allows you to do multiplications on the curve more quickly. This has been known for a long time and 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 endomorphism, you do it the other way around. So you start with some random bits. So say you need a challenge, which is 128 bits. As long as you multiply by some scalars that has 128 bits of entropy, you're fine. I'm not sufficient for the security of the scheme. So you just take the random bits and you 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 two random bits at each step.


35:35: Anna Rose:


What is endomorphism?


35:36: Daira Hopwood:


So it's a mapping basically.


35:39: Anna Rose:


Oh, it's like a morphism, but you call it an... Why is it endomorphism then?


35:44: Daira Hopwood:


Because it's mapping onto the same structure.


35:46: Anna Rose:


Oh, okay.


35:48: Daira Hopwood:


So it's a mapping from a structure onto itself. And it's a mapping that preserves the group operation. So this means that it's equivalent to a particular multiplication. So a multiplication by some scalar.


36:00: Sean Bowe:


You had a fun episode about isogenies recently where you went into morphisms and that was really fun.


36:07: Anna Rose:


Exactly.


36:08: Fredrik:


I tried to reference that episode in our episode with Vitalik 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.


36:29: Sean Bowe:


Actually, that is a thing now. 


36:33: Fredrik:


And what I actually wanted to say is unknown endomorphism ring.


36:37: Anna Rose:


And I saw you were corrected on Twitter.


36:40: Fredrik:


Yeah, which is great.


36:41: Anna Rose:


So what was that, like you just sort of said this, you didn't necessarily start on this path with 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 this protocol. And I guess, when I heard that, I was wondering if like... Is that how the ECC usually works? Is that... Do you have sort of the freedom to just explore in certain directions even though they might seem super inefficient? And like, how would you make a choice to do that? Because you only have limited amount of time.


37:17: Sean Bowe:


I think this is like a new thing for us. I think most of our previous advances and improvements 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.


37:57: Daira Hopwood:


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.


38:07: Anna Rose:


And the three of you, you're all engineers?


38:10: Daira Hopwood:


Yes.


38:10: Sean Bowe:


Yeah.


38:11: Anna Rose:


Most primarily. So you're not necessarily... Like, would you also fall in the research camp?


38:18: Sean Bowe:


I think so. I think we all have contributed to very novel ideas. I think that's partly just because we were the first people to actually deploy SNARK, so we managed to kind of run on this untrodden ground. So, but yeah, yeah, we fall into the research camp, I think...


38:39: Anna Rose:


As well.


38:40: Sean Bowe:


Equally as well as engineering for sure.


38:43: Anna Rose:


So you're sort of like the hybrid researcher engineers who have gotten together to try to look at problems that everybody told you were impossible to make more efficient.


38:52: Daira Hopwood:


I think you do have to have that engineering experience to know what direction to head in because you have a lot of protocols where it doesn't look as though the experience of what can be implemented efficiently has guided the design of the protocol. So that's very important.


39:12: Sean Bowe:


Yeah, I think in two ways I've experienced this in the past. In one way, years ago when... I think it was Ian Miers was telling me, hey, why don't we use Pedersen hashes inside of Sapling, which is a different kind of hash function for the Merkle tree? Because in our original launch of Zcash, we used SHA-256 for the Merkle tree and it was really slow. And he told me, oh, all you really need to use is Pedersen hashes, but won't those be really inefficient in the circuit? 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, we can just make a curve and then over this field, it'll be super efficient. So just the fact that Ian didn't have that experience playing around with SNARKs meant that he thought something was impossible.


40:04:


On the flip side, from an engineering perspective, for a long time, I've been looking at problems that I don't have an engineer or a research background in. I look at the problem and I say, why don't we do this? And actually, this is just a thing that happened for years at the ECC where I'd say, why don't we just do it like this? And the researcher, probably Ariel 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 stay within the safe boundaries of research and only peek out at certain little spots. But from the engineering perspective, you can kind of like totally flip the script. 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 stress out the cryptographers and the people writing proofs, but come up with something really more efficient or groundbreaking in the process. And that's happened many times as well at the ECC.


41:11: Anna Rose:


That's so interesting to hear it 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 and the implementers are like, yo, this is going to be super complicated. 


41:33: Daira Hopwood:


We did that as well.


41:34: Sean Bowe:


Yeah, yeah, as engineers we're 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. 


41:54: Daira Hopwood:


Yeah, there are all of these new algebraic hashes which haven't really had enough cryptanalysis yet. And as engineers, it would be great to have hashes that are really efficient in SNARK circuits. So please, please more cryptanalysis of those.


42:12: Fredrik:


I find that interesting 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's still people out there super gung-ho and just like, oh, yeah, this proof was invented last week, let's put it into production somewhere.


42:36: Daira Hopwood:


Yeah, you can put it into production somewhere, you just can't necessarily put it in production with a currency that has a billion dollar market cap or whatever it is.


42:46: Sean Bowe:


That's actually what I consider production. I've said this before, I think production really means that you're deciding to tell people, hey, I'm willing to risk my money on this, 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 mainnet and Ethereum, it's in production because there's people... People's lives might depend on it. Those finances, those privacy, so.


43:18: Fredrik:


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 as you like we've weaved in and out of what this is and talking about how you're right here, trying to solve some other problem and then 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?


43:47: Sean Bowe:


So the idea behind Halo was to try to implement a really inefficient recursive SNARK using one of these BN curve cycles that we talked about. And we knew it was going to be inefficient and that we'd probably need a cluster of computers in order to even create a proof. But 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 inside of the construction, we were able to realize that it had some structures, some really smooth structure to it. And tying this into these techniques that came out in the Sonic paper, we were able to cheat a little bit. It felt like a cheat at the time and almost didn't really even feel like it was something that would work.


44:46:


But it led to a theoretical improvement, 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 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 kind of turning point. And it led to us starting to explore, 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 want to get rid of trusted setups. 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 strong reliance on them.


45:51: Daira Hopwood:


At first, it wasn't quite obvious whether the curve cycles we were looking for were going to be common enough, because ideally you want curves that, where the prime has a large elicity. So this is a way of making a fast Fourier transforms more efficient. So it wasn't obvious that we could construct pairs of curves forming a cycle where both of them have this high true elicity]. It actually turned out to be quite easy and they're very common, and you just pick a random prime and it almost just falls out of that.


46:24: Anna Rose:


I kind of want to define Halo in some pretty 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 the sides that Plonk 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 like Lego block that, I don't know if that's the right term. But what else can we define Halo in maybe some other simple terms?


47:07: Sean Bowe:


So before I do that, I just want to point out how this is kind of a fundamental problem with when we say, oh, just use Plonk or we just casually refer to these names, there's a lot more nuance to that. Because when I say Plonk, I could be talking about the underlying construction inside of Plonk 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 Plonk. So we'd be talking about a lot of different things. And Halo is 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 computation so that you don't actually have to perform them in the circuit, you perform them outside the circuit. And that allows 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 Plonk or Marlin's fundamental primitive on top of that polynomial commitment scheme and then use it in this nested amortization strategy.


48:41: Anna Rose:


But that's where you could potentially replace them, right? That's where the replacement could live. Okay.


48:47: Sean Bowe:


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, we call it, where you kind of combine this advice string sort of thing. So the combination of those those ideas, the curve  cycles, the endomorphism trick to really speed things up and a bunch of other things are kind of just all combined and mushed together and we call it Halo. That, 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 Plonk, and that's just a confusing conversation that, there's a lot of confusion and nuance to the way that we describe these schemes.


49:40: Anna Rose:


This is actually really nice to hear that described, because it's all like, tools and tricks to get it into a state where recursion is better, where you can recurse easier, faster? What does it do to the recursion?


49:54: Sean Bowe:


So the fundamental challenge underlying recursion, like let's say that you took Bulletproofs and you said, okay, I wanna create a recursive proof using Bulletproofs. Well, this means that you need to take the Bulletproofs verifier and make a circuit out of it and put that circuit into your Bulletproofs 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 not perform that linear time operation. And 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.


51:02: Anna Rose:


And the trick is you never do the proving at the beginning. What is that?


51:06: Sean Bowe:


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 bring it up to the next layer. And so this is what I mean by when I say that the nested amortization strategy allows us to achieve recursion. By achieving 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 Bulletproofs, but you can if you use this trick and use the polynomial commitment scheme and you build some sort of a proving system on top of that.


51:55: Daira Hopwood:


So any proving system that you're trying to use this technique with has to be compatible with the technique. Oh, by the way, back when I was talking about the elicity and constructing pairs of curves with high true elicity. I said something that was slightly wrong. I said that you could 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 repo where the code to generate the curves is, it's Daira/tweedle. That explains it.


52:34: Anna Rose:


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?


52:46: Sean Bowe:


Yeah, so a 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 Madars Virza and Eran Tromer. And essentially what it is, is it's a SNARK where you can check it 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 that it's checking 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 a superior version of no trusted setup. And 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.


53:57: Anna Rose:


But what is that? How does it relate to Halo?


54:00: Sean Bowe:


So I think that Halo has some future in this department. There's potential to have a really efficient verifier. I mean, Halo proofs themselves, I haven't really talked about their performance, but they're really small. They're the smallest recursive proofs. But they aren't super fast to verify, at least alone, in batches, they're pretty quick to verify. But alone, they're not super fast to verify in the no trusted setup mode. And so I think that adding 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 can be used, just the way it is. But I think for people that really want good performance, this sort of this hybrid model is a good direction. And there's obviously this other direction where this is what Coda is doing, and we actually proposed this, this kind of originally how Halo came about, which was using these BN curve cycles where on one side you have the trusted setup 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 why you heard Izaak talking about this a lot in a previous episode. So that's an interesting direction for projects that don't mind trusted setups like Coda.


55:27: Daira Hopwood:


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 recursion is about 3.5 kilobytes and that's strictly logarithmic. So if you wanted a larger circuit it's logarithmic in the circuit size. And then the verifier time for a 2 to the 17 circuit is about one second on a machine 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 not as though you would have to pay one second per transaction. You're paying one second to verify a whole tree of transactions. 


56:20: Anna Rose:


Well, 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?


56:28: Daira Hopwood:


So what this idea of splitting a SNARK scheme into a polynomial commitment part and an arithmetization part and a kind of information theoretically secure protocol does is it allows you to iterate on those independently. That is why we're seeing so much progress recently. We can have different sets of researchers working on those two parts independently. You can mix and match between the two.


56:59: Sean Bowe:


I think that's a good answer for the practical side of why we're seeing an explosion. I think that there's also some other factors that go into it, which is just the fundamental nature of polynomials at their core. They are like this algebraic object that lets us manipulate a lot of different things at the same time. And anytime you have something like that, for example, a Pedersen commitment or whatever, it's a very useful tool in cryptography. 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 Vitalik 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 in 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.


58:05: Daira Hopwood:


And it's also what allows you to have succinctness. There's this property called the Schwartz–Zippel lemma, which basically allows you to prove that two polynomials are equal just by making a small number of checks. So all SNARKs are based on that.


58:23: Anna Rose:


I like that idea that you just presented though where by kind looking closer at this polynomial commitment idea, or you were 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 parts are very similar and then like maybe one part will be... You know, that will be where the optimization, that's the part of the entire protocol that they've decided to focus in on. In the case of Halo, where are the polynomial commitments? What are they doing? 


59:05: Sean Bowe:


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 SNARK. 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 SNARK, in these interactive oracle proofs and so on.


59:38: Daira Hopwood:


By the way, who should we attribute this idea of splitting a SNARK into these two pieces too? Because I know it's implicit in a lot of earlier papers, but it really became clear with Sonic, I think. Was that Mary Maller?


59:53: Sean Bowe:


Yeah, Sonic... I think Sonic was the first scheme to actually break up the protocol from the polynomial commitment scheme. And then it was formalized later on in different ways by Marlin and Supersonic and so on. So yeah, it was introduced by the Sonic paper, I think. But yeah, like you said, it was implicit in previous constructions.


1:00:21: Anna Rose:


Given all of these protocols that have come out, what would you say is actually a comparable protocol to Halo?


1:00:28: Sean Bowe:


So Halo is more than just a proving system like Plonk and Marlin. It's also just a recursive proving system. So it supports recursion and it's kind of inherent in its design. 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 it currently is something like Fractal. And Fractal obviously has this, it's post-quantum secure, and it also has this property of succinctness where the verifier actually takes polylogarithmic time to execute depending on the underlying circuit that it's checking. In Halo, we don't have that strictly speaking. 


1:01:18:


The actual cost of checking the Halo, they're fully recursive proof, 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 a more efficient version of... Or at least smaller proof sizes compared to Supersonic. But Halo's proof sizes are the fully recursive proofs and just in the recursive setting are much smaller than Fractals. So 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 amount of wiggle room that I can tell in 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 going to be interesting next couple years, I guess.


1:02:27: Daira Hopwood:


The other axis you can compare systems along is the cryptographic assumptions that they depend on. So Halo depends only on discrete log-like assumptions. It's proven secure in the algebraic group model, but something like Supersonic, for example, requires groups of unknown-order, which is sort of another level of complexity in cryptography that needs analysis. And then you have all of the pairing-based protocols.


1:02:58: Sean Bowe:


Halo definitely isn't proven secure in the algebraic group model though, I'm sure it is, but yeah.


1:03:03: Anna Rose:


What's in store for Halo? We started talking a little bit about where ECC is at, and like this focus on scaling. Halo has now been at least, has it been implemented? It's been described. Where are you at with it?


1:03:19: Sean Bowe:


Yeah, we've definitely... We've implemented Halo and a very efficient version of Halo and 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 Plonk or Turbo-Plonk 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 more to go. I think that massive improvements to 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.


1:04:12: Anna Rose:


But where would it live? Like, 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 doing one of these like ETH 2 new setups and migrations?


1:04:31: Daira Hopwood:


So the scaling proposal that I described at Zcon1, and there's a video of the Amsterdam ZKProof event, that can directly use Halo. I don't think there's any other sort of theoretical research needed to make that proposal work. It's just design and engineering.


1:04:52: Anna Rose:


But is that being brought into the next upgrade, or is that it existing as a standalone project that would need migration towards?


1:05:00: Sean Bowe:


We don't have any concrete plans currently. I'd say that it would likely look like a prototype before it would end up being deployed.


1:05:09: Daira Hopwood:


Yeah, it would definitely be deployed on a testnet first.


1:05:12: Sean Bowe:


Yeah. Whether or not we would use a giant migration approach, like Ethereum, that's how I would intuitively prefer to do it, but I don't think we've made a decision on that kind of...


1:05:33:  Anna Rose:


But you would need that. That's actually the question I have here is 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.


1:05:42: Sean Bowe:


So not necessarily, but we didn't use our existing protocol as the payment addresses that people use today would not be the same as that what would be the future with Halo, at least as far as we understand, but this all depends on if we use Halo. For example, if Fractal got to be so efficient that it didn't, just in terms of proof size, we might not use Halo and we might use Fractal 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. There's also other political discussions. There's a lot up in the air. We have no idea.


1:06:23: Daira Hopwood:


So, yeah, remember that we have done an upgrade of all of the cryptography or most of the cryptography in Zcash once before, we have done Sapling. And that was pretty successful. So don't underestimate our ingenuity in figuring out how to make this work and we'll make it work somehow.


1:06:43: Anna Rose:


So I want to say thank you both for being here and for kind of going on this journey with us through Halo, through kind of where it comes from, and a little bit about where it's going. It does sound like given that this is pretty new research, I guess there's going to be a lot of discussion and debate and kind of, I don't know, more research in the meantime.


1:07:10: Daira Hopwood:


Yeah, we have two upgrades in the pipeline. One to let more things be done in a shielded way and to support this thing called Flyclient and Merkle Mountain Ranges. I won't go into detail about that. And then there's another upgrade which will be adding the new Zcash 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.


1:07:51: Fredrik:


All right, it's been a great conversation and so much to dig into. And I hope to have both of you back sometime. Thank you very much for joining.


1:08:00: Daira Hopwood:


We'd like that.


1:08:01: Sean Bowe:


Thanks for having us.


1:08:02: Fredrik:


And to our listeners, thanks for listening.


1:08:04: Anna Rose:


Thanks for listening.