ProtoGalaxy:  Efficient ProtoStar-style folding of multiple instances

Liam Eagen; Ariel Gabizon

Paper 2023/1106

ProtoGalaxy: Efficient ProtoStar-style folding of multiple instances

Liam Eagen, Blockstream Research, Zeta Function Technologies

Ariel Gabizon, Zeta Function Technologies

Abstract

We continue the recent line of work on folding schemes. Building on ideas from ProtoStar [BC23] we construct a folding scheme where the recursive verifier's ``marginal work'', beyond linearly combining witness commitments, consists only of a logarithmic number of field operations and a constant number of hashes. Moreover, our folding scheme performs well when \emph{folding multiple instances at one step}, in which case the marginal number of verifier field operations per instance becomes constant, assuming constant degree gates.

Note: indexing typo

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: SNARKs Folding Schemes
Contact author(s): liameagen @ protonmail com
ariel gabizon @ gmail com
History: 2024-01-30: last of 13 revisions; 2023-07-15: received; See all versions
Short URL: https://ia.cr/2023/1106
License: CC0

BibTeX

@misc{cryptoeprint:2023/1106,
      author = {Liam Eagen and Ariel Gabizon},
      title = {{ProtoGalaxy}:  Efficient {ProtoStar}-style folding of multiple instances},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1106},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1106}
}