TY - GEN
T1 - Recursive proof composition from accumulation schemes
AU - Bünz, Benedikt
AU - Chiesa, Alessandro
AU - Mishra, Pratyush
AU - Spooner, Nicholas
N1 - Publisher Copyright:
© International Association for Cryptologic Research 2020.
PY - 2020
Y1 - 2020
N2 - 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.
AB - 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.
KW - Proof-carrying data
KW - Recursive proof composition
KW - Succinct arguments
UR - http://www.scopus.com/inward/record.url?scp=85098281776&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85098281776&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-64378-2_1
DO - 10.1007/978-3-030-64378-2_1
M3 - Conference contribution
AN - SCOPUS:85098281776
SN - 9783030643775
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 1
EP - 18
BT - Theory of Cryptography - 18th International Conference, TCC 2020, Proceedings
A2 - Pass, Rafael
A2 - Pietrzak, Krzysztof
PB - Springer Science and Business Media Deutschland GmbH
T2 - 18th International Conference on Theory of Cryptography, TCCC 2020
Y2 - 16 November 2020 through 19 November 2020
ER -