Abstract
Σ-protocols are fundamental building blocks in modern zero-knowledge proofs, yet they have historically struggled with efficiency when applied to high-degree polynomial relations. Traditional "linearization" techniques introduce communication overhead that scales linearly with the number of instances, creating a significant bottleneck. This paper introduces Σ-Check, a novel framework that replaces linearization with a dual-phase sum-check protocol. By applying sum-check to both amortization and compression, Σ-Check achieves logarithmic communication overhead ($O(\log k)$ and $O(\log m)$) for polynomial relations without requiring additional polynomial commitment schemes.
1. Introduction
Σ-protocols serve as the backbone for various cryptographic applications, including digital signatures and confidential transactions. While recent advancements like Bulletproofs have successfully compressed linear relations to a logarithmic scale, high-degree polynomial relations remain problematic. The standard approach—converting these relations into arithmetic circuits and proving them as linear relations—imposes a "linear tax." Specifically, the communication cost of the amortization phase scales linearly ($O(k)$) with the number of instances, and the process often requires memory-intensive Fast Fourier Transforms (FFTs).
2. Methodology
Σ-Check bypasses the linearization bottleneck by utilizing the sum-check protocol in two distinct, unified phases:
2.1 Amortization with Sum-check
To handle $k$ distinct proof instances, Σ-Check encodes them into a single polynomial. A sum-check protocol is then used to "fold" these instances into one. This transformation reduces the communication cost of the amortization phase from the traditional $O(k)$ to $O(\log k)$.
2.2 Compression with Sum-check
Following amortization, the resulting relation remains high-degree, making it incompatible with standard Bulletproofs. Σ-Check employs a second sum-check protocol to compress the witness size ($m$) down to a logarithmic scale ($O(\log m)$). Notably, Σ-Check leverages the binding property of existing Pedersen vector commitments to verify evaluation claims, eliminating the need for an external Polynomial Commitment Scheme (PCS).
3. Results and Asymptotic Performance
The primary contribution of Σ-Check is its asymptotic superiority over previous state-of-the-art methods like AC20 and ACF21. As illustrated in Table 1, Σ-Check is the first protocol to achieve logarithmic amortization for polynomial relations.
Experimental evaluations using a Rust implementation (arkworks) confirm these theoretical gains. Benchmarks across varying instance counts ($k$) and witness lengths ($m$) demonstrate the expected logarithmic growth in proof size and verifier time. Furthermore, because the protocol avoids FFTs, it remains memory-efficient for the prover, even as polynomial degrees increase.
4. Conclusion
Σ-Check provides a high-efficiency pipeline for proving complex polynomial constraints. By unifying amortization and compression through the sum-check protocol, it removes the linear communication costs associated with previous linearization techniques. Future work will focus on developing pre-built "proof gadgets" for common tasks like range checks and integrating the framework into general-purpose zero-knowledge argument systems.
Summary updated