This is the reading note and a preparation for the paper-sharing session during my stay at the Antalpha Lab Chiang Mai Hacker House 2024. Special thanks to Dr. Yu Guo, PinHao, Gunit for the discussion on the paper understanding and everyone in the hacker house 💛, and the reviewers from TEM!

zkSNARKs are helpful because they’re generic and privacy-preserving. However, the major limitation is that only a single party with a witness could compile the proof. This limitation is barring zkSNARKs from some applications where multiple parties with individual secrets are needed to generate the proof collaboratively.

What if there exists a solution that we can compute the zk-SNARK proofs with multiparty? This would enable some useful applications:

1. Outsource ZKP computation:
   Imagine using your phone to do computation-heavy ZKP. One solution is to share the secret and have the other server compute for you, but we would not want that, as the secret would no longer be a secret. Instead, we could use coSNARK and separate the secret into pieces, send them to separated servers, and have the servers compute the result for you, and none of them would be able to know the whole secret.
2. Public auditable MPC from collaborative proofs:
   One of the core features of combining MPC with ZKP is verifiability for MPC computation. The combination extends secure MPC to produce proof that the computation was performed correctly can be checked on individually and eliminates the need for auditor participation.

For more use cases I suggest checking out Taceo’s documentation

To make coSNARK possible, a naive thought is to “MPC” the prover. MPC stands for Multi-Party Computation, it will take in a function to compute the output and the input from multi-parties, and the participants would not be able to learn the inputs of other parties. While this could work, in practice if we were to compute the zk-SNARK as the function in the general purpose MPC it’ll be inefficient. zkSNARK proof generation is roughly 1000x slower than the verification, MPC itself is also roughly 1,000x solwer than the underlying computation. MPC the prover will introduce a 1,000,000x slowdown. The research goal of this paper is to find out the solution that limits the slowdown to only 1,000x ~ 2,000x.

coSNARK

The definition of coSNARK is similar to what we have in conventional zkSNARK with the proving steps being distributed to multiple provers.

What do we do now we know our goal is to combine MPC and zkSNARK somehow? The strategy is as follows:

• Choose the suitable MPC scheme — SPDZ and GSZ
• Generalize the zkSNARK scheme for multi provers
• Optimization

Choose the suitable MPC scheme — SPDZ and GSZ

SPDZ is a dishonest majority MPC protocol and GSZ is an honest majority MPC protocol, both of them are linear secret-sharing schemes. SPDZ is using additive secret sharing and GSZ is using shamir secret sharing. The previous paper shows that SPDZ could operate on the elliptic curve group and the same for GSZ since it uses Shamir Secret Sharing under the hood. Operating directly on the elliptic curve group largely decreases the communication cost compared to when we compute on the base field. In my understanding, linear secret sharing + ability to operate on an elliptic curve group make these two MPC schemes good options for coSNARK.

Generalized zkSNARKs for multi provers

There are lots of building blocks in zkSNARKs, and here we want to address the MPC protocol for polynomial comments. Here we utilize the linear reconstruction ability from a linear sharing scheme, meaning each party could compute their shares and prove individually and combine them together as a valid commit or proof.

Using KZG as an example:
As the function is shared already, the question is in the commit and proving stage, the operations remain the same for setup and check. The paper argues that linear reconstruction for the commit and proving stage would allow multiparty to compute their parts individually and still be correct and secure.

Optimization

We now look at how to optimize the computation by looking into the individual “gadgets” within a zkSNARK. The paper includes other proving schemes, and here I’ll focus on plonk for easy understanding. FFT, MSM, polynomial division, and product check are the main gadgets, and we’ll walk through them one by one.

FFT and MSM are linear operations, in the MPC style each party could compute their shares locally without communication and then combine them, this is exciting because the traditional bottlenecks do not bring more overhead when we do them in the MPC style.

Polynomial division is a nonlinear and complex operation, however in most snarks for example in KZG we’ll be using public value to construct the polynomial to be divided, as this would not be changed with different witness input shares, this would not introduce more overhead in the MPC fashion.

Lastly product check, to product check on all parties, we need to multiply all n shares from each individual, naively this could take up n-1 rounds of communication, by using a trick proposed by Barr-Ilan and Beaver, we could parallelize the product check process and make the communication cost constant. The high-level idea is that the parties agree on a set of shared random numbers, and the parties encrypt their parts with the random numbers and the inverse of the last random number, when combining the encrypted parts together the random number will cancel out with only the first random number and the inverse of the last random number.

Performance

The performance from the experiment is exciting, schemes using GSZ (honest majority) could achieve almost the same runtime as the Single Prover, and for SPDZ (dishonest majority) the schemes only introduce a 2x slow down, in this sense the application that could tolerance the runtime of single prover should also be able to use multiple provers, and that coSNARKs are practical.

When the constraint size is small, the multi-prover methods are slower because the network communication cost dominates. And because the number of communications is sub-linear in constraints, the multi-prover performs quite well when the constraint is bigger.

The honest majority provers (GSZ) have essentially the same runtime as a single prover and the 2x runtime increase from SPDZ comes from how SPDZ uses message authentication code (MAC) in the protocol, from a high level one could think that computing with SPDZ we need to operate on the message itself and the MAC, leading to 2x computation.

Closing note

I first heard of coSNARK in the ZK Podcast and got curious about how it works under the hood. This paper is also good for starters in ZKP (aka me) since it broadly covers the topics of different ZKP schemes, the gadgets used, and MPC. Not scary with too much math and is a good learning source to get the general idea across the board.

For some recent breakthroughs, Taceo, cursive, and PSE collaborative launched the coSNARK alphanet, this blog walks through the high level design and the process! I think it’s a good read to see how coSNARKs are used IRL.

References

• Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets
• coSNARK implementation by Alex
• talk by Alex
• coSNARKs from TACEO on ZeroKnowledge Podcast

A Short Note on Collaborative zkSNARKs was originally published in Taipei Ethereum Meetup on Medium, where people are continuing the conversation by highlighting and responding to this story.