The Gold Standard of Zero-Knowledge Proofs | Bounding Sum-Check Error When Challenges Are Biased or Predictable

A nonzero univariate polynomial of degree at most d over a field has at most d distinct roots. That fact concerns the polynomial. It does not say that every root is equally likely to be sampled by a particular challenge generator.

Suppose a polynomial has one root in a seventeen-element field. Under uniform sampling, that root is selected with probability one-seventeenth. If the challenge source assigns half its probability to that same point, the probability becomes one-half. The polynomial did not acquire extra roots; the distribution changed.

Write these as separate lines in a solution: how many agreement points are possible, and how much challenge probability can lie on them? Only then combine the two. This makes the source of the error bound visible and prevents field size from being used as a substitute for evidence about the sampling law.

The Georgetown sum-check notes provide the standard protocol and soundness context. Our weighted examples investigate a changed sampling assumption rather than propose a correction to that standard theorem.

Contents · Next chapter

We use the field of integers modulo seventeen, written F17. Addition and multiplication are followed by reduction modulo seventeen. Thus eighteen represents one, thirty-four represents zero and minus one represents sixteen.

Every nonzero field element has a multiplicative inverse. For example, ten is the inverse of twelve because 12 × 10 = 120, whose remainder modulo seventeen is one. Division by a nonzero element means multiplication by that inverse.

Probabilities remain ordinary real numbers. A challenge probability of one-half is not the field element nine, even though nine is the multiplicative inverse of two in F17. Those numbers have different roles. We perform polynomial consistency checks in the field and probability calculations in ordinary arithmetic.

This distinction matters throughout the examples. A polynomial’s values may be reduced modulo seventeen while the probability masses assigned to challenge points must still add to one as real numbers. Label the two calculations rather than allowing the shared fraction notation to blur them.

Contents · Previous chapter · Next chapter

For a polynomial f in several variables, sum-check addresses a claimed sum of f over all zero-or-one assignments to those variables. In each round, the prover sends a univariate polynomial, and the verifier checks its allowed degree and whether its values at zero and one add to the current claim.

After that message is fixed, the verifier supplies a challenge. The message evaluated at that challenge becomes the next claim. The final claim is checked against a trusted evaluation of the original polynomial at the full challenge tuple.

The Vega Prover Book's primer explains this abstract sequence and its final evaluation. It explicitly distinguishes the primer from particular implementation instances.

Three checks have different jobs: the degree limit restricts the message, the endpoint sum links it to the earlier claim, and the final evaluation anchors the chain to f. A counterexample that ignores one of those checks is not yet a counterexample to the complete protocol. We will preserve all three when constructing our examples.

Contents · Previous chapter · Next chapter

Let R be a challenge in a finite field and let p(a) be its probability of equalling a. For a fixed nonzero difference polynomial h, write Z for its set of roots. Then the agreement probability is P(h(R) = 0) = Σ p(a), summing over a in Z.

If the degree bound is d, the set Z has at most d points. Arrange all field-point probabilities from largest to smallest. The root-set probability is no greater than the sum of the d largest masses, or all masses when d exceeds the field size.

A simpler bound is min(1, d × pmax), where pmax is the largest single-point mass. It can be easier to state but looser than the ordered-mass bound.

These are upper bounds for a root test. They do not establish that a prover in a larger protocol can choose every root set freely. Endpoint consistency and earlier messages may constrain which difference polynomials are possible. We first calculate the sampling bound, then check whether an actual allowed message attains it.

Contents · Previous chapter · Next chapter

Assign probability one-half to challenge point three. Give each of the other sixteen points probability one-thirty-second. The probabilities add to one because one-half plus sixteen times one-thirty-second is one.

A polynomial with sole root three passes its root test with probability one-half. A polynomial with sole root five passes with probability one-thirty-second. Both have exactly one root, but their agreement probabilities differ by a factor of sixteen.

For the root set containing three and five, the probability is one-half plus one-thirty-second, or seventeen-thirty-seconds. The degree-two pmax bound is one, while the sum of the two largest masses gives seventeen-thirty-seconds and is sharper.

The table concerns fixed root sets under the supplied distribution. It does not yet claim a soundness error for every multi-round proof using that source. That broader conclusion requires the transcript and admissible-message analysis developed next.

Contents · Previous chapter · Next chapter

Take the true polynomial f(x) = 0 over F17. Its sum at x = 0 and x = 1 is zero. Suppose the permitted public degree bound is one, while a dishonest prover claims the sum is one.

The prover sends g(x) = 10x + 4. This has degree one. At zero its value is four, and at one its value is fourteen. Their sum is eighteen, which equals one in F17, so the verifier’s consistency check accepts the claimed sum.

The final check compares g(r) with the true f(r), which is zero. At r = 3, g(3) = 34, equal to zero modulo seventeen. This linear polynomial has no other root.

Under the biased challenge distribution from the previous chapter, the false sum is therefore accepted with probability exactly one-half. Every required check has been specified. The example demonstrates actual acceptance in a complete one-round teaching protocol, rather than merely naming a convenient root of an unconstrained polynomial.

Contents · Previous chapter · Next chapter

The true zero polynomial also satisfies a degree-two upper bound. If the protocol permits degree-two messages, the prover has a larger family of possible messages. That permission is a property of this new teaching instance; we are not silently changing a verifier after a proof begins.

Choose g(x) = 3x² + 10x + 11 over F17. Its endpoint values are eleven and seven, summing to eighteen and therefore one. Its values at three and five are sixty-eight and one hundred thirty-six, both divisible by seventeen.

The polynomial factors as 3(x − 3)(x − 5) in F17, so those are its two roots. Under the supplied biased distribution, the false sum is accepted with probability seventeen-thirty-seconds.

A looser allowed degree can enlarge the possible agreement set, even when the actual honest polynomial has smaller degree. The lesson is to record the enforced public degree bound. Do not substitute the honest example’s actual degree for the limit the verifier really accepts, or give a dishonest prover extra degree that the stated verifier would reject.

Contents · Previous chapter · Next chapter

Move the half-probability mass from point three to point nine, leaving every other point at one-thirty-second. Retain the one-round zero-polynomial instance, false sum one and degree-one message limit.

Any nonconstant linear message with root nine has the form a(x − 9). Its values at zero and one sum to a(1 − 18), equal to zero in F17. It therefore cannot satisfy the required false-sum consistency equation of one.

A nonzero constant message can satisfy consistency but has no root. Every allowed linear message with a root must consequently place that root somewhere other than nine. Such points all have probability one-thirty-second.

For example, g(x) = x has endpoint sum one and sole root zero. It passes with probability one-thirty-second. Thus this particular protocol’s maximum false-acceptance probability is one-thirty-second, even though the generic one-root pmax bound is one-half.

This is why an upper bound and an attainable cheating probability must be distinguished. The sampling law matters, and the protocol’s algebraic constraints matter too.

Contents · Previous chapter · Next chapter

In an interactive protocol, the prover sees earlier messages before choosing its next polynomial. The relevant challenge law is therefore conditional on the information available when that polynomial is fixed.

Let H denote that earlier information, including the prover’s applicable view. For a fixed history h, inspect P(R = a given H = h). A bound on the largest such conditional mass can support a root-test argument for a polynomial selected using that history.

An unconditional frequency chart averages over histories. It can look perfectly uniform even when every next challenge is completely predictable after the history is known. The averaging removes precisely the information the adaptive prover uses.

Ask two separate questions about a challenge source: how often does each value occur overall, and what can be predicted after the earlier transcript? The second question is not answered by the first. The Randomness guide provides the broader distinction between marginal distributions, dependence and useful randomness.

Contents · Previous chapter · Next chapter

Choose R1 uniformly from F17. Define R2 to equal R1. Viewed by itself, each challenge is uniformly distributed across the seventeen points. Every point has probability one-seventeenth in either individual histogram.

After R1 has been revealed, however, R2 is known exactly. Its conditional distribution puts probability one on the already revealed value and zero elsewhere.

A prover choosing its second polynomial after seeing R1 can exploit that knowledge. It is insufficient to say that both challenges are uniform and therefore each round automatically has the familiar degree-over-field bound.

This source has only seventeen possible challenge pairs: (0,0), (1,1), and so on. Independent uniform challenges would have 289 equally likely pairs. Counting possible pairs helps expose the dependence, but the decisive issue is the knowledge available before the second message is fixed.

Next we construct an allowed two-round false transcript. This goes beyond a generic copied-randomness warning by checking endpoint consistency and the final polynomial evaluation for every first challenge.

Contents · Previous chapter · Next chapter

Let f(x,y) = 0 over F17, with degree at most one allowed in each variable. The true sum across (0,0), (0,1), (1,0) and (1,1) is zero. The prover falsely claims that the sum is one.

In round one the prover sends the constant polynomial g1(x) = 9. Its endpoint sum is 9 + 9 = 18, equal to one in the field. Its degree is within the permitted bound.

After the first challenge r1, the current claim is g1(r1) = 9, regardless of which r1 appeared. The second message must therefore be linear or constant and satisfy g2(0) + g2(1) = 9.

The final evaluation of the original f is always zero. To be accepted, the prover needs g2(r2) = 0 as well as the endpoint and degree checks. The challenge source sets r2 = r1, so that target point is already known when g2 is chosen. These conditions completely specify the remaining problem.

Contents · Previous chapter · Next chapter

For r1 different from nine, define a = 9/(1 − 2r1) in F17 and send g2(x) = a(x − r1). The denominator is nonzero for those sixteen first-challenge values, so the inverse exists.

The endpoint sum is a(−r1) + a(1 − r1) = a(1 − 2r1) = 9. Thus round-two consistency holds. The message has degree one and g2(r1) = 0.

Because r2 = r1, the final check also succeeds: g2(r2) equals the true f(r1,r2), namely zero. The prover has met every stated verification check for those sixteen possible first challenges.

For a numerical instance, let r1 = 3. The denominator is minus five, represented by twelve, whose inverse is ten. Hence a = 90 modulo seventeen = 5. The message is g2(x) = 5(x − 3), or 5x + 2. Its endpoint values are two and seven, summing to nine; at the known next challenge three it evaluates to seventeen, or zero.

Contents · Previous chapter · Next chapter

When r1 = 9, the construction would divide by zero. This is not an inconvenient numerical detail to skip. It identifies the one first challenge for which a degree-one message cannot meet both requirements.

Any linear g2 having root nine has endpoint sum zero, as shown earlier. It cannot simultaneously have endpoint sum nine. A constant g2 that vanishes at nine is identically zero and likewise has endpoint sum zero.

The prover therefore fails for this one first-challenge value under the stated degree bound and final evaluation. It succeeds for each of the other sixteen values.

Since R1 is uniform, this explicit false-claim strategy has acceptance probability sixteen-seventeenths. That is approximately 94.12%, despite both individual challenge distributions being uniform.

The conclusion concerns the deliberately dependent challenge source and the completely specified toy protocol. It is not a result about a named implementation. Its purpose is to show exactly where a familiar soundness argument loses its required conditional sampling assumption.

Contents · Previous chapter · Next chapter

Now keep the same polynomial, false claim and verification checks, but draw R2 independently and uniformly after the second message is fixed. The prover can no longer know its value from R1.

Under the particular strategy just constructed, a valid second message has one root for sixteen possible values of R1. For the exceptional value, choose the constant nine divided by two, which passes endpoint consistency but has no root. The strategy’s false-acceptance probability is then (16/17) × (1/17) = 16/289.

This is the acceptance probability of that specified strategy, not the maximum over every possible strategy. The ordinary two-round degree-one soundness upper bound is two-seventeenths under its uniform fresh-challenge assumptions.

Keep the comparison labelled: sixteen-seventeenths for our strategy with the copied challenge, and sixteen-two-hundred-eighty-ninths for the same strategy with an independent second challenge. Changing the source changed what the adaptive prover could arrange before the final sample. Repeating individual histogram checks would not reveal that distinction by itself.

Contents · Previous chapter · Next chapter

Suppose that, at each relevant history in round j, every set of at most dj challenge points has conditional probability at most εj. The message polynomial must already be fixed relative to the next sampling step, and the verifier must enforce the promised degree bound.

While a false current claim remains false, the sent polynomial differs from the honest round polynomial. It can become consistent with the honest restricted claim only at an agreement point of the corresponding nonzero difference polynomial.

