✳flâneur — a map of the web's best reading

STARKs, Part II: Thank Goodness It's FRI-day

vitalik.eth.limo · 3,218 words · saved by 1 readers

In the last part of this series, we talked about how you can make some pretty interesting succinct proofs of computation, such as proving that you have computed the millionth Fibonacci number, using a technique involving polynomial composition and division. However, it rested on one critical ingredient: the ability to prove that at least the great majority of a given large set of points are on the same low-degree polynomial. This problem, called "low-degree testing", is perhaps the single most complex part of the protocol. We'll start off by once again re-stating the problem. Suppose that you have a set of points, and you claim that they are all on the same polynomial, with degree less than 𝐷 (ie. 𝑑 𝑒 𝑔 < 2 means they're on the same line, 𝑑 𝑒 𝑔 < 3 means they're on the same line or parabola, etc). You want to create a succinct probabilistic proof that this is actually true. If you want to verify that the points are all on the same degree < 𝐷 polynomial, you would have

Dark Mode Toggle STARKs, Part II: Thank Goodness It's FRI-day 2017 Nov 22 See all posts STARKs, Part II: Thank Goodness It's FRI-day Special thanks to Eli Ben-Sasson for ongoing help and explanations, and Justin Drake for reviewing In the last part of this series, we talked about how you can make some pretty interesting succinct proofs of computation, such as proving that you have computed the millionth Fibonacci number, using a technique involving polynomial composition and division. However, it rested on one critical ingredient: the ability to prove that at least the great majority of a give

Explore this link on the map →

related reading