TL;DR

It is expensive to run transactions on the Ethereum EVM. Verifiable computing (VC) lets us outsource computing away from the EVM. Today, a popular and exciting form of VC algorithm is the SNARK. There are various families of SNARKs that use the sum-check protocol, which is a simple algorithm to introduce VC. This is a tutorial on the sum-check protocol. This post is focused on how the sum-check protocol is implemented - it does not go into theory. You can skip straight to the finished code here. Thank you to Gokay Saldamli, Gabriel Soule, and Tomasz Kornuta for providing valuable feedback on this article.

Background

Executing code on Ethereum is expensive. Verifiable computing algorithms promise a way to reduce costs, by outsourcing computing to untrusted parties and only verifying the result on-chain. A key point about useful verifiable computing algorithms is that the verification must be less expensive than the original computation. The sum-check protocol is a foundational algorithm in the field of verifiable computing. In a stand-alone setting, sum-check is not particularly useful. However, it is an important building block of more sophisticated and useful SNARK algorithms. This tutorial introduces sum-check as a way to familiarize the reader with a relatively simple verifiable computing algorithm.

The sum-check protocol is used to outsource the computation of the following sum:

$$\begin{equation*} H := \sum_{x_1 \in {0,1}} \sum_{x_2 \in {0,1}} \cdots \sum_{x_v \in {0,1}} g(x_1, x_2, \cdots, x_v) \end{equation*}$$

The sum-check protocol allows a Prover $P$ to convince a Verifier $V$ that $P$ computed the sum $H$ correctly. You can assume that $P$ has ample computational power or ample time to compute, e.g., it could be an untrusted server somewhere on the internet, and $V$ is has limited computational power, e.g., it could be the EVM.

Why would you want to sum a function over all Boolean inputs, as is done in the equation above? One reason would be if you wanted to provide an answer to the #SAT (“sharp sat”) problem. #SAT is concerned with counting the number of inputs to a Boolean-valued function that result in a true output. For example, what is the #SAT of $f(x_1, x_2, x_3) = x_1 \text{ AND } x_2 \text{ AND } x_3$? It is 1, because only a single input, $x_1=1$, $x_2=1$, $x_3 = 1$, results in 1 being output from $f$. You can probably see that it would be computationally intensive for you to solve #SAT for complex problems. With the sum-check protocol, $P$ can do that work instead of you.

Unless you are a complexity theorist, you may not get too excited about the #SAT problem at first glance. However, more practical problems can be mapped to #SAT, and then sum-check can be used. For example, given an adjacency matrix, you can use sum-check to solve for how many triangles are connected. You can also use sum-check to outsource matrix multiplication. Check out the book mentioned next for more details.

In this tutorial, we use the same example as given in Justin Thaler’s book: Proofs, Arguments, and Zero-Knowledge. In Justin’s book, sum-check is used to solve #SAT for the following example function:

$$\begin{equation*} \phi(x_1, x_2, x_3, x_4) = (\bar{x_1} \text{ AND } x_2) \text{ AND } (x_3 \text{ OR } x_4) \end{equation*}$$

where $\bar{x_1}$ means NOT $x_1$. The function $\phi$ (phi) can also be represented graphically as:

In the graph of $\phi$, we see the logic symbols for AND ($\wedge$) and OR ($\vee$). Note that $\phi$ is only defined over the Boolean inputs (0/1) and that $\phi$ has a Boolean output. However, most popular verifiable computing algorithms only support arithmetic operations, so we need to convert $\phi$ to its arithmetic version. The arithmetized version is called $g$. For our example, $g$ is defined as:

$$\begin{equation*} g(x_1, x_2, x_3, x_4) = (1-x_1)x_2((x_3+x_4)-(x_3x_4)) \end{equation*}$$

and visualized as:

In $g$, notice that the Boolean functions: NOT, AND, OR have been compiled into their arithmetic equivalents. Take a moment to convince yourself that if you pick Boolean values for $x_1$, $x_2$, $x_3$, and $x_4$, that $\phi$ and $g$ will output the same thing.

For reference, here are the specific compiler rules used when converting $\phi$ into $g$:

Boolean gate	Arithmetized version
A AND B	A*B
A OR B	(A+B)-(A*B)
NOT A	1-A

Notice that $g$ has extended the domain of our original Boolean formula and is now valid for Boolean inputs and integers. The facts that $g$ equals $\phi$ when evaluated at Boolean inputs and that integers are valid inputs to $g$ are leveraged by the sum-check protocol.

The sum-check protocol

This section introduces the sum-check protocol. We will follow the same steps and naming convention as used in Justin’s book. The protocol steps are summarized as:

1. Prover $P$ calculates the total sum of $g$ evaluated at all Boolean inputs

