Welcome to the resource topic for 2024/1038
Title:
Constraint-Packing and the Sum-Check Protocol over Binary Tower Fields
Authors: Quang Dao, Justin Thaler
Abstract:SNARKs based on the sum-check protocol often invoke the zero-check PIOP''. This reduces the vanishing of many constraints to a single sum-check instance applied to an $n$-variate polynomial of the form $g(x) = \text{eq}(r,x) \cdot p(x)$, where $p$ is a product of multilinear polynomials, $r$ is a random vector, and $\text{eq}$ is the multilinear extension of the equality function. In recent SNARK designs, $p(x)$ is defined over a small’’ base field, while r is drawn from a large extension field \mathbb{F} for security.
Recent papers (Bagad, Domb, and Thaler 2024; Gruen 2024) have optimized the sum-check protocol prover for this setting. However, these works still require the prover to ``pre-compute’’ all evaluations of \text{eq}(r, x) as x ranges over \{0, 1\}^{n},
and this computation involves about n multiplications over the extension field \mathbb{F}.
In this note, we describe a modification to the zero-check PIOP in the case of binary tower fields that reduces this pre-computation cost by a factor of close to \log |\mathbb{F}|, which is 128 in important applications. We show that our modification is sound, and that it strictly generalizes a (possibly folklore) technique of constraint-packing over field extensions.
ePrint: https://eprint.iacr.org/2024/1038
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 .