<style> .reveal { font-size: 24px; } </style> --- # Collaborative zkSNARKs A solution for verifiable multiparty computation --- ## What's the problem? 1. use data that is held by many parties 2. not reveal any more data to each party than what they already have 3. compute securely over this data 4. _produce a proof of correct computation and output_ 1, 2 and 3 together constitute classical multiparty computation. Adding 4 provides _verifiability_ to our multiparty computation --- ## Existing solutions - MPC: an old and well studied primitive - 2 kinds: honest majority and dishonest majority - For honest majority: Yao's garbled circuits, GSZ etc. - For dishonest majority: SPDZ, Overdrive etc. - Proofs for verifiability - SNARKs: Groth16, Marlin, Plonk etc. - STARKs --- ## Arithmetic circuits Arithmetic circuits are circuits constructed from two gates, multiplication $\otimes$ and and addition $\oplus$. The algorithms we implement will compile to something similar.  --- ## A taste of MPC Shares of a secret $x\in \mathbb{F}$ are distributed among parties. $[x] = x_1 + x_2$ $[y] = y_1 + y_2$ addition is easy (just do it locally, then share result) $[x+y] = (x_1 + y_1) + (x_2 + y_2)$ multiplication is hard (needs communication and also reveals shares) $[xy] = (x_1x_2) + \underline{x_1y_2 + y_1x_2} + (y_1y_2)$ addition + multiplication are universal for arithmetic circuits (Note all operations are modulo prime $p$, determined by $\mathbb{F}$) --- ## the SPDZ protocol All data is represented as elements of $\mathbb{F}$. Consider $n$ parties, $n-1$ are malicious. A key $\alpha \in \mathbb{F}$ is predetermined, each participant has share $\alpha_i$. $$ \alpha = \sum \alpha_i $$ Say our data is $x$. Each party holds - a data share $x_i$ - a MAC share $\gamma_i(x)$ $$ \alpha = \sum \gamma_i(x) $$ --- ## Addition and multiplication in SPDZ Preprocessing: we pre-computed sets of triples ([a], [b], [ab]) Addition or multiplication by a constant is trivial: - add $x_i + y_i$ and $\gamma_i(x) + \gamma_i(y)$ - multiply $k\cdot x_i$ and $k\cdot \gamma(x_i)$ Multiplication: We use one set of triples ([a], [b], [ab]) to do multiplication (Very interesting but a bit complex, can explain if there is time later) The verification uses the MAC shares --- ## PLONK Plonk has 3 stages: 1. Setup: We pick a certain point on an elliptic curve, and iteratively multiply it with a randomly-chosen secret scalar, to generate more points on the curve (Some more data is also generated). This set of points is then distributed among all provers, and is used in proof generation. The number of points depends linearly on the circuit depth. 2. Prove: The statement to be proven is expressed in terms of an arithmetic circuit. After a series of rounds, a proof is generated. 3. Verify: The verifier checks the proof. If the verification passes, the proof is verified. --- Say I wanna prove I know a Pythagorean triple $x_1, x_2, x_3$, such that $x_1^2 + x_2^2 = x_3^2$. Since PLONK allows only 1 addition or multiplication at a time, we express these _constraints_ as $x_1 \times x_1 = x_4, \quad x_2 \times x_2 = x_5$ $x_3 \times x_3 = x_6,\quad x_4 + x_5 = x_6$ where $x_4, x_5, x_6$ are ephemeral values. --- A simple generic PLONK circuit looks like: $$q_l\cdot a + q_r\cdot b + q_o\cdot c + q_m\cdot a\cdot b + q_p = 0$$ Notice that if $q_l$ and $q_r = 1$ and $q_o = -1$ (and the other $q$'s 0) we get the addition gate $a + b - c =0$. Similar, if $q_m$ and $q_o = 1$ (and the $q$'s 0), we get $ab=c$, the multiplication gate. So for the Pythagorean triples, our constraints are:  We now construct vectors $q_l = (0,0,0,1) , a = (3, 4, 5, 9)$ etc. and do some **magic** to obtain polynomials. We also have polynomials to encode relations between outputs and inputs of different gates (joining wires in the arithmetic circuit). --- ## Observation 1. Linear operations (addition or multiplying by a fixed value) are cheap, even in MPC. 2. Polynomials (which are an important part of the PLONK proof) are constructed by linear operations. However, in the KZG commitment, polynomials are not evaluated on scalars but on elliptic curve points. So to get a better MPC protocol, instead of arithmetic circuits, we work over elliptic curve circuits! Elliptic curve circuits = arithmetic circuits + linear operations over curve points --- ## KZG with multiple provers KZG is a commitment scheme for committing to an polynomial $f$ by evaluations over an elliptic curve. $c = f(\alpha)\cdot g$ for $\alpha \in \mathbb{F}$ randomly chosen in the Setup phase, and $g$ a point on the curve. How to make a commitment [c] to a secret shared polynomial $[f]$: Let $f = f_0 + f_1x + f_2x^2 ... f_dx^d$ Then [f] is determined by the list $[f_0], [f_1]..$, where $f_i$ are secret shares with party $i$. Then each party commit: $c^i = f_0^i + f_1^i(\alpha\cdot g) + f_2^i (\alpha^2\cdot g) + ...$ which is a share of the secret [c]. There is another phase of KZG that needs to be modified but the idea is the same; exploit linearity! --- Traditional bottlenecks 1. Fast fourier transforms: matrix multiplication 2. Multiscalar multiplications: linear combinations of curve points What do these bottlenecks have in common? Linearity! Again, we can split them into shares that can be computed by parties locally. The paper also gives a way to adaptthe PRODCHECK protocol in Plonk to a multiprover setting. ---  --- Benchmarks https://eprint.iacr.org/2021/1530.pdf ---