SubLogarithmic Linear Time SNARKs from Improved Sum-Check

본문 미리보기

We present $\mathsf{HybridSpartan}$ and $\mathsf{HybridPlonk}$ -- the first SNARKs that simultaneously achieve linear-time prover, sublogarithmic proof size, logarithmic verifier, and also feature updatable setups. Our constructions are provably secure in the Random Oracle Model (ROM) and the Algebraic Group Model (AGM). As a core technical contribution (possibly of independent interest), we reduce the communication complexity of the classical sumcheck protocol for multivariate polynomials from