[wallacoloo]

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?

[Ar-Curunir]

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.