Welcome to the resource topic for 2023/1282
Title:
Proof-Carrying Data from Multi-folding Schemes
Authors: Zibo Zhou, Zongyang Zhang, Jin Dong
Abstract:Proof-carrying data (PCD) is a powerful cryptographic primitive that allows mutually distrustful parties to perform distributed computation defined on directed acyclic graphs in an efficiently verifiable manner. Important efficiency parameters include prover’s cost at each step and the recursion overhead that measures the additional cost apart from proving the computation.
In this paper, we construct a PCD scheme having the smallest prover’s cost and recursion overhead in the literature. Specifically, the prover’s cost at each step is dominated by only one O(|C|)-sized multi-scalar multiplication (MSM), and the recursion overhead is dominated by only one 2r-sized MSM, where |C| is the computation size and r is the number of incoming edges at certain step. In contrast, the state-of-the-art PCD scheme requires 4r+12 O(|C|)-sized MSMs w.r.t. the prover’s cost and six 2r-sized MSMs, one 6r-sized MSM w.r.t. the recursion overhead. In addition, our PCD scheme supports more expressive constraint system for computations—customizable constraint system (CCS) that supports high-degree constraints efficiently, in contrast with rank-1 constraint system (R1CS) that supports only quadratic constraints used in existing PCD schemes.
Underlying our PCD scheme is a multi-folding scheme that reduces the task of checking multiple instances into the task of checking one. We generalize existing construction to support arbitrary number of instances.
ePrint: https://eprint.iacr.org/2023/1282
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .