# Univariate skip

## Context

The Sumcheck protocol is a fundamental interactive proof protocol used to verify that the sum of a multivariate polynomial over all points of the Boolean hypercube is equal to a claimed value.

Let us suppose that the prover $\mathcal{P}$ knows a multivariate polynomial function $\hat{f}(X_0, \dots, X_{n-1})$, and wants to convince the verifier $\mathcal{V}$ that the following sum is correct:

\begin{equation}
v = \sum_{\mathbf{x} \in \{0,1\}^n} \hat{f}(\mathbf{x})
\end{equation}

Here, $\mathbf{x}$ denotes a binary vector in the Boolean hypercube $\{0,1\}^n$. That is, $\mathbf{x} = (x_0, x_1, \dots, x_{n-1})$ where each $x_i \in \{0,1\}$.

The Sumcheck protocol allows $\mathcal{P}$ to convince $\mathcal{V}$ of the correctness of this sum by sending much less data than writing out every evaluation of $\hat{f}(\mathbf{x})$. Instead, the prover sends univariate polynomials in a sequence of rounds, each reducing the dimensionality of the problem by one variable.

To make this concrete, let's work through a simple example.

:::info
Consider the following polynomial function in three Boolean variables:

\begin{equation}
g(X_1, X_2, X_3) = 2 X_1^3 + X_1 X_3 + X_2 X_3
\end{equation}

Our goal is to compute the sum of $g$ over all $8$ points in the 3-dimensional hypercube $\{0,1\}^3$:
\begin{equation}
H = \sum_{X_1 \in \{0,1\}} \sum_{X_2 \in \{0,1\}} \sum_{X_3 \in \{0,1\}} g(X_1, X_2, X_3)
\end{equation}

To do this using Sumcheck, the prover $\mathcal{P}$ starts by expressing this sum in terms of smaller univariate polynomials.

In the first round, $\mathcal{P}$ considers $X_1$ as the free variable and sums over all values of $X_2$ and $X_3$. This gives a univariate polynomial $g_1(X_1)$:

\begin{equation}
g_1(X_1) = \sum_{(X_2, X_3) \in \{0,1\}^2} g(X_1, X_2, X_3)
\end{equation}

Let’s compute $g_1(X_1)$ explicitly. There are four possible values for $(X_2, X_3)$:

- $g(X_1, 0, 0) = 2 X_1^3$
- $g(X_1, 0, 1) = 2 X_1^3 + X_1$
- $g(X_1, 1, 0) = 2 X_1^3$
- $g(X_1, 1, 1) = 2 X_1^3 + X_1 + 1$

Adding these up:

\begin{align}
g_1(X_1) &= \left(2 X_1^3\right) + \left(2 X_1^3 + X_1\right) + \left(2 X_1^3\right) + \left(2 X_1^3 + X_1 + 1\right) \\
&= 8 X_1^3 + 2 X_1 + 1
\end{align}

This univariate polynomial is sent to the verifier. The verifier checks that its evaluations at $0$ and $1$ match the original claimed sum for $X_1 = 0$ and $X_1 = 1$ respectively. Then the verifier sends back a random challenge point $r_1 \in \mathbb{F}$ (often sampled from a larger extension field), and the prover must continue the protocol with $X_1 = r_1$ fixed, reducing over the next variable.
:::

This process continues for each variable. In round $i$, the prover sends a univariate polynomial over variable $X_i$, summing over the remaining variables. The verifier checks consistency and sends back a new random challenge $r_i$. After $n$ rounds, all variables are fixed to random values, and the verifier checks that the final evaluation matches the claimed polynomial evaluation at that point.

### Special nature of the first round

The first round of the protocol is special. Before any verifier challenge has been issued, all values used by the prover can remain in the base field $\mathbb{F}$. This is a significant distinction because later rounds require evaluating the constraint polynomial at random points drawn from an extension field $\mathbb{G}$, which is computationally more expensive.

This leads to a natural question: can we perform **more** work in the first round, while we’re still in the cheap base field, in order to reduce the expensive work required in later rounds?

This is the motivation behind the **univariate skip** optimization: instead of reducing the sum one variable at a time, can we reduce multiple variables in a single step during the first round—while still staying within the base field? The answer is yes, and this idea leads to significant computational savings.

In the next sections, we’ll explore how the univariate skip works, step by step, starting from the constraint polynomial setup and progressing to an optimized version of the protocol.

## The constraint polynomial $C$

### The starting point: a structured table of data

Let’s begin with the basic object at the heart of many proof systems: a large table of data. This table, which we’ll call $T$, has size $2^n \times \ell$:

- Each row in the table corresponds to a point in the Boolean hypercube $H^n = \{0,1\}^n$.
- Each column represents a different quantity or "trace variable," and is denoted as $\omega_i$, where $0 \leq i < \ell$.

This means that for every binary vector $\mathbf{x} = (x_0, x_1, \dots, x_{n-1}) \in H^n$, the table provides values for $\omega_0(\mathbf{x}), \omega_1(\mathbf{x}), \dots, \omega_{\ell-1}(\mathbf{x})$.

Now suppose we want to check that these rows satisfy some algebraic constraint. We express this using a fixed polynomial function $C$ over $\ell$ variables. The idea is simple:

- For every row of the table, we plug its values into $C$.
- We require that the result is always zero.

This gives the core condition:

\begin{equation}
C(T_{i,0}, T_{i,1}, \dots, T_{i,\ell - 1}) = 0 \quad \text{for all rows } i
\end{equation}

This means: the constraint polynomial $C$ vanishes on every row of the table.

### Interpreting table columns as polynomials

To work algebraically, we switch from viewing the table as raw data to interpreting each column as a polynomial.

Specifically, for each column $i$, we define a multilinear polynomial $\omega_i(\mathbf{X})$, where $\mathbf{X} = (X_0, X_1, \dots, X_{n-1})$, such that:

\begin{equation}
\omega_i(\mathbf{X}) \in \mathbb{F}[X_0, X_1, \dots, X_{n-1}]
\end{equation}

Each $\omega_i$ is defined to interpolate the values in the $i$-th column of the table. Because we only have evaluations over the Boolean cube $H^n$, each $\omega_i$ is multilinear: its degree in every variable $X_j$ is at most $1$.

Thus, the entire table $T$ is now represented by a collection of polynomials:

- Column $i$ is represented by $\omega_i(\mathbf{X})$
- The data in the table is now encoded as evaluations of these polynomials on $H^n$

This algebraic representation is essential—it allows us to work with compact, symbolic objects instead of exponentially large raw data.

### Defining the constraint polynomial $C$

Now that each column is represented as a polynomial $\omega_i(\mathbf{X})$, we define a new composed polynomial:

\begin{equation}
C(\mathbf{X}) = C\left(\omega_0(\mathbf{X}), \omega_1(\mathbf{X}), \dots, \omega_{\ell - 1}(\mathbf{X})\right)
\end{equation}

This is a multivariate polynomial in the variables $\mathbf{X} = (X_0, \dots, X_{n-1})$, obtained by:

1. Evaluating each $\omega_i$ at the point $\mathbf{X}$ to get $\omega_i(\mathbf{X})$
2. Plugging those into the constraint function $C$ to compute $C(\mathbf{X})$

So, we have:

\begin{equation}
C(X_0, \dots, X_{n-1}) = C\left(\omega_0(X_0, \dots, X_{n-1}), \dots, \omega_{\ell - 1}(X_0, \dots, X_{n-1})\right)
\end{equation}

This composed polynomial captures whether the constraint holds at each point $\mathbf{X} \in H^n$. If the constraint is satisfied at all table rows, then:

\begin{equation}
C(\mathbf{X}) = 0 \quad \text{for all } \mathbf{X} \in H^n
\end{equation}

This is the main algebraic goal we want to prove using protocols like Sumcheck or Zerocheck.

### Transforming the problem into a sumcheck

Instead of checking $C(\mathbf{X}) = 0$ at every point individually (which would be exponential work), we reduce the problem to evaluating a sum over the hypercube using polynomial techniques.

The idea is to construct a new function that "selects" values from $H^n$ and sums the constraint evaluations:

\begin{equation}
\hat{F}(\boldsymbol{\alpha}) = \sum_{\mathbf{x} \in H^n} \hat{\delta}_n(\boldsymbol{\alpha}, \mathbf{x}) \cdot C(\mathbf{x})
\end{equation}

Here:

- $\boldsymbol{\alpha} \in \mathbb{G}^n$ is a random point sampled by the verifier from an extension field
- $\hat{\delta}_n(\boldsymbol{\alpha}, \mathbf{x})$ is the *delta interpolant*, a special polynomial that behaves like a Kronecker delta: it equals $1$ when $\mathbf{x} = \boldsymbol{\alpha}$ and $0$ at all other points in $H^n$

Why is this useful? If $C(\mathbf{x}) = 0$ for all $\mathbf{x} \in H^n$, then the entire sum is zero:

\begin{equation}
\hat{F}(\boldsymbol{\alpha}) = 0
\end{equation}

And thanks to the Schwartz–Zippel lemma, if $C$ is nonzero on some point in $H^n$, then $\hat{F}(\boldsymbol{\alpha})$ will be nonzero with high probability.

So proving that $\hat{F}(\boldsymbol{\alpha}) = 0$ at a random point is enough to convince the verifier that $C(\mathbf{x})$ is identically zero on $H^n$.

This transforms our original constraint-checking problem into a Sumcheck problem.

### A concrete example

Let’s walk through a small, illustrative example. Suppose we work with $n = 2$ variables and $\ell = 2$ columns.

We define the constraint polynomial:

\begin{equation}
C(\omega_0, \omega_1) = \omega_1 - \omega_0
\end{equation}

We interpret this as saying: column 1 must equal column 0 in every row.

Suppose our table is:

| $(X_0, X_1)$ | $\omega_0(X_0, X_1)$ | $\omega_1(X_0, X_1)$ | Constraint holds? |
|-------------|----------------------|----------------------|--------------------|
| $(0, 0)$ | $1$ | $1$ | yes |
| $(0, 1)$ | $2$ | $2$ | yes |
| $(1, 0)$ | $3$ | $3$ | yes |
| $(1, 1)$ | $4$ | $4$ | yes |

From this table, we interpolate two multilinear polynomials $\omega_0(X_0, X_1)$ and $\omega_1(X_0, X_1)$ such that they match the values above at each point in $H^2$.

Then the composed constraint polynomial is:

\begin{equation}
C(X_0, X_1) = \omega_1(X_0, X_1) - \omega_0(X_0, X_1)
\end{equation}

Since the two columns are equal at all hypercube points, $C(X_0, X_1)$ evaluates to $0$ everywhere on $H^2$.

This small example illustrates how algebraic constraints over a data table become polynomial equations, and how those equations can be verified efficiently with sumcheck-based techniques.

## Initial thought: compute a multivariate polynomial to skip the first $k$ rounds

Let’s now return to our motivating idea: since the first round of the sumcheck protocol is cheap (operating entirely in the base field $\mathbb{F}$), can we do more work upfront to reduce the number of expensive rounds later?

A natural approach would be to skip not just one variable in the first round, but multiple variables at once. Specifically, instead of reducing over a single variable (as in traditional sumcheck), we attempt to reduce over the last $n - k$ variables immediately, and retain only $k$ "free" variables. That is, we compute:

\begin{equation}
v(X_0, \dots, X_{k-1}) = \sum_{\mathbf{x} \in H^{n-k}} \hat{\delta}_{n-k}((\alpha_k, \dots, \alpha_{n-1}), \mathbf{x}) \cdot C(X_0, \dots, X_{k-1}, \mathbf{x})
\end{equation}

Here’s what this expression means:

- We fix the verifier’s random challenges $(\alpha_k, \dots, \alpha_{n-1})$ for the last $n - k$ variables.
- We sum over all Boolean assignments $\mathbf{x}$ to those last $n - k$ variables.
- The function $C(X_0, \dots, X_{k-1}, \mathbf{x})$ is the constraint polynomial, partially evaluated with the last $n - k$ variables instantiated.
- The delta interpolant $\hat{\delta}_{n-k}$ ensures this sum focuses only on one randomly chosen point of the hypercube, preserving soundness.

The result is a **multivariate polynomial** $v(X_0, \dots, X_{k-1})$ in the first $k$ variables. The idea is to send this entire polynomial to the verifier right away—effectively skipping the first $k$ rounds.

At first glance, this looks promising. But there’s a catch.

### Why this idea becomes expensive

Let’s understand the structure of the polynomial $v(X_0, \dots, X_{k-1})$ and why it quickly becomes costly to compute.

First, recall how $C(\mathbf{X})$ is constructed:

\begin{equation}
C(\mathbf{X}) = C\left(\omega_0(\mathbf{X}), \omega_1(\mathbf{X}), \dots, \omega_{\ell - 1}(\mathbf{X})\right)
\end{equation}

Where:

- Each $\omega_i(\mathbf{X})$ is multilinear: degree at most $1$ in each $X_j$.
- The constraint polynomial $C$ has total degree at most $d$ in its inputs $\omega_i$.

So, when composed, the resulting polynomial $C(\mathbf{X})$ has degree at most $d$ in each variable $X_j$ individually. In particular, this includes all $k$ variables $X_0, \dots, X_{k-1}$ that we’re keeping as symbolic in $v$.

As a result, the output polynomial $v(X_0, \dots, X_{k-1})$ has degree at most $d$ in each of its $k$ variables. This is important.

Now comes the core issue: to **fully determine** a multivariate polynomial of degree $d$ in each of $k$ variables, we must evaluate it at every point in a $(d+1)^k$ grid.

That is:
- For each variable $X_i$, we need at least $d+1$ distinct evaluations.
- To interpolate the full multivariate polynomial, we must evaluate it at every combination of those points.

So the total number of required evaluations is:

\begin{equation}
(d + 1)^k
\end{equation}

This is an exponential cost in $k$.

Let’s see how this grows with small values:

- If $k = 1$ and $d = 2$: we need $(2 + 1)^1 = 3$ evaluations.
- If $k = 2$ and $d = 2$: we need $(2 + 1)^2 = 9$ evaluations.
- If $k = 3$ and $d = 2$: we need $(2 + 1)^3 = 27$ evaluations.
- If $k = 4$ and $d = 3$: we already need $(3 + 1)^4 = 256$ evaluations.

This quickly becomes impractical for even modest values of $k$.

### Summary

While this multivariate skip idea lets us reduce multiple variables at once, the cost of interpolating and sending the resulting polynomial $v(X_0, \dots, X_{k-1})$ grows exponentially in $k$.

This defeats the original purpose of reducing prover work—especially in large systems, where even one extra round is expensive.

So although this method is conceptually clean, it's too costly in practice.

In the next section, we’ll present a smarter way to skip $k$ rounds without ever constructing a full multivariate polynomial: the **univariate skip**. This method avoids exponential blowup by changing the structure of the evaluation domain. It’s a subtle but powerful idea.

## Univariate skip

### Key idea: avoiding exponential cost by reorganizing the evaluation domain

In the last section, we saw that trying to skip $k$ rounds all at once by computing a multivariate polynomial $v(X_0, \dots, X_{k-1})$ leads to exponential cost: we need $(d+1)^k$ evaluations just to interpolate that polynomial. This quickly becomes impractical.

The **univariate skip** is a clever technique that avoids this cost. Instead of producing a multivariate polynomial, we restructure the evaluation domain so that we can still skip $k$ rounds—but **end up with a univariate polynomial** that can be interpolated efficiently.

Let’s now walk through exactly how this works, step by step.

### Step 1: Change the structure of the domain

Originally, all our polynomial evaluations happen over the Boolean hypercube $H^n = \{0,1\}^n$. To skip $k$ rounds, we would traditionally keep $k$ variables free and sum over the remaining $n - k$ variables. This gives us:

\begin{equation}
\sum_{\mathbf{x} \in H^{n-k}} C(X_0, \dots, X_{k-1}, \mathbf{x})
\end{equation}

But as we saw, this leads to a multivariate polynomial in $k$ variables, which is too expensive to handle.

**Instead, we now choose a new domain of the form:**
\begin{equation}
D \times H^j
\end{equation}

where:
- $D$ is a **multiplicative subgroup** of the field $\mathbb{F}_p$, and we will choose it to have size $|D| = 2^k$
- $H^j$ is a Boolean hypercube in the remaining $j = n - k$ variables

The key insight is that we are replacing the multivariate Boolean part $\{0,1\}^k$ with a **structured, univariate domain** $D \subset \mathbb{F}_p$. This means that rather than keeping $k$ variables symbolic, we introduce **one univariate variable** $X$, and evaluate $C$ over the domain $(X, \mathbf{x}) \in D \times H^j$.

This choice will allow us to reduce the first $k$ variables in one step while still ending up with a **univariate** polynomial in $X$.

### Step 2: How the table polynomials are reinterpreted

To make this work, we now interpret the data table $T$ differently.

- Before: rows of $T$ were indexed by elements of $H^n = \{0,1\}^n$
- Now: rows of $T$ are indexed by pairs $(x, \mathbf{y}) \in D \times H^j$

Each column $\omega_i$ is now viewed as a function $f_i(x, \mathbf{y})$ defined over this new domain $D \times H^j$.

To interpolate these values as polynomials, we define each $f_i$ as a bivariate polynomial in $(x, \mathbf{y})$ with the following degree bounds:

\begin{equation}
\deg_x f_i(x, \mathbf{y}) \leq |D| - 1, \quad \deg_{y_j} f_i(x, \mathbf{y}) \leq 1 \quad \text{for all } j
\end{equation}

This means:

- The degree in $x$ can be as high as $|D| - 1$, since $x$ ranges over a multiplicative subgroup $D$ of size $|D|$
- The degree in each $y_j$ remains at most $1$, just like in the original multilinear setting

So even though we’re no longer in a Boolean domain for the first $k$ variables, we preserve the same interpolation properties: the polynomials $f_i$ are well-defined and efficiently computable over this new domain.

:::info
**Example: Constraint table with 3 variables**

Suppose we have a constraint polynomial $C(\omega_0, \omega_1) = \omega_1 - \omega_0$, over a table with 3 variables $X_0, X_1, X_2$. We define two columns:

- $\omega_0(X_0, X_1, X_2)$: table column 0, interpreted as a multilinear polynomial
- $\omega_1(X_0, X_1, X_2)$: table column 1, likewise a multilinear polynomial

Here's a sample of 8 rows (the full Boolean cube $\{0,1\}^3$):

| $X_0$ | $X_1$ | $X_2$ | $\omega_0$ | $\omega_1$ | $C(\omega_0, \omega_1)$ |
|------|------|------|-------------|-------------|---------------------------|
| 0 | 0 | 0 | 1 | 1 | 0 |
| 0 | 0 | 1 | 2 | 2 | 0 |
| 0 | 1 | 0 | 3 | 3 | 0 |
| 0 | 1 | 1 | 4 | 4 | 0 |
| 1 | 0 | 0 | 5 | 5 | 0 |
| 1 | 0 | 1 | 6 | 6 | 0 |
| 1 | 1 | 0 | 7 | 7 | 0 |
| 1 | 1 | 1 | 8 | 8 | 0 |

We now want to apply **univariate skip** to fold over $k = 2$ variables, say $X_0$ and $X_1$. Instead of evaluating over $\{0,1\}^2$ for those variables, we treat the 4 assignments as a **multiplicative subgroup** $D$ of size 4.

We then reinterpret each column $\omega_i$ as a bivariate polynomial $f_i(x, y)$ over the domain $D \times \{0,1\}$, where:

- $x$ encodes the subgroup point corresponding to $(X_0, X_1)$
- $y$ encodes the remaining Boolean variable $X_2$

:::

### Step 3: What happens to the constraint polynomial $C$

Now let’s consider the constraint polynomial $C$, which is composed from the table polynomials:

\begin{equation}
C(x, \mathbf{y}) = C\left(f_0(x, \mathbf{y}), f_1(x, \mathbf{y}), \dots, f_{\ell - 1}(x, \mathbf{y})\right)
\end{equation}

Suppose $C$ has total degree $d$ in its arguments. Since each $f_i(x, \mathbf{y})$ has degree at most $|D| - 1$ in $x$, the composition $C(x, \mathbf{y})$ has degree at most $d(|D| - 1)$ in $x$.

Therefore, if we fix $\mathbf{y}$ and vary $x \in \mathbb{F}_p$, the function $x \mapsto C(x, \mathbf{y})$ is a **univariate polynomial** of degree at most:

\begin{equation}
\deg_x C(x, \mathbf{y}) \leq d(|D| - 1)
\end{equation}

This is the crucial observation: by reinterpreting the domain of the first $k$ variables as a single variable $x \in D$, the constraint polynomial becomes univariate in $x$.

This allows us to interpolate it using only a linear number of evaluations in $x$, avoiding the exponential cost of multivariate interpolation.

### Summary of what we gain

Let’s summarize what we’ve done:

- We replaced the $k$ Boolean variables $\{0,1\}^k$ with a multiplicative subgroup $D \subset \mathbb{F}_p$ of size $2^k$
- We now represent the table rows over $D \times H^j$, where $j = n - k$
- Each table column becomes a polynomial $f_i(x, \mathbf{y})$ with degree at most $|D| - 1$ in $x$ and multilinear in $\mathbf{y}$
- The constraint polynomial $C(x, \mathbf{y})$ becomes univariate in $x$, with degree at most $d(|D| - 1)$

In the next section, we will explain how to construct and evaluate this univariate polynomial in practice, and show precisely how it lets us skip the first $k$ rounds of sumcheck using only evaluations in the base field $\mathbb{F}$.

## Computing the univariate polynomial explicitly

After reorganizing the domain to $D \times H^j$ and interpreting our constraint polynomial accordingly, we’re now ready to compute the univariate polynomial that will let us skip the first $k$ rounds of the sumcheck protocol.

In the standard sumcheck approach, each round reduces over one variable. But now, since we’ve replaced the first $k$ variables with a single univariate variable $X$ ranging over $D$, we can reduce over all $n - k$ remaining variables in one step.

To do this, the prover $\mathcal{P}$ constructs the following univariate polynomial:

\begin{equation}
v(X) = \sum_{\mathbf{x} \in H^j} \hat{\delta}_j(\boldsymbol{\alpha}, \mathbf{x}) \cdot C(X, \mathbf{x})
\end{equation}

Here:

- $X$ is the variable ranging over the multiplicative subgroup $D$
- $\mathbf{x} \in H^j$ represents all possible assignments to the remaining $j = n - k$ Boolean variables
- $\boldsymbol{\alpha} \in \mathbb{G}^j$ is a random vector of verifier challenges for those $j$ variables
- $\hat{\delta}_j(\boldsymbol{\alpha}, \mathbf{x})$ is the *delta interpolant* over the Boolean cube $H^j$, which evaluates to $1$ when $\mathbf{x} = \boldsymbol{\alpha}$ and $0$ otherwise

This construction is exactly analogous to how sumcheck typically reduces over one variable at a time. The difference is that here we reduce over **all** the $j$ Boolean variables at once—leaving us with a single variable $X$.

The result is a univariate polynomial $v(X)$, which behaves just like the round-one polynomial in sumcheck—but it's doing the job of **$k$ rounds at once**.

### What is the degree of $v(X)$?

To understand how costly it is to compute or interpolate $v(X)$, we need to know its degree.

Recall from earlier:

- The constraint polynomial $C(X, \mathbf{x})$ has degree at most $d(|D| - 1)$ in $X$
- The delta interpolant $\hat{\delta}_j(\boldsymbol{\alpha}, \mathbf{x})$ depends only on $\mathbf{x}$, not on $X$

So when we form the sum over $\mathbf{x} \in H^j$, the delta weights act as constants with respect to $X$. That means the degree of $v(X)$ is determined solely by the degree of $C(X, \mathbf{x})$ in $X$ for each $\mathbf{x}$.

Therefore, we have:

\begin{equation}
\deg(v) \leq d(|D| - 1)
\end{equation}

This is a manageable degree. For example, if we choose $|D| = 2^k$, then $v(X)$ has degree at most $d(2^k - 1)$.

So to interpolate $v(X)$, we only need roughly $d(2^k - 1) + 1$ evaluations—**a linear cost in $2^k$**, rather than the exponential cost of multivariate interpolation from the previous approach.

### What does this mean?

By computing this single univariate polynomial $v(X)$, we’ve effectively reduced all $k$ of the first variables **in one round**, while remaining entirely in the base field $\mathbb{F}$. This means:

- The expensive extension field evaluations ($\mathbb{G}$) are avoided in these first $k$ rounds
- The verifier still retains soundness guarantees, thanks to the randomness in $\boldsymbol{\alpha}$
- The prover performs more base field work up front, but saves significantly on extension field work overall

This is the core benefit of the **univariate skip**: the same soundness, much less extension field cost.

In the next section, we’ll quantify exactly how many evaluations the prover needs to compute $v(X)$, and compare it to the cost of the standard sumcheck protocol.

## Complexity analysis and demonstration

Let’s now analyze how much work the prover saves by using the univariate skip. We’ll walk through both the **naive approach** (no skipping) and the **univariate skip** approach, and clearly show the difference in the number of evaluations required.

### Step 1: Cost of the naive multivariate approach