2. $P$ computes a partial sum of $g$, leaving the first variable $x_1$ free

3. Verifier $V$ checks that the partial sum and total sum agree when the partial sum is evaluated at 0 and 1 and its outputs added

4. $V$ picks a random number $r_1$ for the free variable and sends it to $P$

5. $P$ replaces the free variable $x_1$ with the random number $r_1$ and computes a partial sum leaving next variable $x_2$ free

6. $P$ and $V$ repeat steps similar to 3—5 for the rest of the variables: $x_2, \cdots, x_v$

7. $V$ evaluates $g$ at one input using access to an “oracle”, i.e., $V$ must make a singled trusted execution of $g(r_1, r_2, \cdots, r_v)$

If $V$ makes it through Step 7 without error, then $V$ accepts $P$‘s proof. Otherwise, $V$ rejects.

We expand the steps of the algorithm in the following sections.

1. $P$ calculates the total sum of $g$ evaluated at all Boolean inputs

$H$ is the sum described in the first equation in this article. In round zero, $P$ should perform the summation described in the first equation. $P$ assigns this sum to $g_0$ and returns it to $V$. Note that this sum is the #SAT solution, i.e., it gives the answer of how many unique inputs to the function result in 1 being output from $g$. The remainder of the sum-check algorithm is designed to ensure that $P$ performed the #SAT solution correctly.

In our example, $g_0 = 3$ will be returned in Step 1. The following table shows $P$‘s work where the must iterate over all possible Boolean combinations of $x_1$,$x_2$, $x_3$, and $x_4$ and evaluate $g(x_1, x_2, x_3, x_4) = (1-x_1)x_2((x_3+x_4)-(x_3x_4))$:

$$\begin{aligned}g(0, 0, 0, 0) &= (1-0) \cdot 0 \cdot ((0 + 0)-(0 \cdot 0)) = 0\\ g(0, 0, 0, 1) &= (1-0) \cdot 0 \cdot ((0 + 1)-(0 \cdot 1)) = 0\\ g(0, 0, 1, 0) &= (1-0) \cdot 0 \cdot ((1 + 0)-(1 \cdot 0)) = 0\\ g(0, 0, 1, 1) &= (1-0) \cdot 0 \cdot ((1 + 1)-(1 \cdot 1)) = 0\\ g(0, 1, 0, 0) &= (1-0) \cdot 1 \cdot ((0 + 0)-(0 \cdot 0)) = 0\\ g(0, 1, 0, 0) &= (1-0) \cdot 1 \cdot ((0 + 1)-(0 \cdot 1)) = 1\\ g(0, 1, 1, 0) &= (1-0) \cdot 1 \cdot ((1 + 0)-(1 \cdot 0)) = 1\\ g(0, 1, 1, 0) &= (1-0) \cdot 1 \cdot ((1 + 1)-(1 \cdot 1)) = 1\\ g(1, 0, 0, 0) &= (1-1) \cdot 0 \cdot ((0 + 1)-(0 \cdot 1)) = 0\\ g(1, 0, 0, 1) &= (1-1) \cdot 0 \cdot ((0 + 1)-(0 \cdot 1)) = 0\\ g(1, 0, 1, 0) &= (1-1) \cdot 0 \cdot ((1 + 0)-(1 \cdot 0)) = 0\\ g(1, 0, 1, 1) &= (1-1) \cdot 0 \cdot ((1 + 1)-(1 \cdot 1)) = 0\\ g(1, 1, 0, 0) &= (1-1) \cdot 1 \cdot ((0 + 0)-(0 \cdot 0)) = 0\\ g(1, 1, 0, 0) &= (1-1) \cdot 1 \cdot ((0 + 1)-(0 \cdot 1)) = 0\\ g(1, 1, 1, 0) &= (1-1) \cdot 1 \cdot ((1 + 0)-(1 \cdot 0)) = 0\\ g(1, 1, 1, 0) &= (1-1) \cdot 1 \cdot ((1 + 1)-(1 \cdot 1)) = 0\end{aligned}$$

The outputs of the above evaluations are added to arrive at $g_0 = 3$.

2. $P$ computes a partial sum of $g$, leaving the first variable $x_1$ free

In Step 2, $P$ computes a similar sum as they did in Step 1, except the first variable is left free/unassigned. I.e.,

$$\begin{equation*} g_1(X_1) = \sum_{x_2 \in \{0,1\}} \sum_{x_3 \in \{0,1\}} \cdots \sum_{x_v \in \{0,1\}} g(X_1, x_2, \cdots, x_v) \end{equation*}$$

Note that $g_1$ is a monomial in $X_1$, and all other variables have been assigned values in each iteration of the loop. We refer to this monomial as the “partial sum” in the next step. Also observe that the only difference between the definition for $g_1$ and the definition for $H$ is that the $g_1$ summation is missing $\sum_{x_1 \in \{0,1\}}$.

