In a companion post I explained how coSNARKs work. The key takeaway from that post is that the logic of the prover must be distributed over multiple nodes. To avoid leaking the witness, the logic must be run over secret-shared data.
In this post I will hoover over the details to run the logic on secret-shared data. Many popular schemes operate over elliptic curves. Common operations that the provers of these schemes perform include
-
group operations,
-
multi-scalar multiplications (MSMs),
-
number-theoretic transforms (NTTs).
Group operation over secret-shared data
Two secret-sharing schemes were considered in [BO21]. Additive secret sharing with information-theoretic MACs, and Shamir secret-sharing. The exact secret-sharing depends on the chosen MPC protocol. [SPDZ] uses the former, and [GSZ] uses the latter.
An inefficient solution: secret-sharing point coordinates. Both secret-sharing schemes are defined over finite fields. One naive approach would be secret-share the coordinates (over the base field) of the curve points, and run the group operation in MPC. This is not efficient, though. Point addition requires multiplication in the base field; which means that rounds of interactions are needed. What is worse, scalar multiplication requires even more field multiplications, yielding unacceptable performance in terms of bandwidth.
Secret-sharing points directly. The efficient solution is to define the secret-sharing schemes over curve points. That is, the shares of point G are also points in the curve. Since the secret-sharing is linear, point addition G_1+G_2 requires no communication.
Also, scalar multiplication x\cdot G when the base G is constant (publicly known) is also linear; so it does not require communication neither.
The only operation that needs interaction is scalar multiplication of a secret-shared scalar [x] by a secret-shared point [G]. The situations is not as simple as depicted above, but [SPDZ] shares can be defined over curves (shown in [ST19]), as well as Shamir shares (shown in [BO21]).
Multi-scalar multiplications over secret-shared data
A scalar multiplication is defined as M = x_1 \cdot G_1+\cdots + x_\ell \cdot G_\ell, where G_i are curve points and x_i are scalars (elements of the exponent field). Note that an MSM is linear in the scalars. Therefore, if the bases G_i are public, but the scalars x_i are secret-shared, the MSM requires no communication.
MSMs are used at several points. For example, when committing to a polynomial using KZG.
Number-theoretic transform (NTT)
Provers need to convert polynomials p(X) = \sum_j c_j X^j, over the exponent field of the curve, from its coefficient representation \vec c = (c_0,\ldots, c_n) to its point-wise representation \vec y = (y_1,\ldots, y_{n+1}), where y_i = p(\omega_j). The other direction, from point-wise to coefficient representation, is also needed. This is a matrix-multiplication transformation:
The matrix \mathbf{W} with the evaluation points is public. Therefore, \vec{y} = \mathbf{W}\cdot \vec{c} is linear. However, matrix multiplication is slow (it takes O(n^2) field operations), so provers do not do it this way. The number-theoretic transform (NTT) is used to speed up the process. The idea behind NTTs exploits the structure of the n-th roots of unity \omega_j; but understanding the algorithm is beyond the scope of this post (see this article if it really itches you). The important point to be made is that NTTs (and its inverse) are also linear operations in \vec c (and the inverse in \vec y). So they both can be run distributedly without requring communication in secret-shared data [\vec c] and [\vec y], respectively.
Other operations that need to be distributed
Some provers also do other, more evolved, operations. These include polynomial division, sum checks, and partial product checks. To keep things simple, I will do not discuss how to distribute these more evolved operations.
Ammenable schemes to distribute the prover
The following table (based on [Fig.5, BO21]) lists popular schemes and the type of operations their provers need to perform.
