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 .