Spartan: Efficient and General-Purpose zkSNARKs without Trusted Setup

Abstract

This paper introduces Spartan, a new family of zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for the rank-1 constraint satisfiability (R1CS), an NP-complete language that generalizes arithmetic circuit satisfiability. A distinctive feature of Spartan is that it offers the first zkSNARKs without trusted setup (i.e., transparent zkSNARKs) for NP where verifying a proof incurs sub-linear costs—without requiring uniformity in the NP statement’s structure. Furthermore, Spartan offers zkSNARKs with a time-optimal prover, a property that has remained elusive for nearly all zkSNARKs in the literature.

To achieve these results, we introduce new techniques that we compose with the sum-check protocol, a seminal interactive proof protocol: (1) computation commitments, a primitive to create a succinct commitment to a description of a computation; this technique is crucial for a verifier to achieve sub-linear costs after investing a one-time, public computation to preprocess a given NP statement; (2) SPARK, a cryptographic compiler to transform any existing extractable polynomial commitment scheme for multilinear polynomials to one that efficiently handles sparse multilinear polynomials; this technique is critical for achieving a time-optimal prover; and (3) a compact encoding of an R1CS instance as a low-degree polynomial. The end result is a public-coin succinct interactive argument of knowledge for NP (which can be viewed as a succinct variant of the sum-check protocol); we transform it into a zkSNARK using prior techniques. By applying SPARK to different commitment schemes, we obtain several zkSNARKs where the verifier’s costs and the proof size range from O(\log^2 n) to O(\sqrt{n}) depending on the underlying commitment scheme (n denotes the size of the NP statement). These schemes do not require a trusted setup except for one that requires a universal trusted setup.

We implement Spartan as a library in about 8,000 lines of Rust. We use the library to build a transparent zkSNARK in the random oracle model where security holds under the discrete logarithm assumption. We experimentally evaluate it and compare with state-of-the-art zkSNARKs for R1CS instance sizes up to 2^{20} constraints. Among transparent zkSNARKs, Spartan offers the fastest prover with speedups of 36–152 \times depending on the baseline, produces proofs that are shorter by 1.2–416 \times, and incurs the lowest verification times with speedups of 3.6–1326 \times. The only exception is proof sizes under Bulletproofs, but Bulletproofs incurs slower verification both asymptotically and concretely. When compared to the state-of-the-art zkSNARKs with trusted setup, Spartan’s prover is 2\times faster for arbitrary R1CS instances and 16\times faster for data-parallel workloads.

Keywords: zkSNARKs, transparent arguments, sum-check protocol, R1CS, polynomial commitments

1. Introduction

We revisit the problem of designing zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs) for the complexity class NP: they enable a computationally-bounded prover to convince the membership of a problem instance in an NP language by producing a proof—without revealing anything besides the validity of the statement. Furthermore, the proof size and the verifier’s costs are sub-linear in the size of the statement. We are motivated to design zkSNARKs because they enable many applications that involve various forms of delegation of computation for scalability or privacy.

Specifically, we are interested in zkSNARKs that prove the satisfiability of R1CS instances over a finite field \mathbb{F} (an NP-complete language that generalizes arithmetic circuit satisfiability): given a problem instance \mathbb{X} = (\mathbb{F}, A, B, C, io, m, n), we desire a proof that demonstrates the knowledge of a witness w such that \mathtt{Sat}_{R1CS}(\mathbb{X}, w) = 1. We desire zkSNARKs for R1CS because there exist efficient toolchains to transform high-level applications of interest to R1CS.

There are many approaches to construct such arguments in the literature, starting with the work of Kilian who provided the first construction of a succinct interactive argument protocol by employing probabilistically checkable proofs (PCPs) in conjunction with Merkle trees. Micali made a similar protocol non-interactive in the random oracle model, thereby obtaining the first zkSNARK. Unfortunately, the underlying PCP machinery remains extremely expensive for the prover and the verifier—despite foundational advances.

The paper discusses how GGPR addressed prover asymptotics with quadratic arithmetic programs (QAPs), achieving O(n \log n) prover cost, O(1) proof size, and O(|io|) verification—but requiring a per-statement trusted setup. This motivated transparent zkSNARKs including Hyrax, STARK, Aurora, Ligero, and Bulletproofs, each facing limitations: Hyrax is restricted to low-depth uniform circuits; STARK requires uniform circuits; and Ligero, Bulletproofs, and Aurora incur O(n) verification costs.

1.1 Summary of Contributions

This paper presents a new family of zkSNARKs, which we call Spartan, for proving the satisfiability of NP statements expressed in R1CS. Spartan offers the first transparent zkSNARK that achieves sub-linear verification costs for arbitrary NP statements. Spartan also offers zkSNARKs with a time-optimal prover.

Spartan introduces three key techniques: (i) computation commitments, a primitive for creating succinct cryptographic commitments to a mathematical description of an NP statement, critical for achieving sub-linear verification costs; (ii) SPARK, a cryptographic compiler to transform any existing extractable polynomial commitment scheme for multilinear polynomials to one that efficiently handles sparse multilinear polynomials, critical for achieving a time-optimal prover; and (iii) a compact encoding of an R1CS instance as a degree-3 multivariate polynomial that decomposes into four multilinear polynomials.

The paper also contributes: (2) an optimized implementation and experimental evaluation in about 8,000 lines of Rust; (3) a unified understanding of different strands of theory on probabilistic proofs; and (4) improvements in zkSNARKs with universal setup via Spartan_{\text{KE}}, which supports arbitrary R1CS instances instead of layered arithmetic circuits.

1.2 Additional Related Work

Following the Spartan preprint, three transparent zkSNARKs appeared: Fractal, SuperSonic, and Virgo. Fractal and SuperSonic achieve sub-linear verification costs for arbitrary NP statements by instantiating computation commitments, but both incur orders of magnitude higher expense than Spartan. Virgo is specialized to layered uniform circuits.

The paper reviews linear PCPs and QAPs (IKO, GGPR, Pinocchio, Zaatar, BCGTV, BCTV, Groth16), interactive proofs (GKR, CMT, Hyrax, Libra, Virgo), and how Spartan relates to each line of work. Spartan can be viewed as an efficient mechanism to compile two-prover protocols into a public-coin succinct interactive argument of knowledge without employing FHE or low-degree tests.

2. Preliminaries

We use \mathbb{F} to denote a finite field (e.g., the prime field \mathbb{F}_p for a large prime p) and \lambda to denote the security parameter. We use \mathsf{negl}(\lambda) to denote a negligible function in \lambda.

2.1 Problem Instances in R1CS

R1CS generalizes arithmetic circuit satisfiability because the entries in matrices A, B, C can encode addition and multiplication gates over \mathbb{F}. Furthermore, they can encode a class of degree-2 constraints of the form L(z) \cdot R(z) = O(z), where L, R, O are degree-1 polynomials.

2.2 Succinct Interactive Arguments of Knowledge

2.3 Polynomials and Low-Degree Extensions

Low-degree extensions (LDEs). Given a function g : \{0,1\}^m \to \mathbb{F}, a multilinear extension (MLE) is the unique multilinear polynomial \widetilde{g} : \mathbb{F}^m \to \mathbb{F} such that \widetilde{g}(x) = g(x) for all x \in \{0,1\}^m. Given Z: \{0,1\}^m \to \mathbb{F}, the MLE is computed as:

2.4 A Polynomial Commitment Scheme for Multilinear Polynomials

A polynomial commitment scheme for multilinear polynomials is a tuple of four protocols \text{PC} = (\text{Setup}, \text{Commit}, \text{Open}, \text{Eval}).

3. The Sum-Check Protocol: Opportunities and Challenges

The sum-check protocol is a seminal interactive proof protocol. Suppose there is a \mu-variate low-degree polynomial \mathcal{G}: \mathbb{F}^\mu \to \mathbb{F} where the degree of each variable is at most \ell. A verifier \mathcal{V}_{SC} checks if the following claim by an untrusted prover holds:

The protocol proceeds over \mu rounds. At the end, \mathcal{V}_{SC} must evaluate \mathcal{G} at a random point r \in \mathbb{F}^\mu. The properties are: completeness (with probability 1), soundness (error at most \ell \cdot \mu / |\mathbb{F}|), and succinctness (communication O(\mu \cdot \ell) elements of \mathbb{F}).

3.1 Challenges with Using the Sum-Check Protocol for Succinct Arguments

