Welcome to the resource topic for 2024/1210
Title:
More Optimizations to Sum-Check Proving
Authors: Quang Dao, Justin Thaler
Abstract:Many fast SNARKs apply the sum-check protocol to an n-variate polynomial of the form g(x) = \text{eq}(w,x) \cdot p(x), where p is a product of multilinear polynomials, w \in \mathbb{F}^n is a random vector, and \text{eq} is the multilinear extension of the equality function.
In this setting, we describe an optimization to the sum-check prover that substantially reduces the cost coming from the \text{eq}(w, x) factor. Our work further improves on a prior optimization by Gruen (ePrint 2023), and in the small-field case, can be combined with additional optimizations by Bagad, Domb, and Thaler (ePrint 2024), and Dao and Thaler (ePrint 2024).
Over large prime-order fields, our optimization eliminates roughly 2^{n + 1} field multiplications compared to a standard linear-time implementation of the prover, and roughly 2^{n-1} field multiplications when considered on top of Gruen’s optimization. These savings are about a 25% (respectively 10%) end-to-end prover speedup in common use cases, and potentially even larger when working over binary tower fields.
ePrint: https://eprint.iacr.org/2024/1210
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .