# Sum-Check as an Algebraic Tensor Reduction: Part I

- **Authors**: Nicolas Mohnblatt, Marco Besier
- **Date**: April 27, 2026
- **Tags**: sum-check, algebraic reductions of knowledge, tensors

![Thumbnail image](https://blog.zksecurity.xyz/posts/tensor-reductions-1/top.png)

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](https://eprint.iacr.org/2022/009). 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](https://youtu.be/XV62OB022tU?si=8MlVwFJjf_YCW0BN).

**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](https://people.cs.georgetown.edu/jthaler/ProofsArgsAndZK.pdf).

**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](https://sumcheck.zksecurity.xyz/).

## 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,
$$

## 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](#bcc16), [BBB+18](#bbb18), [BMM+21](#bmm21), [BCS21](#bcs21)], aggregation schemes for polynomial commitments [[BGH19](#bgh19), [BDFG21](#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](https://yoichihirai.com/), [Varun Thakore](https://varunthakore.github.io/), and [Youssef23](https://github.com/youssef23youssef) for spending their valuable time helping us polish this post.

#### Footnotes

[¹](#fnref1) 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.

---

This article was published on the [ZK/SEC Quarterly](https://blog.zksecurity.xyz) blog by [ZK Security](https://www.zksecurity.xyz), a leading security firm specialized in zero-knowledge proofs, MPC, FHE, and advanced cryptography. ZK Security has audited some of the most critical ZK systems in production, discovered vulnerabilities in major protocols including Aleo, Solana, and Halo2, and built open-source tools like [Clean](https://github.com/Verified-zkEVM/clean) for formally verified ZK circuits. For more articles, see the [full list of posts](https://blog.zksecurity.xyz/llms.txt).