To build a succinct interactive argument of knowledge for R1CS, three sub-problems must be solved:

1. Encode R1CS instances as sum-check instances. Devise a degree-\ell, \mu-variate polynomial that sums to a specific value over the Boolean hypercube if and only if the R1CS instance is satisfiable.
2. Achieve communication-succinctness. After the sum-check reduction, the verifier must evaluate \mathcal{G}(r), which depends on the prover’s witness, so naive evaluation requires O(m) communication.
3. Achieve verifier-succinctness. Evaluating \mathcal{G}(r) requires O(n) computation if the statement has no structure, motivating preprocessing.

3.2 Prior Solutions (Spartan’s Closely Related Works)

Prior literature offers solutions via multi-prover interactive proofs (MIPs), short PCPs, and doubly-efficient interactive proofs. The paper discusses how Blumberg et al. use two non-colluding provers; how Babai et al. devise short PCPs; and how GKR-based doubly-efficient IPs solve all three sub-problems but restrict to layered circuits. Spartan can be viewed as an efficient mechanism to compile such protocols into a single-prover succinct argument without FHE or low-degree tests.

4. An Encoding of R1CS Instances as Low-Degree Polynomials

Let s = \lceil \log m \rceil. View matrices A, B, C as functions \{0,1\}^s \times \{0,1\}^s \to \mathbb{F}. Given a purported witness w, let Z = (io, 1, w). Define:

The polynomial extension \widetilde{F}_{io} is defined using MLEs of A, B, C, Z:

To ensure that all terms are individually zero (not just the sum), define:

where \widetilde{\text{eq}}(t, x) = \prod_{i=1}^s (t_i \cdot x_i + (1 - t_i)(1 - x_i)). Then Q_{io}(\cdot) is a zero-polynomial if and only if \widetilde{F}_{io} evaluates to zero at all Boolean points.

Proof of Theorem 4.1. Define \mathcal{G}_{io,\tau}(x) = \widetilde{F}_{io}(x) \cdot \widetilde{\text{eq}}(\tau, x), so Q_{io}(\tau) = \sum_{x \in \{0,1\}^s} \mathcal{G}_{io,\tau}(x). This polynomial is degree-3 in s = \log m variables. With \tau \in_R \mathbb{F}^s, the sum equals zero if and only if \widetilde{F}_{io}(x) = 0 for all x \in \{0,1\}^s, except for negligible soundness error (by Lemmas 4.2 and 4.3).

5. A Family of NIZKs with Succinct Proofs for R1CS

5.1 A New Public-Coin Succinct Interactive Argument of Knowledge

The protocol uses two instances of the sum-check protocol. After the first sum-check reduces \sum_{x \in \{0,1\}^s} \mathcal{G}_{io,\tau}(x) = 0 to evaluating \mathcal{G}_{io,\tau}(r_x), the prover sends claims v_A = \overline{A}(r_x), v_B = \overline{B}(r_x), v_C = \overline{C}(r_x). A second sum-check verifies a random linear combination of these three claims:

At the end of the second sum-check, the verifier evaluates:

The only term depending on the witness is \widetilde{Z}(r_y), which is handled by an extractable polynomial commitment scheme. The prover commits to \widetilde{w}(\cdot) and uses:

Analysis of costs. The prover incurs O(n) for sum-check participation plus the cost of PC.Commit and PC.Eval. The verifier incurs O(\log m) for sum-check, PC.Eval costs, and O(n) to evaluate \widetilde{A}, \widetilde{B}, \widetilde{C}. Communication is O(\log m) plus the commitment size and PC.Eval communication.

5.2 A Family of NIZKs with Succinct Proofs for R1CS

The interactive argument is public coin, so zero-knowledge is added using prior compilers (from Hyrax or Libra/Virgo), and non-interactivity is achieved via the Fiat-Shamir transform in the random oracle model, yielding a family of NIZKs with succinct proofs for R1CS.

6. Computation Commitments: zkSNARKs for R1CS from NIZK

The NIZK from Section 5 does not yet achieve sub-linear verification because the verifier incurs O(n) costs to evaluate \widetilde{A}, \widetilde{B}, \widetilde{C} at (r_x, r_y). Computation commitments address this via a preprocessing step.

In an offline phase, the verifier commits to the sparse multilinear polynomials encoding the R1CS structure:

During proof verification, the prover evaluates \widetilde{A}, \widetilde{B}, \widetilde{C} at (r_x, r_y) and proves correctness via PC.Eval against the retained commitments. This preprocessing cost is amortized over all future proofs for R1CS instances with the same structure—and unlike GGPR’s trusted setup, it does not involve secret trapdoors.

However, existing polynomial commitment schemes are inefficient for sparse polynomials: the prover incurs at least O(m^2) costs for Eval on the 2\log m-variate polynomials \widetilde{A}, \widetilde{B}, \widetilde{C}. This motivates the SPARK compiler (Section 7).

7. The SPARK Compiler

SPARK is a cryptographic compiler that transforms an existing extractable polynomial commitment scheme for dense multilinear polynomials into one that efficiently handles sparse multilinear polynomials.

7.1 SPARK-naive: A Straw-Man Solution

The straw-man builds an O(\log \mu)-depth circuit with O(n \cdot \mu) gates that evaluates \widetilde{M}(r) using Equation (1):

The circuit is data-parallel (n identical sub-circuits), so Hyrax can verify it. However, the prover incurs O(n \log n) costs, an asymptotic overhead over direct evaluation.

7.2 Eliminating Asymptotic Overheads by Leveraging Memory Checking

SPARK improves on the straw-man by devising an O(n)-sized circuit for sparse polynomial evaluation. The key observation is that \widetilde{M}(r_x, r_y) can be rewritten as:

Precomputing tables of \widetilde{\text{eq}}(i, r_x) and \widetilde{\text{eq}}(j, r_y) for all i, j \in \{0,1\}^s takes O(m) time each. But computing the sum requires n random accesses into these tables, which is handled by offline memory checking techniques with public-coin multiset hash functions:

Optimizations. Several optimizations reduce constants: (1) tailoring Hyrax for the specific circuit instead of black-box use; (2) building a single circuit for \widetilde{A}, \widetilde{B}, \widetilde{C} to reuse memory-checking state; (3) deriving write timestamps from read timestamps; (4) leveraging succinct representations to avoid committing to certain polynomials; (5) combining multiple multilinear polynomials into a single polynomial with additional variables, reducing from 23 committed polynomials to 3.

8. Implementation and Optimizations

Spartan is implemented as a modular library in about 8,000 lines of Rust. The prover under SPARK outperforms SPARK-naive by > 10\times for R1CS instances with 2^{20} constraints. The optimizations reduce proof lengths from 3.1 MB to 142 KB (> 20\times improvement) and improve prover and verification times by about 10\times.

The implementation uses curve25519-dalek for a prime-order Ristretto group (ristretto255), with optimized scalar arithmetic yielding \approx 10\times speedup. Zero knowledge is added via Hyrax’s transformation with a simplification: separate dot-product proof protocols per sum-check round. The Fiat-Shamir transform uses the merlin library.

9. Experimental Evaluation

9.1 Metrics, Methodology, and Testbed

Evaluation metrics are: prover costs, verifier preprocessing costs, verifier proof verification costs, and proof size. Experiments use a Microsoft Surface Laptop 3 (Intel Core i7-1065G7, 16 GB RAM, Ubuntu 20.04) on a single CPU core. Baselines include: Groth16, Ligero, Hyrax, Aurora, and Fractal.

9.2 Performance Results

Prover. Spartan_{\text{SNARK}} is 36\times faster than Fractal at 2^{18} constraints. Spartan_{\text{NIZK}} is 24\times faster than Ligero, 152\times faster than Aurora, and 99\times faster than Hyrax at 2^{20} instances. Compared to Groth16, Spartan_{\text{SNARK}} is 2\times faster and Spartan_{\text{NIZK}} is 16\times faster for 2^{20} constraints.

Proof sizes. Spartan_{\text{SNARK}} offers \approx 23\times shorter proofs than Fractal at 2^{18} constraints. Spartan_{\text{NIZK}} offers proofs 1.2–416\times shorter than baselines. All transparent zkSNARKs produce orders of magnitude longer proofs than Groth16 (128 bytes).

Verifier. Among transparent schemes, Spartan_{\text{SNARK}} is 3.6\times faster than Fractal, 1326\times faster than Aurora, 383\times faster than Ligero, and 80\times faster than Hyrax at 2^{20} constraints. Spartan_{\text{SNARK}} beats Spartan_{\text{NIZK}} for verification at approximately 2^{17} constraints since the former incurs O(\sqrt{n}) costs versus O(n).

Encoder. Spartan_{\text{SNARK}}’s encoder is up to 52\times faster than Fractal’s and about 4.7\times faster than Groth16’s trusted setup at the largest instance sizes.

Acknowledgements

Comments from Sebastian Angel, Melissa Chase, Hao Chen, Ben Fisch, Esha Ghosh, Abhiram Kothapalli, Satya Lokam, Bryan Parno, Ioanna Tzialla, Ramarathnam Venkatesan, and the CRYPTO 2020 reviewers helped improve this paper. Special thanks to Justin Thaler, Riad Wahby, and Michael Walfish for their detailed attention and thorough comments, and to Jonathan Lee for insightful discussions. We thank Henry de Valence for help with curve25519-dalek.

Appendix A: Proof of Witness-Extended Emulation

Proof. If \mathbf{x} is not satisfiable, then Q_{io}(t) is not a zero-polynomial. By the Schwartz-Zippel lemma, the verifier choosing a “bad” \tau where Q_{io}(\tau) = 0 happens with probability at most \log m / |\mathbb{F}|. Otherwise, a malicious prover begins with a false claim in the sum-check protocol and succeeds with probability at most (\ell_1 \cdot \mu_1 + \ell_2 \cdot \mu_2 + 1)/|\mathbb{F}| where \mu_1 = \mu_2 = \log m, \ell_1 = 3, \ell_2 = 2. A union bound establishes the result.

Proof. The proof is identical to Hyrax’s except where their proof invokes properties of Gir++, we invoke properties of Spartan-core (the information-theoretic variant).

References

• [Eth] Ethereum Roadmap. ZK-Rollups.
• [Mer] Merlin: composable proof transcripts for public-coin arguments of knowledge.
• [cur25519] A pure-Rust implementation of group operations on Ristretto and Curve25519.
• [Ris] The Ristretto group.
• [Spa] Spartan: High-speed zkSNARKs without trusted setup. github.com/Microsoft/Spartan.
• [AHIV17] S. Ames, C. Hazay, Y. Ishai, and M. Venkitasubramaniam. “Ligero: Lightweight sublinear arguments without a trusted setup.” In: CCS, 2017.
• [Ara+17] A. Arasu et al. “Concerto: A high concurrency key-value store with integrity.” In: SIGMOD, 2017.
• [ALMS98] S. Arora, C. Lund, R. Motwani, M. Sudan, and M. Szegedy. “Proof verification and the hardness of approximation problems.” J. ACM, 45(3), 1998.
• [AS98] S. Arora and S. Safra. “Probabilistic checking of proofs: A new characterization of NP.” J. ACM, 45(1):70–122, 1998.
• [AS03] S. Arora and M. Sudan. “Improved low-degree testing and its applications.” Combinatorica, 23(3):365–426, 2003.
• [Bab85] L. Babai. “Trading group theory for randomness.” In: STOC, 1985.
• [BFLS91] L. Babai, L. Fortnow, L. A. Levin, and M. Szegedy. “Checking computations in polylogarithmic time.” In: STOC, 1991.
• [BFL92] L. Babai, L. Fortnow, and C. Lund. “Non-deterministic exponential time has two-prover interactive protocols.” Computational Complexity, 2(4), 1992.
• [BO+88] M. Ben-Or et al. “Everything provable is provable in zero-knowledge.” In: CRYPTO, 1988.
• [BBHR18] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev. “Scalable, transparent, and post-quantum secure computational integrity.” ePrint 2018/046.
• [BS+20] E. Ben-Sasson et al. “Proximity gaps for Reed-Solomon codes.” ePrint 2020/654.
• [BS+14] E. Ben-Sasson et al. “Zerocash: Decentralized anonymous payments from Bitcoin.” In: S&P, 2014.
• [BCGT13] E. Ben-Sasson, A. Chiesa, D. Genkin, and E. Tromer. “Fast reductions from RAMs to delegatable succinct constraint satisfaction problems.” In: ITCS, 2013.
• [BS+13a] E. Ben-Sasson et al. “On the concrete efficiency of probabilistically-checkable proofs.” In: STOC, 2013.
• [BS+13b] E. Ben-Sasson et al. “SNARKs for C: Verifying program executions succinctly and in zero knowledge.” In: CRYPTO, 2013.
• [BS+19a] E. Ben-Sasson et al. “Aurora: Transparent succinct arguments for R1CS.” In: EUROCRYPT, 2019.
• [BCS16] E. Ben-Sasson, A. Chiesa, and N. Spooner. “Interactive Oracle Proofs.” In: TCC, 2016.
• [BS+14b] E. Ben-Sasson et al. “Scalable zero knowledge via cycles of elliptic curves.” In: CRYPTO, 2014.
• [BS+14c] E. Ben-Sasson et al. “Succinct non-interactive zero knowledge for a von Neumann architecture.” In: USENIX Security, 2014.
• [BS+05] E. Ben-Sasson et al. “Short PCPs verifiable in polylogarithmic time.” In: Computational Complexity, 2005.
• [BS05] E. Ben-Sasson and M. Sudan. “Simple PCPs with poly-log rate and query complexity.” In: STOC, 2005.
• [BS08] E. Ben-Sasson and M. Sudan. “Short PCPs with polylog query complexity.” SIAM J. Comput., 38(2), 2008.
• [Bit+12] N. Bitansky et al. “From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again.” In: ITCS, 2012.
• [BC12] N. Bitansky and A. Chiesa. “Succinct arguments from multi-prover interactive proofs.” In: CRYPTO, 2012.
• [Bit+13] N. Bitansky et al. “Succinct non-interactive arguments via linear interactive proofs.” In: TCC, 2013.
• [BEGK91] M. Blum, W. Evans, P. Gemmell, S. Kannan, and M. Naor. “Checking the correctness of memories.” In: FOCS, 1991.
• [BTVW14] A. J. Blumberg, J. Thaler, V. Vu, and M. Walfish. “Verifiable computation using multiple provers.” ePrint 2014/846.
• [Bon+19] D. Boneh et al. “Zero-knowledge proofs on secret-shared data via fully linear PCPs.” ePrint 2019/188.
• [Boo+16] J. Bootle et al. “Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting.” In: EUROCRYPT, 2016.
• [Bow] S. Bowe. A BLS12-381 implementation.
• [Bow+18] S. Bowe et al. “Zexe: Enabling decentralized private computation.” ePrint 2018/962.
• [BCC88] G. Brassard, D. Chaum, and C. Crépeau. “Minimum disclosure proofs of knowledge.” J. Comput. Syst. Sci., 37(2), 1988.
• [Bra+13] B. Braun et al. “Verifying computations with state.” In: SOSP, 2013.
• [BFS19] B. Bünz, B. Fisch, and A. Szepieniec. “Transparent SNARKs from DARK compilers.” ePrint 2019/1229.
• [But18] V. Buterin. “On-chain scaling to potentially 500 tx/sec through mass tx validation.” 2018.
• [But19] V. Buterin. “The dawn of hybrid layer 2 protocols.” 2019.
• [Bun+18] B. Bünz et al. “Bulletproofs: Short proofs for confidential transactions and more.” In: S&P, 2018.
• [CFQ19] M. Campanelli, D. Fiore, and A. Querol. “LegoSNARK: modular design and composition of succinct zero-knowledge proofs.” ePrint 2019/142.
• [CRR12] R. Canetti, B. Riva, and G. N. Rothblum. “Two protocols for delegation of computation.” In: ICITS, 2012.
• [CFS17] A. Chiesa, M. A. Forbes, and N. Spooner. “A zero knowledge sumcheck and its applications.” CoRR, abs/1704.02086, 2017.
• [COS19] A. Chiesa, D. Ojha, and N. Spooner. “Fractal: Post-quantum and transparent recursive proofs from holography.” ePrint 2019/1076.
• [Cla+03] D. Clarke et al. “Incremental multiset hash functions and their application to memory integrity checking.” In: ASIACRYPT, 2003.
• [CMT12] G. Cormode, M. Mitzenmacher, and J. Thaler. “Practical verified computation with streaming interactive proofs.” In: ITCS, 2012.
• [Cos+15] C. Costello et al. “Geppetto: Versatile verifiable computation.” In: S&P, 2015.
• [CD98] R. Cramer and I. Damgård. “Zero-knowledge proofs for finite field arithmetic.” In: CRYPTO, 1998.
• [DL+16] A. Delignat-Lavaud et al. “Cinderella: Turning shabby X.509 certificates into elegant anonymous credentials.” In: S&P, 2016.
• [Din07] I. Dinur. “The PCP theorem by gap amplification.” J. ACM, 54(3), 2007.
• [Dwo+09] C. Dwork et al. “How efficient can memory checking be?” In: TCC, 2009.
• [Fei+96] U. Feige et al. “Interactive proofs and the hardness of approximating cliques.” J. ACM, 43(2), 1996.
• [FS86] A. Fiat and A. Shamir. “How to prove yourself: Practical solutions to identification and signature problems.” In: CRYPTO, 1986.
• [Fio+16] D. Fiore et al. “Hash first, argue later: Adaptive verifiable computations on outsourced data.” In: CCS, 2016.
• [GGP10] R. Gennaro, C. Gentry, and B. Parno. “Non-interactive verifiable computing.” In: CRYPTO, 2010.
• [GGPR13] R. Gennaro, C. Gentry, B. Parno, and M. Raykova. “Quadratic span programs and succinct NIZKs without PCPs.” In: EUROCRYPT, 2013.
• [Gen09] C. Gentry. A fully homomorphic encryption scheme. PhD thesis, Stanford, 2009.
• [GW11] C. Gentry and D. Wichs. “Separating succinct non-interactive arguments from all falsifiable assumptions.” In: STOC, 2011.
• [GKR08] S. Goldwasser, Y. T. Kalai, and G. N. Rothblum. “Delegating computation: Interactive proofs for muggles.” In: STOC, 2008.
• [GMR85] S. Goldwasser, S. Micali, and C. Rackoff. “The knowledge complexity of interactive proof-systems.” In: STOC, 1985.
• [Gro10] J. Groth. “Short pairing-based non-interactive zero-knowledge arguments.” In: ASIACRYPT, 2010.
• [Gro16] J. Groth. “On the size of pairing-based non-interactive arguments.” In: EUROCRYPT, 2016.
• [GI08] J. Groth and Y. Ishai. “Sub-linear zero-knowledge argument for correctness of a shuffle.” In: EUROCRYPT, 2008.
• [Gro+18] J. Groth et al. “Updatable and universal common reference strings with applications to zk-SNARKs.” In: CRYPTO, 2018.
• [Ham15] M. Hamburg. “Decaf: Eliminating cofactors through point compression.” In: CRYPTO, 2015.
• [Has97] J. Håstad. “Some optimal inapproximability results.” In: STOC, 1997.
• [IKO07] Y. Ishai, E. Kushilevitz, and R. Ostrovsky. “Efficient arguments without short PCPs.” In: Computational Complexity, 2007.
• [Ish+07] Y. Ishai et al. “Zero-knowledge from secure multiparty computation.” In: STOC, 2007.
• [Kal17] Y. T. Kalai. “Delegating computation: A new perspective.” Workshop at STOC 2017.
• [KZG10] A. Kate, G. M. Zaverucha, and I. Goldberg. “Constant-size commitments to polynomials and their applications.” In: ASIACRYPT, 2010.
• [Kil92] J. Kilian. “A note on efficient zero-knowledge proofs and arguments.” In: STOC, 1992.
• [Kos+16] A. Kosba et al. “Hawk: The blockchain model of cryptography and privacy-preserving smart contracts.” In: S&P, 2016.
• [KPS18] A. Kosba, C. Papamanthou, and E. Shi. “xJsnark: A framework for efficient verifiable computation.” In: S&P, 2018.
• [LNS20] J. Lee, K. Nikitin, and S. Setty. “Replicated state machines without replicated execution.” In: S&P, 2020.
• [libfen] libfennel. Hyrax reference implementation.
• [libiop] libiop. A C++ library for IOP-based zkSNARK.
• [libsnark] libsnark. A C++ library for zkSNARK proofs.
• [Lip12] H. Lipmaa. “Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments.” In: TCC, 2012.
• [LFKN90] C. Lund, L. Fortnow, H. Karloff, and N. Nisan. “Algebraic methods for interactive proof systems.” In: FOCS, 1990.
• [Mal+19] M. Maller et al. “Sonic: Zero-knowledge SNARKs from linear-size universal and updateable structured reference strings.” ePrint 2019/099.
• [Mer88] R. C. Merkle. “A digital signature based on a conventional encryption function.” In: CRYPTO, 1988.
• [Mic94] S. Micali. “CS proofs.” In: FOCS, 1994.
• [MR08] D. Moshkovitz and R. Raz. “Sub-constant error low degree test of almost-linear size.” SIAM J. Comput., 38(1), 2008.
• [OWB19] A. Ozdemir, R. S. Wahby, and D. Boneh. “Scaling verifiable computation using efficient set accumulators.” ePrint 2019/1494.
• [PST13] C. Papamanthou, E. Shi, and R. Tamassia. “Signatures of correct computation.” In: TCC, 2013.
• [PGHR13] B. Parno, C. Gentry, J. Howell, and M. Raykova. “Pinocchio: Nearly practical verifiable computation.” In: S&P, 2013.
• [RRR16] O. Reingold, G. N. Rothblum, and R. D. Rothblum. “Constant-round interactive proofs for delegating computation.” In: STOC, 2016.
• [Rot09] G. Rothblum. Delegating Computation Reliably: Paradigms and Constructions. PhD thesis, MIT, 2009.
• [Set+18] S. Setty et al. “Proving the correct execution of concurrent services in zero-knowledge.” In: OSDI, 2018.
• [SBW11] S. Setty, A. J. Blumberg, and M. Walfish. “Toward practical and unconditional verification of remote computations.” In: HotOS, 2011.
• [Set+13] S. Setty et al. “Resolving the conflict between generality and plausibility in verified computation.” In: EuroSys, 2013.
• [Set+12a] S. Setty et al. “Making argument systems for outsourced computation practical (sometimes).” In: NDSS, 2012.
• [Set+12b] S. Setty et al. “Taking proof-based verified computation a few steps closer to practicality.” In: USENIX Security, 2012.
• [Tha13] J. Thaler. “Time-optimal interactive proofs for circuit evaluation.” In: CRYPTO, 2013.
• [Tha17] J. Thaler. “A state of the art MIP for circuit satisfiability.” Lecture notes, 2017.
• [Tha+12] J. Thaler et al. “Verifiable computation with massively parallel interactive proofs.” In: HotCloud, 2012.
• [Vu+13] V. Vu et al. “A hybrid architecture for verifiable computation.” In: S&P, 2013.
• [Wah+16] R. S. Wahby et al. “Verifiable ASICs.” In: S&P, 2016.
• [Wah+17] R. S. Wahby et al. “Full accounting for verifiable outsourcing.” In: CCS, 2017.
• [Wah+15] R. S. Wahby et al. “Efficient RAM and control flow in verifiable outsourced computation.” In: NDSS, 2015.
• [WTST18] R. S. Wahby, I. Tzialla, A. Shelat, J. Thaler, and M. Walfish. “Doubly-efficient zkSNARKs without trusted setup.” In: S&P, 2018.
• [WB15] M. Walfish and A. J. Blumberg. “Verifying computations without reexecuting them.” Commun. ACM, 58(2), 2015.
• [Whi+18] B. WhiteHat et al. “Roll_up / roll_back snark side chain ~17000 tps.” 2018.
• [XZZP19] T. Xie, J. Zhang, Y. Zhang, C. Papamanthou, and D. Song. “Libra: Succinct zero-knowledge proofs with optimal prover computation.” ePrint 2019/317.
• [ZXZS20] J. Zhang, T. Xie, Y. Zhang, and D. Song. “Transparent polynomial delegation and its applications to zero knowledge proof.” In: S&P, 2020.
• [Zha+17] Y. Zhang et al. “vSQL: Verifying arbitrary SQL queries over dynamic outsourced databases.” In: S&P, 2017.
• [Zha+17b] Y. Zhang et al. “A zero-knowledge version of vSQL.” ePrint 2017/1146.
• [Zha+18] Y. Zhang et al. “vRAM: Faster verifiable RAM with program-independent preprocessing.” In: S&P, 2018.