Summary: This document describes the challenges on how to turn the IVC scheme of Nova into a fully general PCD and describes some applications for it:

• We first recaps how Nova works and how the PSE notes and codebase work in the setting of parallel iteration.
• We then describe generically how to adapt its core to work in the setting of general graph structure (useful for zkMapReduce). It then dives into details on how to implement this proposal in the context of cycle of curves by highlighting a major blocker which prevented PSE proofs to be satisfiable.
• It then proposes a new augmented F’ circuit that works both in parallel iteration or parallel computation on independent leaves (i.e. our setting, MapReduce).
• Among others, one important application that concerns us using this technology is zkMapReduce, for example proving batch membership of many leaves in parallel in a Merkle Tree (implementation), and even more advanced scheme such as RecProofs.

The key technical takeaway of this post is that turning IVC into PCD is not necessarily trivial, even native multi-folding schemes such as Hypernova or Protogalaxy !

Requirements: Even though this post presents some recap, it assumes some high level familiarity into how Nova works. Please see the awesome-folding repo for some introduction material in Nova.

👁️ Motivation

⛓️ Proving sequential computations in parallel

The PSE team put out some great notes and PoC codebase to allow a prover to use Nova to prove in parallel a sequence of operations. In their context, the sequence is a sequence of opcodes, where steps are “linked together”:

The whole execution trace of a program is chunked into multitude of chunks, where output of chunk $i$ is the input of chunk $i+1$

The motivation is instead of doing it via vanilla Nova that only provides IVC computation style, and thus, forces the prover to prove each execution sequentially in the IVC path, one can organize the computations / chunks in a tree.

In order to do this, each chunk is carefully placed at specific position in the tree, and the prover can prove in parallel all nodes in one level, starting from the leaves to the root. For example, the second chunk is the parent node of the first and the third, and ensures the transition of outputs “1 → 2 → 3” See the figure from their notes where each node is a step of the computation:

https://kroki.io/graphviz/svg/eNqNk8FvgjAYxe_-FV96wqRLCiLiTD1yW7I781ChCpG1pLBkYvzfV5QWMJCsBw6vv_e176Us0vysWJlBlnPFVJJd4bYAvYRMOcQnKWrBvjn9kEJWJUs4bqUqbzh1Ca4yVnJ6lL-HhwdFKwRve7ihyEV3iNNc0SNLLhgKduQFReAQ7C3RYfeKr6dxcHwcDPiN4bcz40Pskil-NTefjOa7hicjPpGFVBSdFecCjcKQKbP3HzM43qiKtXH781X4U3wwwQMFfb1glG1rDOHcASEOp3iXzBn0CxjU_fhEBOIO0CViGKXvwMjrGW-O8XvGt2LQi4EVw14MregO7qEDmFROLvJ6iSCu6mvBacqqjKd2k4t0Zu8JlErKE-q6KH44hiFqm_lssXf4EtrjNAToHhrdkx4wnPb8zdqlmLjQSv9lOytFm7b87sCHen91vrhstNanq7fxGzJ4ouS5b5IaZNCQ7rA77774A4tODx8=

Problem: In order to do this, the Nova codebase has been tailored for this specific use case and can’t support other such as the following.

🪜Generalization to independent computations in parallel

For our use case, we want to implement a more general case, i.e. a fully-generalized PCD / DAG structure:

• Distinct leaves: Inputs to leaves are any arbitrary set of values. The computations done at the leaf level are not necessarily linked together
• Merge operation: The intermediate nodes take the output of their children and compute one output.