It seems a special (already very useful) case of ZKP as explained in the article is when f is independent of x, giving you the concept of certificates, a concept well-known in interactive theorem proving, for example: https://link.springer.com/chapter/10.1007/978-3-642-21046-4_...
I'm glad Vitalik acknowledged the implicit assumption that the P(x) provided by the prover was really <= 1000000 in degree, because that caught me up when I reached that point.
But I'm a bit lost on how one would apply STARKs in practice. I can't tell if this scheme is intended to provide a proof of existence or a proof of knowledge, for example. Both examples are trivial enough that one can assume their existence (of course there's some P(x) for which 0 <= P(x) <= 9 for all x in [0, 1000000)). But they're also trivial enough that it's reasonable to assume that anyone can know the millionth Fibonacci number. So what good is using this as a proof of knowledge?
STARKs are proofs of knowledge (it's in the name: Succinct Transparent ARguments of Knowledge). Sure, the fibonacci example is a bit useless, because anyone can compute that easily. But the proof process holds for proving knowledge of a preimage of a hash, or the opening to a commitment, or any NP statement in general.
Let C(x) be a constraint checking polynomial; C(x) = 0 if 0 <= x <= 9 and is nonzero otherwise. There’s a simple way to construct C(x): x * (x-1) * (x-2) * ... * (x-9)
This is only true if x is an integer in that range, right? But the polynomial he's transforming by applying C to it doesn't have a discrete range
I think the polynomial is supposed to have only integer coefficients, which means that it will only take integer values at integer coordinates. Since real-valued coefficients need some rational approximation anyway, and rational coefficients can be rescaled, that assumption is easy to justify. (Alternatively, the coefficients might be in some finite field, but then the range is discrete as well.)