Article

HyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates

Authors:

Benedikt Bünz,

Zhenfei ZhangAuthors Info & Claims

Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II

Pages 499 - 530

https://doi.org/10.1007/978-3-031-30617-4_17

Published: 23 April 2023 Publication History

Abstract

Plonk is a widely used succinct non-interactive proof system that uses univariate polynomial commitments. Plonk is quite flexible: it supports circuits with low-degree “custom” gates as well as circuits with lookup gates (a lookup gate ensures that its input is contained in a predefined table). For large circuits, the bottleneck in generating a Plonk proof is the need for computing a large FFT.

We present HyperPlonk, an adaptation of Plonk to the boolean hypercube, using multilinear polynomial commitments. HyperPlonk retains the flexibility of Plonk but provides several additional benefits. First, it avoids the need for an FFT during proof generation. Second, and more importantly, it supports custom gates of much higher degree than Plonk without harming the running time of the prover. Both of these can dramatically speed up the prover’s running time. Since HyperPlonk relies on multilinear polynomial commitments, we revisit two elegant constructions: one from Orion and one from Virgo. We show how to reduce the Orion opening proof size to less than 10 KB (an almost factor 1000 improvement) and show how to make the Virgo FRI-based opening proof simpler and shorter (This is an extended abstract. The full version is available on EPRINT[22]).

References

[1]

Aly, A., Ashur, T., Ben-Sasson, E., Dhooghe, S., Szepieniec, A.: Design of symmetric-key primitives for advanced cryptographic protocols. IACR Trans. Symm. Cryptol. 2020(3), 1–45 (2020).

[2]

Aranha, D.F., Bennedsen, E.M., Campanelli, M., Ganesh, C., Orlandi, C., Takahashi, A.: ECLIPSE: enhanced compiling method for pedersen-committed zkSNARK engines. Cryptology ePrint Archive, Report 2021/934 (2021). https://eprint.iacr.org/2021/934

[3]

Arun, A., Ganesh, C., Lokam, S., Mopuri, T., Sridhar, S.: Dew: transparent constant-sized zkSNARKs. Cryptology ePrint Archive, Report 2022/419 (2022). https://eprint.iacr.org/2022/419

[4]

Babai L and Moran S Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes J. Comput. Syst. Sci. 1988 36 2 254-276

[5]

Barbara, M., et al.: Reinforced concrete: fast hash function for zero knowledge proofs and verifiable computation. Cryptology ePrint Archive, Report 2021/1038 (2021). https://eprint.iacr.org/2021/1038

[6]

Bayer S and Groth J Pointcheval D and Johansson T Efficient zero-knowledge argument for correctness of a shuffle Advances in Cryptology – EUROCRYPT 2012 2012 Heidelberg Springer 263-280

[7]

Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-solomon interactive oracle proofs of proximity. In: Chatzigiannakis, I., Kaklamanis, C., Marx, D., Sannella, D. (eds.) ICALP 2018. LIPIcs, vol. 107, pp. 14:1–14:17. Schloss Dagstuhl, July 2018.

[8]

Ben-Sasson E, Bentov I, Horesh Y, and Riabzev M Boldyreva A and Micciancio D Scalable zero knowledge with no trusted setup Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 701-732

[9]

Ben-Sasson, E., Carmon, D., Kopparty, S., Levit, D.: Elliptic curve fast fourier transform (ECFFT) part ii: scalable and transparent proofs over all large fields (2022)

[10]

Ben-Sasson E, Chiesa A, Riabzev M, Spooner N, Virza M, and Ward NP Ishai Y and Rijmen V Aurora: transparent succinct arguments for R1CS Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 103-128

[11]

Ben-Sasson E, Chiesa A, and Spooner N Hirt M and Smith A Interactive oracle proofs Theory of Cryptography 2016 Heidelberg Springer 31-60

[12]

Ben-Sasson E and Sudan M Short pcps with polylog query complexity SIAM J. Comput. 2008 38 2 551-607

[13]

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Goldwasser, S. (ed.) ITCS 2012, pp. 326–349. ACM, January 2012.

[14]

Bitansky N, Chiesa A, Ishai Y, Paneth O, and Ostrovsky R Sahai A Succinct non-interactive arguments via linear interactive proofs Theory of Cryptography 2013 Heidelberg Springer 315-333

[15]

Bootle J, Cerulli A, Ghadafi E, Groth J, Hajiabadi M, and Jakobsen SK Takagi T and Peyrin T Linear-time zero-knowledge proofs for arithmetic circuit satisfiability Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 336-365

[16]

Bootle J, Chiesa A, and Groth J Pass R and Pietrzak K Linear-time arguments with sublinear verification from tensor codes Theory of Cryptography 2020 Cham Springer 19-46

[17]

Bootle, J., Chiesa, A., Hu, Y., Orrù, M.: Gemini: elastic SNARKs for diverse environments. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 427–457. Springer, Heidelberg, May/June 2022.

[18]

Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy, pp. 315–334. IEEE Computer Society Press, May 2018.

[19]

Bünz B, Fisch B, and Szepieniec A Canteaut A and Ishai Y Transparent SNARKs from DARK compilers Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 677-706

[20]

Campanelli M, Faonio A, Fiore D, Querol A, and Rodríguez H Tibouchi M and Wang H Lunar: a toolbox for more efficient universal and updatable zkSNARKs and commit-and-prove extensions Advances in Cryptology – ASIACRYPT 2021 2021 Cham Springer 3-33

[21]

Campanelli, M., Fiore, D., Querol, A.: LegoSNARK: modular design and composition of succinct zero-knowledge proofs. In: Cavallaro, L., Kinder, J., Wang, X., Katz, J. (eds.) ACM CCS 2019, pp. 2075–2092. ACM Press, November 2019.

[22]

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

[23]

Chiesa, A., Forbes, M.A., Spooner, N.: A zero knowledge sumcheck and its applications. Cryptology ePrint Archive, Report 2017/305 (2017). https://eprint.iacr.org/2017/305

[24]

Chiesa A, Hu Y, Maller M, Mishra P, Vesely N, and Ward N Canteaut A and Ishai Y Marlin: preprocessing zkSNARKs with universal and updatable SRS Advances in Cryptology – EUROCRYPT 2020 2020 Cham Springer 738-768

[25]

Drake, J.: Plonk-style SNARKs without FFTs (2019). https://notes.ethereum.org/DLRqK9V7RIOsTZkab8HmQ?view

[26]

Gabizon, A.: Multiset checks in plonk and plookup. https://hackmd.io/@arielg/ByFgSDA7D

[27]

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

[28]

Gabizon, A., Williamson, Z.J.: Proposal: the turbo-plonk program syntax for specifying snark programs (2020). https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-turbo_plonk.pdf

[29]

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

[30]

Gennaro R, Gentry C, Parno B, and Raykova M Johansson T and Nguyen PQ Quadratic span programs and succinct NIZKs without PCPs Advances in Cryptology – EUROCRYPT 2013 2013 Heidelberg Springer 626-645

[31]

Goldwasser S, Micali S, and Rackoff C The knowledge complexity of interactive proof systems SIAM J. Comput. 1989 18 1 186-208

[32]

Golovnev, A., Lee, J., Setty, S., Thaler, J., Wahby, R.S.: Brakedown: linear-time and post-quantum SNARKs for R1CS. Cryptology ePrint Archive, Report 2021/1043 (2021). https://eprint.iacr.org/2021/1043

[33]

Grassi, L., Khovratovich, D., Rechberger, C., Roy, A., Schofnegger, M.: Poseidon: a new hash function for zero-knowledge proof systems. In: Bailey, M., Greenstadt, R. (eds.) USENIX Security 2021, pp. 519–535. USENIX Association, August 2021

[34]

Groth J Fischlin M and Coron J-S On the size of pairing-based non-interactive arguments Advances in Cryptology – EUROCRYPT 2016 2016 Heidelberg Springer 305-326

[35]

Harvey D and Van Der Hoeven J Polynomial multiplication over finite fields in time J. ACM (JACM) 2022 69 2 1-40

[36]

Kate A, Zaverucha GM, and Goldberg I Abe M Constant-size commitments to polynomials and their applications Advances in Cryptology - ASIACRYPT 2010 2010 Heidelberg Springer 177-194

[37]

Kattis, A.A., Panarin, K., Vlasov, A.: RedShift: transparent SNARKs from list polynomial commitments. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022, pp. 1725–1737. ACM Press, November 2022.

[38]

Lee J Nissim K and Waters B Dory: efficient, transparent arguments for generalised inner products and polynomial commitments Theory of Cryptography 2021 Cham Springer 1-34

[39]

Lund C, Fortnow L, Karloff H, and Nisan N Algebraic methods for interactive proof systems J. ACM (JACM) 1992 39 4 859-868

[40]

Papamanthou C, Shi E, and Tamassia R Sahai A Signatures of correct computation Theory of Cryptography 2013 Heidelberg Springer 222-242

[41]

Pearson, L., Fitzgerald, J., Masip, H., Bellés-Muñoz, M., Muñoz-Tapia, J.L.: PlonKup: reconciling PlonK with plookup. Cryptology ePrint Archive, Report 2022/086 (2022). https://eprint.iacr.org/2022/086

[42]

Posen, J., Kattis, A.A.: Caulk+: table-independent lookup arguments. Cryptology ePrint Archive, Report 2022/957 (2022). https://eprint.iacr.org/2022/957

[43]

Setty S Micciancio D and Ristenpart T Spartan: efficient and general-purpose zkSNARKs without trusted setup Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 704-737

[44]

Setty, S., Lee, J.: Quarks: quadruple-efficient transparent zkSNARKs. Cryptology ePrint Archive, Report 2020/1275 (2020). https://eprint.iacr.org/2020/1275

[45]

System, E.: Jellyfish jellyfish cryptographic library (2022). https://github.com/EspressoSystems/jellyfish

[46]

Thaler J Canetti R and Garay JA Time-optimal interactive proofs for circuit evaluation Advances in Cryptology – CRYPTO 2013 2013 Heidelberg Springer 71-89

[47]

Thaler, J.: Proofs, arguments, and zero-knowledge (2020)

[48]

Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup. In: 2018 IEEE Symposium on Security and Privacy, pp. 926–943. IEEE Computer Society Press, May 2018.

[49]

Xie T, Zhang J, Zhang Y, Papamanthou C, and Song D Boldyreva A and Micciancio D Libra: succinct zero-knowledge proofs with optimal prover computation Advances in Cryptology – CRYPTO 2019 2019 Cham Springer 733-764

[50]

Xie, T., Zhang, Y., Song, D.: Orion: zero knowledge proof with linear prover time. Cryptology ePrint Archive, Report 2022/1010 (2022). https://eprint.iacr.org/2022/1010

[51]

Xie, T., Zhang, Y., Song, D.: Orion: zero knowledge proof with linear prover time. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part IV. LNCS, vol. 13510, pp. 299–328. Springer, Heidelberg, August 2022.

[52]

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

[53]

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, November 2022.

[54]

Zcash: PLONKish arithmetization. https://zcash.github.io/halo2/concepts/arithmetization.html (2022)

[55]

Zhang, J., Xie, T., Zhang, Y., Song, D.: Transparent polynomial delegation and its applications to zero knowledge proof. In: 2020 IEEE Symposium on Security and Privacy, pp. 859–876. IEEE Computer Society Press, May 2020.

Cited By

Lu TChen YWang ZWang XChen WZhang JEeckhout LSmaragdakis GLiang KSampson AKim MRossbach C(2025)BatchZK: A Fully Pipelined GPU-Accelerated System for Batch Generation of Zero-Knowledge ProofsProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3669940.3707270(100-115)Online publication date: 3-Feb-2025
https://dl.acm.org/doi/10.1145/3669940.3707270
Faonio AFiore DRusso LLuo BLiao XXu JKirda ELie D(2024)Real-World Universal zkSNARKs are Non-MalleableProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690351(3138-3151)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690351
Sun HLi JZhang HLuo BLiao XXu JKirda ELie D(2024)zkLLM: Zero Knowledge Proofs for Large Language ModelsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670334(4405-4419)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670334
Show More Cited By

Recommendations

Constructive linear-time temporal logic: Proof systems and Kripke semantics

In this paper we study a version of constructive linear-time temporal logic (LTL) with the ''next'' temporal operator. The logic is originally due to Davies, who has shown that the proof system of the logic corresponds to a type system for binding-time ...
A Paraconsistent Linear-time Temporal Logic

Inconsistency-tolerant reasoning and paraconsistent logic are of growing importance not only in Knowledge Representation, AI and other areas of Computer Science, but also in Philosophical Logic. In this paper, a new logic, paraconsistent linear-time ...
Extending a High-Performance Prover to Higher-Order Logic
Tools and Algorithms for the Construction and Analysis of Systems
Abstract
Most users of proof assistants want more proof automation. Some proof assistants discharge goals by translating them to first-order logic and invoking an efficient prover on them, but much is lost in translation. Instead, we propose to extend ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II

Apr 2023

640 pages

ISBN:978-3-031-30616-7

DOI:10.1007/978-3-031-30617-4

Editors:
Carmit Hazay
Bar-Ilan University, Ramat Gan, Israel
,
Martijn Stam
Simula UiB, Bergen, Norway

© International Association for Cryptologic Research 2023.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 23 April 2023

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

26
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Lu TChen YWang ZWang XChen WZhang JEeckhout LSmaragdakis GLiang KSampson AKim MRossbach C(2025)BatchZK: A Fully Pipelined GPU-Accelerated System for Batch Generation of Zero-Knowledge ProofsProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 110.1145/3669940.3707270(100-115)Online publication date: 3-Feb-2025
https://dl.acm.org/doi/10.1145/3669940.3707270
Faonio AFiore DRusso LLuo BLiao XXu JKirda ELie D(2024)Real-World Universal zkSNARKs are Non-MalleableProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3690351(3138-3151)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3690351
Sun HLi JZhang HLuo BLiao XXu JKirda ELie D(2024)zkLLM: Zero Knowledge Proofs for Large Language ModelsProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670334(4405-4419)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670334
Gao RWan ZHu YWang HLuo BLiao XXu JKirda ELie D(2024)A Succinct Range Proof for Polynomial-based Vector CommitmentProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670324(3152-3166)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670324
Abbaszadeh KPappas CKatz JPapadopoulos DLuo BLiao XXu JKirda ELie D(2024)Zero-Knowledge Proofs of Training for Deep Neural NetworksProceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security10.1145/3658644.3670316(4316-4330)Online publication date: 2-Dec-2024
https://dl.acm.org/doi/10.1145/3658644.3670316
Cong MYuen TYiu SQuek TGao DZhou JCardenas A(2024)zkMatrix: Batched Short Proof for Committed Matrix MultiplicationProceedings of the 19th ACM Asia Conference on Computer and Communications Security10.1145/3634737.3645003(289-305)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.1145/3634737.3645003
Bui DChu HCouteau GWang XWeng CYang KYu Y(2024)An Efficient ZK Compiler from SIMD Circuits to General CircuitsJournal of Cryptology10.1007/s00145-024-09531-438:1Online publication date: 5-Dec-2024
https://dl.acm.org/doi/10.1007/s00145-024-09531-4
Kohrita TTowa P(2024)Zeromorph: Zero-Knowledge Multilinear-Evaluation Proofs from Homomorphic Univariate CommitmentsJournal of Cryptology10.1007/s00145-024-09519-037:4Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1007/s00145-024-09519-0
Xie JHu YYu Y(2024)Hadamard Product Argument from Lagrange-Based Univariate PolynomialsInformation Security and Privacy10.1007/978-981-97-5025-2_24(472-492)Online publication date: 15-Jul-2024
https://dl.acm.org/doi/10.1007/978-981-97-5025-2_24
Fleischhacker NHall-Andersen MSimkin MWagner B(2024)Jackpot: Non-interactive Aggregatable LotteriesAdvances in Cryptology – ASIACRYPT 202410.1007/978-981-96-0938-3_12(365-397)Online publication date: 10-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-0938-3_12
Show More Cited By

View Options

View options

Figures

Tables

Media

View Table of Conten