Darlin: Recursive proofs using Marlin
Haböck, Ulrich
ulrich@horizenlabs.io

Garoffolo, Alberto
alberto@horizenlabs.io

Di Benedetto, Daniele
daniele@horizenlabs.io
October 1, 2021

Abstract
This document1 describes Darlin, a succinct zero-knowledge argumentof knowledge based on the Marlin SNARK [CHM+ 20] and the ‘dlog’ polynomial commitment scheme from [BCC+ 16, BBB+ 18]. Darlin addresses
recursive proofs by integrating the amortization technique from Halo[BGH19] for the non-succinct parts of the dlog verifier, and we adapt
their strategy for bivariate circuit encoding polynomials to aggregate
Marlin’s inner sumchecks across the nodes the recursive scheme. We estimate the performance impact of inner sumcheck aggregation by about
30% in a tree-like scheme of in-degree 2, and beyond when applied tolinear recursion.

Contents
1 Introduction

2

2 Preliminary notes

4

3 A cohomological sumcheck argument

5

4 Coboundary Marlin
7
4.1 Arithmetization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
4.2 The protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
4.3 A note on performance . . . . . . . . . . . . . . . . . . . . . . . . . 12
1 This paper is the full version of the previously published extended abstract ‘Darlin: A
proof-carrying data scheme based on Marlin’.

15 Recursion
12
5.1 Inner sumcheck aggregation . . . . . . . . . . . . . . . . . . . . . . 13
5.2 Generalization to several circuits . . . . . . . . . . . . . . . . . . . 15
5.3 Accumulating the dlog hard parts . . . . . . . . . . . . . . . . . . . 16
5.4 The main recursive argument . . . . . . . . . . . . . . . . . . . . . 16
5.5 A note on performance . . . . . . . . . . . . . . . . . . . . . . . . . 19
6 Future work

19

7 Acknowledgements

20

Bibliography

20

A Appendix
23
A.1 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
A.2 Interactive arguments . . . . . . . . . . . . . . . . . . . . . . . . . . 23
A.3 Forking Lemmas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
A.4 Proof of Theorem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
A.5 Proof of Theorem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
A.6 Polynomial commitment schemes . . . . . . . . . . . . . . . . . . . 29
A.7 The dlog commitment scheme from [BCMS20] . . . . . . . . . . . 30
A.8 The batch evaluation protocol from [BDFG20] . . . . . . . . . . . 31
A.9 Segmentation of linear commitment schemes . . . . . . . . . . . . 32
A.10 Facts on the Lagrange kernel . . . . . . . . . . . . . . . . . . . . . . 33

1

Introduction

Succinct non-interactive arguments of knowledge (SNARKs) are the basis forsecure decentralized computations, allowing to verify the correctness of a large
number of operations by a single succinct and easy to verify cryptographic
proof. Since the advent of SNARKs [Gro10, GGPR13] practical proof systems
followed soon after, e.g. Pinocchio [PHGR13], Groth16 [Gro16], and Groth17[GM17]. Whereas the first SNARKs are intrinsically connected to pairings via
non-standard knowledge commitments, proof systems from the second wave,
such as Sonic [MBKM19], Aurora [BSCR+ 19], Marlin [CHM+ 20], or Plonk[GWC19], are built in a modular way on any polynomial commitment scheme.
To scale over large amounts of data to be processed, recursive arguments ormore generally proof-carrying data (PCD) schemes [CT10, BCCT13], are inevitable. Recursive arguments verify the existence of a previous such, and theirperformance is largely dependent on how efficient the verifier itself is translated
into an argument. The issue of such a translation step is that typically the assertion to be proven is arithmetized (as a relation or circuit) over a field of adifferent characteristic than the proof itself, and simulating the arithmetics ofa ‘foreign’ field is costly. The most common approach to tackle the problem
is using a 2-cycle of elliptic curves [SS11, CCW18]. Such cycles are pairs of
elliptic curves in which the subgroup of one curve is of the same prime order2

as the base field of the other. Applied to pairing-based SNARKs the cycle
approach requires high field sizes. The only known cycles are based on MNTcurves of low embedding degree [CCW18], and as such they demand field sizes
beyond 1, 000 bit to meet a reasonable level of security [GS19]2 . Second wave
SNARKs are not necessarily bound to pairings, hence allow to use cycles of
non pairing-friendly curves [BGH19, BLH+ ], or such in which at least one of
the curves is not pairing-friendly [Ol]. Although allowing for smaller field sizes,
the use of non pairing-friendly cycles introduces another issue. Due to a lackof better alternatives, such constructions apply (a variant of) the ‘dlog’ polynomial commitment scheme from [BCC+ 16] the verifier of which is linear in
the size of the circuit to be proven; a serious obstacle for efficient recursion. In
their seminal work [BGH19], Bowe et al. showed how to overcome the problemof linear verifier size by a novel approach called nested amortization. In nested
amortization the proof system aggregates the computational ‘hard parts’ of theverifier outside the circuit, reducing the verification of all of them to a single
expensive check at the recursion end.
Since [BGH19] amortization schemes became an active field of research.
Bünz et al. [BCMS20] gave a more modular approach to the [BGH19] concept of amortization (named accumulation scheme therein). However, theirapproach is less performant than the one in [BGH19], which directly integrates
the amortization rounds into the argument system. Boneh et al. [BDFG20]
extend the concept of amortization to private aggregation schemes for polynomial commitments, which allow to aggregate entire opening proofs along thenodes of a PCD scheme. An even more radical approach for rank one constraint systems (R1CS) is followed by [BCL+ 20], who aggregate entire R1CS
solutions over recursion. Although both approaches lead to a significant speedup of recursion, they come at the cost of increased proof sizes for the PCD.
The private witnesses aggregated across the nodes are as large as the circuit
itself. For a Marlin verifier it is at about 1 MiB at minimum, and multiples ofthat in typical applications [BCL+ 20].
In this document we describe the Darlin proof carrying data scheme, therecursive SNARK for a Latus sidechain of Zendoo [GKO20], a blockchain system which supports cross-chain communication. Latus sidechains are highly
customizable blockchains which share the same token as the Zendoo mainchain
they are bootstrapped from, and the Darlin scheme is used to provide succinct
proofs of correct side chain state transitions. Darlin is based on the Marlin
argument system, modified in order to handle the aggregation of both Marlin’s
inner sumchecks and the ‘dlog’ hard parts. According to our estimates, we
expect the advantage of Darlin over standard Marlin (without inner sumcheckaggregation) to be about 30% when ‘merging’ two previous proofs, at the costof only tripling the proof size, cf. Table 1.
2 [BMRS20] uses a cycle of MNT4/MNT6 curves with 753 bit field sizes targeting asecurity level of 128 bit. However, improvements on the towered number field sieve [GS19,
Gui20] enforce to increase the field size up to 1, 000 bits.

3

Table 1: The impact of inner sumcheck amortization: Comparison of Marlin/dlog [CHM+ 20] versus Darlin for a PCD node which verifies two previous
proofs, both using the Pasta curves [HBG], and using the optimization techniques from [BGH19] to reduce the size of the verifier in circuit. We “segmentize” dlog commitments to speed up the prover. See Section 5.5 for details.
As our implementation is not ready yet, the prover times are estimates for an
Amazon EC2 G4dn instance (4 Intel Xeon@2.5 GHz + 1 NVIDIA T4).
dlog segment size†
Marlin∗constraints
DarlinMarlin∗proof size
DarlinMarlin∗prover time
Darlin∗∗∗219≈ 320 k≈ 290 k≈ 4.2 kB
≈ 15.3 kB≈ 16.5 s≈ 12.3 s (9.6 s∗∗ )218≈ 384 k≈ 320 k≈ 4.6 kB
≈ 15.7 kB≈ 15.9 s≈ 11.7 s (9.1 s∗∗ )217≈ 520 k≈ 390 k≈ 5.3 kB
≈ 16.8 kB≈ 15.38 s≈ 11.4 (8.8 s∗∗ )Assuming R1CS density d = 2, which is large enough in our applications.
only at the two lowest levels of a proof tree, where aggregation is trivial.

The document is organized as follows. In Section 3 we describe a variant of
the univariate sumcheck argument from [BSCR+ 19, CHM+ 20], inspired by the
grand product argument of Plonk [GWC19]. This variant does not rely on degree bound proofs and allows a more lightweight zero-knowledge randomization.
In Section 4 we informally describe our variant of Marlin, which besides using
a slightly different matrix arithmetization applies the sumcheck argument from
Section 3. In Section 5 we recapitulate the amortization strategy for the dlog
hard parts, explain the aggregation of Marlin’s inner sumcheck across multiple
circuits, and summarize the main recursive argument. All formal definitions
and proofs are postponed to the appendix, Section A.

2

Preliminary notes

Whenever appropriate, we formulate our protocols as algebraic oracle proofs,
with oracles as an information-theoretic model for homomorphic polynomialcommitments. An algebraic oracle proof is a multi-round protocol in which theprover responds to verifier challenges with oracles for some low-degree polynomials, receives another challenge from the verifier. The prover replies with someother oracles, and so on. The verifier is allowed to query these oracles for thevalues of any linear combination of their polynomials at any point she chooses.
As in algebraic holographic proofs [CHM+ 20], the verifier may access some of
the inputs only via oracle queries, but we do not assume that these oracles stemfrom a (circuit-specific) setup phase. Algebraic oracle proofs can be viewed asa variant of fully linear interactive oracle protocols [BBCGI19], considering
4

an evaluation query as a linear functional of the polynomial to be queried.
However, we shall not dwell on their separate information-theoretic security
properties, nor we explicitly provide the compiler which transforms these into
their corresponding ones for the resulting interactive argument systems when
instantiating the oracles by a polynomial commitment scheme. Instead, theproof of our main recursive argument from Section 5.4 relies on a compiler as
used implicitly in the security analysis of the batch evaluation protocol from[BDFG20].

3

A cohomological sumcheck argument

Let F be a finite field, H be a multiplicative subgroup of order n, and assume that p(X) is a polynomial of arbitrary degree. The univariate sumcheckargument from [BSCR+ 19, CHM+ 20] is an algebraic oracle proof for showingthat∑ p(x) = 0.
x∈H

The sumcheck argument is the key ingredient to Marlin’s way of proving awitness polynomial satisfying the rules of a given circuit (see Section 4). It isbased on the fact that the above sum is equal to n times the constant term of
the polynomial, if p(X) is of reduced form, i.e. of a degree strictly less thanthe domain size ∣H∣ = n. Hence showing that the reduced form of p(X) hasconstant term zero, i.e.
p(X) = X ⋅ g(X) + h(X) ⋅ (X n − 1),(1)

for some polynomials h(X) and g(X) whereas deg(g(X)) < n − 1, proves theclaimed sum. To convince the verifier of (1) the prover provides the oracles forp(X) g(X) and h(X), which we denote by[p(X)], [g(X)], [h(X)],
together with a proof that deg(g(X)) ≤ n−1. In response the verifier samples arandom challenge z ←$ F on which the oracles are queried for p(z), g(z), h(z).
These evaluations are used to validate the identity (1) at X = z. In order toobtain (honest verifier) zero-knowledge, the prover samples a random ‘mask’polynomial s(X) of degree at least n and proves thatp̂(X) = p(X) + s(X)(2)

sums up to σ = ∑z∈H s(z), which is done by an ordinary sumcheck argument
for p̂(X) − σ/n. See [CHM+ 20] for the details.
Our sumcheck argument carries over the grand product argument from
Plonk [GWC19] to the additive setting. Instead of using the reduced form of
the polynomial p(X) in question, the prover shows that the additive cocyclewith respect to the group action of Z on H defined by g,
k−1

fp (k, X) = ∑ p(g i ⋅ X)
i=0

5

(3)

is a coboundary, which is characterized by the following folklore Lemma.
Lemma 1. Let H be a multiplicative subgroup of a finite field F and let g bea generator of H. For any univariate polynomial p(X) of arbitrary degree wehave ∑z∈H p(z) = 0 if and only if there exists a polynomial U (X) such that
U (g ⋅ X) − U (X) = p(X) mod (X n − 1).

(4)

Proof. Suppose that ∑z∈H p(z) = 0. Define U (X) on H by intitializing U (g 0 ) =U (1) to any arbitrary value, and setting
k−1

U (g k ) = U (1) + ∑ p(g i )i=0

for k = 1, . . . , n − 1. By definition U (g k+1 ) = U (g k ) + p(g k ) for all k, 0 ≤k ≤ n − 2. The equation also holds for k = n − 1, since the full cycle sumn−1∑i=0 p(g i ) = ∑z∈H p(z) vanishes. This shows that U (g ⋅ z) − U (z) = p(z) forall z in H, thus any extension U (X) beyond H satisfies the claimed identity
U (g ⋅ X) − U (X) = p(X) mod (X n − 1). The other direction of the proof is
obvious.
The main advantage of the coboundary approach is that the algebraic oracle
proof for equation (4) allows a more lightweight zero-knowledge randomization
than that of equation (1): Since no reduced form is needed for U (X), we cansimply randomize U (X) by means of the vanishing polynomial of H,
Û (X) = U (X) + (c0 + c1 ⋅ X) ⋅ (X n − 1),(5)with uniformly random c0 , c1 ←$ F , assuming that Û (X) is not queried beyond
the sumcheck protocol. We describe the sumcheck argument as an algebraic
oracle proof for polynomials from R = F [X]/(X n − 1) with the aim to provethat the prover knows an element from R which is subject to the sumcheck∑x∈H p(X) = 0.
Protocol 1 (Coboundary sumcheck). Let H be a multiplicative subgroup of afinite field F , g be a generator of H having order n. The prover is given p(X)from R = F [X]/(X n − 1) subject to ∑x∈H p(x) = 0, and the verifier is given theoracle of a random representant p̂(X) = p(X) + r(X) ⋅ (X n − 1), where r(X) is
sampled uniformly from the set of polynomials of degree strictly less than b + 1.
3(1) The prover P computes U (X) of deg(U (X)) < n according to the coboundary identity (4). It computes Û (X) as in (5), with c0 , c1 ←$ F , and thequotient polynomial h(X) satisfyingÛ (g ⋅ X) − Û (X) = p̂(X) + h(X) ⋅ (X n − 1).

(6)

P then sends [Û (X)], [h(X)] to the verifier.
3 The bound b ≥ 0 corresponds to the maximum number of allowed queries for [p̂(X)]beyond the sumcheck protocol.

6(2) The verifier V samples a random challenge z ←$ F ∖ H and queries theoracles [Û (X)], [h(X)], and [p̂(X)] for their values at z. (The oracle
aborts, if z ∈ H.) V uses these values to verify identity (6) at X = z, andaccepts if valid. (Otherwise, the verifier rejects.)
The security analysis of Protocol 1 (applied to a specific p̂(X)) is given in
the course of the proof of Theorem 2. As a separate algebraic oracle proof it isperfectly complete and computationally knowledge sound, assuming the size of
H is negligible compared to the size of the field F . It is succinct and perfectly
honest verifier zero-knowledge, assuming that each the oracles [p̂(X)] is queriedoutside the protocol at most another b times (and [Û (X)] is not queried atall). The latter is an immediate consequence of the fact that the conditional
distribution of(v1 , v2 , v3 , v4 ) = (Û (g ⋅ z), Û (z), p̂(z), h(z)),
conditional to z ∉ H, is uniform on the relation Rz = {(v1 , v2 , v3 , v4 ) ∈ F 4 ∶v1 − v2 − v3 = v4 ⋅ (z n − 1)}. If one instantiates the oracle with a computationally binding (Definition 8) and perfectly hiding (Definition 7) polynomialcommitment scheme, the opening proof of which is an argument of knowledge(Definition 5), then the protocol is compiled into a succinct honest verifierzero-knowledge argument of knowledge.

4

Coboundary MarlinThis section describes Coboundary Marlin, a slight variant of the Marlin SNARK[CHM+ 20]. We introduce two changes: First, we replace Marlin’s sumcheck argument by the coboundary argument from Section 3. Second, we4 make use of
the Lagrange kernel
Ln (X, Y ) =1 Y ⋅ (X n − 1) − X ⋅ (Y n − 1)
⋅
n
X −Y
n

(7)

n

−Y
instead of the non-normalized version R(X, Y ) = XX−Y
. The Lagrange kernel
shares the same key properties as R(X, Y ). It can be evaluated succinctly, andallows a practical sumcheck representation for the bivariate circuit polynomials, as shown below. However, we point out that our favor for the Lagrange
kernel is mainly for esthetic reasons. Using it allows us to argue directly withthe bivariate circuit polynomials instead of a derivative in both of Marlin’s
sumcheck arguments as well as our aggregation strategy from Section 5.
4 We would like to thank A. Querol for pointing out that [CFF+ 20] also choose the Lagrange kernel. As a consequence, our version of the lincheck is exactly the same as theirs.

7

4.1

Arithmetization

We assume an arithmetic circuit C over F being represented by a rank-one
constraint system (R1CS), i.e.
(A ⋅ y) ⊙ (B ⋅ y) = C ⋅ y,(8)where we assume that A, B, C are n × n matrices over F , ⋅ is the vector matrix
product and ⊙ denotes the entry-wise (Hadamard) product of vectors. The
witness vector y ∈ F n is composed of a public part x and a private part w,
i.e. y = (x∥w). Notice assuming quadratic matrices is no loss in generality,
as the constraint system may always be padded with dummy constraints orvariables. Moreover, we presume that ∣F ∣ − 1 is divisible by a high power of
two, assuring the existence of sufficiently large multiplicative subgroups of 2adic order. Subgroups of such smooth order allow for a fast Fourier transformwhich runs in time O(n log(n)), where n is the order of the subgroup. (In thesequel we call such subgroups FFT domains.)
In Marlin the R1CS equations are expressed over the FFT domain H = {z ∈F ∶ z n − 1 = 0} using Lagrange encoding. That is, given an arbitrary enumeration {z1 , . . . , zn } of H a vector y = (yk )nk=1 is associated with the polynomial
y(X) = ∑ yk ⋅ L(X, zk ).

(9)kIn other words, (yk ) is the vector of coordinates with respect to the Lagrange
basis (L(X, xk ))k . Therefore y ∈ F n is a solution of (8) if and only if its
associated polynomial y(X) = ∑k yk ⋅ L(X, zk ) satisfies
yA (X) ⋅ yB (X) = ∑ C(X, z) ⋅ y(z) mod (X n − 1),

(10)

z∈H

where
yA (X) = ∑ A(X, z) ⋅ y(z) mod (X n − 1),

(11)

z∈H

yB (X) = ∑ B(X, z) ⋅ y(z) mod (X n − 1).

(12)

z∈H

In these equations, A(X, Y ), B(X, Y ), C(X, Y ) are the bivariate polynomials with the entries of the R1CS matrices A, B, C respectively as Lagrange
coordinates,n

M (X, Y ) = ∑ Mi,j ⋅ L(X, zi ) ⋅ L(Y, zj ),

(13)

i,j=1

for M = A, B, C. The double sum in (13) is made amenable to a univariate
sumcheck argument by indexing its non-zero terms over yet another FFT domain K = {w ∈ F ∶ wm − 1 = 0}, again assuming the existence of a sufficiently
large smooth multiplicative subgroup. As in Marlin, we denote byvalM (X), rowM (X), colM (X) ∈ F [X]/(X m − 1)8(14)the polynomials of degree < m which index M ’s non-zero values, their row andcolumn indices (the latter two regarded as points from H, as in (13)), so that
M (X, Y ) = ∑ valM (w) ⋅ L(X, rowM (w)) ⋅ L(Y, colM (w)).
w∈K
n

−1)
whenever z is from H, we haveSince Ln (X, z) = n1 ⋅ z⋅(X
X−z

M (X, Y ) =(X n − 1) ⋅ (Y n − 1)nvalM (w) ⋅ rowM (w) ⋅ colM (w)⋅ ∑(X− rowM (w)) ⋅ (Y − colM (w))
w∈K

mod (X m − 1). (15)This representation, which differs slightly from [CHM+ 20], is the one we use
for the second sumcheck argument, the ‘inner sumcheck’. We assume that for
M = A, B, C, the precomputed polynomials
row.colM (X) = rowM (X) ⋅ colM (X) mod (X m − 1),
val.row.colM (X) = valM (X) ⋅ rowM (X) ⋅ colM (X) mod (X

(16)
m

− 1),

(17)

regarded of degree < m, are also part of the verifier key.

4.2

The protocol

In Marlin, public circuit inputs x = (xi ) define the Lagrange representation of
the input polynomial
x(X) = ∑ xi ⋅ L` (xi , X) ∈ F [X]/(X ` − 1)iover an properly sized input domain I ≤ H of size `, and the full circuit statepolynomial y(X) is combined via
y(X) = x(X) + (X ` − 1) ⋅ w(X),(18)

