Lagrange interpolation: turning points into a polynomial

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^2 + 2x + 1$

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

• $5x^3 - x$ - degree 3 (cubic)
• $7x + 4$ - degree 1 (linear)
• $42$ - degree 0 (constant)

Why does $7x + 4$ have no $x$ on the last term? Because $4$ is really $4 \cdot x^0$, and $x^0 = 1$ for any value of $x$. Every polynomial has an implicit $x^0$ on its constant term - we just don't write it.

The general form of a degree-$n$ polynomial:

$P(x) = a_n x^n + a_{n-1} x^{n-1} + \cdots + a_1 x + a_0$

where $a_0, a_1, \ldots, a_n$ 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, \quad P(2) = 5, \quad 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)

For our three points, that unique parabola is $P(x) = x^2 + 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^2 + bx + c$:

$P(1): \quad a + b + c = 2$

$P(2): \quad 4a + 2b + c = 5$

$P(3): \quad 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^2 + 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_1$, $L_2$, $L_3$.

$L_1(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_1(x) = \frac{(x - 2)(x - 3)}{2}$

Verify: $L_1(1) = \frac{(-1)(-2)}{2} = 1$, $\quad L_1(2) = \frac{(0)(-1)}{2} = 0$, $\quad L_1(3) = \frac{(1)(0)}{2} = 0$. Exactly what we need.

If you expand $\frac{(x-2)(x-3)}{2}$, you get $\frac{1}{2}x^2 - \frac{5}{2}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_2(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_2(x) = \frac{(x - 1)(x - 3)}{-1}$

• $L_2(1) = 0, \quad L_2(2) = 1, \quad L_2(3) = 0$

$L_3(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_3(x) = \frac{(x - 1)(x - 2)}{2}$

• $L_3(1) = 0, \quad L_3(2) = 0, \quad L_3(3) = 1$

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

Why 1 matters

The number 1 is a neutral multiplier: $1 \times \text{anything} = \text{anything}$. Since $L_1(1) = 1$, we can multiply by any y-value and deliver it exactly:

$2 \cdot L_1(1) = 2 \cdot 1 = 2$

And since $L_1$ is 0 at the other x-values, those stay zero:

$2 \cdot L_1(2) = 2 \cdot 0 = 0 \qquad 2 \cdot L_1(3) = 2 \cdot 0 = 0$

So $2 \cdot L_1(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, \mathbf{2})$.

Combining them

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

$P(x) = 2 \cdot L_1(x) + 5 \cdot L_2(x) + 10 \cdot L_3(x)$

Check at each point:

$P(1) = 2 \cdot 1 + 5 \cdot 0 + 10 \cdot 0 = 2$

$P(2) = 2 \cdot 0 + 5 \cdot 1 + 10 \cdot 0 = 5$

$P(3) = 2 \cdot 0 + 5 \cdot 0 + 10 \cdot 1 = 10$

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

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

$L_i(x) = \prod_{\substack{j=1 \\ j \neq i}}^{n} \frac{x - x_j}{x_i - x_j}$

The $\prod$ 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_j)$ creates a zero at $x_j$; the denominator $(x_i - x_j)$ normalizes to 1 at $x_i$.

---

4. The interpolating polynomial

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

$P(x) = \sum_{i=1}^{n} y_i \cdot L_i(x)$

The $\sum$ 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.

Result: From three basis polynomials $L_1$, $L_2$, $L_3$ and three data points $(1, 2)$, $(2, 5)$, $(3, 10)$, we combined them into a weighted sum:

$P(x) = 2 \cdot L_1(x) + 5 \cdot L_2(x) + 10 \cdot L_3(x) = x^2 + 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.

---

Further resources

• Lagrange Interpolation Calculator - plug in your own points and see the polynomial step by step
• Polynomial interpolation - Wikipedia