Collaborative SNARKs

(See https://eprint.iacr.org/2021/1530.)

Suppose we have $n$ parties, represented by integers $i \in [n]$, that each hold some private witness $w_i$. We would like to verifiably compute some function (encoded as a circuit $C$) on all of their inputs $C(w_1, \dots, w_n)$ while keeping $w_i$ secret. In other words, we want to generate a SNARK proof that $C(w_1, \dots, w_n)=y$ while preserving privacy. For example, suppose we want to prove that all parties have some trust scores $w_i$ that fall within a certain range of each other, but we don’t want to reveal anyone’s exact trust score.

One way we could do this is by using MPC Fully Homomorphic Encryption (FHE). Each party would feed encryptions $\operatorname{Enc}(w_i)$ to a server, which then runs a circuit representing SNARK proof generation within FHE. The server would then give the encrypted proof for users to collectively decrypt. However, there are two drawbacks to this approach, namely that (i) it requires a central server to run the circuit computation, and (ii) FHE is expensive. What if instead we wanted to verifiably compute $C(w_1, \dots, w_i)$ in a decentralized way? This is what Collaborative SNARKs let us do.

At a high level, a Collaborative SNARK will be a circuit representing the SNARK proving protocol on some private inputs $w_i$ and public inputs $y_i$. Each party has their private inputs to only some of the input wires of this circuit. We need to compute this circuit in a distributed way, where each party is computing their own circuit, but we haven’t yet figured out what parties should be plugging in for the wires that correspond to the other parties’ secrets.

It turns out the parties will distribute their secret to the other parties in a way that hides the secret, using something called Secret Sharing. We’ll discuss this in more detail before returning to the high-level Collaborative SNARK protocol.

Secret Sharing

In this post, we introduce the notion of secret sharing, discuss how to perform arbitrary circuit computations using a tool called Beaver triples, which will lead us into our next post on Collaborative SNARKs.

Suppose we have some secret $s$ and $n$ parties, represented by integers $i \in [n].$ We want to somehow “split” this secret among the $n$ parties, so that no one can recover $s$ unless all parties communicate with each other. This is called “secret-sharing”.

The most basic scheme is to give each party a share $s_i$ such that $s_1 + \dots + s_n = s$. How can we ensure this doesn’t reveal any information about $s$ unless all parties collude? We can simply let $s_1, \dots, s_{n-1}$ be randomly generated (say from $\mathbb{F}_q$ for some large prime $q$), and set $s_n = s - \sum_i^{n-1} s_i$. Then each $s_i$ individually is distributed uniformly at random (in $\mathbb{F}_q$), so any $n-1$ parties cannot uncover information about $s$ by talking to each other. There are also other secret sharing schemes, such as Shamir Secret Sharing. It is also possible to define a $t$-of-$n$ secret sharing scheme, which just means that if at least $t$ parties collude then they can recover the secret, and otherwise parties cannot gain any information about the secret. We do not go into detail in this blog post.

Now we want to see how to do a few basic circuit operations on these secret shares. Throughout, let $[s] = \{s_1, \dots, s_n\}$ denote the set of secret shares of $s.$

Basic circuit operations on secret shares

Suppose we have secret shares $[x] = \{x_1, \dots, x_n\}$ and $[y]=\{y_1, \dots, y_n\}.$ Then we can do the following operations on our secret(s) and obtain the corresponding secret shares:

• Add a public constant $a$: We can compute the shares $[s + a] = \{s_1 + \frac{a}{n}, \dots, s_n + \frac{a}{n}\}$, where each person adds $\frac{a}{n}$ to their share. Again, we can verify that $\sum_i^n (s_i + \frac{a}{n}) = \sum_i^n s_i + n \cdot \frac{a}{n} = s + a.$
• Multiply by a public constant $a$: We can compute the shares $[as] = \{as_1, \dots, as_n\}$, where each person can just multiply their own share $s_i$ by constant $a$. We can verify that $\sum_i^n as_1 = as$ as desired.
• Add two secrets: Suppose we have secret shares $[x]$ and $[y]$. We can compute the shares $[x+y] = \{x_1 + y_1, \dots, x_n+y_n\}$. We can verify again that $\sum_i^n (x_i + y_i) = \sum_i^n x_i + \sum_i^n y_i = x+y.$

Question: How do we multiply two secrets?

For example, we can’t just multiply our secret shares $x_iy_i$ to obtain secret shares of $xy$, since in general $\sum_i x_iy_i \neq (\sum_i x_i)(\sum_i y_i)$.

It turns out that we need (i) communication and (ii) some pre-generated random shares that have some nice correlation. You can think of the purpose of these random values as blinding factors that allow parties to reveal expressions involving their shares that other parties can then can compute on, without revealing the shares themselves. These random shares are called Beaver triples, which we describe below.

Beaver Triples

At the moment, the parties have shares $[x]$ and $[y]$. Here is the additional information we need:

A Beaver triple is a triple of random shares $[a], [b], [c]$ where $c = ab$. Suppose a trusted administrator chooses secret values of $a$, $b$, and $c=ab$, then distributes shares of $[a]$, $[b]$, $[c]$ to the parties (without revealing $a$, $b$, $c$).

We show how this auxiliary share can be used to help the party shares for $[xy]$.

The key is to notice that because $a$ and $b$ are random values, their shares are also random. Therefore, it is safe for a party to reveal their share $x_i + a_i$ of $[x+a]$ since $a_i$ blinds $x_i$. In fact, it is safe for all parties to reveal their shares $x_i + a_i$, since reconstructing $x + a$ still hides $x$.

Now we can compute $[xy]$ as follows, using the existing basic circuit operations previously outlined.

Multiply two secrets:

• Have each party reveal $x_i + a_i$ to the whole group, so everyone computes $x+a$. Similarly everyone can compute $y + b$.
• Now parties can compute $[(x+a)y]$, since $x+a$ is just a public constant. Similarly, parties can compute $[(y+b)x]$.
• All parties compute $[(x+a)y + (y+b)x] = [2xy + ay + bx]$ as a sum of the two shares above.
• Now they can compute $[2xy + ay + bx - (x+a)(y+b)] = [xy - ab]$, since $(x+a)(y+b)$ is just a public constant.
• Finally, they can compute $[xy-ab + c] = [xy]$, since they have the secret shares $[c] = [ab]$.

To recap, given secret shares $[x]$ and $[y]$, we can now obtain secret shares of the following:

• $[x+k]$ for some public constant $k$
• $[kx]$ for some public constant $k$
• $[x+y]$
• $[xy]$

Note that these four operations allow us to perform an arbitrary circuit computation (with addition and multiplication gates) on secrets, while staying in secret share form.

Fitting everything together

Recall that we wanted to somehow do a distributed computation of a circuit representing a SNARK prover on secret inputs $w_i$, but we didn’t know what each party should plug into the wires corresponding to secrets they don’t own. Now that we have a secret sharing scheme, we can simply have each party compute secret shares of their secret $[w_i]$ and distribute them to the other parties.

Finally, we already showed earlier how to do arbitrary circuit computations on secrets in a distributed, secret share form. This means the parties can compute secret shares of the proof, and do a round of communication to sum up their shares and recover the desired SNARK proof!