If we try to skip $k$ rounds by constructing a multivariate polynomial in $k$ variables (as discussed earlier), then the prover must evaluate this polynomial at enough points to interpolate it fully.

Since the polynomial has degree at most $d$ in each variable, the total number of required evaluations is:

\begin{equation}
(d + 1)^k
\end{equation}

This grows exponentially with $k$, and quickly becomes infeasible for large $k$.

### Step 2: Cost of the univariate skip

With the univariate skip, we never construct a multivariate polynomial. Instead, we compute a single univariate polynomial $v(X)$ over the multiplicative subgroup $D \subset \mathbb{F}$ of size $|D| = 2^k$.

The key idea is:

- The prover computes $C(X, \mathbf{x})$ for all $\mathbf{x} \in H^j$ (where $j = n - k$), and for $X$ values that are **not** in $D$
- For $X \in D$, we know that $C(X, \mathbf{x}) = 0$ for all $\mathbf{x}$ (because $C$ vanishes on the trace), so those points don’t require evaluation

Hence, we only need to evaluate $C(X, \mathbf{x})$ for points $X \notin D$. There are $d(|D| - 1) + 1$ such $X$ values needed to interpolate the univariate polynomial $v(X)$.

So, the total number of constraint evaluations is:

\begin{equation}
2^j \cdot (d(|D| - 1) + 1 - |D|)
\end{equation}

We subtract $2^j \cdot |D|$ to account for the fact that evaluations on $X \in D$ are zero and thus free.

Let’s plug in $|D| = 2^k$ and $j = n - k$. Then:

\begin{equation}
\text{Total evaluations} = 2^{n-k} \cdot \left(d(2^k - 1) + 1 - 2^k\right) = 2^{n-k}(d - 1)(2^k - 1)
\end{equation}

This is much smaller than $(d + 1)^k$, especially for large $k$.

### Step 3: A concrete example

Let’s make this tangible with a small example.

Suppose:
- $n = 3$ (so $2^n = 8$ total rows)
- $d = 2$ (the constraint polynomial has degree at most $2$)
- $k = 2$ (we try to skip the first $2$ rounds)

Then $j = n - k = 1$, and $|D| = 2^k = 4$. Applying our formula:

- Naive multivariate approach requires:

\begin{equation}
(d + 1)^k = 3^2 = 9 \quad \text{evaluations}
\end{equation}

- Univariate skip requires:

\begin{equation}
2^{n - k}(d - 1)(2^k - 1) = 2^1 \cdot 1 \cdot 3 = 6 \quad \text{evaluations}
\end{equation}

So we save 33% of the work right away in this small example. The savings become even more dramatic as $k$ increases.

## Comparison with the standard approach (no skipping)

Let’s now compare the prover’s cost in the **standard sumcheck** protocol with and without the univariate skip.

### Standard approach (no skip):

- In the first round (over $X_0$), evaluations happen in the base field $\mathbb{F}$: cost is cheap.
- In the remaining $k - 1$ rounds, evaluations happen in the extension field $\mathbb{G}$: these are much more expensive.

So the total cost for the first $k$ rounds looks like:

\begin{equation}
\underbrace{2^{n - 1}(d - 1) C_F}_{\text{Base field cost (round 0)}} + \underbrace{2^{n - k}(d - 1)(2^{k - 1} - 1) C_G}_{\text{Extension field cost (rounds 1 to $k-1$)}}
\end{equation}

Here:
- $C_F$ is the cost of evaluating $C$ in the base field
- $C_G$ is the cost of evaluating $C$ in the extension field, typically much larger

### Univariate skip approach:

By using the univariate skip, we push **all** $k$ rounds into the first step and do the work **entirely in the base field**. The cost becomes:

\begin{equation}
\underbrace{2^{n - k}(d - 1)(2^k - 1) C_F}_{\text{All $k$ rounds in base field}}
\end{equation}

This has two major benefits:
- The total number of evaluations is lower
- All evaluations are done in the base field $\mathbb{F}$, which is significantly cheaper than $\mathbb{G}$

## Summary

The univariate skip lets the prover reduce multiple variables in one shot, using fewer evaluations and keeping all the work in the base field. This saves both time and computational resources.

In large proof systems, where thousands or millions of constraint evaluations are needed, these savings translate to major performance gains.

Next, we'll walk through the final optimized protocol using univariate skip, and see how all the pieces fit together.