Cryptology ePrint Archive: Report 2020/499

Proof-Carrying Data from Accumulation Schemes

Benedikt BŁnz and Alessandro Chiesa and Pratyush Mishra and Nicholas Spooner

Abstract: 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.

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. However, they omit details about this approach and do not prove that it satisfies any security property. Nonetheless, schemes based on their ideas have already been implemented in software.

In this work we present a collection of results that establish the theoretical foundations for a generalization of the above approach. We define an *accumulation scheme* for a non-interactive argument, and show that this suffices to construct PCD, even if the argument itself does not have a sublinear-time verifier. Moreover we give constructions of accumulation schemes for SNARKs, which yield PCD schemes with novel efficiency and security features.

Category / Keywords: foundations / succinct arguments, proof-carrying data, recursive proof composition

Original Publication (with major differences): IACR-TCC-2020

Date: received 28 Apr 2020, last revised 29 Sep 2020

Contact author: benedikt at cs stanford edu,alexch@berkeley edu,pratyush@berkeley edu,nick spooner@berkeley edu

Available format(s): PDF | BibTeX Citation

Version: 20200929:225643 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]