Paper 2026/1469

MULTILINEAR POLYNOMIALS VIA TREE-BASED CIRCUIT AND THE SUMCHECK PROTOCOL

Abstract

The Sumcheck protocol is a cornerstone of modern proof systems, yet its prover remains a performance bottleneck. Even in the multilinear case, the repeated construction of round polynomials leads to significant overhead, limiting scalability in practice. We take a different approach: instead of modifying the protocol, we rethink the representation of multilinear polynomials. We show that any multilinear polynomial admits a simple and structured binary-tree circuit representation, where each node follows a clean recursive rule. This perspective is not merely conceptual; it directly translates into faster algorithms. Our circuit view unifies three core operations: evaluation, summation over the Boolean hypercube, and Sumcheck round generation within a single framework. Construction from the coefficient vector costs exactly nN field operations, and evaluation via bottom-up folding requires exactly N − 1 multiplications — optimal for this class of algorithms. A key structural property of the circuit is its regularity: fixed depth, local recurrences, and no data-dependent branching. This is not incidental — it is a direct consequence of the recursive decomposition, and it is precisely what makes the representation amenable to parallel execution and hardware acceleration. We implement our approach in Rust on the BN254 scalar field and benchmark it against ark-poly with parallelism enabled on both sides. At n = 20, our parallel evaluation kernel achieves a 3.4× speedup over ark-poly (14 ms vs 48 ms). The verifier completes in under 1 μs across all tested dimensions, yielding a prover-to-verifier ratio exceeding 105 at n = 20. Our results suggest that revisiting polynomial representations is a promising direction for accelerating fundamental primitives in proof systems.

Note: Corrected a typo in the first author's email address (algoizk → algorizk). No technical changes.