Paper 2024/336

RAMenPaSTA: Parallelizable Scalable Transparent Arguments of Knowledge for RAM Programs

Khai Hanh Tang, Nanyang Technological University
Minh Pham, Orochi Network, Ho Chi Minh City University of Technology
Chan Nam Ngo, Independent

Incremental Verifiable Computation (IVC) allows a prover to prove to a verifier the correct execution of a sequential computation. Recent works focus on improving the universality and efficiency of IVC Schemes, which can be categorized into Accumulation and Folding-based IVCs with Folding-based ones being more efficient (due to their deferred proof generation until the final step). Unfortunately, both approaches satisfy only heuristic security as they model the Random Oracle (RO) as a circuit in their non-constant depth recursive composition of the base Scheme. Such drawback is two-fold: to connect the consecutive execution step the RO is recursively modeled as a circuit during the folding or the accumulating process, and again in the final SNARK wrapper circuit (a common practice in Folding-based IVCs). We revisit this problem, with a focus on the Folding-based IVCs due to their efficiency, and propose the detachment of RO invocation from the folding circuit. We can instead accumulate such invocations, yielding the so-called Conditional Folding (CF) Scheme to overcome the first drawback. One can consider our CF Scheme a hybrid Folding-Accumulation Scheme with provable security. We provide a non-trivial practical construction for our CF scheme that is natively parallelizable, which offers great efficiency. We rigorously prove the security of our CF scheme (also for the case of folding in parallel; and our scheme can be made non-interactive using Fiat-Shamir). Our CF scheme is generic and does not require trusted setup. It can be adapted to construct the first IVC for RAM programs, i.e. Parallelizable Scalable Transparent Arguments of Knowledge for RAM Programs that we dub RAMenPaSTA, that can be used to build zero-knowledge virtual machines (zkVMs). Both our CF Scheme and RAMenPaSTA can be of independent research interests.

Available format(s)
Cryptographic protocols
Publication info
Incremental Verifiable ComputationFolding SchemeROMProvable SecurityRAM ProgramsTransparent SetupzkVMs
Contact author(s)
khaihanh tang @ ntu edu sg
minh pham @ orochi network
ngochannam @ gmail com
2024-03-02: last of 2 revisions
2024-02-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Khai Hanh Tang and Minh Pham and Chan Nam Ngo},
      title = {RAMenPaSTA: Parallelizable Scalable Transparent Arguments of Knowledge for RAM Programs},
      howpublished = {Cryptology ePrint Archive, Paper 2024/336},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.