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

Abstract

zk-SNARK constructions that utilize an updatable universal structured reference string remove one of the main obstacles in deploying zk-SNARKs. The important work of Maller et al. [MBKM] presented Sonic — the first potentially practical zk-SNARK with fully succinct verification for general arithmetic circuits with such an SRS. However, the version of Sonic enabling fully succinct verification still requires relatively high proof construction overheads.

We present a universal SNARK construction with fully succinct verification, and significantly lower prover running time (roughly 7.5–20 times fewer group exponentiations than [MBKM] in the fully succinct verifier mode depending on circuit structure).

Similarly to [MBKM] we rely on a permutation argument based on Bayer and Groth [BG12]. However, we focus on “evaluations on a subgroup rather than coefficients 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 significant 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 satisfiability 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.
4. The verifier run time is polylogarithmic in circuit size.

Maller et al. [MBKM] constructed for the first time a universal fully succinct zk-SNARK for circuit satisfiability, called Sonic. [MBKM] also give a version of Sonic with dramatically improved prover run time, at the expense of efficient verification only in a certain amortized sense.

1.1 Our Results

In this work we give a universal fully-succinct zk-SNARK with significantly 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 [MBKM]. This is combined with a permutation argument over univariate evaluations on a multiplicative subgroup rather than over coefficients of a bivariate polynomial as in [MBKM].

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 coefficients of polynomials at “neighbouring monomials”.

We observe that if we think of the points x, g \cdot x as neighbours, where g is a generator of a multiplicative subgroup of a field \mathbb{F}, it is very convenient to check relations between different polynomials at such pairs of points.

A related convenience is that multiplicative subgroups interact well with Lagrange bases. For example, suppose H \subset \mathbb{F} is a multiplicative subgroup of order n, and x \in H. The polynomial L^x of degree n - 1 that vanishes on H \setminus \{x\} and has L^x(x) = 1, has a very sparse representation of the form

for a constant c_x. This is beneficial when constructing an efficiently verifiable [BG12]-style permutation argument in terms of polynomial identities.

1.2 Efficiency 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 [MBKM]. This protocol requires the prover compute 273n \mathbb{G}_1 group exponentiations, where n is the number of multiplication gates.

Our universal SNARK requires the prover to compute 5 polynomial commitments, combined with two opening proofs to evaluate the polynomial commitments at a random challenge point. There are two “flavours” 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 approximately 10%. The combined degree of the polynomials is either 9(n + a) (larger proofs) or 11(n + a) (smaller proofs, reduced verifier work), where n is the number of multiplication gates and a is the number of addition gates.

Currently, the most efficient 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 \mathbb{G}_1 and n \mathbb{G}_2 group exponentiations, where m is formally the number of R1CS variables, and is typically bounded by n. If we assume that one \mathbb{G}_2 exponentiation is equivalent to three \mathbb{G}_1 exponentiations, this yields 6n + m equivalent \mathbb{G}_1 group exponentiations.

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” flavour of PlonK). This is a significant reduction in the SRS size compared to the state of the art.

1.3 Performance and Benchmarks

[Figure 1 describes 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.]

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 significant advancement in the efficiency of universal SNARKs, which are now practical for a wide range of real-world use-cases.

Circuit preprocessing is a one-off computation, required for each program codified 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 field multiplications in Table 1 is obtained from 8 FFTs of size 4n, 5 FFTs of size 2n and 12 FFTs of size n.

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 difficult constraints to be compressed are linear relations between the system variables, i.e. constraints of the form \langle a_i, x \rangle = 0 where x \in \mathbb{F}^m are the system variables, and a_i \in \mathbb{F}^m represents one of the constraints.

These are analogous to the less general “wiring constraints” in a circuit satisfiability statement, which have the form x_i = x_j (e.g. when x_i represents the output wire of a gate G, and x_j an input wire from G into another gate G').

A random linear combination of linear constraints might have the form

for a uniform r \in \mathbb{F}.

Coming back to PlonK, the reason we don’t require the “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. 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”.

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. For the same value of n, PlonK outperforms Marlin by roughly a 2x factor in prover group operations and proof size.

2. Preliminaries

2.1 Terminology and Conventions

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

Whenever we use the term “efficient”, we mean an algorithm running in time \text{poly}(\lambda). Furthermore, we assume an “object generator” \mathcal{O} that is run with input \lambda before all protocols, and returns all fields and groups used. Specifically, in our protocol \mathcal{O}(\lambda) = (\mathbb{F}, \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t, e, g_1, g_2, g_t) where:

• \mathbb{F} is a prime field of super-polynomial size r = \lambda^{\omega(1)}.
• \mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_t are all groups of size r, and e is an efficiently computable non-degenerate pairing e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_t.
• g_1, g_2 are uniformly chosen generators such that e(g_1, g_2) = g_t.

We write \mathbb{G}_1 and \mathbb{G}_2 additively. We use the notations [x]_1 := x \cdot g_1 and [x]_2 := x \cdot g_2. We often denote by [n] the integers \{1, \ldots, n\}.

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 \mathcal{A} in an SRS-based protocol we mean a \text{poly}(\lambda)-time algorithm which satisfies the following: for i \in \{1, 2\}, whenever \mathcal{A} outputs an element A \in \mathbb{G}_i, it also outputs a vector v over \mathbb{F} such that A = \langle v, \text{srs}_i \rangle.

Knowledge soundness in the Algebraic Group Model: We say a protocol \mathcal{P} between a prover P and verifier V for a relation \mathcal{R} has knowledge soundness in the Algebraic Group Model if there exists an efficient E such that the probability of any algebraic adversary \mathcal{A} winning the following game is \text{negl}(\lambda):

1. \mathcal{A} chooses input x and plays the role of P in \mathcal{P} with input x.
2. E, given access to all of \mathcal{A}’s messages during the protocol (including the coefficients of the linear combinations), outputs \omega.
3. \mathcal{A} wins if V outputs \text{acc} at the end of the protocol, and (x, \omega) \notin \mathcal{R}.

3. A Batched Version of the [KZG10] Scheme

Crucial to the efficiency of our protocol is a batched version of the [KZG10] polynomial commitment scheme (PCS) similar to Appendix C of [MBKM], allowing to query multiple committed polynomials at multiple points. We begin by defining polynomial commitment schemes in a manner conducive to our protocol.

3.1 The PCS

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

1. \text{gen}(d): choose uniform x \in \mathbb{F}. Output \text{srs} = ([Bootle16]_1, [x]_1, \dots, [x^{d-1}]_1, [Bootle16]_2, [x]_2).
2. \text{com}(f, \text{srs}) := [f(x)]_1.
3. The \text{open} protocol for a single evaluation point z: V_{\text{PC}} sends random \gamma \in \mathbb{F}. P_{\text{PC}} computes the polynomial
   h(X) := \sum_{i=1}^{t} \gamma^{i-1} \cdot \frac{f_i(X) - f_i(z)}{X - z}
   and sends W := [h(x)]_1. V_{\text{PC}} outputs \text{acc} iff
   e(F - v, [Bootle16]_2) \cdot e(-W, [x - z]_2) = 1.

The open protocol for multiple evaluation points consists of running in parallel the open protocol for each evaluation point and applying a generic method for batch randomized evaluation of pairing equations.

4. Idealised Low-Degree Protocols

We define a limited type of protocol between a prover and a verifier 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 \mathcal{I}. The verifier may then ask \mathcal{I} whether certain identities hold between the prover’s polynomials, and additional predefined polynomials known to the verifier.

4.1 Polynomial Protocols on Ranges

In our protocol V_{\text{poly}} actually 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 \subset \mathbb{F}, we define an S-ranged polynomial protocol identically to a polynomial protocol, except that the verifier asks if his identities hold on all points of S, rather than identically.

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. When P_{\text{poly}} sends a polynomial f_i to \mathcal{I} in \mathscr{P}, \mathbf{P} sends \text{cm}_i = \text{com}(f_i) to \mathbf{V}.

Reducing the number of field elements: An optimization by Mary Maller reduces the number of \mathbb{F}-elements in the proof from M. The idea is to use the linearisation polynomial: instead of sending all evaluation values, the prover sends only a subset S \subset [M], and the verifier computes the commitment to the linearised polynomial F_L using the linearity of \text{com}.

5. Polynomial Protocols for Identifying Permutations

At the heart of 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, MBKM]. Our main advantage over [MBKM] is getting a simpler protocol by working with univariate polynomials and multiplicative subgroups.

