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