# Ligerito-by-hand

## Structure

1. Why inner product? How is inner product equivalent to a polynomial evaluation?
2. Can we just run one big sumcheck to evaluate the inner product? What would be the disadvantage?
3. How is Ligerito improving on that (on a very high level, because the detailed explanation will follow)?
4. Explain multilinear evaluation, the equivalenece of a vector-vector product and matrix-vector product to a full and partial evaluation ($vr$ vs $Mat(v)r$)
5. Matrix-Vector product protocol
6. Partial sumcheck protocol
7. Batching and Gluing
8. Matrix-vector product with partial sumcheck
9. Full Ligerito protocol

- In each mini-protocol or the main protocol, define the following:
- Verifier expectations
- Why in the end the verifier is convinced by the prover that the statement is true?

## Goal

- Cover the middle ground between the paper (https://angeris.github.io/papers/ligerito.pdf) and the implementation (https://github.com/bcc-research/Ligerito.jl)

## Best "By-hand" writeups

- https://research.metastate.dev/plonk-by-hand-part-1/
- https://arnaucube.com/blog/ipa.html
- https://risencrypto.github.io/Sumcheck/?extension-polynomials-and-multilinear-extensions - good example, can take the same approach of pointing to the Julia code
- https://medium.com/%40laurippeltonen/sumcheck-protocol-for-iq-200-d95a49bd3b9a
- https://blog.electisec.com/sumcheck
- https://anoma.net/research/superspartan-by-hand
- https://anoma.net/research/hypernova-by-hand

---

## Equivalence Between Vector-Vector Product and Multilinear Polynomial Evaluation

A general definition of a multilinear polynomial (e.g., [on Wikipedia](https://en.wikipedia.org/wiki/Multilinear_polynomial)) is given in the coefficient form and is useful to understand why the polynomial is linear in each variable. However, it is not very practical to use in zero-knowledge proofs. Usually we are rather interested in encoding a set of values as a polynomial (which happens to be multilinear in case of Ligerito). Let's see how we can define a multilinear polynomial in such a way that it evaluates to a set of our desired values $v_x$ on our desired set of points $x$. A practical set of points for our purposes would be the vertices of a boolean $k$-dimensional hypercube, so that $x\in\{0,1\}^k$. This literally means that each $x$ value is a length-$k$ binary vector. For example, if $k=2$, then the 4 possible values of $x$ (in lex order) are $\{00,01,10,11\}$. With that in mind, look at the following formula for a multilinear polynomial:

$$
v(z_1,\dots,z_k)
\;=\;
\sum_{x\in\{0,1\}^k} v_x\,\prod_{i=1}^k (1 - z_i)^{1-x_i} z_i^{x_i}
$$

For example, for $k=2$, the formula

$$
v(z_1,z_2)
=\sum_{(x_1,x_2)\in\{0,1\}^2}v_{x_1x_2}\,(1-z_1)^{1-x_1}z_1^{x_1}\,(1-z_2)^{1-x_2}z_2^{x_2}
$$

expands to the four terms

$$
\begin{aligned}
v(z_1,z_2)
={}&v_{00}\,(1-z_1)(1-z_2)\\
+&v_{10}\;z_1\,(1-z_2)\\
+&v_{01}\;(1-z_1)\,z_2\\
+&v_{11}\;z_1\,z_2\,.
\end{aligned}
$$

Now imagine that we have a set of values

$$
v_{00}=1,\quad v_{10}=2,\quad v_{01}=3,\quad v_{11}=4,
$$

that we want to encode as a 2-variable multilinear polynomial. Then

$$
v(z_1,z_2)
=1\cdot(1-z_1)(1-z_2)
+2\cdot z_1(1-z_2)
+3\cdot(1-z_1)z_2
+4\cdot z_1z_2,
$$
and if we evaluate this polynomial on a vertex of the hypercube, we get the corresponding evaluation:

$$
v(1,0)
=1\cdot(1-1)(1-0)
+2\cdot 1(1-0)
+3\cdot(1-1)0
+4\cdot 1 \cdot 0=
\\
2=v_{10}
$$

Therefore, we have demonstrated how a vector $v$ can be viewed as a function $v(z_1,\dots,z_k)$ that evaluates to vector elements at the desired points.

We can rewrite our 2-variable example as follows:

$$
\begin{pmatrix}v_{00}\,v_{01}\,v_{10}\,v_{11}\end{pmatrix}\cdot
\begin{pmatrix}
(1-z_1)(1-z_2)\\
(1-z_1)\,z_2\\
z_1\,(1-z_2)\\
z_1\,z_2
\end{pmatrix}=
v\cdot
\begin{pmatrix}
(1-z_1)(1-z_2)\\
(1-z_1)\,z_2\\
z_1\,(1-z_2)\\
z_1\,z_2
\end{pmatrix}
$$
As we can see, the second factor is a vector of products of all possible combinations of either $z_i$ or its "boolean inverse", $1-z_i$ (keep in mind, though, that the variables are not restricted to boolean values only). The paper introduces a very handy "barred" notation for this kind of vector to make it even more compact:

$$
\bar z
=\begin{pmatrix}
(1-z_1)(1-z_2)\\
(1-z_1)\,z_2\\
z_1\,(1-z_2)\\
z_1\,z_2
\end{pmatrix}
=\;(1-z_1,\,z_1)\;\otimes\;(1-z_2,\,z_2),
$$
or, more generally, for $k$ variables:

$$
\bar z \;=\;(1 - z_1,\,z_1)\;\otimes\;(1 - z_2,\,z_2)\;\otimes\;\cdots\;\otimes\;(1 - z_k,\,z_k)\;\in\;\Bbb F^{2^k},
$$

where $\otimes$ is a Kronecker product. This notation helps us rewriting our multilinear polynomial $v(z_1,\dots,z_k)$ simply as $v \bar z$.

## Equivalence Between Matrix-Vector Product and Partial Multilinear Polynomial Evaluation

An important tool of Ligerito is a partial evaluation that means evaluating the original multilinear polynomial at the first $k'$ variables, and leaving the remaining $k−k'$ variables free. Let's take a look at the difference between the full and partial evaluation. Let's evaluate a 2-variable polynomial at a random point r:

$$
\begin{equation}
\begin{aligned}
v \, \bar r=
{}&v_{00}\,(1-r_1)(1-r_2)\\
+&v_{10}\;r_1\,(1-r_2)\\
+&v_{01}\;(1-r_1)\,r_2\\
+&v_{11}\;r_1\,r_2\,.
\end{aligned}
\tag{1}
\end{equation}
$$

This is a full evaluation in all $k=2$ variables. Let's take a look at a partial evaluation as introduced in the paper. In our case we would evaluate $v$ in a number of variables $k'<k$, so let's choose $k'=1$. The evaluation point $\bar r$ would look like
$$
\bar r=\begin{pmatrix}
1-r_1 \\
r_1
\end{pmatrix}
$$

The paper suggests that we can achieve a partial evaluation $y$ of $v$ by re-shaping $v$ into a matrix in a "column-major" way and then multiplying by $\bar r$:

$$
y = Mat(v)\bar r =
\begin{pmatrix}
v(0,0) & v(1,0)\\
v(0,1) & v(1,1)
\end{pmatrix}
\bar r =
\begin{pmatrix}
v(0,0) & v(1,0)\\
v(0,1) & v(1,1)
\end{pmatrix}
\begin{pmatrix}
1-r_1\\
r_1
\end{pmatrix}=
$$
$$
=\begin{pmatrix}
(1-r_1)\,v(0,0)+r_1\,v(1,0)\\[6pt]
(1-r_1)\,v(0,1)+r_1\,v(1,1)
\end{pmatrix}=
\begin{pmatrix}
v(r_1,0)\\
v(r_1,1)
\end{pmatrix}.
$$

Let's apply the same trick and "partially evaluate" the result at point $\bar r':$

$$
\bar r'=\begin{pmatrix}
1-r_2 \\
r_2
\end{pmatrix}
,
\quad
y' = y^T\,\bar r'
\;=\;
\begin{pmatrix}y_0 & y_1\end{pmatrix}
\begin{pmatrix}1-r_2\\[4pt]r_2\end{pmatrix}
\;=\;
y_0\,(1-r_2)+y_1\,r_2
\;=\;
$$
$$
\;=\;v(r_1,0)(1-r_2)\;+\;v(r_1,1)\,r_2
$$

Now, if we start from the full expansion $(1)$, and collect the terms involving $(1-r_2)$ and $r_2$ separately, we will get:

$$
\begin{aligned}
v(\,r_1,r_2)
&=v_{00}\,(1-r_1)(1-r_2)
+v_{10}\,r_1\,(1-r_2)
+v_{01}\,(1-r_1)\,r_2
+v_{11}\,r_1\,r_2
\\[6pt]
&=\;
\underbrace{\bigl[v_{00}(1-r_1)+v_{10}r_1\bigr]}_{\displaystyle v(r_1,0)}
\;\cdot\;(1-r_2)
\;+\;
\underbrace{\bigl[v_{01}(1-r_1)+v_{11}r_1\bigr]}_{\displaystyle v(r_1,1)}
\;\cdot\;r_2.
\\
&=\;
y'
\end{aligned}
$$

We're now convinced that the partial evaluation works as intended since we have arrived at the full evaluation by performing the necessary number of consecutive partial evaluations.

## Matrix-Vector Product Protocol

In matrix-vector product protocol the prover is telling verifier:
> "I have committed to some secret matrix $\widetilde X$, and here's its partial evaluation (if viewed as a polynomial) $y_r$ at the point $r$ you have provided."

The prover won't learn the matrix $\widetilde X$, will only provide the evaluation point $r$, but will be convinced with high probability that the evaluation is equal to $y_r$.

The dimensions of $\widetilde X$ should be $n\times n'$ where $n' = 2^k$. This allows us to consider a partial $k$-variate evaluation of $\widetilde X$. Let’s instantiate a toy example of a matrix-vector product protocol with the following parameters: $k = 2,n' = 2^k = 4, n = 2.$

We’ll work through every step of computing

$$
y_r \;=\; \widetilde X\,\bar r
\;\in\;\Bbb F^n.
$$

Let's choose a tiny “secret” matrix $\widetilde X\in\Bbb F^{n\times n'}$

$$
\widetilde X \;=\;
\begin{pmatrix}
1 & 2 & 3 & 4 \\
5 & 6 & 7 & 8
\end{pmatrix}
$$

### Prover
---

### 1. Encode $\widetilde X$ using a linear code

A linear code is a fixed linear mapping (via its generator $G$) that expands each input ($\widetilde X$) into a longer codeword ($X$) so that any two distinct inputs produce codewords differing in at least a prescribed number of positions $d$.
*TODO linear codes are out of scope of the article, but we need to explain how d guarantees the result*
Simply speaking, to encode $\widetilde X$, we need to perform the following matrix multiplication:
$$
X = G \widetilde X
$$

For simplicity we won't calculate a real linear code generator $G$, but let the code generator matrix be

$$
G=\begin{pmatrix}
1 & 2 \\
3 & 4 \\
5 & 6
\end{pmatrix}.
$$

Let's encode the $\widetilde X$ using the code $G$:

$$
X = G \widetilde X = \begin{pmatrix}
1 & 2 \\
3 & 4 \\
5 & 6
\end{pmatrix} \begin{pmatrix}
1 & 2 & 3 & 4 \\[4pt]
5 & 6 & 7 & 8
\end{pmatrix} =
\begin{pmatrix}
1\cdot1+2\cdot5 & 1\cdot2+2\cdot6 & 1\cdot3+2\cdot7 & 1\cdot4+2\cdot8 \\[6pt]
3\cdot1+4\cdot5 & 3\cdot2+4\cdot6 & 3\cdot3+4\cdot7 & 3\cdot4+4\cdot8 \\[6pt]
5\cdot1+6\cdot5 & 5\cdot2+6\cdot6 & 5\cdot3+6\cdot7 & 5\cdot4+6\cdot8
\end{pmatrix} =
$$
$$
=\begin{pmatrix}
11 & 14 & 17 & 20 \\[3pt]
23 & 30 & 37 & 44 \\[3pt]
35 & 46 & 57 & 68
\end{pmatrix}.
$$

### 2. Commit to the rows of $X$

In the real instantiation of Ligerito, the verifier will commit to the rows of $X$ using, for example, a Merkle tree. The commitment is out of scope of this article, so we will just pretend that the plaintext $X$ stays with the prover and the verifier will only have an oracle access to it via commitment openings.

### 3. Receive a random challenge $r$ from verifier

In the real instantiation of Ligerito this step is done using Fiat-Shamir transform. For illustration let’s take $r=(r_1,r_2)\in\Bbb F^2:$

$$
r_1 = 0.1,\quad r_2 = 0.2.
$$

### 4. Compute the partial‐evaluation $y_r = \widetilde X\,\bar r$

We enumerate the four Boolean points $(b_1,b_2)\in\{0,1\}^2$ in lex order:

$$
(0,0),\;(0,1),\;(1,0),\;(1,1).
$$

Then

$$
\bar r = \begin{pmatrix}
(1-r_1)(1-r_2) \\
(1-r_1)\,r_2 \\
r_1\,(1-r_2) \\
r_1\,r_2
\end{pmatrix}=\begin{pmatrix}
0.9\cdot0.8 \\
0.9\cdot0.2 \\
0.1\cdot0.8 \\
0.1\cdot0.2
\end{pmatrix}=\begin{pmatrix}
0.72 \\
0.18 \\
0.08 \\
0.02
\end{pmatrix}.
$$

$$
y_r = \begin{pmatrix}
1 & 2 & 3 & 4 \\
5 & 6 & 7 & 8
\end{pmatrix}\begin{pmatrix}
0.72 \\
0.18 \\
0.08 \\
0.02
\end{pmatrix}=\begin{pmatrix}
1\cdot0.72 \;+\; 2\cdot0.18 \;+\; 3\cdot0.08 \;+\; 4\cdot0.02 \\[6pt]
5\cdot0.72 \;+\; 6\cdot0.18 \;+\; 7\cdot0.08 \;+\; 8\cdot0.02
\end{pmatrix}=\begin{pmatrix}
1.4 \\
5.4
\end{pmatrix}.
$$

At the end of this step prover sends $y_r$ to the verifier.

### Verifier
---

The verifier knows the code $G$ and the commitment to $X$. The verifier then picks a random challenge $\bar r = (0.72,\,0.18,\,0.08,\,0.02)^\top$ and receives the corresponding $y_r = (1.4,\,5.4)^\top$.

### 1. Querying the commitment to $X$

Let's pick a set of rows $S \subseteq \{1,2,3\}$, for example, of size $\lvert S\rvert = 2,$ e.g., $S=\{2,3\}$. For the random challenge $\bar r = (0.72,\,0.18,\,0.08,\,0.02)^\top$ and partial‐evaluation $y_r=(1.40,\,5.40)^\top$, we would have to check rows $2$ and $3$ (*TODO how is this related to the protocol soundness?*).

In the real instantiation of Ligerito, the verifier will only be able to open the commitment to $X$ at the queried points. As we omit the commitment description, let's pretend that for $S=\{2,3\}$ verifier receives opening proofs for values in rows $X_{2,\ast}$ and $X_{3,\ast}$. Let's only check row $2$ for brevity. The left-hand side would be
$$
X_{2,\ast}\,\bar r
=\;(23,\,30,\,37,\,44)
\begin{pmatrix}0.72\\0.18\\0.08\\0.02\end{pmatrix}
=23\cdot0.72+30\cdot0.18+37\cdot0.08+44\cdot0.02
=25.8
$$
Now let's check the right-hand side:
$$
G_{2,\ast}\,y_r
=\;(3,\,4)
\begin{pmatrix}1.4\\5.4\end{pmatrix}
=3\cdot1.4+4\cdot5.4
=25.8.
$$

As we can see, the check has passed! This convinces the verifier in the following:
- the matrix that the prover has committed to has $n$ columns that can be viewed as a degree $<n$ polynomials;
- vector $y_r$ is indeed equal to the product $\widetilde X r$. In other words, prover knows that the verifier has committed to some $\widetilde X$ and the partial evaluation of $\widetilde X$ at point $r$, if viewed a as a polynomial, is equal to $y_r$, all of that without knowing anything about $\widetilde X$ and working only with the commitment to the codeword $X$.

Since the $X$ is committed, and $G$ is known to the verifier, a dishonest prover could try to cheat after receiving the challenges $r$ by tweaking the $y_r$, but the same $y_r$ would be used in $i$ row checks $G_{i,\ast}\,y_r$. It would be practically impossible for all $i$ checks to pass because the prover doesn't know in advance which set of rows $S$ would the verifier pick to check.

## Partial Sumcheck Protocol

### High level protocol

The sumcheck is well-known interactive protocol for computing an inner product between two vectors.

Standard sumcheck protocol is for computing an function evaluation on boolean hypercube.
$$
H = \sum_{x_1 \in \{0,1\}} \sum_{x_2 \in \{0,1\}} \cdots \sum_{x_v \in \{0,1\}} f(x_1, \ldots, x_v)
$$

- Verifier expectations
In the sumcheck, the verifier wants to check if the "claimed" value $H$ is the correct sum of multivariable function $f(x_1, ..., x_v)$ evaluations in certain domain(e.g., Hypercube).
- Why in the end the verifier is convinced by the prover that the statement is true?
In the end of protocol, the verifier is convinced by interactive check. She already knows the multivariate polynomial/function(specifically, the coefficients). She gets the one-variable polynomial from prover, step by step, from claimed value $H$, downward. Every step, the verifier checks the sum. At the end, the verifier does one final computaion - evaluation of multivariable function in random point $r=\{r_1, r_2, ..., r_v\}$. The verifier then compares this evaluation with prover-given polynomial evaluation. If match, she confirms that $H$ is correct sum.

(We can learn more about the standard sumcheck protocol in this article - ["Sumcheck protocol for IQ < 200"](https://medium.com/%40laurippeltonen/sumcheck-protocol-for-iq-200-d95a49bd3b9a).)

Given some known vector $w \in F^{2^k}$, which we interpret as an $k$ variable multilinear polynomial, and some claimed inner product $\alpha \in F$, the sumcheck protocol is an interactive protocol for reducing a claims of the form

$$
\sum_{z \in \{0,1\}^k} w(z) \tilde{X}(z) = \alpha
$$

to a claim of the form
$$
\sum_{z' \in \{0,1\}^{k'}} w(r, z') \tilde{X}(r, z') = \alpha'
$$

For some $\alpha'$, randomness $r$ which we specify next, and $k' < k$. (In other words, we reduce the sum over $k$ variables to a sum over $k'$ variables and some partial evaluations of $w$ and $\tilde{X}$.)

**Example**:
Standard sumcheck includes $k = 2$ variables - $z_1$, $z_2$

$$
\begin{aligned}
w(z) &= 1 + z_1 + z_2 \\
\tilde{X}(z) &= 1 + 2z_1 + 3z_2
\end{aligned}
$$

$$
\begin{aligned}
w(z)\tilde{X}(z) = (1 + z_1 + z_2)(1 + 2z_1 + 3z_2) \\
= 1 + 3z_1 + 4z_2 + 5z_1z_2 + 2z_1^2 + 3z_2^2
\end{aligned}
$$

$$
\begin{aligned}
\sum_{z \in \{0,1\}^2} w(z) \tilde{X}(z) &= w(0, 0)\tilde{X}(0,0) + w(0, 1)\tilde{X}(0, 1) + w(1, 0)\tilde{X}(1, 0) + w(1, 1)\tilde{X}(1, 1) \\
&= 1*1 + 2*4 + 2*3 + 3*6 \\
&= 1 + 8 + 6 + 18 \\
&= 33
\end{aligned}
$$

After we set $k'=1$, we apply randomness $r=3$ to $z_1$, and reduce the sumcheck to **one** variable - $z_2$.

$$
k' = 1, r = 3
$$

$$
w(r, z') = 1 + 3 + z_2 = 4 + z_2
$$

$$
\begin{aligned}
\tilde{X}(r, z') &= 1 + 2z_1 + 3z_2 \\
&= 1 + 8 + 3z_2 \\
&= 9 + 3z_2
\end{aligned}
$$

$$
\begin{aligned}
w(r, z')\tilde{X}(r, z') &= w(3, z_2)\tilde{X}(3, z_2) \\
&= (4 + z_2)(9 + 3z_2) \\
&= 36 + 21z_2 + 3z_2^2
\end{aligned}
$$

$$
\sum_{z' \in \{0,1\}^1} w(r, z') \tilde{X}(r, z') = \sum_{z_2 \in \{0,1\}} w(3, z_2) \tilde{X}(3, z_2) = 96
$$

Here, we can say that we have reduced an original problem of proving that the sum over hypercube of a **2-variable polynomial** is equal to **33** to a new problem where the sum of a **1-variable polynomial** is equal to **96**.
(End of example)

Another way to view sumcheck equation and the protocol is that we begin with an inner product between $\tilde{X}$ and the vector $w$,
$$
w^T \, \mathrm{vec}(\tilde{X}) = \alpha
$$

**Example**:
Following equations show the evaluations of the multilinear polynomial $v$ and $\tilde{X}$, at $z \in F^k$
$$v(z) = v^T \bar{z} = v^T ((1-z_1, z_1) \otimes ... \otimes (1-z_k, z_k) )$$

$$\tilde{X}(z)=(\mathrm vec(\tilde{X}))(z)$$

Let's assume $k = 2$,
$$
w(z)=1 + z_1 + z_2,
(w = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 0 \end{bmatrix})
$$

$$
\tilde{X}(z)=1 + z_1 + z_2 + z_1z_2,
(\mathrm vec{(\tilde{X})}=\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix})
$$

Then,
$$
\begin{aligned}
\sum_{z \in \{0,1\}^2} w(z) \tilde{X}(z) = w(0, 0)\tilde{X}(0, 0) + w(0, 1)\tilde{X}(0, 1) + \\
w(1, 0)\tilde{X}(1, 0) + w(1, 1)\tilde{X}(1, 1)
\end{aligned}
$$

First: $z = [0, 0]$

$$
\bar{z} = (1 - 0, 0) \otimes (1 - 0, 0) = (1, 0) \otimes (1, 0) = (1 * 1, 1 * 0, 0 * 1, 0 * 0) = (1, 0, 0, 0)
$$

$$
w(z) = w^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix}1 \\ 0 \\ 0 \\ 0 \end{bmatrix} = 1
$$

$$
(\mathrm vec({\tilde{X}
}))(z) = (\mathrm vec({\tilde{X}}))^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix}1 \\ 0 \\ 0 \\ 0 \end{bmatrix} = 1
$$

Next: $z = [0, 1]$

$$
\bar{z} = (1 - 0, 0) \otimes (1 - 1, 1) = (1, 0) \otimes (0, 1) = (1 * 0, 1 * 1, 0 * 0, 0 * 1) = (0, 1, 0, 0)
$$

$$
w(z) = w^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix}0 \\ 1 \\ 0 \\ 0 \end{bmatrix} = 1
$$

$$
(\mathrm vec({\tilde{X}
}))(z) = (\mathrm vec({\tilde{X}}))^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix}0 \\ 1 \\ 0 \\ 0 \end{bmatrix} = 1
$$

Next: $z = [1, 0]$

$$
\bar{z} = (1 - 1, 1) \otimes (1 - 0, 0) = (0, 1) \otimes (1, 0) = (0 * 1, 0 * 0, 1 * 1, 1 * 0) = (0, 0, 1, 0)
$$

$$
w(z) = w^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix}0 \\ 0 \\ 1 \\ 0 \end{bmatrix} = 1
$$

$$
(\mathrm vec({\tilde{X}
}))(z) = (\mathrm vec({\tilde{X}}))^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix}0 \\ 0 \\ 1 \\ 0 \end{bmatrix} = 1
$$

