**Experimenting with Collaborative zk-SNARKs: Zero-Knowledge Proofs for Distributed Secrets**

*Alex Ozdemir and Dan Boneh*

**Abstract: **A zk-SNARK is a powerful cryptographic primitive that provides a
succinct and efficiently checkable argument that the prover has a
witness to a public NP statement, without revealing the witness.
However, in their native form, zk-SNARKs only apply to a secret witness
held by a single party. In practice, a collection of parties often need
to a prove a statement where the secret witness is distributed or shared
among them.

We implement and experiment with *collaborative zk-SNARKs*: proofs over the secrets of multiple, mutually distrusting parties. We construct these by lifting conventional zk-SNARKs into secure protocols among $N$ provers to jointly produce a single proof over the distributed witness. We optimize the proof generation algorithm in pairing-based zk-SNARKs so that algebraic techniques for multiparty computation (MPC) yield efficient proof generation protocols. For some zk-SNARKs, optimization is more challenging. This suggests MPC "friendliness" as an additional criterion for evaluating zk-SNARKs.

We implement 3 collaborative proofs and evaluate the concrete cost of proof generation. We find that over a good network, security against a malicious minority of provers can be achieved with *approximately the same runtime* as a single prover. Security against $N-1$ malicious provers requires only a $2\times$ slowdown. This efficiency is unusual: most computations slow down by several orders of magnitude when securely distributed. It is also significant: most server-side applications that can tolerate the cost of a single-prover proof should also be able to tolerate the cost of a collaborative proof.

**Category / Keywords: **cryptographic protocols / zero knowledge, multi-party computation, implementation

**Date: **received 18 Nov 2021, last revised 5 Dec 2021

**Contact author: **aozdemir at cs stanford edu, dabo at cs stanford edu

**Available format(s): **PDF | BibTeX Citation

**Note: **Provide background on & discuss protocols in the same family as GSZ'20.

**Version: **20211205:010944 (All versions of this report)

**Short URL: **ia.cr/2021/1530

[ Cryptology ePrint archive ]