DSS 2026 — The Sumcheck Algorithm from First Principles Jeffrey Scholz Source video: https://www.youtube.com/watch?v=Jk4JrZFmoYc Automatic captions — not human-reviewed. Complete spoken-audio coverage is unverified. Source language tag: en (English). Source export SHA256: f09e218a7befb6039d3c76963f6fecfc7ff19dd35b6553b30465055fea253458 [0:00] All right. [0:01] So, hello everyone. My name is um [0:04] Jeff. [0:05] And we'll be talking about the sum check [0:08] protocol, which is actually quite [0:09] simple, but it I don't I haven't seen a [0:11] good explanation for the intuition [0:13] behind it or how you could have [0:14] discovered it on your own if you wound [0:15] back about 10 years or so. Or no, 1990 [0:18] was 26 years ago. [0:20] So, let's look at [0:22] the underlying mechanics. [0:26] Now, what is the problem statement? So, [0:27] let's say we have a polynomial like the [0:29] one shown on the screen. It's a function [0:31] of several variables, X1, X2, and X3. [0:34] And what we're going to do is we're [0:35] going to pick a subset from the domain. [0:38] And by convention, that subset is called [0:41] the Boolean hypercube, which just means [0:43] all of the [0:44] X values are 0 or 1. [0:47] And [0:48] that's going to form a set of eight [0:49] points. We can, of course, plug that [0:52] these points into the polynomial, like [0:54] you see on the right over there. And [0:55] then that's going to give us an [0:56] evaluation. So, if we plug 0 0 0 into [0:59] this polynomial, we're going to get two, [1:00] which is why you see two as the first [1:02] entry and the sum over there. When we [1:04] add them all up, we're going to get 34. [1:06] Nothing surprising there. [1:12] The question though is if somebody told [1:14] us [1:15] next slide. [1:18] The question though is if somebody told [1:19] us, hey, [1:20] I evaluated the sum of polynomials in [1:23] this manner [1:25] and this is the sum. So, 34 is the sum. [1:27] Can you check their answer without [1:29] actually adding up evaluating all the [1:30] points yourselves and then adding them [1:32] up? [1:33] And why would we care about that? Well, [1:34] because [1:35] the Boolean hypercube, the set of [1:37] variables where they're all 0 or 1, [1:38] doubles every time you add another [1:40] variable to the polynomial, right? So, [1:42] if we have two variables, then we're [1:43] going to evaluate it on four entries. If [1:45] we have three variables, we're going to [1:47] evaluate it on eight entries, so forth [1:49] and so on until we get to 30 variables, [1:51] then that's going to be over a billion [1:52] entries. And we don't want to run a [1:54] billion terms in our sum if we don't [1:56] have to. [1:58] And something I should emphasize is that [1:59] even though a terms is a lot, the [2:01] polynomial itself is not that big, [2:02] right? You could probably evaluate this [2:04] polynomial in one millisecond on a [2:05] Raspberry Pi. [2:07] The challenge is doing it a billion [2:09] times and then adding things up. So we [2:11] want to say [2:12] if you tell me that I know the sum to [2:14] this and the sum is this, how can I [2:16] check it without re-running the whole [2:17] computation? [2:20] Uh okay. [2:21] Uh forward. Sorry. So one way we might [2:24] start is well trees tend to give a nice [2:27] structure, right? We don't want to just [2:28] put it into a list and then add it [2:29] because it's not going to give us any [2:30] shortcuts. So let's add it as if it's a [2:32] tree. [2:33] And as you can see here, each of the [2:35] leaves is the polynomial evaluated at a [2:39] particular point in the Boolean [2:40] hypercube, right? So oh this is behind [2:42] the podium, but you can see the math, [2:44] right? [2:45] And then each parent of those leaves is [2:47] going to be what I'm going to call a [2:48] partial sum. You can see 2 + 2 is 4, 5 + [2:50] 5 is 10, blah blah blah. And we'll keep [2:52] doing the partial sums until we get to [2:53] the root and 34 was the original sum of [2:56] the polynomial. [2:58] Now how's the verifier going to check [2:59] this? The verifier can't check the [3:01] entire tree. So what do we do? [3:03] We typically default to random sampling, [3:04] right? [3:05] So what we're going to say is hey uh [3:07] prover, give me the children of the [3:10] root, the partial sums there. If you [3:12] computed everything correctly, they [3:13] should add up to 34. [3:14] And the prover says sure, 14 and 20. [3:19] And again, the verifier can't pick both [3:21] sides of the tree, too big. So we'll [3:23] make a random choice. We'll randomly go [3:24] down the 20 branch. Hey prover, what are [3:27] the children of 20? [3:28] 7 and 13. [3:30] Now something I should emphasize is the [3:31] prover could be lying about this, right? [3:33] The verifier has is like is not anchored [3:35] to anything in the real world. But when [3:36] we get to the leaves, [3:39] like I said, the polynomial is cheap to [3:40] evaluate. The the verifier can say well, [3:43] okay, you say the [3:44] the the children of seven are three and [3:46] four, but I'm actually going to evaluate [3:48] the polynomial at 100 and 101. [3:50] And then out comes three and four. Okay, [3:53] turns out the prover was honest. I [3:54] believe that. [3:57] The [3:58] challenge though is how reliable is this [4:00] protocol when the prover lies? So let's [4:02] say the prover says it's 35 instead of [4:04] 34. [4:06] Well, to make this lie believable, the [4:08] prover needs to update the children of [4:09] 35 so that it adds up to 39, right? [4:12] So, they'll update 20 to become 21 and [4:15] then that lie has to propagate down [4:16] because if if the verifier picks 21, [4:18] then you they want to see that 7 + 14 is [4:20] 21 and so forth. The challenge for the [4:24] prover will be once the verifier hits [4:26] the leaf, [4:28] then the prover can't lie anymore [4:30] because 6 + 7 is not 14. [4:33] Okay? [4:33] Uh [4:34] a challenge for the verifier though is [4:36] that in all of these other cases though, [4:38] the leaves do actually add up to their [4:39] parent. [4:41] So, if the verifier [4:45] um [4:47] I'm sorry, there's a massive lag here. [4:49] Okay. If the verifier if the prover lies [4:51] in only one leaf, what's the chance that [4:54] the verifier randomly picks a path and [4:56] then finds out that leaf or they don't [4:58] add up to the parent? Probably not high, [5:00] right? If the tree is quite large. [5:02] So, what we need to do is we need to [5:04] amplify the chances that the verifier is [5:05] going to find a dishonest node. [5:09] So, we're going to add a couple couple [5:10] tools to our toolkit. The first one is [5:12] that we can conveniently label the [5:13] edges, right? If you go down one [5:15] particular branch, like say x 1 is equal [5:17] to 1, then notice that every evaluation [5:19] has x 1 plugged in. All right? That will [5:21] become handy later. [5:22] Uh go forward. [5:25] And the other thing that we're going to [5:27] do is instead of just giving the two [5:29] children as the raw value 14 and 20, we [5:32] need to tie them together somehow so [5:34] that when you lie about one, it creates [5:35] lies elsewhere. And polynomials are a [5:37] very natural way to do that. So, instead [5:39] of giving 14 and 20, give me 6 x 1 + 14 [5:42] because at 0, remember the the branches [5:44] are just evaluations. [5:46] At 0, it gives you 14 and 1, it gives [5:48] you 20. Now, of course, an issue there [5:50] is [5:51] well, if I wanted to lie about one of [5:53] the children, I'll I'll just change the [5:54] polynomial. No problem, right? [5:56] Uh so we need to But luckily, we can [5:58] handle that a little more easily this [5:59] time. [6:00] Let's say somehow we add more leaves to [6:02] the tree rather than just having a QRA a [6:04] two-ary tree, we're going to have a [6:05] ternary tree. [6:07] What does that even mean? Because we [6:08] don't care about the branches where x is [6:10] equal to 2, we only care about the [6:11] branches where x is equal to 1. I'll get [6:13] to that, but just somehow we add extra [6:15] children. [6:17] And we can say, well, I'm going to not [6:19] only add extra children, but I'm going [6:21] to force that all of the values of those [6:22] nodes lie on a line. [6:25] Okay? So when you give me a polynomial [6:27] prover, you need to give me a linear [6:29] polynomial. [6:30] And if it's not a linear polynomial, I [6:31] know you do something fishy. [6:34] And [6:35] when the prover wants to lie about, hey, [6:37] I want to make 14 and 20 add up to 34, [6:39] well, I'm going to push 20 up to 21 so [6:41] that it adds up to 35. Now, well, now [6:42] they have to lie about a third node. So [6:44] it was 26 became 28 so that they all lie [6:46] on a straight line. [6:47] So now the lie is affecting more more [6:49] nodes. [6:53] Uh next slide. [6:55] But then, okay, so if we're going to add [6:56] more leaves to the add more nodes to the [6:58] tree, then what what exactly should [6:59] those nodes contain? Because right now [7:01] we only care about the nodes that are [7:02] shown here. [7:03] Well, we'll just follow the same pattern [7:04] that we have been doing. Notice that [7:06] every node here is the sum of its left [7:08] two children. [7:10] Okay? [7:10] And the leaves are just evaluations. So [7:14] next slide. [7:17] So here we add g of 0 0 2 for example. [7:19] Oh, you can't see that. Wait, we added 2 [7:21] as a potential evaluation, but that [7:23] doesn't change the parent leaves. The [7:25] parent leaves still only sum the left [7:26] two children. [7:27] Okay? So what do we do with the rest of [7:29] the empty nodes? We just say they're the [7:30] sum of their left two children, which is [7:31] when x is equal to 0 or equal to 1. Next [7:33] slide. [7:35] Uh okay, next slide. Keep keep going. [7:37] All right, wait, stop there. Yep. [7:39] Right. So every node is the sum of its [7:41] left two children. And the third leaf [7:44] it's just we're evaluating it outside [7:45] the domain that we the subset that we [7:47] care about. Okay, next slide. [7:50] Next slide. [7:52] Now [7:53] I can't show the animation because this [7:55] is a PowerPoint and this was originally [7:56] written in HTML, but uh [7:59] notice that any node you pick, all of [8:01] its children are equally spaced apart, [8:03] which means if you plot them against 0 1 [8:04] 2, they're going to lie on a line. [8:07] So any node you pick, all of its [8:08] children lie on the line. [8:10] Next slide. [8:11] Okay. So, how can we verify in this [8:13] setting? Next slide. [8:16] The prover uh [8:18] is going to construct a tree and the [8:20] verifier asks for the polynomial. So, [8:22] what polynomial crosses 14 20 26? Well, [8:24] it's still the same one. [8:26] Now, the prover will check Remember, the [8:27] rule is that the left two nodes need to [8:28] add to their parent. So, we'll the left [8:30] two nodes because it interpolates the [8:31] children, we'll just say we'll evaluate [8:33] g of 0, we'll evaluate g of 1 and add [8:34] them together. And then that's supposed [8:36] to equal the node that we're currently [8:37] at. [8:38] If that If that sum doesn't hold, then [8:40] clearly the whole thing is false. And if [8:41] the polynomial received is not linear, [8:44] then [8:45] the f the prover did something fishy. [8:46] Okay. Next slide. [8:48] And the check keeps repeating. We check [8:49] that the left two nodes went add up to [8:51] the parent. But I I want to stress that [8:52] we're not the ver prover is not actually [8:54] handing 7 and 13 back. They're handing a [8:55] polynomial that you evaluate at 0 and 1 [8:57] and then that's how you get 7 and 13 out [8:59] of it. [9:00] Okay? So, do the do the left two nodes [9:02] add up to the parent? And is the [9:03] polynomial I got a straight line? [9:06] Next slide. [9:07] And we keep doing this. Next slide. [9:10] Until we get to a leaf where we actually [9:12] arrive at the ground truth. So, how does [9:13] this help us? Next slide. [9:15] Next slide. [9:17] If the prover lies about one leaf, then [9:18] that's going to mess up a a the other uh [9:22] children or the siblings, right? Next [9:24] slide. [9:25] And then that lie will force the prover [9:27] to [9:28] Next slide. [9:29] Sorry. [9:31] Uh [9:31] that that lie is going to force the [9:33] prover to propagate the lie down until [9:35] eventually we are Next slide. [9:38] Sorry, guys. It's really hard without [9:39] the clicker. [9:40] [laughter] Um until eventually we hit [9:42] the point where the children no longer [9:44] add up to their parent. So, 9 and 10 [9:46] used to add up to 19, but now it add it [9:47] does now in 21 is there. So, there's [9:49] wherever there's a red box, if the [9:51] verifier happens to pick that path, they [9:53] will are guaranteed to eventually hit a [9:54] point where the children where the [9:57] leaves don't add up to their parent. [10:01] Okay? [10:02] Next slide. [10:05] Now, the ch challenge here is well, at [10:08] at every branch we have a two out of [10:10] three chance of catching the prover, [10:11] which is good, but two out of three is [10:12] not cryptographically secure. So, how do [10:14] you make two out of three bigger? Well, [10:16] you just make your tree bigger. Next [10:17] slide. [10:19] And since we're working in a finite [10:21] field, so everything is done modulo Q, [10:23] we can have as many as Q branches. [10:25] Next slide. [10:27] Now, that leaves a question. Okay, if we [10:29] have Q branches and you have a big [10:31] finite field, how is the prover actually [10:32] going to interpolate that polynomial? [10:33] That's kind of crazy, right? [10:36] Uh, [10:37] so we need a shortcut to not actually [10:39] explicitly [10:41] create this entire tree. [10:42] Uh, otherwise it's it it's just the [10:44] exponentials are just crazy. [10:47] Next slide. [10:49] Okay, so here's how we're going to do [10:50] it. Again, like I said, every [10:52] node [10:54] is the sum of its [10:56] left two children, and that propagates [10:57] upward. You can say in general that a [10:58] given intermediate node is the sum of [11:00] all the Boolean leaves underneath it, [11:03] right? [11:05] So, [11:06] again, one more slide. [11:09] So, what does that mean? If you want to [11:10] know what's the polynomial that [11:11] represents a certain level, [11:14] then [11:16] that level, you leave that variable free [11:19] and you sum up all of the Boolean leaves [11:20] afterwards. That's what you can see [11:23] right here. [11:24] Right? So, X2 is free and we're only [11:26] going to sum up all of the Boolean [11:27] leaves afterwards. [11:29] So, only these leaves get summed up and [11:30] we're free to [11:32] pick any direction we want to because X [11:33] two is not chosen, [11:35] but X one is how we arrived at that [11:37] point. [11:39] So, this sum over here [11:42] is going to capture only [11:44] these, [11:45] and then that's going to create the [11:47] that that's going to actually generate [11:49] the the polynomial over here. [11:51] Uh, next slide. [11:53] So, generally [11:55] the interpolation polynomial is what's [11:56] the path the random path the verifier [11:57] took so far? [11:59] Leave the next variable free, sum up all [12:01] the Boolean leaves using the same [12:03] polynomial. [12:05] Next slide. [12:06] And then that gives us the algorithm. [12:10] So, if you ask whatever your favorite AI [12:12] is, hey, give me the sum check protocol [12:14] call. It's going to spit this out. [12:16] But what does it actually mean? [12:18] Well, we start with our polynomial. Give [12:19] me the polynomial that interpolates the [12:20] children. I'm just going to check that [12:22] the left two children add up to the sum, [12:23] then I'm going to pick a random path. [12:26] Then I'm going to repeat. [12:28] Okay, I've taken this random path. I'm [12:29] going to leave this variable free and [12:31] I'm going to sum up over the rest of [12:32] them. [12:33] That's going to give me the next [12:34] interpolating polynomial. Now I'm going [12:36] to check, do the left two [12:38] children add up to the node I was just [12:40] at? Okay, I'm going to pick a random [12:42] path again [12:43] until we get to the leaves. [12:45] And then we're done. [12:49] So that is [12:50] how the sum check protocol works and [12:52] that's the geometric interpretation of [12:55] what the AI tells you.