Next: $z = [1, 1]$

$$
\bar{z} = (1 - 1, 1) \otimes (1 - 1, 1) = (0, 1) \otimes (0, 1) = (0 * 0, 0 * 1, 1 * 0, 1 * 1) = (0, 0, 0, 1)
$$

$$
w(z) = w^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix}0 \\ 0 \\ 0 \\ 1 \end{bmatrix} = 0
$$

$$
(\mathrm vec({\tilde{X}
}))(z) = (\mathrm vec({\tilde{X}}))^T \bar{z} = \begin{bmatrix} 1 & 1 & 1 & 1 \end{bmatrix} \begin{bmatrix}0 \\ 0 \\ 0 \\ 1 \end{bmatrix} = 1
$$

Hence:
$$ \sum_{z \in \{0,1\}^2} w(z) \tilde{X}(z) = 1 * 1 + 1 * 1 + 1 * 1 + 0 * 1 = 3 $$

$$ w^T \mathrm vec({\tilde{X})} = \begin{bmatrix} 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = 3 $$
(End of example)

Above equation can be reduced to a new inner product between the partial evaluations
$$
(\mathrm{Mat}(w)\bar{r})^T(\tilde{X}\bar{r})=\alpha'
$$
where $\mathrm Mat(w)$ is the reshaping of 𝑤 to the appropriate dimensions. We will make use of this particular observation later in the note.

