# Collaborative zk-SNARKs --- Problem: zk-SNARKs do not work on distributed secrets ---  ---  --- co-SNARKs and Publicly Auditable MPC (PA-MPC) are *almost* the same thing. The first solves the following problem: *generating a proof when the secret data is distributed among multiple parties* The second solves the following problem: *Output generated by a MPC protocol are not verifiable by a party that wasn't involved into the MPC (third-party verifiability)* --- ### t zero knowledge  --- ### Implementation The paper defines the implementation of co-SNARKs with Elliptic-curve and pairing based zk-SNARKs constructions such as: - Groth16 - Marlin (KZG) - Plonk (KZG) --- ### Constraint Defintion co-SNARKs work with R1CS relations to define arithmetic constraints inside the circuit. Computation -> Arithmetic Circuits -> R1CS constraints. In order to support the MPC protocol, co-SNARKs work with secret shares of the witness to be fed into the R1CS. In particular, we assume that at the beginning of the protocol the witness $w$ is secret shared among the parties $[w]$. --- ### Approaches to PA-MPC --- **Approach #1**: Snarkify the MPC  --- **Approach #2**: MPC the Prover  --- Paper goes for Approach #2 ---  --- The goal of the paper is to define techniques that are able to achieve this composition between two protocols without incurring into a 1M times slowdown. Schemes used are: - SPDZ - authenticated additive shares - malicious and dishonest majority - GSZ - shamir shares - passive (honest-but-curious) and honest majority ---  --- Do not support the property of *guaranteed output delivery*. Therefore we are gonna assume that all the $N$ parties joining the protocol as provers do want to generate the proof and therefore dropping off the protocol is against their interest. --- ### Bottlenecks "Traditional" zk prover bottlenecks: - Elliptic curve operations - Fourier Transforms - Polynomial Commitments --- ### Bottlenecks MPC bottlenecks: - Polynomial Division - Sequence of products (typical to PLONK) - Merkle Tree evaluations and hashing (for hashing-based SNARKs) --- ### Elliptic Curve Operations - Naive A naive approach to perform EC operations inside MPC would be to define a point on the curve as a set of $x, y$ coordinates. This approach is not efficient because the EC addition formula involves a lot of multiplications in the field, which is not good in MPC! --- ### Elliptic Curve Operations - Efficient The second option is to share the points themselves using an EC additive secret sharing.  Now elliptic curve addition (and scalar multiplication) become a linear operation that can be performed locally with no-cost and no-communication between the parties. --- ### KZG Commitments Each party locally commits to their individual share of the polynomial to be committed. The results can be interpreted as shares of the desired polynomial commitment. Given that such polynomial commitment it is required to be public, the polynomial commitment can be recovered starting from the shares of the parties. --- ### Performance ---  ---  ---  ---  --- ## Conclusions - Collaborative snarks suits better for elliptic curve based SNARK rather than hashing based SNARKs because performing hashing is an highly non-linear computation that is not efficient inside a MPC - Wrapping ZKP inside MPC makes more sense as a general approach rather than the opposite - In particular, the performance shows a 1x/2x slowdown between the single player proof generation and the multi-party proof generation. This is due to optimization techniques that transformed many of the main zkp bottlenecks into linear operations that are really efficient to translate into MPC. --- ### Followups - [ ] Compare it to other publicly verifiable MPC protocols such as https://eprint.iacr.org/2014/075.pdf - [ ] How to write a circuit with Co-SNARKs? - [ ] Does it support the offline phase too?