I was thinking to post this question in the discord, but feeling the timeline style of conversion there is difficult to track of. Not sure if this is the best place to ask implementation questions relating the knowledge in the survey paper. If not, please let me know if there is an alternative.

The sum check and the triangle counting example is intriguing. Currently I am making an implementation to demonstrate the sumcheck protocol over the triangle counting, with the MatMul IP optimization described in the section 4.4.2 of the survey paper. While implementing for the example definitely helps me understand the concepts thoroughly, I think this might serve as another examples to help others enhance the understanding the combination usage of the related concepts in addition to the existing vanilla sumcheck implementations.

One area in the protocol puzzles me for quite a while is how the two sum check protocols used in the triangle counting example wire up. To describe the question in details, I outline my understanding of the procedures of invoking the sum check and MatMul IP protocols below.

1st sumcheck

1.1 Prover calculates the MLEs give the entries of matrix $A$ and $A^2$, and invokes the sumcheck protocol using the following equation and send univariate $g$ polynomial to verifier $$\tilde{f}_{A^2}(X, Y) \cdot \tilde{f}_A(X, Y)$$ 1.2 Verifier recursively checks $$g_{j-1}(r_{j-1})=g_j(0)+g_j(1)$$ 1.3 until the last round $$g_v\left(X_v\right)=g\left(r_1, \ldots, X_v\right)$$

Because it is expensive for the verifier to validate the result in the last round by evaluating the $g(r_1,r_2,...,r_v)$, which corresponds to $\widetilde{f}_{A^{2}} \cdot \widetilde{f}_A$ given the entries of $A$ matrix, so it invokes the matmul IP to complete the check for the final round in the 1st sumcheck.

2nd sumcheck

2.1 Verifier chooses $(r_1, r_2)$ and invokes MatMul IP 2.2 Prover responses $$s(X):=\widetilde{f}_A\left(r_1, X\right) \cdot \widetilde{f}_A\left(X, r_2\right)=\left(r_1(1-X)+\left(1-r_1\right) X\right) \cdot\left(X\left(1-r_2\right)+r_2(1-X)\right)$$ 2.3 Verifier evaluates $$\tilde{f}_{A^2}\left(r_1, r_2\right)=s(0)+s(1)=r_1 r_2+\left(1-r_1\right)\left(1-r_2\right)$$, and multiplies it with $\tilde{f}_A\left(r_1, r_2\right)$ in order to get the target result $$\widetilde{f}_{A^{2}}\left(r_1, r_2\right) \cdot \widetilde{f}_A\left(r_1, r_2\right)$$ In my understanding, to convince the verifier the result of the double sumcheck protocol, the values from the equations of (1.3) and (2.3) should be equal.

However, in the first sumcheck, the random values $(r_1, r_2,...,r_{v-1})$ are already bounded(or I should call it "determined"). But in the second sumcheck in the matmul IP, the $(r_1, r_2)$ are newly chosen random values, unrelated to the corresponding ones although synthetically the same.

If $(r_1, r_2)$ doesn't represent the same random numbers as in the first sumcheck, the resulting value in the (1.3) won't be equal to (2.3). So I assume applying a new random number $r_3$ to both $s(X)$ in (2.2) and $g_v(X_v)$ in (1.3) neither makes them equal.

Then how can the verifier be convinced of the whole process? It is probably something I am missing during the process described above. Appreciate any hints.