Paper 2023/1282

Proof-Carrying Data from Multi-folding Schemes

Zibo Zhou, Beihang University
Zongyang Zhang, Beihang University
Zhiyu Zhang, N Labs
Jin Dong, Beijing Academy of Blockchain and Edge Computing

Proof-carrying data (PCD) is a cryptographic primitive enabling mutually distrustful parties to perform distributed computations on directed acyclic graphs with efficient and incremental verification. Key performance metrics include the prover cost at each step and the recursion overhead, which measures the additional cost beyond proving the original computation. Despite substantial advancements in constructing efficient PCD schemes, these metrics continue to be bottlenecks hindering their widespread application. In this paper, we advance the research by constructing a new PCD scheme based on a new generalized construction of multi-folding schemes. Compared with the state-of-the-art PCD scheme by Bünz et al. (CRYPTO'21), our scheme reduces the prover cost at each step from $4r+6$ multi-scalar multiplications (MSMs) of size $O(|C|)$ to $1$ MSM of the same size, and the recursion overhead from $6$ MSMs of size $2r-1$, $1$ MSM of size $6r-3$ to $1$ MSM of size $2r-1$, where $r$ is the number of incoming edges at certain step and $|C|$ is the proving computation size. Additionally, our PCD scheme supports a more expressive constraint system for encoding computations, namely the customizable constraint system, which supports high-degree constraints, in contrast to the rank-1 constraint system adopted by existing PCD schemes that only supports quadratic constraints. We implement our PCD scheme and report the concrete recursion overhead and practical efficiency for different values of $r$ and $|C|$. Compared with Bünz et al. (CRYPTO'21), our PCD scheme achieves a $2.5$ times lower recursion overhead when $r=2$ and $|C|=2^{20}$. Additionally, when $r=2$ and a proving computation size (excluding recursion overhead) of $2^{24}$, it takes $49$ seconds to generate a PCD proof at each step. Using a SNARK to compress the proof reduces the proof size from $1031$ MB to $13$ KB, with a tradeoff in the verifier time, which increases from $11$ seconds to $22$ seconds.

Note: add implementation

Available format(s)
Publication info
proof-carrying datarecursive proof compositionfolding schemes
Contact author(s)
zbzhou @ buaa edu cn
zongyangzhang @ buaa edu cn
zknevermore @ gmail com
dongjin @ baec org cn
2024-07-11: revised
2023-08-25: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial


      author = {Zibo Zhou and Zongyang Zhang and Zhiyu Zhang and Jin Dong},
      title = {Proof-Carrying Data from Multi-folding Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1282},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.