BUsec Seminar: "Proof-Carrying Data from Accumulation Schemes" with Nick Spooner

Recursive proof composition has been shown to lead to powerful primitives such as incrementally-verifiable computation (IVC) and proof-carrying data (PCD). All existing approaches to recursive composition take a succinct non-interactive argument of knowledge (SNARK) and use it to prove a statement about its own verifier. This technique requires that the verifier run in time sublinear in the size of the statement it is checking, a strong requirement that restricts the class of SNARKs from which PCD can be built. This in turn restricts the efficiency and security properties of the resulting scheme. In exciting recent work, Bowe, Grigg, and Hopwood (ePrint 2019/1021) outlined a novel approach to recursive composition, and applied it to a particular SNARK construction which does *not* have a sublinear-time verifier. In this talk I will present a formalisation of this approach called an 'accumulation scheme', and show that a SNARK with an accumulation scheme can be used to construct PCD, even if the SNARK itself does not have a succinct verifier. I will also present some accumulation schemes for SNARKs, which yield PCD schemes with novel properties via this construction. This is joint work with Benedikt Bünz, Alessandro Chiesa and Pratyush Mishra.