PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge

Ariel Gabizon

Protocol Labs

Zachary J. Williamson Aztec Protocol

Oana Ciobotaru

December 11, 2019

Abstract

zk-SNARK constructions that utilize an updatable universal structured reference + string remove one of the main obstacles in deploying zk-SNARKs[GKM]. The important work of Maller et al. [MBKM19] presented Sonic- the rst potentially practical zk-SNARK with fully succinct verication for general arithmetic circuits with such an SRS. However, the version of Sonic enabling fully succinct verication still requires relatively high proof construction overheads. We present a universal SNARK construction with fully succinct verication, and signicantly lower prover running time (roughly 7.5-20 less group exponentiations than [MBKM19] in the fully succinct verier mode depending on circuit structure).

Similarly to [MBKM19] we rely on a permutation argument based on Bayer and Groth [BG12]. However, we focus on \Evaluations on a subgroup rather than coecients of monomials"; which enables simplifying both the permutation argument and the arithmetization step.

1 Introduction

Due to real-world deployments of zk-SNARKs, it has become of signicant interest to have the structured reference string (SRS) be constructible in a \universal and updatable" fashion. Meaning that the same SRS can be used for statements about all circuits of a certain bounded size; and that at any point in time the SRS can be updated by a new party, such that the honesty of only one party from all updaters up to that point is required for soundness. For brevity, let us call a zk-SNARK with such a setup process universal.

For the purpose of this introduction, let us say a zk-SNARK for circuit satisability is fully succinct if

1.The preprocessing¹ phase/SRS generation run time is quasilinear in circuit size.

2.The prover run time is quasilinear in circuit size.

3.The proof length is logarithmic² in circuit size.

3 4.The verier run time is polylogarithmic in circuit size.

Maller et al. [MBKM19] constructed for the rst time a universal fully succinct zk- SNARK for circuit satisability, called Sonic.

[MBKM19] also give a version of Sonic with dramatically improved prover run time, at the expense of ecient verication only in a certain amortized sense.

1.1 Our results

In this work we give a universal fully-succinct zk-SNARK with signicantly improved prover run time compared to fully-succinct Sonic.

At a high level our improvements stem from a more direct arithmetization of a circuit + as compared to the [BCC 16]-inspired arithmetization of [MBKM19]. This is combined with a permutation argument over univariate evaluations on a multiplicative subgroup rather than over coecients of a bivariate polynomial as in [MBKM19].

$$ [ \mathrm {B C C} ^ {+} 1 6 ] $$

In a nutshell, one reason multiplicative subgroups are useful is that several protocols, including Sonic, use a permutation argument based on Bayer and Groth [BG12]. Ultimately, in the \grand product argument", this reduces to checking relations between coecients of polynomials at \neighbouring monomials".

We observe that if we think of the points *x;*g x as neighbours, where g is a generator of a multiplicative subgroup of a eld F, it is very convenient to check relations between dierent polynomials at such pairs of points.

$$ x,\mathbf{g}\cdot x $$

A related convenience is that multiplicative subgroups interact well with Lagrange bases. For example, suppose H F is a multiplicative subgroup of order n + 1, and x 2 H. The polynomial L_xof degree at most n that vanishes on H nfxg and has f (x) = 1, has a very sparse representation of the form

$$ H\subset\mathbb{F} $$

$$ n+1 $$

$$ x,\in,H $$

$$ L_{x} $$

$$ n $$

$$ H\setminus{x} $$

$$ f(x)=1 $$

$$ L_{x}(X)={\frac{c_{x}(X^{n+1}-1)}{(X-x)}}, $$

for a constant c_x. This is benecial when constructing an eciently veriable [BG12]- style permutation argument in terms of polynomial identities.

$$ c_{x} $$

¹ We use the term SNARK in this paper for what is sometimes called a \SNARK with preprocessing"(see e.g. [GGPR13]) where one allows a one-time verier computation that is polynomial rather than polylogarithmic in the circuit size. In return, the SNARK is expected to work for all non-uniform circuits, rather than only statements about uniform computation.

$$ \mathrm {e . g}. $$

² From a theoretical point of view, polylogarithmic proof length is more natural; but logarithmic nicely captures recent constructions with a constant number of group elements, and sometimes is a good indication of the \practicality barrier".

³ In many denitions, only proof size is required to be polylogarithmic. For example, in the terminology of [GGPR13], additionally requiring polylogarithmic verier run time means the SNARK is unsubtle.

1.2 Eciency Analysis

We compare the performance of this work to the state of the art, both for non-universal SNARKs and universal SNARKs. At the time of publication, the only fully succinct universal SNARK construction is (the fully-succinct version of) the Sonic protocol [MBKM19]. This protocol requires the prover compute 273n G₁ group exponentiations, where n is the number of multiplication gates. In fully-succinct Sonic, every wire can only be used in three linear relationships, requiring the addition of ‘dummy’ multiplication gates to accommodate wires used in more than three addition gates. This increase in the multiplication gate count is factored into the prover computation estimate (see [MBKM19] for full details).

$$ \mathbb{G}_{1} $$

Our universal SNARK requires the prover to compute 6 polynomial commitments, combined with two opening proofs to evaluate the polynomial commitments at a random challenge point. There are two \avours"of PLONK to suit the tastes of the user. By increasing the proof size by two group elements, the total prover computations can be reduced by 10%. The combined degree of the polynomials is either 9(n + a) (larger proofs) or 11(n + a) (smaller proofs, reduced verier work), where n is the number of multiplication gates and a is the number of addition gates. Currently, the most ecient fully-succinct SNARK construction available is Groth’s 2016 construction [Gro16], which requires a unique, non-updateable CRS per circuit. Proof construction times are dominated by 3n + m G₁ and n G₂ group exponentiations. If we assume that one G₂ exponentiation is equivalent to three G₁ exponentiations, this yields 6n + m equivalent G₁ group exponentiations.

$$ 9(n+a) $$

$$ 11(n+a) $$

$$ 3n+m\ \mathbb{G}_{1} $$

$$ \mathbb{G}_{2} $$

$$ \mathbb{G}_{2} $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{1} $$

Performing a direct comparison between these SNARK arithmetisations requires some admittedly subjective assumptions. When evaluating common circuits, we found that the number of addition gates is 2x the number of multiplication gates, however circuits that are optimized under the assumption that addition gates are ‘free’ (as is common in R1CS based systems like [Gro16]) will give worse estimates.

$$ 'f r e e' $$

At one extreme, for a circuit containing no addition gates and only fan-in-2 multiplication gates, our universal SNARK proofs require 1*:* 1 times more prover work than [Gro16], and 30 fewer prover work than Sonic. If a = 2n, the ratios change to 2*:* 25 times more prover work than [Gro16], and 10 times less work than Sonic. If a = 5n, this changes to 3 times more work than [Gro16], and 5 times less work than Sonic. We should note that these comparisons are only comparing the required number of group exponentiations.

$$ \approx30 $$

$$ a=2n $$

$$ \approx2.25 $$

$$ \approx10 $$

$$ a=5n $$

We also note that the degree of PLONK’s structured reference string is equal to the number of gates in a circuit (if one uses the "fast" avour of PLONK). This is a signicant reduction in the SRS size compared to the state of the art.

When comparing proof construction, we also include the number of eld multiplications for PLONK, as the number of fast-fourier-transforms required to construct proofs is non-trivial. All other succinct universal SNARK constructions also have high FFT transform costs, however given the diculty of nding hard numbers, we cannot include them in the above table. Qualitative analysis suggests that the FFTs consume slightly

Table 1: Prover comparison. m = number of wires, n = number of multiplication gates, a = number of addition gates

$$ \mathbf{s i z e}\leq d $$

$$ 3n+m;\mathbb{G}_{1} $$

$$ 3n+m-\ell\ \mathbb{G}_{1}\ mathrm{\ e x p}, $$

$$ 2:\mathbb{G}{1},:1:\mathbb{G}{2} $$

$$ \overline{{\mathrm{}{\ 12d\mathbb{G}_1,12d\mathbb{G}_2}}} $$

$$ \underline{{n;{\mathbb{G}_{2};\mathrm{e x p}}}} $$

$$ \overline{{4,\mathbb{G}_{1},\ \\ \ {\mathbb{F}}}} $$

$$ \overline{{\mathrm{}{4d\mathbb{G}_{1},4d\mathbb{G}_{2}}}} $$

$$ \frac {n \mathbb {G} _ {2} \exp}{1 8 n \mathbb {G} _ {1} \exp} $$

$$ \underline{{36n\ {mathbb G}_{1}}} $$

$$ \overline{{8n,\mathbb{G}_{1},\mathrm{e x p}}} $$

$$ 273n\mathbb{G}_{1}\mathrm{e x p} $$

$$ \overline{{\ 20\ \mathbb{G}_{1},\ 16\ \mathbb{F}\ }} $$

$$ \overline{{\mathrm{}{2d\mathbb{G}_11,2d\mathbb{G}_2~}}} $$

$$ \overline{{\underline{{6\ \mathbb{G}_{1},\ 4\ \mathbb{F}}}}} $$

$$ \overline{{11n+11a;\mathbb{G}_{1};\mathrm{e x p}\ }} $$

$$ 3d,\mathbb{G}{1},1,\mathbb{G}{2} $$

$$ 3n+3a\ \mathbb{G}{1},:1\ \mathbb{G}{2} $$

$$ \approx54(n+a)\dot{\log}(dot{n+a});{\mathbb{F}};\mathrm{m u l} $$

$$ 7;\mathbb{G}_{1},;7;\mathbb{F} $$

$$ \overline{{9n+9a\ \mathbb{G}_{1}\ }} $$

$$ d;\mathbb{G}{1},;1;\mathbb{G}{2} $$

$$ n+a\ \mathbb{G}{1},:1\ \mathbb{G}{2} $$

$$ 9;\mathbb{G}_{1},;7;\mathbb{F} $$

$$ \approx54(n+a)\mathrm{l o g}(n+a);\mathbb{F};\mathrm{m u l} $$

less compute time than the G₁ group exponentiations. More details on the number of eld multiplications are given in section 1.3.

$$ \mathbb{G}_{1} $$

Verier computation per proof is shown in table 2. Only two bilinear pairing operations are required, due to the simple structure of the committed prover polynomials. In addition, the G₂ elements in each pairing are xed, enabling optimizations that reduce pairing computation time by 30% [CS10].

$$ \mathbb{G}_{2} $$

Table 2: Verier comparison per proof, P=pairing, ‘=num of pub inputs. For nonsuccinct protocols, additional helper work is specied

$$ {\overline{{3P,,\ell,mathbb G_{1},\exp}}} $$

$$ 3\ \mathbb{G}_{1},\ 2\ \mathbb{F} $$

$$ \ overline{5{P,},66}\ \mathbb{G}_{1}\ \mathrm{e x p} $$

$$ \overline{{8,\mathbb{G}_{1},,10,\mathbb{F}}} $$

$$ \overline{{12P}} $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{G}_{11} $$

1.3 Performance and Benchmarks

Figure 1: Benchmarks for test PLONK circuits using the BN254 curve. Does not include witness generation. Tests performed on a Surface pro 6 with 16GB RAM and a core i7-8650U CPU, utilizing all 8 logical/4 physical cores.

Figure 1 provides some estimates for the time required to construct and verify PLONK proofs. The benchmarks in question utilize the BN254 elliptic curve, using the Barretenberg ecc library.

https://github.com/AztecProtocol/barretenberg berg ecc library.

Even for circuits with over a million gates, PLONK proofs are capable of being constructed on consumer-grade hardware in under 23 seconds. This marks a signicant advancement in the eciency of universal SNARKs, which are now practical for a wide range of realworld use-cases.

Circuit preprocessing is a one-o computation, required for each program codied into a PLONK circuit. This step generates the polynomial commitments to the ‘selector’ polynomials required to verify proofs.

When constructing proofs, the time taken to perform the required fast fourier transforms is comparable to the time taken for elliptic curve scalar multiplications. The number of eld multiplications in table 1 is obtained from 8 FFTs of size 4n, 5 FFTs of size 2n and 12 FFTs of size n.

The number of FFT transforms can be signicantly reduced, if a circuit’s preprocessed polynomials are provided as evaluations over the 4n’th roots of unity (instead of in Lagrange-base form). However, given this dramatically increases the amount of information required to construct proofs, we omit this optimisation from our benchmarks.

$$ 4n^{\circ} $$

We conclude the introduction with a comparision to relevant concurrent work.

1.4 Comparison with the randomized sumcheck approach, and Fractal/Marlin:

Roughly speaking, all succinct proving systems work by using randomness to compress many constraint checks into one. The general way to obtain such compression, is by taking a random linear combination of the constraints. In the case of R1CS and similar systems, the more dicult constraints to be compressed are linear relations between the m system variables, i.e. constraints of the form < ai;x >= 0 where x 2 F are the system m 4 variables, and a_i2 F represents one of the constraints.

$$ <a_{i},x>=0 $$

$$ x\in\mathbb{R}^{m} $$

$$ a_{i}\in\mathbb{F}^{m} $$

These are analogous to the less general \wiring constraints" in a circuit satisability statement, which have the form x_i= x_j(e.g. when x_irepresents the output wire of a gate G, and x_jan input wire from G into another gate G⁰).

$$ x_{i}=x_{j} $$

$$ x_{i} $$

$$ x_{j} $$

$$ G^{\prime}!) $$

A random⁵ linear combination of linear constraints might have the form

$$ \sum_{i\in[n]}r^{i}<a_{i},x>=0 $$

for a unifrom r 2 F

$$ r\in\mathbb{F} $$

Skipping some details, [MBKM19] and the subsequent work of [Gab19] (relying on ⁺ [BCR 19]) reduce such a check to evaluating a degree n bivariate S at a random point; such that the number of non-zero monomials in S corresponds to the number of non- zero entries in the constraint vectors faⁱg. ^[MBKM19^] at this point devise a clever i2[n] strategy to amortize the cost of many evaluations of S across many proofs. This variant of [MBKM19] is much more prover ecient, but not fully succinct because of the need for the verier to compute at least one evaluation of S by themselves.

$$ \mathrm{[B C R^{+}19])} $$

$$ \left{a_{i}\right}_{i\in[n]} $$

⁴ We emphasize that the vector ai here does not precisely correspond to one of the r1cs matrix rows, P0i;j 0i but rather to a \attening" of it, i.e. it is a constraint of the form y = a x_j where a is one the r1cs matrix rows.

$$ \ {_{a i}} $$

$$ a_{i}^{\prime} $$

$$ y=\sum a_{i,j}^{\prime}x_{j} $$

$$ ^\mathrm{i{}t t,,i.e.} $$

⁵ It is a standard derandomization trick to use powers of a single random r 2 F rather than random independent ri.

$$ r\in\mathbb{F} $$

$$ r_{i} $$

Thus, the barrier to a fully succinct version of the more prover ecient version of Sonic (and for a fully succinct version of [Gab19]), is a method to eciently verify an evaluation S(z;y) in the case S only contains O(n) non-zero monomials.

$$ S(z,y) $$

$$ O(n) $$

A signicant technical contribution of the recent concurrent Fractal and Marlin sys- + tems [CHM 19, COS19] is a solution to this problem \in Lagrange Basis".

Specically, suppose that H;K are multiplicative subgroups of size O(n) of F such + that S has only M non-zero values on H K; then [CHM 19, COS19] devise a protocol to convince a succinct verier that S(z;y) = t where the prover’s work is linear in M. This is a good point to note that the solution to this problem by the natural generalization of [KZG10] to a bi-variate polynomial commitment scheme would have led to O(n²) proving time.

$$ O(n) $$

$$ H!K $$

$$ [\mathrm{C H M^{+}19} $$

$$ S(z,y)=t $$

$$ O(n^{2}) $$

Coming back to PLONK, the reason we don’t require this \bi-variate evaluation breakthrough" is that we focus on constant fan-in circuits rather than R1CS/unlimited addition fan-in; and thus our linear constraints are just wiring constraints that can be reduced to a permutation check (as explained in Sections 5.2, 6). One way to interpret the [BG12] technique is that \linear constraints that correspond to a permutation can be more simply combined than general linear constraints". For example, in the above equation each constraint is multiplied by a distinct random coecient, whereas in the [BG12] randomization, it suces in a sense to add the same random shift to each variable value. (See the permutation protocol in Section 5 for details.)

Concrete comparison to Marlin While Fractal leverages the sparse bi-variate evaluation technique in the context of transparent recursive SNARKs, Marlin focuses on constructing a fully succinct (universal) SNARK as in this paper.

• It is not completely straightforward to compare this work and [CHM 19], as we are in the realm of concrete constants, and the basic measure both works use is dierent. While we take our main parameter n to be the number of addition and multiplication
• gates in a fan-in two circuit; [CHM 19] use as their main parameter the maximal number of non-zeroes in one of the three matrices describing an R1CS. For the same value of n PLONK outperforms Marlin, e.g. by roughly a 2x factor in prover group operations and proof size. In the extreme case of a circuit with only multiplication gates, this would indeed represent the performance dierence between the two systems.

$$ [\mathrm{C H M^{+}19}] $$

$$ [\mathrm{C H M^{+}19}] $$

However, in constraint systems with \frequent large addition fan-in" Marlin may outperform the currently specied variant⁶ of PLONK. For example, this happens in the extreme case of one \fully dense" R1CS constraint 0 1 0 1

$$ \left(\sum_{j\in[m]}a_{j}x_{j}\right)\cdot\left(\sum_{j\in[m]}b_{j}x_{j}\right)=\sum_{j\in[m]}c_{j}x_{j}. $$

m where a;b;c 2 F have all non-zero entries.

$$ a,b,c\in\mathbb{F}^{m} $$

⁶ It seems that the natural variants of PLONK where the addition fan-in is increased to three or four according to the instance could outperform the current numbers given in Marlin for any R1CS.

Morever, it seems ideas implicit in Fractal, or alternatively a \plug-in" of the mentioned sparse bi-variate evaluation protocol into [Gab19] will lead to improved performance via this route; especially in cases where some of the prover work can be delegated to an outside helper (in PLONK there is less opportunity for such delegation, as the wiring + is checked on the witness itself, whereas in [Gab19, CHM 19, COS19] it is in a sense checked on the random coecients of the verier).

$$ \mathrm{C H M^{+}19} $$

2 Preliminaries

2.1 Terminology and Conventions

We assume our eld F is of prime order. We denote by F<d[X] the set of univariate polynomials over F of degree smaller than d. We assume all algorithms described receive as an implicit parameter the security parameter.

$$ \mathbb{F}_{<d}[X] $$

$$ \mathbb{F} $$

Whenever we use the term \ecient", we mean an algorithm running in time poly(). Furthermore, we assume an \object generator" O that is run with input before all protocols, and returns all elds and groups used. Specically, in our protocol O() = (F*;G₁;G₂;* G_t;e;g₁;g₂;g_t) where

$$ \lambda $$

$$ \lambda $$

$$ (\mathbb{F},\mathbb{G}{1},\mathbb{G}{2},\mathbb{G}{t},e,g{1},g_{2},g_{t}) $$

$$ \mathcal{O}(\lambda)= $$

!(1) F is a prime eld of super-polynomial size r =.

$$ \mathbb{F} $$

$$ r=\lambda^{\omega(1)} $$

G₁*;G₂;* G_tare all groups of size r, and e is an eciently computable non-degenerate pairing e : G₁ G₂*!* G_t.

$$ \mathbb{G}{1},\mathbb{G}{2},\mathbb{G}_{t} $$

$$ e:\mathbb{G}{1}\times\mathbb{G}{2}\to\mathbb{G}_{t} $$

g₁;g₂ are uniformly chosen generators such that e(g₁;g₂) = g_t.

$$ g_{1},g_{2} $$

$$ e(g_{1},g_{2})=g_{t} $$

We usually let the parameter be implicit, i.e. write F instead of F(). We write G₁ and G₂ additively. We use the notations [x] := x g₁ and [x] := x g₂. 1 2

$$ \mathbb{F}(\lambda) $$

$$ \mathbb{G}_{1} $$

$$ \mathbb{F} $$

$$ \mathbb{G}_{2} $$

$$ \ [x]{1}:=x\cdot g{1} $$

$$ \left[x boldsymbolright\right]{2}:=x\cdot g{2}. $$

We often denote by [n] the integers f1*;:::;ng*. We use the acronym e.w.p for \except with probability"; i.e. e.w.p means with probability at least 1.

$$ {1,\ldots,n} $$

universal SRS-based public-coin protocols We describe public-coin (meaning the verier messages are uniformly chosen) interactive protocols between a prover and verier; when deriving results for non-interactive protocols, we implicitly assume we can get a proof length equal to the total communication of the prover, using the Fiat-Shamir transform/a random oracle. Using this reduction between interactive and non-interactive protocols, we can refer to the \proof length" of an interactive protocol.

We allow our protocols to have access to a structured reference string (SRS) that can be derived in deterministic poly()-time from an \SRS of monomials" of the form i ⁱ x, x, for unⁱform x 2 F, and some integers a;b;c;d with absolute 1 a i b 2 c i d value bounded by poly(). It then follows from Bowe et al. [BGM17] that the required SRS can be derived in a universal and updatable setup requiring only one honest participant; in the sense that an adversary controlling all but one of the participants in the setup does not gain more than a negl() advantage in its probability of producing a proof of any statement.

$$ \big{\big[x^{i}\big]{1}\big}{a\leqslant i\leqslant b},,\big{\big[x^{i}\big]{2}\big}{c\leqslant i\leqslant d}, $$

$$ x\in\mathbb{F} $$

$$ a,b,c,d $$

For notational simplicity, we sometimes use the SRS srs as an implicit parameter in protocols, and do not explicitly write it.

2.2 Analysis in the AGM model

For security analysis we will use the Algebraic Group Model of Fuchsbauer, Kiltz and Loss[FKL18]. In our protocols, by an algebraic adversary A in an SRS-based protocol we mean a poly()-time algorithm which satises the following.

For i 2f1*;* 2g, whenever A outputs an element A 2 G_i, it also outputs a vector v over F such that A =< v; srsi>.

$$ \mathcal{A} $$

$$ i\in{1,2} $$

$$ A\in\mathbb{G}_{i}, $$

$$ A=<v,\mathsf{s r s_{i}}> $$

Idealized verier checks for algebraic adversaries We introduce some terminology to capture the advantage of analysis in the AGM.

First we say our srs has degree Q if all elements of srsⁱare of the form [f (x)] for f 2 i F<Q[X] and uniform x 2 F. In the following discussion let us assume we are executing a protocol with a degree Q SRS, and denote by f_i;jthe corresponding polynomial for the j’th element of srs_i.

$$ \mathrm{s r s}_{\mathrm{i}} $$

$$ [f(x)]_{i} $$

$$ \mathbb{F}_{<Q}[X] $$

$$ x\in\mathbb{F} $$

$$ f\in $$

$$ f_{i,j} $$

$$ j^{\ } $$

$$ \mathrm{s r S i} $$

Denote by a;b the vectors of F-elements whose encodings in G₁*;*G₂ an algebraic adversary A outputs during a protocol execution; e.g., the j’th G₁ element output by A is [a^j]. ¹

$$ a,b $$

$$ \mathbb{G}{1},\mathbb{G}{2} $$

$$ \mathrm{e{..}g. $$

$$ \mathbb{G}_{1} $$

$$ [a_{j}]_{1} $$

By a \real pairing check" we mean a check of the form

$$ (a\cdot T_{1})\cdot(T_{2}\cdot b)=0 $$

for some matrices T₁;T₂ over F. Note that such a check can indeed be done eciently given the encoded elements and the pairing function e : G₁ G₂*!* G_t.

$$ T_{1},T_{2} $$

$$ \mathbb{F} $$

$$ e:\mathbb{G}{1}\times\mathbb{G}{2}\to\mathbb{G}_{t} $$

Given such a \real pairing check", and the adversary A and protocol execution during which the elements were output, dene the corresponding \ideal check" as follows. Since A is algebraic when he outputs [aj] he also outputs a vector v such that, from linearity, PiP a_j= v_‘fⁱ;‘(x) = R_i;j(x) for R_i;j(X) := v_‘f_i;‘(X). Denote, for i 2f1*;* 2g the vector of polynomials R_i= (R_i;j)_j. The corresponding ideal check, checks as a polynomial identity whether (R₁ T₁) (T₂ R₂) 0

$$ \left[ a _ {j} \right] _ {i} $$

$$ v $$

$$ a_{j}=\sum v_{\ell}f_{i,\ell}(x)=R_{i,j}(x) $$

$$ R_{i,j}(X):=\sum v_{\ell}f_{i,\ell}(X) $$

$$ i\in{1,2} $$

$$ R_{i},=,(R_{i,j})_{j} $$

$$ (R_{1}\cdot T_{1})\cdot(T_{2}\cdot R_{2})\equiv0 $$

The following lemma is inspired by [FKL18]’s analysis of [Gro16], and tells us that for soundness analysis against algebraic adversaries it suces to look at ideal checks. Before stating the lemma we dene the Q-DLOG assumption similarly to [FKL18].

Denition 2.1. Fix integer Q. The Q-DLOG assumption for (G₁*;*G₂) states that given

$$ (\mathbb{G}{1},\mathbb{G}{2}) $$

$$ Q $$

$$ \left[1\right]{1},\left[x\right]{1},\ldots,\left[x^{Q}\right]{1},\left[1\right]{2},\left[x\right]{2},\ldots,\left[x^{Q}\right]{2} $$

for uniformly chosen x 2 F*, the probability of an ecient A outputting x is* negl().

$$ x\in\mathbb{F} $$

Lemma 2.2. Assume the Q-DLOG for (G₁*;G₂). Given an algebraic adversary A partic-* ipating in a protocol with a degree Q SRS, the probability of any real pairing check passing is larger by at most an additive negl() factor than the probability the corresponding ideal check holds.

$$ (\mathbb{G}{1},\mathbb{G}{2}) $$

Proof. Let be the dierence between the satisability of the real and ideal check. We describe an adversary A for the Q-DLOG problem that succeeds with probability; this implies = negl(). A receives the challenge

$$ \gamma $$

$$ \mathcal{A}^{*} $$

$$ \gamma={\mathsf{n e g l}}(\lambda) $$

$$ \left[1\right]{1},\left[x\right]{1},\ldots,\left[x^{Q}\right]{1},\left[1\right]{2},\left[x\right]{2},\ldots,\left[x^{Q}\right]{2} $$

and constructs using group operations the correct SRS for the protocol. Now A runs the protocol with A, simulating the verier role. Note that as A receives from A the vectors of coecients v, he can compute the polynomials fR_i;jg and check if we are in the case that the real check passed but ideal check failed. In case we are in this event, A computes R := (R₁ T₁)(T₂ R₂):

$$ \mathcal{A}^{*} $$

$$ {\mathcal A}, $$

$$ \mathcal{A}^{*} $$

$$ {R_{i,j}} $$

$$ R:=(R_{1}\cdot T_{1})(T_{2}\cdot R_{2}). $$

$$ \mathcal{A}^{*} $$

We have that R 2 F<2Q[X] is a non-zero polynomial for which R(x) = 0. Thus A can factor R and nd x.

$$ R\in\mathbb{F}_{<2Q}|X| $$

$$ R(x)=0 $$

$$ \mathcal{A}^{*} $$

Knowlege soundness in the Algebraic Group Model We say a protocol P between a prover P and verier V for a relation R has Knowledge Soundness in the Algebraic Group Model if there exists an ecient E such that the probability of any algebraic adversary A winning the following game is negl().

$$ \mathcal{P} $$

1. A chooses input x and plays the role of P in P with input x.

$$ \mathbf{P} $$

$$ \ .. $$

$$ \mathcal{P} $$

2. E given access to all of A’s messages during the protocol (including the coecients of the linear combinations) outputs*!*.

$$ \ {{\cal A}}^{\circ}! $$

3. A wins if

(a) V outputs acc at the end of the protocol, and

(b)(x*;!*) 2R =.

$$ (\mathsf x,)\notin\mathcal{.}R. $$

3 A batched version of the [KZG10] scheme

Crucial to the eciency of our protocol is a batched version of the [KZG10] polynomial commitment scheme similar to Appendix C of [MBKM19], allowing to query multiple committed polynomials at multiple points. We begin by dening polynomial commitment schemes in a manner conducive to our protocol. Specically, we dene the open procedure in a batched setting having multiple polynomials and evaluation points.

Denition 3.1. A d-polynomial commitment scheme consists of gen(d)- a randomized algorithm that outputs an SRS srs*.*

$$ {\mathsf{g e n}}(d)-a $$

com(f; srs)- that given a polynomial f 2 F<d[X] returns a commitment cm to f.

$$ \mathsf{c o m}(f,\mathsf{s r s}) $$

$$ f\in\mathbb{F}_{<d}[X] $$

$$ f, $$

A public coin protocol open between parties P_PCand V_PC. P_PCis given f₁;:::;f_t2 F<d[X]. PPCand VPCare both given integer t = poly(), cm₁;:::; cmt- the alleged commitments to f₁;:::;f_t, z₁;:::;z_t2 F and s₁;:::;s_t2 F*- the alleged correct* openings f₁(z₁);:::;f_t(z_t). At the end of the protocol V_PCoutputs acc or rej*.*

$$ f_{1},\ldots,f_{t}\in $$

$$ \mathbb{F}_{<d}[X] $$

$$ \mathbf{V}_{\mathsf{P C}} $$

$$ t=\ \ {tt p p l y y}(\lambda),\ {\tt c m}{1},\ldots,\ {\tt c m}{t}\cdot\cdot h e $$

$$ f_{1},\ldots,f_{t},,z_{1},\ldots,z_{t}\in\mathbb{F} $$

$$ s_{1},\ldots,s_{t}\in\mathbb{F} $$

$$ f_{1}(z_{1}),\ldots,f_{t}(z_{t}) $$

such that

Completeness: Fix integer t, z₁;:::;zt2 F, f₁;:::;ft2 F<d[X]. Suppose that for each i 2 [t], cm_i= com(f_i;srs). Then if open is run correctly with values t; fcm_i;z_i;s_i= f_i(z)g, V_PCoutputs acc with probability one. i2[t]

$$ {\it t},\ z_{1},\ldots z{\it t}\ \in\ {\mathbb F},\ f_{1},\ldots,\ f_{t}\ \in\ {\mathbb F}_{<d}[X] $$

$$ i \in [ t ], \mathrm {c m} _ {i} = \operatorname {c o m} \left(f _ {i}, \mathrm {s r s}\right) $$

$$ t,\big{\mathfrak{c m}{i},z{i},s_{i}=f_{i}(z)\big}{i\in[t]},\operatorname{V}{\mathsf{P C}} $$

Knowledge soundness in the algebraic group model: There exists an e- cient E such that for any algebraic adversary A the probability of A winning the following game is negl() over the randomness of A and gen*.*

$$ e\mathcal{H}- $$

1.Given srs*, A outputs t;* cm₁*;:::;* cm_t.

$$ t,\mathsf{c m}{1},\ldots,\mathsf{c m}{t} $$

2. E, given access to the messages of A during the previous step, outputs f₁;:::;f_t2 F<d[X].

$$ f_{1},\ldots,f_{t}\in $$

$$ \mathbb{F}_{<d}[X] $$

3. A outputs z₁;:::;z_t2 F*, s₁;:::;s*_t2 F*.*

$$ z_{1},\ldots,z_{t}\in\mathbb{F},,s_{1},\ldots,s_{t}\in\mathbb{F} $$

4. A takes the part of P_PCin the protocol open with inputs cm₁*;:::;* cm_t;z₁;:::;z_t;s₁;:::;s_t.

$$ \mathsf{c m}{1},\ldots,\mathsf{c m}{t},z_{1},\ldots,z_{t},s_{1},\ldots,s_{t} $$

5. A wins if

{ V_PCoutputs acc at the end of the protocol.

{ For some i 2 [t], s_i6= f_i(z_i).

$$ i\in[t],,s_{i}\neq f_{i}(z_{i}) $$

We describe the following scheme based on [KZG10, MBKM19].

$$ \mathrm{[K Z G10,M B K M19]} $$

d 1

1. gen(d) - choose uniform x 2 F. Output srs = ([₁]; [x];:::; x;[¹]; [x]). 1 1 1 2 2

$$ x\in\mathbb{F} $$

$$ {\mathsf{s r s}}=(\left[1\right]{1},\left[x\right]{1},\ldots,\left[x^{d-1}\right]{1},\left[1\right]{2},\left[x\right]_{2}). $$

$$ {\mathsf{c o m}}(f,{\mathsf{s r s}}):=\left[f(x)\right]_{1}. $$

3.We rst describe the open protocol in the case z₁ = ::: = z_t= z. open(fcm_ig; fz_ig; fs_ig):

$$ z_{1}=\ldots=z_{t}=z $$

$$ \left(\left{c m_{i}\right},\left{z_{i}\right},\left{s_{i}\right}\right) $$

(a)V_PCsends random 2 F.

$$ \gamma\in\mathbb{F} $$

(b)P_PCcomputes the polynomial

$$ h(X):=\sum_{i=1}^{t}\gamma^{i}\cdot\frac{f_{i}(X)-f_{i}(z)}{X-z} $$

and using srs computes and sends W := [h(x)]. ₁

$$ W:=\left[h(x)\right]_{1} $$

(c)V_PCcomputes the elements

$$ F:=\sum_{i\in[t]}\gamma^{i}\cdot\mathsf{c m}{i},v:=\left[\sum{i\in[t]}\gamma^{i}\cdot s_{i}\right]_{1} $$

(d)V_PCoutputs acc if and only if

$$ \mathrm{V}_{\mathsf{P C}} $$

$$ e\bigl(F-v,[1]{2}\bigr)\cdot e\bigl(-W,[x-z]{2}\bigr)=1. $$

We argue knowledge soundness for the above protocol. More precisely, we argue the existence of an ecient E such that an algebraic adversary A can only win the KS game w.p. negl() when restricting itself to choosing z = z₁ = ::: = z_t.

$$ z=z_{1}=\ldots=z_{t} $$

Let A be such an algebraic adversary.

P _d ¹ _j A begins by outputting cm₁*;:::;* cm_t. Each cmⁱis a linear combination a_i;jx. ^j=0 ₁ E, who is given the coecients fa_i;jg, simply outputs the polynomials

$$ \mathsf{c m}{1},\ldots,\mathsf{c m}{t} $$

$$ \ {sf c m}_{i} $$

$$ \sum_{j=0}^{d-1}a_{i,j}\left[x^{j}\right]_{1} $$

$$ {a_{i,j}} $$

$$ f_{i}(X):=\sum_{j=0}^{d-1}a_{i,j}\cdot X^{j}. $$

A now outputs z;s₁;:::;s_t2 F. Assume that for some i 2 [t], f_i(z) 6= s_i. We show that for any strategy of A from this point, V_polyoutputs acc w.p negl().

$$ z,s_{1},\ldots,s_{t}\in\mathbb{F} $$

$$ i\in[t],,f_{i}(z)\neq s_{i} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

In the rst step of open, V_polychooses a random 2 F. Dene X X

$$ \mathrm{V}_{\mathrm{p o l y}} $$

$$ \gamma\in\mathbb{F} $$

$$ f(X):=\sum_{i\in[t]}\gamma^{i}\cdot f_{i}(X),s:=\sum_{i\in[t]}\gamma^{i}\cdot s_{i}. $$

We have that e.w.p. t=jFj, f (z) 6= s. Now A outputs W = H(x) for some H 2 F<d[X]. According to Lemma 2.2, it suces to upper bound the probability that the ideal check corresponding to the real pairing check in the protocol passes. It has the form f (X) s H(X)(X z):

$$ t/|\mathbb{F}|,;{f}z({\it)neq;!s}. $$

$$ W;=;H(x) $$

$$ H\in\mathbb{F}_{<d}[X] $$

$$ f(X)-s\equiv H(X)(X-z). $$

The check passing implies that f (X) s is divisible by (X z), which implies f (z) = s. Thus the ideal check can only pass w.p. negl() over the randomness of V_poly, which implies the same thing for the real check according to Lemma 2.2.

$$ f(X)-s $$

$$ (X-z) $$

$$ f(z)=s. $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

The open protocol for multiple evaluation points simply consists of running in parallel the open protocol for each evaluation point and the polynomials evaluated at that point. And then applying a generic method for batch randomized evaluation of pairing equations. For notational simplicity we describe the open protocol explicitly only in the case of two distinct evaluation points among z₁;:::;z_t(this also happens to be our case in the main protocol). For this, let us denote the distinct evaluation points by z;z⁰ and by t₁;t₂ the number of polynomials and by ff_ig; ff g _the polynomials to be evaluated at z;z⁰ respectively. i2[t1] i0 i2[t2] open(fcm g; fcm⁰g; fz;z⁰g; fs;s⁰g):

$$ z{}{1},\ldots,z{}{t} $$

$$ z,z^{\prime} $$

$$ t_{1},t_{2} $$

$$ \left{f_{i}\right}{i\in[t{1}]},\left{f_{i}^{\prime}\right}{i\in[t{2}]} $$

$$ z,z^{\prime} $$

$$ \mathsf{o p e n}(\left{c m_{i}\right}{i\in\left[t{1}\right]},\left{c m_{i}^{\prime}\right}{i\in\left[t{2}\right]},\left{z,z^{\prime}\right},\left{s_{i},s_{i}^{\prime}\right})! $$

0 (a)V_PCsends random*; 2* F.

$$ \gamma\gamma^{\prime},\in\mathbb{F} $$

$$ \mathrm{V p C} $$

(b)P_PCcomputes the polynomials

$$ \mathrm{P}\mathsf{P C} $$

$$ h (X) := \sum_ {i = 1} ^ {t _ {1}} \gamma^ {i - 1} \cdot \frac {f _ {i} (X) - f _ {i} (z)}{X - z} $$

$$ h^{\prime}(X):=\sum_{i=1}^{t_{2}}\gamma^{\prime i-1}\cdot\frac{f_{i}^{\prime}(X)-f_{i}^{\prime}(z^{\prime})}{X-z^{\prime}} $$

and using srs computes and sends W := [h(x)];W⁰ := [h⁰(x)]. ₁ 1

$$ W:=\left[h(x)\right]{1},W^{\prime}:=\left[h^{\prime}(x)\right]{1} $$

(c)V_PCchooses random r;r⁰ 2 F.

$$ r,r^{\prime}\in\mathbb{H}. $$

(d)V_polycomputes the element 0 2

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ F:=r{\cdot}\left(\sum_{i\in[t_{1}]}\gamma^{i-1}\cdot\mathsf{c m}{i}-\left[\sum{i\in[t_{1}]}\gamma^{i-1}\cdot s_{i}\right]{1}\right){r^{\prime}\ }\left(\sum{i\in[t_{2}]}\gamma^{i-1}\cdot\mathsf{c m}{i}^{\prime}-\left[\sum{i\in[t_{2}]}\gamma^{i-1}\cdot s_{i}^{\prime}\right]_{1}\right) $$

V_PCcomputes outputs acc if and only if

$$ e\left(F+r z\cdot W+r^{\prime}z^{\prime}\cdot W^{\prime},[1]{2}\right)\cdot e(-r\cdot W-r^{\prime}\cdot W^{\prime},[x]{2})=1. $$

We summarize the eciency properties of this batched version of the [KZG10] scheme.

Lemma 3.2. Fix positive integer d. There is a d-polynomial commitment scheme S such that

(a)For n d and f 2 F<n[X], computing com(f) requires n G₁-exponentiations.

$$ n\leq d $$

$$ \mathbb{G}_{1} $$

$$ f\in\mathbb{F}_{<n}[X] $$

t (b)Given z := (z₁;:::;zt) 2 F;f₁;:::;ft2 F<d[X], denote by t the number of distinct values in z*; and for i 2* [t], dⁱ:= maxfdeg(fⁱ)g where Sⁱ i2Si is the set of indices j such that z_jequals the i’th distinct point in z*. Let* cm_i= com(f_i). Then open (fcm_i;f_i;z_i;s_ig) requires P

$$ \mathbf{z};:=;(z_{1},\ .\ .\ .\ z_{t});\in;\mathbb{F}^{t},;f_{1},\ .\ .\ ,f_{t};\in;\mathbb{F}_{<d}[X] $$

$$ t^{*} $$

$$ i,\in,[t^{*}],\ d,,= $$

$$ {\deg(f_{i})}{i\in S{i}} $$

$$ S_{i} $$

$$ z_{j} $$

$$ {\mathsf{c m}}{i}={\mathsf{c o m}}(f{i}) $$

$$ ({c m_{i},f_{i},z_{i},s_{i}}) $$

i. d_iG₁*-exponentiations of* P_poly. _i2[t_]

$$ \textstyle\sum_{i\in[t^{*}]}d_{i}\ \mathbb{G}_{1} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

ii. t + t G₁*-exponentiations and 2 pairings of* V_poly.

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ t+t^{*},\mathbb{G}_{1} $$

4 Idealised low-degree protocols

We dene a limited type of protocol between a prover and a verier to cleanly capture and abstract the use of a polynomial commitment scheme such as [KZG10]. In this protocol, the prover sends low-degree polynomials to a third trusted party I. The verier may then ask I whether certain identites hold between the prover’s polynomials, and additional predened polynomials known to the verier.

Denition 4.1. Fix a positive integers d;D;t;‘. A (d;D;t;‘)-polynomial protocol is a multiround protocol between a prover P_poly, verier V_polyand trusted party I that proceeds as follows.

$$ l,D,t,\ell) $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

1.The protocol denition includes a set of preprocessed polynomials g₁;:::;g_‘2 F<d[X].

$$ \mathbb{F}_{<d}[X] $$

$$ g_{1},\ldots,g_{\ell}\ in $$

2.The messages of Ppolyare sent to I and are of the form f for f 2 F<d[X]. If Ppoly sends a message not of this form, the protocol is aborted.

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ f\in\mathbb{F}_{<d}[X] $$

3.The messages of V_polyto P_polyare arbitrary (but we will concentrate on public coin protocols where the messages are simply random coins).

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

4.At the end of the protocol, suppose f₁;:::;f_tare the polynomials that were sent from P_polyto I. V_polymay ask I if certain polynomial identities holds between ff₁;:::;f_t;g₁;:::;g_‘g. Where each identity is of the form

$$ f_{1},\ldots,f_{t} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

$$ {f_{1},\ldots,f_{t},g_{1},\ldots,g_{\ell}} $$

$$ F(X):=G(X,h_{1}(v_{1}(X)),\ldots,h_{M}(v_{M}(X)))\equiv0, $$

for some hi2ff₁;:::;ft;g₁;:::;g‘g, G 2 F[X;X₁;:::;XM], v₁;:::;vM2 F<d[X] such that F 2 F<D[X] for every choice of f₁;:::;ftmade by Ppolywhen following the protocol correctly.

$$ h_{i}\in{f_{1},\ldots,f_{t},g_{1},\ldots,g_{\ell}},;G\in\mathbb{F}[X,X_{1},\ldots,X_{M}],;v_{1},\ldots,v_{M}\in\mathbb{F}_{<d}[X] $$

$$ F\in\mathbb{F}_{<D}[X] $$

$$ f_{1},\ldots,f_{t} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

5.After receiving the answers from I regarding the identities, V_polyoutputs acc if all identities hold, and outputs rej otherwise.

$$ \mathrm{V}_{\mathrm{p o l y}} $$

Remark 4.2. A more expressive model would be to have P_polysend messages (f;n) for n d to I instead of just f; and have I enforce f 2 F<n[X]. We avoid doing this as this extra power is not needed for our protocol, and results in reduced eciency as it translates to needing to use a polynomial commitment scheme with the ability to dynamically enforce a smaller than d degree bound (as the [MBKM19]-variant of [KZG10] is able to do).

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ n\leq d $$

$$ (f,n) $$

$$ f,\in,\mathbb{F}_{<n}[X] $$

We dene polynomial protocols for relations in the natural way.

Denition 4.3. Given a relation R, a polynomial protocol for R is a polynomial pro- tocol with the following additional properties.

1.At the beginning of the protocol, P_polyand V_polyare both additionally given an input x*. The description of* P_polyassumes possession of ! such that (x*;!*) 2R.

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ (\mathsf X\omega)\in\mathcal{R} $$

2. Completeness: If P_polyfollows the protocol correctly using a witness ! for x*,* V_polyaccepts with probability one.

$$ \mathrm{P}_{\mathrm{p o l y}} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

3. Knowledge Soundness: There exists an ecient E, that given access to the messages of P_polyto I outputs ! such that, for any strategy of P_poly, the probability of the following event is negl().

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ \mathrm{P_{p o l y}} $$

(a) V_polyoutputs acc at the end of the protocol, and

$$ \mathrm{V}_{\mathsf{p o l y}} $$

(b) (x*;!*) 2R =.

$$ (\mathsf x,)\notin\mathcal{R}. $$

Remark 4.4. We intentionally do not dene a zero-knowlege property for idealized protocols, as acheiving ZK will depend on how much information on the polynomials sent to I is leaked in the nal \compiled" protocol. This in turn depends on specic details of the polynomial commitment scheme used for compilation.

4.1 Polynomial protocols on ranges

In our protocol V_polyactually needs to check if certain polynomial equations hold on a certain range of input values, rather than as a polynomial identity. Motivated by this, for a subset S F, we dene an S-ranged (d;D;t;‘)-polynomial protocol identically to a (d;D;t;‘)-polynomial protocol, except that the verier asks if his identities hold on all points of S, rather than identically. We then dene ranged polynomial protocols for relations in the exact same way as in Denition 4.3.

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ S\subset\mathbb{F} $$

$$ (d,D,t,\ell) $$

We show that converting a ranged protocol to a polynomial protocol only incurs one additional prover polynomial.

Lemma 4.5. Let P be an S-ranged (d;D;t;‘)-polynomial protocol for R. Then we can construct a (maxfd; jSj;D jSjg;D;t + 1*;‘* + 1)-polynomial protocol P for R.

$$ \mathcal{P} $$

$$ (d,D,t,\ell) $$

$$ \mathcal{R} $$

$$ {d,|S|,D-|S|},D,t+1,\ell+1 $$

$$ \mathcal{P}^{*} $$

For the lemma, we use the following simple claim.

Claim 4.6. Fix F₁;:::;Fk2 F<n[X]. Fix Z 2 F<n[X]. Suppose that for some i 2 [k], Z-F_i. Then

$$ F_{1},\ldots,F_{k}\in\mathbb{F}_{<n}[X] $$

$$ i\in[k] $$

$$ Z\in\mathbb{F}_{<n}[X] $$

$$ Z\nmid F_{i} $$

1.e.w.p 1*=jFj over uniform a₁;:::;a*_k2 F*, Z doesn’t divide*

$$ 1/|\mathbb{F}| $$

$$ a_{1},\ldots,a_{k}\in\mathbb{F},,\mathcal{Z} $$

$$ F:=\sum_{j=1}^{k}a_{j}\cdot F_{j}. $$

2.Assuming Z decomposes to distinct linear factors over F*, e.w.p k=jFj over uniform* a 2 F*, Z doesn’t divide* k X

$$ \mathbb{F},;e.w.p;k/|\mathbb{F}| $$

$$ a\in\mathbb{F},,Z $$

$$ G:=\sum_{j=1}^{k}a^{j}\cdot F_{j}. $$

Proof. ZjF is equivalent to F mod Z = 0. Denoting R := F_imod Z, we have that R 6= 0; i.e. R isn’t the zero polynomial. And we have

$$ Z|F $$

$$ R:=F_{i} $$

$$ Z=0 $$

$$ R\neq0; $$

$$ Z, $$

$$ F=\sum_{j=1,j\neq i}^{k}a_{j}\cdot F_{j}+a_{i}\cdot R\pmod{Z} $$

Thus, for any xing of fa^jg there ⁱs at most one value a_i2 F such that F mod Z = 0. j6=i The rst item of the claim follows.

$$ {\boldsymbol{{}a}{j}}{j\neq i} $$

$$ a_{i}\in\mathbb{F} $$

$$ Z=0 $$

To prove the second, write similarly

$$ G=\sum_{j=1,j\neq i}^{k}a^{j}\cdot F_{j}+a^{i}\cdot R\pmod Z{Z} $$

Let x 2 F be such that Z(x) = 0 but R(x) 6= 0. Then G mod Z = 0 implies G(x) = 0, which means a is a root of the non-zero polynomial

$$ Z(x)=0 $$

$$ x\in\mathbb{F} $$

$$ R(x)\neq0 $$

$$ Z=0 $$

$$ G(x)=0 $$

$$ g(Y):=\sum_{j=1,j\neq i}^{k}Y^{j}\cdot F_{j}(x)+Y^{i}\cdot R(x), $$

which is the case for at most k values of a.

$$ \ . $$

Proof. (Of Lemma 4.5) Let P be the S-ranged (d;D;t;‘)-polynomial protocol. We construct the protocol P. The set of preprocessed polynomials in P are the same as Q in P with the addition of Z_S(X) := (X a). P proceeds exactly as P until the a2S point where V_polyasks about identites on S. Suppose that the k identities the verier asks about are F₁(X);:::;F_k(X) (where each F_iis of total degree at most D and of the form described in Denition 4.1). P now proceeds as follows:

$$ \mathcal{P} $$

$$ (d,D,t,\ell). $$

$$ \mathcal{P}^{*} $$

$$ \mathcal{P}^{*} $$

$$ \mathcal{P} $$

$$ Ztextstyle{\mathcal{S}}(X):=\prod_{n\in{\mathcal{S}}}(X-a).\ {\mathcal{P}}^{*} $$

$$ \mathcal{P} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ F_{1}(X),\ldots,F_{k}(X) $$

$$ F_{i} $$

$$ \mathcal{P}^{*} $$

V_polysends uniform a₁;:::;a_k2 F to P_poly.

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ a_{1},\ldots,a_{k}\in\mathbb{F} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

P i2[k]aiFi P_polycomputes the polynom^ial T :=. _ZS

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ T:=\frac{\sum_{i\in[k]}a_{i}\cdot F_{i}}{Z_{S}} $$

P_polysends T to I.

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

V_polyqueries the identity

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ \sum_{i\in[k]}a_{i}\cdot F_{i}(X)\equiv T\cdot Z_{S} $$

It follows from Claim 4.6 that e.w.p. 1*=jFj* over V_poly’s choice of a₁;:::;a_k, the existence of an appropriate T 2 F[X] is equivalent to F₁;:::;F_‘vanishing on S. This in turn is equivalent to V_polyoutputting acc in the analogous execution of P.

$$ \mathrm{e.w.p.}\quad1/|\mathbb{F}| $$

$$ \mathrm{V}_{\mathsf{p o l y}}{}^{\prime}\mathrm{S} $$

$$ a_{1},\ldots,a_{k} $$

$$ T\in\mathbb{F}[X] $$

$$ F_{1},\ldots,F_{\ell} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ \mathcal{P} $$

4.2 From polynomial protocols to protocols against algebraic adversaries

We wish to use the polynomial commitment scheme of Section 3 to compile a polynomial protocol into one with knowledge soundness in the algebraic group model (in the sense dened in Section 2.2).

For the purpose of capturing the eciency of the transformation, we rst dene somewhat technical measures of the (d;D;t;‘)-polynomial protocol P.

$$ \mathcal{P} $$

$$ (d,D,t,\ell) $$

$$ i\in[t] $$

For i 2 [t], let d_ibe the maximal degree of f_isent by an honest prover in P. Assume only one identity G(X;h₁(v₁(X));:::;h_M(v_M(X))) 0 is checked by V_polyin P.

$$ d_{i} $$

$$ f_{i} $$

$$ \mathcal{P} $$

$$ i\in[M] $$

$$ \mathrm{V}_{\mathtt{p o l}!} $$

0i 0i 0i For i 2 [M], let d be the \matching" d_j. That is d = d_jif h_i= f_j, and d = deg(g_j) if h_i= g_j.

$$ G(X,h_{1}(\upsilon_{1}(X)),\ldots,h_{M}(\upsilon_{M}(X)))\equiv0 $$

$$ \mathcal{P} $$

$$ d_{i}^{\prime} $$

$$ d_{j} $$

$$ d_{i}^{\prime}=d_{j}\ {\mathrm{i f}}\ h_{i}=f_{j} $$

$$ d_{i}^{\prime}=\deg(g_{j}) $$

$$ h_{i}=g_{j} $$

Let t = t (P) be the number of distinct polynomials amongst v₁;:::;v_M. Let S₁ [ ::: [ S_t= [M] be a partition of [M] according to the distinct values. For j 2 [t], 0i let e_j:= maxfd g _i2Sj P P

$$ t^{},=,t^{}(\mathcal{P}) $$

$$ v_{1},\ldots,v_{M} $$

$$ S_{1}\cup\ldots\cup S_{t^{*}}=[M] $$

$$ [M] $$

$$ j\in[t^{*}] $$

$$ e_{j}:=\operatorname*{m a x}\left{d_{i}^{\prime}\right}_{i\in S} $$

Finally, dene e(P) := (d_i+ 1) + e_j. i2_[t] j2[t]

$$ \mathsf{e}(\mathring{\mathcal{P}}):=\sum_{i\in[t]}(d_{i}+1)+\sum_{j\in[t^{*}]}e_{j} $$

Lemma 4.7. Let P be a public coin (d;D;t;‘)-polynomial protocol for a relation R where only one identity is checked by V_poly. Then we can construct a protocol P for R with knowledge soundness in the Algebraic Group Model under 2d-DLOG such that

$$ \mathcal{P} $$

$$ (d,D,t,\ell) $$

$$ \mathcal{R} $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

$$ \mathcal{P}^{*} $$

1.The prover P in P requires e(P) G₁*-exponentiations.*

$$ \mathcal{P}^{*} $$

$$ \mathsf{e}(\mathcal{P})\ {\mathbb{G}}_{1}\texttt{e x p o n e n t i a t i o n}. $$

2.The total prover communication consists of t + t (P) G₁ elements and M F*-* elements.

$$ t+t^{*}(\mathcal{P})\enspace\mathbb{G}_{1} $$

3.The verier V requires t + t (P) G₁*-exponentiations, two pairings and one eval-* uation of G.

$$ t+t^{*}(\mathcal{P})\ \mathbb{G}_{1} $$

Proof. Let S = (gen*;com;open) be the d-polynomial commitment scheme described in Lemma 3.2. The SRS of P includes srs = gen(d), with the addition of fcom(g₁);:::;* com(g_‘)g.

$$ \mathcal{S}=(\mathsf{g e n},\mathsf{c o m},\mathsf{o p e n}) $$

$$ \mathcal{P}^{*} $$

$$ {\mathsf{s r s}}={\mathsf{g e n}}(d) $$

$$ {\mathsf{c o m}(g_{1}),\ldots,\mathsf{c o m}(g_{\ell})} $$

Given P we describe P. P and V behave identically to P_polyand V_poly, except in the following two cases.

$$ \mathcal{P} $$

$$ \mathcal{P}^{*} $$

$$ \mathrm{P}_{\mathsf{p o l y}} $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

Whenever Ppolysends a polynomial fi2 F<d[X] to I in P, P sends cmi= com(fi) to V.

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ \mathcal{T} $$

$$ \mathcal{P} $$

$$ f_{i}\in\mathbb{F}_{<d}[X] $$

$$ {\mathsf{c m}}{i}={\mathsf{c o m}}(f{i}) $$

Let v₁;:::;v_tbe the distinct polynomials amongst v₁;:::;v_M. When V_polyasks about the identity

$$ v_{1}^{},\ldots,v_{t^{}}^{*} $$

$$ v_{1},\ldots,v_{M} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ F (X) := G \left(X, h _ {1} \left(v _ {1} (X)\right), \dots , h _ {M} \left(v _ {M} (X)\right)\right) \equiv 0, $$

1. V chooses random x 2 F, computes v₁(x);:::;v_t(x), and sends x to P.

$$ x\in\mathbb{F} $$

$$ v_{1}^{}(x),\ldots,v_{t^{}}^{*}(x) $$

$$ \mathbf{P} $$

2. P replies with fs_ig, which are the alleged values h₁(v₁(x));:::;h_M(v_M(x)). i2[M]

$$ \left{s_{i}\right}_{i\in[M]} $$

$$ h_{1}(v_{1}(x)),\ldots,h_{M}(v_{M}(x)) $$

3. V engages in the protocol open with P to verify the correctness of fs_ig

$$ \left{s_{i}\right} $$

4. V outputs acc if and only if

$$ G(x,s_{1},\ldots,s_{M})=0. $$

The eciency claims about P follow directly from Lemma 3.2.

$$ \mathcal{P}^{*} $$

To prove the claim about knowledge soundness in the AGM we must describe the extractor E for the protocol P. For this purpose, let E_Pbe the extractor of the protocol P as guaranteed to exist from Denition 4.3, and E_Sbe the extractor for the Knowledge Soundness game of S as in Denition 3.1.

$$ E\mathcal{P} $$

$$ \mathcal{P}^{*} $$

$$ \mathcal{P} $$

$$ E_{\mathcal{S}} $$

$$ \mathcal{S} $$

Now assume an algebraic adversary A is taking the role of P in P.

$$ \mathcal{P}^{*} $$

$$ \mathcal{A} $$

1. E sends the commitments cm₁*;:::;* cm_tto E_Sand receives in return f₁;:::;f_t2 F<d[X].

$$ \mathsf{c m}{1},\ldots,\mathsf{c m}{t} $$

$$ E $$

$$ E_{\mathcal{S}} $$

$$ f_{1},\ldots,f_{t}\in $$

$$ \mathbb{F}_{<d}[X] $$

2. E plays the role of I in interaction with E_P, sending him the polynomials f₁;:::;f_t.

$$ f_{1},\ldots,f_{t} $$

$$ E _ {\mathcal {P}} $$

3.When E_Poutputs*!, E also outputs!*.

$$ \omega $$

$$ E\mathcal{P} $$

Now let us dene two events (over the randomness of V,A and gen):

$$ \mathbf{v},\mathcal{A} $$

1.We think of an adversary A_Pparticipating in P, and using the polynomials f₁;:::;f_tas their messages to I. We dene A to be the event that the identity F held, but (x*;!*) 2R =. By the KS of P, Pr(A) = negl().

$$ \mathcal{A}\mathcal{D} $$

$$ \mathcal{P} $$

$$ f_{1},\ldots,f_{t} $$

$$ {\mathcal{P}},\operatorname*{P r}(A)={\mathsf{n e g l}}(\lambda) $$

$$ (\mathsf x,,\omega)\notin\mathcal{R} $$

2.We let B be the event that for some i 2 [M];h_i(v_i(x)) 6= s_i, and at the same time V_PChas output acc when open was run as a subroutine in Step 3. By the KS of S, Pr(B) = negl().

$$ i\in[M],h_{i}(v_{i}(x))\neq s_{i}, $$

$$ \mathrm{V}_{\mathsf{P C}} $$

$$ {\mathcal{I}},\operatorname*{P r}(B)={\mathsf{n e g l}}(\lambda) $$

Now look at the event C that V outputs acc, but E failed in the sense that (x*;!*) 2R =. We split C into two events.

$$ (\mathsf x,,\omega)\notin\mathcal{R} $$

1. A or B also happened - this has negl() probability.

2. C happened but not A or B. This means F is not the zero polynomial, but F (x) = 0; which happens w.p. negl().

$$ F(x)=0; $$

Reducing the number of eld elements We describe an optimization by Mary Maller, to reduce the number of F-elements in the proof from M. We begin with an illustrating example. Suppose V wishes to check the identity h₁(X) h₂(X) h₃(X) 0. The compilation described above would have P send the values of h₁;h₂;h₃ at a random x 2 F; and V would check if h₁(x)h₂(x) h₃(x) = 0. Thus, P sends three eld elements.

$$ h_{1}(X)\cdot h_{2}(X)-h_{3}(X)\equiv0 $$

$$ h_{1},h_{2},h_{3} $$

$$ x\in\mathbb{F} $$

$$ h_{1}(x)h_{2}(x)-h_{3}(x)=0 $$

Note however, that we could instead have P send only c := h₁(x), and then simply verify in the open protocol whether the polynomial L(X) := c h₂(X) h₃(X) is equal to zero at x. (Note that we can compute com(L) = c com(h₂) com(h₃).)

$$ c:=h_{1}(x) $$

$$ L(X):=c\cdot h_{2}(X)-h_{3}(X) $$

$$ 1!()!=\circ\mathsf{c o m}(h_{2})-\circ\mathsf{c o m}(h_{3}).! $$

To describe the general method, we must dene another technical measure of a polynomial protocol. We assume again (mainly for simplicity) that V_polychecks only one identity F. Now dene r(P) to be the minimal size of a subset S [M] such that

$$ \mathrm{V}_{\mathfrak{p o l v}} $$

$$ \ {mathfrak r}({\mathcal P}) $$

$$ S subset M $$

([M] n S) S_ifor one of the subsets S_iof the partition described before Lemma 4.7.

$$ ([M]\setminus S)\subset S_{i} $$

$$ S_{i} $$

The polynomial G such that

$$ F(X):=G(X,h_{1}(v_{1}(X)),\ldots,h_{M}(v_{M}(X))) $$

has degree zero or one as a polynomial in the variables fX_jg whose coej2[M]nS cients are polynomials in X and fX_jg. _j2S

$$ \left{X_{j}\right}_{j\in[M]\backslash S} $$

$$ \left{X_{j}\right}_{j\in S}. $$

$$ \mathcal{P} $$

Assume P is such that r := r(P) < M

$$ \mathsf{r}:=\mathsf{r}(\mathcal{P})<M $$

We claim that the reduction of Lemma 4.7 can be changed such that only r F-elements are sent by P.

$$ \mathsf{r F}. $$

1. P now sends only fs_i= h_i(v_i(x))g. _i2S

$$ {s_{i}=h_{i}(v_{i}(x))}_{i\in S} $$

2.Now let L be the restriction Gj^{X=x;Xi=si;i2S}. V and P use fcom(fⁱg, and the i2[S] linearity of com, to compute the commitment to the corresponding restriction F_L of F.

$$ G|{X=x;X{i}=s_{i},i\in S} $$

$$ {\mathsf{c o m}(f_{i}}_{i\in[S]} $$

$$ F_{L} $$

3. V computes the unique value s = F_L(v (x)), that will imply F (x) = 0, assuming i correctness of fs_ig. _i2S

$$ F(x)=0 $$

$$ s=F_{L}(v_{i}^{*}(x)) $$

$$ \left{s_{i}\right}_{i\in S} $$

4.Now P and V engage in the protocol open to verify the correctness of fs_ig [fsg. _i2S

$$ \left{s_{i}\right}_{i\in S}\cup\left{s\right} $$

5 Polynomial protocols for identifying permutations

At the heart our universal SNARK is a \permutation check" inspired by the permutation + argument originally presented by Bayer and Groth [BG12] and its variants in [BCC 16, MBKM19]. Again, our main advantage over [MBKM19] is getting a simpler protocol by working with univariate polynomials and multiplicative subgroups.

Degree bounds: We use two integer parameters n d. Intuitively, n is the degree of the honest prover’s polynomials, and d is the bound we actually enforce on malicious provers. Accordingly, we assume degree bound n while analyzing prover eciency and describing \ocial" protocol inputs; but allow degree bound d while analyzing soundness.

$$ n\leq d $$

We assume the existence of a multiplicative subgroup H F of order n with generator g.

$$ H\subset\mathbb{F} $$

i For i 2 [n], we denote by Li(X) the element of F<n[X] with Li(g) = 1 and Li(a) = 0 i for a 2 H dierent from g, ⁱ.e. fLⁱg is a Lagrange basis for H. i2[n]

$$ L_{i}(X) $$

$$ i\in[n] $$

$$ \mathbb{F}_{<n}[X] $$

$$ L_{i}(\mathbf{g}^{i})=1 $$

$$ L_{i}(a)=0 $$

$$ a\in H $$

$$ \mathbf{g}^{i} $$

$$ \left{L_{i}\right}_{i\in\left[n\right]} $$

One thing to note is that the fL_ig can \reduce point checks to range checks". More precisely, the following claim follows directly from the denition of fL_ig.

$$ \left{L_{i}\right} $$

$$ \left{L_{i}\right} $$

Claim 5.1. Fix i 2 [n], and Z;Z 2 F[X]. Then L_i(a)(Z(a) Z (a)) = 0 for each i i a 2 H if and only if Z(g) = Z (g).

$$ i,\in,[n] $$

$$ Z,Z^{*},\in,\mathbb{F}[X] $$

$$ L_{i}(a)(Z(a)-Z^{*}(a))=0 $$

$$ a\in H $$

$$ ^ {f} Z \left(\mathbf {g} ^ {i}\right) = Z ^ {*} \left(\mathbf {g} ^ {i}\right) $$

For f;g 2 F<d[X] and a permutation : [n]! [n], we write g = (f) if for each i (i) 7 a 2 H, g(g) = f⁽g⁾.

$$ f,g,\in,{\mathbb{F}}_{<d}[X] $$

$$ \sigma:[n]\to[n] $$

$$ g=\sigma(f) $$

$$ a\in H,,g(\mathfrak{g}^{i})=f(\mathfrak{g}^{\sigma(i)}) $$

We present a ranged polynomial protocol enabling P_polyto prove that g = (f).

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ g=\sigma(f) $$

i Preprocessed polynomials: The polynomial SID2 F<n[X] dened by SID(g) = i for each i i 2 [n] and S 2 F<n[X] dened by S (g) = (i) for each i 2 [n].

$$ \mathsf{S}{\mathsf{I D}}\in\mathbb{F}{<n}[X] $$

$$ \mathsf{S}_{\mathsf{I D}}(\mathbf{g}^{i})=i $$

$$ \mathsf{S}{\sigma}\in\mathbb{F}{<n}[X] $$

$$ i\in[n] $$

$$ \mathsf{S}_{\sigma}(\mathbf{g}^{i})=\sigma(i) $$

$$ i\in[n] $$

$$ f,g\in\mathbb{F}_{<n}[X] $$

Inputs: f;g 2 F<n[X]

⁷ Note that according to this denition there are multiple g with g = (f). Intuitively, we think of (f) as the unique such g 2 F<n[X], but do not dene this formally to avoid needing to enforce this degree bound for eciency reasons.

$$ g=\sigma(f) $$

$$ g,\in,\mathbb{F}_{<n}[X] $$

$$ \sigma(f) $$

Protocol:

1.V_polychooses random*; 2* F and sends them to P_poly.

$$ \beta,\gamma\in\mathbb{F} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

2.Let f⁰ := f + S_ID+;g⁰ := g + S +. That is, for i 2 [n]

$$ f^{\prime}:=f+\beta\cdot\mathsf{S}{\mathsf{I D}}+\gamma,g^{\prime}:=g+\beta\cdot\mathsf{S}{\sigma}+\gamma $$

$$ i\in[n] $$

$$ f^{\prime}(\mathbf{g}^{i})=f\big(\mathbf{g}^{i}\big)+\beta\cdot i+\gamma,g^{\prime}(\mathbf{g}^{i})=g\big(\mathbf{g}^{i}\big)+\beta\cdot\sigma(big)i+\gamma $$

3.Ppolycomputes Z 2 F<n[X], such that Z(g) = 1; and for i 2f2;:::;ng Y

$$ \mathrm{P}_{\mathrm{p o l y}} $$

$$ Z\in\mathbb{F}_{<n}[X] $$

$$ Z({\mathfrak{g}})=1. $$

$$ i\in{2,\ldots,n} $$

$$ Z(\mathbf{g}^{i})=\prod_{1\leq j<i}f^{\prime}(\mathbf{g}^{j})/g^{\prime}(\mathbf{g}^{j}). $$

(If one of the product elements is undened, which happens w.p. negl() over, the protocol is aborted⁸.)

$$ \gamma $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

4.P_polysends Z to I.

5.V_polychecks if for all a 2 H

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ a\in H $$

(a) L₁(a)(Z(a) 1) = 0.

$$ L_{1}(a)\big(Z(a)-1\big)=0. $$

(b) Z(a)f⁰(a) = g⁰(a)Z(a g).

$$ Z(a)f^{\prime}(a)=g^{\prime}(a)Z(a\cdot\mathsf{g}). $$

and outputs acc i all checks hold.

Lemma 5.2. Fix f;g 2 F<d[X]. For any strategy of Ppoly, the probability of Vpoly outputting acc in the above protocol when g 6= (f) is negl().

$$ f,g,\in,\mathbb{F}_{<d}[X] $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

$$ \mathrm{P}_{\mathrm{p o l y}} $$

$$ g\neq\sigma(f) $$

Proof. Suppose that g 6= (f). By claim A.1, e.w.p negl() over the choice of*; 2* F, Y Y

$$ g\neq\sigma(f) $$

$$ \beta,\gamma\in\mathbb{H}. $$

$$ a:=\prod_{i\in[n]}f^{\prime}(\mathbf{g}^{i})\neq b:=\prod_{i\in[n]}g^{\prime}(\mathbf{g}^{i}). $$

i Assume*;* were chosen such that the above holds, and also such that g⁰(g) 6= 0 for all i 2 [n]. We show V_polyrejects; specically, that assuming both identites V_polychecks hold leads to contradiction.

$$ \beta,\gamma $$

$$ g^{\prime}(\mathbf{g}^{i})\neq0 $$

$$ i\in[n] $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

From the rst check we know that Z(g) = 1. From the second check we can show inductively, that for each i 2 [n]

$$ Z({mathfrak g g})=1 $$

$$ i\in[n] $$

$$ Z(\mathbf{g}^{i+1})=\prod_{1\leq j\leq i}\frac{f^{\prime}(\mathbf{g}^{j})}{g^{\prime}(\mathbf{g}^{j})}. $$

n+1 In particular, Z(g) = a=b.

$$ Z \left(\mathbf {g} ^ {n + 1}\right) = a / b $$

$$ 1 = Z (\mathbf {g}) = Z \left(\mathbf {g} ^ {n + 1}\right) = a / b \neq 1, $$

$$ \mathfrak{g}^{n+1}=\mathfrak{g} $$

ⁿ⁺¹ As g = g,

which is a contradiction.

⁸ This abort ruins the perfect completeness of the protocol. If one wishes to preserve perfect comi pleteness, the protocol can be altered such that if for some i, g⁰(g) = 0, Ppolyproves this to Vpoly, and Vpolyaccepts in this case. This adds a negl() factor to the soundness error.

$$ i, g ^ {\prime} \left(\mathbf {g} ^ {i}\right) = 0, \mathrm {P} _ {\mathrm {p o l y}} $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

$$ \mathrm{V}_{\mathrm{p o l y}} $$

5.1 Checking \extended" permutations

In our protocol, we in fact need to check a permutation \across" the values of several polynomials. Let us dene this setting formally. Suppose we now have mutliple polynomials f₁;:::;fk2 F<d[X] and a permutation : [kn]! [kn]. For (g₁;:::;gk) 2 k (F<d[X]) , we say that (g₁;:::;gk) = (f₁;:::;fk) if the following holds.

$$ f_{1},\ldots,f_{k},\in,\mathbb{F}_{<d}[X] $$

$$ \sigma,:,[k n],\to,[k n] $$

$$ {\bigl(}g_{1},\ldots,g_{k}{\bigr)}={\sigma}bigl({f_{1}},\ldots,{f_{k}}{\bigr)} $$

$$ \left(11,,\ldots,g{k}\right)\in; $$

$$ \big(\mathbb{F}_{<d}[X]\big)^{k} $$

kn Dene the sequences (f₍₁₎;:::;f_(kn)); (g₍₁₎;:::;g_(kn)) 2 F by

$$ (f_{(1)},\ldots f{}{(k n)}),(g{(1)},\ldots,g_{(k n)}){\ \in\ }{mathbb}F^{k n} $$

$$ f_{((j-1)\cdot n+i)}:=f_{j}(\mathsf{g}^{i}),g_{((j-1)\cdot n+i)}:=g_{j}(\mathsf{g}^{i}), $$

for each j 2 [k];i 2 [n]. Then we have g_(‘)= f_{( (‘))}for each ‘ 2 [kn].

$$ j\in[k],i\in[n] $$

$$ g_{(\ell)}=f_{(\sigma(\ell))} $$

$$ \ell\in|k n| $$

i Preprocessed polynomials: The polynomials SID1;:::;SIDk2 F<n[X] dened by SIDj(g) = (j 1) n + i for each i 2 [n].

$$ \mathsf{S}{\mathsf{I D}1},\ldots,\mathsf{S}{\mathsf{I D}k}\in\mathbb{F}_{<n}[X] $$

$$ \mathsf{S}{\mathsf{I D}{j}}(\mathsf{g}^{i})= $$

$$ i\in[n] $$

$$ (j-1)\cdot n+i $$

In fact, only S_ID= S_ID1is actually included in the set of preprocessed polynomials, as S^IDj(x) can be computed as S^IDj(x) = S^ID(x) + (j 1) n.

$$ S _ {\mathrm {I D}} = S _ {\mathrm {I D} 1} $$

$$ \mathsf{S}_{\mathsf{D D}}(x) $$

i For each j 2 [k], Sj2 F<n[X], dened by Sj(g) = ((j 1) n + i) for each i 2 [n].

$$ j\in[k],\mathsf{S}{\sigma j}\in\mathbb{F}{<n}[X] $$

$$ \mathrm {S} _ {\sigma j} \left(\mathbf {g} ^ {i}\right) = \sigma ((j - 1) \cdot n + i) $$

$$ i\in[n] $$

Inputs: f₁;:::;fk;g₁;:::;gk2 F<n[X]

$$ f_{1},\ldots,f_{k},g_{1},\ldots,g_{k}\in\mathbb{F}_{<n}[X] $$

Protocol:

1.V_polychooses random*; 2* F and sends to P_poly.

$$ \mathrm{V}_{\mathfrak{p o l y}} $$

$$ \beta,\gamma\in\mathbb{F} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

2.Let f := f_j+ S_IDj+, and g := g_j+ S_j+. That is, for j 2 [k];i 2 [n] j0 j0

$$ f_{j}^{\prime}:=f_{j}+\beta\cdot\mathsf{S}_{\mathsf{I D}j}+\gamma $$

$$ g_{j}^{\prime}:=g_{j}+\beta\cdot\mathsf{S}_{\sigma j}+\gamma $$

$$ j\in[k],i\in[n] $$

$$ f_{j}^{\prime}(\mathbf{g}^{i})=f_{j}(\mathbf{g}^{i})+\beta((j-1)\cdot n+i)+\gamma,g_{j}^{\prime}(\mathbf{g}^{i})=g_{j}(\mathbf{g}^{i})+\beta\cdot\sigma((j-1)\cdot n+i)+\gamma $$

3.Dene f⁰;g⁰ 2 F<kn[X] by

$$ f^{\prime},g^{\prime}\in\mathbb{F}_{<k n}[X] $$

$$ f^{\prime}(X):=\prod_{j\in[k]}f_{j}^{\prime}(X),g^{\prime}(X):=\prod_{j\in[k]}g_{j}^{\prime}(X). $$

4.Ppolycomputes Z 2 F<n[X], such that Z(g) = 1; and for i 2f2;:::;ng Y

$$ \mathrm{P}_{\mathrm{p o l y}} $$

$$ Z\in\mathbb{F}_{<n}[X] $$

$$ Z(\mathfrak{g})=1. $$

$$ i\in{2,\ldots,n} $$

$$ Z(\mathbf{g}^{i})=\prod_{1\leq\ell<i}f^{\prime}(\mathbf{g}^{j})/g^{\prime}(\mathbf{g}^{j}). $$

(The case of one of the products being undened is handled as in the previous protocol.)

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

5.P_polysends Z to I.

6.V_polychecks if for all a 2 H

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ a\in H $$

(a) L₁(a)(Z(a) 1) = 0.

$$ L_{1}(a)\ Z(a)-1)=0 $$

(b) Z(a)f⁰(a) = g⁰(a)Z(a g).

and outputs acc i all checks hold.

$$ Z(a)f^{\prime}(a)=g^{\prime}(a)Z(a\cdot\mathfrak{g}). $$

Lemma 5.3. Fix any f₁;:::;fk;g₁;:::gk2 F<d[X] and permutation on [kn] as inputs to the above protocol P_k. Suppose that (g₁;:::;g_k) 6= (f₁;:::;f_k). Then, for any strategy of P_poly, the probability of V_polyoutputting acc is negl().

$$ f_{1},\ldots,f_{k},g_{1},\ldots g_{k}\in\mathbb{F}_{<d}[X] $$

$$ \mathcal{P}_{k} $$

$$ \ \ (g_{1},\ldots,g_{k})\neq\ \sigma(f_{1},\ldots,f_{k}) $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

Proof. (g₁;:::;gk) 6= (f1*;:::;fk) implies that with high probability over; 2* F the n o i product F of the values f (g) ⁱs dierent from the product G of the values j0 j2[k];i2[n] n o ⁱ g (g). Note _now that j0 j2[k];i2[n] Y Y

$$ {\big(}g_{1},\ldots,g_{k}{\big)}\neq\sigma(f_{1},\ldots,f_{k}{\big)} $$

$$ \beta,\gamma\in\mathbb{F} $$

$$ \left{f_{j}^{\prime}(\mathbf{g}^{i})\right}_{j\in[k],i\in[n]} $$

$$ \left{g _ {j} ^ {\prime} \left(\mathbf {g} ^ {i}\right) \right} _ {j \in [ k ], i \in [ n ]} $$

$$ F=\prod_{i\in[n]}f^{\prime}(\mathbf{g}^{i}),G=\prod_{i\in[n]}g^{\prime}(\mathbf{g}^{i}), $$

and that the next steps of the protocol are identical to those in the previous protocol, and as analyzed there - exactly check if these products are equal.

5.2 Checking \extended copy constraints" using a permutation

We nally come to the actual primitive that will be used in our main protocol. Let T = fT₁;:::;Tsg be a partition of [kn] into disjoint blocks. Fix f₁;:::;fk2 F<n[X]. kn We say that f₁;:::;f^kcopy-satisfy T if, when dening (f⁽¹⁾;:::;f_(kn)) 2 F as above, 0 we have f_(‘)= f_(‘0)whenever ‘;‘ belong to the same block of T.

$$ \mathcal{T}={T_{1},\ldots,T_{s}} $$

$$ f_{1},\ldots,f_{k}\in\mathbb{F}_{<n}[X] $$

$$ f_{1},\ldots,f_{k} $$

$$ \ {cal tau T}\mathrm{i f f.} $$

$$ (f_{(1)},\ldots,f_{(k n)})\in\mathbb{^k k} $$

$$ f_{(\ell)}=f_{(\ell^{\prime})} $$

$$ \ell,\ell^{\prime} $$

$$ \mathcal{T} $$

We claim that the above protocol for extended permutations can be directly used for checking whether f₁;:::;f_ksatisfy T : Dene a permutation (T) on [kn] such that for each block T_iof T, (T) contains a cycle going over all elements of T_i. Then, (f₁;:::;f_k) copy-satisfy T if and only if (f₁;:::;f_k) = (f₁;:::;f_k).

$$ f_{1},\ldots,f_{k} $$

$$ \tau $$

$$ \sigma (\mathcal {T}) $$

$$ |k n| $$

$$ T_{i} $$

$$ \mathcal{T},\sigma(\mathcal{T}) $$

$$ T_{i} $$

$$ (f_{1},\ldots,f_{k}) $$

$$ {f_{1},\ldots,f_{k}})=\sigma({{f{1},\ldots,f_{k}}}) $$

6 Constraint systems

Fix integers m;n with n m 2n We present a type of constraint system that captures fan-in two arithmetic circuits of unlimited fan-out with n gates and m wires (but is more general).

$$ m,n $$

$$ n\leq m\leq2n $$

The constraint system C = (V; Q) is dened as follows.

$$ \mathcal{C}=(\mathcal{V},\mathcal{Q}) $$

n V is of the form V = (a*;* b*;c), where a;* b*;* c 2 [m]. We thiⁿk of a*;* b*;*c as the left, right and output sequence of C respectively.

$$ \ {\mathcal{V}}=(\mathbf{a},\mathbf{b},\mathbf{c}) $$

$$ \ {mathfrakb}b,{\mathfrak c c}\in[m]^{n} $$

n 5 n Q = (q_L; q_R; q_O; q_M; q_C) 2 (F) where we think of q_L; q_R; q_O; q_M; q_C2 F as \selector vectors".

$$ \mathcal{Q}=(\mathbf{q_{L}},\mathbf{q_{R}},\mathbf{q_{O}},\mathbf{q_{M}},\mathbf{q_{C}}),\ \in,(\mathbb{F}^{n})^{5} $$

$$ \mathbf {q} _ {\mathrm {L}}, \mathbf {q} _ {\mathrm {R}}, \mathbf {q} _ {\mathrm {O}}, \mathbf {q} _ {\mathrm {M}}, \mathbf {q} _ {\mathrm {C}} \in \mathbb {F} ^ {n} $$

$$ \mathbf{x}\in\mathbb{R}^{m} $$

$$ i\in[n] $$

m We say x 2 F satises C if for each i 2 [n],

$$ \mathcal{C} $$

$$ (\mathbf{c_{I L}}){i}\cdot\mathbf{x}{\mathbf{a}{i}}+(\mathbf{c{I L}}){i}\cdot\mathbf{x}{\mathbf{b}{i}}+(\mathbf{c{I O}}){i}\cdot\mathbf{x}{\mathbf{c}{i}}+(\mathbf{c{I M}}){i}\cdot(\mathbf{c{I M}}){i}\cdot(\mathbf{x{a_{i}}\mathbf{x}{\mathbf{b}{i}}})+(\mathbf{c_{I C}})_{i}=0. $$

To dene a relation based on C, we extend it to include a positive integer ‘ m, and subset I [m] of \public inputs". Assume without loss of generality that I = f1*;:::;‘g*. ‘ m ‘ Now we can dene the relation R_Cas the set of pairs (x*;!) with x 2 F;! 2* F such that x := (x*;!*) satises C.

$$ \ell\leq m, $$

$$ {\mathcal{I}}\subset[m] $$

$$ \mathcal{C} $$

$$ \ {mathcal I={1,\ldots,\ell}} $$

$$ \mathcal{R}_{\mathcal{C}} $$

$$ (\mathsf x\boldsymbol) $$

$$ \mathbf{x}:=(\mathsf{x},\omega) $$

$$ \mathcal{C} $$

$$ \mathsf{x}\in\mathbb{F}^{\ell},\omega\in\mathbb{F}^{m-\ell} $$

We proceed to show some useful instantiations of this type of constraints.

Arithmetic circuits: A fan-in 2 circuit of n gates, each being either an addition or multiplication gate, can be captured in such a constraint system as follows.

1. m is set to be the number of wires, and each wire is associated with an index i 2 [m].

$$ i\in[m] $$

$$ i\in[n] $$

For each i 2 [n],

2.Set a_i; b_i; c_ito be the index of left/right/output wire of the i’th gate respectively.

$$ \mathbf{a}{i},\mathbf{b}{i},\mathbf{c}_{i} $$

3.Set (q_L)_i= 0*;(q_R)_i= 0;(q_M)_i= 1;*(q_O)_i= 1 when the i’th gate is a multiplication gate.

$$ (\mathbf{q}{\mathbf{L}}){i}=\mathbf{0},(\mathbf{q}{\mathbf{R}}){i}=\mathbf{0},(\mathbf{q}{\mathbf{M}}){i}=\mathbf{1},(\mathbf{q}{\mathbf{O}}){i}=-\mathbf{1} $$

4.Set (q_L)_i= 1*;(q_R)_i= 1;(q_M)_i= 0;(q_O)_i= 1 when the i’th gate is an addition gate. (Note that we can get \linear combination gates" by using other non-zero values for (q_L)_i;*(q_R)_i.)

$$ (\mathbf{q_{L}}){i}=\mathbf{1},(\mathbf{q{R}}){i}=\mathbf{1},(\mathbf{q{M}}){i}=\mathbf{0},(\mathbf{q{O}})_{i}=\mathbf{-1} $$

$$ (\mathbf{q_{L}}){i},(\mathbf{q{R}})_{i}.) $$

5.Always set (q_C)_i= 0.

$$ (\mathfrak{q c})_{i}=0 $$

Booleanity constraints: A common occurrence in proof systems is the need to enforce x_j2f0*;* 1g for some j 2 [m]. This is equivalent in our system to setting, for some i 2 [n],

$$ \mathtt{X}_{j}\in{0,1} $$

$$ i\in[n] $$

$$ j\in[m] $$

$$ \mathbf{a}{i}=\mathbf{b}{i}=j,(\mathbf{q}{\mathbf{L}}){i}=-1,(\mathbf{q}{\mathbf{M}}){i}=1,(\mathbf{q}{\mathbf{R}}){i}=(\mathbf{q}{\mathbf{O}}){i}=(\mathbf{q}{\mathbf{O}}){i}=0(\mathbf{q}{\mathbf{C}}){i}=0. $$

Enforcing public inputs: It is quite convenient and direct to enforce values of public inputs x₁*;:::* x_‘: To enforce the constraint x_j= x_jwe set for some i 2 [n]

$$ \mathbf{x}{1},\ldots\mathbf{x}{\ell}\colon $$

$$ \ {\tt x}{j}={\tt x}{j} $$

$$ i\in[n] $$

$$ \mathbf{a}{i}=j,(\mathbf{q}{\mathbf{L}}){i}=1,(\mathbf{q}{\mathbf{M}}){i}=(\mathbf{q}{\mathbf{R}}){i}=(\mathbf{q}{\mathbf{0}}){i}=0,(\mathbf{q}{\mathbf{C}}){i}=-\mathsf{x}{j}. $$

7 Main protocol

Let C = (V; Q) be a constraint system of the form described in Section 6. We present our main protocol for the relation R_C. It will be convenient to rst dene the following notion of the partition of C, denoted T_C, as follows.

$$ \mathcal{R}_{\mathcal{C}} $$

$$ \mathcal{T}_{\mathcal{C}} $$

$$ \ {\mathcal{V}}=(\mathbf{a},\mathbf{b},\mathbf{c}) $$

$$ \mathcal{C} $$

3n Suppose V = (a*;* b*;c); think of V as a vector V iⁿ [m]. For i 2 [m], let T_i[3n*] be the set of indices j 2 [3n] such that V_j= i. Now dene

$$ [m]^{3n} $$

$$ \mathcal{V} $$

$$ i\in[m] $$

$$ j\in[3n] $$

$$ T_{i}\subset[3n] $$

$$ V_{j}=i $$

$$ \mathcal{T}{\mathcal{C}}:=\left{T{i}\right}_{i\in[m]} $$

We make a nal denition before presenting the protocol. We say C is prepared for ‘ public inputs if for i 2 [‘]

$$ \mathcal{C} $$

$$ i\in[\ell] $$

$$ \mathbf{a}{i}=mathit,(\mathbf{e}{\mathbf{I}\mathbf{L}}){i}=\mathbf{1},(\mathbf{q}{\mathbf{I}\mathbf{M}}){i}=(\mathbf{q}{\mathbf{I}\mathbf{R}}){i}=(\mathbf{q}{\mathbf{O}}){i}=\mathbf{0},(\mathbf{q}{\mathbf{C}})_{i}=\mathbf{0}. $$

n Recall that H = fg*;:::;*g g. We present an H-ranged polynomial protocol for R_C.

$$ \mathcal{R}_{\mathcal{C}} $$

$$ H={\mathbf{g},\ldots,\mathbf{g}^{n}} $$

Preprocessing: Let = (T_C).

$$ \sigma=\sigma(\mathcal{T}_{\mathcal{C}}) $$

The polynomials SID1; SID2; SID3; S1; S2; S32 F<n[X] as dened in the protocol of subsection 5.1 .

$$ {\sf{S}}{\ {sf I}{\sf D}{1}},{\sf{S}}{\sf{I}{\sf D}{2}},{\sf{S}}{\ {\sf I}{\sf D}{3}},{\sf{S}}{\sigma}{}{1},{\sf{S}}{\sigma}{}{2},{\sf{S}}{\sigma}{}{3}\in\mathbb{F}_{<n}[X] $$

Overloading notation, the polynomials qL; qR; qO; qM; qC2 F<n[X] dened for each i 2 [n] by

$$ \ {tt q}{tt{L}},{\tt q}{\tt R},{\tt q}{{\tt q0}},{\tt q}{\tt M},{\tt q}{\mathbb C}\in\mathbb{F}_{<n}[X] $$

$$ i\in[n] $$

$$ \mathbf{q}{\mathbf{L}}(\mathbf{g}^{i})\mathrel{\mathop:}=(\mathbf{q}{\mathbf{L}}){i},\mathbf{q}{\mathbf{R}}(\mathbf{g}^{i})\mathrel{\mathop:}=(\mathbf{q}{\mathbf{R}}){i},\mathbf{q}{\mathbf{O}}(\mathbf{g}^{i})\mathrel{\mathop:}=(\mathbf{q}{\mathbf{O}}){i},\mathbf{q}{\mathbf{M}}(\mathbf{g}^{i})\mathrel{\mathop:}=(\mathbf{q}{\mathbf{M}}){i},\mathbf{q}{\mathbf{C}}(\mathbf{g}^{i})\mathrel{\mathop:}=(\mathbf{q}{\mathbf{C}})_{i} $$

Protocol:

m 1.Let x 2 F be P_poly’s assignment consistent with the public input x. P_polycomputes the three polynomials fL;fR;fO2 F<n[X], where for i 2 [n]

$$ \mathbf{x}\in\mathbb{R}^{m} $$

$$ \mathrm{P_{p o l y}} $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ f_{L},f_{R},f_{O}\in\mathbb{F}_{<n}[X] $$

$$ i\in[n] $$

$$ f_{L}(i)=\mathbf{x}{\mathbf{a}{i}},f_{R}(i)=\mathbf{x}{\mathbf{b}{i}},f_{O}(i)=\mathbf{x}{\mathbf{c}{i}}. $$

P_polysends f_L;f_R;f_Oto I.

$$ \tau. $$

$$ \mathrm{P}{}_{\mathrm{p o l y}} $$

$$ f_{L},f_{R},f_{O} $$

2.P_polyand V_polyrun the extended permutation check protocol using the permutation between (f_L;f_R;f_O) and itself. As explained in Section 5.2, this exactly checks whether (f_L;f_R;f_O) copy-satises T_C.

$$ \mathrm{V}_{\mathrm{p o l y}} $$

$$ \mathrm{P}_{\mathrm{p o l y}} $$

$$ \sigma $$

$$ (f_{L},f_{R},f_{O}) $$

$$ (f_{L},f_{R},f_{O}) $$

$$ \tau_{\mathcal{C}} $$

3.V_polycomputes the \Public input polynomial" X

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ {\mathsf{P I}}(X):=\sum_{i\in[\ell]}-\mathsf{x}{i}\cdot L{i}(X) $$

4.V_polynow checks the identity

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ \mathbf{q_{L}}\cdot f_{L}+\mathbf{q_{R}}\cdot f_{R}+\mathbf{q_{O}}\cdot f_{O}+\mathbf{q_{M}}\cdot f_{L}\cdot f_{R}+(\mathbf{q_{C}}+\mathsf{P I})=0, $$

on H.

Theorem 7.1. The above protocol is an H -ranged polynomial protocol for the relation R_C.

$$ \mathcal{R}_{\mathcal{C}} $$

Proof. Our main task is to describe and prove correctness of an extractor E. E simply uses the values of f_L;f_R;f_Oto construct an assignment in the natural way - e.g. if a_i= j i for some i 2 [n], let x_j= f_L(g). Fⁱnally, E denes and outputs*!* := (x_‘+1;:::;x_m). Now, let us look at the event C where (x;!) 2R = but V_polyoutputs acc. We split C into the two subevents, where (f_L;f_R;f_O) doesn’t copy-satisfy (C), and where it does. The

$$ f_{L},f_{R},f_{O} $$

$$ \mathbf{a}_{i}=j $$

$$ \mathbf{x}{j}=f{L}(\mathbf{g}^{i}) $$

$$ i\in[n] $$

$$ \omega:=\left(\mathtt{x}{\ell+1},\dots,\mathtt{x}{m}\right) $$

$$ (\mathsf{x},\omega)\notin\mathcal{R} $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ (f_{L},f_{R},f_{O}) $$

$$ \sigma(\mathcal{C}) $$ rst subevent has probability negl() according to the correctness of Lemma 5.3 and its use for copy-satisability checks as explained in Section 5.2.

On the other hand, if (f_L;f_R;f_O) copy-satises (C) and the identity checked by V_polyholds, it must be the case that (x*;!*) 2R_C.

$$ (f_{L},f_{R},f_{O}) $$

$$ \sigma(\mathcal{C}) $$

$$ \mathrm{V}_{\mathsf{p o l y}} $$

$$ (\mathsf{x},\omega)\in\mathcal{R}_{\mathcal{C}} $$

Now, using Lemma 4.5 and Lemma 4.7 we get

Corollary 7.2. Let C be a constraint system of the form described in Section 6 with parameter n. There is a protocol for the relation R_Cwith Knowledge Soundness in the Algebraic Group Model such that

$$ \mathcal{C} $$

$$ \mathcal{R}_{\mathcal{C}} $$

1.The prover P requires 11n + 2 G₁*-exponentiations.*

$$ n2\,\mathbb{G}_{1} $$

9 2.The total prover communication consists of 7 G₁*-elements and* 8 F*-elements.*

$$ 7\mathrm{G}_{1} $$

$$ 3~\mathbb{F}{e l e m e n t s}.{^9} $$

Proof. We bound the quantities e(P);t (P)*;*r(P) from Section 4.2; where P is the polynomial protocol derived from the protocol of Theorem 7.1 using Lemma 4.5. The result then follows from Lemma 4.7 and the discussion after. (For extra clarity, a full self-contained description of the nal protocol is given in Section 8.)

$$ \mathsf{e}(\mathcal{P}),t^{*}(\mathcal{P}),\mathsf{r}(\mathcal{P}) $$

$$ \mathcal{P} $$

We commit to polynomials fL;fR;fO2 F<n[X];Z 2 F<n+1[X] and a polynomial T 2 F<3n[X] resulting from division by ZH. This requires 7n + 1 G₁-exponentiations. Then, we need to open at random x 2 F: f_L(x);f_R(x);f_O(x);T(x); S_ID(x); S₁(x); S₂(x) and at x g: Z(x g).

$$ f_{L},f_{R},f_{O}:\in:\mathbb{F}{<n}[X],Z:\in:\mathbb{F}{<n+1}[X] $$

$$ T\in\mathbb{F}_{<3n}[X] $$

$$ Z_{H^{*}} $$

$$ 7n+1\ \mathbb{G}_{1} $$

$$ \ {\ {x}\in\ }\mathbb{F}\colon f_{L}(x),f_{R}(x),f_{O}(x),\mathit{T}(x),\mathsf{S}{\mathsf{I D}}(x),\mathsf{S}{\sigma1}(x),\mathsf{S}_{\sigma2}(x)} $$

$$ x\cdot\mathbf{g}\colon Z,x\cdot\mathbf{g}) $$

Note that xing these 8 values, our identity becomes a linear polynomial L which is a linear combination of q_L; q_R; q_O; q_M; q_C*;Z;*S₃. This implies r(P) 8.

$$ Z,\mathsf{S}_{\sigma3} $$

$$ \mathfrak{r}(\mathcal{P})\leq8 $$

It follows that

e(P) = 11n + 2 - as we add to the 7n + 1 cost of commitments, the maximal degree among the polynomial evaluated at x which is 3n plus the maximum degree among polynomials evaluated at *x=*g which is n + 1.

$$ \mathrm {e} \left(\mathcal {P}\right) = 1 1 n + 2 $$

$$ 7n+1 $$

$$ x/\mathbf{g} $$

$$ n+1 $$

t (P) = 2 - as we have two distinct evaluation points.

$$ t^{*}(\mathcal{P})=2 $$

r(P) 8.

$$ {\mathfrak{r}}({\mathcal{P}})\leq8. $$

8 The nal protocol, rolled out

For the reader’s convenience we present the full nal protocol.

Adding zero-knowledge was not explicitly discussed so far, but is implemented here: All that is needed is essentially adding random multiples of Z_Hto the witness basedpolynomials. This does not ruin satisability, but creates a situation where the values are either completely uniform or determined by verier equations.

$$ Z_{H} $$

⁹ The result stated in introduction with 7 F-elements uses an additional optimization suggested by Vitalik Buterin explained in Section 8.

We explicitly dene the multiplicative subgroup H as containing the n’th roots of unity in F_p, where*!* is a primitive n’th root of unity and a generator of H. i.e: n 1 H = f1*;!;:::;! g*.

$$ n^{\prime}\mathrm{t h}. $$

$$ H $$

$$ \mathbb{F}_{p}. $$

$$ \omega $$

$$ n ^ {2} $$

$$ H={1,\omega,\ldots,\omega^{n-1}} $$

We assume that the number of gates in a circuit is no more than n.

We also include an optimisation suggested by Vitalik Buterin, to dene the identity permutations through degree-1 polynomials. The identity permutations must map each wire value to a unique element 2 F. This can be done by dening S_ID1(X) = *X;*S_ID2(X) = *k₁X;*S_ID3(X) = k₂X, where k₁;k₂ are quadratic non-residues 2 F. This eectively maps each wire value to a root of unity in H, with right and output wires having an additional multiplicative factor of k₁;k₂ applied respectively. By representing the identity permutation via degree-1 polynomials, their evaluations can be directly computed by the verier. This reduces the size of the proof by 1 F element, as well as reducing the number of Fast-Fourier-Transforms required by the prover.

$$ \in\mathbb{F} $$

$$ \mathsf{S}{\mathsf{I D1}}(X)=X,\mathsf{S}{\mathsf{I D2}}(X)= $$

$$ k_{1}X,\mathsf{S}{\mathsf{I D3}}(X)=k{2}X $$

$$ k_{1},k_{2} $$

$$ \in\mathrm{F} $$

$$ k_{1},k_{2} $$

Finally, in the following protocol we use H to refer to a hash function, where H : ‘ f0*;* 1g!f0*;* 1g is an eciently computable hash function that takes arbitrary length inputs and returns ‘-bit outputs

$$ H $$

$$ {0,1}^{*}\rightarrow{0,1}^{\ell} $$

8.1 Polynomials that dene a specic circuit

The following polynomials, along with integer n, uniquely dene a universal SNARK circuit:

$$ n, $$

q_M(X); q_L(X); q_R(X); q_O(X); q_C(X), the ‘selector’ polynomials that dene the circuit’s arithmetisation

$$ \mathsf{q}{\mathsf{M}}(X),\mathsf{q}{\mathsf{L}}(X),\mathsf{q}{\mathsf{R}}(X),\mathsf{q}{\mathsf{O}}(X),\mathsf{q}_{\mathsf{C}}(X) $$

S_ID1(X) = X;S_ID2(X) = k₁X;S_ID3(X) = k₂X: the identity permutation applied to a; b;c. k₁;k₂ 2 F are chosen such that H;k1 H;k2 H are distinct cosets of H in F , and thus consist of 3n distinct elements. (For example, when*!* is a quadratic residue in F, take k₁ to be any quadratic non-residue, and k₂ to be a quadratic non-residue not contained in k₁ H.)

$$ {\sf S}{{sf\sf I D}1}(X){\ =\ }X,{\sf S}{\sf{I D}2}(X){\ =\ }k_{1}X,{\sf S}{\sf{I\ }D}3(X){\ =\ }k{2}X $$

$$ \mathbf {a}, \mathbf {b}, \mathbf {c}. k _ {1}, k _ {2} \in \mathbb {F} $$

$$ \mathbb{F}^{*} $$

$$ \omega $$

$$ \mathbb{F} $$

$$ k_{1} $$

$$ k_{2} $$

$$ k_{1}\cdot H. $$

S₁(X); S₂(X); S₃(X): the copy permutation applied to a*;* b*;* c

$$ \mathsf{S}{\sigma1}(X),\mathsf{S}{\sigma2}(X),\mathsf{S}_{\sigma3}(X) $$

$$ \mathbf{a},\mathbf{b},\mathbf{c} $$

n, the total number of arithmetic gates for a given circuit. This is used by Vsnark() n to compute the vanishing polynomial Z_H(X) = X 1

$$ n. $$

$$ \mathsf{Z}_{\mathsf{H}}(X)=X^{n}-1 $$

8.2 Commitments to wire values

For the following protocol we describe a proof relation for a universal SNARK circuit containing n arithmetic gates. The witnesses to the proof are the wire value witnesses ³ⁿ (w_i). The commitments [a]₁; [b]₁; [c]₁are computationally binding Kate polynomial i=1 commitments to the wire value witnesses, utilizing a structured reference string containn ing the group elements (x [1]₁;:::;x [1]₁).

$$ (w_{i})_{i=1}^{3n} $$

$$ [a]{1},[b]{1},[c]_{1}] $$

$$ \ x\cdot[1]{1},\ldots,x^{n}\cdot[1]{1}) $$

8.3 The un-rolled universal SNARK proof relation 8

$$ \mathcal {R} \mathrm {s n a k} (\lambda) = \left{ \begin{array}{c} (x, w, c r s) = \left(\left(w _ {i}\right) _ {i \in [ \ell ]}\right), \left(\left(w _ {i}\right) _ {i = 1, i \notin [ \ell ]} ^ {3 n}\right), \ \left(q _ {M i}, q _ {L i}, q _ {R i}, q _ {O i}, q _ {C i}\right) _ {i = 1} ^ {n}, n, \sigma (x)) \ \text {F o r a l l} i \in {1, \dots , 3 n }: w _ {i} \in \mathbb {F} _ {p}, \text {a n d f o r a l l} i \in {1, \dots , n }: \ w _ {i} w _ {n + i} q _ {M i} + w _ {i} q _ {L i} + w _ {n + i} q _ {R i} + w _ {2 n + i} q _ {O i} + q _ {C i} = 0 \ \text {a n d f o r a l l} i \in {1, \dots , 3 n }: w _ {i} = w _ {\sigma (i)} \end{array} \right. $$

8.4 The protocol

Common input:

$$ n,(x\cdot[1]{1},\ldots,x^{n+2}\cdot[1]{1}),(q_{M i},q_{L i},q_{R i},q_{Q i},q_{C i})_{i=1}^{n},\sigma(X), $$

$$ \mathfrak{q}{\mathbb{M}}(X)=\sum{i=1}^{n}q_{M i}\mathsf{L}_{i}(X), $$

$$ \mathfrak{q}{\mathsf{L}}\big(X\big)=\sum{i=1}^{n}q_{L i}\mathsf{L}_{i}\big(X\big), $$

$$ \mathrm {q} _ {\mathrm {R}} (X) = \sum_ {i = 1} ^ {n} q _ {R i} \mathrm {L} _ {i} (X), $$

$$ \mathfrak{q}{0}(X)=\sum{i=1}^{n}q o i\mathsf{L}_{i}(X), $$

$$ \mathfrak{q}{\mathsf{C}}(X)=\sum{i=1}^{n}q_{C i}\mathsf{L}_{i}(X), $$

$$ \mathsf{S}{\sigma1}(X)=\sum{i=1}^{n}\sigma(i)\mathsf{L}_{i}(X), $$

$$ \mathsf{S}{\sigma2}\big(X\big)=\sum{i=1}^{n}\sigma\big(n+i\big)\mathsf{L}_{i}\big(X\big), $$

$$ \mathsf{S}{\sigma{3}}(X)=\sum_{i=1}^{n}\sigma(2n+i)\mathsf{L}_{i}(X) $$

3n Prover input: ((w_i)) _i=1

$$ \left((w_{i})_{i=1}^{3n}\right) $$

Verier input:

$$ [q_{\mathsf{M}}]{1}:=\mathsf{q}{\mathsf{M}}(x)\cdot[1]{1},[q{\mathsf{L}}]{1}:=\mathsf{q}{\mathsf{L}}(x)\cdot[1]{1},[q{\mathsf{R}}]{1}:=\mathsf{q}{\mathsf{R}}(X)\cdot[1]{1},[q{\mathsf{O}}]{1}:=\mathsf{q}{\mathsf{O}}(X)\cdot[1]_{1}, $$

$$ [s_{\sigma\mathbf{1}}]{1}:=\mathsf{S}{\sigma\mathbf{1}}\cdot[1]{1},[s{\sigma\mathbf{2}}]{1}:=\mathsf{S}{\sigma\mathbf{2}}\cdot[1]{1},[s{\sigma\mathbf{3}}]{1}:=\mathsf{S}{\sigma\mathbf{3}}\cdot[1]_{1} $$

$$ x\cdot[1]_{2} $$

3n Psnark()((w_i)) : _i=1

$$ ({lambda}){}(({{w_{i}}})_{i=1}^{3n}) $$

Generate random blinding scalars (b₁;:::;b₉) 2 F_p

$$ (b_{1},\ldots,b_{9})\in\mathbb{F}_{p} $$

Compute wire polynomials a(X)*;b(X);*c(X) :

$$ \ {\mathsf{a}}(X),{\mathsf{b}}(X),{\mathsf{c}}(X) $$

$$ \mathsf{a}(X)=(b_{1}X+b_{2})\mathsf{Z}{\mathsf{H}}(X)+\sum{i=1}^{n}w_{i}\mathsf{L}_{i}(X) $$

$$ \mathsf{b}(X)=(b_{3}X+b_{4})\mathsf{Z}{\mathsf{H}}(X)+\sum{i=1}^{n}w_{n+i}\mathsf{L}_{i}(X) $$

$$ \mathsf{c}(X)=(b_{5}X+b_{6})\mathsf{Z}{\mathsf{H}}(X)+\sum{i=1}^{n}w_{2n+i}\mathsf{L}_{i}(X) $$

Compute $ [a]{1} := \mathsf{a}(x)\cdot[1]{1},[b]{1}:=\mathsf{b}(x)\cdot[1]{1},[c]{1}:=\mathsf{c}(x)\cdot[1]{1} $

$$ [a]{1}:=\mathtt{a}(x)\cdot[1]{1},[b]{1}:=\mathtt{b}(x)\cdot[1]{1},[c]{1}:=\mathtt{c}(x)\cdot[1]{1} $$

First output of Psnark() is ((w_i)_i2[‘]; [a]₁; [b]₁; [c]₁)

$$ \left((w_{i}){i\in[\ell]},[a]{1},[b]{1},[c]{1}\right) $$

$$ \mathcal{P s n a r k}(\lambda) $$

Compute permutation challenges (;) 2 F_p:

$$ (\beta,\gamma)\in\mathbb{F}_{p} $$

$$ \beta=H([a]{1},[b]{1},[c]{1},(w{i}){i\in[\ell]}),\gamma=H([a]{1},[b]{1},[c]{1},(w_{i})_{i\in\ell},\beta) $$

Compute permutation polynomial z(X) :

$$ \begin{array}{c}{\mathsf{z}(X)=(b_{7}X^{2}+b_{8}X+b_{9})Z mathsf{z}{\mathsf{H}}(X)}\ {+\mathsf{L}{1}(X)+\sum_{i=1}^{n-1}\left(\mathsf{L}{i+1}(X)\prod{j=1}^{d}\frac{(w_{j}+\beta\omega^{j-1}+\gamma)(w_{n+j}+\beta)w_{2n+j}+\beta k_{2}\omega^{j-1}+\gamma)}{(w_{j}+\sigma(j)\beta+\gamma)(w_{n+j}+\sigma(n+j)\beta+\gamma)(w_{2n+j}+\sigma(2n+j)\beta+\gamma)}\right)}\ \end{array} $$

Compute [z]₁:= z(x) [1]₁

$$ [z]{1}:=\mathsf{z}(x)\cdot[1]{1} $$

Second output of Psnark() is ([z]₁)

Compute quotient challenge 2 F_p:

$$ \alpha\in\mathbb{F}_{p} $$

$$ \alpha=H([a]{1},[b]{1},[c]{1},[z]{1}) $$

Compute quotient polynomial t(X) :

$$ \begin{array}{l} \mathrm {t} (X) = \ (\mathrm {a} (X) \mathrm {b} (X) \mathrm {q} _ {\mathrm {M}} (X) + \mathrm {a} (X) \mathrm {q} _ {\mathrm {L}} (X) + \mathrm {b} (X) \mathrm {q} _ {\mathrm {R}} (X) + \mathrm {c} (X) \mathrm {q} _ {\mathrm {O}} (X) + \mathrm {P I} (X) + \mathrm {q} _ {\mathrm {C}} (X)) \frac {\alpha}{\mathrm {Z} _ {\mathrm {H}} (X)} \ + \left(\left(a (X) + \beta X + \gamma\right) \left(b (X) + \beta k _ {1} X + \gamma\right) \left(c (X) + \beta k _ {2} X + \gamma\right) z (X)\right) \frac {\alpha^ {2}}{Z _ {\mathrm {H}} (X)} \ - \left(\left(a (X) + \beta S _ {\sigma 1} (X) + \gamma\right) \left(b (X) + \beta S _ {\sigma 2} (X) + \gamma\right) \left(c (X) + \beta S _ {\sigma 3} (X) + \gamma\right) z (X \omega)\right) \frac {\alpha^ {2}}{Z _ {\mathrm {H}} (X)} \ + \left(z (X) - 1\right) \mathrm {L} _ {1} (X) \frac {\alpha^ {3}}{Z _ {\mathrm {H}} (X)} \ \end{array} $$

Split t(X) into degree-n polynomials t_lo(X);t_mid(X);t_hi(X), where

$$ t_{l o}(X),t_{m i d}(X),t_{h i}(X) $$

$$ t(X)=t_{l o}(X)+X^{n}t_{m i d}(X)+X^{2n}t_{h i}(X) $$

$$ \operatorname {C o m p u t e} \left[ t _ {l o} \right] _ {1}: = \mathrm {t} _ {\mathrm {l o}} (x) \cdot [ 1 ] _ {1}, \left[ t _ {m i d} \right] _ {1}: = \mathrm {t} _ {\mathrm {m i d}} (x) \cdot [ 1 ] _ {1}, \left[ t _ {h i} \right] _ {1}: = \mathrm {t} _ {\mathrm {h i}} (x) \cdot [ 1 ] _ {1} $$

Third output of Psnark() is ([t_lo]₁; [t_mid]₁; [t_hi]₁)

$$ ([t_{l o}]{1},[t{m i d}]{1},[t{h i}]_{1}) $$

Compute evaluation challenge z 2 F_p:

$$ z\in\mathbb{F}_{p} $$

$$ z=H([a]{1},[b]{1},[c]{1},[z]{1},[t_{l o}]{1},[t{m i d}]{1},[t{h i}]_{1}) $$

Compute opening evaluations:

$$ \begin{array}{c}{\bar{a}=\mathsf{a}(z),\bar{b}=\mathsf{b}(z),\bar{c}=\mathsf{c}(z),\bar{\mathsf{s}}{\sigma1}=\mathsf{S}{\sigma1}(z),\bar{\mathsf{s}}{\sigma2}=\mathsf{S}{\sigma2}(z),}\ {\bar{t}=\mathsf{t}(z),\bar{z}=\mathsf{z}(z\omega)}\end{array} $$

Compute linearisation polynomial r(X) :

$$ r(X) $$

$$ \begin{array}{l}{\mathsf{r}(X)=}\ {\quad\left(\bar{a}\bar{b}\cdot\mathsf{q}{\mathsf{M}}(X)+\bar{a}\cdot\mathsf{q}{\mathsf{M}}(X)+\bar{b}\cdot\mathsf{q}{\mathsf{R}}(X)+\bar{c}\cdot\mathsf{q}{\mathsf{O}}(X)+\mathsf{q}{\mathsf{C}}(X)\right)\alpha}\ {\quad+\left((\bar{a}+\beta z+\gamma)(\bar{b}+\beta k{1}z+\gamma)(\bar{c}+\beta k_{2}z+\gamma)\cdot\mathsf{z}(X)\right)\alpha^{2}}\ {\quad-\left((\bar{a}+\beta\mathsf{z}{\sigma1}+\gamma)(\bar{b}+\beta\mathsf{z}{\sigma2}+\gamma)\beta\mathsf{z}(z\omega)\cdot\mathsf{S}{\sigma3}(X)\right)\alpha^{2}}\ {\quad+(\mathsf{z}(X))\mathsf{l}{1}(z)\alpha^{3}}\ \end{array} $$

Compute linearisation evaluation r = r(z)

$$ \bar{r}=\ \ {pm{pm\ }}(z) $$

Fourth output of Psnark() is (a; b; c;s₁; s₂; z; t; r)

$$ \left(\bar{a},\bar{b},\bar{c},\bar{\mathsf{s}}{\sigma1},\bar{\mathsf{s}}{\sigma2},\bar{z},\bar{t},\bar{r}\right) $$

$$ vboldsymbol\in\mathbb{F}_{p} $$

Compute opening challenge v 2 F_p:

$$ v = H \left([ a ] _ {1}, [ b ] _ {1}, [ c ] _ {1}, [ z ] _ {1}, [ t ] _ {1}, \bar {a}, \bar {b}, \bar {c}, \bar {\mathbf {s}} _ {\sigma 1}, \bar {\mathbf {s}} _ {\sigma 2}, \bar {z}, \bar {t}, \bar {r}\right) $$

$$ \ {mathbb W}_{\mathsf{z}}(X) $$

Compute opening polynomial W_z(X) : 0

$$ \mathrm {W} _ {\mathrm {z}} (X) = \frac {1}{X - z} \left( \begin{array}{l} \left(\mathrm {t} _ {\mathrm {l o}} (X) + z ^ {n} \mathrm {t} _ {\mathrm {m i d}} (X) + z ^ {2 n} \mathrm {t} _ {\mathrm {h i}} (X) - \bar {t}\right) \ + v (\mathrm {r} (X) - \bar {r}) \ + v ^ {2} (\mathrm {a} (X) - \bar {a}) \ + v ^ {3} (\mathrm {b} (X) - \bar {b}) \ + v ^ {4} (\mathrm {c} (X) - \bar {c}) \ + v ^ {5} \left(\mathrm {S} _ {\sigma 1} (X) - \bar {\mathrm {s}} _ {\sigma 1}\right) \ + v ^ {6} \left(\mathrm {S} _ {\sigma 2} (X) - \bar {\mathrm {s}} _ {\sigma 2}\right) \end{array} \right) $$

Compute opening polynomial W_z!(X) :

$$ \mathsf{W}_{\mathsf{z}\omega}(X) $$

$$ \mathsf{W}_{\mathsf{z}\omega}(X)=\frac{v^{7}(\mathsf{z}(X)-\bar{z})}{X-z\omega} $$

Compute [W_z]₁:= W_z(x) [1]₁; [W_z!]₁:= W_z!(x) [1]₁

$$ [ W _ {z} ] _ {1} := \mathrm {W} _ {\mathrm {z}} (x) \cdot [ 1 ] _ {1}, [ W _ {z \omega} ] _ {1} := \mathrm {W} _ {\mathrm {z} \omega} (x) \cdot [ 1 ] _ {1} $$

Fifth output of Psnark() is ([W_z]₁; [W_z!]₁)

$$ ([W_{z}]{1},[W{z\omega}]_{1}) $$

Return

$$ \pi_ {\mathrm {S N A R K}} = \left( \begin{array}{c} [ a ] _ {1}, [ b ] _ {1}, [ c ] _ {1}, [ z ] _ {1}, [ t _ {l o} ] _ {1}, [ t _ {m i d} ] _ {1}, [ t _ {h i} ] _ {1}, [ W _ {z} ] _ {1}, [ W _ {z \omega} ] _ {1}, \ \bar {a}, \bar {b}, \bar {c}, \bar {\mathbf {s}} _ {\sigma 1}, \bar {\mathbf {s}} _ {\sigma 2}, \bar {r}, \bar {z} \end{array} \right) $$

Vsnark()((w_i)_i2[‘];_SNARK): Validate ([a]; [b]; [c];

$$ (\lambda)\big((w_{i}){i\in[\ell]},\pi{\sf{S N A R K}}\big) $$

$$ \left([ a ] _ {1}, [ b ] _ {1}, [ c ] _ {1}, [ z ] _ {1}, \left[ t _ {l o} \right] _ {1}, \left[ t _ {m i d} \right] _ {1}, \left[ t _ {h i} \right] _ {1}, \left[ W _ {z} \right] _ {1}, \left[ W _ {z \omega} \right] _ {1}\right) \in \mathbb {G} _ {1} $$

$$ (\bar{}\ \bar{a},\bar{b},\bar{c},\bar{\mathsf{s}}{\sigma1},\bar{\mathsf{s}}{\sigma2},\bar{r},\bar{z})\in\mathbb{F}_{p}^{7} $$

Validate (a; b; c;s₁; s₂; r; z) 2 F⁷_p

‘p Validate (w_i)_i2[‘]2 F

$$ (w_{i}){i\in[\ell]}\in\mathbb{F}{p}^{\ell} $$

Compute permutation challenges (;) 2 F_p:

$$ (\beta,\gamma)\in\mathbb{F}_{p} $$

$$ \beta=H([a]{1},[b]{1},[c]{1},(w{i}){i\in[\ell]}),\gamma=H([a]{1},[b]{1},[c]{1},(w_{i})_{i\in[\ell]},\beta) $$

$$ \boldsymbol{\alpha}\in\mathbb{F}_{p} $$

Compute quotient challenge 2 F_p:

$$ \alpha=H([a]{1},[b]{1},[c]{1},[z]{1}) $$

Compute evaluation challenge z 2 F_p:

$$ z\in\mathbb{F}_{p} $$

$$ z = H \left([ a ] _ {1}, [ b ] _ {1}, [ c ] _ {1}, [ z ] _ {1}, \left[ t _ {l o} \right] _ {1}, \left[ t _ {m i d} \right] _ {1}, \left[ t _ {h i} \right] _ {1}\right) $$

n Compute zero polynomial evaluation Z^H(z) = z 1

$$ \mathsf{Z}_{\mathsf{H}}(z)=z^{n}-1 $$

zn1 Compute Lagrange polynomial evaluation L₁(z) = ⁿ(^zP¹)

$$ \mathsf{L}_{1}(z)=\frac{z^{n}-1}{n(z-1)} $$

Compute public input polynomial evaluation PI(z) = w_iL_i(z) i2‘

$$ \mathsf{P I}(z)=\sum_{i\in\ell}w_{i}\mathsf{L}_{i}(z) $$

Compute quotient polynomial evaluation

$$ \bar{t}=\frac{\bar{r}+\mathsf{P I}(z)\alpha-((\bar{a}+\beta\mathtt{S}{\sigma1}+\gamma)(\bar{b}+\beta\mathtt{S}{\sigma2}+\gamma)(\bar{c}+\gamma)\bar{z})\alpha^{2}-\mathsf{L}_{1}(z)\alpha^{3}}{\mathtt{Z u}(z)} $$

Compute opening challenge v 2 F_p:

$$ \boldsymbol{v{}\ in\mathbb{{}F}_{p} $$

$$ v = H \left([ a ] _ {1}, [ b ] _ {1}, [ c ] _ {1}, [ z ] _ {1}, [ t _ {l o} ] _ {1}, [ t _ {m i d} ] _ {1}, [ t _ {h i} ] _ {1}, \bar {a}, \bar {b}, \bar {c}, \bar {\mathbf {s}} _ {\sigma 1}, \bar {\mathbf {s}} _ {\sigma 2}, \bar {z}, \bar {t}, \bar {r}\right) $$

Compute multipoint evaluation separation challenge u 2 F_p:

$$ \boldsymbol{u{}\ in\mathbb{{}F}_{p} $$

$$ u H[[[]]{1},[b]{1},[c]{1},[z]{1},[t_{l o}]{1},[t{m i d}]{1},[t{h i}]{1},[W{z}]{1},[W{z\omega^{-1}}]{1},\bar{a},\bar{b},\bar{c},\bar{\mathsf{s}}{\sigma1},\bar{\mathsf{s}}_{\sigma2},\bar{z},\bar{t},\bar{r}) $$

Compute partial opening commitment [D]₁:= v [r]₁+ v⁷u [z₁]₁:

$$ [D]{1}:=v\cdot[r]{1}+v^{7}u\cdot[z_{1}]_{1} $$

$$ [D]{1}:=\begin{array}{l}{\bar{a}\bar{b}\alpha v\cdot[q{\mathsf{R}}]{1}+\bar{a}\alpha v\cdot[q{\mathsf{R}}]{1}+\bar{b}\alpha v\cdot[q{\mathsf{R}}]{1}+\bar{c}\alpha v\cdot[q{\mathsf{Q}}]{1}+\alpha v\cdot[q{\mathsf{C}}]{1}}\ {+\big((\bar{a}+\beta z+\gamma)(\bar{b}+\beta k{1}z+\gamma)(\bar{c}+\beta k_{2}z+\gamma)\alpha^{2}v+\mathsf{L}{1}(z)\alpha^{4}v+v^{7}u\big)\cdot[z]{1}}\ \end{array} $$

Compute batch opening commitment [F]₁:

$$ [F]_{1} $$

$$ [F]{1}:=\begin{array}{l}{[t{l o}]{1}+z^{n}\cdot[t{m i d}]{1}+z^{2n}\cdot[t{h i}]{1}}\ {+[D]{1}+v^{2}\cdot[a]{1}+v^{3}\cdot[b]{1}+v^{4}\cdot[c]{1}+v^{5}\cdot[s{\sigma1}]{1}+v^{6}\cdot[s{\sigma2}]_{1}}\ \end{array} $$

Compute batch evaluation commitment [E]₁:

$$ [E]{1}:=\left(\begin{array}{l}{\bar{t}{l o}+z^{n}\bar{t}{m i d}+z^{2n}\bar{t}{h i}+v\bar{r}+v^{2}\bar{a}+v^{3}\bar{b}+v^{4}\bar{c}}\ {+v^{5}\bar{\mathsf{s}}{\sigma1}+v^{6}\bar{\mathsf{s}}{\sigma2}+v^{7}u\bar{z_{1}}}\ \end{array}\right)\cdot[1]_{1} $$

Validate

$$ e([W_{z}]{1}+u\cdot[W{z\omega}]{1},x\cdot[1]{2})\stackrel{?}{=}e(z\cdot[W_{z}]{1}+u z\omega\cdot[W{z\omega}]{1}+[F]{1}-[E]{1},[1]{2}) $$

Acknowledgements

We thank Mary Maller for telling us about the eld element reduction method discussed in the end of Section 4. We thank Vitalik Buterin for suggesting that we dene the identity permutation using degree-1 polynomials, which reduces proof construction time, as well as reducing the proof size by 1 eld element, and reduces the verication costs by 1 scalar multiplication. We thank Swastik Kopparty for pointing out an error in the permutation argument in a previous version of the paper, whose correction led to improved performance. We also thank Justin Drake and Konstantin Panarin for discussions leading to corrections and simplications of the permutation argument.

References

⁺ [BCC 16]J. Bootle, A. Cerulli, P. Chaidos, J. Groth, and C. Petit. Ecient zeroknowledge arguments for arithmetic circuits in the discrete log setting. pages 327{357, 2016. ⁺ [BCR 19]E. Ben-Sasson, A. Chiesa, M. Riabzev, N. Spooner, M. Virza, and N. P. Ward. Aurora: Transparent succinct arguments for R1CS. In Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19-23, 2019, Proceedings, Part I, pages 103{128, 2019. [BG12]S. Bayer and J. Groth. Ecient zero-knowledge argument for correctness of a shue. In Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, pages 263{280, 2012. [BGM17]S. Bowe, A. Gabizon, and I. Miers. Scalable multi-party computation for zksnark parameters in the random beacon model. Cryptology ePrint Archive, Report 2017/1050, 2017. https://eprint.iacr.org/2017/1050. ⁺ [CHM 19]A. Chiesa, Y. Hu, M. Maller, P. Mishra, N. Vesely, and N. P. Ward. Marlin: Preprocessing zksnarks with universal and updatable SRS. IACR Cryptology ePrint Archive, 2019:1047, 2019. [COS19]A. Chiesa, D. Ojha, and N. Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. IACR Cryptology ePrint Archive, 2019:1076, 2019. [CS10]C. Costello and D. Stebila. Fixed argument pairings. In International Con- ference on Cryptology and Information Security in Latin America, pages 92{108. Springer, 2010. [FKL18]G. Fuchsbauer, E. Kiltz, and J. Loss. The algebraic group model and its applications. In Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19- 23, 2018, Proceedings, Part II, pages 33{62, 2018. [Gab19]A. Gabizon. Auroralight:improved prover eciency and SRS size in a soniclike system. IACR Cryptology ePrint Archive, 2019:601, 2019. [GGPR13]R. Gennaro, C. Gentry, B. Parno, and M. Raykova. Quadratic span programs and succinct nizks without pcps. In Advances in Cryptology - EU- ROCRYPT 2013, 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings, pages 626{645, 2013.

⁺ [GKM]J. Groth, M. Kohlweiss, M. Maller, S. Meiklejohn, and I. Miers. Updatable and universal common reference strings with applications to zk-snarks. IACR Cryptology ePrint Archive, 2018. [Gro16]J. Groth. On the size of pairing-based non-interactive arguments. In Ad- vances in Cryptology-EUROCRYPT 2016-35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, pages 305{326, 2016. [KZG10]A. Kate, G. M. Zaverucha, and I. Goldberg. Constant-size commitments to polynomials and their applications. pages 177{194, 2010. [MBKM19]M. Maller, S. Bowe, M. Kohlweiss, and S. Meiklejohn. Sonic: Zeroknowledge snarks from linear-size universal and updateable structured reference strings. IACR Cryptology ePrint Archive, 2019:99, 2019.

A Claims for permutation argument:

Fix a permutation of [n], and a₁;:::;a_n;b₁;:::;b_n2 F.

$$ \sigma $$

$$ [n] $$

$$ a_{1},\ldots,a_{n},b_{1},\ldots,b_{n}\in\mathbb{F} $$

Claim A.1. If the following holds with non-negligible probability over random ; 2 F Y Y

$$ \beta,\gamma\in\mathbb{F} $$

$$ \prod_{i\in[n]}(a_{i}+\beta\cdot i+\gamma)=\prod_{i\in[n]}(b_{i}+\beta\cdot\sigma(i)+\gamma) $$

then 8i 2 [n], b_i= a_(i).

$$ \forall i\in[n],,b_{i}=a_{\sigma(i)} $$

We will prove claim A.1 using the following lemmas. For completeness, we include below a variant of the well-known Schwartz-Zippel lemma that we use in this paper.

Lemma A.2. (Schwartz-Zippel). Let P(X₁;:::;X_n) be a non-zero multivariate polyno- mial of degree d over Z_p, then the probability of P(₁;:::;_n) = 0 Z_pfor randomly chosen₁;:::;_nis at most d=p.

$$ P(X_{1},\ldots,X_{n}) $$

$$ \mathbb{Z}_{p} $$

$$ P(\alpha_{1},\ldots,\alpha_{n})=0\leftarrow\mathbb{Z}_{p} $$

$$ \alpha_{1},\ldots,\alpha_{n} $$

$$ d/p $$

The Schwartz-Zippel lemma is used in polynomial equality testing. Given two multivariate polynomials P₁(X₁;:::;X_n) and P₂(X₁;:::;X_n) we can test whether P₁(₁;:::;_n) P₂(₁;:::;_n) = 0 for random₁;:::;_nZ_p. If the two polynomials are identical, this will always be true, whereas if the two polynomials are dierent then the equality holds with probability at most max(d₁;d₂)=p, where d₁ and d₂ are the degrees of the polynomials P₁ and P₂.

$$ P_{1}(X_{1},\ldots,X_{n}) $$

$$ P_{2}(X_{1},\ldots,X_{n}) $$

$$ P_{1}(\alpha_{1},\ldots,\alpha_{n})- $$

$$ P_{2}(\alpha_{1},\ldots,\alpha_{n})=0 $$

$$ \alpha_{1},\ldots,\alpha_{n}\leftarrow\mathbb{Z}_{p} $$

$$ (d_{1},d_{2})/p $$

$$ d_{1} $$

$$ P_{1} $$

$$ d_{2} $$

$$ P_{2} $$

Lemma A.3. If the following holds with non-negligible probability over random 2 F*,*

$$ \gamma\in\mathbb{F} $$

$$ \prod_{i=1}^{n}(a_{i}+\gamma)=\prod_{i=1}^{n}(b_{i}+\gamma) $$

(1)

then the entries in the tuple (a₁;:::;a_n) equal the entries in the tuple (b₁;:::;b_n), but not necessarily in that order.

$$ (a_{1},\ldots,a_{n}) $$

$$ (b_{1},\ldots,b_{n}) $$

Q Q n n Proof. Let P^a(X) = (X + aⁱ) and Pb(X) = (X + bⁱ). The roots of Paare ⁱ=1 i=1 ( a₁;:::; a_n) and the roots of P^bare ( b₁;:::; b_n). By the Schwartz-Zippel lemma, if polynomials P^a(X) and Pb(X) are not equal, equality 1 holds with probability ^jnFj which is negligible for any polynomial degree n used in our snark construction. Thus, equality 1 holds with non-negligible probability only when the two polynomials P_a(X) and P_b(X) are equal. This implies all the roots of P_a(X) must be roots of P_b(X) and the other way around, which, in turn, implies the conclusion of the lemma. As a note, the conclusion of the lemma can be written in an equivalent but more formal way: there exist a permutation of [n] such that b_i= a_(i); 8i 2 [n].

$$ \textstyle{P_{a}(X)=\prod_{i=1}^{n}(X+a_{i})} $$

$$ \textstyle P_{b}(X)=\prod_{i=1}^{n}\bigl(X+b_{i}\bigr) $$

$$ P_{a} $$

$$ (-a_{1},\ldots,-a_{n}) $$

$$ (-b_{1},\ldots,-b_{n}) $$

$$ P_{b} $$

$$ P_{a}(X) $$

$$ P_{b}(X) $$

$$ \frac{n}{|\mathbb{F}|} $$

$$ P_{a}(X) $$

$$ P_{b}(X) $$

$$ P_{b}(X) $$

$$ P_{a}(X) $$

$$ b_{i}=a_{\sigma(i)},\forall i\in[n] $$

Corollary A.4. Fix a permutation of [n], and A₁;:::;A_n;B₁;:::;B_n2 F*. If the* following holds with non-negligible probability over random 2 F*,* Y Y

$$ A_{1},\ldots,A_{n},B_{1},\ldots,B_{n}\in\mathbb{F} $$

$$ \beta\in\mathbb{F} $$

$$ \prod_{i\in[n]}(A_{i}+\beta\cdot i)=\prod_{i\in[n]}(B_{i}+\beta\cdot\sigma(i)) $$

B1 Bn then the values in the tuple ₍;:::;₎ are the same as the values in the tuple (1) (n) An (A₁;:::;), but not necessarily in this order. n

$$ \textstyle\big(\frac{B_{1}}{\sigma(1)},\ldots,\frac{B_{n}}{\sigma(n)}\big) $$

$$ (A_{1},\ldots,\frac{A_{n}}{n}) $$

Q An Proof. The roots of P^A(Y) = (i Y +Aⁱ) are ( A₁;:::;), the roots of P_B(Y) = i2[n] n Q B1 Bn ( (i) Y + B_i) are ₍;:::;₎. Together with lemma A.3, we obtain the _i2[n] (1) (n) desired conclusion.

$$ \left(- A _ {1}, \dots , - \frac {A _ {n}}{n}\right) $$

$$ P_{B}(Y)= $$

$$ \textstyle{\prod_{i\in[n]}}\ !(\sigma(i)\cdot Y+B_{i}, $$

$$ \textstyle\left(-\frac{B_{1}}{\sigma(1)},\ldots,-\frac{B_{n}}{\sigma(n)}\right) $$

Proof. for Claim A.1

Lets denote by B_i= bⁱ+ and Aⁱ= aⁱ+, 8i 2 [n]. Then, according to A.4, the B1 Bn Ann values in the tuple ₍;:::;₎ are the same as the values in the tuple (A₁;:::;), (1) (_n) 8i 2 [n]. Assume there exists i₀ 2 [n] such that Bⁱ⁰6= A⁽ⁱ⁾. This implies there exists 0 Bi Aj 0 j 2 [n], with j 6= (i₀) such that =. Expending, we obtain j (b_i0+) = (i0) j (i₀) (a_j+) and this holds with non-negligible probability over the choice of. Using the Schwartz-Zippel lemma as in A.3, we obtain that (i₀) = j which contradicts our assumption. Hence, we have proven that 8i 2 [n];B_i= A_(i), which, in turn, implies b_i= a_(i), 8i 2 [n].

$$ B_{i}=b_{i}+\gamma $$

$$ A_{i}=a_{i}+\gamma,,\forall i\in[n] $$

$$ \left(\frac {B _ {1}}{\sigma (1)}, \dots , \frac {B _ {n}}{\sigma (n)}\right) $$

$$ (A_{1},\ldots,\textstyle\frac{A_{n}}{n}) $$

$$ \forall i\in[n] $$

$$ i_{0}\in[n] $$

$$ B_{i_{0}}\neq A_{\sigma(i_{0})} $$

$$ j,\in,[n] $$

$$ j\neq\sigma(i_{0}) $$

$$ \frac{B_{i_{0}}}{\sigma(i_{0})},=,\frac{A_{j}}{j} $$

$$ j\cdot(b_{i_{0}}+\gamma),= $$

$$ \sigma(i_{0})\cdot(a_{j}+\gamma) $$

$$ \gamma $$

$$ \sigma(\dot{i}_{0})=\dot{j} $$

$$ \forall i\in[n],B_{i}=A_{\sigma(i)} $$

$$ b_{i}=a_{\sigma(i)},,\forall i\in[n] $$