facebook / winterfell

A STARK prover and verifier for arbitrary computations
MIT License
795 stars 180 forks source link

Optimize handling of periodic column multi-linear extension for sum-check prover #310

Open Al-Kindi-0 opened 2 months ago

Al-Kindi-0 commented 2 months ago

In the high degree sum-check prover, and due to the succinctness of the periodic columns, when we are iterating over all of the terms in the sum (i.e., the i index) there is some work, which is not significant but not negligible either, which is redundant across terms e.g., interpolating the periodic multi-linear extensions. We should be able reduce this by doing all of the work we do for each term at the outset i.e., before entering the loop.