Background
In late 2023, Justin Thaler posted a paper on optimized sumcheck for fields of small characteristics. Having experience with low-level hardware-optimized modular multiplication, Yuval Domb began exploring ways to further optimize Justin’s results using his extensive knowledge of efficient multiplication techniques. He wondered if the Karatsuba algorithm could be applied to reduce the number of base-field multiplications in Justin’s optimized sumcheck prover algorithm (referred to as Algorithm 3 in the paper).
The Karatsuba algorithm reduces the number of multiplications needed for two large integers from four to three, offering a 25% improvement. While this may seem modest, Justin helped us see that even small improvements are significant in the context of the sumcheck protocol over smaller fields. This is particularly relevant as commitment schemes like the one in Binius have become so efficient that the sumcheck protocol could become a bottleneck in SNARKs. Thus, we focused on incorporating the Karatsuba algorithm into Justin’s Algorithm 3 for the case when the sumcheck polynomial degree is
𝑑 = 2. The two main challenges were:
- For the 𝑑 = 2 case, how do we apply the Karatsuba algorithm across multiple rounds of the sumcheck protocol?
- If we solve the first challenge, how do we generalize the Karatsuba algorithm to any degree 𝑑 > 2 ?
We successfully optimized Justin’s algorithm, reducing the number of base-field multiplications in the sumcheck protocol over small fields from O(2ᵈ) to O(d) using a generalized Karatsuba algorithm. We refer to this as Algorithm 4. The details of both Algorithms 3 and 4 are presented in our recent paper[1], co-authored with Justin. In this blog, we explain the motivation behind our work and how our algorithms can improve the sumcheck protocol over binary fields. We also provide a high-level overview of how the two algorithms function.
Links
Paper: https://eprint.iacr.org/2024/1046
Code: Smallfield-super-sumcheck: https://github.com/ingonyama-zk/smallfield-super-sumcheck
