This blog post series will give you a gentle introduction to algebraic tensor reductions, a unifying way to describe recursive protocols, as defined in Kothapalli’s and Parno’s Algebraic Reductions of Knowledge. Reductions of knowledge are a generalization of arguments of knowledge, which reduce checking knowledge of a witness in one relation to checking knowledge of a witness in another (simpler) relation.
This series is not trying to explain the whole paper, though. Instead, we will narrowly focus on the paper’s Appendix C: Recovering the Sum-Check Protocol, as sum-check is one of the ideal motivating examples for algebraic tensor reductions. Appendix C is well-written and already quite explicit. Still, being part of an academic paper, it’s not what most people would call an easy read.
Therefore, the main goal of this series is to give you a full understanding of sum-check as a tensor reduction by adding more context, examples, and explainers to what’s already present in Appendix C of the paper.
The game plan is as follows:
Part I: Sum-Check as a Recursive Algebraic Reduction This post. We briefly revisit one recursive step of sum-check and explain why it is a good motivating example for a tensor reduction.
Part II: The Tensor Language We Need We introduce modules, direct sums, tensor products, and tensor evaluation statements.
Part III: Tensor Reduction and Linearized Polynomials We explain the tensor reduction itself and then specialize it to multivariate polynomials represented in linearized form.
Part IV: Recovering Sum-Check From a Tensor Reduction We follow Appendix C directly and align one step of the ordinary sum-check with one step of the linearized tensor-reduction protocol.
Prerequisites
While we tried to keep these posts as self-contained as possible, we assume familiarity with the sum-check protocol and basic mathematical concepts such as fields, polynomials, and matrices.
If you are unfamiliar with sum-check, we recommend the following resources, depending on the time you want to invest and the depth of understanding you are looking for:
Minimal time investment (6 minutes) for a high-level overview, which is sufficient background for this series: video explainer by David Wong.
Medium time investment (1–3 hours) for a solid understanding of the basic protocol: Section 4.1 of Justin Thaler’s Proofs, Arguments, and Zero Knowledge.
High time investment (1–5 days) for an implementation-oriented deep dive, including sum-check’s connection to more advanced polynomial IOPs such as zero-check and product-check: interactive sum-check tutorial by zkSecurity.
One Recursive Step of Sum-Check
We start by fixing a field $\mathbb{F}$, a polynomial $P\in \mathbb{F}[x_1,...,x_n]$, and a claimed sum $\sigma\in \mathbb{F}$ such that
$$ \sum_{x_1,...,x_n\in \{0,1\}}P(x_1,...,x_n)=\sigma. $$A single recursive step of sum-check proceeds as follows: The prover starts by sending the univariate polynomial
$$ p(X)=\sum_{x_1,...,x_{n-1}\in \{0,1\}}P(x_1,...,x_{n-1},X). $$The verifier then performs what we’ll call the sum consistency check:
$$ p(0)+p(1)=\sigma $$If that passes, the verifier samples a random challenge $r\in \mathbb{F}$ and reduces the original $n$-variate claim to the $(n-1)$-variate claim
$$ \sum_{x_1,...,x_{n-1}\in \{0,1\}}P(x_1,...,x_{n-1},r)=p(r). $$Notice that the verifier does not resolve the original claim immediately. Instead, the verifier asks for an intermediate object, makes a brief consistency check, and then transforms the original claim into a simpler claim of the same general form.
To make the reduction to a simpler claim even more apparent, let’s define $P^\prime(x_1,...,x_{n-1}):=P(x_1,...,x_{n-1},r)$ and $\sigma^\prime:=p(r)$. Then, our reduced sum-check claim reads
$$ \sum_{x_1,...,x_{n-1}\in \{0,1\}}P^\prime(x_1,...,x_{n-1})=\sigma^\prime, $$which is structurally equivalent to the original claim, only with one variable less.¹
A Small Example
Take the bivariate polynomial $P\in \mathbb{F}[x_1,x_2]$, given as
$$ P(x_1,x_2)=a_0+a_1x_1+a_2x_2+a_3x_1x_2, $$where $a_0,...,a_3\in \mathbb{F}$ denote the coefficients. The original sum-check claim is
$$ P(0,0)+P(0,1)+P(1,0)+P(1,1)=\sigma, $$where $\sigma\in \mathbb{F}$ denotes the target sum. The honest prover starts by sending
$$ \begin{align*} p(X)&=P(0,X)+P(1,X)\\ &=(a_0+a_2X)+(a_0+a_1+(a_2+a_3)X)\\ &=2a_0+a_1+(2a_2+a_3)X. \end{align*} $$The verifier then checks $p(0)+p(1)=\sigma$. Indeed, we have
$$ \begin{align*} p(0)+p(1)&=(2a_0+a_1)+(2a_0+a_1+2a_2+a_3)\\ &=4a_0+2a_1+2a_2+a_3\\ &=P(0,0)+P(0,1)+P(1,0)+P(1,1)\\ &=\sigma. \end{align*} $$The verifier then samples a random $r\in \mathbb{F}$, and reduces the original claim to
$$ P'(0)+P^\prime(1)=P(0,r)+P(1,r)=p(r)=\sigma^\prime, $$where we defined $P^\prime(x_1):=P(x_1,r)$ and $\sigma^\prime:=p(r)$. In other words, the two-variable sum-check claim has become a one-variable sum-check claim.
While this example is trivial to understand, it nicely illustrates the core structure of the protocol: One variable is peeled off, a univariate summary is sent, a boundary identity is checked (sum consistency check), and the remaining burden is pushed into a smaller instance.
The General Pattern
The above example shows that one recursive step of sum-check has a very rigid structure: First, the original claim is split according to an internal decomposition of the underlying object (i.e., one treats an $n$-variate polynomial as a polynomial in “one variable plus the remaining $n-1$ variables”). Second, the prover sends an object that summarizes the effect of that split. Concretely, that object is the univariate polynomial $p$. Third, the verifier performs a consistency check. (This is what we earlier referred to as the “sum consistency check” $p(0)+p(1)=\sigma$.) Finally, the verifier uses randomness to fold the unresolved consistency question into a smaller claim by evaluating at a random point $r\in \mathbb{F}$. In particular, the verifier’s output is not “accept” or “reject,” but a simpler instance of the same general problem.
This recursive nature of the protocol is precisely why sum-check is a great motivating example for understanding algebraic tensor reductions: the protocol already looks like a general reduction. The tensor formalism we’ll discuss later in this series merely helps to make this mechanism more explicit, and provides a unifying language that covers not only sum-check, but all protocols that rely on similar interactive reductions such as inner-product arguments [BCC+16, BBB+18, BMM+21, BCS21], aggregation schemes for polynomial commitments [BGH19, BDFG21], etc.
In other words, one step of sum-check is not just a polynomial identity check. Instead, it is better viewed as a recursive algebraic reduction.
What’s Ahead
At this point, it’s worth restating the scope: This blog post series is not a survey of all recursive arguments covered by Kothapalli’s and Parno’s paper. It is also not a detailed tour of the full theory of algebraic reductions of knowledge. However, we will help you develop a solid understanding of
- the mathematical tooling for algebraic tensor reductions,
- the “tensorized” version of the sum-check protocol (a.k.a. linearized sum-check),
- and the structural equivalence between classical and linearized sum-check.
With that, you’ll be well-equipped to venture out and explore the wider theory of algebraic reductions of knowledge on your own.
In the next post, we’ll start by introducing the minimum algebra needed to express sum-check as an algebraic tensor reduction. We’ll talk about modules, direct sums, tensor products, and tensor evaluation statements. Once that language is established, the transition from classical to linearized sum-check will be straightforward.
Acknowledgements
Special thanks to Yoichi Hirai, Varun Thakore, and Youssef23 for spending their valuable time helping us polish this post.
Footnotes
¹ Strictly speaking, we’re also introducing a new claim $P^\prime(x_1,\ldots,x_{n-1}) := P(x_1,\ldots,x_{n-1}, r)$here. For our two sum-check claims, $\sum_{x_1,...,x_n\in \{0,1\}}P(x_1,...,x_n)=\sigma$ and $\sum_{x_1,...,x_{n-1}\in \{0,1\}}P^\prime(x_1,...,x_{n-1})=\sigma^\prime$, to be truly equivalent, the verifier needs to check $P^\prime(x_1,\ldots,x_{n-1}) = P(x_1,\ldots,x_{n-1}, r)$, too. In practice, these checks are usually deferred until the very end of the recursive loop, and manifest as a single evaluation check of $P$ at a random point $\textbf{r}\in \mathbb{F}^n$. The attentive reader may also notice that we omit the usual degree conditions. In the full sum-check protocol, the verifier also checks that the prover’s message $p$ has the expected degree bound. We leave that part aside here because it is not needed to understand the recursive reduction pattern that this post focuses on.
References
[KP22] Abhiram Kothapalli and Bryan Parno, Algebraic Reductions of Knowledge. In Advances in Cryptology–CRYPTO 2023, pages 669–701, Cham, 2023. Springer Nature Switzerland.
[T22] Justin Thaler, Proofs, Arguments, and Zero-Knowledge. In Foundations and Trends in Privacy and Security: Vol. 4, No. 2–4, pp 117–660, 2022. DOI: 10.1561/3300000030.
[BCC+16] Jonathan Bootle, Andrea Cerulli, Pyrros Chaidos, Jens Groth, and Christophe Petit. Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In Advances in Cryptology–EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II 35, pages 327–357. Springer, 2016.
[BBB+18] Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. Bulletproofs: Short proofs for confidential transactions and more. In 2018 IEEE symposium on security and privacy (SP), pages 315–334. IEEE, 2018.
[BMM+21] Benedikt Bünz, Mary Maller, Pratyush Mishra, Nirvan Tyagi, and Psi Vesely. Proofs for inner pairing products and applications. In Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part III 27, pages 65–97. Springer, 2021.
[BCS21] Jonathan Bootle, Alessandro Chiesa, and Katerina Sotiraki. Sumcheck arguments and their applications. In Advances in Cryptology–CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part I 41, pages 742–773. Springer, 2021.
[BGH19] Sean Bowe, Jack Grigg, and Daira Hopwood. Recursive proof composition without a trusted setup. Cryptology ePrint Archive, Paper 2019/1021, 2019.
[BDFG21] Dan Boneh, Justin Drake, Ben Fisch, and Ariel Gabizon. Halo infinite: Proof-carrying data from additive polynomial commitments. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, pages 649–680, Cham, 2021. Springer International Publishing.