Proof of Sumcheck

A key observation that the Hyrax protocol makes is that the verifier's sumcheck "checks," i.e. that $g_i(0)+g_i(1)=g_{i-1}(r_{i-1})$, and the final oracle query, can be modeled as linear equations.

At each round, $\mathcal{P}$ "sends" $\mathcal{V}$ the univariate $g_i(X)$ by committing to its coefficients using Pedersen scalar commitments. Let $a_{i,0},\dots ,a_{i,n}$ (to get commitments $C_{a_{i,0}},\dots ,C_{a_{i,n}}$) be the coefficients for a degree $n$ univariate, where $a_{i,j}$ is the coefficient of the $j$-th degree term.

Notice that $g_i(0)$ is simply $a_{i,0}$ and $g_i(1)$ is ${\sum }_j{a}_{i,j}$. Then $g_i(0)+g_i(1)$ is $2a_{i,0}+a_{i,1}+\cdots +a_{i,n}$. We can compute the commitment to this using just the commitments to the coefficients as $2C_{a_{i,0}}+C_{a_{i,1}}+\cdots +C_{a_{i,n}}$. Similarly, the evaluation $g_{i-1}(r_{i-1})$ can be computed using commitments to the coefficients of $g_{i-1}$ as ${\sum }_j{r}^j{C}_{a_{i-1,j}}$. For each intermediate round of sumcheck, we simply have to compute a proof of equality between the two commitments $2C_{a_{i,0}}+{\sum }_j{C}_{a_{i,j}}$ and ${\sum }_k{r}^k{C}_{a_{i-1,k}}$.

We can formulate the verifier's checks as a matrix vector product where the matrix $M$ contains the linear combination coefficients over the prover's messages, and the vector $\vec{\pi }$ contains the prover's sumcheck messages as coefficients of the univariate polynomial in each round. Let round $i$'s univariate have $d_i$ coefficients. Then, we can write the verifier's checks as such:

$$\begin{gathered} M=\left[\begin{array}{cccccc}\underset{d_0}{\underbrace{\begin{array}{cccc}2& 1& \cdots & 1\end{array}}}& & & & & \\ & & & & & \\ & & & & & \\ \begin{array}{cccc}-1& -r_0& \cdots & -r_0^{d_0-1}\end{array}& \underset{d_1}{\underbrace{\begin{array}{cccc}2& 1& \cdots & 1\end{array}}}& & & & \\ & & & & & \\ & & & & & \\ & \begin{array}{cccc}-1& -r_1& \cdots & -r_1^{d_1-1}\end{array}& \underset{d_2}{\underbrace{\begin{array}{cccc}2& 1& \cdots & 1\end{array}}}& & & \\ & & & & & \\ & & & \ddots & & \\ & & & & & \\ & & & & \begin{array}{cccc}-1& -r_{n-1}& \cdots & -r_{n-1}^{d_{n-1}-1}\end{array}& \underset{d_n}{\underbrace{\begin{array}{cccc}2& 1& \cdots & 1\end{array}}}\\ & & & & & \\ & & & & & \begin{array}{cccc}-1& -r_n& \cdots & -r_n^{d_n-1}\end{array}\end{array}\right] \\ \vec{\pi }=\left[\begin{array}{c}{C}_{a_{0,1}}\\ C_{a_{0,2}}\\ ⋮\\ C_{a_{0,d_0}}\\ ⋮\\ C_{a_{n,1}}\\ C_{a_{n,2}}\\ ⋮\\ C_{a_{n,d_n}}\end{array}\right] \end{gathered}$$

To encode all of the verifier's sumcheck checks in one go, we have $\mathcal{V}$ check that:

$$M\cdot \vec{\pi }=\left[\begin{array}{c}H\\ 0\\ ⋮\\ 0\\ ?\end{array}\right]$$

The final $?$ represents the fact that the final dot product in the matrix-vector product $M\cdot \vec{\pi }$ is not $0$. In fact, it should be exactly equal to the value that $\mathcal{V}$ receives when it does the final "oracle query" in sumcheck. This is discussed next.

Every non-specified entry in the matrix $M$ is $0$, and it has dimension $(n+1)\times {\sum }_i{d}_i$. $\vec{\pi }$ has dimension ${\sum }_i{d}_i\times 1$. Its product has dimension $(n+1)\times 1$. The sum $H$ represents $\mathcal{P}$'s original claim for the sumcheck expression -- the sum of the first univariate $g_0(0)+g_0(1)$ should be equal to the sum, which is what the first row of the matrix multiplied by $\vec{\pi }$ encodes.

Note that we can do a proof of dot product for each of the row of the matrix with $\vec{\pi }$ as the private vector, and each entry in the resultant vector as the claimed dot product.

However, there is a small subtlety: every $d_i$ coefficients in $\vec{\pi }$ must be committed to before the challenge $r_i$ is sampled for sumcheck. Otherwise, $\mathcal{P}$ can modify the commitments to make false claims using its knowledge of $r_i.$ Therefore, $\vec{\pi }$ is committed to incrementally, and after each commitment $r_i$ is sampled. Finally, $\mathcal{V}$ and $\mathcal{P}$ engage in a proof of dot product for every row of the matrix $M$.

The final "oracle query"

Over here we have encoded all of $\mathcal{V}$'s checks except for the final oracle query. Recall that at the end of sumcheck, $\mathcal{P}$ has claims on underlying MLEs. In the Hyrax universe, $\mathcal{P}$ commits to the claims it has on each of these MLEs, say via the commitments $v_0,\dots ,v_k.$ Then $\mathcal{V}$ can combine these commitments linearly to compute a commitment to the expected value $f(r_1,\dots ,r_n).$ Then, we expand the matrix $M$ to have $k$ additional columns and add the coefficients $\mathcal{V}$ needs to compute the linear combination of $v_0,\dots ,v_k$ to the last (the $n$-th) row of $M$, and $\vec{\pi }$ has $k$ additional entries with the commitments $v_0,\dots ,v_n$. Then $\mathcal{V}$ can expect the result of the final dot product to be $0$.

Example

We provide a minimal example to show how $M$ and $\pi$ are constructed. Assume $\mathcal{P}$ and $\mathcal{V}$ are engaging in sumcheck over the claim that $V_i(g_1,g_2)=H$, and via layerwise encoding, $V_i(z)={\sum }_{x_i,y_i,z_i\in \{0,1\}}\widetilde{\mathrm{add}}(z_1,z_2;x_1,x_2;y_1)(V_{i+1}(x_1,x_2)+V_{i+1}(y_1)).$ There are $3$ rounds of sumcheck (for each of the $x$ and $y$) variables, where $r_1,r_2$ bind to $x_1,x_2$ and $r_3$ is bound to $x_3$. At the end of sumcheck, $\mathcal{P}$ commits to ${\tilde{V}}_{i+1}(r_1,r_2)$ and ${\tilde{V}}_{i+1}(r_3)$ as $V_0$ and $V_1.$

$M,\vec{\pi }$ look like this: $$M=\left[\begin{array}{ccccccccccc}2& 1& 1& 0& 0& 0& 0& 0& 0& 0& 0\\ -1& -r_1& -r_1^2& 2& 1& 1& 0& 0& 0& 0& 0\\ 0& 0& 0& -1& -r_2& -r_2^2& 2& 1& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& -1& -r_3& -r_3^2& \widetilde{\mathrm{add}}(g_1,g_2;r_1,r_2;r_3)& \widetilde{\mathrm{add}}(g_1,g_2;r_1,r_2;r_3)\end{array}\right]$$

$$\vec{\pi }=\left[\begin{array}{c}{C}_{a_{0,1}}\\ C_{a_{0,2}}\\ C_{a_{0,3}}\\ C_{a_{1,1}}\\ C_{a_{1,2}}\\ C_{a_{1,3}}\\ C_{a_{2,1}}\\ C_{a_{2,2}}\\ C_{a_{2,3}}\\ V_0\\ V_1\end{array}\right]$$

And their result that $\mathcal{V}$ expects, which it can compute on its own is:

$$M\cdot \vec{\pi }=\left[\begin{array}{c}H\\ 0\\ ⋮\\ 0\end{array}\right]$$

Optimizations

There is an optimization specified in the original Hyrax paper which allows us to take the random linear combination of the rows of $M$ and do $n$ proofs of dot product of just size $d_i$ where $d_i$ is the number of coefficients in the univariate of round $i$, rather than $n$ proofs of dot product of size $n\cdot d_i$. We don't go into how to formulate this optimization, but suggest reading the original paper and specifically the "squashing $\mathcal{V}$'s checks" section. We have implemented this optimization in Remainder.