The conditional assumption bounds that repair event by εj. Acceptance from a false initial sum requires a repair at some round before the final trusted evaluation can agree. A union bound therefore gives an upper bound of min(1, Σ εj), under the stated protocol conditions.

This is a sum across possible repair rounds, not automatically a product of independent round failures. Different probability arguments answer different questions. A repeated whole-protocol construction might support another analysis, but it should not be inferred merely because a protocol has several internal rounds.

Contents · Previous chapter · Next chapter

If every next-point conditional probability is at most αj, a usable round bound is min(1, dj αj). Equivalently, a point-mass cap of 2 to the power minus k can be expressed through an appropriate min-entropy statement for that distribution.

The qualification is important. An unconditional entropy figure does not establish the same cap after transcript information is revealed. Definitions of conditional min-entropy also distinguish worst-case and averaged formulations. Here the sufficient assumption is explicitly a pointwise bound for every relevant history.

For a numerical illustration, a degree-three root test with a justified conditional point-mass cap of one-sixty-fourth has agreement probability at most three-sixty-fourths. That does not mean a generator has been certified from a histogram containing sixty-four bins.

Use Randomness and the existing generator, entropy and statistical-test guide for the broader source-assessment question. This article’s contribution is connecting a specified conditional law to the polynomial agreement event.

Contents · Previous chapter · Next chapter

A challenge can be uniform on a proper subset of a larger field. Suppose it is sampled uniformly from four specified points in F17, with zero probability assigned to all other points.

A fixed degree-two polynomial can have at most two roots in that four-point support. Its root-test probability is therefore at most one-half, rather than two-seventeenths. This assumes the polynomial is fixed before the challenge and the four-point sampling rule is the relevant conditional law.

The field still supplies seventeen elements for the algebra. The sampling support supplies only four equally likely possibilities for this check. Neither number should silently replace the other.

For a changed task, enlarge the support to eight points while keeping the degree at most two. The same argument gives an upper bound of one-quarter. This comparison concerns root testing alone; a full protocol may impose additional restrictions on attainable roots, just as the one-round endpoint equation excluded point nine in our earlier example.

Contents · Previous chapter · Next chapter

Suppose a toy source selects an integer uniformly from zero through thirty-one, then reduces it modulo seventeen. Remainders zero through fourteen each have two preimages, while fifteen and sixteen have one each.

The first fifteen remainders consequently have probability one-sixteenth, and the final two have probability one-thirty-second. Every field element is possible, but the distribution is not uniform.

For a fixed linear difference polynomial rooted at remainder three, the root-test probability is one-sixteenth. Rooted at sixteen, it is one-thirty-second. Both differ from one-seventeenth.

As a paper variation, retain only input values zero through sixteen and condition on retention. Each remainder then has one preimage and the retained output is uniform. This is an exact calculation about this finite source, not an implementation recommendation or a security analysis of rejection sampling in a real system.

The broader habit is to count preimages and preserve the source’s actual assumptions. A deterministic map does not make a biased or dependent input independent and uniform merely because its output is displayed as a field element.

Contents · Previous chapter · Next chapter

A histogram of individual values can check one aspect of a record. A table of successive pairs can reveal dependence omitted by that histogram. Neither finite observation by itself proves the required conditional law against every relevant prover strategy.

In our copied-challenge construction, a long-run histogram can be uniform in both columns, while every observed pair lies on the diagonal. The first chart and second chart answer different questions. Reporting only the first would conceal an obvious feature of the constructed process.

Likewise, repeatedly accepting honest examples checks neither the maximum probability of accepting a false claim nor the source’s unpredictability. Honest completeness and dishonest soundness require different evidence.

A useful mathematical review states the source model, the adversary’s available information, the moment each message becomes fixed and the verification checks actually performed. An empirical test record can supplement that account, with its sample size and limits identified. It should not be promoted into a theorem about histories or behaviours it never examined.

Contents · Previous chapter · Next chapter

Use F11 and the one-round zero polynomial, with a public degree-one bound and a false claimed sum of one. Give challenge point two probability two-fifths, and each other point probability three-fiftieths. These probabilities sum to one.

