Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model

Abstract

We present MMORPG, a built system for zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARK) parameter generation. zk-SNARKs are compact, efficient, and publicly verifiable zero-knowledge proofs for arbitrary computation. They have emerged as a valuable tool for verifiable computation, privacy preserving protocols, and blockchains. Currently practical schemes require a common reference string (CRS) to be constructed in a one-time setup for each statement. Corruption of this process leads to forged proofs and for applications such as cryptocurrencies, potentially billions of dollars in theft. Ben-Sasson, Chiesa, Green, Tromer and Virza [Ben-Sasson+15] devised a multi-party protocol to securely compute such a CRS, and an adaptation of this protocol was used to construct the CRS for the Zcash cryptocurrency [BowGabGre17]. The trustworthiness of these protocols is obstructed by the need for a precommitment phase which forces the selection of a very small number of participants in advance and requires them to secure their secret randomness throughout the duration of the protocol. Our primary contribution is a more scalable multi-party computation (MPC) protocol, secure in the random beacon model, which omits the precommitment phase. We show that security holds even if an adversary has limited influence on the beacon. Next, we apply our main result to obtain a two-phase protocol for computing an extended version of the CRS of Groth’s zk-SNARK [Groth16]. We show that knowledge soundness is maintained in the generic group model when using this CRS. Finally, we implement and evaluate our system.

1. Introduction

Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) [Ben-Sasson+13a], [Bitansky+13], [Gen+13b], [Groth16], [Groth10], [Kilian92], [Lipmaa12], [Lipmaa13], [Micali00], [Parno+13] have seen increased usage both in the literature and the real world, ranging from publicly verifiable computation, to deployed usage for anonymous payment systems such as Zerocash [Ben-Sasson+14] and Zcash [Zcash17] and smart contract systems such as Ethereum.

Despite the power of zk-SNARKs, challenges stand in the way of their widespread use. Most significantly, these schemes are secure in the common reference string (CRS) model, which assumes a trusted setup of parameters used for constructing and verifying proofs. The generation of this CRS is a major challenge, given that corruption or subversion of the parameters means the proof systems are no longer sound, i.e. proofs can be forged. The existence of trusted setup parties is often assumed in academic work; in practice these parties are hard to find, even harder to get a large and diverse group to agree on, and potentially untrustworthy in the face of the tangible monetary gains that arise in real world deployment.

The current approach for deployed systems is for the CRS to be generated via a multi-party computation protocol [Ben-Sasson+15], [BowGabGre17] built from scratch for the task of computing a CRS. These protocols guarantee soundness — i.e. that proofs cannot be forged — when at least one participant is honest, and guarantee zero-knowledge even if none of the participants are honest. However, these protocols fundamentally cannot scale beyond a handful of participants, and can even be too expensive to perform for just one or two participants in some settings. This is not an engineering and optimization issue. Fundamentally, it is a cryptographic issue: because of restrictions required to deal with adaptive attackers, participants in the current MPC schemes must commit to their share of the parameters up front and maintain availability and security throughout the entire duration of the protocol — even after the majority of their individual computation is completed.

[The paper continues with detailed discussion of the need for crowd-scale parameter generation for high-value applications, highlighting that systems like Zcash (nearly $1 billion) and Ethereum ($40 billion market cap) use zk-SNARKs and would benefit from more robust CRS generation. The authors also discuss random beacons as a source of public randomness, distinguishing them from random oracles by noting that beacon values are not available until certain time slots.]

1.1 Our Results

In this paper, we design, implement, and evaluate a scalable open participation multiparty computation protocol for generating zk-SNARK parameters. We aim to make zk-SNARKs suitable for wide-scale usage by providing a new zk-SNARK scheme and MPC system for CRS generation suitable for real world usage. We offer three contributions:

Player-exchangeable MPC. Our primary contribution is a new kind of multi-party computation protocol, a player-exchangeable MPC (px-MPC) and an efficient and implemented px-MPC protocol for CRS generation. A px-MPC is described by a sequence of messages players are supposed to send; however, importantly, there is no restriction on the identity of the sender of each message. In particular, although we will discuss multi-phase protocols where in each phase all players participate in a round-robin process, there is no need to assume the same players participate in different phases. Since there is no private state between messages, players may be swapped out or removed after every message.

zk-SNARKs with an efficient and amortized px-MPC CRS generation process. We prove the security of Groth’s zk-SNARK with an extended CRS which allows for a two phase px-MPC protocol. The first phase is agnostic to the statement (up to statement size), and so can be performed once for all statements up to some large (but bounded) size. The second phase is statement-specific, but significantly cheaper.

MMORPG, a built system. As a final contribution, we offer MMORPG, a built system for massively multiparty open reusable parameter generation for our modified version of Groth’s zk-SNARK. For a circuit size up to 2^{21} multiplication gates, participants in the first round must receive a 1.2GB file, perform a computation that lasts about 13 minutes on a desktop machine, and produce a 600MB file. We also adopt a new pairing-friendly elliptic curve called BLS12-381 which targets 128-bit security.

1.2 Outline

This paper is structured as follows. In section 2 we give an overview of our approach. In section 3 we give cryptographic preliminaries, notation, and supporting lemmas. In section 4 we detail our MPC protocol. In section 5 we detail a proof of security. In section 6 we instantiate our protocol using Groth’s zk-SNARK. Finally, in section 9 we evaluate our implementation.

2. Overview of Our Approach

Our goal is to build a practical protocol between n players and an untrusted coordinator that: gives a zk-SNARK CRS where proofs cannot be forged if at least one of the n players is honest; places no limits on n, the number of participants; does not require players to be selected in advance; and does not require players to pre-commit to their random coins and therefore keep them secure throughout the protocol.

The key to achieving these goals is removing the pre-commitment phase used in previous protocols [Ben-Sasson+15], [BowGabGre17]. To do this, we design our protocol around the use of a random beacon, a source of public randomness that is not available before a fixed time.

A toy CRS. For exposition, we consider a CRS that consists only of the elements s \cdot g_1 and \alpha P(s) \cdot g_1 where g_1 is a generator of a group \mathbb{G}_1 of order p; s and \alpha are uniform elements in \mathbb{F}_p^*; and P is the degree one polynomial P(x) := 3x + 5 over \mathbb{F}_p.

Phase 1. Alice and Bob need to compute s \cdot g_1 for a uniform s \in \mathbb{F}_p^* unknown to either of them. Alice chooses a uniform s_1 \in \mathbb{F}_p^*, and sends M = s_1 \cdot g_1 to Bob. Bob is requested to multiply M by a uniform s_2 \in \mathbb{F}_p^*. The problem is that as Bob is malicious he can adaptively choose s_2 based on Alice’s message. Previous protocols [Ben-Sasson+15], [BowGabGre17] solved this with a precommitment phase; this paper’s main observation is that assuming a random beacon, we can omit the precommitment phase and still prevent adaptive attacks.

With the random beacon, our simplified protocol proceeds: (1) Alice chooses random s_1 \in \mathbb{F}_p^* and broadcasts M = s_1 \cdot g_1; (2) Bob chooses a value s_2 \in \mathbb{F}_p^* and broadcasts M' = s_1 s_2 \cdot g_1; (3) the coordinator invokes the random beacon to obtain a uniform s_3 \in \mathbb{F}_p^*, and the protocol output is s_3 \cdot M' = s_1 s_2 s_3 \cdot g_1. The output is s \cdot g_1 for uniform s regardless of Bob’s choice.

Phase 2. After Phase 1, P(s) \cdot g_1 is a linear combination

of the public values s \cdot g_1, g_1. Thus, the coordinator can efficiently compute P(s) \cdot g_1. Phase 2 proceeds analogously to Phase 1 for computing \alpha P(s) \cdot g_1.

3. Preliminaries

3.1 Notation

