Unable to understand Eli Ben Sasson's STARK arithmetization & proof example

This is from this video - https://www.youtube.com/watch?v=9VuZvdxFZQo

Bob has a list of length $10^6$. Bob wants to convince Alice that every number in the list is between 1 & 10. Alice needs to verify it with just 2 queries & 99% certainty.

This is the protocol given by Ben

• $f$ is polynomial created by interpolating all $10^6$ numbers in the list.

• $g$ is any polynomial of degree $10^7 - 10^6$ i.e. any polynomial of degree 9 million

• $C(x) = (x-1)(x-2)...(x-10)$

• $D(x) = (x-1)(x-2)...(x-10^6)$

• Alice chooses random $x_0 \in \{1, 2, ..., 10^9\}$

• Let $f(x_0) = \alpha$ & $g(x_0) = \beta$

• Alice will believe that all numbers in the list are between 1 & 10, if & only if $C(\alpha) = \beta\cdot D(x_0)$

I don't understand why the last statement is true. He gives the completeness & soundness arguments also which I don't understand.

Here is the completeness argument.

• Let $P(X)$ be the interpolant of $f$

• Then $C(P(X))$ vanishes on $x_0 \in \{1, 2, ..., 10^6\}$

He goes on beyond this for the completeness argument but the above is what is I didn't first understand.

Why would $C(P(X))$ vanish on $x_0 \in \{1, 2, ..., 10^6\}$?

$P$ vanishes only if $x_0$ is between 1 & 10. But $x_0$ is a random number picked from a huge domain - so with very high probability $P(x_0) \ne 0$ & we don't know the value of $P(x_0)$ also - it can be anything, right? So why would $C(P(X))$ vanish considering it vanishes only at 10 values from 1 to 10?

Also, I think he says this is with 100% probability & not just very high probability, but that's a secondary thing to figure out.

If you do want to look through the video, then you can jump directly to the beginning of this particular protocol at https://www.youtube.com/watch?v=9VuZvdxFZQo&t=765s

Important to remember here is that this is a proof of completeness, which is the property that "Bob honest $\rightarrow$ Alice accepts". The lecturer has made the implicit assumption that Bob is honest, i.e. every element of his list is $\in \{1,...,10\}$ and is proving that this results in Alice's acceptance.

Recall that the "interpolant" of any element $w \in \mathbb{k}^n$ is the unique polynomial $ P \in \mathbb{k}[x]$ with $\text{deg} P \leqslant n$ such that $\forall i \in {1,...n}$, $P(i) = w_i$. Hence if Bob is honest, $P$ restricted to $1,...,10^6$ will take only values in $1,...,10$, hence $C \circ P$ vanishes on this set. I believe you have misquoted the slide slightly since the second line of the completeness proof only requires that this vanishes on the domain of interest, $1,...,10^6$.

Note that for any value of $x_0 > 10^6$, $D(x_0) \neq 0$ (in this example case by the fundamental theorem of algebra, in the most general case by the Schwartz–Zippel lemma), hence the relation $$ C(f(x_0)) = g(x_0)D(x_0) $$ would only ever hold when $g(x_0) = 0$ if $C \circ P$ vanished on the entire domain.