Welcome to the resource topic for 2023/620
Title:
ProtoStar: Generic Efficient Accumulation/Folding for Special Sound Protocols
Authors: Benedikt Bünz, Binyi Chen
Abstract: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+d-1 elliptic curve multiplications and k+1 field operations. Alternatively the accumulation verifier performs just k EC multiplications at the cost of O(\log\ell) additional hashes. 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 the lesser of either d^*+1 group scalar multiplications or \log(n)+2 hashes, where d^* is the degree of the highest gate and n is the number of gates in a supported circuit. 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.
ePrint: https://eprint.iacr.org/2023/620
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .