Paper 2024/1038
ConstraintPacking and the SumCheck Protocol over Binary Tower Fields
Abstract
SNARKs based on the sumcheck protocol often invoke the ``zerocheck PIOP''. This reduces the vanishing of many constraints to a single sumcheck 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 sumcheck protocol prover for this setting. However, these works still require the prover to ``precompute'' 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 zerocheck PIOP in the case of binary tower fields that reduces this precomputation 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 constraintpacking over field extensions.
Note: Typo fixes
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 sumcheck protocolbinary tower fieldsinteractive proofsSNARKs
 Contact author(s)
 justin thaler @ georgetown edu
 History
 20240711: revised
 20240626: received
 See all versions
 Short URL
 https://ia.cr/2024/1038
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1038, author = {Quang Dao and Justin Thaler}, title = {ConstraintPacking and the SumCheck Protocol over Binary Tower Fields}, howpublished = {Cryptology ePrint Archive, Paper 2024/1038}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/1038}}, url = {https://eprint.iacr.org/2024/1038} }