We will be working over bilinear groups \mathbb{G}_1, \mathbb{G}_2, and \mathbb{G}_T each of prime order p, together with respective generators g_1, g_2 and g_T. These groups are equipped with a non-degenerate bilinear pairing e: \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T, with e(g_1, g_2) = g_T. We write \mathbb{G}_1 and \mathbb{G}_2 additively, and \mathbb{G}_T multiplicatively. For a \in \mathbb{F}_p, we denote [a]_1 := a \cdot g_1, [a]_2 := a \cdot g_2. We use the notation \mathbf{G} := \mathbb{G}_1 \times \mathbb{G}_2 and \mathbf{g} := (g_1, g_2).

We assume that we have a generator \mathcal{G} that takes a parameter \lambda and returns the three groups above having prime order p at least super polynomial in \lambda, together with uniformly chosen generators g_1 \in \mathbb{G}_1^*, g_2 \in \mathbb{G}_2^*. We use the acronym e.w.p. to mean “except with probability”; i.e., e.w.p. \gamma means “with probability at least 1 - \gamma”.

3.2 Random Beacons

We assume we have at our disposal a “random beacon” RB that outputs elements in \mathbb{F}_p^*. We think of RB as a function receiving a time slot J, and positive integer k; and outputting k elements a_1, \ldots, a_k \in \mathbb{F}_p^*. We say RB is resistant to \mathcal{A}, if for any positive integers J and k for which RB is defined: for any random variable X generated by \mathcal{A} before time J, the distribution of \mathsf{RB}(J, k) is uniform in (\mathbb{F}_p^*)^k and independent of (\mathrm{rand}_{\mathcal{A}}, X).

We say RB is u-co-resistant to \mathcal{A}, if for any positive integers J and k: for any random variable X generated by \mathcal{A} before time J, the distribution of \mathsf{RB}(J,k) conditioned on any fixing of (\mathrm{rand}_{\mathcal{A}}, X) has co-min-entropy at most u (i.e. min-entropy at least k \cdot \log |\mathbb{F}_p^*| - u).

3.3 Input Domains

We assume implicitly in all method descriptions that if an input is not in the prescribed range the method outputs \mathsf{rej}. This means that in an implementation of the protocol a method expecting input in \mathbb{G}_2^* checks that the received input is indeed in this range and outputs \mathsf{rej} otherwise.

3.4 Player-exchangeable Protocols and Adaptive Adversaries

We assume there are N players P_1, \ldots, P_N in each phase of the protocol. Though we use this notation for each phase, we do not assume it is the same player P_i in each phase, nor that the identity of the player was determined before the time slot where they send their message. When we discuss an adversary \mathcal{A} controlling K players in the protocol, we mean that \mathcal{A} can adaptively choose a different subset of K players to control in each phase.

3.5 Preliminary Claims

3.6 Auxiliary Methods

We define some methods to check whether certain ratios between elements hold, using the pairing function e.

Algorithm 1 (SameRatio): Determine if x \in \mathbb{F}_p^* exists such that B = A \cdot x and D = C \cdot x. Given A, B \in \mathbb{G}_1 and C, D \in \mathbb{G}_2, check whether e(A, D) = e(B, C). If so, return \mathsf{acc}; else return \mathsf{rej}.

Algorithm 2 (Consistent): Check whether the ratio between A and B is the s \in \mathbb{F}_p^* encoded in C. This is used in the protocol verification to ensure players correctly contributed their shares.

3.7 Proofs of Knowledge

We will use a discrete log proof of knowledge scheme based on the Knowledge of Exponent assumption.

Algorithm 3 (POK): Construct a proof of knowledge of \alpha. Given \alpha \in \mathbb{F}_p^* and a string v, compute r \leftarrow \mathcal{R}([\alpha]_1, v) \in \mathbb{G}_2^*, then return ([\alpha]_1, \alpha \cdot r).

Algorithm 4 (CheckPok): Verify a proof of knowledge. Given a \in \mathbb{G}_1^*, b \in \mathbb{G}_2^*, and a string v, compute r \leftarrow \mathcal{R}(a, v) \in \mathbb{G}_2^*, then return \mathsf{SameRatio}((g_1, a), (r, b)).

[Proof of Claim 3.5 proceeds by constructing \mathcal{A}_i for each i \in [\ell], invoking the KEA assumption on each, and applying a union bound over all oracle query indices.]

4. Multi-party Computation for Parameter Generation

4.1 The Circuit Structure

We assume we have an arithmetic circuit \mathbf{C} over \mathbb{F}_p with the following structure. The circuit consists of alternate multiply/divide layers C_1, \ldots, C_d, and linear combination layers L_1, \ldots, L_d. We call d the depth of the circuit. The circuit inputs \mathbf{x} are partitioned into disjoint sets \mathbf{x}^1, \ldots, \mathbf{x}^d corresponding to the layers.

A multiply/divide layer C satisfies: (1) all gate outputs are outputs of the circuit; (2) C = C_\ell has an input gate for each of its inputs; (3) all gates besides input gates are division and multiplication gates of fan-in two. A linear combination layer L consists of linear combination gates of unbounded fan-in.

4.2 The Protocol Coordinator

In addition to messages of the players, the protocol description includes messages that are to be sent by the protocol coordinator. These messages are a deterministic function of the protocol description and the transcript up to that point. There is no need to trust this party, and anyone can later verify that the protocol coordinator’s messages are correct.

4.3 The MPC

The goal of the protocol is to compute \mathbf{C}(\mathbf{x}) \cdot \mathbf{g} for uniformly chosen \mathbf{x} \in (\mathbb{F}_p^*)^t, where t is the number of \mathbf{C}’s inputs. More specifically, we will have \mathbf{x} = \mathbf{x}_1 \cdots \mathbf{x}_N \cdot \mathbf{x}' (product defined coordinate-wise), where \mathbf{x}_i \in (\mathbb{F}_p^*)^t is the input of P_i, and \mathbf{x}' is a random beacon output.

4.4 The Phase Structure

We fix a layer \ell \in [1..d] and denote C = C_\ell, L = L_\ell. We assume that for all gates g in previous layers, we have already computed an output value [g] \in \mathbf{G}. Note that the output of every gate g \in C is a Laurent monomial in C’s inputs, possibly multiplied by an output from a previous layer.

The phase consists of three steps: (1) For each j \in [N], Player j outputs proofs of knowledge for each input and computes the partial gate values [g]^{\mathbf{j}}; (2) The protocol coordinator computes beacon values and final gate outputs; (3) The coordinator computes the linear combination layer outputs.

Verification: For each j \in [N], the protocol verifier checks: CheckPOK for each input; consistency of input updates; and consistency of gate computations (multiplication or division) with respect to their left and right inputs.

5. Security Proof

We denote by \mathbf{C}_S a random variable equal to the encoded output of the circuit \mathbf{C} with uniformly chosen input. That is, \mathbf{C}_S := [\mathbf{C}(s)] for uniform s \in (\mathbb{F}_p^*)^t. Let \mathcal{A} be an adversary that controls a subset of N-1 players in each phase. We denote by \mathbf{C}_{\mathcal{A}} the circuit output generated by \mathcal{A} participating in the protocol together with an honest player in each phase. For a predicate P with range \{\mathsf{acc}, \mathsf{rej}\}, we define

Suppose P is a predicate that runs a zk-SNARK verifier with some fixed public input, using its first input as the zk-SNARK parameters, and the second as the proof; take a constant d and u = O(\log \lambda). The theorem implies that if \mathcal{A} cannot construct a correct proof with non-negligible probability for independently generated parameters, it cannot do so for parameters generated in the protocol in which it participated.

Proof sketch. Denote by H the set of inputs of the honest player in each phase. The circuit output and the string \mathsf{z} that \mathcal{A} outputs can be viewed as a function of \mathsf{x} = (\mathrm{rand}_{\mathcal{A}}, H, \mathrm{rand}_{\mathrm{oracle}}, \mathrm{rand}_{\mathrm{beacon}}). As RB is u-co-resistant to \mathcal{A}, the beacon outputs have co-min-entropy at most ud conditioned on other randomness. By Claim 3.1:

The proof then constructs \mathcal{B} which, given [\mathbf{C}(s)], simulates the protocol with \mathcal{A} by extracting adversary inputs using the KEA extractor, choosing the honest player’s input to embed s, and programming the random oracle and beacon accordingly. The key properties are: (1) the randomness elements used are uniform and independent; and (2) aborts occur with negligible probability by Claim 3.5.

6. Reducing the Depth of Groth’s CRS

In this section we assume familiarity with Quadratic Arithmetic Programs [Gen+13a] and the work of Groth [Groth16]. Let \{u_i, v_i, w_i\}_{i \in [0..m]} \cup \{t\} be the polynomials of a degree n QAP over \mathbb{F}_p, where t is the degree n target polynomial.

The extended Groth CRS. For \alpha, \beta, \delta, x \in \mathbb{F}_p^*, \mathrm{Groth}(\alpha, \beta, \delta, x) is defined as the set of elements:

The additional elements compared to [Groth16] are \{x^i\}_{i \in [n..2n-2]}, \{\alpha x^i\}_{i \in [1..n-1]}, \{\beta x^i\}_{i \in [1..n-1]}. The elements \left\{\frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma}\right\}_{i \in [0..\ell]} and \gamma from [Groth16] have disappeared; they were needed there for verifier computation which can now be done as a linear combination of our added elements.

Groth can be computed by a depth two circuit: C_1 with inputs \{x, \alpha, \beta\} computes the power/product terms; L_1 computes linear combinations including \{x^i \cdot t(x)\} and \{\beta u_i(x) + \alpha v_i(x) + w_i(x)\}; C_2 with input \{\delta\} computes the division-by-\delta terms.

Groth prover and verifier. The prover chooses random r, s \in \mathbb{F}_p and computes:

The verifier checks that:

Proving knowledge soundness. From [Groth16] it is enough to prove that we can extract a witness for the QAP given A, B, C that are linear combinations of CRS elements such that the verification equation holds as a polynomial identity. Our focus is to show the new monomials added to the CRS — \{x^i\}_{i \in [n..2n-2]}, \{\alpha x^i\}_{i \in [1..n-1]}, \{\beta x^i\}_{i \in [1..n-1]} — are not used in A, B, C.

[The proof proceeds by monomial analysis. Since \alpha\beta \in A \cdot B, we must have \alpha \in A, \beta \in B (w.l.o.g.). Assuming \beta x^i \in A leads to \beta^2 x^k \in A \cdot B which cannot appear in C^*, yielding a contradiction. Similar arguments show \alpha x^i \notin B for i \geq 1, and that the new terms do not appear in the proof. The maximal power of x in A and B is bounded by n-1, and similarly for C.]

7. Multi-party Computation for Groth’s zk-SNARK

We now instantiate the protocol of Section 4 to get a protocol for computing the CRS of the zk-SNARK corresponding to the NILP described in Section 6. The output will have the form:

7.1 Round 1: “Powers of \tau”

We need to compute the set \mathbf{M}_1 consisting of \{[x^i]\}_{i \in [0..n-1]}, \{[x^i]_1\}_{i \in [n..2n-2]}, \{[\alpha x^i]_1\}_{i \in [0..n-1]}, [\beta], [\delta], and \{[\beta x^i]_1\}_{i \in [1..n-1]}.

Initialization: Values are initialized with [x^i]^{\mathbf{0}} := \mathbf{g} for i \in [1..n-1], and g_1 for higher powers and \alpha, \beta multiples.

