Recursive Proof Composition without a Trusted Setup

Abstract

Non-interactive arguments of knowledge are powerful cryptographic tools that can be used to demonstrate the faithful execution of arbitrary computations with publicly verifiable proofs. Increasingly efficient protocols have been described in recent years, with verification time and/or communication complexity that is sublinear in the size of the computation being described. These efficiencies can be exploited to realize recursive proof composition: the concept of proofs that attest to the correctness of other instances of themselves, thereby allowing large computational effort to be incrementally verified. All previously known realizations of recursive proof composition have required a trusted setup and cycles of expensive pairing-friendly elliptic curves. We obtain and implement Halo, the first practical example of recursive proof composition without a trusted setup, using the discrete log assumption over normal cycles of elliptic curves. In the process we develop several novel techniques that may be of independent interest.

Keywords: recursive proofs · incrementally verifiable computation · zero knowledge

1 Introduction

Proofs of knowledge [GMR89], introduced by Goldwasser, Micali and Rackoff, allow us to demonstrate knowledge of a satisfying witness to some NP statement. If these proofs also do not reveal anything about the witness we refer to them as zero-knowledge proofs of knowledge. The works of Kilian, Micali and others showed that proofs of knowledge could be non-interactive, and that these proofs could even be smaller than the statement being proven. [Kil92, Mic00, BFM88, BSMP91] In the decades since, significant reductions in the size and verification time of such protocols have been made, culminating in zero-knowledge succinct non-interactive arguments of knowledge, or zk-SNARKs for short. Today, the most efficient zk-SNARKs require pairing-friendly elliptic curves and trusted setup assumptions as in [Gro16] but in return admit small, constant-size proofs with constant-time verification.

One of the motivating use cases for zk-SNARKs is the application of verifiable computation [GGP10], whereby computations can be delegated to an untrusted third party who returns the result as well as a cryptographic proof that the result is correct. Ideally this proof would be asymptotically smaller and less expensive to check than the computation itself, a property of zk-SNARKs that we call succinctness. A direct consequence of a succinct argument is the concept of incrementally verifiable computation [Val08] in which proofs not only attest to the correct execution of a computation but also, by exploiting succinctness, the validity of a previous proof. In this way a large and virtually unbounded amount of computation can be verified with a single proof, and with this proof alone we may extend the computation with further proofs.

As a concrete motivation for incrementally verifiable computation, consider a blockchain network that requires all participants in the network to download the entire history of the blockchain and validate each individual state transition (transaction) merely in order to validate and process new state changes. SNARKs allow us to partially address this scalability problem by outsourcing some of these verification steps to a third party. However, the participant still must download and check each proof. Incrementally verifiable computation solves this issue, allowing a single proof to inductively demonstrate the correctness of many previous proofs. The participant in the blockchain network need only download the current state of the network as well as a single proof that this state is correct. Further proofs of state changes can be constructed with the latest proof alone, allowing active participants to prune old state changes.

We can obtain incremental verifiable computation via recursive proof composition, i.e. proofs that can feasibly attest to the correctness of other instances of themselves. These proofs can be used to ensure the satisfaction of compliance predicates between old and new states, leading to concepts such as proof-carrying data [CT10] which can be extended to obtain verifiable distributed computations as in [BCCT13]. The first practical realization of recursive proof composition was shown in [BCTV14] and relies on SNARKs built over pairing-friendly elliptic curves. Elliptic curve groups are typically instantiated over a base field \mathbb{F}_p, but these groups are often of a prime order q \neq p so that the SNARK construction, which demonstrates satisfiability of an arithmetic circuit over the scalar field \mathbb{F}_q, cannot efficiently encode the \mathbb{F}_p arithmetic needed to verify its own proofs. The authors of [BCTV14] sidestep this issue by constructing a 2-cycle of pairing-friendly elliptic curves such that the base field of either curve is the scalar field of the other. Unfortunately, only a single family of pairing-friendly curves is known to admit cycles of this form [CC18], and due to their low embedding degrees secure curves in this family must be constructed over large (780-bit) fields, disturbing performance. Perhaps more importantly, all known pairing-based SNARKs require a trusted setup.

In theory it should be possible to instantiate recursive proof composition using any zk-SNARK, and in recent years protocols such as STARKs [BBHR18] offer alternatives to pairing-based SNARKs that do not require trusted setups. However, recursive proof composition has never been practically realized with these protocols due to large constants; for example STARKs have proofs that are hundreds of kilobytes in size even for relatively simple computations.

1.1 Our Contributions

We present Halo, the first practical realization of recursive proof composition without a trusted setup. As in [BCTV14], we use a cycle of elliptic curves such that proofs constructed with one curve can efficiently verify proofs constructed over the other. However, neither curve is pairing-friendly; the cycle consists of normal 255-bit prime-order curves that are conjectured to approach the 128-bit security level. Such cycles are easy to construct, as discussed in Section 6.1. Proof size and verification time in our protocol does not increase with the depth of recursion.

Polynomial Commitments with Amortized Succinctness   In Section 3 we present a new polynomial commitment scheme based on the inner product argument of [BCC+16, BBB+18], inspired by a similar protocol from [WTas17]. We make a novel observation that, by exploiting the smooth structure of vectors that the verifier must work with, we can amortize away (across many proofs) the linear-time verification operation for commitment openings with the assistance of an untrusted third party “helper.” In particular, instead of performing a linear-time operation for each commitment opening proof, the helper provides the claimed output of these linear-time operations for each proof and then uses a new argument to demonstrate that every claimed output was correct. This new argument requires that the verifier perform the same linear-time operation, but this time only once for the entire batch of proofs. This strategy allows us to build proofs for arithmetic circuit satisfiability in which the marginal verification time is logarithmic in the size of the circuit, improving asymptotically over Bulletproofs [BBB+18]. This is similar to the helped variant of the Sonic protocol [MBKM19, Section 8], except that our approach avoids the need for a trusted setup.

Nested Amortization   All previously known attempts at achieving recursive proof composition have followed a similar strategy: build a fully succinct, non-interactive argument system and then construct a verification circuit for this system. Due to the succinctness property, at some threshold the verification circuit will be smaller than the size of the circuit being checked, allowing arbitrary-depth recursion to be achieved. Argument systems based on elliptic curve groups have the smallest communication complexity known in the literature, but currently they either require trusted setups (as in all pairing-based SNARKs) or have linear-time verifiers (as in Bulletproofs [BBB+18]) and so are not fully succinct.

Our primary contribution is a novel approach for reducing the verification circuit size by exploiting the amortization strategy explained previously. In short, the verification circuit never performs linear-time operations itself, but rather takes the input and (claimed) output of the linear-time operation to be public inputs to the circuit, i.e. they are encoded in the statement being proven. The circuit proceeds on the assumption that the claimed output is correct and so the circuit is sublinear in size. This effectively defers the full verification of the “inner” proof to the verifier, who must also perform a similar linear-time operation to check the “outer” proof. Using the amortization argument described previously, the verifier can collapse these two computations together into one with the assistance of a helper. In the recursive context we simply embed the verifier of this amortization argument at each depth of the recursion so as to continually collapse the cost of verifying arguments. The linear-time verification operation is thus only performed once at the end of the recursive chain, and never as part of the verification circuit itself, bypassing the conventional need for a fully succinct argument and in fact avoiding the need for pre-processing.

Implementation   We fully implement our protocol in Section 6 to demonstrate its practicality and assist in comparison with future work. In the process, we describe a 2-cycle of elliptic curves – which we refer to as Tweedledum and Tweedledee, respectively – with attractive performance and security. We instantiate an argument for arithmetic circuit satisfiability over each elliptic curve group, exploiting their cyclic nature to efficiently express verification circuits as in [BCTV14]. The curves we choose are also specifically designed to support certain endomorphisms which we exploit to reduce the size of our verification circuit in various novel ways described in Section 6.2, which are likely of independent interest.

1.2 Concurrent Work

In concurrent work, Fractal [COS19] is a proposed recursive zero-knowledge protocol based on recent efficient low-degree testing techniques, with plausible post-quantum security and full succinctness. Our work is not fully succinct (in that the verifier’s work is linear in the circuit size) but our fully-recursive proofs are 3.5 KiB in size, compared to Fractal’s which are over 120 KiB in size at the 128-bit security level. Further, Halo’s recursion threshold^1 is less than 2^{17} multiplication gates — at least an order of magnitude smaller than Fractal’s — which has the potential for substantially reducing proving time/memory requirements.

Supersonic [BFS19] is a recent zk-SNARK based on groups of unknown order, which does not require a trusted setup. It is not clear to us if recursion can be practically achieved using this scheme or, if so, how competitive it would be with our results.

^1 The recursion threshold is the number of (multiplication) gates in the smallest circuit that can achieve arbitrary-depth proof composition.

2 Preliminaries

We take \lambda as our security parameter, and unless explicitly noted, all algorithms and adversaries are probabilistic interactive Turing machines that run in polynomial time in this security parameter. We use \mathrm{negl}(\lambda) to describe a function that is negligible in \lambda.

2.1 Zero-Knowledge Arguments of Knowledge

Zero-knowledge proofs of knowledge allow a prover \mathcal{P} to demonstrate knowledge of a witness w such that (x,w) \in \mathcal{R} for a polynomial-time decidable relation \mathcal{R} and some statement x, without revealing any information about w to the verifier \mathcal{V} of the proof except that which can be inferred from the truth of the statement. We’ll write relations in the form \{(\text{statement}; \text{witness}) : \text{predicate}\}.

We will work with arguments of knowledge which assume computationally bounded provers. We will model \mathcal{P}, \mathcal{V} as interactive algorithms, with a preliminary algorithm Setup that produces a common reference string \sigma. We will denote the transcript of the interaction as \langle \mathcal{P}(\sigma, x, w), \mathcal{V}(\sigma, x; \rho) \rangle, with the verifier’s internal randomness \rho sometimes being omitted.

