GuildOfWeavers / genSTARK

A library for generating zk-STARKs.
MIT License
142 stars 18 forks source link

Potentially simplify linear combination for low degree proof #7

Closed bobbinth closed 5 years ago

bobbinth commented 5 years ago

To reduce the size of FRI proofs, polynomials P(x), B(x) and D(x) are combined into a single polynomial using random linear combination. In Vitalik Buterin's STARKs, Part 3: Into the Weeds this done by combining P, Psteps, B, Bsteps, and D as follows:

E = k1 P + k2 P xsteps+ k3 B + k4 B xsteps + D

This library implements a generalized version of this approach, but it is not clear to me why the linear combination can't be done with just Psteps, Bsteps, and D as:

E = k1 P xsteps+ k2 B xsteps + D

If the above does not sacrifice security, it would simplify the code a little and also make #5 straightforward to implement.

bobbinth commented 5 years ago

This simplification doesn't seem to be possible per Vitalik Buterin's comment from here:

Ah yes, this is a very subtle point. P and B are degree < n polynomials, and D is a degree < 2n polynomial. Hence for a degree < 2n check to properly check the degree of both polynomials, we need to multiply P and B by x^n. However, if we do just that, then a value like P(x)=1/(x^n) would also pass, which is not what we want, and so we need to do a linear combination P′(x)=P(x)∗k1+ P(x) x^n k2, which does successfully ensure that if deg(P)≥ n then deg(P′)≥ 2n.