We use two integer parameters n \leq d. Intuitively, n is the degree of the honest prover’s polynomials, and d is the bound we actually enforce on malicious provers.

We assume the existence of a multiplicative subgroup H \subset \mathbb{F} of order n with generator \mathbf{g}. For i \in [n], we denote by L_i(X) the element of \mathbb{F}_{< n}[X] with L_i(\mathbf{g}^i) = 1 and L_i(a) = 0 for a \in H different from \mathbf{g}^i, i.e. \{L_i\}_{i \in [n]} is a Lagrange basis for H.

For f, g \in \mathbb{F}_{< d}[X] and a permutation \sigma : [n] \to [n], we write g = \sigma(f) if for each i \in [n], g(\mathbf{g}^i) = f(\mathbf{g}^{\sigma(i)}). We present a ranged polynomial protocol enabling P_{\text{poly}} to prove that g = \sigma(f).

Preprocessed polynomials: S_{\text{ID}} \in \mathbb{F}_{< n}[X] defined by S_{\text{ID}}(\mathbf{g}^i) = i and S_\sigma \in \mathbb{F}_{< n}[X] defined by S_\sigma(\mathbf{g}^i) = \sigma(i).

Protocol:

1. V_{\text{poly}} chooses random \beta, \gamma \in \mathbb{F} and sends them to P_{\text{poly}}.
2. Let f' := f + \beta \cdot S_{\text{ID}} + \gamma, g' := g + \beta \cdot S_\sigma + \gamma.
3. P_{\text{poly}} computes Z \in \mathbb{F}_{< n}[X] such that Z(\mathbf{g}) = 1; and for i \in \{2, \dots, n\}:
   Z(\mathbf{g}^i) = \prod_{1 \leq j < i} f'(\mathbf{g}^j) / g'(\mathbf{g}^j).
4. P_{\text{poly}} sends Z to \mathcal{I}.
5. V_{\text{poly}} checks if for all a \in H: (a) L_1(a)(Z(a) - 1) = 0, and (b) Z(a)f'(a) = g'(a)Z(a \cdot \mathbf{g}).

5.1 Checking “Extended” Permutations

In our protocol, we in fact need to check a permutation “across” the values of several polynomials. Suppose we now have multiple polynomials f_1, \ldots, f_k \in \mathbb{F}_{< d}[X] and a permutation \sigma : [kn] \to [kn]. For (g_1, \ldots, g_k) \in (\mathbb{F}_{< d}[X])^k, we say that (g_1, \ldots, g_k) = \sigma(f_1, \ldots, f_k) if the corresponding sequences satisfy g_{(\ell)} = f_{(\sigma(\ell))} for each \ell \in [kn].

The protocol for extended permutations uses the same structure as the basic protocol, but with products across all k polynomials:

5.2 Checking “Extended Copy Constraints” Using a Permutation

Let \mathcal{T} = \{T_1, \ldots, T_s\} be a partition of [kn] into disjoint blocks. Fix f_1, \ldots, f_k \in \mathbb{F}_{< n}[X]. We say that f_1, \ldots, f_k copy-satisfy \mathcal{T} if f_{(\ell)} = f_{(\ell')} whenever \ell, \ell' belong to the same block of \mathcal{T}.

The above protocol for extended permutations can be directly used for checking whether f_1, \ldots, f_k satisfy \mathcal{T}: define a permutation \sigma(\mathcal{T}) on [kn] such that for each block T_i, \sigma(\mathcal{T}) contains a cycle going over all elements of T_i. Then, (f_1, \ldots, f_k) copy-satisfy \mathcal{T} if and only if (f_1, \ldots, f_k) = \sigma(f_1, \ldots, f_k).

6. Constraint Systems

Fix positive integers m and n. 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.

Arithmetic circuits: A fan-in 2 circuit of n gates can be captured: set a_i, b_i, c_i to be the indices of left/right/output wires of the i’th gate. For multiplication gates, set (q_M)_i = 1, (q_O)_i = -1, others zero. For addition gates, set (q_L)_i = 1, (q_R)_i = 1, (q_O)_i = -1, others zero.

Booleanity constraints: To enforce x_j \in \{0, 1\}, set a_i = b_i = j, (q_L)_i = -1, (q_M)_i = 1, others zero.

Enforcing constants: To enforce x_j = a, set (q_L)_i = 1, (q_C)_i = -a, others zero.

7. Main Protocol

Let \mathscr{C} = (V, Q) be a constraint system of the form described in Section 6. We present our main protocol for the relation \mathcal{R}_{\mathscr{C}}. Define the partition of \mathscr{C}, denoted \mathcal{T}_{\mathscr{C}}, as follows: suppose V = (a, b, c); think of V as a vector in [m]^{3n}. For i \in [m], let T_i \subset [3n] be the set of indices j with V_j = i. Now define \mathcal{T}_{\mathscr{C}} := \{T_i\}_{i \in [m]}.

Preprocessing: Let \sigma = \sigma(\mathcal{T}_{\mathscr{C}}). The polynomials S_{\text{ID}1}, S_{\text{ID}2}, S_{\text{ID}3}, S_{\sigma 1}, S_{\sigma 2}, S_{\sigma 3} as defined in subsection 5.1. Also, the selector polynomials q_L, q_R, q_O, q_M, q_C \in \mathbb{F}_{< n}[X].

Protocol:

1. P_{\text{poly}} computes the three polynomials f_L, f_R, f_O \in \mathbb{F}_{< n}[X], where for i \in [n]: f_L(\mathbf{g}^i) = x_{a_i}, f_R(\mathbf{g}^i) = x_{b_i}, f_O(\mathbf{g}^i) = x_{c_i}. Sends f_L, f_R, f_O to \mathcal{I}.
2. Run the extended permutation check between (f_L, f_R, f_O) and itself using \sigma. This checks whether (f_L, f_R, f_O) copy-satisfies \mathcal{T}_{\mathscr{C}}.
3. V_{\text{poly}} computes the public input polynomial \text{PI}(X) := \sum_{i \in [\ell]} -x_i \cdot L_i(X).
4. V_{\text{poly}} checks the identity on H:
   q_L \cdot f_L + q_R \cdot f_R + q_O \cdot f_O + q_M \cdot f_L \cdot f_R + (q_C + \text{PI}) = 0.

8. The Final Protocol, Rolled Out

For the reader’s convenience we present the full final protocol. A few preliminary notes:

• Zero-knowledge: Adding zero-knowledge is implemented by adding random multiples of Z_H to the prover polynomials, and requiring the verifier to send challenges in \mathbb{F} \setminus H.
• Multiplicative subgroup: We explicitly define H as containing the n’th roots of unity in \mathbb{F}, where \omega is a primitive n’th root of unity and generator of H, i.e. H = \{1, \omega, \dots, \omega^{n-1}\}.
• Identity permutation optimization: An optimization by Vitalik Buterin represents the identity permutation via degree-1 polynomials, reducing proof size by one field element.
• Non-interactive via Fiat-Shamir: We use \mathcal{H} to refer to an efficiently computable hash function for obtaining a non-interactive version of our protocol.

8.1 Polynomials that Define a Specific Circuit

The following polynomials, along with integer n, uniquely define our circuit:

• q_M(X), q_L(X), q_R(X), q_O(X), q_C(X): the selector polynomials that define the circuit’s arithmetisation.
• S_{\text{ID}1}(X) = X, S_{\text{ID}2}(X) = k_1 X, S_{\text{ID}3}(X) = k_2 X: the identity permutation applied to a, b, c. k_1, k_2 \in \mathbb{F} are chosen such that H, k_1 \cdot H, k_2 \cdot H are distinct cosets of H.
• S_{\sigma 1}(X), S_{\sigma 2}(X), S_{\sigma 3}(X): the three permutation polynomials encoding \sigma^*.

8.2 The SNARK Proof Relation

Given \ell \leq n and fixed values for the above polynomials, we wish to prove statements of knowledge for the relation \mathcal{R} \subset \mathbb{F}^\ell \times \mathbb{F}^{3n - \ell} containing all pairs x = (w_i)_{i \in [\ell]}, w = (w_i)_{i = \ell+1}^{3n} such that:

1. For all i \in [n]:
   q_{Mi} w_i w_{n+i} + q_{Li} w_i + q_{Ri} w_{n+i} + q_{Oi} w_{2n+i} + q_{Ci} = 0.
2. For all i \in [3n]: w_i = w_{\sigma(i)}.

8.3 The Protocol

The protocol is described as a non-interactive protocol using the Fiat-Shamir heuristic. We always denote by \text{transcript} the concatenation of the common preprocessed input, public input, and proof elements written by the prover up to a certain point.

Round 1

Generate random blinding scalars (b_1, \ldots, b_9) \in \mathbb{F}. Compute wire polynomials:

Compute [a]_1 := [a(x)]_1, [b]_1 := [b(x)]_1, [c]_1 := [c(x)]_1. First output of P is ([a]_1, [b]_1, [c]_1).

Round 2

Compute permutation challenges \beta = \mathcal{H}(\text{transcript}, 0), \gamma = \mathcal{H}(\text{transcript}, 1). Compute the permutation polynomial z(X) using blinding scalars (b_7, b_8, b_9) and the accumulated product of the ratios of the wire values shifted by the permutation challenges. Second output of P is ([z]_1).

Round 3

Compute quotient challenge \alpha = \mathcal{H}(\text{transcript}). Compute quotient polynomial t(X) which encodes all constraints divided by Z_H(X):

Split t(X) into degree < n polynomials t_{\text{lo}}(X), t_{\text{mid}}(X), t_{\text{hi}}(X) such that t(X) = t_{\text{lo}}(X) + X^n t_{\text{mid}}(X) + X^{2n} t_{\text{hi}}(X). Third output of P is ([t_{\text{lo}}]_1, [t_{\text{mid}}]_1, [t_{\text{hi}}]_1).

Round 4

Compute evaluation challenge \mathfrak{z} = \mathcal{H}(\text{transcript}). Compute opening evaluations:

Fourth output of P is (\bar{a}, \bar{b}, \bar{c}, \bar{s}_{\sigma 1}, \bar{s}_{\sigma 2}, \bar{z}_\omega).

Round 5

Compute opening challenge v = \mathcal{H}(\text{transcript}). Compute linearisation polynomial r(X) and opening proof polynomials W_{\mathfrak{z}}(X) and W_{\mathfrak{z}\omega}(X).

The final output is:

Compute multipoint evaluation challenge u = \mathcal{H}(\text{transcript}).

Verifier Algorithm

The verifier algorithm proceeds as follows:

1. Validate all \mathbb{G}_1 elements and field elements.
2. Compute challenges \beta, \gamma, \alpha, \mathfrak{z}, v, u \in \mathbb{F}.
3. Compute zero polynomial evaluation Z_H(\mathfrak{z}) = \mathfrak{z}^n - 1.
4. Compute Lagrange polynomial evaluation L_1(\mathfrak{z}) = \frac{\omega(\mathfrak{z}^n - 1)}{n(\mathfrak{z} - \omega)}.
5. Compute public input polynomial evaluation \text{PI}(\mathfrak{z}).
6. Compute r’s constant term r_0 and the non-constant part r'(X) := r(X) - r_0.
7. Compute first part of batched polynomial commitment [D]_1 incorporating the linearisation.
8. Compute full batched polynomial commitment [F]_1:
   [F]_1 := [D]_1 + v \cdot [a]_1 + v^2 \cdot [b]_1 + v^3 \cdot [c]_1 + v^4 \cdot [s_{\sigma 1}]_1 + v^5 \cdot [s_{\sigma 2}]_1
9. Compute group-encoded batch evaluation [E]_1.
10. Batch validate all evaluations via a single pairing check:
    e([W_{\mathfrak{z}}]_1 + u \cdot [W_{\mathfrak{z}\omega}]_1, [x]_2) \stackrel{?}{=} e(\mathfrak{z} \cdot [W_{\mathfrak{z}}]_1 + u\mathfrak{z}\omega \cdot [W_{\mathfrak{z}\omega}]_1 + [F]_1 - [E]_1, [Bootle16]_2)

Acknowledgements

The authors thank Mary Maller for the field element reduction method (end of Section 4), Vitalik Buterin for suggesting the identity permutation be defined using degree-1 polynomials, Swastik Kopparty for pointing out an error in the permutation argument whose correction led to improved performance, and Justin Drake and Konstantin Panarin for discussions leading to corrections and simplifications. They also thank Sean Bowe for noticing the public inputs were not being hashed in the original Fiat-Shamir description, along with many other contributors for comments and corrections.

References

• [BCC+16] Bootle, Cerulli, Chaidos, Groth, Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. pp. 327–357, 2016.
• [BCR+19] Ben-Sasson, Chiesa, Riabzev, Spooner, Virza, Ward. Aurora: Transparent succinct arguments for R1CS. EUROCRYPT 2019, Part I, pp. 103–128.
• [BDFG20] Boneh, Drake, Fisch, Gabizon. Halo infinite: Recursive zksnarks from any additive polynomial commitment scheme. IACR Cryptol. ePrint Arch., 2020/1536.
• [BG12] Bayer, Groth. Efficient zero-knowledge argument for correctness of a shuffle. EUROCRYPT 2012, pp. 263–280.
• [BGM17] Bowe, Gabizon, Miers. Scalable multi-party computation for zksnark parameters in the random beacon model. eprint 2017/1050. [page on this site]
• [CHM+19] Chiesa, Hu, Maller, Mishra, Vesely, Ward. Marlin: Preprocessing zksnarks with universal and updatable SRS. IACR ePrint 2019:1047.
• [COS19] Chiesa, Ojha, Spooner. Fractal: Post-quantum and transparent recursive proofs from holography. IACR ePrint 2019:1076.
• [CS10] Costello, Stebila. Fixed argument pairings. LATINCRYPT 2010, pp. 92–108.
• [FKL18] Fuchsbauer, Kiltz, Loss. The algebraic group model and its applications. CRYPTO 2018, Part II, pp. 33–62.
• [Gab19] Gabizon. Auroralight: improved prover efficiency and SRS size in a sonic-like system. IACR ePrint 2019:601. [page on this site]
• [GGPR13] Gennaro, Gentry, Parno, Raykova. Quadratic span programs and succinct nizks without pcps. EUROCRYPT 2013, pp. 626–645.
• [GKM+] Groth, Kohlweiss, Maller, Meiklejohn, Miers. Updatable and universal common reference strings with applications to zk-snarks. IACR ePrint 2018.
• [Gro16] Groth. On the size of pairing-based non-interactive arguments. EUROCRYPT 2016, Part II, pp. 305–326.
• [KZG10] Kate, Zaverucha, Goldberg. Constant-size commitments to polynomials and their applications. pp. 177–194, 2010.
• [MBKM] Maller, Bowe, Kohlweiss, Meiklejohn. Sonic: Zero-knowledge snarks from linear-size universal and updateable structured reference strings. eprint 2019/099.
• [Set] Setty. Spartan: Efficient and general-purpose zkSNARKs without trusted setup. eprint 2019/550. [page on this site]

Appendix A: Claims for Permutation Argument

The following claim is crucial for the correctness of the protocols in Section 5.

Proof (by Tohru Kohrita). By Schwartz-Zippel and the assumption of the claim, the following equality of polynomials holds in \mathbb{F}[X, Y]:

Since \mathbb{F}[X, Y] is a unique factorization domain where the invertible elements are exactly \mathbb{F}^*, and the linear factors are irreducible, there must be a one-to-one map between the factors of each side that maps a factor on the LHS to one on the RHS with the same coefficient for X. Since the coefficient of Y in all terms is one, the constant must be 1. Thus, for all i \in [n]:

Therefore b_i = a_{\sigma(i)} for all i \in [n].