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.
Category / Keywords: foundations / proof-carrying data; accumulation schemes; recursive proof composition Original Publication (with major differences): IACR-CRYPTO-2021 Date: received 31 Dec 2020, last revised 1 Dec 2021 Contact author: benedikt at cs stanford edu, alexch at berkeley edu, pratyush at berkeley edu, nspooner at bu edu Available format(s): PDF | BibTeX Citation Note: Fix minor typo in abstract Version: 20211201:212231 (All versions of this report) Short URL: ia.cr/2020/1618