STARKs, Part I: Proofs with Polynomials(vitalik.ca)
vitalik.ca
STARKs, Part I: Proofs with Polynomials
http://vitalik.ca/general/2017/11/09/starks_part_1.html
8 comments
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
* 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?
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.
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
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.)
Makes sense - thanks! I was confused by the continuous plot.
in practice these polynomials won't be over integers or rationals, they will be over finite fields.
https://www.youtube.com/watch?v=x1v2tX4_dkQ
they're also used extensively in reed-solomon coding.
https://www.youtube.com/watch?v=x1v2tX4_dkQ
they're also used extensively in reed-solomon coding.