0xluk3

Posted on Apr 12 • Originally published at luk3.tech on Apr 12

Lagrange interpolation: turning points into a polynomial

#math #zk #cryptography

1. What is a polynomial?

A polynomial is an expression built from a variable x, using only addition, multiplication, and non-negative integer exponents:

P(x) = 3x² + 2x + 1

The degree is the highest power of x. The example above is degree 2 (quadratic) because x² is the highest term. Some more examples:

5x³ − x - degree 3 (cubic)
7x + 4 - degree 1 (linear)
42 - degree 0 (constant)

Note: 7x + 4 has no x on the last term because 4 is really 4 · x⁰, and x⁰ = 1 for any value of x. Every polynomial has an implicit x⁰ on its constant term - we just don't write it.

The general form of a degree-n polynomial:

P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ⋯ + a₁x + a₀

where a₀, a₁, …, aₙ are constants called coefficients.

2. The setup: points on a graph

You have three data points - expressed as inputs and outputs of some unknown function:

P(1) = 2,  P(2) = 5,  P(3) = 10

How many polynomials pass through these points? Through a single point, infinitely many curves fit - constants, lines, parabolas, cubics. Add a second point and you rule out some of them, but many still work. A result in algebra called the unisolvence theorem tells us that n points pin down exactly one polynomial of degree at most n − 1:

1 point - exactly one degree-0 polynomial (a constant)
2 points - exactly one degree-1 polynomial (a line)
3 points - exactly one degree-2 polynomial (a parabola)

Interactive visualization: The original post has a step-through widget here that lets you watch how adding points progressively constrains the polynomial.

For our three points, that unique parabola is P(x) = x² + 1. No lower-degree polynomial (a line, a constant) can pass through all three - this is the lowest-degree polynomial that fits.

Finding that polynomial is called interpolation. One way to do it: set up a system of equations. Plug each point into P(x) = ax² + bx + c:

P(1):  a + b + c = 2
P(2):  4a + 2b + c = 5
P(3):  9a + 3b + c = 10

Subtract the first equation from the second: 3a + b = 3. Subtract the second from the third: 5a + b = 5. Subtract those two results: 2a = 2, so a = 1. Back-substitute: b = 0, c = 1. The answer is P(x) = x² + 1.

It works, but it's slow and repetitive - three equations for three points, and it only gets worse as you add more. Joseph-Louis Lagrange found a much more elegant way.

This matters because ZK proof systems encode computation as polynomials - a prover's data becomes evaluations of a polynomial, and Lagrange interpolation is how that happens. But for now, let's focus purely on the math.

3. Lagrange's approach: basis polynomials

We still have the same three points: P(1) = 2, P(2) = 5, P(3) = 10. In section 2 we found the polynomial by setting up equations and solving for coefficients. Lagrange's approach reaches the same answer with a completely different method.

The goal: three basis polynomials

Our three x-values are 1, 2, 3. Lagrange's idea: build three basis polynomials, one for each x-value. Each one equals 1 at its own x-value and 0 at the other two. We'll call them L₁, L₂, L₃.

L₁(x) - should equal 1 at x = 1, and zero at x = 2 and x = 3.

How do we build it? The expression (x − 2) equals zero when x = 2. The expression (x − 3) equals zero when x = 3. Multiply them together:

(x − 2)(x − 3)

Anything times zero is zero, so this product is zero at both x = 2 and x = 3 - exactly where we need zeros. But what does it give at x = 1?

(1 − 2)(1 − 3) = (−1)(−2) = 2

We got 2, but we need 1. So we divide the whole thing by 2:

L₁(x) = (x − 2)(x − 3) / 2

Verify: L₁(1) = (−1)(−2) / 2 = 1, L₁(2) = (0)(−1) / 2 = 0, L₁(3) = (1)(0) / 2 = 0. Exactly what we need.

If you expand (x − 2)(x − 3) / 2, you get ½x² − ⁵⁄₂x + 3 - a polynomial just like in section 1. But the factored form is the point: it makes the zeros and the normalization obvious.

L₂(x) - should equal 1 at x = 2, and zero at x = 1 and x = 3.

Same recipe. We need zeros at x = 1 and x = 3, so use factors (x − 1)(x − 3). Evaluate at x = 2: (2 − 1)(2 − 3) = −1. Divide by −1:

L₂(x) = (x − 1)(x − 3) / (−1)

L₂(1) = 0, L₂(2) = 1, L₂(3) = 0.

L₃(x) - should equal 1 at x = 3, and zero at x = 1 and x = 2.

Factors (x − 1)(x − 2). Evaluate at x = 3: (3 − 1)(3 − 2) = 2. Divide by 2:

L₃(x) = (x − 1)(x − 2) / 2

L₃(1) = 0, L₃(2) = 0, L₃(3) = 1.

Each polynomial equals 1 at one x-value and 0 at the others.

Interactive visualization: The original post has a step-through widget here that graphs each basis polynomial, showing how it equals 1 at its own point and 0 at the others.

Why 1 matters

The number 1 is a neutral multiplier: 1 × anything = anything. Since L₁(1) = 1, we can multiply by any y-value and deliver it exactly:

2 · L₁(1) = 2 · 1 = 2

And since L₁ is 0 at the other x-values, those stay zero:

2 · L₁(2) = 2 · 0 = 0    2 · L₁(3) = 2 · 0 = 0

So 2 · L₁(x) gives us exactly 2 at x = 1 and contributes nothing at the other points. Where does the 2 come from? It's the y-value of our first data point: (1, 2).

Combining them

Do the same for each data point. Multiply each Lᵢ by the y-value of that point and add them up. The y-values come from our data points: (1, 2), (2, 5), (3, 10).

P(x) = 2 · L₁(x) + 5 · L₂(x) + 10 · L₃(x)

Check at each point:

P(1) = 2 · 1 + 5 · 0 + 10 · 0 = 2
P(2) = 2 · 0 + 5 · 1 + 10 · 0 = 5
P(3) = 2 · 0 + 5 · 0 + 10 · 1 = 10

All three data points are hit. Each Lᵢ delivers its y-value to the right place and contributes nothing elsewhere.

In general, for n points the i-th basis polynomial is:

Lᵢ(x) = ∏(j=1 to n, j≠i) [(x − xⱼ) / (xᵢ − xⱼ)]

The ∏ symbol means "multiply all these together" - like a for loop that multiplies instead of adding. In pseudocode:

function basis(i, x, points):
    result = 1
    for j = 1 to n:
        if j != i:
            result = result * (x - points[j].x) / (points[i].x - points[j].x)
    return result

The loop skips j = i and multiplies one fraction per remaining point. The numerator (x − xⱼ) creates a zero at xⱼ; the denominator (xᵢ − xⱼ) normalizes to 1 at xᵢ.

4. The interpolating polynomial

Section 3 built the result for three specific points. The general formula for any set of n points:

P(x) = ∑(i=1 to n) [yᵢ · Lᵢ(x)]

The ∑ symbol means "add all these together" - like a for loop that adds. In pseudocode:

function interpolate(x, points):
    result = 0
    for i = 1 to n:
        result = result + points[i].y * basis(i, x, points)
    return result

The loop goes through each data point, computes its basis polynomial at x, multiplies by the y-value, and adds it to the total.

This is Lagrange interpolation. Given any set of points, this formula produces the unique polynomial that passes through all of them. No guessing, no solving equations. You just plug in your points and get the polynomial directly. Every point contributes exactly its y-value at the right place and nothing elsewhere.

Interactive visualization: The original post has a step-through widget here that shows the weighted basis polynomials combining into the final interpolating polynomial.

Result: From three basis polynomials L₁, L₂, L₃ and three data points (1, 2), (2, 5), (3, 10), we combined them into a weighted sum:

P(x) = 2 · L₁(x) + 5 · L₂(x) + 10 · L₃(x) = x² + 1

This is the unique polynomial that passes through all three points. Each basis polynomial carried one y-value to the right place. The weighted sum produced one new polynomial out of three building blocks.

One property to keep in mind: change any single data point and the entire polynomial changes. Every point influences every part of the result. This sensitivity is what makes polynomials useful for encoding computation - any error in the input propagates through the entire polynomial.

5. Why ZK cares

In a ZK proof, the prover encodes their computation as evaluations of a polynomial. The computation produces some set of values at specific points - Lagrange interpolation is how those values become a polynomial.

The verifier never sees the full polynomial. They see a commitment (a locked-down version of it) and check a few evaluations. The fact that there's exactly one polynomial through any set of points is what makes this work - if the prover's polynomial passes through the right values, it must be the right polynomial.