- \(T\): number of reads in read-only case. number of alternating reads and writes in the read/write case.
- values returned by any read operation -> \(\widetilde{\mathsf{rv}}\)
- value of register \(k\), \(\mathsf{Val}(k)\)
- \(\mathsf{ra}(k,j)=\left\{ \begin{aligned} & 1, \quad \text{register} \quad \mathsf{k} \quad \text{is read at cycle} \quad j \\ & 0, \quad \text{otherwise} \end{aligned} \right.\)
Read only memory:
checking all reads are correct is equivalent to confirming that for all cycles \( j\), the following constraint is satisfied:
$$\sum\limits_{\text{register} \quad k} \mathsf{ra}(k,j) \mathsf{Val}(k)= \mathsf{rv}(j)$$
Twist: read and write:
$$\sum\limits_{k \in [K]} \mathsf{ra}(k,j) \cdot \mathsf{Val}(k,j)= \mathsf{rv}(j)$$
for all the cycles \(j \in [T]\). (note the difference: \(\mathsf{Val}(k,j)\) in read write, and \mathsf{Val}(k) in read only)
for the above equations to hold, it is equivalent to check at random point \(r’ \in \mathbb{F}^{\log T}\) that the following equation holds:
$$\widetilde{\mathsf{rv}}(r’)=\sum_{(k,j)\in \{0,1\}^{\log K}\times \{0,1\}^{\log T}} \widetilde{\mathsf{eq}} (r’,j) \cdot \mathsf{ra}(k,j) \cdot \mathsf{Val}(k,j)$$
(the above equation is transferring \( \mathsf{rv}\) to its multilinear extension, don’t mess up with \(\mathsf{ra}\) and \(\mathsf{Val}\))
the sum of the above equation is the same as:
$$\sum_{(k,j)\in \{0,1\}^{\log K}\times \{0,1\}^{\log T} } \widetilde{\mathsf{eq}} (r’,j) \cdot \mathsf{\widetilde{ra}}(k,j) \cdot \mathsf{\widetilde{Val}}(k,j)$$
and now we can use sumcheck to prove the sum of the above equation.
I was confused with the switch from \(\widetilde{\mathsf{ra}}\) and \(\mathsf{ra}\), actually, when using sumcheck, you can interpret the polynomial to be multi-linear extension, or just consider the polynomial itself is not defined only on boolean hypercube by default.
Namely, you can use sumcheck to check
$$\widetilde{\mathsf{rv}}(r’)= \sum_{(k,j)\in \{0,1\}^{\log K}\times \{0,1\}^{\log T} } eq(\rho, j||k) \cdot \mathsf{eq} (r’,j) \cdot \mathsf{ra}(k,j) \cdot \mathsf{Val}(k,j)$$
this interpret the right side after \(\sum\) is a table, and get its multilinear extension
but you can also interpret the right side is already defined on fields. then it is
$$\widetilde{\mathsf{rv}}(r’)= \sum_{(k,j)\in \{0,1\}^{\log K}\times \{0,1\}^{\log T} } \widetilde{\mathsf{eq}} (r’,j) \cdot \mathsf{\widetilde{ra}}(k,j) \cdot \mathsf{\widetilde{Val}}(k,j)$$
the difference is the degree of the sumcheck protocol, it working on different polynomials, but they there sum on the hypercube are the same (left side is a constant, \(r’\) is chosen)
in the last round of sum-check, the randomness size is \(\mathbb{F}^{\log T + \log K}\)
so let’s transferring the right side to multilinear extension: