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_...

Introductory videos from the inventor of STARKS that may be useful (similar content in both)

* Eli Ben Sasson at SV Ethereum meetup https://www.youtube.com/watch?v=HJ9K_o-RRSY

* Eli Ben Sasson at SF Bitcoin Devs https://www.youtube.com/watch?v=kYmnXxs9kUM

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?

I'm a little confused by

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