2.2 Groups

We use the notation \mathbb{G} for a group of prime order p, and \mathbb{F}_p to denote its scalar field. We will often write the field as \mathbb{F} if the size of the field is implied or unimportant. Rather than drawing verifier challenges from \mathbb{F}^{\times} we will draw them instead from a challenge space \mathbb{I} \subset \mathbb{F}^{\times} that is of size 2^{\lambda}.

We use uppercase letters to denote group elements, and lowercase letters to denote scalars. Group operations are written additively, and scalar multiplication is denoted by [a] G for a \in \mathbb{F} and G \in \mathbb{G}. The additive identity in \mathbb{G} is written as \mathcal{O}. We use boldface variable names for vectors, such that \mathbf{a} is a vector of scalars and \mathbf{G} is a vector of group elements. All vectors are zero-indexed unless explicitly noted.

We write the inner product a_0b_0 + a_1b_1 + \cdots + a_{n-1}b_{n-1} of scalar vectors \mathbf{a}, \mathbf{b} \in \mathbb{F}^n, as \langle \mathbf{a}, \mathbf{b} \rangle. Similarly we write the multiscalar multiplication [a_0]G_0 + [a_1]G_1 + \cdots + [a_{n-1}]G_{n-1} of a scalar vector \mathbf{a} \in \mathbb{F}^n with a vector of group elements \mathbf{G} \in \mathbb{G}^n, as \langle \mathbf{a}, \mathbf{G} \rangle. We will sometimes write \mathbf{G}_{\mathrm{lo}} or \mathbf{G}_{\mathrm{hi}} to refer to the first half or second half of a vector of group elements or scalars.

3 Polynomial Commitments

Polynomial commitment schemes [KZG10] form a fundamental building block in many modern arguments of knowledge. [MBKM19, CHM+19, GWC19, BFS19] In these schemes, a prover can construct commitments to polynomials and then later provably evaluate the committed polynomials at arbitrary points. We present a univariate polynomial commitment scheme (\mathsf{Setup}, \mathsf{Commit}, \mathsf{Open}, \mathsf{VerifyOpen}) based on the multivariate scheme of [WTas17], which is itself a variant of the inner product argument first presented in [BCC+16], with adaptations from Bulletproofs [BBB+18].

First, for a given degree bound d-1 we define \mathsf{Setup}(1^\lambda, d) as an algorithm that produces a common reference string \sigma = (\mathbb{G}, \mathbb{F}_p, \mathbf{G}, H) for group \mathbb{G} of prime order p, with random \mathbf{G} \in \mathbb{G}^d and H \in \mathbb{G}. Let \mathsf{Commit} be defined as

for blinding factor r, where \mathbf{a}_i \in \mathbb{F} is the coefficient for the ith degree term of p(X), and p(X) \in \mathbb{F}_p[X] is of maximal degree d-1. We will sometimes omit the blinding factor r if it is either implicit or unnecessary. This is a Pedersen vector commitment to the polynomial coefficients, and we remark that such commitments are perfectly hiding and additively homomorphic: \forall\, a, b, r, s \in \mathbb{F}_p and p(X), q(X) \in \mathbb{F}_p[X] we have

We will have (\mathsf{Setup}, \mathsf{Open}, \mathsf{VerifyOpen}) be a PSHVZK argument of knowledge for the relation

which will allow a prover to demonstrate to a verifier that the polynomial contained “inside” the commitment P evaluates to v at x, and moreover, that the committed polynomial has maximum degree d-1.

3.1 Protocol Description

The protocol takes the polynomial commitment P, point x, and claimed evaluation v as common inputs. In the first move the verifier \mathsf{VerifyOpen} sends a random group element U \in \mathbb{G}. Both parties compute

and begin an argument (described next) to demonstrate that the prover \mathsf{Open} knows \mathbf{a} \in \mathbb{F}_p^d and r, v' \in \mathbb{F}_p such that

and that v' = \langle \mathbf{a}, (1, x, x^2, \ldots, x^{d-1}) \rangle. As the prover did not know U in advance, this establishes that v = v'.

Modified Inner Product   Bulletproofs [BBB+18] presents a variant of the inner product argument [BCC+16] in which a prover aims to convince a verifier that they know \mathbf{a}, \mathbf{b} \in \mathbb{F}^d such that

for some given P', and random generators \mathbf{G}, \mathbf{H} \in \mathbb{G}^d, U \in \mathbb{G}. We use a variant of this argument in which the second vector \mathbf{b} = (1, x, x^2, \ldots, x^{n-1}) is fixed for the given choice of x, and known to both the prover and verifier. As a result no vector \mathbf{H} is necessary. Further, we allow an additional generator H to serve as a mechanism for perfectly blinding both prover messages and the commitment P' itself.

