$$

$$

$$

$$

$$

$$

Grand product arguments

Let

$\mathbb{F}$ be a finite field and consider a vector

$f=(f_0,\dots ,f_{n-1})\in {\mathbb{F}}^n$, where

$n=2^v$.
Given some kind of commitment

${\text{comm}}_f$ to

$f$ and a value

$y\in \mathbb{F}$, we want to convince a verifier that the product of the elements of

$f$ is

$y$,

$\prod f_i=y$.

Using AIR constraints

This problem can be solved using univariate polynomials and AIR constraints. This is the approach taken in Plonk^[1].

Let

$c_i=\prod _{j\le i}{f}_j$ be the vector of cumulative products of

$f$. The equality

$\prod f_i=y$ is equivalent to

$c_{n-1}=y$. Therefore, a protocol to prove this equality is to commit to both

$f$ and

$c$ and check the following AIR constraints

• $c_0=f_0$,
• $c_{i+1}=c_i\cdot f_{i+1}$ for all
  $i<n-1$,
• $c_{n-1}=y$.

Using GKR

This is the approach of [Tha13, 5.3.1]^[2].
For

$0\le k\le v$, we consider the vector

$g_k$ of size

$2^k$ given by

$$g_{k,i}=\prod _{i\cdot 2^{v-k}\le j<(i+1)\cdot 2^{v-k}}{f}_j.$$
Note that

$g_v=f$ and

$g_0$ is the constant

$y$. The vector

$g_k$ can be seen as the

$k$-th layer in the binary multiplication tree with leaves

$f$.
These vectors satisfy the relations

$$g_{k,i}=g_{k+1,2i}\cdot g_{k+1,2i+1}.$$
Seeing

$g_k$ as a function

$\{0,1{\}}^k\to \mathbb{F}$ instead, the relation becomes

$$g_k(\mathbf{i})=g_{k+1}(\mathbf{i},0)\cdot g_{k+1}(\mathbf{i},1).$$
Therefore, the MLEs

${\tilde{g}}_k$ satisfy

$${\tilde{g}}_k(\mathbf{i})={\tilde{g}}_{k+1}(\mathbf{i},0)\cdot {\tilde{g}}_{k+1}(\mathbf{i},1).$$
and thus for any

$\mathbf{z}\in {\mathbb{F}}^k$ we have

$${\tilde{g}}_k(\mathbf{z})=\sum _{\mathbf{i}\in \{0,1{\}}^k}\widetilde{\text{eq}}(\mathbf{z},\mathbf{i})\cdot {\tilde{g}}_{k+1}(\mathbf{i},0)\cdot {\tilde{g}}_{k+1}(\mathbf{i},1).$$
The evaluation of this sum can be proved using the sumcheck protocol. At the end of the protocol, the verifier needs to evaluate

${\tilde{g}}_{k+1}$ at

$(\mathbf{r},0)$ and

$(\mathbf{r},1)$ for a random

$\mathbf{r}\in {\mathbb{F}}^k$.

The trick to do so efficiently is to consider the degree one univariate polynomial

$h(t)={\tilde{g}}_{k+1}(\mathbf{r},t)$ for

$t\in \mathbb{F}$. We have

$$h(0)={\tilde{g}}_{k+1}(\mathbf{r},0)\text{ and }h(1)={\tilde{g}}_{k+1}(\mathbf{r},1)$$
therefore to send

$h$ it is sufficient to send

${\tilde{g}}_{k+1}(\mathbf{r},0)$ and

${\tilde{g}}_{k+1}(\mathbf{r},1)$ (which are anyways required by the verifier). Then the verifier sends a random

$u\in \mathbb{F}$ and uses the sumcheck protocol to check that

$$h(u)={\tilde{g}}_{k+1}(\mathbf{r},u).$$
Therefore, proving an opening

${\tilde{g}}_k(\mathbf{z})$ can be reduced to a sumcheck argument and an opening

${\tilde{g}}_{k+1}(\mathbf{r},u)$.

The strategy to prove

$\prod f_i=g_0=y$ is then clear:

• Reduce the evalutation proof
  $g_0=y$ to a sumcheck argument and an evaluation
  ${\tilde{g}}_1({\mathbf{r}}_1)$.
• For
  $k=1,\dots ,v-1$, reduce the evalutation proof
  ${\tilde{g}}_k({\mathbf{r}}_k)$ to a sumcheck argument and an evaluation
  ${\tilde{g}}_{k+1}({\mathbf{r}}_{k+1})$.
• The last evaluation
  ${\tilde{g}}_v({\mathbf{r}}_v)=\tilde{f}({\mathbf{r}}_v)$ is proved using the commitment to
  $f$.

Costs

• Prover: A sumcheck argument costing
  $O(2^k)$ for
  $k=0\dots v-1$ and an evaluation proof for
  $f$, so in total
  $O(n)+\text{ prover cost of evaluation proof}$. The commited polynomial is
  $f$ of size
  $n$.
• Verifier: A sumcheck argument costing
  $O(k)$ for
  $k=0\dots v-1$ and an evaluation proof for
  $f$, so in total
  $O(v^2)+\text{ verifier cost of evaluation proof}$.
• Proof size: A sumcheck argument of size
  $O(k)$ for
  $k=0\dots v-1$ and an evaluation proof for
  $f$, so in total
  $O(v^2)+\text{ size of evaluation proof}$.

Quarks

This is the approach of [SL20, Section 5]^[3].
Instead of using

$v+1$ different functions

$\{g_k:\{0,1{\}}^k\to \mathbb{F}{\}}_{k=0}^v$, we can pack them into a single function

$g:\{0,1{\}}^{v+1}\to \mathbb{F}$ given by

$$g(1^l,0,x)=g_{v-l}(x)\text{ for }x\in \{0,1{\}}^{v-l},$$
and

$g(\mathbf{1})=0$. Note that

$g(0,x)=g_v(x)=f(x)$ for

$x\in \{0,1{\}}^v$ and

$g(1^v,0)=g_0=y$. Furthermore, the relation between the adjacent functions

$g_k$ and

$g_{k+1}$ becomes

$$g(1,x)=g(x,0)\cdot g(x,1)\text{ for }x\in \{0,1{\}}^v.$$
Let

$h(x)=g(1,x)-g(x,0)\cdot g(x,1)$ for

$x\in \{0,1{\}}^v$, then

$\tilde{h}$ is the zero polynomial, which we can check with the usual zero-check

$$0=h(\tau )=\sum _{x\in \{0,1{\}}^v}\widetilde{\text{eq}}(\tau ,x)(g(1,x)-g(x,0)\cdot g(x,1)),$$
where

$\tau$ is a random verifier challenge, which is proved with a sumche
Therefore, the product

$\prod f=y$ can be proved by commiting to

$\tilde{g}$ and

• using the sumcheck argument to prove
  $h(\tau )=0$,
• prove
  $g(0,x)=f(x)$ by checking
  $\tilde{g}(0,\gamma )=\tilde{f}(\gamma )$ for a random
  $\gamma$,
• open
  $\tilde{g}(1^v,0)=\prod f=y$.

Costs

• Prover: A sumcheck argument costing
  $O(n)$ and evaluation proofs for
  $g$ and
  $f$, so in total
  $O(n)+\text{ prover cost of evaluation proofs}$. The commited polynomials are
  $f$ of size
  $n$ and
  $g$ of size
  $2n$.
• Verifier: A sumcheck argument costing
  $O(v+1)$ and evaluation proofs for
  $g$ and
  $f$, so in total
  $O(v)+\text{ verifier cost of evaluation proofs}$.
• Proof size: A sumcheck argument of size
  $O(v)$ and evaluation proofs for
  $g$ and
  $f$, so in total
  $O(v)+\text{ size of evaluation proofs}$.

Note that compared to GKR, the verifier cost and proof size go from quadratic in

$v$ to linear in

$v$, at the cost of more and larger evaluation proofs.

Hybrid approach

This is the approach of [SL20, Section 6]^[3:1], also used in Lasso^[4].
We can get the best of both approaches by combining them. Fix a number

$1\le \ell \le v$, we use the Quarks approach for the first

$\ell +1$ layers

$\{g_k{\}}_{k=0}^{\ell }$ and the GKR approach for the last

$v-l$ layers

$\{g_k{\}}_{k=\ell +1}^v$. Concretely, this means that in the Quarks protocol, we instead have

$g(0,x)=g_{\ell }(x)$ for all

$x\in \{0,1{\}}^{\ell }$, which we check by evalutating at a random value

$\gamma$,

$\tilde{g}(0,\gamma )={\tilde{g}}_{\ell }(\gamma )$.
The evaluation

${\tilde{g}}_{\ell }(\gamma )$ is computed using the GKR protocol, by reducing it to a sumcheck argument and an evaluation of

${\tilde{g}}_{\ell +1}$, and so on until an evaluation of

${\tilde{g}}_v=\tilde{f}$.

Costs

• Prover:
  $O(2^{\ell })$ for Quarks +
  $O(\sum _{k=\ell +1}^v{2}^k)$ for GKR, so
  $O(n)$ in total, plus commitments to
  $f$ of size
  $n$ and
  $g$ of size
  $2^{\ell +1}$.
• Verifier:
  $O(\ell )$ for Quarks +
  $O(\sum _{k=\ell +1}^{v}k)=O((v-\ell )\cdot v)$, so
  $O(\ell +(v-\ell )\cdot v)$ in total, plus cost of evaluation proofs.
• Proof size: Similarly to the verifier costs,
  $O(\ell +(v-\ell )\cdot v)$ in total, plus size of evaluation proofs.

For example, setting

$\ell =v-3\log v$, the proof size is

$O(v-3\log v+3v\log v)=O(3v\log v)$ which is better than the proof size of

$O(v^2)$ when using only GKR for large enough

$v$. This comes at the cost of commiting to

$g$ of size

$2^{v-3\log v+1}=\frac{2n}{v^3}$, which is much smaller than

$2n$, the corresponding size of

$g$ when using only Quarks.

---

1. https://eprint.iacr.org/2019/953 ↩︎

2. https://eprint.iacr.org/2013/351 ↩︎

3. https://eprint.iacr.org/2020/1275 ↩︎ ↩︎

4. https://eprint.iacr.org/2023/1216 ↩︎