# 1/5: [[DP23]](https://eprint.iacr.org/2023/630.pdf): Logarithmic Randomness

## Summary

Recall the statement from [1/3: Ligero's Proof for $q < d'/3$](https://hackmd.io/k8_1AfQNTfy25N23QTmZ6g) -

> The main statement is that
>
> $$\left\lVert \sum_{i=1}^n r_i x_i - V \right\rVert_0 \le q \implies X \text{ is } q\text{-close to } V$$
>
> where $r_i$ are random, with failure probability $q/\lvert \mathbb{F} \rvert$.

To test $n$ vectors, we needed $n$ random elements. However, this isn't all that great - for example, in the ultimate batched FRI soundness proof in [[BCI+23]](https://eprint.iacr.org/2020/654.pdf), it deals with correlated agreement over a parameterized curve, so that one samples $r \in \mathbb{F}$ and uses the coefficients $1, r, r^2, \cdots , r^{n-1}$ instead of sample $n$ random values like we did in Ligero.

This paper enables us to reduce the number of random elements to $\log n$.

This paper is also a fundamental building block for Binius (2023/1784) as well.

In essence the random vector to be used for testing is non other than the all-to-familiar

$$(1 - r_0, r_0) \otimes (1 - r_1, r_1) \otimes \cdots \otimes (1 - r_{\log n - 1}, r_{\log n - 1}) $$

which makes this testing even more awesome for multilinear polynomial commitment schemes.

The failure probability only increases by a factor of $\log n$ as well, which is great.

Regarding the proofs, it's a nice practice for fully understanding emulators / forking lemma / witness-extended emulation and the stuff that's usually the hardest to understand completely.

Lots of abuse of notation in this notes, because I'm too lazy to LaTeX everything, sorry.

Denote $\mu(S)$ as the density of set $S$ over their "natural habitat".
## Testing via Tensor Product

> For any $[n, k, d]$ code $V \in \mathbb{F}_q^n$ and $e < d/3$, given $u_0, \cdots, u_{m-1} \in \mathbb{F}_q^n$ such that
>
> $$\text{Pr}_{(r_0, \cdots, r_{\log m - 1}) \in \mathbb{F}_q} \left( d( [\otimes_{i=0}^{\log m - 1} (1 - r_i, r_i)] \cdot [u_0, \cdots, u_{m-1}]^T, V) \le e \right) > 2 \cdot \log m \cdot \frac{e}{q}$$
>
> then $U = [u_0, \cdots, u_{m-1}]$ is $e$-close to $V$.

Write $l = \log m$ and work with induction on $l$, where $l = 1$ is the usual Ligero proof.

Now assume the statement for $l - 1$ and we prove the statement for $l$.

For $(r_0, \cdots, r_{l-2})$, consider

$$M_0 = [\otimes_{i=0}^{l-2} (1 - r_i, r_i)] \cdot [u_0, \cdots , u_{2^{l-1}-1}]^T$$

$$M_1 = [\otimes_{i=0}^{l-2} (1 - r_i, r_i)] \cdot [u_{2^{l-1}}, \cdots , u_{2^{l}-1}]^T$$

$$R_0 = \{(r_0, \cdots, r_{l-2}) : d(M_0, V) \le e\}, \quad R_1 = \{(r_0, \cdots, r_{l-2}) : d(M_1, V) \le e\}$$

$$p(r_0, \cdots, r_{l-2}) = \text{Pr}_{r_{l-1} \in \mathbb{F}_q} \left[ d((1-r_{l-1}) M_0 + r_{l-1} M_1, V ) \le e \right]$$

$$R^\star = \left\{(r_0, \cdots , r_{l-2}) : p(r_0, \cdots, r_{l-2}) > \frac{e+1}{q} \right\}$$

The proof idea is as follows. It's easy to show that $R^\star \in R_0 \cap R_1$ and $\mu(R^\star) > 2e(l-1)/q$.
These two show that the assumption for the statement for $l-1$ holds on $[u_0, \cdots , u_{2^{l-1}-1}]$ and $[u_{2^{l-1}}, \cdots ,u_{2^l-1}]$. This means that one can define the distances

$$e_0 = d([u_0, \cdots, u_{2^{l-1} - 1}], V), \quad e_1 = d([u_{2^{l-1}}, \cdots , u_{2^l - 1}] , V)$$

as well as their corresponding close codewords $v_0, v_1, \cdots, v_{2^{l-1}-1}, v_{2^{l-1}}, \cdots, v_{2^l-1}$. Also, we can define their correlated disagreement sets $D_0$ and $D_1$. We also set

$$N_0 = [\otimes_{i=0}^{l-2} (1 - r_i, r_i)] \cdot [v_0, \cdots , v_{2^{l-1}-1}]^T$$

$$N_1 = [\otimes_{i=0}^{l-2} (1 - r_i, r_i)] \cdot [v_{2^{l-1}}, \cdots , v_{2^{l}-1}]^T$$

and define

$$B_0 = \{(r_0, \cdots , r_{l-2}) : d(M_0, N_0) < e_0 \}, \quad B_1 = \{(r_0, \cdots, r_{l-2}) : d(M_1, N_1) < e_1\}$$

One then proves that $\mu(B_0), \mu(B_1) \le e(l-1)/q$, which then forcees an element

$$(r_0^\star, \cdots , r_{l-2}^\star) \in R^\star \setminus (B_0 \cup B_1)$$

Denote $M_0^\star, M_1^\star, N_0^\star, N_1^\star$ as the respective values from $(r_0^\star, \cdots, r_{l-2}^\star)$. From the proof of the usual line case, it happens that there must be a set $D^\star$ with size at most $e$ such that $M_0^\star, M_1^\star$ are both close to a codeword with correlated disagreement, a subset of $D^\star$.

It can be proved that $D_0$ and $D_1$ are both subsets of $D^\star$, finishing the proof of the theorem.

Now we work on the details. First, let's prove $R^\star \in R_0 \cap R_1$. This is by the "line" case we handled back in $l=1$ - if we are in $R^\star$, then the entire line $(1 - r_{l-1})M_0 + r_{l-1} M_1$ is $e$-close to $V$, which immediately implies $d(M_0, V), d(M_1, V) \le e$, implying we are in $R_0 \cap R_1$.

Now we show $\mu(R^\star) > 2e(l-1)/q$. From the assumption

$$\text{Average}_{(r_0, \cdots , r_{l-2})} (p(r_0, \cdots , r_{l-2})) > 2el / q$$

the left hand side is at most

$$(1 - \mu(R^\star)) \cdot (e+1) / q + \mu(R^\star)$$

so we have

$$\mu(R^\star) + (e+1) / q \ge \text{Average}_{(r_0, \cdots , r_{l-2})} (p(r_0, \cdots , r_{l-2})) > 2el / q$$

which is sufficient to prove $\mu(R^\star) > 2e(l-1)/q$ as desired.

We move on to proving $\mu(B_0), \mu(B_1) \le e(l-1)/q$. We just prove it for $B_0$. For each $j \in D_0$,

$$C_{j} = \{(r_0, \cdots , r_{l-2}) : M_{0, j} = N_{0, j} \}$$

is basically a set of zeroes of a $l-1$-variate nonzero multilinear polynomial. Therefore, via Schwartz-Zippel we have $\mu(C_{b, j}) \le (l - 1) / q$, and via a union bound one has

$$\mu(B_0) = \mu \left( \cup_{j \in D_0} C_{j} \right) \le e_0 (l-1)/q \le e(l-1)/q$$

as desired, and same proof works for $B_1$ as well.

We now prove that $D_0 \cup D_1 \subset D^\star$, ending the proof. We'll just prove $D_0 \subset D^\star$.

Since $(r_0^\star, \cdots, r_{l-2}^\star) \notin B_0$, we have that $M_0^\star$ and $N_0^\star$ disagree exactly at $D_0$. At the same time, $M_0^\star$ is close to a codeword $O_0$ that disagrees at a subset of $D^\star$ - but since we are in unique decoding radius, it happens that $N_0^\star = O_0$, so $D_0 \subset D^\star$ as desired.

## Polynomial Commitments

NOTE: I'll assume usual multilinear polynomial + linear-time encodable codes + merkle tree approaches - I read Brakedown to study this, so I recommend reading that too.

One of the more interesting observations in sumcheck related protocols is that the final evaluation point for the multilinear polynomial is a random point - therefore, the provided polynomial commitments could be only suitable for random queries. For comparison, note how KZG commitments can handle any queries. Combining this with the observation about how the random vector used for testing proximity is exactly like a multilinear polynomial evaluation, one can combine the testing and evaluation phases into one, and ultimately optimize computation.

Apparently this random query vs all query dynamics was first eploited by Marlin [CHM+20].

The randomness reduction helps in the case of proof composition - where the second prover has the additional task of verifying that the randomness was generated correctly via Fiat-Shamir. With low number of randomness, the verifier can directly access the random oracle and keep a low verifier complexity. I was kinda confused on this on Orion too, lol.

The claim that testing and evaluation is the same is quite straightforward - as usual consider a $2\log m$-variable polynomial $t(X_0, \cdots, X_{2\log m - 1})$ and put the $m^2$ coefficients in a matrix, then

$$t(r_0, \cdots , r_{2 \log m - 1}) = [ \otimes_{i=\log m}^{2 \log m - 1} ( 1 - r_i, r_i)] \cdot [t_0, \cdots, t_{m-1}]^T \cdot [\otimes_{i=0}^{\log m - 1} (1 - r_i, r_i)]^T$$

From now on, we use the definitions and notations from the paper.





Extractability implies that $\mathcal{E}$, given full rewinding + random oracle query for $\mathcal{A}$, can extract $t, u$.

We work with a $[n, m, d]$ code $V$ - also assume that $d = \Omega(n)$ and $\kappa = \Theta( \lambda)$.

The commitment scheme works as follows: let $l = \log m$ and consider a $2l$-variate polynomial $t$. We write $t$'s coefficients as a $m \times m$ matrix, and encode each row to obtain $(u_i)_{i=0}^{m-1}$. We get a merkle root $c$ for $u$ ready and this is our commitment - note that we will have to provide entire columns as a query answer later - so merkle leaf ordering is important for optimization. This $u$ will serve as our opening hint. To open the commitment $c$ with input $t, u$ - one checks that $u$ merkle hashes to the commitment $c$ and that the distance between encodings of $t$'s rows and $u$s is below $d/3$. It's clear that correct commitments open correctly.

The prover and verifier works as follows - both know $c, s, (r_0, \cdots , r_{2l-1})$. The claim is

$$t(r_0, \cdots, r_{2l-1}) = s$$

- Prover computes and sends $t' = [\otimes_{i=l}^{2l-1} (1 - r_i, r_i)] \cdot [t_0, \cdots, t_{m-1}]^T$
- Verifier samples $\kappa$ random indices from $\{0, 1, \cdots, n-1\}$. Denote this set as $J$.
- Prover sends the $\kappa$ columns as well as their merkle proofs to the Verifier
- Verifier checks all the merkle proofs, and decides if the following hold for all $j \in J$

$$[\otimes_{i=l}^{2l-1} (1 - r_i, r_i)] \cdot [u_{0, j}, \cdots, u_{m-1, j}]^T = \text{Enc}(t')_j$$

- Verifier computes $t' \cdot [\otimes_{i=0}^{l-1} (1 - r_i, r_i)]^T$ and checks if it equals $s$

In reality, Fiat-Shamir is used to make the system non-interactive.

The commitment is binding due to us being in the unique decoding radius of the code.

Extractability proof will be read and written later. Need to brush up on techniques...