For our example, $g(x_1, x_2, x_3, x_4) = (1-x_1)x_2((x_3+x_4)-(x_3x_4))$. To calculate $g_1(X_1)$, we leave $x_1$ free and then calculate the sum of $g$ evaluated at all possible Boolean combinations assigned to $x_2$, $x_3$, and $x_4$. The following table contains the intermediate calculations:

$$\begin{aligned}g(X1, 0, 0, 0) &= (1-X1) \cdot 0 \cdot ((0 + 0)-(0 \cdot 0)) = 0\\ g(X1, 0, 0, 1) &= (1-X1) \cdot 0 \cdot ((0 + 1)-(0 \cdot 1)) = 0\\ g(X1, 0, 1, 0) &= (1-X1) \cdot 0 \cdot ((1 + 0)-(1 \cdot 0)) = 0\\ g(X1, 0, 1, 1) &= (1-X1) \cdot 0 \cdot ((1 + 1)-(1 \cdot 1)) = 0\\ g(X1, 1, 0, 0) &= (1-X1) \cdot 1 \cdot ((0 + 0)-(0 \cdot 0)) = 0\\ g(X1, 1, 0, 0) &= (1-X1) \cdot 1 \cdot ((0 + 1)-(0 \cdot 1)) = (1-X1)\\ g(X1, 1, 1, 0) &= (1-X1) \cdot 1 \cdot ((1 + 0)-(1 \cdot 0)) = (1-X1)\\ g(X1, 1, 1, 0) &= (1-X1) \cdot 1 \cdot ((1 + 1)-(1 \cdot 1)) = (1-X1)\end{aligned}$$

After summing all the rows in the table, we get $g_1(X_1) = -3X_1 + 3$.

3. $V$ checks that the partial sum and total sum agree when the partial sum is evaluated at 0 and 1 and its outputs added

In Step 3, $V$ checks that $P$ was consistent with what they committed in Step 0 and Step 1. Specifically, $V$ checks the following:

$$\begin{equation*} g_0 \stackrel{?}{=} g_1(0) + g_1(1) \end{equation*}$$