Assume d = 2^k for k > 0. Initializing for the prover \mathbf{G}' := \mathbf{G}, \mathbf{a}' := \mathbf{a}, \mathbf{b}' := \mathbf{b}, we will proceed in k rounds of interaction, where in the jth round (starting with j = k and finishing with j = 1) the prover sends

with random blinding factors l_j, r_j \in \mathbb{F}_p. The verifier responds with a random challenge u_j \in \mathbb{I} and the prover computes

for the next round. After the final round, \mathbf{G}', \mathbf{a}', \mathbf{b}' are each of length 1. Note that the verifier can compute G = \mathbf{G}'_0 as \langle \mathbf{s}, \mathbf{G} \rangle and b = \mathbf{b}'_0 as \langle \mathbf{s}, \mathbf{b} \rangle where \mathbf{s} has a binary counting structure arising from the fact that in each round the inverted challenges are used to scale bases in the first half \mathbf{G}'_{\mathrm{lo}}, while the ordinary challenges scale the bases in the second half \mathbf{G}'_{\mathrm{hi}}.

The verifier next computes

and the prover proceeds to demonstrate knowledge of a=\mathbf{a}'_0 and synthetic blinding factor r'=\sum_{j=1}^k(l_ju_j^2)+r+\sum_{j=1}^k(r_ju_j^{-2}) such that

which establishes the claim that v = v' = \langle \mathbf{a}, \mathbf{b} \rangle as described in [BBB+18, Section 3].

Zero-Knowledge Opening   The prover demonstrates knowledge of a, r' \in \mathbb{F}_p such that Equation 2 is satisfied, without revealing a, r', in order to establish the claim without revealing anything else about the committed polynomial. We use a generalized Schnorr protocol that is modified from the protocol in [WTas17, Appendix A.3] to improve efficiency.

The prover begins by sampling random d, s \in \mathbb{F}_p and sending

which the verifier responds to with random challenge c \in \mathbb{I}. The prover now sends

and the verifier accepts if [c]\, Q + R = [z_1]\,(G + [b]U) + [z_2]\,H.

3.2 Amortization Strategy

The polynomial commitment scheme just described suffers from an undesirable asymptotic property: although the communication complexity is logarithmic in the degree bound, the verifier must compute G = \langle \mathbf{s}, \mathbf{G} \rangle and b = \langle \mathbf{s}, \mathbf{b} \rangle to accept the argument. One of our novel observations is to exploit the structure of \mathbf{s} and \mathbf{b} by defining a polynomial

such that b = \langle \mathbf{s}, \mathbf{b} \rangle = g(x, u_1, u_2, \ldots, u_k) which can be computed by the verifier in logarithmic time. This alone seems uninteresting, as computing G still requires a linear-time multiscalar multiplication. However, observe that

which suggests the following strategy: instead of the verifier computing G itself for multiple (independent) arguments, it can ask an untrusted third-party “helper” to compute each G_1, G_2, \ldots, G_m for m separate arguments and provide an argument that each are correct by demonstrating that a random linear combination of the commitments opens at a random point to a value that the verifier can compute in time O(m \log(d)). Due to the degree bound of the polynomial commitment scheme the helper convinces the verifier with high probability (given a large enough field) only if the claimed commitments are correct. This new argument itself requires an invocation of the polynomial commitment opening protocol, and so the verifier still must ultimately perform a linear-time operation. However, the verifier has traded m linear-time operations for one, with a marginal cost that is logarithmic in the degree bound. This is of crucial importance for our later techniques.

4 Nested Amortization

The general approach for achieving recursive proof composition is to first obtain a non-interactive argument of knowledge for arithmetic circuit satisfiability (i.e. \mathcal{C}(x, w) = 1 for auxiliary input w and public input x), and then to encode the verification algorithm for this argument into such an arithmetic circuit. Assuming that the verification circuit for a proof is sublinear in the size of the circuit that the proof reasons about, then at some threshold it will be possible to recursively verify proofs. In our setting we do not have a protocol which can be fully verified in sublinear time, and so naively applying this strategy will not yield results beyond fixed-depth composition. Instead, we devise a novel technique which allows us to avoid fully verifying proofs at each layer of the recursion, leveraging the fact that our protocol in Section 5 has sublinear marginal verification time and logarithmic proof size.

Arithmetic circuits are often encoded into systems of constraints such that, given a satisfying assignment of variables (the prover’s witness), the satisfaction of the constraint system implies the satisfiability of the circuit. The inherent non-determinism in this process means that some expensive operations can be performed more efficiently when the prover is allowed to assist. As an example, in circuits where a field inversion of a variable u must be computed, rather than exponentiating “in the circuit” (u^{p-2} which requires \log(p) multiplication constraints), the prover can instead witness v = u^{-1} and show that it is the correct inverse with the single multiplication constraint uv = 1. We will exploit this non-determinism in a slightly different way: when our circuit contains an expensive fixed operation f that is invoked with some input x we will instead allow the prover to witness y = f(x) and then take (x, y) as public inputs to the circuit. The circuit can then proceed under the assumption that y is correct, delegating the responsibility of checking the correctness of y to the verifier of the proof.

In the context of proof composition, we apply this optimization so that a verification circuit for a proof will not perform any linear-time (or otherwise expensive) operation f but rather take their inputs and the prover’s alleged outputs (x, y) as public inputs to its own circuit. Observe that as proofs are continually composed, increasing instances of (x, y) accumulate because the verification circuit will not check them but rather continually delegate these checks to its verifier. In order to prevent this runaway cost we introduce an amortization strategy: given instances (x, y) and (x', y'), the prover will provide a non-interactive proof that y = f(x) and y' = f(x') as a witness to the verification circuit, and the verification circuit will check this proof. In order to fully check this amortization proof the verification circuit may need to perform a linear-time (or otherwise expensive) operation. However, if this operation is equivalent to invoking f then the verifier has collapsed the two instances (x, y) and (x', y') into a single fresh instance (x'', y''), allowing us to continually amortize away the cost of invoking f as proofs are composed. It is only “outside” of the circuit that f is invoked once by the ultimate verifier, demonstrating the correctness of the entire underlying tree of proofs by induction. We refer to this strategy as “nested amortization.”

The public-coin PSHVZK argument of knowledge for arithmetic circuit satisfiability described in Section 5 is designed to exploit this nested amortization strategy, leveraging the polynomial commitment amortization technique we explored in Section 3.2. The setting is described as a stream of arguments from the prover to the verifier, where the verifier will maintain logarithmic-size state and perform logarithmic-time operations to partially verify each proof in sequence. Finally, at the end of a stream of proofs the verifier will choose to accept or reject all of them simultaneously in linear time. By applying the Fiat–Shamir heuristic [FS86] in Section 6 we can transform this argument into a non-interactive zero-knowledge argument of knowledge. The result is then grafted to the nested amortization technique, where the “state” maintained by the verifier is merely the deferred values that are shepherded through public inputs. This leads directly to a recursive proof of arbitrary depth^2 where the verifier outside of the circuit will be responsible only for checking the correctness of the verifier state once, with a linear-time operation that is never performed inside the circuit.

^2 We remark that, theoretically, the knowledge extractor requires a number of transcripts from the prover that increases exponentially as the depth increases. However, there are no known attacks and this concern is often disregarded in practice. In any case, applications can sometimes sidestep this theoretical concern by restricting to a fixed-depth tree of proofs as in [BCCT13].

5 Main Argument

The main argument of Sonic [MBKM19] allows a prover to demonstrate the satisfiability of an arithmetic circuit (e.g., \mathcal{C}(x, w) = 1) for some public input x and auxiliary input w. Our main protocol is a variant of Sonic that is adapted to the polynomial commitment scheme described in Section 3. We will work within a restricted setting to aid later exposition: the circuit \mathcal{C} is fixed, and the prover will repeatedly interact with the verifier to engage in multiple arguments in sequence. Our goal will be for the verifier to perform logarithmic marginal work in choosing to accept or reject all of the arguments simultaneously, leveraging the technique described in Section 3.2 as well as an analogous technique described in Section 8 of [MBKM19].

In all of the following let N, Q, k be integers such that d = 4N = 2^k and 3Q < d. Let the common reference string \sigma \leftarrow \mathsf{Setup}(1^\lambda, d) be shared between the prover and verifier.

5.1 Central Argument

The prover aims to demonstrate that \mathcal{C}(x, w) = 1 for public input x and auxiliary (witness) input w without revealing w. It will do so by demonstrating that a system of arithmetic constraints that encodes \mathcal{C} is satisfied for witness \mathbf{a}, \mathbf{b}, \mathbf{c} \in \mathbb{F}^N known only to the prover and some instance \mathbf{k} \in \mathbb{F}^Q which encodes the public inputs. This system of constraints consists of N multiplication constraints, where the ith such constraint is of the form

and Q linear constraints, where the qth such constraint is of the form

for some fixed \mathbf{u}_q, \mathbf{v}_q, \mathbf{w}_q \in \mathbb{F}^N that encode \mathcal{C}. Just as in [MBKM19], we will embed all of these constraints into a single equation in formal indeterminate Y

where we define the polynomials

such that given a choice of \mathbf{a}, \mathbf{b}, \mathbf{c}, \mathbf{k} we have that Equation 4 holds at all points when the constraint system is satisfied. Given a second formal indeterminate X let us define the polynomials

such that the constant term of t(X,Y) is exactly the left-hand side of Equation 4. Observe that because r(X,Y) = r(XY,1) the prover can commit to r(X,Y) using a univariate polynomial commitment scheme, i.e. \mathsf{Commit}(\sigma, r(X,1)). The remaining polynomials are fully determined by this choice of r(X,Y) and do not depend on the witness \mathbf{a}, \mathbf{b}, \mathbf{c}. The general strategy is for the prover to send a commitment to r(X,Y) and then to demonstrate that the constant term of t(X,Y) is the zero polynomial.

5.2 Full Protocol

We now bring together a full description of the protocol. The prover and verifier will engage in a series of PSHVZK arguments of knowledge for the relation \mathcal{R} defined as

where the verifier will not immediately choose to accept or reject each individual argument, as it requires the computation of G_{\text{new}}, S_{\text{new}} each requiring linear time in |\mathcal{C}|. Instead the prover will take the values as G_{\text{old}}, S_{\text{old}} for the next argument and suspend its decision to accept. After the final argument the verifier will check the values G_{\text{new}}, S_{\text{new}} in linear time.

6 Implementation

We apply the Fiat–Shamir heuristic to the protocol from Section 5 to obtain a non-interactive argument of knowledge that is secure in the random oracle model and has perfect zero knowledge. The verifier’s challenges are substituted for outputs of a secure hash function over the transcript of messages sent previously by the prover. We instantiate this scheme in the uniform random string model by taking the group elements in \sigma as outputs of a hash function that models a random function.

In practice we will use the Rescue [AABS19] algebraic hash function for prime fields to obtain verifier challenges. We instantiate it with a duplex sponge construction [BDPV12] where prover messages are “absorbed” and verifier challenges are “squeezed.”

6.1 Cycles of Curves

The partial verification operation for a proof (which is encoded in the circuit) is dominated by group operations. If we were to instantiate our protocol over an arbitrary elliptic curve E over base field \mathbb{F}_p, for security reasons we must obtain a group of prime order q \neq p. This presents a challenge as our protocol will demonstrate arithmetic circuit satisfaction over the scalar field \mathbb{F}_q, and simulating \mathbb{F}_p arithmetic over a distinct field is expensive. This efficiency problem was addressed in [BCTV14] by finding a “2-cycle” E_p, E_q of elliptic curves, constructed over the base fields \mathbb{F}_p and \mathbb{F}_q respectively, such that \#E_p = q and \#E_q = p.

We performed a search for the 2-cycle used in our implementation, seeking curves that had highly 2-adic scalar fields. We affectionately refer to the resulting curves as Tweedledum and Tweedledee [Car72]:

where p and q are 255-bit primes:

Both curves have 126-bit security against Pollard rho attacks.^3

^3 A conservative estimate of the available improvement to Pollard rho is that on a group of prime order q with an automorphism group of order 6, the attack cost is \sqrt{\frac{\pi q}{12}}, as compared to \sqrt{\frac{\pi q}{4}} using only the negation map as described in [BLS11]. That is, the maximum speed-up is only a factor of \sqrt{3} \approx 1.732 for a given success probability.

6.2 Endomorphism-based Optimizations

Our method of searching for 2-cycles finds curves E/\mathbb{F}_p with an endomorphism \phi defined on \mathbb{F}_p-rational points by \phi((x,y)) = (\zeta_p x, y), where \phi(P) = [\zeta_q]P for some \zeta_q \in \mathbb{F}_q of multiplicative order 3. We leverage this endomorphism to optimize the multiplication of group elements by challenges, which is the dominating cost of partial proof verification in the circuit.

Algorithm 1 can be implemented with 3.5 multiplication constraints per bit of \mathbf{r}. We show in Appendix C that this algorithm is equivalent to computing [n(\mathbf{r})]P where for the Tweedledum and Tweedledee curves with \lambda = 128, n:\{0,1\}^\lambda \mapsto \mathbb{I} is injective.

6.3 Other Optimizations

In the polynomial commitment scheme described in Section 3 the verifier samples a challenge u in each round of the modified inner product argument. The verifier will compute [u^{-2}]L and [u^2]R in each round to check the proof. It is possible for the prover to witness L' = [u^{-2}]L and then in the circuit multiply L' by u^2 to obtain the expected value L, demonstrating the correctness of L'. In order to improve the performance of computing [u^2]P for arbitrary P \in \mathbb{G} we modify the protocol so that the verifier samples its challenge as u^2 instead.

6.4 Evaluation

We obtain benchmarks for our protocol on a 16-core Intel i9-7960X CPU @ 2.80 GHz, using 16 threads. Recursion is achieved at a cross-over point that is just below 2^{17} multiplication gates. Fully recursive proofs in our protocol are at least 3.5 KiB in size.

7 Conclusion

We devised a novel strategy (nested amortization) for achieving a practical realization of recursive proof composition without a trusted setup. After several optimizations we obtain a fully recursive proof that is only 3.5 KiB in size at the 128-bit security level. We implement our scheme to show that it is efficient to create and verify proofs on consumer hardware.

In the process we obtained a modified variant of the polynomial commitment scheme from [WTas17] and observed a new technique for amortizing away the cost of verifying many inner product arguments. We also devised a proving system with marginal verification time that is logarithmic in the size of the circuit, improving asymptotically on Bulletproofs [BBB+18] and realizing the “helped” mode of Sonic [MBKM19] without the need for pairings or trusted setups.

7.1 Future Work

We remark that our nested amortization technique can be applied using cycles of elliptic curves such that only one curve is pairing-friendly, and a pairing-based SNARK can be constructed on one end of the cycle instead; this is trivial to obtain using Barreto–Naehrig [BN05] curves with an embedding degree of 12, which allows for the use of smaller fields to improve performance compared to MNT4/MNT6 cycles proposed in [BCTV14].

References

• [AABS19] Aly, A., Ashur, T., Ben-Sasson, E., Dhooghe, S., Szepieniec, A.: Efficient symmetric primitives for advanced cryptographic protocols. ePrint 2019/426.
• [BN05] Barreto, P., Naehrig, M.: Pairing-friendly elliptic curves of prime order. ePrint 2005/133.
• [BBHR18] Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. ePrint 2018/046.
• [BCTV14] Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Scalable Zero Knowledge via cycles of elliptic curves. CRYPTO 2014. ePrint 2014/595.
• [BL] Bernstein, D., Lange, T.: SafeCurves: choosing safe curves for elliptic-curve cryptography.
• [BLS11] Bernstein, D., Lange, T., Schwabe, P.: On the correct use of the negation map in the Pollard rho method. PKC 2011.
• [BDPV12] Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: Duplexing the sponge: Single-pass authenticated encryption and other applications. SAC 2012. ePrint 2011/499.
• [BCCT13] Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKs and Proof-Carrying Data. STOC 2013. ePrint 2012/095.
• [BSMP91] Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive Zero-Knowledge. SIAM J. Comput. 20(6), 1991.
• [BFM88] Blum, M., Feldman, P., Micali, S.: Proving security against chosen ciphertext attacks. CRYPTO 1988.
• [DDFG20] Boneh, D., Drake, J., Fisch, B., Gabizon, A.: Efficient polynomial commitment schemes for multiple points and polynomials. ePrint 2020/081.
• [BCC+16] Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient Zero-Knowledge arguments for arithmetic circuits in the Discrete Log setting. EUROCRYPT 2016. ePrint 2016/263.
• [BBB+18] Bunz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: Short proofs for confidential transactions and more. IEEE S&P 2018. ePrint 2017/1066.
• [BFS19] Bunz, B., Fisch, B., Szepieniec, A.: Transparent SNARKs from DARK compilers. ePrint 2019/1229.
• [Car72] Carroll, L.: Through the Looking-Glass, and What Alice Found There. Macmillan and Co. (1872).
• [CC18] Chiesa, A., Chua, L.: On cycles of pairing-friendly elliptic curves. SIAM J. Appl. Algebra Geometry 3(2), 2018.
• [CHM+19] Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., Ward, N.: Marlin: Preprocessing zkSNARKs with universal and updatable SRS. ePrint 2019/1047.
• [COS19] Chiesa, A., Ojha, D., Spooner, N.: Fractal: Post-quantum and transparent recursive proofs from holography. ePrint 2019/1076.
• [CT10] Chiesa, A., Tromer, E.: Proof-Carrying Data and hearsay arguments from signature cards. ICS 2010.
• [DGM99] Duursma, I., Gaudry, P., Morain, F.: Speeding up the discrete log computation on curves with automorphisms. ASIACRYPT 1999.
• [FS86] Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. CRYPTO 1986.
• [GWC19] Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge. ePrint 2019/953. [page on this site]
• [GGP10] Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: Outsourcing computation to untrusted workers. CRYPTO 2010. ePrint 2009/547.
• [GMR89] Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 1989.
• [Gro16] Groth, J.: On the size of pairing-based non-interactive arguments. ePrint 2016/260.
• [Hop1] Hopwood, D.: GitHub repository ‘daira/tweedle’: Generator and supporting evidence for security of the Tweedledum/Tweedledee pair of elliptic curves.
• [Hop2] Hopwood, D.: GitHub repository ‘zcash/zcash’: Issue 3924 – Faster variable-base scalar multiplication in zk-SNARK circuits.
• [HBHW] Hopwood, D., Bowe, S., Hornby, T., Wilcox, N.: Zcash protocol specification.
• [HI] Hopwood, D., Israel, R.: Under what conditions on A and v is the size of the sumset v \cdot A + A over \mathbb{F}_p equal or close to |A|^2? MathOverflow.
• [KZG10] Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. ASIACRYPT 2010.
• [Kil92] Kilian, J.: A Note on Efficient Zero-knowledge Proofs and Arguments. STOC 1992.
• [MBKM19] Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: Zero-Knowledge SNARKs from linear-size universal and updatable Structured Reference Strings. CCS 2019. ePrint 2019/099.
• [Mic00] Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 2000.
• [RCB15] Renes, J., Costello, C., Batina, L.: Complete addition formulas for prime order elliptic curves. ePrint 2015/1060.
• [SM16] Susella, R., Montrasio, S.: A compact and exception-free ladder for all short Weierstrass elliptic curves. CARDIS 2016.
• [Val08] Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. TCC 2008.
• [WTas17] Wahby, R.S., Tzialla, I., abhi shelat, Thaler, J., Walfish, M.: Doubly-efficient zk-SNARKs without trusted setup. ePrint 2017/1132.

