DSS

DSS 2026 / Day 1 / Pearl Hall

The Sumcheck Algorithm from First Principles

Jeffrey Scholz

12:58 · Recording

Watch on YouTube ↗Open recording viewerOriginal programme entry
Download plain textDownload timestamped JSON

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

Source export SHA256: f09e218a7befb6039d3c76963f6fecfc7ff19dd35b6553b30465055fea253458