# HOWTO: GKR compression

approximate project guide for GKR Bootcamp; feel free to change / adjust anything, this is more like a set of recommendations

### 1. Define verification IR

This is the set of ops that we are trying to verify. Basically, it should involve

1. Arithmetic constraints.
2. Hashes (in the form of Poseidon permutation).

Additionally, if we want to apply this to something like STARK verification (i.e. make a recursively compressing GKR that verifies the STARK), we will also need non-native ops (or at least operations that do range-checks).

The reason for this is that STARK will likely be defined over a small field (though it's hash can still be large-field Poseidon, the arithmetic on the polynomial values will be non-native; I have first seen it [here](https://github.com/polymerdao/plonky2-circom), but almost any STARK on-chain verifier does this)

Similar consideration is applied to GKR over small field, if we are doing one - while hashes can use large-field Poseidon, the arithmetic of the sumcheck verifier will be over the extension of this small field.

*Q: Why I think that you need IR?*

*A: It is very desirable to be able to adjust protocols. Instead of doing monolithic circuit to verify our protocol, it is far better to be able to verify any protocol whos verifier is expressed in this (fairly minimalistic IR).*

*Q: Why don't we have elliptic curve ops in this IR, I thought GKR involves commitments?*

*A: We can. But our current plan does not involve full recursive verification, so in a sense we will only be doing the sumcheck part of the GKR. It might simplify a lot of stuff, though, so optionally we can add these ops to IR.*

### 2. Teach your favorite GKR framework to compile verifier into this IR

Nuff said. Actually, we probably should have an operation in GKR doing "batch open KZG commitments", as a placeholder for an actual verification of KZG commitments.

Additionally, note that my definition of IR is only "constraint system" (extended with primitives such as hashes). So realistically protocol should give the IR, and it's previous result (proof struct) should be interpreted as *assignment* (witness) to this system of constraints.

### 3. Make a protoboard

GKR by itself is absolutely terrible at control flow, because if you do random wiring between layers, the verifier blows up.

It is somewhat decent at control flow of data-parallel circuits (and *I think* Expander attempts to layout it in a sensible way, so a circuit doing, for example, 10000 Poseidons should be *okay*). If it is not the case, we will need to write Poseidon-doing circuits manually (and yes, there will be no circuits that do anything else but Poseidons).

Protoboard is, basically, our take on control flow - let PlonK manage it, and only use GKR for highly data-parallel circuits. The difference with PlonK that it is multiround.

GKR has tradeoff between depth (larger depth = larger verifier) and amount of data that we need to commit.

I am assuming that we have a collection of PlonK-ish columns $C_0, C_1, C_2, ...$ (actually, each $C_i$ maybe represented by multiple columns if the data does not fit well enough, similar to Axiom's Halo2 framework).

We start off with a given circuit in our IR.

$C_0$ represents commitments done by our original protocol.

$C_1$ represents the following computation - it runs the provided IR, up to all the hash operations. Hash operations (inputs/outputs) are copied to a particular column (which represent input to GKR protocol running all the Poseidons in parallel).

This gives us a new IR circuit (representing sumcheck part of the GKR circuit doing the Poseidons). This circuit is run in $C_2$ (up to deferred operations), et cetera.

Now, plot twist is that we are gradually decreasing the depth of the GKR circuit: for example, if we are doing 10k Poseidons, GKR verifier wants to do ~1000. But if we are doing ~700 Poseidons, we get to the point that GKR will not compress it further. So we need to aggresively chunk the Poseidon into pieces -

Three rounds of compression are likely optimal (but you can experiment on this by yourself):

1. Monolithic Poseidon circuit.
2. Split into ~4 pieces.
3. Single layer with nonlinear $x \mapsto x^5$ operation (and some linear stuff). Also, check Neptune strategy of Poseidon computation to understand how to commit to less intermediate terms in partial rounds of Poseidon.

### 4. Connections

Protoboard itself should run Hyperplonk protocol. However, we also need to connect outputs of some protocols with inputs, so the Hyperplonk verifier will need to be modified.

Specifically, it must ensure that

1. $C_i$ is fed as an input of Fiat-Shamir of the $i$-th protocol (which is being executed inside of $C_{i+1}$). I.e. we need to extract $\text{comm}(C_i)$ and (after parsing as collection of native field elements) feed it back as public input to $C_{i+1}$.

2. Final opening claim of $i$-th run is returned (as public output) and validated by Hyperplonk opening argument.

### 5. I'm scared, why is this sound?

I don't have written proof for this, but here is the rough argument.

$C_n$ faithfully executes the verifier (because it is just HyperPlonK, and we believe in HyperPlonK). It justifies that the run of $C_{n-1}$ is correct (as long as we correctly fed the i/o). Proceed by induction.

### 6. Optimizations, tricks.

As you can see, HyperPlonK for $C_i$ and $i$-th run of GKR will both demand to open in some points. Suggest doing multiopening reduction before it (it is almost free in multilinear world, just an additional round of sumcheck applied globally to all our $C_i$-s).

### 7. Looks like we need to write everything from scratch?

I am not exactly sure, but it looks like a lot of frameworks do not acknowledge a lot of these tricks. So possibly yes (though I think even just having a verifier IR will be a welcome addition to Expander)