Find a legal linear prover message rooted at two. Write g(x) = a(x − 2). Its endpoint sum is minus three times a, which equals one when a = 7 in F11. Thus g(x) = 7x + 8.

Check the endpoints: eight plus four equals twelve, or one in F11. Check the target: g(2) = 22, or zero. The complete one-round false claim passes with probability two-fifths under this source.

Now move the heavy probability to point six. A linear message rooted at six has endpoint sum a(1 − 12) = 0, so it cannot support the false sum one. The largest achievable root probability becomes three-fiftieths, attained for example by g(x) = x, whose root is zero.

Explain why the generic largest-mass bound stays valid while the actual attainable maximum changes. The source probabilities and consistency constraints must both survive the transfer.

Contents · Previous chapter · Next chapter

Sometimes the supplied mathematical information is that a challenge law is close to uniform, rather than a list of its exact masses. State what close means before using that information. On a finite field of q elements, define δ as half the sum of the absolute differences between each actual mass p(a) and the uniform mass 1/q.

The positive differences and the negative differences have equal total magnitude, because both distributions sum to one. Each total is δ. For any chosen set Z, the extra probability above uniform on that set cannot exceed the total positive difference δ.

Consequently P(R in Z) is at most |Z|/q + δ. A fixed degree-d difference polynomial therefore has root-test probability at most min(1, d/q + δ). This follows directly from the defined distance and root count; no empirical histogram guarantee has been assumed.

For the earlier F17 distribution with half its mass at three, the excess at that point is 1/2 − 1/17 = 15/34. Every other point has a deficit, so δ is exactly 15/34. For a one-root test, the bound becomes 1/17 + 15/34 = 1/2, matching the mass at three.

The important limitation is where the distance guarantee applies. A marginal distance-to-uniform guarantee does not establish the corresponding conditional guarantee after a transcript. To use this bound round by round, supply the appropriate distance assumption for each relevant conditional law. Otherwise the same averaging mistake returns under a different numerical label.

Contents · Previous chapter · Next chapter

The two-round construction is small enough to audit without estimating a probability from random trials. Make a table with one row for each first challenge from zero through sixteen. In every row record the denominator 1 − 2r1 reduced modulo seventeen.

For the sixteen nonzero denominators, calculate its inverse, multiply by nine and obtain the coefficient a. Check that the two endpoint values of a(x − r1) add to nine. Then substitute the copied second challenge r1 and check that the polynomial value is zero.

For the row r1 = 9, mark the denominator as zero and use the impossibility argument, rather than pretending that a numerical inverse can be found. The table should show sixteen accepting rows and one failing row for the specified strategy. Uniform probability on the seventeen rows then gives sixteen-seventeenths exactly.

Next give every row seventeen subrows for an independently uniform second challenge. Each of the sixteen constructed nonconstant messages has one accepting subrow. Use a nonzero constant message for the exceptional first row so that its endpoint sum remains valid but it has no accepting subrow. There are then sixteen accepting challenge pairs among 289.

This check establishes the two constructed strategies’ exact probabilities. It does not search every possible prover strategy or independently certify a general theorem. Keeping that boundary visible lets an exhaustive finite calculation be useful without asking it to establish a broader cryptographic claim.

Contents · Previous chapter · Next chapter

The verifier normally reveals a challenge so the prover can construct its next message. Public visibility after the relevant message is fixed is therefore compatible with the ordinary interactive argument. The problem is knowledge of that next challenge before choosing the message it is supposed to test.

In our counterexample, r2 becomes known when r1 is revealed because the source copies it. The second polynomial can then be chosen with a root at that future test point. No secret transcript theft or implementation exploit is needed; the dependence was built into the toy source’s stated law.

For a useful classroom sequence, write message one, challenge one, message two and challenge two on separate cards. Draw an arrow showing which information was available before each message. Then replace the independent second challenge by a copy of the first and add the new information arrow. The changed dependency is the mathematical reason the previous bound can no longer be used unchanged.

Contents · Previous chapter · Next chapter

Use a separate honest instance f(x,y) = x + y over F17. Its values on the four Boolean inputs are zero, one, one and two, so the true claimed sum is four. The honest first-round polynomial is g1(x) = 2x + 1.