### Partial sumcheck protocol

As before, we will describe the prover and verifier algorithms separately. In this construction,
we will reduce the original sum over $n$ variables to a sum over $n'$ variables.

#### Prover
1. For $i = 1, ... , k - k'$
1. Send the polynomial $s_i(t) = \sum_{z \in \{0,1\}^(k-i)} w(r_1, ..., r_{i-1}, t, z) \tilde{X}(r_1, ..., r_{i-1}, t, z)$
2. Receive a random challenge $r_i \in F$, to be used in next round

#### Verifier
1. Set $s_0 = \alpha$ to be a constant polynomial and $r_0=0$ for convenience
2. For each of $i=1, ... , k-k'$:
1. Send some uniformly sampled $r_{i-1} \in F$
2. Receive some degree 2 polynomial $s_i : F \to F$
3. Verify that $s_i(0) + s_i(1) = s_{i-1}(r_{i-1})$

If all verificaions pass, the verifier accepts the proof. Otherwise, it rejects. Note that the verifier does not need to know neither $w$ nor $\tilde{X}$ to run this algorithm.

**Example**:
$$
\begin{aligned}
k &= 3, k'=1 \\
w(z) &= 1 + z_1 + z_2 + z_3 \\
\mathrm vec(\tilde{X}) &= 1 + 2z_1 + 3z_2 + 2z_3
\end{aligned}
$$
Here, total claimed sum $\alpha=104$.

