Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols

Benedikt Bünz; Binyi Chen

doi:10.1007/978-981-99-8724-5_3

Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols

Benedikt Bünz, Binyi Chen

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 -move special-sound protocol with a verifier that checks degree-d equations. The accumulation verifier only performs elliptic curve multiplications and field/hash operations. Using the compiler from BCLMS21 (Crypto 21), 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 field elements, where 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.

Original language	English (US)
Title of host publication	Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Jian Guo, Ron Steinfeld
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	77-110
Number of pages	34
ISBN (Print)	9789819987238
DOIs	https://doi.org/10.1007/978-981-99-8724-5_3
State	Published - 2023
Event	29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023 - Guangzhou, China Duration: Dec 4 2023 → Dec 8 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14439 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023
Country/Territory	China
City	Guangzhou
Period	12/4/23 → 12/8/23

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-981-99-8724-5_3

Cite this

Bünz, B., & Chen, B. (2023). Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols. In J. Guo, & R. Steinfeld (Eds.), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 77-110). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14439 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-981-99-8724-5_3

Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols. / Bünz, Benedikt; Chen, Binyi.
Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Jian Guo; Ron Steinfeld. Springer Science and Business Media Deutschland GmbH, 2023. p. 77-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14439 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bünz, B & Chen, B 2023, Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols. in J Guo & R Steinfeld (eds), Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14439 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 77-110, 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023, Guangzhou, China, 12/4/23. https://doi.org/10.1007/978-981-99-8724-5_3

Bünz B, Chen B. Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols. In Guo J, Steinfeld R, editors, Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Springer Science and Business Media Deutschland GmbH. 2023. p. 77-110. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-981-99-8724-5_3

Bünz, Benedikt ; Chen, Binyi. / Protostar : Generic Efficient Accumulation/Folding for Special-Sound Protocols. Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Jian Guo ; Ron Steinfeld. Springer Science and Business Media Deutschland GmbH, 2023. pp. 77-110 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{fd9e1d3fef2548e8bee5d7b06a199891,

title = "Protostar: Generic Efficient Accumulation/Folding for Special-Sound Protocols",

abstract = "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 -move special-sound protocol with a verifier that checks degree-d equations. The accumulation verifier only performs elliptic curve multiplications and field/hash operations. Using the compiler from BCLMS21 (Crypto 21), 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 field elements, where 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.",

author = "Benedikt B{\"u}nz and Binyi Chen",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023 ; Conference date: 04-12-2023 Through 08-12-2023",

year = "2023",

doi = "10.1007/978-981-99-8724-5_3",

language = "English (US)",

isbn = "9789819987238",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "77--110",

editor = "Jian Guo and Ron Steinfeld",

booktitle = "Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Protostar

T2 - 29th Annual International Conference on the Theory and Application of Cryptology and Information Security, Asiacrypt 2023

AU - Bünz, Benedikt

AU - Chen, Binyi

PY - 2023

Y1 - 2023

N2 - 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 -move special-sound protocol with a verifier that checks degree-d equations. The accumulation verifier only performs elliptic curve multiplications and field/hash operations. Using the compiler from BCLMS21 (Crypto 21), 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 field elements, where 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.

AB - 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 -move special-sound protocol with a verifier that checks degree-d equations. The accumulation verifier only performs elliptic curve multiplications and field/hash operations. Using the compiler from BCLMS21 (Crypto 21), 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 field elements, where 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.

UR - http://www.scopus.com/inward/record.url?scp=85180736478&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85180736478&partnerID=8YFLogxK

U2 - 10.1007/978-981-99-8724-5_3

DO - 10.1007/978-981-99-8724-5_3

M3 - Conference contribution

AN - SCOPUS:85180736478

SN - 9789819987238

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 77

EP - 110

BT - Advances in Cryptology – ASIACRYPT 2023 - 29th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Guo, Jian

A2 - Steinfeld, Ron

PB - Springer Science and Business Media Deutschland GmbH

Y2 - 4 December 2023 through 8 December 2023

ER -