Welcome to the resource topic for 2025/594
Title:
Efficient SNARKs for Boolean Circuits via Sumcheck over Tower Fields
Authors: Tianyi LIu, Yupeng Zhang
Abstract:In this paper, we present efficient SNARKs for Boolean circuits, achieving significant improvements in the prover efficiency. The core of our technique is a novel tower sumcheck protocol and a tower zero-check protocol tailored for tower fields, which enable this efficiency boost. When instantiated with Wiedemann’s binary tower fields with the base field of GF(2) and the top-level field GF(2^{2^\ell}), assuming the quadratic complexity of multiplications (O(2^{2\ell})) in the top-level field with 2^\ell bits, the prover time of our sumcheck protocol is (O(2^{1.5\ell}N)). It is faster than the standard sumcheck protocol over the large field with the complexity of (O(2^{2\ell}N)). To achieve a reasonable security level, 2^\ell is usually set to 128.
Leveraging this advancement, we improve the efficiency of IOP protocols over the binary or small characteristic fields for Plonkish, CCS, and GKR-based constraint systems. Moreover, to further improve the prover efficiency of the SNARKs, we introduce a basis-switching mechanism that efficiently transforms polynomial evaluations on the base-field polynomial to evaluations on the tower-field polynomial. With the basis-switching, we are able to compile the binary-field IOPs to SNARKs using large-field polynomial commitment schemes (PCS) that batch the witness over the base field. The size of the large-field PCS is only \frac{1}{2^\ell} of the size of the witness over the base field. Combining the IOP and the PCS, the overall prover time of our SNARKs for Boolean circuits significantly faster than the naive approach of encoding Boolean values in a large field.
ePrint: https://eprint.iacr.org/2025/594
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 .