Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Potentially simplify linear combination for low degree proof #7

Closed
bobbinth opened this issue May 29, 2019 · 1 comment

Comments

Projects
None yet
1 participant
@bobbinth
Copy link
Contributor

commented May 29, 2019

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

This comment has been minimized.

Copy link
Contributor Author

commented Jun 10, 2019

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.

@bobbinth bobbinth closed this Jun 10, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.