# Building a Zero Knowledge Proving Marketplace with Folding Schemes

> Molly Cantillon

[ToC]

Zero Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARKs) are a powerful cryptographic primitive enabling one party to prove a certain statement to another party without revealing any information about the input or intermediate steps.

zk-SNARKs possess an inherent succinctness, generating concise and easily verifiable proofs. Additionally, their non-interactive nature enables verifiers to authenticate these proofs without any involvement from the prover. As the feasibility of zk-SNARKs continues to expand, their prominence in discussions surrounding privacy and scalability is only set to soar.

However, despite their remarkable potential, a noteworthy obstacle persists: the arduous and costly challenge of proof generation.

Limitations in computational resources hinder the widespread adoption of zk-SNARKS. It is imperative to find ways to reduce the computational cost and improve efficiency of the prover. This is where the motivation for Incrementally Verifiable Computation arises, offering a promising solution to overcome the challenge.

### Incrementally Verifiable Computation (IVC)

Incrementally Verifiable Computation (IVC) is a technique that enables, in theory, infinite computation to be run on a machine. In addition to demonstrating the integrity of a machine's execution by providing proofs of correctness at each step, it provides evidence that all preceding steps have been properly executed.

Compared to traditional proving methods, IVC presents several advantages. IVC does not require static bounds on loop iterations, which is necessary for computations that require dynamic control flow. It minimizes memory overhead by only requiring space proportional to each step, which eliminates the need for storing the entire computation trace. IVC streamlines the process for parallel proof generation, enabling faster and more efficient computation.

To recursively prove the correct execution of incremental computations, the prover takes an input $z_i$, along with some extra witness $w_i$, and applies a step computation $F$ to generate an output where $F^{i}(z_0) = z_i$.

For each incremental step i, the prover uses a SNARK to construct a proof $\pi_i$ that demonstrates two things: (1) that it has applied $F$ correctly to the output of the previous step, i - 1, and (2) that the SNARK verifier has accepted the SNARK from i - 1.

** I'm not great at UML, will have to do a better job with the diagram **

##### One step of IVC

Prover->Verifier: Step computation F, input x, & witness w
Note right of Verifier: Verifier receives input
Prover->Verifier: Apply F^i(x_0) to get x_i
Note right of Verifier: Verifier checks computation
Prover->Verifier: Construct SNARK proof π_i
Note right of Verifier: Verifier checks proof

In this system, at each step, the prover needs to call a universal circuit as well as the verifier circuit, which makes the cost of proving this program proportional to the size of the universal circuit, impossibly large in some cases.

To overcome this high cost, Nova introduces **folding schemes**, IVC for a single instruction. They recursive folds together N circuit instances into one.

In more detail, they aggregate SNARKs by combining random linear combinations of witness vectors. This approach enables the verification of multiple incremental computations through a single proof. Folding schemes offer significant benefits: the verifier circuit remains of constant size, and the prover's workload is optimized.

Generalizing Nova's high-speed recursive proof system, SuperNova implements folding schemes for non-uniform IVC. SuperNova enables parallel running instances for each function, which helps to further reduce the proving cost by allowing multiple steps to be proved simultaneously.

Supernova handles a number of arbitrary polynomial-time functions $(F_1 .... F_n)$, where the choice of which function is executed, $F_i$ where $i \in [n]$, is determined by a selector function ϕ that chooses the instruction to execute at each step in the incremental computation. Thus, there exists witnesses $(w_0, ..., w_{i-1})$ such that:

$$
z_{j+1} ← F_{ϕ(z_i, w_i)}(z_i, w_i)
$$

SuperNova empowers the proof of universal machine executions without relying on universal circuits, using relaxed-committed R1CS, its significance lies in its support for machines with rich instruction sets. With Supernova, there can be N parallelized running instances for each function, which all fold together into the current steps' proof.

So, how can IVC, Folding Schemes, Nova, and SuperNova, solve the problem of expensive zk-SNARK proving?

### Delegation of Computation As A Service

As mentioned, the heavy computational resources required to prove zk-SNARK statements is unrealistic. Folding schemes serve as a solution to amortize the proving cost across multiple proofs of independent and unrelated statements. Now, instead of having to generate seperate computations for each statement, the prover only needs to produce a proof for one singular verifiable proof.

