Boosting Batch Arguments and RAM Delegation

We show how to generically improve the succinctness of non-interactive publicly verifiable batch argument (BARG) systems. In particular, we show (under a mild additional assumption) how to convert a BARG that generates proofs of length poly(m) • k 1-ϵ , where m is the length of a single instance and k is the number of instances being batched, into one that generates proofs of length poly(m) • poly log k, which is the gold standard for succinctness of BARGs. By prior work, such BARGs imply the existence of SNARGs for deterministic time T computation with optimal succinctness poly log T .

Our result reduces the long-standing challenge of building publicly-verifiable delegation schemes to a much easier problem: building a batch argument system that beats the trivial construction. It also immediately implies new constructions of BARGs and SNARGs with polylogarithmic succinctness based on either bilinear maps or a combination of the DDH and QR assumptions.

Along the way, we prove an equivalence between BARGs and a new notion of SNARGs for (deterministic) RAM computations that we call "flexible RAM SNARGs with partial input soundness." This is the first demonstration that SNARGs for deterministic computation (of any kind) imply BARGs. Our RAM SNARG notion is of independent interest and has already been used in a recent work on constructing rate-1 BARGs (Devadas et. al. FOCS 2022).