Accumulation schemes are powerful primitives that enable distributed and incremental verifiable computation with less overhead than recursive SNARKs. However, existing schemes with constant-size accumulation verifiers, suffer from linear-sized accumulators and deciders, leading to linear-sized proofs that are unsuitable in distributed settings. Motivated by the need for bandwidth efficient accountable voting protocols, (I) We introduce KZH, a novel polynomial commitment scheme, and (II) KZH-fold, the first sublinear accumulation scheme with a constant-size verifier (3 group scalar multiplications) and O(n1/2 ) accumulator size and decider time. Our scheme generalizes to achieve accumulator and decider complexity of k • n1/k with a verifier of size k. Using the BCLMS compiler, (III) we build the first IVC/PCD scheme with sublinear proof and decider. (IV) Next, we propose a new approach to non-uniform IVC, where the cost of proving a step is proportional to the maximum size of all instruction circuits, and unlike previous approaches, the witness size is not linear in the number of instructions. (V) Leveraging these advancements, we demonstrate the power of KZH-fold by implementing an accountable voting scheme using a novel signature aggregation protocol supporting millions of nodes, significantly reducing communication overhead and verifier time compared to BLS-based aggregation. We implemented and benchmarked our protocols, and KZH-fold achieves a 2000x reduction in communication and a 50x improvement in decider time over Nova when proving 2000 Poseidon hashes, at the cost of 3x the prover time.

We present position-hiding linkability for vector commitment schemes: one can prove in zero knowledge that one or m values that comprise commitment \cm all belong to the vector of size N committed to in \com. Our construction \textsfCaulk can be used for membership proofs and lookup arguments and outperforms all existing alternatives in prover time by orders of magnitude.

We introduce Checkable Subspace Sampling Arguments, a new information theoretic interactive proof system in which the prover shows that a vector has been sampled in a subspace according to the verifier's coins. We show that this primitive provides a unifying view that explains the technical core of most of the constructions of universal and updatable pairing-based (zk)SNARKs. This characterization is extended to a fully algebraic framework for designing such SNARKs in a modular way. We propose new constructions of CSS arguments that lead to SNARKs with different performance trade-offs.