# Faster PLONK verification for Halo-like PCD

Prior to our discovery of [Halo](https://eprint.iacr.org/2019/1021), proof-carrying data (PCD) was achieved using a straightforward transformation: find a SNARK that has a sublinear-time verifier in the circuit size, embed this verifier into the circuit, and now recursively compose your proofs. Linear-time verifiers can't work with this recursion approach because the recursive circuit will never converge to a finite size. The problem is that the most attractive SNARKs with sublinear-time verifiers that we are aware of today have either pairings and trusted setups (and are over huge elliptic curves) or have large proofs in practice.

The [inner product argument](https://eprint.iacr.org/2016/263) is a protocol that does not require a trusted setup and can be built over ordinary and efficient elliptic curves. It can be used as a subprotocol to build a wide variety of different SNARKs. Unfortunately, its verification routine is linear-time in the circuit size. As part of Halo, we sidestepped this problem by discovering a technique that could be used to build PCD using the inner product argument anyway. The idea was later formalized into a more general concept called an [accumulation scheme](https://eprint.iacr.org/2020/499). Informally, here's how it works:

* There's this object called an **accumulator**. This object does not grow in size.
* You create a proof that some previous proof(s) exist and that some previous state of the accumulator was "updated" with these proofs, producing a new accumulator state. Checking that this update to the accumulator was performed correctly is asymptotically more efficient than the circuit size of the proofs being added to it, allowing your circuits to converge in size.
* At any point, you can check the accumulator using a linear-time "decision" procedure. If it checks out, all the proofs previously added to the accumulator are correct by induction.

This approach allowed us to use the inner product argument for PCD, and later works figured out that an even larger class of protocols can be used to build IVC/PCD, including ones that are [not succinct at all](https://eprint.iacr.org/2020/1618) and others that [don't even have](https://eprint.iacr.org/2020/1536) linearly homomorphic commitment schemes.

## Avoiding pre-processing

At the time we wrote Halo we were using the inner product argument to obtain a polynomial commitment scheme, since from there obtaining a SNARK is a simple matter of throwing a Polynomial IOP at it. Except that at the time the only such IOP we knew of was [Sonic](https://eprint.iacr.org/2019/099).

Sonic had a quirk which required the verifier to compute $s(x, y)$ for some _public_ bivariate polynomial $s(X, Y)$ and some verifier challenges $x, y$. This polynomial was used to encode the entire circuit and so evaluating it is linear-time in the circuit size. In other words, Sonic was not fully succinct even if the underlying polynomial commitment scheme we used was. IOPs which didn't have this problem, such as [Marlin](https://eprint.iacr.org/2019/1047) and [PLONK](https://eprint.iacr.org/2019/953), used pre-processing to avoid it. Unfortunately, they didn't appear publicly until just after we had developed Halo.

So, to avoid the problem of computing $s(X, Y)$ as part of Halo, we inadvertently devised yet _another_ accumulation scheme (sort of), inspired by a similar trick in the Sonic paper. It works roughly like this: have the prover commit to $C = \text{Comm}(s(x, Y))$ for the concrete value $x$, then have the prover open $C$ at $y$ to obtain $s(x, y)$. It remains to show that the prover's choice of $C$ is correct. We can do this with an "accumulation scheme" (roughly speaking) that works as follows:

* The accumulator is $(S_\text{old}, y_\text{old})$.
* The decision procedure for checking the accumulator is $S_\text{old} =^? \text{Comm}(s(X, y_\text{old}))$.
* The update procedure takes $(S_\text{old}, y_\text{old}), x, C$ as input
* The verifier chooses challenge $y_\text{new}$.
* The prover supplies $S_\text{new} = \text{Comm}(s(X, y_\text{new}))$.
* The prover opens $C$ at the point $y_\text{new}$ to the same value that $S_\text{new}$ opens at $x$.
* The prover opens $C$ at the point $y_\text{old}$ to the same value that $S_\text{old}$ opens at $x$.
* The new accumulator is $(S_\text{new}, y_\text{new})$

Now, the decision procedure shows the previous values of $C$ (and thus all of the evaluations of $s(x, y)$ that were provided by the prover) are correct by induction. This happens because $y_\text{new}$ is always chosen after the prover supplies $C$, so if $C$ is a commitment to a polynomial $c(Y)$ and $c(y_\text{new}) = s(x, y_\text{new})$ then with high probability we have $c(Y) = s(x, Y)$. The same effect occurs when checking $c(y_\text{old})$ against $S_\text{old}$ because $x$ is chosen after $S_\text{old}$ is determined.

This allowed us to use Sonic for Halo even though it was not a "succinct" Polynomial IOP. It also meant that Halo didn't require any pre-processing, strictly speaking. This was somewhat surprising because pre-processing is considered a vital tool for building most kinds of SNARKs in the first place.

## Speeding up other IOPs

There are many newer Polynomial IOPs (such as PLONK) which do use pre-processing: they typically encode parts of the circuit into some number of fixed polynomials $l_i(X)$ which have to be evaluated at some concrete value $x$ during the verification procedure. Instead, it's better to compute commitments to these polynomials in advance so that the prover can open them for the verifier.

However, sometimes there are _a lot_ of these fixed polynomials. For example, in the Zcash "Orchard" protocol we (currently) have $44$ different fixed polynomials that have to be opened by the prover per transaction. These include things like "selectors", lookup tables, permutation polynomials etc. The cost of having so many commitments to open during PCD is especially irritating: you now need to supply a hash of the verification key as a public input, "unhash" it to obtain these commitments and then perform group arithmetic on each of them. (You can avoid some of the hashing in special cases.)

An alternative is to do what we did in Halo. Let

$$s(X, Y) = \sum_i Y^i l_i(X)$$

Now, do the same accumulation trick as described above except instead of the prover committing to $C$ with a polynomial commitment scheme, have the prover send a commitment to $C$ as the coefficients of $s(x, Y)$ directly. These coefficients are literally each of the evaluations $l_i(x)$ that the verifier needs! The remainder of the accumulation scheme stays the same.

This means that during PCD you do not need to perform a hash operation and group arithmetic over each fixed polynomial commitment. Instead, you continually accumulate the provers' claims about the evaluations of these fixed polynomials. The decision procedure for this accumulator is also efficient once you do have access to commitments to the $l_i(X)$ polynomials, because deciding $(S, y)$ requires a multiscalar multiplication the same size as the number of fixed polynomials. Notably, this also means you could "decide" this accumulator somewhere in the middle of your PCD-tree rather than at the very end!