facebook / winterfell

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

Optimize construction of multi-linear polynomials for final sum-check #303

Open Al-Kindi-0 opened 2 months ago

Al-Kindi-0 commented 2 months ago

Before running the final sum-check of GKR in LogUp-GKR, we need to build multi-linear extensions of the relevant main trace columns. These are originally over the base field but the multi-linear extension as it is currently constructed stores them as extension field elements. We should investigate if it is possible to avoid this as it could provide a nice reduction in the memory footprint.