Paper 2023/620

ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols

Benedikt Bünz, Espresso Systems
Binyi Chen, Espresso Systems

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 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 $d^*$ field elements, where $d^*$ 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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
incremental verifiable computationaccumulation schemesrecursive proof compositionproof-carrying data
Contact author(s)
benedikt @ espressosys com
binyi @ espressosys com
2023-12-21: last of 12 revisions
2023-05-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benedikt Bünz and Binyi Chen},
      title = {ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2023/620},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.