Using a property called selective verification introduced by Ràfols and Zacharakis [CITE], the prover aggregates statements coming from multiple different parties and is able to provide evidence that a specific statement was considered in constructing the final aggregated statement. Importantly, the proofs remain sublinear in the number of aggregated statements, making selective verification a powerful tool for validating individual statements without needing knowledge of the entire aggregation process.

In scenarios of computation delegation, the key value lies in deriving a single proof $\pi$ that enables the validation of multiple verifiers' proofs in a trustless manner. This becomes especially relevant when a prover outsources its computational resources to verifiers who require performing diverse, arbitrary computations. By consolidating these proofs into a single proof and verifying numerous computations in one singular job, proof generation becomes more efficient and reliable.

### Trees for Efficient Aggregation

To efficiently aggregate SNARK proofs and reduce the proving time, we can employ the hierarchical data structure of a **statement aggregation tree**.

With the use of a tree, the proof generation becomes logarithmic in the number of aggregated statements, significantly reducing computational resources for proof generation. Starting from the leaf nodes, where each leaf represents a distinct statement, we iteratively fold the leaf nodes to form their parent nodes. As we ascend the tree, pairs of parent nodes are again folded into higher-level parent nodes until a single root node is generated, which holds the final folded proof aggregating information from all the $2^k-1$ leaves.

We build on the approach derived from Ràfols and Zacharakis to bootstrap any 2-instance folding scheme to a N-instance folding scheme.

** Replace this with own tree diagram **

This technique takes advantage of the incremental folding that we mentioned earlier in the context of SuperNova, as it propagates upwards through the tree and combines information from multiple statements at each level.

The tree structure not only reduces the overhead of generating proofs but it also provides a natural parallelization mechanism for efficient verifications. By examining the proofs only pertaining to the relevant subtree, a verifier can selectively verify a specific aggregated statement without needing to validate the entire tree. This selective verification further improves the efficiency of the system by reducing the burden on the verifier and enabling rapid validations for individual statements, paving the way for formation of a marketplace.

### Construction of the Marketplace

In order for a marketplace to exist and flourish, there must be a well-aligned incentive structure that drives demand and supply. In the context of zk-proof generation, this involves provers who offer computation services and verifiers seeking secure, trustless verification for various computations. Both parties, ranging from hobbyist gamers with idle GPU resources to smart contract developers looking to save gas on verification, must converge. This enables individuals from around the world to bring their unique statements to be proven in an efficient, secure, and accessible manner.

The follwing architecture may further illuminate this proposal. Alice and Bob, as arbitrary verifiers, bring their statements to the marketplace to get their proofs generated. The market prover takes their public input, $z_i$ as well as their respective private input $w_i$ (which is omitted here for notational simplicity), and collapses the statements into one aggregate statement. This is done by inserting their statements as leaves in a statement aggregation tree and folding the tree upward to generate a single, compressed proof $\pi$ at the root. The marketplace prover then shares this proof with Alice and Bob, along with any additional data needed for selective verification.

By participating in the marketplace, Alice and Bob can offload the computational burden of generating their respective zk-SNARK proofs onto the prover, who aggregates and optimizes the proof generation through the use of folding schemes and a tree structure. This arrangement benefits both parties: Alice and Bob save computational cost and time, while the prover is compensated for their services through fees or other incentives.

The marketplace thus serves as a digital forum that connects parties in need of zk-proof generation with those who can efficiently generate the proofs. As the utilization of zk-SNARKs grows in the areas of privacy and scalability, a thriving marketplace will become an essential infrastructure for the widespread adoption of this powerful cryptographic primitive.


## Extensions
A different approach: Collaborative zk-SNARK Proving to split work among N provers who jointly produce a single proof over the distributed witness

## References [TODO]
Nova - https://eprint.iacr.org/2021/370.pdf
SuperNova - https://eprint.iacr.org/2022/1758.pdf?ref=hackernoon.com
Folding Schemes with Selective Verification - https://eprint.iacr.org/2022/1576.pdf
Nova-based ZKVM spec - https://hackmd.io/@monyverse/H1XSVmHNh

Use this for further discussion? Protostar - https://eprint.iacr.org/2023/620.pdf
Collaborative zk-SNARKs: https://www.usenix.org/system/files/sec22-ozdemir.pdf

Room for more writing:

More setting up defintions (ie commitment scheme, property definitions)
R1CS Math for this type of computation
Analysis on security with overcoming adversaries