- $i = 1$
**Prover** sends the poly $s_1(t) = \sum_{z \in \{0, 1\}^2}w(t, z)\tilde{X}(t, z)$

$$
\begin{aligned}
s_1(t)&=\sum_{z_2, z_3 \in \{0, 1\}^2}w(t, z_2, z_3)\tilde{X}(t, z_2, z_3) \\
&= w(t, 0, 0)\tilde{X}(t, 0, 0) + w(t, 0, 1)\tilde{X}(t, 0, 1) + w(t, 1, 0)\tilde{X}(t, 1, 0) + w(t, 1, 1)\tilde{X}(t, 1, 1) \\
&= (1+t)(1+2t) + (1+t+1)(1+2t+2) + (1+t+1)(1+2t+3) + (1+t+2)(1+2t+5) \\
&=1+3t+2t^2+(6+7t+2t^2)+(8+8t+2t^2)+(18+12t+2t^2) \\
&=33+30t+8t^2
\end{aligned}
$$

**Verifier** set $s_0=\alpha=104$ & $r_0=0$ for convenience.
**Verifier** uniformly sample $r_i \in F$ and send it; she sends $r_1=2$.
**Verifier** receives $s_1: F \to F$; $s_1=33+40t+8t^2$
**Verifier** verifies that $s_i(0) + s_i(1) = s_{i-1}(r_{i-1})$
$$s_1(0) + s_1(1) = 33 + 33 + 30 *1 + 8 * 1^2 = 104 = s_0$$

- $i=k-k'= 3 - 1=2$
**Prover** received $r_1=2$.
**Prover** sends the poly $s_2(t)=\sum_{z \in \{0, 1\}^1}w(r_1, t, z)\tilde{X}(r_1, t, z)$

$$
\begin{aligned}
s_2(t)&=\sum_{z \in \{0, 1\}^1}w(r_1, t, z)\tilde{X}(r_1, t, z)\\
&=\sum_{z_3 \in \{0, 1\}^1}w(r_1, t, z_3)\tilde{X}(r_1, t, z_3)\\
&=w(r_1, t, 0)\tilde{X}(r_1,t, 0) + w(r_1, t, 1)\tilde{X}(r_1,t,1)\\
&=(1+r_1+t+0)(1+2r_1+3t+0) + (1+r_1+t+1)(1+2r_1+3t+2*1)\\
&=(1+r_1+t)(1+2r_1+3t) + (2+r_1+t)(3+2r_1+3t)\\
&=(1+2+t)(1+2*2+3t) + (2+2+t)(3+2*2+3t)\\
&=(3+t)(5+3t) + (4+t)(7+3t)\\
&=15+14t+3t^2+28+19t+3t^2\\
&=43+33t+6t^2
\end{aligned}
$$

**Verifier** send some uniformly sampled $r_2 \in F$; No need for that.
**Verifier** receives $s_2=43+33t+6t^2$
**Verifier** verifies that $s_i(0) + s_i(1) = s_{i-1}(r_{i-1})$
$$s_2(0) + s_2(1) = 43+43+33+6 = 125$$
$$s_1(r_1) = 33 + 30 * 2 + 8 * 2^2=125$$
So, $s_2(0) + s_2(1) = s_1(r_1)$

Verification SUCCESS!

One note: The **Verifier** can compute this one - $\alpha'$, by herself.
$$\alpha'=\sum_{z' \in \{0, 1\}^{k'}}w(r_1, ..., r_{k-k'},z')\tilde{X}(r_1,...,r_{k-k'},z') = \sum_{z_2, z_3 \in \{0, 1\}^2}w(r_1, z_2, z_3)\tilde{X}(r_1, z_2, z_3) $$
She just needs to check if $\alpha'=s_{k-k'}(r_{k-k'}) = s_1(r_1)$.

#### Guarantees
The guarantees of the partial sumcheck is as follows. If the verifier knows that,
for a new uniformly randomly sampled $r_{k-k'} \in F$,
$$s_{k-k'}(r_{k-k'})=\alpha'=\sum_{z' \in \{0, 1\}^{k'}}w(r_1, ..., r_{k-k'},z')\tilde{X}(r_1,...,r_{k-k'},z')$$
then, after running the verifier algorithm it is guaranteed that
$$
\sum_{z \in \{0, 1\}^k}w(z)\tilde(X)(z) = \alpha
$$

In particular, if $k'=0$, this reduces to standard sumcheck since the terminal condition is simply to evaluate the product of $w$ and $\tilde{X}$ at $(r_1, ..., r_k)$:
$$s_k(r_k)=w(r_1,...,r_k)\tilde{X}(r_1, ..., r_k)$$
The proof is identical to the standard sumcheck protocol proof.

#### Discussion
Above equation can be written in matrix form as:
$$
s_{k-k'}(r_{k-k'})=(\mathrm{Mat}(w)\bar{r})^T(\tilde{X}\bar{r})
$$
where, as before, $\bar{r}=(1-r_1, r_1) \otimes ... \otimes (1-r_{k-k'}, r_{k-k'})$

### Observations
In this section, we make some observations about the partial sumcheck protocol which we use in the protocol that follows.

#### Inner products
As mentioned before, the sumcheck protocol can be viewed as a protocl for verifying that the inner product between two vectors, $w$ and $\mathrm vec(\tilde{X})$ is, say, $\alpha$; written out, this means that
$$w^T\mathrm vec(\tilde{X}) = \sum_{z \in \{0,1\}^k} w(z) \tilde{X}(z) = \alpha$$

**Example**: Reference the above example in ["High level protocol"](https://hackmd.io/QtfWQ98HRfKDqcktWRxhFA?view#High-level-overview-of-partial-sumcheck-protocol).

#### Batching evaluations
If we are given a list of 𝑞 vectors $w_1, ..., w_q \in F^{2^k}$, and claimed inner products $\alpha_1,..., \alpha_q \in F$, we can ‘batch’ the evaluations and proofs into a single partial sumcheck protocol instance. The observation is very simple: once $\alpha_1, ..., \alpha_q$ are received, the verifier can draw some uniform randomness $\beta_1, ..., \beta_q \in F$ and simply run the partial sumcheck protocol over the new ector
$$
\tilde{w}=\beta_1w_1 + ... + \beta_qw_q
$$
and the new claimed inner product
$$
\tilde{\alpha}=\beta_1\alpha_1 + ... + \beta_q\alpha_q
$$
holding $\tilde{X}$ constant. This adds only a small probability of error, namely $1/|F|$, to the error probability of the protocol, if we use uniform and independent randomness for each $\beta_i$. We will call this new vector $\tilde{w}$, resulting from the batching process, the *batched vector* or *batched polynomial*.

**Example**:
$q = 3$
$w_1=1+x_1$, $\alpha_1=3$
$w_2=1+x_2$, $\alpha_2=3$
$w_3=1+x_3$, $\alpha_3=3$

Let's assume the following:
$\beta_1=1$, $\beta_2=2$, $\beta_3=3$

Then,
$$
\tilde{w}=1(1+x_1) + 2(1+x_2) + 3(1+x_3) = 6 + x_1 + 2x_2 + 3x_3
$$

$$
\tilde{\alpha}=1*3 + 2*3 + 3*3=18
$$

*batched vector*: $\tilde{w}=6 + x_1 + 2x_2 + 3x_3$
*new claimed inner product*: $\tilde{\alpha}=18$

#### Gluing sumchecks
One observation is that, given a partial sumcheck protocol instance, where the we are reducing a sum over $k$ variables to a sum over $k''$ variables, it is possible to, at any round $k'$ with $k'' < k' < k$, view the partial sumcheck protocol from $k$ to $k''$ as two 'glued' instances of the sumcheck protocol: one from $k$ to $k'$ variables and one from $k'$ to $k''$ variables. It is then possible, via the batching observations above, to batch two inner products: one sum over $k$ variables and one sum over $k'$ variables(with the rest of the variables fixed by the randomness of the first partial sumcheck).

#### Complete batched and glued sumcheck
For completeness, we describe the batched and glued sumcheck below. We assume that the prover has some matrix $\tilde{X} \in F^{{2^k}\times{2^{k'}}}$(which itself could be a partial evaluation of some larger matrix).

**Prover**
1. Receive some vectors $w_1, ..., w_q \in F^{2^{k+k'}}$
2. Send evaluations $\alpha_i=\mathrm vec({\tilde{X}})^Tw_j$ for $j=1, ..., q$
3. Receive some batching randomness $\beta \in F^q$
4. Construct a batched vector $\tilde{w}=\sum_{j=1}^{q}\beta_jw_j$
5. For $i=1,...,k-k'$
1. Send the polynomial $s_i(t)=\sum_{z \in \{0,1\}^{k-i}}\tilde{w}(r_1,...,r_{i-1}, t, z)\tilde{X}(r_1,...,r_{i-1}, t, z)$
2. Receive a random challenge $r_i \in F$, to be used in next rounde, if $i < k-k'$

**Verifier**
1. Send some vectors $w_1,...,w_q \in F^{2^{k + k'}}$
2. Receive (claimed) evaluations $\alpha_j$ for $j=1,...,q$
3. Send batching randomness $\beta \in F^q$
4. Construct a batched vector $\tilde{w}=\sum_{j=1}^{q}\beta_jw_j \in F^{2^{k+k'}}$
5. Set $s_0=\sum_{j=1}^{q}\beta_j\alpha_j$ to be a constant polynomial and $r_0=0$ for convenience
6. For $i=1,...,k-k'$:
1. Send some uniformly sampled $r_{i-1} \in F$
2. Receive some degree 2 polynomial $s_i: F \to F$
3. Verify that $s_i(0)+s_i(1)=s_{i-1}(r_{i-1})$

If all verifier checks pass, the verifier accepts the proof.

**Example**:
$k=3, k'=1, q=3$

- Prover has following matrix $\tilde{X}$
$$
\tilde{X}=\begin{bmatrix} 1 & -1\\1 & 1\\-1 & -1\\1 & 1\\-1 & 1\\1 & -1\\1 & -1\\-1 & 1 \end{bmatrix} \in F^{2^3 \times 2^1}
$$

- Verifier send the following vectors $w_1, w_2, w_3$
$$
w_1, w_2, w_3 \in F^{2^{3 + 1}}
$$

$$
w_1=
\begin{bmatrix}
1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1
\end{bmatrix}
w_2=
\begin{bmatrix}
1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1 \\ 1 \\ -1 \\ -1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1
\end{bmatrix}
w_3=
\begin{bmatrix}
-1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1
\end{bmatrix}
$$

- Prover receives vectors $w_1, w_2, w_3 \in F^{2^4}$
- Prover sends evaluations $\alpha_j=\mathrm vec(\tilde{X})^Tw_j$ for $j=1, 2, 3$
$$
\mathrm vec(\tilde{X})^T=\begin{bmatrix} 1 & 1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 \end{bmatrix}
$$
$$
\begin{aligned}
\alpha_1=\mathrm vec(\tilde{X})^Tw_1
&=\begin{bmatrix} 1 & 1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \\
&= 1 * 1 + 1 * 1 + (-1 * 1) + 1 * 1 + (-1 * 1) + 1 * 1 + 1 * 1 + (-1 * 1) + (-1 * 1) \\
&+ 1 * 1 + (-1 * 1) + 1 * 1 + 1 * 1 + (-1 * 1) + (-1 * 1) + 1 * 1 \\
&= 2
\end{aligned}
$$

$$
\begin{aligned}
\alpha_2=\mathrm vec(\tilde{X})^Tw_2
&=\begin{bmatrix} 1 & 1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1 \\ 1 \\ -1 \\ -1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1 \end{bmatrix} \\
&= 1 * 1 + 1 * 1 + (-1 * 1) + 1 * 1 + (-1 * 1) + (1 * -1) + 1 * 1 + (-1 * 1) + (-1 * -1) \\
&+ (1 * -1) + (-1 * 1) + 1 * 1 + 1 * 1 + (-1 * 1) + (-1 * -1) + 1 * 1 \\
&= 2
\end{aligned}
$$

$$
\begin{aligned}
\alpha_3=\mathrm vec(\tilde{X})^Tw_3
&=\begin{bmatrix} 1 & 1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 & -1 & 1 & 1 & -1 & -1 & 1 \end{bmatrix} \begin{bmatrix} -1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1 \\ 1 \\ 1 \\ 1 \\ 1 \\ -1 \end{bmatrix} \\
&= (1 * -1) + 1 * 1 + (-1 * 1) + 1 * 1 + (-1 * -1) + 1 * 1 + 1 * 1 + (-1 * 1) + (-1 * 1) \\
&+ 1 * 1 + (-1 * -1) + 1 * 1 + 1 * 1 + (-1 * 1) + (-1 * 1) + (1 * -1) \\
&= 2
\end{aligned}
$$

- Verifier receives (claimed) evaluations $\alpha_j$ for $j=1,2,3$.
She receives $\alpha_1=2, \alpha_2=2, \alpha_3=2$

- Verifier sends batching randomness $\beta \in F^3$
She sends $\beta = [1, 2, 3]$

- Both of Prover & verifier constructs a batched vector $\tilde{w}=\sum_{j=1}^{q}\beta_jw_j \in F^{2^{k + {k'}}}$
$$
\tilde{w} = \sum_{j=1}^{3}\beta_jw_j = 1 * w_1 + 2 * w_2 + 3 * w_3 = \begin{bmatrix} 1 * 1 + 2 * 1 + 3 * -1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * -1 \\ 1 * 1 + 2 * -1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * -1 + 3 * 1 \\ 1 * 1 + 2 * -1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * -1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * 1 \\ 1 * 1 + 2 * -1 + 3 * 1 \\ 1 * 1 + 2 * 1 + 3 * -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 6 \\ 6 \\ 6 \\ 0 \\ 2 \\ 6 \\ 6 \\ 2 \\ 2 \\ 0 \\ 6 \\ 6 \\ 6 \\ 2 \\ 0 \end{bmatrix}
$$

- Verifier sets $s_0 = \sum_{j=1}^{q}\beta_j\alpha_j = \sum_{j=1}^{3}\beta_j\alpha_j=1 * 2 + 2 * 2 + 3 * 2 = 12$ to be a constant polynomial and $r_0 = 0$ for convenience

- For $i = 1, 2$ ($i=1, ..., k-k'(=3-1)$)
Prover & Verifier performs the "partial sumcheck protocol" with $\tilde{w}$ and $\tilde{X}$.

## Old, but may be useful

In section 2.2 the Kronecker product $A\otimes B$ is defiend for matrices, despite only being applied to vectors throughout the paper. This simplifies our task of understanding it - let's see how it works when applied to vectors, for example,
$$
u = \begin{pmatrix}u_1 \\ u_2\end{pmatrix},
\quad
v = \begin{pmatrix}v_1 \\ v_2\end{pmatrix},
$$
We can treat these vectors as column-vectors. Similarly to the matrix notation, we take each element of the first vector and multiply it by the whole second vector:
$$
u \,\otimes\, v
\;=\;
\begin{pmatrix}
u_1\,v \\[6pt]
u_2\,v
\end{pmatrix}
\;=\;
\begin{pmatrix}
u_1\,v_1 \\[3pt]
u_1\,v_2 \\[3pt]
u_2\,v_1 \\[3pt]
u_2\,v_2
\end{pmatrix}.
$$

As we can see, after we expand $v$, each element of $u$ gets "distributed" across all entries of $v.$