In our example, $P$ sent $g_0 = 3$ and $g_1(X_1) = -3x_1 + 3$ to $V$ during Steps 1 and 2, respectively. So $V$ must now check that $3 \stackrel{?}{=} (-3 \cdot 0 + 3) + (-3 \cdot 1 + 3)$, which it does. If this check failed, then $V$ would end the protocol, and $P$‘s claim for $g_0$ (which is the supposed answer to the #SAT problem) would be rejected.

Note here what is happening: in Step 1, $P$ made a commitment to the #SAT answer. In Step 2, $P$ also did almost all of the work for $V$, except $V$ still needed to evaluate the monomial $g_1(X_1)$, at two points: $X_1=0$ and $X_1=1$. This is much less work than what $P$ must do.

Observe that at this point, $V$ doesn’t know whether the polynomial being evaluated by $P$ is actually the polynomial of interest, $g$. At this point, $V$ only knows $P$ has been consistent with the polynomial they have used. In fact, everything until Step 7 is only used to verify the consistency of $P$‘s answers. Step 7 resolves this uncertainty and is used to prove that $P$ has been both consistent and correct. This observation is one of the “slippery” aspects in understanding the sum-check protocol.

4. $V$ picks a random number $r_1$ for the free variable and sends it to $P$

Before beginning this step, it’s time to introduce a security aspect of the protocol. When the protocol starts, $V$ tells $P$ what finite field $\mathbb{F_p}$ they will be working with. This means that all numbers will be restricted (by using the modulus operator) to be between 0 and $p$. For example, if $P$ is told that $p=16$ then $P$ will reduce everything by mod 16, e.g. $74 \text{ mod } 16 = 10$ and $31x + 17 \text{ mod } 16 = 15x + 1$.

Next, $V$ picks a random number $r_1$ for $P$ to assign to $X_1$. $r_1$ is selected from the finite field $\mathbb{F}_p$. For the running example in this article, we will pick $p = 16$. From here on, all example calculations will be performed mod 16.

For the remainder of the protocol, $P$ will always replace $X_1$ with $r_1$. Note that something interesting is now happening. Up until this point, $P$ only evaluated $g$ with Boolean inputs, but now the protocol is leveraging the fact that because $g$ is a polynomial, it can be evaluated using arbitrary integers instead of only 0s or 1s. This is where the security of the protocol is derived: if $p$ is very large, it will be difficult for $P$ to guess the random challenges before receiving them.

For our running example, we will assume that $V$ selects $r_1 = 2$.

5. $P$ replaces the free variable $x_1$ with the random number $r_1$ and computes a partial sum leaving next variable $x_2$ free

$P$ calculates the sum again, except now they replace $X_1$ with the random number $r_1$:

$$\begin{equation*} g_2(X_2) =\sum_{x_3 \in \{0,1\}} \sum_{x_4 \in \{0,1\}} \cdots \sum_{x_v \in \{0,1\}} g(r_1, X_2, x_3, \cdots, x_v) \end{equation*}$$

For our example, near the end of Step 3, $P$ calculated $g_2(X_1, X_2) = -3X_1X_2 + 3X_2$. At the end of Step 4 above, we mention that $V$ selected $r_1 = 2$. So $P$ replaces $X_1$ with $r_1$, giving $g_2(X_2) = -3X_2$. $P$ returns $g_2(X_2) = -3X_2 \text{ mod } 16 = 13X_2$ to $V$.

6. $P$ and $V$ repeat steps similar to 3—5 for the rest of the variables: $x_2, \cdots, x_v$

Steps 3 through 5 above constitute one “round” of the protocol. In total, if $v$ is the number of variables in $g$, then $v$ rounds in total are required to complete the protocol. Each round includes the same operations as given in Steps 3 through 5 above, with the exception that different variables are left free each round.

For example, at the end of Step 5, $P$ returns $g_2(X_2)$ to $V$. If we apply the pattern in Step 3, noting that $g_1(r_1) = -3X_1 + 3 \text { mod } 16 = 13X_1 + 3$, we see that that $V$ must now check that:

$$\begin{aligned}g_1(r_1) \text{ mod } 16 &\stackrel{?}{=} (g_2(0) + g_2(1)) \text{ mod } 16 \\ (13 \cdot 2 + 3) \text{ mod } 16 &\stackrel{?}{=} (13 \cdot 0 + 13 \cdot 1) \text{ mod } 16 \\ 13 \text{ mod } 16 &\stackrel{\checkmark}{=} 13 \text{ mod } 16\end{aligned}$$

So round 2 passes.

In our example, $g$ has four variables, so we will cycle through Steps 3—5 four times, then we move to Step 7.

7. $V$ evaluates $g$ at one input using access to an “oracle”, i.e., $V$ must make a singled trusted execution of $g(r_1, r_2, \cdots, r_v)$

After round $v$ has successfully been checked, then $g_v(X_v)$ has incorporated $r_1, r_2, \cdots, r_{v-1}$. The last step is for $V$ to select $r_v$ and use an oracle to evaluate $g(r_1, r_2, \dots, r_v)$. The oracle is a trusted source which will be guaranteed to evaluate $g$ correctly at a single input. Alternatively, if no oracle is available, then $V$ must compute $g$ once by itself. Without an oracle, $V$ would be required to store and compute $g$ — this could be costly.

After $g(r_1, r_2, \dots, r_v)$ is provided by the oracle, or computed by $V$ itself, then $V$ checks:

$$\begin{equation*} g(r_1, r_2, \dots, r_v) \stackrel{?}{=} g_v(r_v) \end{equation*}$$

If this check passes, then $P$ accepts $V$‘s claim that $g_0$ is equal to $H$, or, in our example, that $g_0$ is the #SAT of $g$.

Conclusions and further reading

Python code implementing sum-check can be found in this repo. We omitted security checks in this tutorial for brevity, but those checks are included in the linked repo. Also, this article did not explain why sum-check is secure, nor did it cover the practical costs of the algorithm. Briefly, the security of sum-check can be analyzed using the Schwartz–Zippel lemma — it is basically like random sampling used for quality control. Regarding the costs, to solve #SAT without the sum-check protocol, $V$ would have had to evaluate $g$ at $2^v$ inputs, but with sum-check, the cost for $V$ drops to $v$ steps of the protocol plus a single evaluation of $g$. If you want more depth, see Justin’s book, which is linked above, and these resources:

1. Sum-check article by Justin Thaler: The Unreasonable Power of the Sum-Check Protocol

2. Sum-check notes by Edge & Node cryptographer, Gabriel Soule: https://drive.google.com/file/d/1tU50f-IpwPdCEJkZcA7K0vCr7nwwzCLh/view

If you have made it this far, you now hopefully have a feel for how interactive arguments of knowledge work. This is the first time we have mentioned “interactive”. Note that $P$ and $V$ had to communicate in each round. This is not ideal in scenarios where computers can go offline, i.e., the real world. The Fiat–Shamir transform makes sum-check non-interactive. As you may know, SNARKs also eliminate interactions, as implied by the “N” in the name which stands for “Non-interactive”. SNARKs also use Fiat-Shamir. Perhaps we will make a part 2 of this article where we implement a non-interactive version of sum-check.