Computation: For each j \in [N], P_j outputs: [\alpha_j]_1, [\beta_j]_1, [x_j]_1; proofs of knowledge y_{\alpha,j}, y_{\beta,j}, y_{x,j}; and updated partial values [x^i]^{\mathbf{j}} := x_j^i \cdot [x^i]^{\mathbf{j}-1}, [\alpha x^i]^{\mathbf{j}} := \alpha_j x_j^i \cdot [\alpha x^i]^{\mathbf{j}-1}, [\beta x^i]^{\mathbf{j}} := \beta_j x_j^i \cdot [\beta x^i]^{\mathbf{j}-1}.

After the last player, the coordinator obtains beacon values (x', \alpha', \beta') := \mathsf{RB}(J, 3) and computes the final values, e.g. [x^i] := x'^i \cdot [x^i]^{\mathbf{N}}.

Verification: The verifier checks CheckPOK for each player’s \alpha, \beta, x contributions, consistency of each contribution with its proof of knowledge, and structural consistency (e.g., that successive powers are consistent with the base element).

7.2 Linear Combinations Between Phases

For i \in [0..n-2], we compute as linear combinations of \{[x^i]_1\}_{i \in [0..2n-2]} the element H_i' := [t(x)x^i]_1. Using Lagrange polynomials and FFT with O(n \log n) group operations, we compute \mathrm{LAG}_x and then obtain the QAP-related linear combinations including K_i' := [\beta u_i(x) + \alpha v_i(x) + w_i(x)]_1 for i \in [\ell+1..m].

7.3 Round Two

For i \in [\ell+1..m], denote K_i := \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\delta}. For i \in [0..n-2], denote H_i := \frac{t(x)x^i}{\delta}. We need to compute \mathbf{M}_2 = \{[\delta], \{[K_i]_1\}_{i \in [\ell+1..m]}, \{[H_i]_1\}_{i \in [0..n-2]}\}.

Computation: For each j \in [N], P_j outputs [\delta_j]_1, proof of knowledge y_{\delta,j}, and updated partial values by dividing by \delta_j: [\delta]^{\mathbf{j}} := [\delta]^{\mathbf{j}-1}/\delta_j, [K_i]^{\mathbf{j}} := [K_i]^{\mathbf{j}-1}/\delta_j, [H_i]^{\mathbf{j}} := [H_i]^{\mathbf{j}-1}/\delta_j. At the end, the beacon output \delta' is applied similarly.

Verification: The verifier checks CheckPOK for each \delta_j, consistency of [\delta] updates, and consistency of [K_i] and [H_i] updates.

8. BLS12-381

The most common pairing-friendly elliptic curve construction used in zk-SNARK software is a Barreto-Naehrig [BarNae05] (BN) construction with a 254-bit base field and group order, as designed in [Ben-Sasson+13b]. Although the construction originally targeted the 128-bit security level, recent optimizations to the Number Field Sieve algorithm [KimBar15] have reduced its concrete security.

Subsequent analysis [MenSarSin16] recommended that BN curves and Barreto-Lynn-Scott (BLS) curves [BarLynSco02] with embedding degree k = 12 have approximately 384-bit base fields in order to target 128-bit security. BLS12 curves with 384-bit base fields give rise to 256-bit group orders, making them ideal for use with zk-SNARKs.

The largest construction with smallest Hamming weight that meets the requirements is x = -2^{63} - 2^{62} - 2^{60} - 2^{57} - 2^{48} - 2^{16}, which is named BLS12-381. This curve exists within a subfamily of curves, as in [CosLauNae11], which have immediately determined curve parameters. The authors provide an implementation of this curve in Rust [Pairing17].

9. Implementation and Experiments

The implementation of both MMORPG and the pairing library is in Rust. All benchmarks for phase 1 and 2 were done on an Intel Core i7-3770S CPU @ 3.10GHz with 32GB of RAM running Arch Linux.

Because the performance of the protocol is independent of the number of participants, the experimental setup simply measures the performance of a single user in each phase. The experiments consist of running MMORPG for three different circuit sizes: 2^{10}, 2^{17}, and 2^{21} gates. 2^{21} is the size of the largest circuit publicly generated using [BowGabGre17] and corresponds to approximately 60 SHA256 invocations. 2^{17} corresponds to the size of the proposal for the next generation of Zcash [Bowe17].

Bandwidth: For circuit size 2^{15}, phase 1 requires 1.13 GB download / 0.56 GB upload, and phase 2 requires 0.37 GB download / 0.19 GB upload. The results show that a user need only spend 15 minutes doing a computation and after that need no longer participate, requiring low investment and no need to maintain heightened security for extended periods.

Acknowledgements

We thank Paulo Barreto for helpful feedback about the BLS12-381 elliptic curve. We thank Daniel Benarroch, Daira Hopwood and Antoine Rondelet for helpful comments. We thank the anonymous reviewers of S&P 2018 for their comments.

References

• [Bonneau17] Joseph Bonneau. Personal communication.
• [Pairing17] Pairing library. github.com/ebfull/pairing.
• [Zcash17] Zcash. z.cash.
• [Ames+17] Scott Ames, Carmit Hazay, Yuval Ishai, and Muthuramakrishnan Venkitasubramaniam. “Ligero: Lightweight Sublinear Arguments Without a Trusted Setup”. In: CCS 2017, pp. 2087–2104, 2017.
• [Aranha+12] Diego F. Aranha, Laura Fuentes-Castañeda, Edward Knapp, Alfred Menezes, and Francisco Rodríguez-Henríquez. “Implementing Pairings at the 192-bit Security Level”. Cryptology ePrint Archive, Report 2012/232, 2012.
• [BarDuq17] Razvan Barbulescu and Sylvain Duquesne. “Updating Key Size Estimations for Pairings”. Cryptology ePrint Archive, Report 2017/334, 2017.
• [BarLynSco02] Paulo S. L. M. Barreto, Ben Lynn, and Michael Scott. “Constructing Elliptic Curves with Prescribed Embedding Degrees”. Cryptology ePrint Archive, Report 2002/088, 2002.
• [BarNae05] Paulo S. L. M. Barreto and Michael Naehrig. “Pairing-friendly Elliptic Curves of Prime Order”. Cryptology ePrint Archive, Report 2005/133, 2005.
• [Ben-Sasson+15] E. Ben-Sasson, A. Chiesa, M. Green, E. Tromer, and M. Virza. “Secure Sampling of Public Parameters for Succinct Zero Knowledge Proofs”. In: IEEE S&P 2015, pp. 287–304, 2015.
• [Ben-Sasson+17a] Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, and Madars Virza. “Computational Integrity with a Public Random String from Quasi-Linear PCPs”. In: EUROCRYPT 2017, Part III, pp. 551–579, 2017.
• [Ben-Sasson+14] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. “Zerocash: Decentralized Anonymous Payments from Bitcoin”. In: IEEE S&P 2014, pp. 459–474, 2014.
• [Ben-Sasson+13a] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. “SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge”. In: CRYPTO 2013, pp. 90–108, 2013.
• [Ben-Sasson+13b] Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. “SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge”. Cryptology ePrint Archive, Report 2013/507, 2013.
• [Bishop15] Bryan Bishop. “Review of Bitcoin Scaling Proposals”. In: Scaling Bitcoin Workshop Phase, vol. 1, 2015.
• [Bitansky+13] Nir Bitansky, Alessandro Chiesa, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth. “Succinct Non-interactive Arguments via Linear Interactive Proofs”. In: TCC 2013, pp. 315–333, 2013.
• [BowGabGre17] S. Bowe, A. Gabizon, and M. D. Green. “A Multi-party Protocol for Constructing the Public Parameters of the Pinocchio zk-SNARK”. IACR Cryptology ePrint Archive, 2017:602, 2017.
• [Bowe17] Sean Bowe. “Cultivating Sapling: Faster zk-SNARKs”. z.cash/blog, September 2017.
• [BunGolBon17] Benedikt Bünz, Steven Goldfeder, and Joseph Bonneau. “Proofs-of-delay and Randomness Beacons in Ethereum”. In: S&B 2017, April 2017.
• [ButPoo17] Vitalik Buterin and Joseph Poon. “Plasma: Scalable Autonomous Smart Contracts”. plasma.io, August 2017.
• [Chiesa+17] Alessandro Chiesa, Matthew Green, Jingcheng Liu, Peihan Miao, Ian Miers, and Pratyush Mishra. “Decentralized Anonymous Micropayments”. In: EUROCRYPT 2017, Part II, pp. 609–642, 2017.
• [CosLauNae11] Craig Costello, Kristin Lauter, and Michael Naehrig. “Attractive Subfamilies of BLS Curves for Implementing High-Security Pairings”. Cryptology ePrint Archive, Report 2011/465, 2011.
• [Fuchsbauer17] Georg Fuchsbauer. “Subversion-zero-knowledge SNARKs”. Cryptology ePrint Archive, Report 2017/587, 2017.
• [Gen+13a] R. Gennaro, C. Gentry, B. Parno, and M. Raykova. “Quadratic Span Programs and Succinct NIZKs without PCPs”. In: EUROCRYPT 2013, pp. 626–645, 2013.
• [Gen+13b] Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. “Quadratic Span Programs and Succinct NIZKs without PCPs”. In: EUROCRYPT 2013, pp. 626–645, 2013.
• [Gilad+17] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. “Algorand: Scaling Byzantine Agreements for Cryptocurrencies”. In: SOSP 2017, pp. 51–68, 2017.
• [Goldwasser+13] Shafi Goldwasser, Yael Kalai, Raluca Ada Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich. “How to Run Turing Machines on Encrypted Data”. Cryptology ePrint Archive, Report 2013/229, 2013.
• [Groth16] J. Groth. “On the Size of Pairing-based Non-interactive Arguments”. In: EUROCRYPT 2016, Part II, pp. 305–326, 2016.
• [Groth10] Jens Groth. “Short Pairing-based Non-interactive Zero-knowledge Arguments”. In: ASIACRYPT 2010, pp. 321–340, 2010.
• [Kilian92] Joe Kilian. “A Note on Efficient Zero-knowledge Proofs and Arguments (Extended Abstract)”. In: STOC 1992, pp. 723–732, 1992.
• [KimBar15] Taechan Kim and Razvan Barbulescu. “Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case”. Cryptology ePrint Archive, Report 2015/1027, 2015.
• [Kosba+16] Ahmed Kosba, Andrew Miller, Elaine Shi, Zikai Wen, and Charalampos Papamanthou. “Hawk: The Blockchain Model of Cryptography and Privacy-preserving Smart Contracts”. In: IEEE S&P 2016, pp. 839–858, 2016.
• [Lipmaa12] Helger Lipmaa. “Progression-free Sets and Sublinear Pairing-based Non-interactive Zero-knowledge Arguments”. In: TCC 2012, pp. 169–189, 2012.
• [Lipmaa13] Helger Lipmaa. “Succinct Non-interactive Zero Knowledge Arguments from Span Programs and Linear Error-correcting Codes”. In: ASIACRYPT 2013, pp. 41–60, 2013.
• [MenSarSin16] Alfred Menezes, Palash Sarkar, and Shashank Singh. “Challenges with Assessing the Impact of NFS Advances on the Security of Pairing-based Cryptography”. Cryptology ePrint Archive, Report 2016/1102, 2016.
• [Micali00] Silvio Micali. “Computationally Sound Proofs”. In: SIAM J. Comput., 30(4):1253–1298, 2000.
• [Parno+13] Bryan Parno, Craig Gentry, Jon Howell, and Mariana Raykova. “Pinocchio: Nearly Practical Verifiable Computation”. In: IEEE S&P 2013, pp. 238–252, 2013.
• [Peck16] Morgen E. Peck. “The Crazy Security Behind the Birth of Zcash, the Inside Story”. IEEE Spectrum, December 2016.
• [EthTeam17] Ethereum Team. “Byzantium HF Announcement”. blog.ethereum.org, October 2017.