Appendix A: Proof of Theorem 1

Proof. Perfect completeness follows trivially. In order to establish perfect special honest-verifier zero knowledge we demonstrate that a simulator \mathcal{S} exists which, when given the verifier’s randomness and the statement, can produce a transcript that is equally distributed with transcripts from an honest prover that has a witness.

In each round of the modified inner product argument the simulator will simply output random group elements, which are distributed identically to the honest prover’s outputs. Upon calculation of Q the simulator chooses d, s \in \mathbb{F}_p at random and uses its access to c to send the verifier

which has the same distribution as the honest prover. Finally, since by definition we have

the simulator sends z_1 = d and z_2 = s, which are again distributed the same as an honest prover, and which satisfy the verifier’s check.

In order to show computational witness-extended emulation we first prove the existence of an extractor \mathcal{X}_{\text{poly}} which, with full access to an adversary \mathcal{P}^* that outputs accepting transcripts, can extract a witness in expected polynomial time. We show that we can extract a, r' such that

by rewinding \mathcal{P}^* once and continuing the argument with fresh challenge c'. If \mathcal{P}^* succeeds in both arguments, then we have pairs of responses (z_1, z_2) and (z'_1, z'_2) such that

Observe by the equalities ac + d = z_1 and ac' + d = z'_1 and the fact that c \neq c' that a, d are fully determined, and similarly for r', s. If it is then not the case that Q = [a](G + [b]U) + [r']H we have extracted a non-trivial discrete log relation between G, U, H.

We now proceed with our extracted a, r' to obtain a witness \mathbf{a}, v' such that

and that v' = \langle \mathbf{a}, (1, x, x^2, \ldots, x^{n-1}) \rangle. We see that our extractor \mathcal{X}_{\text{poly}} is efficient (requiring 4d^2 transcripts in total, which is polynomial in \lambda) and so by the general forking lemma [13, Theorem 6] we have shown computational witness-extended emulation.

Appendix B: Proof of Theorem 2

Proof. Let f(X) = q(X) \cdot (X - y) be a polynomial of maximal degree d, and let g(X) = p(X) - v be a polynomial of maximal degree d - 1. Since we have that f(X) = g(X) over a domain of size d + 1, by the degree bounds of f(X) and g(X) this gives us that f(X) = g(X). Following the definition of f(X) we have that g(X) is perfectly divisible by (X - y) and so by the factor theorem p(y) = v.

Proof of Theorem 2. Perfect completeness follows from the perfect completeness of the polynomial commitment opening argument. Perfect special honest-verifier zero knowledge is shown with a simulator \mathcal{S} that behaves identically to the honest prover except that it outputs random R, T_{\text{lo}}, T_{\text{hi}}, H \in \mathbb{G} and supplies random v_1, v_5, v_6, v_9, v_{10}, v_{12} \in \mathbb{F} such that the verifier’s check is satisfied.

In total the extractor \mathcal{X} requires 5 \cdot (d+1) \cdot 5 \cdot 7 \cdot 2d \cdot d \cdot d invocations of the extractor \mathcal{X}_{\text{poly}} which is polynomial in \lambda and so by the general forking lemma [13, Theorem 6] we have shown computational witness-extended emulation.

Appendix C: Proof for Algorithm 1

Collecting the scalars by which \phi_p(P) and P are multiplied, we see that Algorithm 1 is equivalent to Algorithm 2, which outputs [a\zeta_q + b]P. The equivalence holds because invariants \mathrm{Acc} = [a]\phi_p(P) + [b]P = [a\zeta_q + b]P and S_i = [\mathbf{c}_i]\phi_p(P) + [\mathbf{d}_i]P = [\mathbf{c}_i\zeta_q + \mathbf{d}_i]P are maintained at corresponding steps.

Corollary 1. \mathbf{r} \mapsto (a, b) is injective, following from Lemma 2 and the relations a = 2^{\lambda/2} + 1 + 2\sum_{j=0}^{\lambda/2-1} \mathbf{c}_j 2^j and b = 2^{\lambda/2} + 1 + 2\sum_{j=0}^{\lambda/2-1} \mathbf{d}_j 2^j in Algorithm 2.

Corollary 2. Let n_p(\mathbf{r}) = (a_{\mathbf{r}}\zeta_q + b_{\mathbf{r}}) \bmod q as computed by Algorithm 2 for \lambda = 128, and similarly for n_q, where p, q, \zeta_p and \zeta_q are as defined for the Tweedledum and Tweedledee curves (Section 6.1). Then n_p and n_q are injective.

Hence, on each curve, sampling \mathbf{r} uniformly at random from \{0,1\}^\lambda and computing [n(\mathbf{r})]P via Algorithm 1 will be equivalent to sampling the challenge scalar uniformly at random from \mathbb{I}. This is sufficient for security of our protocol, which does not depend on the specific set \mathbb{I} but only that its size is at least 2^\lambda.