# Reducing constraints by adapting GKR protocol in zkbnb proving

## Purpose
We are the zkbnb team and we are planning to launch zkbnb mainnet soon. Using gnark as backend proving and [Groth16](https://eprint.iacr.org/2016/260.pdf) as backend proving protocol, the number of constraints is the major factor of performance bottleneck.

With the number of constraints growing bigger, the metrics below grow bigger or larger, which significantly impacts the performance in the proof system backend, including R1CS size, pk size, and proving time.

So the main purpose of this blog is to use an IOP protocol called GKR to reduce constraints number.

## Background

#### Groth16
[Groth16](https://eprint.iacr.org/2016/260.pdf) are widely used by layer 2 and roll-up projects as their final prove backend system. It will output a succinct proof that can be easily verified onchain. Groth16 first needs an arithmetic circuit that fully describes the function.

#### Constraints Number

In the zksnarks proving system, the frontend will first translate the program defined by DSL or codes into an arithmetic circuit, then the circuit will be described by the R1CS.

An arithmetic circuit consists of gates computing arithmetic operations like addition and multiplication, with wires connecting the gates. For example, the circuit looks like this


R1CS is the description of an arithmetic circuit used by groth16. R1CS is composed of many R1C, every single R1C will contain $L$, $R$, $O$ `LinearExpression`, and `LinearExpression` contains `variables` or `constants` set.

One R1C will describe that $L * R = O$. For the figure above, for the g1 gate we can describe it by R1C $L(w_1) * R(w_2) = O(w_4)$.

The constraint number of R1CS is the number of R1C.

#### Overview of GKR

GKR is an IOP protocol. Interactive oracle proofs (IOPs) are a multi-round generalization of probabilistically checkable proofs that play a fundamental role in the construction of efficient cryptographic proofs. Using GKR in zksnarks can help to save constraints when there is a large number of circuits that are highly repeated, Belling [$^1$](https://hackmd.io/@uCHu_NMSQ4mIUvA8i4qAyg/rkxBcmvcI) has researched the availability of embedding a GKR verifier in a snarks circuit.

The GKR protocol includes sumcheck protocols and how to turn a GKR arithmetic circuit with fan-in 2 inputs gates to specific joint rounds of sumcheck protocols. Every layer in GKR arithmetic circuit will turn into a sumcheck protocol. Here we highly overview the GKR protocol.

**1. GKR Arithmetic circuit**


In the GKR protocol, Describing the protocol requires one to define a certain number of functions. These functions capture either the geometry of the circuit or the values flowing through it. To make matters precise, we need to care about the repeated circuit number, here we have 4, then we need to care about the layer index, here we have 4 for each circuit, then every gate will have an index in the layer, for example here the blue border gate will be described as an index (3,3,2) to locate the position, and the red border gate will be described as an index (4,4,3) to locate the position.

Note that the first layer is the input of the GKR Arithmetic circuit, and the last layer is the output of the GKR Arithmetic circuit.

Thailer [$^2$](https://people.cs.georgetown.edu/jthaler/GKRNote.pdf)'s Refinement has shown that if we have $s_i$ gate in one layer, then for any gate index $z \in \mathbb{F}^{s_i}$, We will have the theorum as follow,
$$
\tilde{W}_i(z)=\sum_{\left(\omega_1, \omega_2\right) \in\{0,1\}^{2 s_{i-1}}} g^{(i)}\left(\omega_1, \omega_2\right) $$

$$
g^{(i)}\left(\omega_1, \omega_2\right)=\left(\tilde{a d d}_i\left(z, \omega_1, \omega_2\right)\left(\tilde{W}_{i-1}\left(\omega_1\right)+\tilde{W}_{i-1}\left(\omega_2\right)\right)+\tilde{m u l}_i\left(z, \omega_1, \omega_2\right) \tilde{W}_{i-1}\left(\omega_1\right) \cdot \tilde{W}_{i-1}\left(\omega_2\right)\right)
$$

**2. sumcheck protocol**

The main technical primitive used within the GKR protocol is the sum-check protocol of Lund, Fortnow, Karloff, and Nisan [$^3$](https://dl.acm.org/doi/10.1145/146585.146605).

Suppose we are given a $v$-variate polynomial $g$ defined over a finite field $\mathbb{F}$. The purpose of the sumcheck protocol is to compute the sum:

$$
H:=\sum_{b_{1} \in\{0,1\}} \sum_{b_{2} \in\{0,1\}} \cdots \sum_{b_{v} \in\{0,1\}} g\left(b_{1}, \ldots, b_{v}\right)
$$

In order to execute the protocol, the verifier needs to be able to evaluate $g\left(r_{1}, \ldots, r_{v}\right)$ for a randomly chosen vector $\left(r_{1}, \ldots, r_{v}\right) \in \mathbb{F}^{v}$.

The protocol proceeds in $v$ rounds as follows. In the first round, the prover sends a polynomial $g_{1}\left(X_{1}\right)$, and claims that $g_{1}\left(X_{1}\right)=\sum_{x_{2}, \ldots, x_{v} \in\{0,1\}^{v-1}} g\left(X_{1}, x_{2}, \ldots, x_{v}\right)$. Observe that if $g_{1}$ is as claimed, then $H=g_{1}(0)+g_{1}(1)$. Also observe that the polynomial $g_{1}\left(X_{1}\right)$ has degree $\operatorname{deg}_{1}(g)$, the degree of variable $x_{1}$ in $g$. Hence $g_{1}$ can be specified with $\operatorname{deg}_{1}(g)+1$ field elements. In implementations, $\mathcal{P}$ can specify $g$ by sending the evaluation of $g$ at each point in the set $\left\{0,1, \ldots, \operatorname{deg}_{1}(g)\right\}$.

Then, in round $j>1, \mathcal{V}$ chooses a value $r_{j-1}$ uniformly at random from $\mathbb{F}$ and sends $r_{j-1}$ to $\mathcal{P}$. In return, the prover sends a polynomial $g_{j}\left(x_{j}\right)$, and claims that

$$
g_{j}\left(X_{j}\right)=\sum_{\left(x_{j+1}, \ldots, x_{v}\right) \in\{0,1\}^{v-j}} g\left(r_{1}, \ldots, r_{j-1}, X_{j}, x_{j+1}, \ldots, x_{v}\right)
$$

The verifier compares the two most recent polynomials by checking $g_{j-1}\left(r_{j-1}\right)=g_{j}(0)+g_{j}(1)$, and rejecting otherwise. The verifier also rejects if the degree of $g_{j}$ is too high: each $g_{j}$ should have degree $\operatorname{deg}_{j}(g)$, the degree of variable $x_{j}$ in $g$.

In the final round, the prover has sent $g_{v}\left(X_{v}\right)$ which is claimed to be $g\left(r_{1}, \ldots, r_{v-1}, X_{v}\right) . \mathcal{V}$ now checks that $g_{v}\left(r_{v}\right)=g\left(r_{1}, \ldots, r_{v}\right)$ (recall that we assumed $\mathcal{V}$ can evaluate $g$ at this point). If this test succeeds (and so do all previous tests), then the verifier accepts, and is convinced that $H=g_{1}(0)+g_{1}(1)$. Proposition 1 (LunD ET AL. [$^3$](https://dl.acm.org/doi/10.1145/146585.146605)) Let $g$ be a $v$-variate polynomial defined over a finite field $\mathbb{F}$, and let $(\mathcal{P}, \mathcal{V})$ be the prover-verifier pair in the above description of the sum-check protocol. $(\mathcal{P}, \mathcal{V})$ is a valid interactive proof protocol for the function $H=\sum_{b_{1} \in\{0,1\}} \sum_{b_{2} \in\{0,1\}} \cdots \sum_{b_{v} \in\{0,1\}} g\left(b_{1}, \ldots, b_{v}\right)$.

**turning the circuit to multiple rounds of sumcheck protocols**
In the GKR protocol, $\mathcal{P}$ and $\mathcal{V}$ first agree on an arithmetic circuit $C$ of fan-in 2 over a finite field $\mathbb{F}$ computing the function of interest ( $\mathcal{C}$ may have multiple outputs). $\mathcal{C}$ is assumed to be in layered form, meaning that the circuit can be decomposed into layers, and wires only connect gates in adjacent layers. Suppose the circuit has depth $d$; we will number the layers from 1 to $d$ with layer $d$ referring to the input layer, and layer 1 referring to the output layer.

In the first message, $\mathcal{P}$ tells $\mathcal{V}$ the (claimed) output of the circuit. The protocol then works its way in iterations towards the input layer, with one iteration devoted to each layer. The purpose of iteration $i$ is to reduce a claim about the values of the gates at layer $i$ to a claim about the values of the gates at layer $i+1$, in the sense that it is safe for $\mathcal{V}$ to assume that the first claim is true as long as the second claim is true. This is accomplished by applying the standard sum-check protocol to a certain polynomial (see Equation (2) in Section 3 for details).

More concretely, the GKR protocol starts with a claim about the values of the output gates of the circuit, but $\mathcal{V}$ cannot check this claim without evaluating the circuit herself, which is precisely what she wants to avoid. So the first iteration uses a sum-check protocol to reduce this claim about the outputs of the circuit to a claim about the gate values at layer 2 (more specifically, to a claim about an evaluation of the multilinear extension of the gate values at layer 2). Once again, $\mathcal{V}$ cannot check this claim herself, so the second iteration uses another sum-check protocol to reduce the latter claim to a claim about the gate values at layer 3 , and so on. Eventually, $\mathcal{V}$ is left with a claim about the inputs to the circuit, and $\mathcal{V}$ can check this claim on her own.

## Architecture

### Record hash inputs

When for practical use of the embedded GKR, we might fast think that it is easy to collect all the hashes used in the circuit and then assign to the GKR circuit. This is workable but will rely on the users understanding of what they're doing, if any of the hashes internal were not counted, then they will not be included in the GKR verifier circuit and cause integrity failure.

The convenient way for users to collect hashes automatically is to let them use hints. We have implemented a hint called MiMC2Elements, during compilation R1CS, we will collect all the hints called with their inputs and outputs, moreover their inputs variables and outputs variables for further adaptations.

### Assign GKR witness

We will separate the GKR circuit and the Non-GKR circuit. That is to record the GKR circuit constraint index, and move the levels builder of the GKR circuit backward. Then during solving the circuit, the GKR circuit will not be solved, it acts almost like an original circuit in gnark.

We need to assign GKR witness after solving all the non-GKR circuit constraints. Notice that we already have the internal inputs for all the hashes in the above steps, the inputs will be verified in GKR verifier circuit after we calculate the GKR proof and insert it into the witness. Notice that since we postpone all GKR circuit related solving steps, the witness has not been consumed in the solving phase, so we have nothing more to do except assignment to witness and its related solutions.

### Finalize and Constraint

After solving the circuit can correctly run and will return a proof, however, this proof can not state that all the hashes used have been verified in the in-circuit GKR verifier. That is, the hashes' results used in the Non-GKR circuit are from hints.

So after compilation, we will need to constrain or link to the GKR circuit in both the input sides and the output sides. Notice that we collect hints' input variables and outputs variables already, thus we just need to collect the GKR verifier's input variables and outputs variables (which will be solved after assigning the GKR proof), and constraint the inputs from hints to the inputs of GKR verifier, constraint the outputs from hints to the outputs of GKR verifier. Then the hashes' results used in the Non-GKR circuit are not only generated from hints but also constrained in the in-circuit GKR verifier.

### Optimization

When the adapted circuits are not enough to make effects using GKR. We have different GKR sizes for different MiMC usage circuits. That is to make sure the GKR verifier constraints are as little as we would use.

GKR verifier circuit also uses a lot of constraints to calculate the internal randomness by hashing. We first split the GKR layers to reduce the constraints the GKR verifier used. And for a split GKR, we can parallelly generate the GKR proofs, reducing the solving phase time.

Moreover, by using Poseidon as a randomness generator we will significantly reduce the constraints used by GKR verifier circuit.

### Other Solution

We notice that gnark team has a plan to launch a more universal solution to integrate GKR into gnark, which is called [GKR api](https://github.com/ConsenSys/gnark/pull/443).
Our solution is customized to mimc hash and we use a pre-define GKR circuit. They will have a more general implementation and no need to pre-define the GKR circuit using GKR api.
However, to use gnark original GKR api users will need to change the circuit implementation a lot to apply GKR api which also calls out the users to fully understand the meaning of GKR api. (including the Fiat-Shamir Transform Initial Hash Calculating.) And we can not tell if the circuit generated by GKR api will definitely save constraints in the specific case, because GKR needs a specific number of repeated circuits to make effects.

## Experiment

Our production experiment showed that in the same situation, the GKR can save more than 40% constraints and more than 50% proving time.


## Contribution

1. We include a practical way to embed GKR into real production. And finally, reduce half of the constraints used in zkbnb.

2. We make the GKR api more unconscious to users, while they don't need prerequisites of GKR protocols or Fiat-Shamir Transform.

3. We include splitting layers, hashing block commitment, Poseidon Hash techniques to make the GKR protocols embedded more practical in performance.

## What can be done next?

1. Embedding more GKR circuits in the snarks will be beneficial for reducing more constraints. The reason GKR verifier is using plenty of constraints is that it still needs hash to calculate the internal randomness as the Fiat-Shamir Transform needs. Thus if embed more GKR circuits, we will be able to shrink the original hashes again, and with more GKR circuits, we can shrink them to use a small number of constraints.

2. The recursive GKR is attractive, for more and more layer2 or zkevm teams are using recursive proofs. If using recursive GKR, the GKR proving time can be shrunk exponentially.