An Efficient Verifiable State for zk-EVM and Beyond from the Anemoi Hash Function

Abstract

In our survey of the various zk-EVM constructions, it becomes apparent that verifiable storage of the EVM state starts to be one of the dominating costs. This is not surprising because a big differentiator of EVM from UTXO is exactly the ability to carry states and, most importantly, their transitions; i.e., EVM is a state machine.

In other words, to build an efficient zk-EVM, one must first build an efficient verifiable state. The common approach, which has been used in production, is a Merkle forest to authenticate the memory that would be randomly accessed within zk-SNARK, and optimize the verification of such memory accesses.

In this note, we describe a way to instantiate a Merkle tree with very few gates in TurboPlonk. We use customized gates in TurboPlonk to implement a SNARK-friendly hash function called Anemoi and its Jive mode of operation [Bou+22], by Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Léo Perrin, Robin Salen, Vesselin Velichkov, and Danny Willems.

We demonstrate that with 16 gates (\approx 1 gate per round in a 14-round Anemoi hash), one can verify a 3-to-1 compression in a 3-ary Merkle tree. Before this, prior implementations would often require hundreds of gates. We anticipate this technique to benefit a large number of applications built off zk-SNARK.

Code: github.com/FindoraNetwork/noah

1. Introduction

Verifiable accesses to persistent storage (referred to as “state” in the rest of the note) have been a recurring topic in the research of zero-knowledge proofs for many years. The history of finding an efficient instantiation can be summarized as follows.

• SNARK with a quasilinear prover is a critical enabler of the original Zerocash paper [Ben+14], which uses SHA256 to build a Merkle tree for a verifiable state. In the paper, for each layer of the binary Merkle tree, it takes 28161 R1CS constraints.
• Ajtai hash, or the subset sum hash, is used in an SOSP paper for verifiable state [BFRSBW13] and then the proof-carrying data via cycles of curves paper [BCTV14].
• Pedersen hash over a suitable embedded curve is used in production first in the Sapling upgrade to Zcash. In the end, Pedersen hash shows that for each layer, one can do with about 1000 R1CS constraints.
• Starting from MiMC [AGRRT16], we have witnessed a number of algebraic hash functions that are designed to be SNARK-friendly. Many prior instantiations have about 300 R1CS constraints and about 150 customized gates for verification of each layer of the Merkle tree.

Trend: algebraic-hash-proof-system co-design. There is a trend of research for algebraic hashes to be designed, not just as standalone cryptographic instantiations, but also related to a particular proof system. The future will be a closer collaboration between practitioners and cryptanalysts, i.e., a co-design of algebraic hashes and proof systems.

1.1 Our Approach: Use the Standard TurboPlonk Recipe on Anemoi

Our approach is to leverage a recent algebraic hash function—Anemoi [Bou+22]—and tweak an existing TurboPlonk implementation to inline Anemoi as part of the proof system. We do not claim novelty for our work of tweaking, as it follows the standard recipe of TurboPlonk.

Our approach: inline Anemoi in TurboPlonk. The Anemoi hash follows the substitution-permutation network (SPN). It consists of four steps: constant additions, MDS diffusion, pseudo-Hadamard transform, and S-box. A round with input (a, b, c, d) is being processed correctly resulting in output (a'', b'', c'', d'') if and only if the following equations are satisfied.

where g is a generator of the field \mathbb{F}, (a', b', c', d') is the result of applying the linear layer and the pseudo-Hadamard transform to (a, b, c, d), defined as follows:

If we use a TurboPlonk with four input wires (w_1, w_2, w_3, w_4), we can replace (a, b, c, d) and (a'', b'', c'', d'') as the input for the j-th gate and the (j+1)-th gate. Using an additional selector polynomial q_{sel1}(X), the constraint can be expressed such that all gates satisfy the equations. The prover convinces the verifier by committing witness polynomials and opening them at a random point \zeta.

Experiment results. To demonstrate the efficiency of using Anemoi hash function, measurements were conducted over the BN254 curve on a c6i.xlarge AWS instance:

