Improved zk-SNARK Multi-party Computation Protocol

zk-SNARKs – the zero-knowledge proofs at the core of Zcash – require a parameter generation ceremony to take place for every statement that you wish to create proofs about. Although privacy is protected by zk-SNARKs unconditionally, if this ceremony is compromised it becomes possible to counterfeit Zcash. It is thus important for us to ensure these parameters are created securely.

Last year, Zcash performed such a ceremony using a multi-party computation (MPC) protocol. These protocols have the property that only one party needs to be uncompromised for the resulting parameters to be secure. In other words, in order to compromise the ceremony, every participant needed to be compromised.

However, the protocol we used for the ceremony could not scale beyond a handful of participants. As we continue to upgrade Zcash, we will need to perform more of these setups, so improving the scalability and performance of this protocol is important to us. Also, projects outside Zcash that wish to use zk-SNARKs may need to perform their own setups, so we’d like to make it cheaper and easier for them as well.

Ariel Gabizon, Ian Miers and I have just published a paper detailing a new MPC protocol which can scale to a practically unbounded number of participants. The paper also includes the strengthened elliptic curve construction, BLS12-381, which we’ve blogged about before.

Player-exchangeable MPC

In the original MPC protocol, all participants needed to commit to their share of the “toxic waste” in advance in order to protect against adaptive attacks. This meant that all of the participants needed to be available for the entire duration of the protocol, and nobody could abort without causing the entire protocol to abort. Participants needed to maintain custody of their hardware throughout the process, so this meant the ceremony could not scale beyond a handful of people.

Our new protocol is what we like to call a player-exchangeable MPC. As before, only one participant needs to be honest for the ceremony to be secure. But unlike before, participants join the protocol, do their part and leave immediately. This allows the ceremony to scale to a large number of participants and take place over a longer period of time. It also decreases the surface area of attack for participants and avoids the need for expensive synchronization.

Two phases

The original MPC protocol involved three phases of computation. Participants needed to act and then wait for their turn in the next phase. In between the first and second phase, we needed to perform very expensive fast-fourier transforms. As a result of all this, performance of the original MPC was poor.

In the new protocol, we’ve managed to reduce the MPC to two phases. What’s more, the first phase is agnostic to the precise zk-SNARK circuit, and so a large communal ceremony can be performed which evaluates this phase for all projects that wish to use zk-SNARKs. The second phase does not involve fast-fourier transforms, which means that MPCs for Zcash and other projects can scale to an unbounded number of participants without overly expensive computations.

We have begun an implementation of this first phase of the multi-party computation ceremony, written in Rust, which uses the new BLS12-381 elliptic curve.

Summary

This new protocol allows for far more secure zk-SNARK parameter generation ceremonies:

  • It allows the ceremony to involve a larger number of participants, with the same property that only one of them needs to be honest to guarantee the parameters are secure.
  • It allows us to give participants significant flexibility in the hardware and operating system they use to participate. As a result, it allows us to reduce the number of dependencies and code that we must audit.
  • It greatly reduces the time participants must spend in the ceremony, reducing the surface area of attacks and allowing a broader set of participants to contribute.
  • It uses a stronger elliptic curve construction which improves security.

We look forward to sharing more details about zk-SNARK parameter generation ceremonies in the near future.