Proof-Carrying Data without Succinct Arguments

Benedikt Bünz; Alessandro Chiesa; William Lin; Pratyush Mishra; Nicholas Spooner

Paper 2020/1618

Proof-Carrying Data without Succinct Arguments

Benedikt Bünz, Alessandro Chiesa, William Lin, Pratyush Mishra, and Nicholas Spooner

Abstract

Proof-carrying data (PCD) is a powerful cryptographic primitive that enables mutually distrustful parties to perform distributed computations that run indefinitely. Known approaches to construct PCD are based on succinct non-interactive arguments of knowledge (SNARKs) that have a succinct verifier or a succinct accumulation scheme. In this paper we show how to obtain PCD without relying on SNARKs. We construct a PCD scheme given any non-interactive argument of knowledge (e.g., with linear-size arguments) that has a *split accumulation scheme*, which is a weak form of accumulation that we introduce. Moreover, we construct a transparent non-interactive argument of knowledge for R1CS whose split accumulation is verifiable via a (small) *constant number of group and field operations*. Our construction is proved secure in the random oracle model based on the hardness of discrete logarithms, and it leads, via the random oracle heuristic and our result above, to concrete efficiency improvements for PCD. Along the way, we construct a split accumulation scheme for Hadamard products under Pedersen commitments and for a simple polynomial commitment scheme based on Pedersen commitments. Our results are supported by a modular and efficient implementation.

Note: Fix minor typo in abstract

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in CRYPTO 2021
Keywords: proof-carrying data accumulation schemes recursive proof composition
Contact author(s): benedikt @ cs stanford edu
alexch @ berkeley edu
pratyush @ berkeley edu
nspooner @ bu edu
History: 2021-12-01: last of 5 revisions; 2020-12-31: received; See all versions
Short URL: https://ia.cr/2020/1618
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1618,
      author = {Benedikt Bünz and Alessandro Chiesa and William Lin and Pratyush Mishra and Nicholas Spooner},
      title = {Proof-Carrying Data without Succinct Arguments},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1618},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1618}},
      url = {https://eprint.iacr.org/2020/1618}
}