using a gauged witness polynomial w(X) ∈ F <n−` [X]. The prover provides theoracles for the private witness polynomial w(X), yA (X), yB (X) and convinces
the verifier of the R1CS identities (10), (11), and (12). These three identities
are reduced to a single one by building a random linear combination based ona challenge η ←$ F , i.e.
yη (X) = ∑ Tη (X, z) ⋅ y(z) mod (X n − 1),
z∈H

with
and

yη (X) = yA (X) + η ⋅ yB (X) + η 2 ⋅ yA (X) ⋅ yB (X),Tη (X, Y ) = A(X, Y ) + η ⋅ B(X, Y ) + η 2 ⋅ C(X, Y ).
9(19)

The linear identity (19) is reduced to a sumcheck over H by sampling a polynomial R(X, α) using a suitable kernel R(X, Y ), α ←$ F , and applying it via
scalar product to both sides of the equation. This yields∑ ⟨R(X, α), Tη (X, z)⟩H ⋅ y(z) = ⟨R(X, α), yη (X)⟩H ,
z∈H

hence

∑ ⟨R(X, α), Tη (X, z)⟩H ⋅ y(z) − R(z, α) ⋅ yη (z) = 0.

(20)

z∈H

Choosing the Lagrange kernel Ln (X, Y ) for R(X, Y ), ⟨Ln (X, α), Tη (X, z)⟩H =Tη (α, z), since Tη (X, z) is of degree less than n (see Appendix A.10). Henceequation (20) is equal to∑ Tη (α, z) ⋅ y(z) − Ln (z, α) ⋅ yη (z) = 0.

(21)

z∈H

Equation (21) is the central identity to be proven by the protocol.
We describe the protocol as algebraic oracle proof.
Initialization
In the first step the prover computes the polynomials5 w(X), yA (X), yB (X) ∈F [X]/(X n − 1) from their Lagrange representations, and chooses random representantsŵ(X), ẑA (X), ẑB (X) ∈ F <n+1 [X]according to the sampling rule p̂(X) ←$ p(X) + F ⋅ (X n − 1) using randomizer
polynomials of degree zero. It sends their oracles [ŵ(X)], [ŷA (X)], [ŷB (X)] to
the verifier, who returns the randomnesses η ←$ F and α ←$ F ∖ H for Equation(21).
Outer sumcheck
To prove equation (21) we apply the coboundary argument from Section 3 top̂(X) ∶= Tη (α, X) ⋅ ŷ(X) − Ln (X, α) ⋅ ŷη (X), whereŷ(Y ) ∶= x(Y ) + (Y ` − 1) ⋅ ŵ(Y ),ŷη (Y ) ∶= ŷA (Y ) + η ⋅ ŷB (Y ) + η 2 ⋅ ŷA (Y ) ⋅ ŷB (Y ).
The prover computes the boundary polynomial U1 (X) ∈ F [X]/(X n −1), chooses
a random representant
Û1 (X) ∈ F <n+2 [Y ]5 Unless stated otherwise we assume polynomials p(X) from F [X]/(X n − 1) of reduced
form, i.e. of degree < n.

10

of it, and computes h1 (X) ∈ F <2⋅n+1 [X] for the outer sumcheck identityTη (α, X) ⋅ ŷ(X) − Ln (X, α) ⋅ ŷη (X)= Û1 (gX) − Û1 (X) + h1 (X) ⋅ (X n − 1), (22)where g is a generator of H. It then sends [Û1 (X)], [h1 (X)] together with[Tη (α, X)] to the verifier. The verifier samples another random challengeβ ←$ F ∖ H and queries the oracles for ŵ(β), ŷA (β), ŷB (β), Tη (α, β), Û1 (g ⋅ β),Û1 (β), h1 (β), which are used for checking the identity (22) at Z = β.
Inner sumcheck
To prove that Tη (α, β) as provided by the oracle in fact stems from the circuit
polynomials M (X, Y ), M = A, B, C we adapt Marlin’s inner sumcheck to ourrepresentation (15). Using these we obtainTη (α, β) = ∑

ηM ⋅

∑

w∈K M =A,B,C
nval.row.colM (w),(α − rowM (w)) ⋅ (β − colM (w))

(23)

n

)
⋅ (1, η, η 2 ). We apply the coboundary sumwhere (ηA , ηB , ηC ) = (1−α n)⋅(1−β2check toval.row.colM (X)
p(X) =,∑ ηM ⋅(α−row
M (X)) ⋅ (β − colM (X))
M =A,B,C

regarded as a reduced element from F [X]/(X m − 1). The prover computes
U2 (X) from F [X]/(X m − 1) satisfyingTη (α, β)+ U2 (gK X) − U2 (X) mod (X m − 1),mand then multiplies both sides with the denominatorp(X) =b(X) =(α − rowM (X)) ⋅ (β − colM (X))∏
M =A,B,C=(αβ + β ⋅ rowM (X) + α ⋅ colM (X) + row.colM (X)) ,∏M =A,B,C

where row.colM (X) are the precomputed products (16) from the prover key.
This yields the inner sumcheck identity∑ηM ⋅ val.row.colM (X)

M =A,B,C= b(X) ⋅ (Tη (α, β)+ U2 (gK X) − U2 (X)) + h2 (X) ⋅ (X m − 1), (24)mwhere gK is a generator of K and h2 (X) ∈ F <3⋅m−3 [X]. The prover sends theoracles [U2 (X)] and [h2 (X)] to the verifier, who samples a random challengeγ ←$ F , on which the oracles are queried for rowM (γ), colM (γ), row.colM (γ),
val.row.colM (γ), where M = A, B, C, and U2 (gK ⋅ γ), U2 (γ), h2 (γ). These
values are used by the verifier to check the identity (24) at X = γ.
11Security
The security analysis of Coboundary Marlin is similar to that of our mainrecursive argument, Theorem 2. As for Theorem 2, we stress the fact that
we use the Halevi-Micali [HM98] notion of proof of knowledge with negligible
knowledge error. The proof can be found in the appendix, Section A.5.
Theorem 1. Instantiating the oracle by a computationally binding and perfectly hiding polynomial commitment scheme (Definition 7 and 8, Coboundary
Marlin is a succinct, perfect honest verifier zero-knowledge (Defintion 6) argument of knowledge (Definition 5) for the R1CS relation
R = {((A, B, C, x), w) ∶ y = (x, w) satisfies (A ⋅ y) ⊙ (B ⋅ y) = C ⋅ y}.
Using the Fiat-Shamir transform the interactive argument is transformed
into a zk-SNARK with analog security properties in the random oracle model.

4.3

A note on performance

Marlin’s outer sumcheck takes place over the FFT domain H, the size of which
covers the number of constraints/variables of the constraint system. In practice circuits yield about the same number of variables as constraints, hence itis reasonable to take n the number of constraints as measure for the computational effort of the outer sumcheck, assuming a sufficiently smooth order ofF ∗ to optimally match n. The inner sumcheck runs over the FFT domain Kof size m ≈ maxM =A,B,C ∥M ∥ (∥M ∥ is the number of non-zero entries in M ),again under the assumption of sufficient smoothness. This domain is by thefactormaxM =A,B,C ∥M ∥d=nlarger, where d is the R1CS density of the circuit. The R1CS density is theaverage number of variables per constraint. In practice, we observed values
between d = 1.5 and d = 2 for the circuits we target. (These circuits implement
elliptic curve arithmetics over non-extension fields and the x5 -Poseidon hash
[GKR+ 21] with an internal state of 3 field elements.)

5

Recursion

Our recursive scheme is based on Coboundary Marlin and the [BCMS20] variant of the dlog polynomial commitment scheme from [BCC+ 16]. We take
Coboundary Marlin without inner sumcheck as succinct argument, and weaggregate both the non-succinct parts of the opening proof verifier, as well as
the correctness checks usually served by the inner sumchecks, which is verifyingthat the commitment intended forTη (α, Y ) =∑M =A,B,C

12

ηM ⋅ M (α, Y )Table 2: Computational effort of the (coboundary) zk-Marlin prover, using
an elliptic curve based linear polynomial commitment scheme. We only countfast Fourier transforms FFT(a) in terms of their domain size a, and elliptic
curve multi scalar multiplications MSM(b) in terms of the number of scalars b.
(Without opening proof.)

intial roundouter sumcheck
inner sumcheckoverallpolynomial arithm.
3 FFT(n)2 FFT(n) + 2 FFT(2n)+3 FFT(3n)1 FFT(m) + 1 FFT(4m)≈ (15 + 5 ⋅ d) FFT(n)commit
3 MSM(n)2 MSM(n) + 1 MSM(2n)1 MSM(m) + 1 MSM(3m)≈ (7 + 4 ⋅ d) MSM(n)in fact carries these polynomials. Aggregation of the non-succinct part of thedlog verifier (the dlog hard parts) relies on the same principle as introduced by
Halo [BGH19]. The way we aggregate the inner sumchecks is a generalizationof Halo’s strategy for their circuit encoding polynomial s(X, Y ), and we extend
it across circuits to serve a reasonable number of instances Ci = {Ai , Bi , Ci } simultaneously. As a separate ‘stand-alone’ protocol, our strategy may be taken
as public aggregation scheme in the sense of [BDFG20], or an (atomic) accumulation scheme according to [BCMS20, BCL+ 20]. However, for efficiency reasons
we choose Halo’s ‘interleaved’ approach instead of the blackbox constructions
from [BCMS20, BCL+ 20, BDFG20], and let the rounds of both the argument
system and the aggregation scheme share the same opening proof.
In our recursive argument certain previous proof elements (acci )`i=1 called
accumulators are ‘passed’ through inputs of the ‘current’ circuit and postprocessed within the run of the current argument. Formally, (acci )`i=1 satisfy
a given predicate φ,φ(acci ) = 1, i = 1, . . . , `,and are mapped to dedicated inputs of the current circuit. Beyond the rounds
for proving satisfiability of the current circuit, the accumulators (acci )`i=1 areaggregated within some extra rounds into a new instance, the ‘current’ accumulator acc, which is again subject to φ(acc) = 1. Altogether our recursiveargument is of the form
⟨ Prove((acci )`i=1 , (x, w), pk), Vf((acci )`i=1 , x, vk)⟩,
where (x, w) are public and private circuit witnesses, pk and vk are the proverand verifier key for both Marlin and the aggregation scheme, and the new acc
is output to both prover and verifier.

5.1

Inner sumcheck aggregation

Here, the accumulator consists of a commitment C and the succinct descriptionof the circuit polynomial Tη (z, Y ) intended to be represented by C, i.e. the13

point z ∈ F and the randomnesses η⃗ = (ηA , ηB , ηC ) ∈ F 3 ,accT = (z, η⃗, C).
The corresponding predicate φT is satisfied if and only if C is the commitmentof Tη (z, Y ) (using commitment randomness zero). The prover reduces thecorrectness of several accumulator instances to that of a single new one, andthe verifier validates the correctness of this reduction while keeping track of
the polynomial descriptions (i.e. the point z and the coefficient vector η⃗) byherself. We sketch the strategy assuming a single previous accumulator.
There, a previous instance (α′ , η⃗′ , C ′ ) is ‘merged’ with (α, η⃗, C) of the current outer sumcheck. In a first step, the prover reduces the ‘multi-point’, ‘multipolynomial’ instance6 Tη⃗′ (α′ , Y ), Tη⃗ (α, Y ) to a single-point, multi-polynomial
instanceTη⃗′ (X, β), Tη⃗ (X, β),with random β ←$ F , by providing the commitments to these new polynomials
and proving consistency via polynomial testing: If the old polynomials evaluate
at the challenge β to the same values as the new polynomials at the old point,respectively, then correctness of the new polynomials overwhelmingly implies
that of the old ones. Using the same principle once again, correctness of thesingle-point multi-polynomial instance is then reduced in batch to a single-point
single-polynomial instanceλ ⋅ Tη⃗′ (α′′ , Y ) + Tη⃗ (α′′ , Y ) = Tλ⋅⃗η′ +⃗η (α′′ , Y ),where λ, α′′ ←$ F are random. Note that the resulting polynomial is again of
the form Tη⃗′′ (α′′ , Y ) with η ′′ = λ ⋅ η⃗′ + η⃗. For the reduction, the prover showsthat the linear combination λ ⋅ Tη⃗′ (X, β) + Tη⃗ (X, β) opens at the new challenge
X = α′′ to the same value as the new polynomial λ ⋅ Tη⃗′ (α′′ , Y ) + Tη⃗ (α′′ , Y ) at
the old point Y = β. Again, correctness of the new polynomial overwhelmingly
implies correctness of the old ones.
Protocol 2 is regarded as a subprotocol of our complete recursive argument
Protocol 4, right after the outer sumcheck. We formulate it as an algebraic
oracle protocol, considering commitments as oracles.
Protocol 2 (Inner sumcheck aggregation). Suppose that acc′T = (α′ , η⃗′ , [T ′ (Y )])is a previous accumulator, intended to represent an oracle for T ′ (Y ) = Tη⃗′ (α′ , Y ),and (α, η⃗, [T (Y )]) is as provided by the prover in the current outer sumcheck,intended to represent an oracle for T (Y ) = Tη⃗ (α, Y ), with η⃗ = (1, η, η 2 ). Aggregation of acc′T and (α, η⃗, [T (Y )]) is done according to the following steps
immediately processed after the outer sumcheck.
(1) Given β, the random challenge from the outer sumcheck, the prover sends
the oracles for the ‘bridging polynomials’Tη⃗ (X, β), Tη⃗′ (X, β) ∈ F [X]/(X n − 1),
6 Here ‘multi-point’ refers to the different points α, α′ , and ‘multi-polynomial’ to thedifferent polynomials defined by η⃗, η⃗′ .

14

on which the verifier responds with random λ, γ ←$ F .
(2) Given λ, γ from the verifier, the prover ‘responds’ with the oracle for
T ′′ (Y ) = Tη⃗ (γ, Y ) + λ ⋅ Tη⃗′ (γ, Y ).
The verifier queries [Tη⃗ (X, β)], [Tη⃗′ (X, β)] for their corresponding values v1 ,v2 at X = α and α′ , and checks them against the values of [T (Y )], [T ′ (Y )]at Y = β, respectively. It also queries [T ′′ (Y )] at Y = β and checks its value
against that of the linear combination [Tη⃗ (X, β)] + λ[Tη⃗′ (X, β)] at X = γ. Ifthese checks succeed, then the verifier accepts and the new accumulator isacc′′T = (α′′ , η⃗′′ , C ′′ ) = (γ, η⃗ + λ ⋅ η⃗′ , [T ′ (Y )]).
A formal analysis of Protocol 2 is given in the course of the security proofof the complete recursive argument. As a stand-alone argument having its own
opening proof, the protocol defines a (perfectly) complete and sound accumulation scheme for the predicate φT in the sense of [BCMS20]: If both acc′T and(α, η, C) satisfy the predicate φ, so does acc′′T . And if φ(acc′′T ) = 1, then withoverwhelming probability both φ(acc′T ) and φ(α, η, C) = 1.

5.2

Generalization to several circuits

The aggregation strategy from Section 5.1 is easily extended to serve multiple
circuits C1 , . . . , CL simultaneously. This ‘cross-circuit’ generalization is especially useful in ‘non-homogeneous’ chemes which are composed by a variety ofrecursive circuits. Lets assume that the R1CS matrices Ai , Bi , Ci of the circuits Ci , i = 1, . . . , L, are padded to the same square dimension so that we may
regard their
Ai (X, Y ), Bi (X, Y ), Ci (X, Y ),as bivariate polynomials over the same domain H × H. As in the single-circuit
setting we leverage the linearity of the commitment scheme and keep track ofa single cross-circuit polynomial
L

L

i=1

i=1 M =Ai ,Bi ,Ci

TH (α, Y ) = ∑ Ti,⃗ηi (z, Y ) = ∑∑ηM,i ⋅ M (α, Y )(25)

by means of the cross-circuit coefficient vector H = (⃗
η1 , η⃗2 , . . . , η⃗L ). The crosscircuit accumulator for the collection C = {C1 , . . . , CL } is of the form
accC = (α, H, C),with α ∈ F , coefficient vector H = (⃗
η1 , . . . , η⃗L ) ∈ (F 3 )L , and an element C fromthe commitment group. The corresponding predicate φC is satisfied if and only
if C is in fact the dlog commitment of TH (α, Y ), using blinding randomness
zero.
15

5.3

Accumulating the dlog hard parts

The aggregation strategy for the non-succinct part of the dlog verifier is identical to that in [BCMS20]. The opening proof for the dlog commitment is
an inner product argument that uses the folding technique from [BCC+ 16] togradually reduce the opening claim on the initial full-length polynomial to oneof half the size, until ending up with the opening claim of a single coefficientpolynomial. The final committer key Gf of the opening proof is a single groupelement which is the result of a corresponding folding procedure on the fulllength committer key of the dlog scheme. It equals the commitment of thesuccinct reduction polynomial
k−1⃗ X) = ∏ (1 − ξk−1−i ⋅ X 2 ),
h(ξ,
i

(26)

i=0

where k = log ∣H∣ = n is the number of reduction steps and ξ⃗ = (ξi )k−1
i=0 theirchallenges. The dlog accumulator is of the form
⃗ C),
accdlog = (ξ,where ξ⃗ ∈ F k and C is from the commitment group, and the corresponding
accumulator predicate φdlog is satisfied if and only if C is the commitment of⃗ X), using blinding randomness zero.
h(ξ,As Protocol 2, the aggregation strategy is regarded as a subprotocol of thecomplete recursive argument Protocol 4, and for efficiency reasons we reuse thechallenge γ from the inner sumcheck aggregation. We again restrict to the caseof a single previous accumulator.
Protocol 3 (dlog hard parts aggregation). Suppose that acc′dlog = (ξ⃗′ , [h′ (X)])
is a previous dlog accumulator, with [h′ (X)] representing an oracle for h′ (X) =h(ξ⃗′ , X). The following step is part of the complete recursive argument andprocessed immediately after Protocol 2:(1) The verifier queries [h′ (X)] at for its value v ′ at X = γ from step (2) ofProtocol 2.
If v ′ = h(ξ⃗′ , γ) then the verifier accepts. The new accumulator acc′′dlog =(ξ⃗′′ , C ′′ ) is the one from the dlog opening proof at the end of the complete
protocol.

5.4

The main recursive argument

The complete recursive argument is a composition of Coboundary Marlin’souter sumcheck for the ‘current’ circuit, choosing ‘zero-knowledge bound’ b =1, the aggregation rounds from the cross-circuit variant of Protocol 2, andProtocol 3. As in Section 5.2 we assume that the bivariate circuit polynomials
Ai (X, Y ), Bi (X, Y ), Ci (X, Y ) are over the same domain H ×H, where ∣H∣ = n.
16

The query phases of these subprotocols are gathered at the end of the protocol,
which is then concluded by the batch evaluation argument from [BDFG20].
We formulate the complete argument with oracles for polynomials replacedby their dlog commitments, while keeping with the same notation [p(X)]. For
simplicity, we again restrict to the case of a single previous accumulator. The
general case is straight-forward.
Protocol 4 (Complete recursive argument). Given a composed accumulatoracc′ = (acc′C , acc′dlog ), where accC = (α′ , H ′ , CT′ ) is a cross-circuit accumulator⃗ C ′ ) is a dlog accumulator.
for the collection C = {C1 , . . . , CL } and acc′dlog = (ξ,The recursive argument for an instance (x, w) of the ‘current’ circuit Ck fromC is composed by the following steps.
(1) Intitialization for Ck : The prover computes the gauged witness polynomial
w(X), zA (X), and zB (X) from F [X]/(X n − 1) and chooses random
representantsŵ(X), ẑA (X), ẑB (X) ∈ F <n+1 [X]as described in Section 4. It sends their dlog commitments [ŵ(X)],[ẑA (X)], and [ẑB (X)] to the verifier, who responds with η, α ←$ F .
(2) Outer sumcheck for Ck : The prover computesTη⃗ (α, X) = ηA ⋅ A(α, X) + ηB ⋅ B(α, X) + ηC ⋅ C(α, X) ∈ F [Y ]/(X n − 1)of the current circuit, using η⃗ = (ηA , ηB , ηC ) = (1, η, η 2 ), andÛ1 (X) ∈ F <n+2 [Y ], h1 (X) ∈ F <2⋅n+1 [X]subject to the outer sumcheck identity (22). It sends [Tη⃗ (α, X)], [Û1 (X)],[h1 (X)] to the verifier, who returns another random challenge β ←$ F .
(3) Inner sumcheck aggregation, Step 1: The prover computes the ‘bridging’
polynomials forTη⃗ (X, β), TH ′ (X, β) ∈ F [X]/(X n − 1),and sends [Tη⃗ (X, β)], [TH ′ (X, β)] to the verifier, who answers with another random λ, γ ←$ F .
(4) Inner sumcheck aggregation, Step 2: The prover computes the crosscircuit linear combination
TH ′′ (γ, Y ) = Tη⃗ (γ, Y ) + λ ⋅ TH ′ (γ, Y ) ∈ F [Y ]/(Y n − 1),and [TH ′′ (γ, Y )] to the verifier.

17

After these steps, both prover and verifier engage in the batch evaluation argument from [BDFG20] for the dlog commitment scheme, applied to the queries
as listed below. If the queried values pass the checks of the outer sumcheck, Protocol 2 and Protocol 3, and if (acc′C , acc′dlog ) match with the public input x of thecircuit, then the verifier accepts. The new accumulator is acc′′ = (acc′′C , acc′′dlog )with7acc′′C = (γ, H ′′ , C ′′ ) = (γ, η⃗ ⋅ δk + λ ⋅ H ′ , [TH ′′ (γ, Y )]),⃗ Gf ) from the above batch evaluation proof.
and acc′′dlog = (ξ,The multi-point queries to be proven by the batch evaluation argument are
as follows.
- [ŵ(X)], [ẑA (X)], [ẑB (X)], [Û1 (X)], [h1 (X)], [Tη⃗ (α, X)] at β, as well as[Û1 (X)] at g ⋅ β,
- [Tη⃗ (X, β)] at α, [TH ′ (X, β)] at α′ , and [TH ′′ (γ, Y )], CT′ from acc′C at β,- [Tη⃗ (X, β)] + λ ⋅ [TH ′ (X, β)] at γ, and C ′ from acc′dlog at γ.
For the sake of completeness we summarize the batch evaluation argument in
Section A.8.
The following theorem states that the main recursive argument, i.e. Protocol 4 extended by the predicate check on acc′′C , is a zero-knowledge argument ofknowledge. We point out that we use the Halevi-Micali [HM98] notion of proofof knowledge for negligible soundness error, see Definition 4 and Defintion 5.
Theorem 2. If the dlog commitment scheme is computationally binding (Definition 8) then Protocol 4, extended by the predicate verification on the resulting
inner sumcheck accumulator acc′′C , is a perfectly honest verifier zero-knowledge(Definition 6) argument of knowledge (Definition 5) for the relation
R = {((C, acc′C , acc′dlog , x), w) ∶ (x, w) ∈ RCk ∧ φ(acc′C ) = 1∧ φdlog (acc′dlog ) = 1 ∧ (acc′C , acc′dlog ) is consistent with x},
where C = {C1 , . . . , CL } is a collection of rank-one constraint systems. Here,RCk denotes the R1CS relation given by the circuit Ck , and φ and φdlog are asin Section 5.2 and Section 5.3
The proof of Theorem 2 is given in Section A.4. In practice we use theFiat-Shamir transform to turn Protocol 4 into a non-interactive argument ofknowledge which is zero-knowledge against arbitrary polynomial time adversaries.
7 Here, η⃗ ⋅ δk denotes the vector which is η⃗ at the position of the current circuit Ck in the
cross-circuit accumulator, and zero elsewhere.

18

5.5

A note on performance

Inner sumcheck aggregation is particularly effective when the number of previous accumulators is low, as seen from the operations counts in Table 3. Fora single previous accumulator (` = 1) representing the case of linear recursion,
the prover effort for the recursive argument is comparable to that of standard
Marlin for a circuit of R1CS density d = 1. Having ` = 4 previous accumulators,
as in our Darlin PCD scheme, the equivalent density is about d = 1.5.
Table 3: Recursion prover with and without inner sumcheck aggregation interms of FFT operations and multi-scalar multiplications, for in-degree ` (without opening proof).

intial roundouter sumcheckaggregation rounds
overallwithout aggregation

polynomial arith.
3 FFT(n)2 FFT(n) + 2 FFT(2n)+3 FFT(3n)(4 + `) FFT(n)≈ (15 + `) ⋅ FFT(n)≈ (15 + 5 ⋅ d) FFT(n)commit
3 MSM(n)2 MSM(n) + 1 MSM(2n)(2 + `) MSM(n)≈ (9 + `) MSM(n)≈ (7 + 4 ⋅ d) MSM(n)Compared to a standard Marlin prover for circuits with density d = 2 theperformance improvement is estimated at 27%, as indicated by our estimatesfrom Table 1 in Section 1. The timing estimates from this table are based ona detailed simulation of a Darlin prover (in terms of MSM, FFT, vector andvector-matrix operations), run on an Amazon EC2 G4dn instance (with 4 Intel
Xeon@2.5 GHz and 1 NVIDIA T4) currently offered at a rate of 0.526 USD per
hour. The number of constraints for verifying two previous proofs stem fromdetailed paper-and-pencil counts, where our circuit design follows the ‘deferredarithmetics’ technique from [BGH19], which postpones non-native arithmetic
checks to the ‘next’ circuit in recursion, in which these operations are again
native. (We moreover apply their endomorphism-based scalar multiplication
which reduces the number of constraints significantly.) We vary over different
segment sizes for the dlog commitment scheme (cf. Section A.9 on segmentationof homomorphic polynomial commitment schemes) starting with the smallest
possible domain size ∣H∣ = 219 to cover the two verifier, and then reducing thecommitter key to 218 and 217 . Consequently, the prover times decrease at thecost of increasing proof sizes and the number of constraints for the verifier
circuit.

6

Future work

We will implement Darlin as the recursive main argument of our upcoming
Darlin proof carrying data suite [HB21], using a 2-cycle of ordinary elliptic
19

curves such as the Pasta curves [HBG]. The full suite will cover pure proof
merging nodes (for in-degree 1 and 2) as well as special purpose nodes withadditional consensus specific logic. Beyond that a separate transformation
chain of arguments for converting Darlin proofs into ordinary Marlin proofs
will be provided. A formal description, including an in-depth security analysis
will be given in [HB21].

7

Acknowledgements

The first author is indebted to Maus and Bowie for their appreciated feedback.
Without them, the main recursive argument would miss its most importantfeature, the whisker feedback loop in the cross-meal aggregation of fish, chicken
and beef. One of the first readers is also grateful to Peperita, that helped
moving away from pairings in exchange for tasty kibble.

Bibliography[BBB+ 18]

Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra,
Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs forconfidential transactions and more. In in IEEE Symposium on
Security and Privacy, pages 315–334, 2018.

[BBCGI19] Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, and Yuval Ishai.
Zero-knowledge proofs on secret-shared data via fully linear pcps.
In CRYPTO 2019, volume 11694 of LNCS, pages 67–97. Springer,
2019. full version:https://eprint.iacr.org/2019/188.pdf.
[BCC+ 16]

Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, andChristophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In M. Fischlin and
J.S. Coron, editors, EUROCRYPT 2016, volume 9666 of LNCS.
Springer, 2016. Full version: https://eprint.iacr.org/2016/
263.

[BCCT13] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer.
Recursive composition and bootstrapping for SNARKs and proofcarrying data. In STOC‘13, 2013.
[BCL+ 20]

Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra,and Nicholas Spooner. Proof-carrying data without succinct arguments. In IACR preprint archive 2020/1618, 2020. https://eprint.iacr.org/2020/1618.

[BCMS20] Benedikt Bünz, Alessandro Chiesa, Pratyush Mishra, and Nicholas
Spooner. Proof-carrying data from accumulation schemes. In
IACR preprint archive 2020/499, 2020. https://eprint.iacr.
org/2020/499.
20

[BDFG20] Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. HaloInfinite: recursive zk-snarks from any additive polynomial commitment scheme. In IACR preprint archive 2020/1536, 2020.
https://eprint.iacr.org/2020/1536.
[BGH19]Sean Bowe, Jack Grigg, and Daira Hopwood. Recursive proof
composition without a trusted setup. In IACR preprint archive
2019/1021, 2019. https://eprint.iacr.org/2019/1021.

[BLH+ ]

Sean Bowe, Ying Tong Lai, Daira Hopwood, Jack Grigg, andSteven Smith. Halo 2. https://github.com/zcash/halo2.

[BMRS20] Joseph Bonneau, Izaak Meckler, Vanishree Rao, and Evan Shapiro.
Coda: Decentralized cryptocurrency at scale. In IACR preprintarchive 2020/352, 2020. https://eprint.iacr.org/2020/352.
[BSCR+ 19] Eli Ben-Sasson, Alessandro Chiesa, Michael Riabzev, Nicholas
Spooner, Madars Virza, and Nicholas P. Ward. Aurora: Transparent succinct arguments for R1CS. In Y. Ishai and Vincent Rijmen,
editors, EUROCRYPT 2019, volume 11476 of LNCS. Springer,
2019.
[CCW18]

Alessandro Chiesa, Lyn Chua, and Matthew Weidner. On cyclesof pairing-friendly elliptic curves. In SIAM Journal on Applied
Algebra and Geometry, volume 3(2), 2018.

[CFF+ 20]

Matteo Campanelli, Antonio Faonio, Dario Fiore, Anaï s Querol,and Hádrian Rodríguez. Lunar: a toolbox for more efficient andupdatable zkSNARKs and commit-and-prove extensions. In IACR
preprint archive 2020/1069, 2020. https://eprint.iacr.org/
2020/1069.

[CHM+ 20] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra,
Noah Vesely, and Nicholas Ward. Marlin: Preprocessing zkSNARKs with universal and updatable SRS. In EUROCRYPT
2020, volume 12105 of LNCS, 2020.
[CT10]

Alessandro Chiesa and Eran Tromer. Proof-carrying data andhearsay arguments from signature cards. In ICS‘10. Tsinghua University Press, 2010.

[GGPR13] Rosario Gennaro, Craig Gentry, Brian Parno, and Mariana
Raykova. Quadratic span programs and succinct NIZKs without
PCPs. In Nguyen P.Q., editor, EUROCRYPT 2013, volume 7881
of LNCS. Springer, 2013.
[GKO20]

Alberto Garoffolo, Dmytro Kaidalov, and Roman Oliynykov. Zendoo: a zk-SNARK verifiable cross-chain transfer protocol enabling
decoupled and decentralized sidechains. In IACR preprint archive
2020/123, 2020. https://eprint.iacr.org/2020/123.
21

[GKR+ 21] Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger,
Arnab Roz, and Markus Schofnegger. POSEIDON: A new hashfunction for zero-knowledge proof systems. In USENIX Security
Symposium 2021, 2021.
[GM17]

Jens Groth and Mary Maller. Snarky Signatures: Minimal signatures of knowledge from simulation-extractable snarks. In
Shacham H. Katz J., editor, CRYPTO 2017, volume 10402 of
LNCS. Springer, 2017.

[Gro10]Jens Groth. Short pairing-based non-interactive zero-knowledge
arguments. In Abe M., editor, ASIACRYPT 2010, volume 6477 of
LNCS. Springer, 2010.

[Gro16]

Jens Groth. On the size of pairing-based non-interactive arguments. In M. Fischlin and J.S. Coron, editors, EUROCRYPT 2016,
volume 9666 of LNCS. Springer, 2016.

[GS19]

Aurore Guillevic and Shashank Singh. On the alpha value of polynomials in the tower number field sieve algorithm. In https:// hal. inria. fr/ hal-02263098 , 2019.

[Gui20]

Aurore Guillevic. A note on MNT4 and MNT6 curves: Estimationof STNFS cost. (personal communication), 2020.

[GWC19]Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru.
PLONK: Permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. In IACR preprint archive
2019/953, 2019. https://eprint.iacr.org/2019/953.

[HB21]

Ulrich Haböck and Daniele Di Benedetto. The Darlin proof carrying data protocol suite. in preparation, 2021.

[HBG]

Daira Hopwood, Sean Bowe, and Jack Grigg.
The Pasta
Curves for Halo 2 and beyond. https://electriccoin.co/blog/
the-pasta-curves-for-halo-2-and-beyond/.

[HM98]

Shai Halevi and Silvio Micali. More on proofs of knowledge. In
IACR preprint archive 1998/015, 1998. Appeared in the THEORY
OF CRYPTOGRAPHY LIBRARY and has been included in theePrint Archive. https://eprint.iacr.org/1998/015.

[MBKM19] Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. Sonic: Zero-knowledge SNARKs from linear-size universal
and updatable structured reference strings. In ACM SIGSAC Conference on Computer and Communication Security, pages 2111–
2128, 2019.
[Ol]

O1-labs. Mina Protocol. https://minaprotocol.com.
22

[PHGR13] Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova.
Pinocchio: Nearly practical verifiable computation. In in IEEE
Symposium on Security and Privacy, pages 238–252, 2013.
[SS11]

Joseph H. Silverman and Katherine E. Stange. Amicable pairs andaliquot cycles for elliptic curves. In Experimental Mathematics,
volume 20(3), 2011.

[WTS+ 18] R. S. Wahby, I. Tzialla, A. Shelat, J. Thaler, and M. Walfish.
Doubly-efficient zk-SNARKs without trusted setup. In 2018 IEEE
Symposium on Security and Privacy (SP), pages 926–943, 2018.

A

Appendix

A.1

Notation

We denote the security parameter by λ, where we throughout consider it inunary representation. A function f (λ) is negligible if for every polynomialp(λ), it holds that limλ→∞ f (λ) ⋅ p(λ) = 0, or in short f (λ) = o(1/p(λ)).
Probabilistic algorithms are denoted by capital letters A, B, etc., and wewrite y ← A(x) if an algorithm A ouputs a string y given an input stringx while using some internal random coins r uniformly sampled from {0, 1}∗ .
Whenever we need to refer to the used random coins r, we shall explicitly
write y = A(x; r). We say that A is probabilistic polynomial time (p.p.t.), if
its run time Tx,r on input x and internal random coins r is bounded by somefixed polynomial p(∣x∣) independent of the random coins, where ∣x∣ denotes thelength of its input. We say that A is expected polynomial time if the expected
run time E(Tx,r ), where the expectation is taken over all random coins r, isbounded by some polynomial in the length of the input. The interaction of
two interactive probabilistic algorithms A and B is denoted ⟨A, B⟩, where we
explicitly clarify what are the inputs and outputs of both algorithms.

A.2

Interactive arguments

Let R be a polynomial time decidable binary relation. An interactive argument
system for R consists of three probabilistic polynomial time algorithms(Setup, Prove, Vf).
Given the security parameter λ in unary representation, Setup(λ) outputs acommon reference string crs which supports all statement-witness pairs (x, w)
up to a certain maximum length N = N (λ), which we write in short (x, w) ∈RN . Given (x, w) ∈ RN , the algorithms Prove and Vf are used to interactively
reason about whether x belongs to the language defined by R or not. We
denote their interaction by tr ← ⟨Prove(x, w), Vf(x)⟩ with tr as the transcript23

of the interaction, and we assume that both algorithms have access to the crs
without explicitly declaring them as inputs. After at most polynomially many
steps the verifier accepts or rejects, and we say that tr is accepting or rejecting.
Definition 3 (Perfect completeness). An interactive argument system (Setup,
Prove, Vf) satisfies perfect completeness if
R⎡⎤⎢⟨Prove(x, w), Vf(x)⟩ RRRR crs ← Setup(λ),⎥⎢
RRR (x, w) ← A(λ), with ⎥ = 1.
Pr⎢⎥
R
RRR (x, w) ∈ R⎢ is accepting
⎥
⎣
⎦
N
R
We define knowledge-soundness in the style of [HM98]. However we do notdwell on the structure or the message distribution of the blackbox extractor.
The reason for this choice of definition is the modularity of our proof of Theorem
2, which refers to the security result on the batch evaluation argument from[BDFG20].
Definition 4 (Knowledge-soundness). An interactive argument system (Setup,
Prove, Vf) for the relation R is knowledge sound if for every x from LR andevery adversary A which makes ⟨A, Vf(x)⟩ accept with non-negligible probability ε(x) > negl(λ), there is a strict polynomial time algorithm E = E A withblackbox access to A which does at most poly(∣x∣, λ)/poly(ε) calls, and overwhelmingly outputs a witness w such that (x, w) ∈ R.
Definition 5. We say that an interactive argument system (Setup, Prove, Vf)
is an argument of knowledge, if it is perfectly complete and knowledge sound as
defined above. It is said to be succinct, if the size of the transcript is sublinear
in the size of (x, w) ∈ R.
As we do not require any trust assumptions for the setup, our definition of
zero-knowledge does not make use of trapdoors.
Definition 6 (Perfect honest verifier zero-knowledge). An interactive argument system (Setup, Prove, Vf) is perfect honest verifier zero-knowledge if there
is a p.p.t. algorithm Sim such that for every p.p.t. algorithm A,⎡ (x, w) ∈ RN⎢
Pr⎢⎢∧
⎢ A(tr′ ) = 1⎣

A.3

RRR crs ← Setup(λ), ⎤⎥RRR
RRR (x, w) ← A(crs), ⎥⎥RRR tr′ ← Sim(crs, x) ⎥⎦R
⎡ (x, w) ∈ RN⎢
= Pr⎢⎢∧⎢ A(tr) = 1⎣

RRR crs ← Setup(λ),
⎤
⎥
RRR
⎥.
RRR (x, w) ← A(crs),
RRR tr ← ⟨Prove(x, w), Vf(x)⟩ ⎥⎥⎦R

Forking Lemmas

We use the forking Lemma from [BCC+ 16] and we obtain strict polynomial
time of the sampling algorithm by truncation. Assume that (Setup, Prove, Vf)24is an (2r +1)-move public-coin argument, by which we mean that in each roundthe verifier messages are chosen uniformly at random from a sample space S.
Given a transcript tr resulting from the interaction of A( . ) with the verifier
Vf(crs, x), we denote by tr∣≤i , with i = 0, . . . , r, the partial transcript consistingof the prover and verifier messages of the first 2i + 1 moves. An (n1 , . . . , nr )tree of accepting transcripts is a tree of depth r which is rooted in a prover’s
first message tr∣≤0 and in which each node at level i ∈ {0, . . . , r − 1} represents
a partial transcript tr∣≤i−1 and has exactly ni children nodes extending thistranscript. The tree has overall K(λ) = ∏ri=1 ni leafs standing for complete
transcripts in which the verifier eventually accepts. We assume that the sizeof S grows superpolynomially in λ, so thatPr[x1 ≠ x2 ∣x1 , x2 ←$ S] > 1 − negl(λ).
Lemma 2 ([BCC+ 16]). Let (Setup, Prove, Vf) be a (2r + 1)-move public-coininteractive proof, and A a p.p.t. adversary which runs in expected time tA andsucceeds ⟨A( . ), Vf(crs, x)⟩ with non-negligible probability ε = ε(x) on public
input x. If n1 , . . . , nr ≥ 2 are such that K(λ) = ∏ri=1 ni is polynomially bounded,then there exists a p.p.t. algorithm T that calls the next message functionof A at most 2 ⋅ K(λ)/ε times and with non-negligible probability ε/2 outputs
an (n1 , . . . , nr )-tree of accepting transcripts in which all pairs of sibling-nodechallenges x1 , x2 are subject to x1 ≠ x2 .
For the sake of completeness we shortly sketch the construction of T as
claimed in Lemma 2. The tree finder algorithm T ′ from [BCC+ 16] is a rejection
sampler which is allowed to fail at every first completion of ⟨A, Vf(crs, x)⟩ ona given partial transcript tr∣≤i . It succeeds with probability
ptr∣≤i = Pr[T ′ completes subtree for tr∣≤i ]= Pr[⟨A( . ), Vf(crs, x)⟩ succeeds on tr∣≤i ].
and runs in expected polynomial timeE[# of A calls given tr∣≤i ] ≤ ni ⋅ ni+1 ⋅ . . . ⋅ nr .
Overall T ′ is of expected polynomial time calling A at most K(λ) times on
average, and T ′ succeeds in producing a complete (n1 , ..., nr )-tree of accepting transcript with probability ε. The probability that such a complete treeof accepting transcripts has collisions (i.e. two sibling challenges coincide) is
negligible, see the full version of [BCC+ 16]. Finally limiting the run time of T ′to 2 ⋅ K(λ)/ε calls of A (and returning  in that case) yields a strict polynomial
time algorithm which still succeeds with a probability of at least ε/2.
2ε. Then with probability
Lemma 3 ([BDFG20]). Let δ be such that 0 < δ ≤ 8K(λ)
at least ε/4 the tree finding algorithm T from Lemma 2 outputs a tree of accepting transcripts with the following property: For every partial transcript tr∣≤i oflength i in the tree, the conditional success probability for A( . ) continuing thepartial transcript tr∣≤i is at least δ.

25

Proof. The tree sampler T from Lemma 2 tests at most 2 ⋅ K(λ)/ε partial
transcripts tr∣≤i . Such transcript succeeds with the probability ptr∣≤i as above.
Therefore, the probability that one of these ptr∣≤i is smaller than a given δ isat most 2 ⋅ K(λ)/ε ⋅ δ. Choosing the latter of at most ε/4 yields the assertionof the lemma.
We note that the factors 1/2 in Lemma 2 and 1/8 in Lemma 3 are arbitrary.
Any other choice of these factors > 1 − 1/poly(λ) is possible.

A.4

Proof of Theorem 2

Theorem 2 is subject to Protocol 4, extended by the verification of the resulting
acc′′ = (γ, H ′′ , [TH ′′ (γ, Y )]). We refer to this extended protocol as the full
protocol. The batch evaluation proof Eval is regarded as a subprotocol, and weuse knowledge soundness and honest verifier zero-knowledge of it (Theorem 11
and Theorem 10) to infer the same properties for the full protocol.

Knowledge soundness
Assume maximum degree for the polynomial commitment scheme is d = poly(λ)
with d ≥ 2 ⋅ n + b.The proof is divided into two steps. In the first one, we special
soundness of the algebraic oracle proof. The second step uses the transcript
sampler from Lemma 2 to construct a strict polynomial time extractor fromthe strict polynomial time extractor of the batch evaluation argument.
Step 1. Special soundness.
Consider the protocol as an interactive oracle proof where the oracles are guaranteed having a degree of at most d = poly(λ). Besides the arithmetic checks
on the evaluation claims, the verifier checks the oracle for TH ′′ (γ, Y ) by reading it in full length8 and compare it against the polynomial described by H ′′as computed in the protocol. We claim that this ‘algebraic oracle proof’ is(m1 , m2 , m3 , m4 )-special sound, with
(m1 , m2 , m3 , m4 , m5 ) = (3, n, 2 ⋅ d + 1, 2, d + 1),
in the following sense: Given an (m1 , m2 , m3 , m4 , m5 )-tree of accepting transcripts with pairwise distinct verifier challenges for η ∈ F, α, β ∈ F ∖ H, λ ∈ F, γ ∈F , respectively, then
• the polynomial in the oracle from acc′dlog is the claimed reduction polynomial h(ξ⃗′ , X),• the oracles intended for TH ′ (γ ′ , Y ) and Tη (α, Y ) in fact carry the correct
polynomials, and8 Equivalently, the verifier may query the oracle at d + 1 different points and reconstructs
the polynomial from the values.

26• the polynomial y(X) = x(X) + (X ` − 1) ⋅ ŵ(X) mod (X n − 1) with ŵ(X)from [ŵ(X)] satisfies the R1CS identities (10), (11), (12).
This is true for the following reasons:• m1 = 3 pairwise distinct η1 , η2 , η3 ∈ F are sufficient to derive the R1CS
identities (10), (11), (12) from the ‘lincheck’ identity (19). (The Vandermonde matrix for different choices of η is invertible.)• m2 = n pairwise distinct α1 , . . . , αn ∈ F ∖ H allow inverting the reductionof the lincheck identity (19) to the sumcheck identity (1) by means of
the Lagrange kernel. (Recall that the sumcheck is obtained from thelincheck by applying ⟨Ln (X, α), . ⟩. By Lemma 5 the inner products forany n different values of α allow to uniquely reconstruct the lincheckpolynomial modulo (X n − 1). )• m3 = 2 ⋅ d + 1 pairwise distinct β1 , . . . , β2d+1 ∈ F ∖ H are sufficient to infer
the outer sumcheck identity on the full domain F , as well as the identity
for the first step of the inner sumcheck aggregation. (The polynomials
are of degree at most d.)• m4 = 2 distinct λ1 , λ2 ∈ F allow for reconstructing the component polynomials from their linear combination Tη⃗ (X, β) + λ ⋅ TH ′ (X, β) in the second
step of the inner sumcheck aggregation. (Again, since the Vandermondematrix is invertible.)• and m5 = d + 1 pairwise distinct γ1 , . . . , γd+1 ∈ F are sufficient to inferboth the correctness of the polynomial behind the linear combination[Tη⃗ (X, β)] + λ ⋅ [TH ′ (X, β)], and the polynomial behind the oracle inacc′dlog . (Again, all polynomials are of degree at most d.)
Step 2. Extractor.
Suppose that A is a probabilistic polynomial time adversary which succeeds
the complete verifier with non-negligible probability ε on given inputs (C, acc′C ,acc′dlog , x). As K(λ) = m1 ⋅ . . . ⋅ m5 is polynomial in λ, Lemma 2 guarantees astrict polynomial time algorithm T which calls A at most 2 ⋅ K(λ)/ε = poly(λ)
times and succeeds with a non-negligible probability of ε/2 in sampling an(m1 , m2 , m3 , m4 , m5 )-tree of accepting transcripts as needed for Step 1. Eachpartial transcript tr∣i≤5 records the messages until and including the samplingof the last verifier challenge γ, before entering the batch evaluation protocol
Eval. By Lemma 3 we may assume that for each of these partial transcripts
ε2tr∣i≤5 , the probability that A succeeds on it is at least δ = 8⋅K(λ)> negl(λ). By
knowledge-soundness of the batch evaluation argument Eval, there is a strict
polynomial time extractor which calls A at most poly(λ)/poly(δ) times on eachof the transcripts tr∣i≤5 and outputs the witness polynomials from F <d+1 [X](including commitment randomnesses) for27• [ŵ(X)], [ẑA (X)], [ẑB (X)], [Û1 (X)], [h1 (X)], [Tη⃗ (α, X)],
• [TH ′ (α′ , X)] from acc′C , as well as [Tη⃗ (X, β)], [TH ′ (X, β)],• [Tη⃗ (X, β)] + λ ⋅ [TH ′ (X, β)], and [h(ξ⃗′ , X)] from acc′dlog ,of each of the (η, α, β, λ, γ) = (ηi1 , αi2 , βi3 , λi4 , γi5 ) in the transcript tree. Thesepolynomials have values which pass all the verifier checks of the protocol. Assuming the dlog commitment is computationally binding, the witness polynomials and commitment randomnesses for [ŵ(X)], [ẑA (X)], [ẑB (X)], [Û1 (X)],[h1 (X)], as well as the witness polynomials for the accumulator commitments[TH ′ (X, β)], [h(ξ⃗′ , X)] overwhelmingly coincide for all the verifier challenges(ηi1 , αi2 , βi3 , λi4 , γi5 ), and for the same reason the polynomials for [Tη⃗ (α, X)]
do not depend on (βi3 , λi4 , γi5 ). Hence if we replace the commitments by thesepolynomials we obtain an (m1 , m2 , m3 , m4 , m5 )-tree of accepting transcripts asneeded for Step 1 to conclude that y(X) = x(X)+(X ` −1)⋅ ŵ(X) mod (X n −1)
satisfies the R1CS identities for Ck , and both acc′T and acc′dlog are correct. The
overall run-time of the extractor is strictly bounded by K(λ)⋅poly(λ)/poly(δ) =poly(λ)/poly(ε) and succeeds with a non-negligible probability of at least ε/4.
By amplification we obtain the claimed extractor for knowledge-soundness.

Zero-knowledge
Perfect honest verifier zero-knowledge of Protocol 4 is an immediate consequence of perfect honest verifier zero-knowledge of the batch evaluation argument (Theorem 11) and the same property for the coboundary outer sumcheck.
The latter is obtained from the following auxiliary lemma. The proof of it isstraightforward, and we leave it to the reader.
Lemma 4. Assume that P follows Protocol 4. Then the conditional distribution of (v1 , v2 , v3 , v4 , v5 , v6 ) = (ŵ(β), ŷA (β), ŷB (β), Û (g⋅β), Û (β), h(β)), conditional to (η, α, β), is uniform on the relation Rη,α,β of all (v1 , v2 , v3 , v4 , v5 , v6 )satisfying the outer sumcheck equationTη (α, β) ⋅ (x(β) + (β ` − 1) ⋅ v1 ) − Ln (β, α) ⋅ (v2 + η ⋅ v3 + η 2 ⋅ v2 ⋅ v3 )− v4 + v5 = v6 ⋅ (β n − 1).
Using Lemma 4 the simulator for the outer sumcheck is constructed asfollows. Given a consistent previous accumulator acc′ = (acc′C , acc′dlog ) andany circuit input x ∈ F ` , it first samples η and (α, β) uniformly from F and(F ∖ H)2 , respectively, and (v1 , v2 , v3 , v4 , v5 , v6 ) uniformly from Rη,α,β (bychoosing v1 , . . . , v5 uniformly from F and v6 as determined by the outer sumcheck equation), and then crafts arbitrary polynomials ŵ(X), ŷA (X), ŷB (X),Û (X) and h(X) of degree less than d which evaluate at X = β (and Û (X) also
at X = g ⋅ β) to the corresponding values. All these polynomials are committedusing hiding randomnesses, and the aggregation rounds Step (3) and Step (4)of Protocol 4 are performed as in an honest prover-verifier interaction. Since28

the dlog commitment scheme is perfectly hiding, the resulting conversation is
identically distributed as in an ordinary honest prover-verifier interaction for
Step (1-4). These conversations are completed by calling the simulator forthe batch evaluation argument on the collected commitments. Since the latter partial transcripts are identically distributed to an honest prover-verifierinteraction, so are the completed conversations.

A.5

Proof of Theorem 1

The proof of Theorem 1 is almost identical to that of Theorem 2, hence we only
point out the differences. We assume that the indexer polynomial rowM (X),colM (X), row.colM (X) and val.row.colM (X), M = A, B, C, as defined in Section 4 are verified against their commitments in a precomputation phase of the
protocol.
For knowledge-soundness, observe that Coboundary Marlin viewed as analgebraic oracle proof, is (m1 ,m2 ,m3 ,m4 )-special sound with
(m1 , m2 , m3 , m4 ) = (3, n, 2 ⋅ d + 1, 4 ⋅ m − 3).
Here, d = poly(λ) is the maximum degree of the oracle polynomials, n and m
are the sizes of the domains H and K, and m1 , m2 , m3 , m4 correspond to theverifier challenges η ∈ F , α, β, γ ∈ F ∖H, respectively. The reasoning for m1 , m2 ,m3 is as befor, and m2 = 4 ⋅ m − 2 by the degree of the inner sumcheck identity(24). Based on these modified soundness numbers, the strict polynomial time
extractor is constructed as in Section A.4 by using the forking lemma (Lemma2) and the extractor for the batch evaluation argument.
The proof for perfect honest verifier zero-knowledge can be taken over almost verbatim, replacing completing of the simulated transcript for the outersumcheck by an honest prover-verifier run of the inner sumcheck instead of theaggregation rounds.

A.6

Polynomial commitment schemes

We regard a polynomial commitment scheme consisting of four probabilistic
polynomial time algorithms(Setup, Com, Prove, Vf).
Given the security parameter λ, (ck, vk) ← Setup(λ) generates a common reference string consisting of a committer key ck and a verifier key vk supporting
polynomials over some finite field F having degree of at most N = N (λ), where
N is polynomial in λ. Given the committer key ck, the commitment of a polynomial p(X) of degree at most N is computed by C = Com(p(X); r), where r
denotes the used random coins. (We again omit ck from the inputs for brevity.)29

We regard (Setup, Prove, Vf) as a succinct interactive argument system for the
relationR = {((C, x, v), (p(X), r)) ∶ C = Com(p(X); r) ∧ p(x) = v},
and call the polynomial commitment scheme to satisfy completeness, zeroknowledge and witness-extended emulation if the interactive argument systemdoes. We refer to the interaction ⟨Open, Vf⟩ as opening proof for the polynomial
p(X) at the point x ∈ F .
The security notions computational binding and perfect hiding are as forgeneral non-interactive commitment schemes (Setup, Com). For the sake ofbrevity, we directly cite them applied to polynomial commitment schemes:
Definition 7 (Perfect Hiding). We say that a polynomial commitment scheme(Setup, Com, Open, Vf) is perfectly hiding if every polynomial adversary A has
no advantage over pure guessing when distinguishing the commitments of two
adversarially chosen polynomials,⎡⎤
RRR (ck, vk) ← Setup(λ),
⎢
⎥
RRR
⎢
⎥
RRR for i = 1, 2
⎢
⎥ 1
⎢ ⋆
⎥
R
Pr⎢ b = b RRRpi (X) ← A(ck, vk), deg(pi (X)) ≤ N (λ), ⎥ = .
⎢
⎥ 2
RRR
⎢
⎥
Ci ← Com(pi (X))
RRR
⎢
⎥
∗
⎢
⎥
R
⎣
⎦
RR b ←$ {0, 1}, b ← A(Cb , C1−b )Definition 8 (Computational Binding). A polynomial commitment scheme(Setup, Com, Open, Vf) is computationally binding if for every p.p.t. adversary
A, the probability to find two different messages (pi (X), ri ), i = 1, 2, having
the same commitment is negligible:⎡ Com(p1 (X); r1 ) = Com(p2 (X); r2 ) RRR⎤⎢⎥
RRR (ck, vk) ← Setup(λ),
⎥
∧
Pr⎢⎢
RRR
⎥
(r
,
p
(X),
r
,
p
(X))
←
A(ck,
vk)
R
1 1
2 2
⎢
⎥
R
(p1 (X), r1 ) ≠ (p2 (X), r2 )RR⎣⎦
= negl(λ).
We further make use the notion of a homomorphic schemes, again directly
applied to polynomial commitment schemes:
Definition 9 (Homomorphic commitment). A polynomial commitment scheme(Setup, Com, Open, Vf) with commitments in a commitment group (G, +) is homomorphic (or, linear ), if
Com(p1 (X); r1 ) + Com(p2 (X); r2 ) = Com(p1 (X) + p2 (X); r1 + r2 ).

A.7

The dlog commitment scheme from [BCMS20]

The dlog polynomial commitment scheme from [BCMS20] is an ordinary Pedersen vector commitment. Given the coefficient vector c⃗ = (ci )d−1
i=0 of a polynomial
30

p(X) from F [X] of degree at most d, its commitment is the Pedersen linear
combination
Com(p(X); r) = r ⋅ S + c0 ⋅ G0 + . . . + cd−1 ⋅ Gd−1 ,where S and (Gi ) is the committer key, and the optional hiding randomness
r is uniformly drawn from F . As in [BCC+ 16], [BBB+ 18], or [WTS+ 18], theopening proof is an inner product argument, which uses k = log(d) rounds togradually reduce the size polynomial in question by one half until ending up
with a single-coefficient instance. In the course of the reduction the committer
key is repeatedly folded into a final committer key Gf for the single-coefficient
claim, which depends linearly on the initial committer key by
Gf = h0 ⋅ G0 + . . . + hd−1 ⋅ Gd−1 ,where (hi ) are the coefficients of the reduction polynomial
k−1⃗ X) = ∏ (1 − ξk−1−i ⋅ X 2 ),
h(ξ,
i

i=0

where ξ⃗ = (ξi )k−1
i=0 are the random challenges of the reduction steps.
[BCMS20] for a detailed description.

See

Theorem 10 ([BCC+ 16, BCMS20]). Under the assumption that the dlog commitment scheme is computationally binding, the opening argument is an honest
verifier zero-knowledge (Definition 6) argument of knowledge (Definition 5).
Zero-knowledge is proven in [BCMS20]. To obtain a strict polynomial time
extractor as demanded by Definition 5, one proceeds as in [BCC+ 16] to construct an expected polynomial time extractor with average runtime µ inverse
proportional to the success probability ε of the adversary. Truncating it tostrict polynomial time 2 ⋅ µ/ε zields a running time bounded by poly(λ)/poly(ε)
calls of A and still maintains a success probability of ε/2.

A.8

The batch evaluation protocol from [BDFG20]

We give an informal description of the protocol from [BDFG20], Section 5.2,
for proving a multi-point opening claimpi (xi ) = yi ,i = 1, . . . , m,of given polynomials pi (X), i = 1, . . . , m, for a linear commitment scheme(Setup, Com, Open, Vf). The multi-point evaluation claim is equivalent to thefollowing system of algebraic identities over the set Ω = {x1 , . . . , xm },pi (X) ⋅ Lm (xi , X) − yi = 0 mod z(X),31

i = 1, . . . , m,where Lm (xi , X) is the Lagrange polynomial for Ω, and z(X) = ∏x∈Ω (X −x) isthe vanishing polynomial of Ω. A more practical system of identities is achieved
if we replace the Lagrange polynomials by their non-normalized variantzi (X) =z(X)= ∏ (X − x).
X − xi x∈Ω∖{xi }These m identities are reduced to a single identity over Ω in the usual manner:
The prover receives a random scalar ρ ←$ F from the verifier, and shows the
combined identity
m

∑ρ

i−1

⋅ (pi (X) − yi ) ⋅ zi (X) = 0 mod z(X)i=1instead. For this, the verifier provides an oracle for the quotient polynomial
q(X) in the non-modular identity
m

∑ρ

i−1

⋅ (pi (X) − yi ) ⋅ zi (X) = q(X) ⋅ z(X),i=1

which is probed at a fresh random point x ←$ F . This identity is verified byi−1
showing that the linear combination ∑m⋅ zi (x) ⋅ pi (X) − z(x) ⋅ q(X) opens
i=1 ρ
m
i−1
at x to the expected value v = ∑i=1 ρ ⋅ yi ⋅ zi (x).
Theorem 11 ([BDFG20], Theorem 6). Assume that the commitment scheme
is computationally binding. If the opening argument for the polynomial commitment scheme is a perfect honest verifier zero-knowledge argument of knowledge(Definition 5), then the same holds for the batch evaluation protocol.

A.9

Segmentation of linear commitment schemes

Segmentation of a homomorphic polynomial commitment scheme is a usefultechnique to improve the computational effort of the prover at the cost ofincreasing the commitment size9 . One chooses an undersized committer key
ck = (G0 , . . . , Gs−1 ), where the segment size s is typically magnitudes smaller
than the targeted maximum degree d, and extends its domain beyond degrees − 1 by decomposing a polynomial p(X) intop(X) = p0 (X) + X s ⋅ p1 (X) + . . . + X (k−1)⋅s ⋅ pk (X),with each pi (X), i = 1, . . . , k, of degree at most s. (If d is the degree ofp(X) then the number k of segment polynomials is equal to ⌈(d + 1)/s⌉.) The
commitment of p(X) is then defined as the vector of the commitments of its
segment polynomials using ck,
Com(p(X)) ∶= (Com(p0 (X)), . . . , Com(pk (X))) .
9 We learned this technique from [Ol] but believe that it is commonly known.

32

Every evaluation claim p(x) = v of the full-size polynomial is translated to thesame claim on the linear combination of its segment polynomials,
LCx (p0 (X), . . . , pk (X)) = p0 (X) + xs ⋅ p1 (X) + . . . + x(k−1)⋅s ⋅ pk (X),
which is efficiently proven by leveraging the homomorphic property of thescheme.

A.10

Facts on the Lagrange kernel

Let H = {x ∶ xn − 1 = 0} be an order n subgroup of the multiplicative group ofa finite field F . The Lagrange kernel
Ln (X, Y ) =n−1
1⋅ (1 + ∑ X i ⋅ Y n−i )ni=1

is the unique bivariate symmetric polynomial of individual degree at most n−1,such that for y ∈ H the function L(X, y) restricted to H equals the Lagrangefunction Ly (X), which evaluates to one at X = y, and zero otherwise. The
kernel has the succinct representation
Ln (X, Y ) =1 Y ⋅ ZH (X) − X ⋅ ZH (Y )
⋅
,
n
X −Y

where ZH (X) = X n − 1 is the vanishing polynomial of H. Lagrange kernels
represent point evaluation, as characterized by the following simple Lemma.
Lemma 5. Suppose that H ⊂ F ∗ is a multiplicative subgroup of order n andp(X) is a polynomial of degree deg(p(X)) ≤ n − 1. Then for every z in F ,⟨Ln (X, z), p(X)⟩H = ∑ Ln (z, x) ⋅ p(x) = p(z).
x∈HProof. Since p(X) = ∑y∈H p(y) ⋅ Ln (X, y), it suffices to show the claim forp(X) = Ln (X, y), with y ∈ H. By the property of Ln (X, y), we have ⟨Ln (X, z),
Ln (X, y)⟩H = Ln (y, z), which by symmetry is equal to Ln (X, y) at X = z. This
completes the proof of the Lemma.
Marlin [CHM+ 20] uses the generalized derivativeuH (X, Y ) =ZH (X) − ZH (Y )X −Yinstead of Ln (X, Y ) (again as element from F [X, Y ]/⟨X n − 1, Y n − 1⟩). For thegeneralized derivative a similar inner product formula holds: For every z ∈ F ,⟨uH (X, z), p(X)⟩H = ⟨uH (X, X) ⋅ LH (X, z), p(X)⟩H= ⟨Ln (X, z), uH (X, X) ⋅ p(X)⟩H = p∗ (z),where p∗ (X) = uH (X, X) ⋅ p(X) mod (X n − 1).
33