Paper 2023/1282

Proof-Carrying Data from Multi-folding Schemes

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

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.

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


      author = {Zibo Zhou and Zongyang 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.