Dense PCS

Code: slop: crates/stacked/src/verifier.rs:verify_trusted_evaluation

Now we can move onto the evaluation of $Q$, which is the dense representation of all data (to which the prover originally committed).

As described above, we split this into uniform columns of size $2^{21}$ (can be $2^{22}$, it's configurable - this exponent of $2$ is the log_stacking_height), so for example, if the total trace area is $2^{29}$, then $Q$ itself is of form $2^{21} \times 2^{8}$. The multilinear polynomial $Q(z)$ can be computed as

$$Q(z) = Q(z_{\text{row}}, z_{\text{col}}) = \sum_{c} Q(z_{\text{row}}, c) \cdot \text{eq}(z_{\text{col}}, c) = \sum_{c} Q_c(z_{\text{row}}) \cdot \text{eq}(z_{\text{col}}, c)$$

which means that one just needs a proof of all the $Q_c(z_{\text{row}})$ values, i.e. each column's evaluation at $z_{\text{row}}$. This can be done simply with Batched BaseFold as usual Batch-FRI.

In more detail, the prover first decomposes the multilinear evaluation claim about $Q(z)$ into claims about the distinct columns of which $Q$ is composed. The verifier checks that this decomposition is consistent with the claimed value of $Q(z)$. The verifier then chooses a random linear combination of the columns and the parties run basefold on the resulting polynomial.

Basefold

slop: crates/basefold/src/verifier.rs:verify_mle_evaluations

This is the standard Basefold, the multilinear version of FRI. At a high-level the protocol combines the standard FRI protocol together with a sumcheck, which is used to establish the multilinear evaluation of the committed oracle.

Hypercube's core and recursion proofs do not rely on proximity gap conjectures. Rather, they rely on the proximity gaps theorem, established by Ben Sasson et al. (Eli Ben-Sasson, Dan Carmon, Yuval Ishai, Swastik Kopparty, Shubhangi Saraf: Proximity Gaps for Reed-Solomon Codes, JACM 2023).

The FRI parameters used (rate, queries, grinding, etc) can be found in slop: crates/primitives/src/fri_params.rs