# The cq protocol

This is note for personal consumption, outlining the cq protocol for a rust implementation, this not is meant to be a one place resource describing all relevant details need for the cq protocol.

Of course. Here is a comprehensive breakdown of the variables and symbols used in the cq protocol:

### **General Symbols**

* **F**: A prime field of super-polynomial size.
* **$g_{1}, g_{2}$**: Uniformly chosen generators for the groups $\mathbb{G}_{1}$ and $\mathbb{G}_{2}$.
* **e**: An efficiently computable non-degenerate pairing $e: \mathbb{G}_{1} \times \mathbb{G}_{2} \rightarrow \mathbb{G}_{t}$.
* **P**: The prover in the interactive protocol.
* **V**: The verifier in the interactive protocol.
* **$[a]$**: Represents the integer set {1, ..., a}.
* **$O(n \log n)$**: A representation of the asymptotic prover performance in field operations, indicating the protocol's efficiency.

### **`gen(N, t)` function**

* **N**: The size of the table **t** and the order of the multiplicative subgroup $\mathbb{V}$.
* **t**: A table of predefined legal values of size **N**.
* **x**: A random element chosen from the field **F**.
* **$\{[x^i]_1\}_{i\in\{0,...,N-1\}}$**: A structured reference string (SRS) of monomial in $\mathbb{G}_{1}$.
* **$\{[x^i]_2\}_{i\in\{0,...,N\}}$**: A structured reference string (SRS) of monomial in $\mathbb{G}_{2}$.
* **$\mathbb{V}$**: A multiplicative subgroup of **F** of order **N**.
* **$Z_{\mathbb{V}}(X)$**: A polynomial that has roots at all elements of the subgroup $\mathbb{V}$.
* **T(X)**: A polynomial that encodes the values of the table **t** on the subgroup $\mathbb{V}$.
* **$L_i(X)$**: The i-th Lagrange basis polynomial for the subgroup $\mathbb{V}$.
* **$q_i$**: The commitment to the quotient polynomial $Q_i(X)$.
* **$Q_i(X)$**: The quotient polynomial from the division of $L_i(X) \cdot T(X) - t_i \cdot L_i(X)$ by $Z_{\mathbb{V}}(X)$.

### **`IsInTable(cm, t,srs, H; f)` function**

#### **Round 1: Committing to the multiplicities vector**

* **cm**: The commitment to the polynomial **f(X)**.
* **srs**: The structured reference string generated by **gen(N, t)**.
* **$\mathbb{H}$**: A multiplicative subgroup of **F** of size **n**.
* **f(X)**: A committed polynomial whose values are being checked against the table **t**.
* **n**: The size of the witness and the order of the subgroup $\mathbb{H}$.
* **m(X)**: A polynomial where each coefficient **$m_i$** represents the number of times the table value **$t_i$** appears in the values of **f(X)** on the subgroup $\mathbb{H}$.
* **m**: The commitment to the multiplicity polynomial **m(X)**.

---
#### **Round 2: Interpolating the rational identity at a random $\beta$**

* **$\beta$**: A random value from the field **F** chosen by the verifier.
* **A(X)**: A polynomial whose coefficients **$A_i$** are computed as **$m_i / (t_i + \beta)$**.
* **a**: The commitment to the polynomial **A(X)**.
* **$Q_A(X)$**: The quotient polynomial from the division of **$A(X)(T(X) + \beta) - m(X)$** by **$Z_{\mathbb{V}}(X)$**.
* **$q_a$**: The commitment to the quotient polynomial **$Q_A(X)$**.
* **B(X)**: A polynomial where coefficients **$B_i$** are **$1 / (f_i + \beta)$** for values of **f** on the subgroup $\mathbb{H}$.
* **$B_0(X)$**: The opening proof polynomial for **B(X)** at 0, defined as **$(B(X) - B(0)) / X$**.
* **$b_0$**: The commitment to the polynomial **$B_0(X)$**.
* **$Q_B(X)$**: The quotient polynomial from the division of **$B(X)(f(X) + \beta) - 1$** by **$Z_{\mathbb{H}}(X)$**.
* **$q_b$**: The commitment to the quotient polynomial **$Q_B(X)$**.
* **P(X)**: A polynomial defined as **$B_0(X) \cdot X^{N-1-(n-2)}$**, used for a degree check.
* **p**: The commitment to the polynomial **P(X)**.

---
#### **Round 3: Checking correctness of B at random $\gamma$**

* **$\gamma$**: A random value from the field **F** chosen by the verifier.
* **$b_{0, \gamma}$**: The evaluation of the polynomial **$B_0(X)$** at **$\gamma$**.
* **$f_{\gamma}$**: The evaluation of the polynomial **f(X)** at **$\gamma$**.
* **$a_0$**: The evaluation of the polynomial **A(X)** at 0.
* **$b_{\gamma}$**: The reconstructed evaluation of **B(X)** at **$\gamma$**.
* **$Q_{b, \gamma}$**: The reconstructed evaluation of **$Q_B(X)$** at **$\gamma$**.
* **$\eta$**: A random value from the field **F** used for batching KZG checks.
* **v**: A value used in the batched KZG check, combining several polynomial evaluations.
* **h(X)**: A polynomial constructed for the batched KZG proof.
* **$\pi_{\gamma}$**: The commitment to the polynomial **h(X)**.
* **c**: A commitment used by the verifier in the final KZG check, combining several other commitments.
* **$A_0(X)$**: The opening proof polynomial for **A(X)** at 0, defined as **$(A(X) - a_0) / X$**.
* **$a_0$**: The commitment to the polynomial **$A_0(X)$**.

## PROTOCOL

### `gen(N, t)`:
1. Choose random $x \in \mathbb{F}$ compute and output $\{[x^i]_1\}_{i\in\{0,...,N-1\}}, \{[x^i]_2\}_{i\in\{0,...,N\}}$.
2. Compute and output $[Z_{\mathbb{V}}(x)]_2$.
3. Compute $T(X) = \sum_{i\in[N]} t_i L_i(X)$. Compute and output $[T(x)]_2$.
4. For $i \in [N]$, compute and output:
(a) $q_i = [Q_i(x)]_1$ such that
$$L_i(X) \cdot T(X) = t_i \cdot L_i(X) + Z_{\mathbb{V}}(X) \cdot Q_i(X).$$
(b) $[L_i(x)]_1$.
(c.) $[\frac{L_i(x)-L_i(0)}{x}]_1$.

> Before describing `IsInTable`, we explain an optimization we use in Step 6 of Round 2. Since we know in advance we are going to open B at zero, it is more efficient to commit to the opening proof polynomial $B_0(X) := \frac{B(X)-B(0)}{X}$ of B at 0 instead of committing to B. To evaluate B, V can use the relation $B(X) = B_0(X) \cdot X + b_0$.
>
> We note that it’s possible to make a similar optimization for A to further reduce proof size and prover time. However, this entails an additional verifier pairing for the check in Step 11 of Round 2.

---

### `IsInTable(cm, t, srs, H; f)`:

#### Round 1: Committing to the multiplicities vector
1. **P** computes the polynomial $m(X) \in \mathbb{F}_{<N}[X]$ defined by setting[^1] $m_i$, for each $i \in [N]$, to the number of times $t_i$ appears in $f|_{\mathbb{H}}$.
2. **P** sends $m := [m(x)]_1$.

#### Round 2: Interpolating the rational identity at a random $\beta$; checking correctness of A’s values + degree check for B using pairings
1. **V** chooses and sends random $\beta \in \mathbb{F}$.
2. **P** computes $A \in \mathbb{F}_{<N}[X]$ such that for $i \in [N]$, $A_i = m_i/(t_i + \beta)$.
3. **P** computes and sends $a := [A(x)]_1$.
4. **P** computes and sends $q_a := [Q_A(x)]_1$ where $Q_A \in \mathbb{F}_{<N}[X]$ is such that
$$A(X)(T(X) + \beta) - m(X) = Q_A(X) \cdot Z_{\mathbb{V}}(X)$$
5. **P** computes $B(X) \in \mathbb{F}_{<n}[X]$ such that for $i \in [n]$, $B_i = 1/(f_i + \beta)$.
6. **P** computes $B_0(X) \in \mathbb{F}_{<n-1}[X]$ defined as $B_0(X) := \frac{B(X)-B(0)}{X}$.
7. **P** computes and sends $b_0 := [B_0(x)]_1$.
8. **P** computes $Q_B(X)$ such that
$$B(X)(f(X) + \beta) - 1 = Q_B(X) \cdot Z_{\mathbb{H}}(X).$$
9. **P** computes and sends $q_b := [Q_B(x)]_1$.
10. **P** computes and sends $p = [P(x)]_1$ where
$$P(X) := B_0(X) \cdot X^{N-1-(n-2)}.$$
11. **V** checks that A encodes the correct values:
$$e(a, [T(x)]_2) = e(q_a, [Z_{\mathbb{V}}(x)]_2) \cdot e(m - \beta \cdot a, [1]_2)$$
12. **V** checks that $B_0$ has the appropriate degree:
$$e(b_0, [x^{N-1-(n-2)}]_2) = e(p, [1]_2).$$

