# "Streaming" Aggregation techniques for Testudo

## Goal

The goal is to allow a prover to prove multiple times the same circuit with different witness but **only using memory linear in one proof**, or with a small constant per proofs.
In other words, we would like to have a snarkpack-like aggregation technique for Testudo. In Snarkpack, the prover generates Groth16 proofs sequentially and only keeps around each individual Groth16 proofs before aggregating them all.

## Context

Using uniformity of the circuit already brings down cost a lot for uniform circuits. However,
sometimes we need to compute _many_ of these proofs at once. For example in Snarkpack, miners will compute thousands of Groth16 proofs first and then aggregate with Snarkpack to only publish one aggregated proof onchain. The nice property in this model is that the memory required by the prover in this case is linear but very small, only 1 Groth16 per proof.

**Goal**: Have a snarkpack like aggregation mechanism where the memory of the prover can be linear but for a small amount of memory, i.e. prover is not required to keep the whole witness for each proofs.

## High Level view of current Testudo

Testudo is composed of the following:
* Two sumcheckS which are the same as Spartan
* An optimized PST implementation that replaces the Spartan PCS
* Specifically, we use a SQRT size trusted setup PST in combination with MIPP (from IPP paper)
* The Computational Commitment (CC) that is the same as Spartan (currently)

We are using Testudo on BLS12-377 and BLS12-381, **both curves are part of a 2chain model**. More specifically, we can build another proof on top of a Testudo proof to "compress" the original proof. For BLS12-377 it'd be BW6 with Groth16, and for BLS12-381, it's to-be-defined (it exists but unclear which proof system to use yet).

## Strawman 1

- Do Groth16 for the sumcheck, and keep one Groth16 proof for each circuit
- Keep the PST + CC openings in the clear (in the final proof)
- (a - optional) Verify PST + CC openings in one testudo proof with outer curve

Pros: simple to get
Cons: limited in number of aggregation:
* verifier work is linear in number of aggregated proof
* (a) circuit size will be the limiting factor

## Strawman 2

- Do Groth16 for the sumcheck, and keep one Groth16 proof for each circuit
- Random linear combination of PST polynomials
- P_p(x) = P_1(x) + r*P_2(x) + r^2P_3(x) ...
- only open 1 polynomial P_p(x)
- Random linear combination for CC openings

Problem is that prover needs to keep all the individual polynomials (witnesses) in memory
before deriving the randomness $r$, thus it doesn't solve the problem.

## Final Proposition

To prove K relations. This does not require to have the whole K witnesses but only K smaller states.

We call $\pi_{PSC}$ the "Spartan Sumcheck Core": the two sumcheck proofs proved in Spartan now. You can also think of it as the _witness_ to our current Groth16

The protocol:

- On reception of witness $w_i$ ("keeping" denotes keeping as state)
- Compute MIPP comm $T_i$. **Keep $T$ and its opening $\vec{A}$** ($K*\sqrt{N}$ storage in total)
- compute $\pi^{(i)}_{SPC}$, that is run the sumcheck protocol leading to point $y_i$. **Keep this sumcheck proof**
- Compute polynomials commitments $p^{j}_i$-s. **Keep them**
- Compute PST proof for $U_i$. **Keep it** ($K*log(\sqrt{N})$ storage in total)
- Partial evaluation of CC proofs:
- When it is time to "open", keep the opening point required but **do not open**.
- Only $K * log(N)$ storage in total

- When done steps above for all witnesses:
- Run a single Groth16 for the sumcheck
- Run a single MIPP on a linear combination of the U_i
- Send all U_is and PST proof
- For CC, do a [multi point opening](https://zcash.github.io/halo2/design/proving-system/multipoint-opening.html) to only open _once_ all the points _at once_ on the same polynomial
- Since it is the same polynonial, prover only needs to keep the points to open (x,ry)

Optimizations:
- (a) Do a snarkpack over all individual G16 sumchecks - constraints will be the bottleneck otherwise.
- (b) instead of sending all U_i, you commit to the U_i and do a TIPP on it so you only
send the committed U_is in the proof
* :bulb: How to do it exactly ?
* We can run a MIPP to prove a random linear combination of all U_i but how do you subsequently all U_i have been generated correctly ? (you can't do a mipp of a mipp)
* $U_i = \prod A_{i,j}^{y_i,j}$
* $C_u = Comm(\mathbf{U})$ // MIPP
* $C_T = Comm(\mathbf{T})$
* $U = \prod U_i^{r^i} = \prod_i (\prod_j A_{i,j}^{y_i,j})^{r^i}$
* $T = \prod T_i^{r^i} = \prod_i (\prod e(A_{i,j},h_j))^{r^i}$

## Verifier

$K$ is number of proofs to aggregate, $N$ is circuit size
Either natively or in circuit using an "outer curve":

* Verify snarkpack for the sumcheck proofs
* O(log(K)) for snarkpack
* Compute random linear combination of U_i and verify MIPP proof
* O(K) group addition then O(1) MIPP verification
* :warning: Any way to move from group addition to field addition? and/or to move to O(log(N))?
* Verify all PST proofs
* O(K) PST verification / pairings
* :warning: Any way to go down to O(log(N)) ? Or batch version, like [KZG batch](https://eprint.iacr.org/2020/081.pdf)
* Compute random linear combination of CC openings points and verify CC openings
* at least O(N) field operations then O(1) CC opening

## State
O(K sqrt(N))

## Proof size
O(K log(N))

## Perf estimation (TODO)

We need the following numbers (optimization (a))
* $M_c$ time to perform the PST/MIPP commitment
* $S$ time to perform the sumcheckS and its Groth16 proof
* $M_p$ time to perform the PST opening (without the MIPP)
* $M_m$ time to perform the MIPP proof
* $C_c$ time to perform a single CC opening
* $P$ time to perform a snarkpack over K groth16

A reasonable lower bound on the estimated proving time should be:
$K * (M_c + S + M_p) + C_c + P + M_m$

The verification will be higher but we plan to have a final proof system that verify all
of this, for "compression".