Marlin: preprocessing zkSNARKs with universal and updatable SRS. (English) Zbl 1541.94048
Canteaut, Anne (ed.) et al., Advances in cryptology – EUROCRYPT 2020. 39th annual international conference on the theory and applications of cryptographic techniques, Zagreb, Croatia, May 10–14, 2020. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 12105, 738-768 (2020).
Summary: We present a methodology to construct preprocessing zkSNARKs where the structured reference string (SRS) is universal and updatable. This exploits a novel use of holography, where fast verification is achieved provided the statement being checked is given in encoded form.
We use our methodology to obtain a preprocessing zkSNARK where the SRS has linear size and arguments have constant size. Our construction improves on Sonic [M. Maller et al., CCS 2019, 2111–2128 (2019; doi:10.1145/3319535.3339817], the prior state of the art in this setting, in all efficiency parameters: proving is an order of magnitude faster and verification is thrice as fast, even with smaller SRS size and argument size. Our construction is most efficient when instantiated in the algebraic group model (also used by Sonic), but we also demonstrate how to realize it under concrete knowledge assumptions. We implement and evaluate our construction.
The core of our preprocessing zkSNARK is an efficient algebraic holographic proof (AHP) for rank-1 constraint satisfiability (R1CS) that achieves linear proof length and constant query complexity.
For the entire collection see [Zbl 1475.94008].
We use our methodology to obtain a preprocessing zkSNARK where the SRS has linear size and arguments have constant size. Our construction improves on Sonic [M. Maller et al., CCS 2019, 2111–2128 (2019; doi:10.1145/3319535.3339817], the prior state of the art in this setting, in all efficiency parameters: proving is an order of magnitude faster and verification is thrice as fast, even with smaller SRS size and argument size. Our construction is most efficient when instantiated in the algebraic group model (also used by Sonic), but we also demonstrate how to realize it under concrete knowledge assumptions. We implement and evaluate our construction.
The core of our preprocessing zkSNARK is an efficient algebraic holographic proof (AHP) for rank-1 constraint satisfiability (R1CS) that achieves linear proof length and constant query complexity.
For the entire collection see [Zbl 1475.94008].
MSC:
| 94A60 | Cryptography |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
Software:
MarlinReferences:
| [1] | Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: CCS 2017 (2017) |
| [2] | Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC 1991 (1991) |
| [3] | Ben-Sasson, E.; Chiesa, A.; Spooner, N.; Hirt, M.; Smith, A., Interactive oracle proofs, Theory of Cryptography, 31-60 (2016), Heidelberg: Springer, Heidelberg · Zbl 1397.94048 · doi:10.1007/978-3-662-53644-5_2 |
| [4] | Bayer, S.; Groth, J.; Pointcheval, D.; Johansson, T., Efficient zero-knowledge argument for correctness of a shuffle, Advances in Cryptology - EUROCRYPT 2012, 263-280 (2012), Heidelberg: Springer, Heidelberg · Zbl 1297.94045 · doi:10.1007/978-3-642-29011-4_17 |
| [5] | Bowe, S., Gabizon, A., Green, M.: A multi-party protocol for constructing the public parameters of the Pinocchio zk-SNARK. ePrint Report 2017/602 (2017) |
| [6] | Bowe, S., Gabizon, A., Miers, I.: Scalable multi-party computation for zk-SNARK parameters in the random Beacon model. ePrint Report 2017/1050 (2017) |
| [7] | Bitansky, N.; Chiesa, A.; Ishai, Y.; Paneth, O.; Ostrovsky, R.; Sahai, A., Succinct non-interactive arguments via linear interactive proofs, Theory of Cryptography, 315-333 (2013), Heidelberg: Springer, Heidelberg · Zbl 1316.68056 · doi:10.1007/978-3-642-36594-2_18 |
| [8] | Boneh, D.; Ishai, Y.; Sahai, A.; Wu, DJ; Coron, J-S; Nielsen, JB, Lattice-based SNARGs and their application to more efficient obfuscation, Advances in Cryptology - EUROCRYPT 2017, 247-277 (2017), Cham: Springer, Cham · Zbl 1415.94412 · doi:10.1007/978-3-319-56617-7_9 |
| [9] | Boneh, D.; Ishai, Y.; Sahai, A.; Wu, DJ; Nielsen, JB; Rijmen, V., Quasi-optimal SNARGs via linear multi-prover interactive proofs, Advances in Cryptology - EUROCRYPT 2018, 222-255 (2018), Cham: Springer, Cham · Zbl 1415.94413 · doi:10.1007/978-3-319-78372-7_8 |
| [10] | Bootle, J.; Cerulli, A.; Chaidos, P.; Groth, J.; Petit, C.; Fischlin, M.; Coron, J-S, Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting, Advances in Cryptology - EUROCRYPT 2016, 327-357 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94520 · doi:10.1007/978-3-662-49896-5_12 |
| [11] | Ben-Sasson, E.; Sudan, M., Short PCPs with polylog query complexity, SIAM J. Comput., 38, 2, 551-607 (2008) · Zbl 1172.68025 · doi:10.1137/050646445 |
| [12] | Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: S&P 2018 (2018) |
| [13] | Cramer, R.; Damgård, I.; Krawczyk, H., Zero-knowledge proofs for finite field arithmetic, or: can zero-knowledge be for free?, Advances in Cryptology — CRYPTO 1998, 424-441 (1998), Heidelberg: Springer, Heidelberg · Zbl 0964.94019 · doi:10.1007/BFb0055745 |
| [14] | Chiesa, A., Forbes, M.A., Spooner, N.: A zero knowledge sumcheck and its applications. ePrint Report 2017/305 (2017) |
| [15] | Fuchsbauer, G.; Kiltz, E.; Loss, J.; Shacham, H.; Boldyreva, A., The algebraic group model and its applications, Advances in Cryptology - CRYPTO 2018, 33-62 (2018), Cham: Springer, Cham · Zbl 1430.94068 · doi:10.1007/978-3-319-96881-0_2 |
| [16] | Fiat, A.; Shamir, A.; Odlyzko, AM, How to prove yourself: practical solutions to identification and signature problems, Advances in Cryptology — CRYPTO 1986, 186-194 (1987), Heidelberg: Springer, Heidelberg · Zbl 0636.94012 · doi:10.1007/3-540-47721-7_12 |
| [17] | Gabizon, A.: Improved prover efficiency and SRS size in a Sonic-like system. ePrint Report 2019/601 (2019) |
| [18] | Gennaro, R.; Gentry, C.; Parno, B.; Raykova, M.; Johansson, T.; Nguyen, PQ, Quadratic span programs and succinct NIZKs without PCPs, Advances in Cryptology - EUROCRYPT 2013, 626-645 (2013), Heidelberg: Springer, Heidelberg · Zbl 1300.94056 · doi:10.1007/978-3-642-38348-9_37 |
| [19] | Goldwasser, S.; Kalai, YT; Rothblum, GN, Delegating computation: interactive proofs for muggles, JACM, 62, 4, 1-64 (2015) · Zbl 1393.68071 · doi:10.1145/2699436 |
| [20] | Groth, J.; Kohlweiss, M.; Maller, M.; Meiklejohn, S.; Miers, I.; Shacham, H.; Boldyreva, A., Updatable and universal common reference strings with applications to zk-SNARKs, Advances in Cryptology - CRYPTO 2018, 698-728 (2018), Cham: Springer, Cham · Zbl 1457.94137 · doi:10.1007/978-3-319-96878-0_24 |
| [21] | Groth, J.; Abe, M., Short pairing-based non-interactive zero-knowledge arguments, Advances in Cryptology - ASIACRYPT 2010, 321-340 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94049 · doi:10.1007/978-3-642-17373-8_19 |
| [22] | Groth, J.; Fischlin, M.; Coron, J-S, On the size of pairing-based non-interactive arguments, Advances in Cryptology - EUROCRYPT 2016, 305-326 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94539 · doi:10.1007/978-3-662-49896-5_11 |
| [23] | Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. ePrint Report 2019/953 (2019) |
| [24] | Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC 1992 (1992) |
| [25] | Kate, A.; Zaverucha, GM; Goldberg, I.; Abe, M., Constant-size commitments to polynomials and their applications, Advances in Cryptology - ASIACRYPT 2010, 177-194 (2010), Heidelberg: Springer, Heidelberg · Zbl 1253.94054 · doi:10.1007/978-3-642-17373-8_11 |
| [26] | Lipmaa, H.; Cramer, R., Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments, Theory of Cryptography, 169-189 (2012), Heidelberg: Springer, Heidelberg · Zbl 1303.94090 · doi:10.1007/978-3-642-28914-9_10 |
| [27] | Maller, M., Bowe, S., Kohlweiss, M., Meiklejohn, S.: Sonic: zero-knowledge SNARKs from linear-size universal and updateable structured reference strings. In: CCS 2019 (2019) |
| [28] | Papamanthou, C.; Shi, E.; Tamassia, R.; Sahai, A., Signatures of correct computation, Theory of Cryptography, 222-242 (2013), Heidelberg: Springer, Heidelberg · Zbl 1315.94098 · doi:10.1007/978-3-642-36594-2_13 |
| [29] | Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: STOC 2016 (2016) · Zbl 1373.68274 |
| [30] | Setty, S.: Spartan: efficient and general-purpose zkSNARKs without trusted setup. ePrint Report 2019/550 (2019) · Zbl 1504.94185 |
| [31] | Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: S&P 2018 (2018) |
| [32] | Xie, T.; Zhang, J.; Zhang, Y.; Papamanthou, C.; Song, D.; Boldyreva, A.; Micciancio, D., Libra: succinct zero-knowledge proofs with optimal prover computation, Advances in Cryptology - CRYPTO 2019, 733-764 (2019), Cham: Springer, Cham · Zbl 1509.94140 · doi:10.1007/978-3-030-26954-8_24 |
| [33] | Zcash. https://z.cash/ |
| [34] | The Zcash Ceremony. https://z.cash/blog/the-design-of-the-ceremony.html |
| [35] | Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: A zero-knowledge version of vSQL. ePrint Report 2017/1146 (2017) |
| [36] | Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vSQL: verifying arbitrary SQL queries over dynamic outsourced databases. In: S&P 2017 (2017) |
| [37] | Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vRAM: faster verifiable RAM with program-independent preprocessing. In: S&P 2018 (2018) |
| [38] | Ben-Sasson, E.; Chiesa, A.; Tromer, E.; Virza, M.; Garay, JA; Gennaro, R., Scalable zero knowledge via cycles of elliptic curves, Advances in Cryptology - CRYPTO 2014, 276-294 (2014), Heidelberg: Springer, Heidelberg · Zbl 1334.68077 · doi:10.1007/978-3-662-44381-1_16 |
| [39] | Ben-Sasson, E., Chiesa, A., Tromer, E., Virza, M.: Succinct non-interactive zero knowledge for a von Neumann architecture. In: USENIX Security 2014 (2014) · Zbl 1334.68077 |
| [40] | Ben-Sasson, E., Chiesa, A., Green, M., Tromer, E., Virza, M.: Secure sampling of public parameters for succinct zero knowledge proofs. In: S&P 2015 (2015) |
| [41] | Ben-Sasson, E.; Chiesa, A.; Gabizon, A.; Virza, M.; Kushilevitz, E.; Malkin, T., Quasi-linear size zero knowledge from linear-algebraic PCPs, Theory of Cryptography, 33-64 (2016), Heidelberg: Springer, Heidelberg · Zbl 1375.94101 · doi:10.1007/978-3-662-49099-0_2 |
| [42] | Ben-Sasson, E.; Coron, J-S; Nielsen, JB, Computational integrity with a public random string from quasi-linear PCPs, Advances in Cryptology - EUROCRYPT 2017, 551-579 (2017), Cham: Springer, Cham · Zbl 1415.94409 · doi:10.1007/978-3-319-56617-7_19 |
| [43] | Ben-Sasson, E.; Chiesa, A.; Riabzev, M.; Spooner, N.; Virza, M.; Ward, NP; Ishai, Y.; Rijmen, V., Aurora: transparent succinct arguments for R1CS, Advances in Cryptology - EUROCRYPT 2019, 103-128 (2019), Cham: Springer, Cham · Zbl 1470.94079 · doi:10.1007/978-3-030-17653-2_4 |
| [44] | Ben-Sasson, E.; Chiesa, A.; Goldberg, L.; Gur, T.; Riabzev, M.; Spooner, N.; Hofheinz, D.; Rosen, A., Linear-size constant-query IOPs for delegating computation, Theory of Cryptography, 494-521 (2019), Cham: Springer, Cham · Zbl 1455.94123 · doi:10.1007/978-3-030-36033-7_19 |
| [45] | Ben-Sasson, E.; Bentov, I.; Horesh, Y.; Riabzev, M.; Boldyreva, A.; Micciancio, D., Scalable zero knowledge with no trusted setup, Advances in Cryptology - CRYPTO 2019, 701-732 (2019), Cham: Springer, Cham · Zbl 1509.94063 · doi:10.1007/978-3-030-26954-8_23 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
