Paper 2023/1579

KiloNova: Non-Uniform PCD with Zero-Knowledge Property from Generic Folding Schemes

Tianyu Zheng, The Hong Kong Polytechnic University
Shang Gao, The Hong Kong Polytechnic University
Yu Guo, SECBIT Labs
Bin Xiao, The Hong Kong Polytechnic University

Most existing accumulation/folding schemes focus on implementing Incrementally Verifiable Computation (IVC). Proof-carrying Data (PCD), as a generalization of IVC, enables sequential computation performance by multiple distrusting parties, thereby offering a robust primitive tool in real-world applications. However, building non-uniform PCD from folding schemes faces many technical challenges, particularly in handling cross items and preserving zero knowledge. This paper introduces KiloNova, a non-uniform PCD system with zero-knowledge properties derived from generic folding schemes. Motivated by HyperNova (Kothapalli et al. ePrint 2023), we derive a variant of the Customizable Constraint System with linear claims on circuits and inputs to avoid cross items. With the new constraint system, we propose a generic folding scheme for multiple instances of different circuits and ensure the zero-knowledge property with various effective methods. Consequently, we build a non-uniform ZK-PCD scheme from the generic folding scheme and improve its performance with some optimization techniques, such as circuit aggregation and decoupling. We propose a new construction for ZK-PCD that does not use a ZK argument system and has little influence on the complexity. The theoretical evaluation shows our non-uniform ZK-PCD scheme outperforms previous models. A single multi-scalar multiplication dominates the prover cost at each step. The recursive circuit is dominated by $O(\log(n))$ random-oracle-like hashes and $O(k)$ scalar multiplications, where $n$ is the circuit input length and $k$ is the instance number at each step.

Available format(s)
Cryptographic protocols
Publication info
proof-carrying datacustomizable constraintsrecursive argumentsfolding schemes
Contact author(s)
tian-yu zheng @ connect polyu hk
shanggao @ polyu edu hk
yu guo @ secbit io
csbxiao @ polyu edu hk
2024-02-16: last of 5 revisions
2023-10-12: received
See all versions
Short URL
No rights reserved


      author = {Tianyu Zheng and Shang Gao and Yu Guo and Bin Xiao},
      title = {KiloNova: Non-Uniform PCD with Zero-Knowledge Property from Generic Folding Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1579},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.