#### Round 3: Checking correctness of B at random $\gamma \in \mathbb{F}$
1. **V** sends random $\gamma \in \mathbb{F}$.
2. **P** sends $b_{0,\gamma} := B_0(\gamma)$, $f_\gamma := f(\gamma)$.
3. **P** computes and sends the value $a_0 := A(0)$.
4. **V** sets $b_0 := (N \cdot a_0)/n$.
5. As part of checking the correctness of B, **V** computes $Z_{\mathbb{H}}(\gamma) = \gamma^n - 1$, $b_\gamma := b_{0,\gamma} \cdot \gamma + b_0$ and
$$Q_{b,\gamma} := \frac{b_\gamma \cdot (f_\gamma + \beta) - 1}{Z_{\mathbb{H}}(\gamma)}.$$
6. To perform a batched KZG check for the correctness of the values $b_{0,\gamma}, f_\gamma, Q_{b,\gamma}$:
(a) **V** sends random $\eta \in \mathbb{F}$. **P** and **V** separately compute
$$v := b_{0,\gamma} + \eta \cdot f_\gamma + \eta^2 \cdot Q_{b,\gamma}.$$
(b) **P** computes $\pi_\gamma := [h(x)]_1$ for
$$h(X) := \frac{B_0(X) + \eta \cdot f(X) + \eta^2 \cdot Q_B(X) - v}{X - \gamma}$$
(c.) **V** computes
$$c := b_0 + \eta \cdot cm + \eta^2 \cdot q_b$$
and checks that
$$e(c - [v]_1 + \gamma \cdot \pi_\gamma, [1]_2) = e(\pi_\gamma, [x]_2).$$
7. To perform a KZG check for the correctness of $a_0$:
(a) **P** computes and sends $a_0 := [A_0(x)]_1$ for
$$A_0(X) := \frac{A(X) - a_0}{X}$$
(b) **V** checks that
$$e(a - [a_0]_1, [1]_2) = e(a_0, [x]_2).$$

### Analysis

> Note that although the above description contains nine pairings, we can reduce to five pairings via the standard technique of combining several pairings equations into one pairing product via randomness, and then grouping pairings that share the same $\mathbb{G}_2$ argument. (The different $\mathbb{G}_2$ arguments are $[1]_2, [x]_2, [x^{N-1-(n-2)}]_2, [Z_V(x)]_2, [T(x)]_2$.)

It is easy to check that `cq` is homomorphic according to Definition 4.1. The main things to address are the efficiency of the `gen` algorithm used for preprocessing, the efficiency of **P** in `IsInTable`, and the knowledge soundness of `IsInTable`.

#### Runtime of `gen`
We claim that `gen` requires $O(N \log N)$ $\mathbb{G}_1$- and $\mathbb{F}$-operations and $O(N)$ $\mathbb{G}_2$-operations. The claim regarding the $\mathbb{G}_2$ operations is obvious. The elements $\{q_i\}$ can be computed in $O(N \log N)$ operations according to Lemma 3.1. The elements $\{[L_i(x)]_1\}$ can be computed in $O(N \log N)$ via FFT as explained in Section 3.3 of [BGG17]. Given the element $[L_i(x)]_1$, the element $[\frac{L_i(x)-L_i(0)}{x}]_1$ can be computed as
$$[\frac{L_i(x)-L_i(0)}{x}]_1 = g^{-i} \cdot [L_i(x)]_1 - (1/N) \cdot [x^{N-1}]_1.$$

#### Runtime of P
Note first that the computation of `m`, `a` can be done in $n$ $\mathbb{G}_1$-operations as $m(X)$ and $A(X)$ are $n$-sparse. The main thing to address is the computation of $q_a$; that can be done in $n$ $\mathbb{G}_1$-operations given `srs` according to Theorem 3.2. The only step requiring $O(n \log n)$ $\mathbb{F}$-operations is the computation of the quotient $Q_B(X)$ which involves FFT on $\mathbb{H}$. We also note that the commitment $a_0 = [\frac{A(x)-A(0)}{x}]_1$ can be computed in $n$ $\mathbb{G}_1$-operations as the linear combination
$$[\frac{A(x)-A(0)}{x}]_1 = \sum_{i\in\text{supp}(A)} A_i \cdot [\frac{L_i(x)-L_i(0)}{x}]_1.$$

#### Knowledge soundness proof
Let A be an efficient algebraic adversary participating in the Knowledge Soundness game from Definition 4.1. We show its probability of winning the game is $negl(\lambda)$. Let $f \in \mathbb{F}_{<N}[X]$ be the polynomial sent by A in the third step of the game such that $cm = [f(x)]_1$. As A is algebraic, when sending the commitments $m,a,b_0,p,q_a,q_b,\pi_\gamma,a_0$ during protocol execution it also sends polynomials $m(X), A(X), B_0(X), P(X), Q_A(X), Q_B(X), h(X), A_0(X) \in \mathbb{F}_{<N}[X]$ such that the former are their corresponding commitments. Let E be the event that V outputs acc. Note that the event that A wins the knowledge soundness game is contained in E. E implies all pairing checks have passed. Let $A \subset E$ be the event that one of the corresponding ideal pairing checks as defined in Section 2.2 didn’t pass. According to Lemma 2.3, $Pr(A) = negl(\lambda)$. Given that A didn’t occur, we have:

- From Round 2, Step 11:
$$A(X)(T(X) + \beta) - M(X) = Q_A(X) \cdot Z_{\mathbb{V}}(X)$$
Which means that for all $i \in [N]$,
$$A_i = \frac{M_i}{T_i + \beta}$$

- From Round 2, Step 12:
$$X^{N-1-(n-2)}B_0(X) = P(X),$$
which implies that $deg(B_0) \le n - 2$. Note also that we know $deg(A) < N$ simply from $[x^{N-1}]_1$ being the highest $\mathbb{G}_1$ power in srs.[^2]

- Moving to Round 3, from the checks of steps 6c and 7b, e.w.p. $n/|\mathbb{F}|$ over $\eta \in \mathbb{F}$ (see e.g. Section 3 of [GWC19] for an explanation of batched KZG [KZG10]), we have $b_{0,\gamma} = B_0(\gamma), Q_{b,\gamma} = Q_B(\gamma), f_\gamma = f(\gamma), a_0 = A(0)$.

- Define $B(X) := B_0(X)\cdot X+b_0$ for $b_0$ set as in step 4. Note that we have $deg(B) < n$. Let $\omega$ by a generator of $\mathbb{H}$.

- By how $b_\gamma, Q_{b,\gamma}$ are set in step 5, the above implies that e.w.p. $(N + n)/|\mathbb{F}|$ over $\gamma$:
$$B(X) \cdot (f(X) + \beta) = 1 + Q_B(X)Z_{\mathbb{H}}(X),$$
which implies for all $i \in [n]$ that $B(\omega^i) = \frac{1}{f(\omega^i)+\beta}$.

- We now have using Lemma 2.1 that:
$$N \cdot a_0 = \sum_{i\in[N]} A_i = \sum_{i\in[N]} \frac{m_i}{T_i + \beta},$$
$$n \cdot b_0 = \sum_{i\in[n]} B(\omega^i) = \sum_{i\in[n]} \frac{1}{f(\omega^i) + \beta}.$$
Recall that $b_0$ was set such that $N \cdot a_0 = n \cdot b_0$. Multiplying denominators, we see that e.w.p. $(n + N)/|\mathbb{F}|$ over $\beta \in \mathbb{F}$, we have
$$\sum_{i\in[N]} \frac{m_i}{T_i + X} = \sum_{i\in[n]} \frac{1}{f(\omega^i) + X},$$
which implies $f|_{\mathbb{H}} \subset t$ by Lemma 2.4.

In summary, we have shown the event that V outputs acc while $f|_{\mathbb{H}} \not\subset t$ is contained in a constant number of events with probability $negl(\lambda)$; and so `cq` satisfies the knowledge soundness property.

[^1]: We assume here that t’s values are distinct. If there are duplicate values in t, one must rather set $m_i = 0$ for the indices i of the duplicates.
[^2]: An important point is that when using an SRS built with higher degrees in $\mathbb{G}_1$, A must also be degree checked via an additional pairing. In such a case, we must also change the power of X in Step 12 of Round 2 from $N - 1 - (n - 2)$ to $d - (n - 2)$ where d is the maximal SRS degree in $\mathbb{G}_1$.

### References
https://www.zkm.io/blog/lookup-argument-logup-and-code-analysis