Protostar: generic efficient accumulation/folding for special-sound protocols. (English) Zbl 1543.94711
Guo, Jian (ed.) et al., Advances in cryptology – ASIACRYPT 2023. 29th international conference on the theory and application of cryptology and information security, Guangzhou, China, December 4–8, 2023. Proceedings. Part II. Singapore: Springer. Lect. Notes Comput. Sci. 14439, 77-110 (2023).
Summary: Accumulation is a simple yet powerful primitive that enables incrementally verifiable computation (IVC) without the need for recursive SNARKs. We provide a generic, efficient accumulation (or folding) scheme for any \((2k-1)\)-move special-sound protocol with a verifier that checks \(\ell\) degree-\(d\) equations. The accumulation verifier only performs \(k+2\) elliptic curve multiplications and \(k+d+O(1)\) field/hash operations. Using the compiler from [B. Bünz et al., Lect. Notes Comput. Sci. 12825, 681–710 (2021; Zbl 1485.94066)], this enables building efficient IVC schemes where the recursive circuit only depends on the number of rounds and the verifier degree of the underlying special-sound protocol but not the proof size or the verifier time. We use our generic accumulation compiler to build Protostar. Protostar is a non-uniform IVC scheme for Plonk that supports high-degree gates and (vector) lookups. The recursive circuit is dominated by 3 group scalar multiplications and a hash of \(d^\ast\) field elements, where \(d^\ast\) is the degree of the highest gate. The scheme does not require a trusted setup or pairings, and the prover does not need to compute any FFTs. The prover in each accumulation/IVC step is also only logarithmic in the number of supported circuits and independent of the table size in the lookup.
For the entire collection see [Zbl 1540.94003].
For the entire collection see [Zbl 1540.94003].
Citations:
Zbl 1485.94066References:
| [1] | Attema, T.; Fehr, S.; Klooß, M.; Kiltz, E.; Vaikuntanathan, V., Fiat-Shamir transformation of multi-round interactive proofs, Theory of Cryptography, 113-142, 2022, Cham: Springer, Cham · Zbl 1519.94039 · doi:10.1007/978-3-031-22318-1_5 |
| [2] | 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 |
| [3] | Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: Recursive composition and bootstrapping for SNARKS and proof-carrying data. In: Boneh, D., Roughgarden, T., Feigenbaum, J. (eds.) 45th ACM STOC, pp. 111-120. ACM Press (2013). doi:10.1145/2488608.2488623 · Zbl 1293.68264 |
| [4] | Boneh, D.; Bonneau, J.; Bünz, B.; Fisch, B.; Shacham, H.; Boldyreva, A., Verifiable delay functions, Advances in Cryptology - CRYPTO 2018, 757-788, 2018, Cham: Springer, Cham · Zbl 1444.94046 · doi:10.1007/978-3-319-96884-1_25 |
| [5] | Bonneau, J., Meckler, I., Rao, V., Shapiro, E.: Coda: decentralized cryptocurrency at scale. Cryptology ePrint Archive, Report 2020/352 (2020). https://eprint.iacr.org/2020/352 |
| [6] | Bowe, S., Grigg, J., Hopwood, D.: Halo: recursive proof composition without a trusted setup. Cryptology ePrint Archive, Report 2019/1021 (2019). https://eprint.iacr.org/2019/1021 |
| [7] | Bünz, B., Chen, B.: Protostar: generic efficient accumulation/folding for special sound protocols. In: Cryptology ePrint Archive (2023) · Zbl 1543.94711 |
| [8] | Bünz, B.; Chiesa, A.; Lin, W.; Mishra, P.; Spooner, N.; Malkin, T.; Peikert, C., Proof-carrying data without succinct arguments, Advances in Cryptology - CRYPTO 2021, 681-710, 2021, Cham: Springer, Cham · Zbl 1485.94066 · doi:10.1007/978-3-030-84242-0_24 |
| [9] | Bünz, B.; Chiesa, A.; Mishra, P.; Spooner, N.; Pass, R.; Pietrzak, K., Recursive proof composition from accumulation schemes, Theory of Cryptography, 1-18, 2020, Cham: Springer, Cham · Zbl 1485.94132 · doi:10.1007/978-3-030-64378-2_1 |
| [10] | Buterin, V.: The different types of ZK EVM (2022). https://vitalik.ca/general/2022/08/04/zkevm.html. Accessed 27 Apr 2023 |
| [11] | Chen, B., Bünz, B., Boneh, D., Zhang, Z.: HyperPlonk: plonk with linear-time prover and high-degree custom gates. Cryptology ePrint Archive, Report 2022/1355 (2022). https://eprint.iacr.org/2022/1355 |
| [12] | Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Chi-Chih, A. (ed.) ICS 2010, pp. 310-331. Yao, Tsinghua University Press (2010) |
| [13] | Chiesa, A.; Tromer, E.; Virza, M.; Oswald, E.; Fischlin, M., Cluster computing in zero knowledge, Advances in Cryptology - EUROCRYPT 2015, 371-403, 2015, Heidelberg: Springer, Heidelberg · Zbl 1371.68257 · doi:10.1007/978-3-662-46803-6_13 |
| [14] | Eagen, L., Fiore, D., Gabizon, A.: cq: cached quotients for fast lookups. Cryptology ePrint Archive, Report 2022/1763 (2022). https://eprint.iacr.org/2022/1763 |
| [15] | Gabizon, A., Williamson, Z.J.: plookup: a simplified polynomial protocol for lookup tables. Cryptology ePrint Archive, Report 2020/315 (2020). https://eprint.iacr.org/2020/315 |
| [16] | Gabizon, A., Williamson, Z.J., Ciobotaru, O.: PLONK: permutations over lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive, Report 2019/953 (2019). https://eprint.iacr.org/2019/953 |
| [17] | Haböck, U.: Multivariate lookups based on logarithmic derivatives. Cryptology ePrint Archive, Report 2022/1530 (2022). https://eprint.iacr.org/2022/1530 |
| [18] | Kattis, A., Bonneau, J.: Proof of necessary work: succinct state verification with fairness guarantees. Cryptology ePrint Archive, Report 2020/190 (2020). https://eprint.iacr.org/2020/190 |
| [19] | Khovratovich, D., Maller, M., Tiwari, P.R.: MinRoot: candidate sequential function for ethereum VDF. Cryptology ePrint Archive, Report 2022/1626 (2022). https://eprint.iacr.org/2022/1626 |
| [20] | Kothapalli, A., Setty, S.: HyperNova: recursive arguments for customizable constraint systems. In: Cryptology ePrint Archive (2023) |
| [21] | Kothapalli, A., Setty, S.: SuperNova: proving universal machine executions without universal circuits. Cryptology ePrint Archive, Report 2022/1758 (2022). https://eprint.iacr.org/2022/1758 |
| [22] | Kothapalli, A.; Setty, S.; Tzialla, I.; Dodis, Y.; Shrimpton, T., Nova: recursive zero-knowledge arguments from folding schemes, Advances in Cryptology - CRYPTO 2022, 359-388, 2022, Cham: Springer, Cham · Zbl 1517.94119 · doi:10.1007/978-3-031-15985-5_13 |
| [23] | Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. In: 31st FOCS, pp. 2-10. IEEE Computer Society Press (1990). doi:10.1109/FSCS.1990.89518 |
| [24] | Mohnblatt, N.: Sangria: a folding scheme for PLONK (2023). https://github.com/geometryresearch/technical_notes/blob/main/sangria_folding_plonk.pdf. Accessed 27 Apr 2023 |
| [25] | Naveh, A., Tromer, E.: PhotoProof: cryptographic image authentication for any set of permissible transformations. In: 2016 IEEE Symposium on Security and Privacy, pp. 255-271. IEEE Computer Society Press (2016). doi:10.1109/SP.2016.23 |
| [26] | Pedersen, TP; Feigenbaum, J., Non-interactive and information-theoretic secure verifiable secret sharing, Advances in Cryptology — CRYPTO ’91, 129-140, 1992, Heidelberg: Springer, Heidelberg · Zbl 0763.94015 · doi:10.1007/3-540-46766-1_9 |
| [27] | Posen, J., Kattis, A.A.: Caulk+: table-independent lookup arguments. Cryptology ePrint Archive, Report 2022/957 (2022). https://eprint.iacr.org/2022/957 |
| [28] | Setty, S., Angel, S., Gupta, T., Lee, J.: Proving the correct execution of concurrent services in zero-knowledge. In: 13th USENIX Symposium on Operating Systems Design and Implementation (OSDI 2018), pp. 339-356 (2018) |
| [29] | Setty, S., Thaler, J., Wahby, R.: Customizable constraint systems for succinct arguments. Cryptology ePrint Archive (2023) |
| [30] | Valiant, P.; Canetti, R., Incrementally verifiable computation or proofs of knowledge imply time/space efficiency, Theory of Cryptography, 1-18, 2008, Heidelberg: Springer, Heidelberg · Zbl 1162.68448 · doi:10.1007/978-3-540-78524-8_1 |
| [31] | Wikström, D.: Special soundness in the random oracle model. Cryptology ePrint Archive, Report 2021/1265 (2021). https://eprint.iacr.org/2021/1265 |
| [32] | Xiong, A.L., et al.: VERI-ZEXE: decentralized private computation with universal setup. Cryptology ePrint Archive, Report 2022/802 (2022). https://eprint.iacr.org/2022/802 |
| [33] | Zapico, A., Buterin, V., Khovratovich, D., Maller, M., Nitulescu, A., Simkin, M.: Caulk: lookup arguments in sublinear time. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022, pp. 3121-3134. ACM Press (2022). doi:10.1145/3548606.3560646 |
| [34] | Zapico, A., Gabizon, A., Khovratovich, D., Maller, M., Ràfols, C.: Baloo: nearly optimal lookup arguments. Cryptology ePrint Archive, Report 2022/1565 (2022). https://eprint.iacr.org/2022/1565 |
| [35] | Zhang, Y.X., Vark, A.: Origami - a folding scheme for Halo2 lookups (2023). https://hackmd.io/@aardvark/rkHqa3NZ2. Accessed 12 July 2023 |
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.
