STARKs, Part I: Proofs with Polynomials

STARKs, Part I: Proofs with Polynomials(vitalik.ca)

90 points by kobigurk 8 years ago | 8 comments

auggierose 8 years ago |

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

chrispeel 8 years ago |

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

wallacoloo 8 years ago |

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 8 years ago | |

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.

weber111 8 years ago |

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

yorwba 8 years ago | |

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

weber111 8 years ago | | |

Makes sense - thanks! I was confused by the continuous plot.

dnautics 8 years ago | |

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.