• Number of gates: 16 per Jive compression
• Indexer time: 2.51 ms per Jive compression
• Re-indexer time: 1.25 ms per Jive compression
• Prover time: 1.61 ms per Jive compression
• Verifier time: 4.55 ms (constant verification cost)

Compared with previous techniques that take hundreds of gates, using Anemoi reduces the number of gates needed for a Merkle tree membership proof by about 7\times.

1.2 Applications on Scalability: zk-Rollup, zk-EVM, and zk-BatchVerify

An efficient SNARK-friendly hash implementation benefits applications that seek for improving blockchain efficiency: zk-Rollup, zk-EVM, and zk-BatchVerify.

zk-Rollup: Rolling up a number of coin transfer operations is often done by maintaining and updating a Merkle tree of all accounts and their associated balances, with a zero-knowledge proof showing all operations are legitimate. By making the proving cost for the Merkle tree membership proof cheaper, we reduce the overhead to maintain and update account balances.

zk-EVM: In zk-EVM, layer 2 rolls up not only simple transactions but also smart contract executions. A more pressing challenge for zk-EVM is the “random access” part—the EVM may access a few locations in a large memory, and these locations cannot be easily predicted. One can build an application-specific SNARK-friendly state representation through a Merkle forest.

zk-BatchVerify: A proposed substitute for layer-1 on-chain proof verification. Layer 2 verifies proofs and returns verification results to layer 1 via a Merkle tree arrangement. The SNARK-friendly hash function is used in various places in this system, and improvement on the hash function reduces overhead throughout the construction.

1.3 Applications on Security: Zerocash, zk-DID, and zk-Bridge

An efficient SNARK-friendly hash implementation also benefits various applications that offer security: Zerocash, zk-DID, and zk-Bridge. It is important to realize that efficiency is a crucial limiting factor for the adoption of these applications.

Zerocash: In many dApps, the prover runs in WebAssembly, leading to a performance penalty of 10\times. With a SNARK-friendly hash, the SRS can be shorter and the prover lighter. zk-DID: Privacy ensures minimal information disclosure; the same prover efficiency issue arises. zk-Bridge (redundancy bridge): Zero-knowledge proofs can verify source chain consensus and expected contract executions; the use of a SNARK-friendly hash benefits the persistent state access via Merkle trees.

1.4 Rest of the Note

The rest of the note is organized as follows: Section 2 provides background on TurboPlonk and Anemoi components; Section 3 provides the starting point; Section 4 presents an initial (unoptimized) construction; Section 5 discusses standard optimization techniques; Section 6 gives the detailed final construction; Section 7 describes a design and implementation of privacy token transfer using Anemoi-based Merkle trees; and Section 8 lists reference materials.

2. Background

This section provides the necessary background on TurboPlonk, the Flystel S-box, the Anemoi permutation, the Jive mode of operation, and the Anemoi variable-length hash.

2.1 TurboPlonk

TurboPlonk is Plonk [GWC19] with customized gates. There are many different ways to construct customized gates, and as a result, TurboPlonk does not mean a specific construction, but a family of proof systems based on Plonk.

Circuit representation. TurboPlonk expresses the statement to be proven in zero knowledge as a circuit of gates. Each gate has the same number of wires. TurboPlonk enforces that these gates satisfy certain conditions, consisting of a gate check and a copy check.

Gate check: Each gate has parameters (“selectors”) that define a gate predicate G_i(w_1, w_2, w_3, w_4, w_o) \in \{0, 1\}. The gate check passes if for every gate G_i(w_1, w_2, w_3, w_4, w_o) = 0.

Copy check: To combine gates and represent a full statement, wires between different gates are connected. These connections are expressed as a permutation \sigma over all wires, ensuring connected wires carry the same value.

Arithmetization. TurboPlonk interpolates wire values into polynomials w_1(X), w_2(X), w_3(X), w_4(X), w_o(X) and gate parameters into selector polynomials. The gate check becomes the existence of a polynomial g(X) such that:

The copy check uses a permutation polynomial S(X) defined via a recursion involving a universal one-way hash H(x, y) = x + \beta y + \gamma. Both checks are verified via polynomial IOPs: the prover sends polynomial commitments and opens them at a random point, and the verifier checks by the DeMillo–Lipton–Zippel –Schwartz lemma.

“Supergates”: An important observation is that the gate function can check multiple equations simultaneously. For example, boolean testing constraints q_b(X) \cdot w_i(X) \cdot (w_i(X) - 1) = 0 can be enforced alongside the main gate equation.

2.2 Flystel S-box: Rotating an Algebraic Butterfly

The Flystel S-box [Bou+22] is based on the butterfly structure. It takes input (x, y) and outputs (x', y'). The open butterfly formulas are:

Computing (\cdot)^{1/\alpha} is expensive. The key insight is that by rotating the butterfly counterclockwise, we obtain the closed form:

This is a low-degree polynomial (for BLS12-381, \alpha = 5). Although slightly expensive to compute, it is easy to verify given both input and output, making it ideal for use in a substitution-permutation network within zk-SNARK.

2.3 Anemoi Permutation: a Substitution-Permutation Network

The Anemoi permutation [Bou+22] follows the standard SPN structure with N rounds. Each round consists of four steps for input (\vec{x}, \vec{y}) \in (\mathbb{F}^\ell, \mathbb{F}^\ell):

• Constant addition: Output (\vec{x} + \vec{c}_r, \vec{y} + \vec{d}_r) using round-specific constants.
• MDS matrix: Apply a fixed MDS matrix M \in \mathbb{F}^{\ell \times \ell} to both halves (with a shift on \vec{y}).
• Pseudo-Hadamard transform: Mix \vec{x} and \vec{y} via \vec{v} := \vec{y} + \vec{x} and \vec{u} := \vec{y} + 2\vec{x}.
• S-box: Apply the Flystel S-box component-wise.

The operations are repeated for N rounds, followed by an additional MDS step, yielding a permutation \mathbb{F}^{2\ell} \to \mathbb{F}^{2\ell}.

2.4 Jive Mode of Operation: k-to-1 Compression for Merkle Trees

An important observation in [Bou+22] is that for Merkle trees in zk-SNARK, we only need a collision-resistant hash function (CRH), not a full random oracle. The Anemoi paper shows a CRH construction directly from the permutation P(\vec{x}, \vec{y}) \to (\vec{u}, \vec{v}):

The cost of the CRH is therefore very close to the cost of the permutation itself, and it is used to instantiate the Merkle tree in zk-SNARK.

2.5 Anemoi Variable-Length Hash: a Sponge Construction

The Anemoi permutation can be used to construct a sponge using the Hirose variant [Hir18]. When the field \mathbb{F} is sufficiently large, for a permutation from \mathbb{F}^{2\ell} to \mathbb{F}^{2\ell}, one can create a sponge with rate (2\ell - 1) and capacity 1. The sponge construction is naturally immune to length-extension attacks.

3. Starting Point

The starting point is a regular TurboPlonk implementation, specified via polynomial identity relations and a strategy to open the polynomials. The standard copy check is used. For any element x in a domain H, the gate check includes:

along with boolean testing supergates:

In the linearization step, polynomials are opened at random points, replacing polynomial evaluations with their values at \zeta.

4. Initial Attempt

The note focuses on the case where \ell = 2. The customized gates are designed by representing the equations directly into polynomial identity relations and inlining the linear layer into these relations. The key relationship is between the state after the S-box in a round (x[Abdelrahaman20], x[Martin16], y[Abdelrahaman20], y[Martin16]) and the state after S-box in the following round (x'[Abdelrahaman20], x'[Martin16], y'[Abdelrahaman20], y'[Martin16]).

Processed round keys (PRK). After applying constant addition, MDS matrix, and pseudo-Hadamard transform, we define processed round keys for each round r:

The wire assignments use w_1(X) = x[Abdelrahaman20], w_2(X) = x[Martin16], w_3(X) = y[Abdelrahaman20], w_4(X) = y[Martin16], with w_i(X\omega) for the next-round values. Four selector polynomials q_{sel1}(X) through q_{sel4}(X) control whether each Anemoi equation applies to a given gate. The four polynomial identity relations for the closed Flystel butterfly are:

Cost analysis. The initial attempt has cost 8 + 12: additional indexing for 4 selector and 4 processed key polynomials, plus additional openings for all 4 selectors, 4 processed keys, and 4 witness polynomials at shifted points.

5. Optimization

This section discusses standard optimization techniques applied to the initial construction. These ideas have been used in production TurboPlonk implementations.

5.1 Use Processed Round Key Polynomials as Selectors

For Anemoi-related gates, the processed round key polynomials are nonzero with overwhelming probability. For non-Anemoi gates, we set q_{prk1}(X) through q_{prk4}(X) to zero. This allows replacing the four selector polynomials q_{sel1}(X) through q_{sel4}(X) with q_{prk3}(X) for all four equations, reducing the cost to 4 + 8.

5.2 Skip Unnecessary Opening During Linearization

Not all polynomials need to be opened. The polynomials q_{prk3}(X) and q_{prk4}(X) appear inside a bracket of (\cdot)^5, requiring them to be opened. However, q_{prk1}(X) and q_{prk2}(X) are linear components and can use commitment-based verification. This reduces the cost to 4 + 6.

5.3 Connect the Output Wire to the Next Gate

The construction uses w_1(\zeta), \ldots, w_4(\zeta) and w_1(\zeta\omega), \ldots, w_3(\zeta\omega) but never w_o(\zeta). By substituting w_4(\zeta\omega) with w_o(\zeta) and enforcing correctness via the copy check, we save one opening. The final optimized equations use w_o(X) in place of w_4(X\omega) in the second and fourth equations, reducing the cost to 4 + 5.

5.4 Other Unexplored Optimization

Several additional optimizations were not explored: explicitly structured round keys (may reduce the number of processed round key polynomials), more than five wires (may reduce gates but increases FFT and MSM costs), using \alpha = 3 where permissible (not applicable for BLS12-381 since 3 \mid (q-1)), and using a higher \alpha in the S-box (minor round reduction but increased costs).

6. Final Protocol

The final polynomial identity relations combine the standard TurboPlonk gate check, boolean testing supergates, and four Anemoi/Jive equations using q_{prk3}(X) as the selector and w_o(X) replacing w_4(X\omega) in the second and fourth equations.

6.1 Indexer

The indexer computes commitments and openings for 14 selector polynomials (q_1, q_2, q_3, q_4, q_o, q_{m1}, q_{m2}, q_c, q_{ecc}, q_b, q_{prk1}, q_{prk2}, q_{prk3}, q_{prk4}) and 5 permutation polynomials (S_{\sigma 1}, \ldots, S_{\sigma o}). The indexer proceeds in three steps: (1) commit all polynomials, (2) precompute helper polynomials L_1(X) and Z_H(X), and (3) compute the Lagrange interpolation constants c_j.

6.2 Prover

The prover follows 11 steps:

1. Assemble public inputs.
2. Instantiate the verifier (Fiat-Shamir sponge).
3. Commit witness polynomials with hiding. Given w_1(X), \ldots, w_o(X), add random blinding polynomials:
   \widetilde{w_1}(X) = w_1(X) + Z_H(X) \cdot (b_1 X^2 + b_2 X + b_3)
4. Build the sigma polynomial for wiring (using challenges \beta, \gamma).
5. Commit the sigma polynomial with hiding.
6. Compute the quotient polynomial t(X) using challenge \alpha, incorporating all gate checks, copy checks, boolean tests, and four Anemoi/Jive terms t_{h1}(X) through t_{h4}(X).
7. Commit the split quotient polynomials t_1(X), \ldots, t_5(X).
8. Open the polynomials at a random point \zeta: 15 evaluations including q_{prk3}(\zeta), q_{prk4}(\zeta), \widetilde{w_1}(\zeta\omega), \widetilde{w_2}(\zeta\omega), \widetilde{w_3}(\zeta\omega).
9. Compute the linearization polynomial r(X).
10. Compute the opening proof polynomials W_\zeta(X) and W_{\zeta\omega}(X).
11. Output the full proof.

The final proof consists of 5 witness commitments, 1 sigma commitment, 5 quotient commitments, 15 field element openings, and 2 opening proof commitments.

6.3 Verifier

The verifier proceeds in 7 steps:

1. Compute all challenges \beta, \gamma, \alpha, \zeta, v, u via the Fiat-Shamir sponge.
2. Compute r(\zeta) from the opening evaluations, including the four Anemoi/Jive terms.
3. Assemble \text{cm}_r from available commitments using linear homomorphism.
4. Compute linear combination of commitments \text{cm}.
5. Compute linear combination of evaluations s.
6. Pairing: Compute L = e((\text{cm}_\zeta + u \cdot \text{cm}_{\zeta\omega}), x \cdot H) and R = e((\zeta \cdot \text{cm}_\zeta + u \cdot \zeta \cdot \omega \cdot \text{cm}_{\zeta\omega} + \text{cm} - s \cdot G), H).
7. Decision: Accept if L = R.

7. Design and Implementation

This section presents an application of the Anemoi hash function and the proof system: an anonymous privacy token transfer based on the Zerocash construction [Ben+14], focusing on the Merkle tree membership proof in zk-SNARK. The code is available in the Noah library.

7.1 3-ary Merkle Tree

Coin commitments are organized into a 3-ary Merkle tree storing about 2^{32} coin commitments. Internal node values are h = H(\text{left} \| \text{mid} \| \text{right}). The 3-to-1 compression is implemented using Jive CRH with \ell = 2, which actually provides 4-to-1 compression; a constant is used for the 4th input for domain separation.

7.2 Domain Separation in the Jive CRH

The Anemoi hash function uses the first 200 digits of \pi to generate round keys. The next 200 digits are used through the opened Flystel structure to generate 20 padding constants. For the i-th level of the Merkle tree, the i-th padding constant is used during compression.

7.3 Concrete Instantiation for the Jive CRH

The constraint system for the Jive CRH is organized as follows:

• 1st round: Create a gate with w_1 = x[Abdelrahaman20], w_2 = x[Martin16], w_3 = y[Abdelrahaman20], w_4 = y[Martin16], w_o = y'[Martin16]. Apply the Anemoi constraint with appropriate PRK values and enforce w_4 = \text{salt}.
• Rounds 2–14: Progress the state and create a gate per round with the Anemoi constraint; suppress all other constraints.
• Sum of output: Create a gate computing the sum of the final permutation output with appropriate coefficients (q_1 = 2g, q_2 = g^2 + g + 1, etc.).
• Sum of input and output: Create a gate computing the Jive CRH result as the sum of inputs, output sum, and salt.

In total, one invocation of the Jive CRH takes 14 gates (plus 2 for output summation, totaling 16).

7.4 Concrete Instantiation for the Merkle Tree Membership Proof

The Merkle tree membership proof in zk-SNARK verifies a path from a leaf to the root:

• Compute the leaf hash by applying the Anemoi variable-length hash function.
• Going up the tree path, compute three binary variables: \text{is-left-child}, \text{is-mid-child}, \text{is-right-child}, with boolean and summation checks enforced via gates.
• In each layer, verify the node is in the correct location using two gates: one for partial sum via multiplication gates, another for combining via a linear gate.
• Use the Jive CRH to check hashes layer by layer.

8. Reference Materials

SNARK-friendly hash functions. Cryptographically secure hash functions for prime fields have been increasingly researched. Notable examples include MiMC [AGRRT16], Poseidon [GKRRS21], Rescue [AABSDS20], and Anemoi [Bou+22]. These commonly serve two roles in zk-SNARK: as collision-resistant hash functions for Merkle trees, and as Fiat-Shamir sponges for proof recursion.

TurboPlonk variants. Since the invention of TurboPlonk [Tur], many variants have been deployed including Matter Labs’s Franklin crypto library [Fra], Polygon Zero’s Plonky2 [Plo], Dusk Network’s PLONK [Dus], and Zcash’s Halo2 [Hal].

Verifiable data structures. Four common types are used in zk-SNARK: Merkle trees [Mer87], RSA accumulators [BM93; LLX07; BBF19], offline memory checking [BEGKN91; CDDGS03; SAGL18; Set20], and table lookup [ZBKMNS22; PK22; GK22].

Acknowledgments

We had a discussion with the authors of [Bou+22] and learned a lot about Anemoi. We would like to thank Daira Hopwood, Yuncong Hu, Dmitry Khovratovich, Pratyush Mishra, Robin Salen, Markus Schöfnegger, Danny Willems, and Zhenfei Zhang for discussions that eventually helped make this work.

We would also like to thank the researchers who have pioneered the study of SNARK-friendly hash functions, despite the fact that it is known among researchers that these constructive cryptanalysis papers have a harder time in the peer-review process.

Update: We would like to congratulate Anemoi (as well as Griffin) for being accepted in CRYPTO 2023. This is a breakthrough over prior constructive SNARK-friendly hash function papers. The progression includes: LowMC (EUROCRYPT 2015), MiMC (ASIACRYPT 2016), GMiMC (ESORICS 2019), Rescue (FSE 2020), Poseidon (USENIX Security 2021), Reinforced Concrete (CCS 2022), Ciminion (EUROCRYPT 2022), and now Anemoi and Griffin (CRYPTO 2023).

References

• [AABSDS20] Abdelrahaman Aly, Tomer Ashur, Eli Ben-Sasson, Siemen Dhooghe, and Alan Szepieniec. “Design of symmetric-key primitives for advanced cryptographic protocols”. In: FSE ’20. 2020.
• [AGRRT16] Martin Albrecht, Lorenzo Grassi, Christian Rechberger, Arnab Roy, and Tyge Tiessen. “MiMC: Efficient encryption and cryptographic hashing with minimal multiplicative complexity”. In: ASIACRYPT ’16. 2016.
• [BBF19] Dan Boneh, Benedikt Bünz, and Ben Fisch. “Batching techniques for accumulators with applications to IOPs and stateless blockchains”. In: CRYPTO ’19. 2019.
• [BCMS20] Benedikt Bünz, Alessandro Chiesa, Pratyush Mishra, and Nicholas Spooner. “Proof-carrying data from accumulation schemes”. In: TCC ’20. 2020.
• [BCS16] Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner. “Interactive oracle proofs”. In: TCC ’16b. 2016.
• [BCTV14] Eli Ben-Sasson, Alessandro Chiesa, Eran Tromer, and Madars Virza. “Scalable zero knowledge via cycles of elliptic curves”. In: CRYPTO ’14. 2014.
• [BEGKN91] Manuel Blum, Will Evans, Peter Gemmell, Sampath Kannan, and Moni Naor. “Checking the correctness of memories”. In: FOCS ’91. 1991.
• [BFRSBW13] Benjamin Braun, Ariel J. Feldman, Zuocheng Ren, Srinath Setty, Andrew J. Blumberg, and Michael Walfish. “Verifying computations with state”. In: SOSP ’13. 2013.
• [BM93] Josh Benaloh and Michael de Mare. “One-way accumulators: A decentralized alternative to digital signatures”. In: EUROCRYPT ’93. 1993.
• [Ben+14] Eli Ben-Sasson, Alessandro Chiesa, Christina Garman, Matthew Green, Ian Miers, Eran Tromer, and Madars Virza. “Zerocash: Decentralized anonymous payments from Bitcoin”. In: S&P ’14. 2014.
• [Bou+22] Clémence Bouvier, Pierre Briaud, Pyrros Chaidos, Robin Salen, Léo Perrin, Vesselin Velichkov, and Danny Willems. “New design techniques for efficient arithmetization-oriented hash functions: Anemoi permutations and Jive compression”. In: IACR ePrint 2022/840. 2022. [page on this site]
• [CCZ98] Claude Carlet, Pascale Charpin, and Victor Zinoviev. “Codes, bent functions and permutations suitable for DES-like cryptosystems”. In: Designs, Codes and Cryptography ’98. 1998.
• [CDDGS03] Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, and G. Edward Suh. “Incremental multiset hash functions and their application to memory integrity checking”. In: ASIACRYPT ’03. 2003.
• [CHMMVW20] Alessandro Chiesa, Yuncong Hu, Mary Maller, Pratyush Mishra, Noah Vesely, and Nicholas Ward. “Marlin: Preprocessing zkSNARKs with universal and updatable SRS”. In: EUROCRYPT ’20. 2020.
• [CL20] Alessandro Chiesa and Siqi Liu. “On the impossibility of probabilistic proofs in relativized worlds”. In: ITCS ’20. 2020.
• [CL99] Miguel Castro and Barbara Liskov. “Practical Byzantine fault tolerance”. In: OSDI ’99. 1999.
• [CP17] Anne Canteaut, Sébastien Duval, and Léo Perrin. “A generalisation of Dillon’s APN permutation with the best known differential and nonlinear properties for all fields of size 2^{4k+2}”. In: IEEE Trans. Information Theory ’17. 2017.
• [Can01] Ran Canetti. “Universally composable security: A new paradigm for cryptographic protocols”. In: FOCS ’01. 2001.
• [DL78] Richard A. Demillo and Richard J. Lipton. “A probabilistic remark on algebraic program testing”. In: Information Processing Letters ’78. 1978.
• [Dai] Daira Hopwood. Response in “choose improved hash function for Merkle Tree (or replace Merkle Tree)” PR #2258 to zcash/zcash. url: github.com/zcash/zcash/issues/2258.
• [Dus] Dusk Plonk. url: github.com/dusk-network/plonk.
• [Fra] franklin-crypto: Gadget library for PLONK/Plookup. url: github.com/matter-labs/franklin-crypto.
• [GK22] Ariel Gabizon and Dmitry Khovratovich. “flookup: Fractional decomposition-based lookups in quasi-linear time independent of table size”. In: IACR ePrint 2022/1447. 2022. [page on this site]
• [GKLRSW21] Lorenzo Grassi, Dmitry Khovratovich, Reinhard Lüftenegger, Christian Rechberger, Markus Schöfnegger, and Roman Walch. “Reinforced Concrete: A fast hash function for verifiable computation”. In: IACR ePrint 2021/1038. 2021. [page on this site]
• [GKRRS21] Lorenzo Grassi, Dmitry Khovratovich, Christian Rechberger, Arnab Roy, and Markus Schöfnegger. “Poseidon: A new hash function for zero-knowledge proof systems”. In: USENIX Security ’21. 2021. [page on this site]
• [GWC19] Ariel Gabizon, Zachary J. Williamson, and Oana Ciobotaru. “PLONK: Permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge”. In: IACR ePrint 2019/953. 2019. [page on this site]
• [Gab19] Ariel Gabizon. “AuroraLight: Improved prover efficiency and SRS size in a Sonic-like system”. In: IACR ePrint 2019/601. 2019. [page on this site]
• [Gro16] Jens Groth. “On the size of pairing-based non-interactive arguments”. In: EUROCRYPT ’16. 2016.
• [HBHW] Daira Hopwood, Sean Bowe, Taylor Hornby, and Nathan Wilcox. Zcash protocol specification. url: zips.z.cash/protocol/protocol.pdf.
• [Hal] halo2. url: github.com/zcash/halo2.
• [Hir18] Shoichi Hirose. “Sequential hashing with minimum padding”. In: MDPI Cryptography ’18. 2018.
• [Jub] What is Jubjub? url: z.cash/technology/jubjub/.
• [KZG10] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. “Constant-size commitments to polynomials and their applications”. In: ASIACRYPT ’10. 2010.
• [LLX07] Jiangtao Li, Ninghui Li, and Rui Xue. “Universal accumulators with efficient nonmembership proofs”. In: ACNS ’07. 2007.
• [LTYW18] Yongqiang Li, Shizhu Tian, Yuyin Yu, and Mingsheng Wang. “On the generalization of butterfly structure”. In: IACR Transactions on Symmetric Cryptology ’18. 2018.
• [MBKM19] Mary Maller, Sean Bowe, Markulf Kohlweiss, and Sarah Meiklejohn. “Sonic: Zero-knowledge SNARKs from linear-size universal and updateable structured reference strings”. In: CCS ’19. 2019.
• [Man] WASM Z-prize challenge proposal (draft). url: github.com/Manta-Network/wasm-zkp-challenge.
• [Mer87] Ralph C. Merkle. “A digital signature based on a conventional encryption function”. In: CRYPTO ’87. 1987.
• [PBCWC96] Calton Pu, Andrew P. Black, Crispin Cowan, Jonathan Walpole, and Charles Consel. “A specialization toolkit to increase the diversity of operating systems”. In: ICMAS Workshop on Immunity-Based Systems ’96. 1996.
• [PK22] Jim Posen and Assimakis A. Kattis. “Caulk+: Table-independent lookup arguments”. In: IACR ePrint 2022/957. 2022. [page on this site]
• [PST13] Charalampos Papamanthou, Elaine Shi, and Roberto Tamassia. “Signatures of Correct Computation”. In: TCC ’13. 2013.
• [PUB16] Léo Perrin, Aleksei Udovenko, and Alex Biryukov. “Cryptanalysis of a theorem: Decomposing the only known solution to the big APN problem”. In: CRYPTO ’16. 2016.
• [Plo] Plonky2 & more. url: github.com/mir-protocol/plonky2.
• [RRR16] Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. “Constant-round interactive proofs for delegating computation”. In: STOC ’16. 2016.
• [SAGL18] Srinath Setty, Sebastian Angel, Trinabh Gupta, and Jonathan Lee. “Proving the correct execution of concurrent services in zero-knowledge”. In: OSDI ’18. 2018.
• [Sch80] Jack T. Schwartz. “Fast probabilistic algorithms for verification of polynomial identities”. In: JACM ’80. 1980.
• [Set20] Srinath Setty. “Spartan: Efficient and general-purpose zkSNARKs without trusted setup”. In: CRYPTO ’20. 2020. [page on this site]
• [Sin] Sinsemilla. url: zcash.github.io/halo2/design/gadgets/sinsemilla.html.
• [Tur] Proposal: The Turbo-PLONK program syntax for specifying SNARK programs. url: docs.zkproof.org/.../proposal-turbo_plonk.pdf.
• [Wu21] Alexander Wu. “Optimizations and improvements to cryptographic libraries for zkSNARKs”. MA thesis. EECS Department, University of California, Berkeley, 2021.
• [Xie+22] Tiancheng Xie, Jiaheng Zhang, Zerui Cheng, Fan Zhang, Yupeng Zhang, Yongzheng Jia, Dan Boneh, and Dawn Song. “zkBridge: Trustless cross-chain bridges made practical”. In: CCS ’22. 2022.
• [ZBKMNS22] Arantxa Zapico, Vitalik Buterin, Dmitry Khovratovich, Mary Maller, Anca Nitulescu, and Mark Simkin. “Caulk: Lookup arguments in sublinear time”. In: CCS ’22. 2022.
• [Zip79] Richard Zippel. “Probabilistic algorithms for sparse polynomials”. In: EUROSAM ’79. 1979.
• [Zks] zkSync. url: zksync.io.