Its endpoint sum is one plus three, equal to four. After any first challenge r1, the current claim becomes 2r1 + 1. The honest second-round polynomial is g2(y) = r1 + y, whose endpoint sum is r1 + (r1 + 1) = 2r1 + 1.

For any second challenge r2, the final value is g2(r2) = r1 + r2, exactly the trusted evaluation f(r1,r2). This honest transcript succeeds for every challenge pair. It therefore also succeeds when the source copies r1 into r2 or concentrates its probability on only a few pairs.

For a concrete check, take r1 = 3 and the copied r2 = 3. The first message gives seven as the next claim. The second message is three plus y, with endpoint values three and four. At the final point it gives six, matching f(3,3). Nothing in that honest test reveals the copied-challenge source’s soundness failure against the dishonest strategy from the earlier chapters.

Now try r1 = 5 and r2 = 2. The first message gives eleven; the second message has endpoint values five and six; its final value is seven. The same identities hold. These two concrete transcripts are checks of the honest algebra, while the general expressions explain why every pair works.

This separates two useful test questions. Can the implementation follow a correct transcript without wrongly rejecting it? Can a false initial claim be accepted more often than the stated bound permits? Passing many examples of the first kind does not answer the second. A review needs adversarial reasoning and a justified source model as well as ordinary positive examples.

The conclusion is not that positive tests are pointless. They establish something real about the paths exercised. The repair is to preserve their purpose and then add the different analysis required for soundness, rather than asking one reassuring collection of successful demonstrations to establish both properties at once.

Contents · Previous chapter · Next chapter

“There is one root, so the probability is one over the field size.” Add the sampling assumption. The exact probability is the mass assigned to that root, conditional on the applicable history when the polynomial becomes fixed.

“Both challenges are uniform, so the ordinary round bound applies.” Check their conditional relationship. In the constructed copied-challenge source, both marginals are uniform while the second challenge is known after the first.

“The largest d masses give an achievable cheating probability.” They give a generic root-set upper bound. A protocol’s consistency equations may exclude the heaviest sets. Construct an allowed message before claiming attainability.

“More rounds mean multiply the per-round root probabilities.” Identify the event the proof uses. Sum-check soundness uses a bound on a false claim becoming consistent at some round; the stated extension uses a union bound. A different repetition arrangement needs its own justification.

For each repair, name the missing assumption and one calculation that exposes its role. The goal is a usable explanation, rather than replacing a simple theorem with an equally unqualified warning.

Contents · Previous chapter · Next chapter

Does a nonuniform distribution always make the protocol insecure?

Not automatically. It changes the root-event bound, and the protocol’s constraints also matter. A suitable analysis must use the actual distribution and chronology instead of quoting a uniform-sampling result unchanged.

Does the two-round example attack a real proof library?

No. It is a fully specified synthetic protocol with a deliberately copied second challenge. It establishes the stated mathematical failure mode without identifying a vulnerable deployed product.

Is sum-check itself a zero-knowledge protocol?

Not in general. Its ordinary messages can reveal information. This guide examines a soundness building block within the broader zero-knowledge learning route, while leaving privacy constructions as a separate question.

Do the tiny fields provide real security parameters?

No. Their purpose is to make every residue and probability checkable by hand. Field size, degree, transcript design and the other components of an actual scheme require the scheme’s own security analysis.

Contents · Previous chapter · Next chapter

For the ordinary protocol, return to Checking a Polynomial Sum with Degree Bounds and Fresh Challenges. For the larger statement, witness and application boundaries, use Zero-Knowledge Proofs. For generation and dependence, continue through Randomness and the random-number generator, entropy and testing lesson.

Primary technical routes are the Georgetown protocol notes, the Vega abstract sum-check primer and the Archive of Formal Proofs sum-check entry. The last provides a formal-verification research route; it does not certify the examples or an implementation here. The weighted distributions, false transcripts and changed-field exercises in this article are independent teaching constructions.

The wider route is The Gold Standard of Education: Learning That Transfers into Life within How X Works. A useful final check is to label what was fixed, what was known and what was sampled next. When those labels remain correct after the field, weights or transcript dependence changes, the soundness argument becomes something the learner can actually use.

Contents · Previous chapter · Return to Zero-Knowledge Proofs