Announcing Halo 2

Hello, friends! We at Electric Coin Co just announced that we’re releasing some open source code for an improvement to Halo called Halo 2!

Here’s the main announcement blog post.

And here’s some more technical detail.

As we said in the blog post, ECC is committed to fully productionizing Halo 2. We’ll make sure it gets all of the scientific scrutiny, security auditing, engineering, testing, documentation, user support, marketing, bizdev, etc. necessary to allow the community to deploy Halo 2 in Zcash in order to eliminate trusted setups.

But, this doesn’t mean that we’re deciding that Halo 2 is going to activate in Zcash. That’s not for us to decide! That’s for the community to decide. What we’re committing to doing is making it as easy and safe as possible to deploy, if the Zcash community decides “Yes”.

So, please read the announcements, if you’re a coder, download it from github and test it out and submit a patch, and let us know what you think and if you have any questions.

26 Likes

Very cool!

Can you please explain, in technical terms, how Halo or Halo 2 will be integrated into Zcash on the “as early as 2021” timescale? (cc @ebfull @daira)

We’ve seen how Halo can be used to verify PoW, but I haven’t seen anything about specifically how Halo would be used to verify transactions . Because Halo is not succinct (in the efficient-verifier sense), it’s not a drop-in replacement for existing zk-SNARKs like Groth16. If you just take Sapling and replace Groth16 with Halo, verification would be too slow.

Would you use some new higher-level protocols to exploit Halo’s amortized verification using recursive composition, to compensate for that? What do these protocols look like?

We do know that such protocols are possible in principle (because Coda takes that approach), but we also know that they’ve very difficult to engineer (again, from Coda’s experience, and others’). A big barrier is that a lot more of the transaction parsing and logic needs to be implemented “inside the circuit”, which is difficult to implement and audit.

Can you share your thoughts on this?

(Yes, the above just rephrases one of my flight plan questions from November 2019, which never got answered.)

15 Likes

I used to think it would be too slow, but fortunately, Halo has pretty efficient batch verification. I think that the batch verification, along with some improved DoS resistance measures, will be fast enough even without using recursive proofs.

If it turns out that batch verification still isn’t efficient enough after we’ve finished optimizing, then we have some fallback ideas, but those aren’t cooked enough to explain yet.

9 Likes

Cool. How fast is batching? How slow are single transactions?
And how do you plan on handling the batching vs latency trade off in mempool?

2 Likes

@daira, do you have estimates of the batch verification times?

Is it clear that batch verification really applies in all the pertinent workflows? Some that come to mind:

  • peer-to-peer tx receipt workflow — higher latency before transactions can be verified (as unconfirmed)
  • mempool propagation — do you drastically slow down the broadcast propagation speed, to batch-verify transactions at every hop?
  • miners building block templates — can’t include recent-received transactions which aren’t already in the latest batch verification
  • miners verifying previous blocks — do you delay until batch verification is done? or blindly mine on top of possibly corrupted blocks?

So there are non-obvious UX and dynamics/economics question here, before one can conclude that Halo, even with batch verification, is applicable. Which surprises me, because this means that a tremendous amount of work seems invested in a cryptographic component which may not even be useful to Zcash.

3 Likes

Congratulations! This is really exciting news :slight_smile:

12 Likes

Right now we don’t have concrete figures (only estimates that I’m wary of sharing for fear of inaccuracy), but the vast number of different optimizations and strategies we have available to us (some of which are well known, others we have been cooking up) has led me to prematurely conclude that we will ultimately have something that performs competitively with the existing protocol. Obviously, we’ll have to prove it, and we’ll update everyone with benchmarks and describe our ideas in more detail.

It’s like with Sapling, where at some point we figured out that the performance gains were massive and the road ahead for additional optimizations was vast, so we were confident in committing (publicly) that we intended to go down that path and produce something for the protocol that was safe and addressed pertinent issues.

We’ve now hit that point with Halo and are beginning the process of producing something for the community to consider. :slight_smile:

Which surprises me, because this means that a tremendous amount of work seems invested in a cryptographic component which may not even be useful to Zcash.

@daira alluded to “fallback” ideas for if batch verification doesn’t pan out, but these are really crucial ideas that make batch verification concerns less of an issue in practice and it’s why we really aren’t worried. This includes applying the accumulation strategy from the Halo paper to make batch verification nearly as quick as checking a single proof. We have clever ideas for how we can incorporate this strategy in a broad set of scenarios.

15 Likes

But @ebfull , it isn’t like with Sapling. Sapling is brilliant but it was a very straightforwards approach: make one piece of Zcash go faster. It was like switching to a faster processor. Nothing else in Zcash needed to changed. That isn’t true here.

In order to take advantage of Halo, things need to change. Even to keep existing performance and not make Zcash slower, it seems things need to change. You aren’t saying you have gotten individual halo tx size and verification time down to something like sapling, right?

Cocktail napkin math, what are we talking about for size and time?
And what about Eran’s very real issues with batching ?

For everyone else reading this and wondering whats going on:
Halo isn’t a drop in replacement for our existing zero-knowledge proofs. Far from it.

What Zcash really?
Zcash is pretty simple. Take a bitcoin payment and instead of saying this previous payment(UTXO) is where I got the money I’m spending money from, you replace it with a zero-knowledge proof that the money exists. Since the proof hides which money you are spending, you get privacy. The proof is constant size and fast to verify. Because of this it is really not much different than an ECDSA signature in Bitcoin as far as the blockchain itself goes. So integrating it is merely (a lot of and very tricky) software engineering. I say this as the guy who worked this all out and did that engineering originally on the paper and prototype of Zerocash. This became Zcash and @ebfull and @daira rightly re-did that software from scratch much better. Eran was on that paper with me, I remember working out this stuff with him and what my co-authors and I invented has been the way Zcash has operated since. The downside of all of this is the snark we use (now groth16 then BCTV14b) requires a multi party setup assumption. Ideally you’d like to replace it with something else.

Whats Halo?
So that’s Halo right? Well, in a word, sorta. Halo isn’t just a zksnark without trusted setup. In fact, it is not really a zksnark in that an individual proof is not fully succinct. So proofs are big and take longer time to verify. If you just dropped those into Zcash, it would almost certainly get slower. We’d be less scalable. Consensus might even get tricky. The brilliant part of Halo is that if you take a bunch of those proofs, say a whole block full of halo shielded transactions, you can do some fancy things to combine them (either aggregation or recursion) and wind up with something that is not as expensive to verify as all of those individual halo transactions. But you have to change Zcash to have it do aggregation/recursion somewhere. that’s a consensus change in all likelihood. And doing recursion is computationally expensive, so its a tricky one.

Whats the problem?
But there’s this thing Eran and I and others cannot figure out: where do you do aggregation/recursion and how does it make zcash more scalable? And keep in mind, we are the people who worked out the original Zerocash design — fully succinct snark instead of a pointer to a UTXO and an ECDSA signature – that Zcash uses to this day. This doesn’t mean Halo for Zcash is impossible, but its a pretty good hint there a hell of a lot that needs to be worked out and it might not even work. These cannot be hand waved over. They need to be set out clearly.

Whats needed
@daira suggests batching, But as Eran points out, there are number of places where you need to verify transactions and batching is tricky to do. So, how do we deal with that and the other issues that pop up? We don’t need code or detailed specs, just something that would pass a white board discussion amongst experts. Like I did when I worked out the approach Zcash still uses and @ebfull did for Sapling’s optimizations. And those were simpler systems!

9 Likes

All interesting points here, I just wanted to chime in to say fantastic work by the team!

This kinda stuff makes me proud to be part of the Zcash community, so many smart and respectful people sets Zcash apart from the others.

SmoothHighlevelCaterpillar-small

8 Likes

We’re just not worried about those concerns, and you’re completely over-exaggerating them. There is not “a hell of a lot” that needs to be worked out. We understand the questions @tromer raised and we’ve spent a great deal of time thinking about those problems and how feasible our approach is. We are confident in moving forward.

If you look at the blog post, it says that our first milestone is:

Publish a development branch using PLONK, including benchmarking for various circuit sizes.

That’s what I’m going to focus on instead of arguing about it.

13 Likes

Are these ideas listed anywhere publicly?

2 Likes

Not yet, but we plan to have intuitive and detailed descriptions of the cryptography in notes that accompany the code so that others can learn and contribute.

6 Likes

Hi @ebfull
Circuit benchmarks will be useful, so I look forward to that. But that probably will tell us what we all expect and know from other similar snarks: these things are fairly slow to validate and fairly large.
If not, awesome, we have some crazy optimizations. Then we can see what those do for Halo and what they do for sapling/plonk.

But everything we know now suggests Halo proofs will be slower and larger. Which, again is fine: you can use recursion or aggregation to handle it. In fact, even if Halo is fast, the scaling is from recursion/aggregation. Thats the entire brilliant trick in Halo. So the question is: how do we use it in Zcash?

This isn’t a question of circuits or snarks. It’s a question of overall system design. To make Halo work, since it’s fundamentally not a snark in the way sapling/zcash is today, one needs to change a bunch of things. Thats what I meant by a “A hell of a lot of details.” I’m more that willing to believe there are solutions and you guys worked it all out, but then please tell us what they are.

All i’ve seen, so far, when people like Eran ask for details, is handwaving and the implication that these are just small details that are easily solved. So the reason I am jumping up and down and stressing what I’ve contributed to Zcash and my expertise, is to make very clear the following: these are not mere details that can be left to later. They are the difference between Halo working for Zcash and it not doing anything effective. And the answers are not obvious or simple. And that’s not an exaggeration.

To get that across, evidently, I have to appeal to authority. Which I don’t like, but in the absence of information, it’s the only thing that can be said.

So please, put up a sketch of the overall design. Not of Halo or the circuit, but how you use it in Zcash. Public discussion, peer review, and evaluation is what makes Zcash great. It is what differentials us from both the snake oil cryptography cryptocurrencies and the zk-hype cryptocurrencies. It’s how we got here.

7 Likes

Of course we will. That’s how we have always worked. Expect that detail to be discussed on GitHub, and I expect we’ll be doing a talk and slides on it at some point.

Edit: several GitHub issues have been opened for design issues. They are linked from issue zcash/zcash#4707. GitHub is for technical discussions, so please keep them on the topic of each issue.

7 Likes

This is a great discussion here. Keep up the great work guys!

1 Like

Just to clarify, we don’t have performance numbers yet, but I’ve run some tests locally on crappy code which made me quite optimistic. I don’t want to commit to that, since we’re writing from scratch and being more rigorous and paying more attention to detail. Things could change. That’s why our next milestone is to get benchmarks.

I think a discussion right now about things like batch verification is premature and we aren’t prepared to have that discussion yet.

9 Likes

Do you think you will have some preliminary numbers by the end of this year?

Oh yes, probably within the next month or so.

5 Likes
7 Likes

Is there any reason why all these details on Halo 2 were apparently conceived of, developed, and discussed only internally, and are just now being shared publicly?

I don’t like the idea that the Zcash community pays for ECC’s work, but gets the same “stay tuned for eventual secret announcements!” treatment that other private companies pull. It feels sleazy and corporate.

1 Like