# Ring-Switching: A deep dive into efficient small-field polynomial commitments

## The SNARK designer's dilemma: small-field arithmetic vs. large-field commitments

For those of us deep in the trenches of SNARK design and implementation, the pursuit of prover efficiency is relentless. We're constantly seeking ways to reduce cryptographic overhead and make zero-knowledge proofs more practical for increasingly complex computations. One of the most effective strategies on this front has been the adoption of **tiny fields** for the arithmetization phase of a SNARK.

### The quest for prover speed via tiny fields

When we represent a computation as an arithmetic circuit or a system of polynomial equations, the choice of the underlying finite field `K` for this representation has profound performance implications. Using "tiny" fields – such as the prime field `F_2` (especially relevant for binary circuits) or other small prime fields `F_p` (e.g., 32-bit or 64-bit primes like Goldilocks or Baby Bear) – drastically reduces the bit-length of operands. This, in turn, speeds up the polynomial arithmetic (NTTs/FFTs, multiplications, additions) that forms the backbone of most prover algorithms. The benefits are clear: faster provers, lower computational costs, and increased throughput.

### The Polynomial Commitment Scheme (PCS) challenge

While tiny fields are a boon for arithmetization, the cryptographic heart of many SNARKs – the Polynomial Commitment Scheme (PCS) – often presents a different set of requirements. Many powerful and efficient PCS for multilinear polynomials (MLPs), which are a common choice for modern arithmetizations, are naturally constructed or achieve optimal properties (like succinctness or pairing-friendliness for KZG-based schemes, or concrete efficiency for FRI-based schemes) when operating over **larger extension fields `L`** of our tiny arithmetization field `K`.

This creates a fundamental tension:
- Our computation (and thus our core polynomials) lives over `K`.
- Our commitment mechanism might prefer to live, or offer better features, over `L`.

### The perils of naive embedding

A straightforward approach to bridge this gap might be to simply "embed" the coefficients of our `K`-polynomial into the larger field `L` (e.g., if `k ∈ K`, map it to `(k, 0, ..., 0)` in some `K`-basis representation of `L`) and then apply the `L`-field PCS. However, this naive strategy suffers from significant drawbacks:

1. **Embedding overhead:** If an `L`-element is effectively `d = [L:K]` times larger (in terms of `K`-elements) than a `K`-element, the `L`-field PCS will operate on these larger elements. This means commitment sizes, proof sizes, and verification times might scale with the data size of `L`, even if the actual information content of our polynomial is only `K`-sized. We're paying a `d`-fold penalty in element size for no good reason, negating some of the benefits of using `K` in the first place.
2. **Loss of `K`-ness guarantee:** When we commit to a polynomial whose coefficients are treated as `L`-elements, the `L`-field PCS, by itself, doesn't enforce that these coefficients *originated* from `K` or that they even *could* be represented as elements of `K` (i.e., that their non-first `K`-basis components are zero). A malicious prover could potentially commit to a genuine `L`-polynomial that doesn't correspond to any valid `K`-polynomial, which could be problematic depending on the SNARK's security arguments.

:::info
Consider $K$ as the ~64-bit Goldilocks field and $L$ its quadratic extension, so elements of $L$ can be written as $a+b\alpha$ where $a,b \in K$.

1. Embedding Overhead: A polynomial $t(Y) = \sum c_i Y^i$ with coefficients $c_i \in K$ (each ~64 bits) is naively committed by mapping each $c_i$ to an element like $c_i + 0\alpha \in L$. This element is represented using ~128 bits. If $t(Y)$ has $N$ coefficients, the $L$-PCS effectively processes $N \times \text{size}(L)$ bits of data for what is truly $N \times \text{size}(K)$ bits of information, often doubling the data size for cryptographic operations.

2. Loss of $K$-ness Guarantee: The $L$-PCS commits to a polynomial $\sum c'_j Y^j$ where $c'_j \in L$. It cannot inherently distinguish if a coefficient $c'_j$ corresponds to an honest $c_j \in K$ (embedded as $c_j+0\alpha$) or if it's a general $L$-element $a_j+b_j\alpha$ with $b_j \neq 0$, chosen by a malicious prover. If the SNARK's soundness relies on the committed polynomial having coefficients strictly from $K$, this ambiguity can be exploited.
:::

These issues mean that a more sophisticated approach is required if we want to truly harness the power of tiny arithmetization fields alongside robust large-field PCS.

### Introducing Ring-Switching: An elegant solution

This is where **Ring-Switching**, the technique developed by Diamond and Posen, enters the picture. It offers a generic and highly efficient "compiler" that transforms a given MLP PCS designed for a large extension field `L` into a new MLP PCS that operates on polynomials with coefficients genuinely from a small base field `K`.

Crucially, Ring-Switching achieves this:
* **Without embedding overhead:** The commitment costs are proportional to the actual information content of the `K`-polynomial.
* **With minimal additive overhead** in the evaluation protocol.
* While preserving the essential properties of the underlying `L`-field PCS.

The goal of this article is to provide a detailed technical walkthrough of the Ring-Switching mechanism. We'll explore the algebraic foundations, step through the protocol, and analyze why it's an effective solution to this core dilemma in SNARK design. For crypto engineers looking to understand or implement state-of-the-art proving systems, a grasp of techniques like Ring-Switching is becoming increasingly vital.

## Multilinear Polynomials (MLPs) and Notation

Multilinear polynomials are central to everything in ring-switching, tensor algebras, and zero-knowledge IOPs. Let us clarify exactly what they are and how we work with them.

An $ℓ$-variate polynomial

\begin{equation}
t(X_0, \dots, X_{\ell - 1}) \in K[X_0, \dots, X_{\ell - 1}]
\end{equation}

is called **multilinear** if each variable $X_i$ appears with degree at most 1. That is, $t$ contains no monomials like $X_i^2$ or $X_i X_j^2$. We denote the set of all such polynomials by

\begin{equation}
K[X_0, \dots, X_{\ell - 1}]_{\preceq 1}
\end{equation}

These polynomials form a $K$-vector space of dimension $2^\ell$.

The reason is simple: every multilinear polynomial is uniquely determined by its values on the boolean hypercube

\begin{equation}
B^\ell := \{0,1\}^\ell
\end{equation}

That is, once you know $t(v)$ for all $v \in B^\ell$, you can reconstruct $t$ exactly. These values are often referred to as the **Lagrange coefficients** of $t$ over $B^\ell$.

:::info
### Example: Multilinear polynomial in 2 variables

Let $\ell = 2$ and let $K$ be any field. The boolean hypercube is:

\begin{equation}
B^2 = \{(0,0), (1,0), (0,1), (1,1)\}
\end{equation}

Suppose $t(X_0, X_1) \in K[X_0, X_1]_{\preceq 1}$ has the following evaluations:

\begin{align}
y_{00} &= t(0,0) \\
y_{10} &= t(1,0) \\
y_{01} &= t(0,1) \\
y_{11} &= t(1,1)
\end{align}

Then $t(X_0, X_1)$ can be written as its **Lagrange interpolation**:

\begin{equation}
\begin{aligned}
t(X_0, X_1) &= y_{00} (1 - X_0)(1 - X_1) + y_{10} X_0(1 - X_1) \\
&\quad + y_{01} (1 - X_0)X_1 + y_{11} X_0 X_1
\end{aligned}
\end{equation}

This is a linear combination of tensor products of univariate linear polynomials in each variable. Each term is multilinear, and the $2^2 = 4$ values $y_{ij} \in K$ completely determine $t$.
:::

In practice, we usually represent an $ℓ$-variate multilinear polynomial $t$ by its vector of evaluations on $B^\ell$, stored in lex order (e.g., $(0,0), (1,0), (0,1), (1,1)$ in 2 variables). This makes it easy to perform operations like interpolation, low-degree extension, and folding—all of which play critical roles in protocols like sumcheck and ring-switching.

## Refinement and Packing: Turning field layers into structure

A central mechanism in the ring-switching protocol is the ability to move back and forth between large-field polynomials and structured small-field representations. This is achieved through two dual operations: refinement and packing.

These operations are made possible by working within a recursive tower of binary fields. Specifically, we fix a tower:

\begin{equation}
T_\iota \subset T_\tau
\end{equation}

where $T_\iota = \mathbb{F}_{2^{2^\iota}}$ and $T_\tau = \mathbb{F}_{2^{2^\tau}}$, both built recursively. The difference in tower heights, denoted $\kappa = \tau - \iota$, determines how much we refine or compress.

### Refinement: from coarse to fine

Refinement is the process of expanding a polynomial over a large field into an equivalent one over a smaller field, using more variables. It is conceptually similar to "zooming in" on each coefficient and breaking it into smaller pieces.

Suppose we have a polynomial

\begin{equation}
t(X_0, \dots, X_{\ell-1}) \in T_\tau[X]
\end{equation}

with $2^\ell$ Lagrange coefficients in $T_\tau$. Since $T_\tau$ is a $2^\kappa$-dimensional vector space over $T_\iota$, every element $\alpha \in T_\tau$ can be uniquely expressed as:

\begin{equation}
\alpha = \sum_{i=0}^{2^\kappa - 1} \alpha_i \cdot \beta_i \quad \text{with } \alpha_i \in T_\iota
\end{equation}

Using this decomposition, we replace each $T_\tau$-coefficient with its $2^\kappa$ components in $T_\iota$. This gives a new polynomial

\begin{equation}
t'(X_0, \dots, X_{\ell + \kappa - 1}) \in T_\iota[X]
\end{equation}

which we call the refinement of $t$.

:::info
Refinement spreads the same information across a larger space:
- It increases the number of variables from $\ell$ to $\ell + \kappa$.
- It lowers the field from $T_\tau$ to $T_{\tau - \kappa}$.
- The total information content (in bits) remains unchanged.
:::

### Packing: from fine to coarse

Packing is the reverse operation. It compresses many small-field values into fewer large-field ones, reducing the number of variables in the process.

Suppose we begin with a polynomial

\begin{equation}
t(X_0, \dots, X_{\ell - 1}) \in T_\iota[X]
\end{equation}

with $2^\ell$ Lagrange coefficients. We group these into blocks of $2^\kappa$ and combine each block using the $T_\iota$-basis $(\beta_0, \dots, \beta_{2^\kappa - 1})$ to obtain coefficients in $T_\tau$. The result is a new polynomial

\begin{equation}
t'(X_0, \dots, X_{\ell - \kappa - 1}) \in T_\tau[X]
\end{equation}

This packed polynomial encodes the same total data but over a smaller domain and a larger field. This is especially useful for committing to a polynomial using a large-field PCS.

### Algebraic foundation

These transformations are not arbitrary—they rely on the algebraic structure of binary field towers. The decomposition

\begin{equation}
\alpha = \sum_{i=0}^{2^\kappa - 1} \alpha_i \cdot \beta_i
\end{equation}

is a coordinate expansion with respect to a specific basis of $T_\tau$ over $T_\iota$. The ability to move between $(\alpha_0, \dots, \alpha_{2^\kappa - 1}) \in T_\iota^{2^\kappa}$ and $\alpha \in T_\tau$ is what gives refinement and packing their meaning.

We constantly rely on this view when working with tensor algebra later in ring-switching. In fact, we often treat a large-field element and its small-field coordinate tuple as two sides of the same coin.

### Why this only works in binary towers

This entire framework depends crucially on the recursive nature of binary field towers. Over prime fields like $\mathbb{F}_p$, or classical binary fields like $\mathbb{F}_{2^n}$ constructed via univariate polynomials, there is no such built-in basis hierarchy. In such settings, operations like refinement and packing are not algebraically well-defined.

The layered structure of $T_\iota \subset T_\tau$ makes it possible to switch between representations without ambiguity or loss of structure. This is what allows ring-switching protocols to combine small-field computation with large-field commitments in a mathematically sound way.

:::info
### Example: Refining and Packing Polynomials

Let $T_3 = \mathbb{F}_{2^8}$ and $T_7 = \mathbb{F}_{2^{128}}$. Then $\kappa = 4$, and $T_7$ is a $2^4 = 16$-dimensional vector space over $T_3$.

Suppose we have:

\begin{equation}
t(X_0, \dots, X_{19}) \in T_7[X]
\end{equation}

with $2^{20}$ coefficients. Refining this polynomial yields:

- $2^{24}$ coefficients in $T_3$
- A refined polynomial

\begin{equation}
t'(X_0, \dots, X_{23}) \in T_3[X]
\end{equation}

Conversely, if we start with $t'$ and group every 16 coefficients using the basis of $T_7$ over $T_3$, we obtain the packed version of $t$ back in $T_7[X_0, \dots, X_{19}]$.

The information is preserved in both directions; only its format changes.
:::

## Polynomial Commitment Scheme (PCS) Interface

A Polynomial Commitment Scheme (PCS) is a cryptographic primitive that allows a prover to commit to a polynomial once and later reveal evaluations of it at chosen points, along with succinct, verifiable proofs.

We denote a generic PCS by $\Pi$. Its interface provides the following core functionalities:

- **Commit**

\begin{equation}
\Pi.\text{Commit}(t) \rightarrow C
\end{equation}

This algorithm takes a polynomial $t$ and returns a commitment $C$ that binds the prover to $t$, without revealing it.

- **OpenProof**

\begin{equation}
\Pi.\text{OpenProof}(C, t, z, y) \rightarrow \pi
\end{equation}

Given a polynomial $t$, its commitment $C$, an evaluation point $z$, and a claimed value $y = t(z)$, this algorithm generates a proof $\pi$ attesting to the correctness of the evaluation.

- **VerifyProof**

\begin{equation}
\Pi.\text{VerifyProof}(C, z, y, \pi) \rightarrow \{ \text{accept}, \text{reject} \}
\end{equation}

This verification algorithm checks that the evaluation $y = t(z)$ is consistent with the commitment $C$ and proof $\pi$.

These operations are typically designed to be *succinct* (the commitment and proofs are small) and *binding* (the prover cannot later open the commitment to a different polynomial).

### Our Setting: Small Field, Large Field

In the ring-switching context, we deal with two different fields:

- A **small base field** $K$ (e.g., $\mathbb{F}_{2^8}$ or Goldilocks), where our computations and polynomial definitions originate.
- A **large extension field** $L$, built as a tower over $K$, such that $[L : K] = 2^\kappa$.

We assume access to a secure PCS $\Pi'_L$ that works over the large field $L$. That is, $\Pi'_L$ supports committing to and proving evaluations of polynomials:

\begin{equation}
t' \in L[X_0, \dots, X_{\ell'}]_{\preceq 1}
\end{equation}

Our goal is to construct a PCS for polynomials over the small field $K$ by leveraging $\Pi'_L$ through a technique called **Ring-Switching**. This construction relies on *packing* the $K$-polynomial into an $L$-polynomial, committing to it via $\Pi'_L$, and then proving evaluations in such a way that they correctly reflect the original small-field structure.

This approach enables us to enjoy the efficiency and expressivity of large-field commitments while working with polynomials defined natively over the small field $K$.

Would you like to follow this with a section showing how packing and ring-switching enable this transformation?

## The Algebraic Core: Tensor Algebra and the Secret of Evaluation

At the heart of the ring-switching technique lies a fundamental question:

**How can we verify the evaluation of a small-field polynomial $t$ over $K$ when we only have a commitment to its packed version $t'$ over a larger field $L$?**

To bridge this gap, we introduce a central algebraic object: the tensor algebra $A = L \otimes_K L$. This structure allows us to package many partial evaluations of $t$ into a single element $\hat{s} \in A$, from which the verifier can recover the final claimed value $s = t(r)$.

### Setup: What we know and what we want

Let:
- $t \in K[X_0, \dots, X_{\ell - 1}]_{\preceq 1}$ be the original $\ell$-variate multilinear polynomial over the small field $K$,
- $t' \in L[X_0, \dots, X_{\ell - \kappa - 1}]_{\preceq 1}$ be its packed version over the large field $L$,
- $r = (r_0, \dots, r_{\ell - 1}) \in L^\ell$ be the point at which we want to evaluate,
- $s = t(r)$ be the claimed evaluation.

The verifier has a commitment to $t'$ over $L$, but no direct access to $t$ or its coefficients in $K$. We want to verify that $s$ is indeed $t(r)$.

### Step 1: Splitting the evaluation point

We split the point $r$ into:
- $r_{\text{prefix}} = (r_0, \dots, r_{\kappa - 1})$
- $r_{\text{suffix}} = (r_\kappa, \dots, r_{\ell - 1})$

This split matches the packing scheme, where $t$ was packed along the first $\kappa$ variables.

By multilinearity, the evaluation $t(r)$ can be expanded as:

\begin{equation}
t(r) = \sum_{v \in \{0,1\}^\kappa} t(v, r_{\text{suffix}}) \cdot \text{eqf}(r_{\text{prefix}}, v)
\end{equation}

Each term $t(v, r_{\text{suffix}})$ is called a **partial evaluation**, which we denote as:

\begin{equation}
S_v := t(v, r_{\text{suffix}}) \in L
\end{equation}

So $t(r)$ is a weighted sum of $2^\kappa$ values $S_v$, one for each possible $v \in \{0,1\}^\kappa$.

:::info
### Example: Splitting an Evaluation Point

Let $K = \mathbb{F}_2$ and consider a trivariate multilinear polynomial over $K$:

\begin{equation}
t(X_0, X_1, X_2) = X_0 + X_1 + X_2 + X_0 X_1
\end{equation}

Let’s take $\kappa = 1$, which means we are packing over the first variable $X_0$. Then:
- $r_{\text{prefix}} = (r_0)$
- $r_{\text{suffix}} = (r_1, r_2)$

We want to evaluate $t$ at $r = (r_0, r_1, r_2) \in L^3$, but we'll do it by computing:

\begin{equation}
t(r) = \sum_{v \in \{0,1\}} t(v, r_1, r_2) \cdot \text{eqf}(r_0, v)
\end{equation}

Let’s choose a specific point in $L^3$, say:
- $r_0 = \alpha$
- $r_1 = 1$
- $r_2 = \alpha + 1$

Now compute the two partial evaluations:
- For $v = 0$:
\begin{aligned}
S_0 &= t(0, r_1, r_2) \\
&= 0 + r_1 + r_2 + 0 \\
&= r_1 + r_2 \\
&= 1 + (\alpha + 1) = \alpha
\end{aligned}
- For $v = 1$:
\begin{aligned}
S_1 &= t(1, r_1, r_2) \\
&= 1 + r_1 + r_2 + 1 \cdot r_1 \\
&= 1 + r_1 + r_2 + r_1 \\
&= 1 + 2r_1 + r_2 \\
&= 1 + 0 + (\alpha + 1) \\
&= \alpha + 1
\end{aligned}

Now interpolate using $r_0 = \alpha$:
- $\text{eqf}(r_0, 0) = 1 - r_0 = 1 - \alpha$
- $\text{eqf}(r_0, 1) = r_0 = \alpha$

So the full evaluation is:

\begin{align}
t(r) &= S_0 \cdot (1 - \alpha) + S_1 \cdot \alpha \\
&= \alpha \cdot (1 - \alpha) + (\alpha + 1) \cdot \alpha \\
&= \alpha - \alpha^2 + \alpha^2 + \alpha \\
&= \alpha + \alpha = 0
\end{align}

So $t(r) = 0$.

This example shows how a packed polynomial allows you to recover $t(r)$ from just two partial evaluations $S_0$ and $S_1$, weighted by equality polynomials in $r_0$.
:::

### Step 2: The Problem — How to Access All $S_v$

The verifier needs to use these $S_v$ values to check that $s = t(r)$, but they’re not explicitly available. We only have access to $t'$, the packed polynomial over $L$.

To recover all $S_v$ in a single object, we construct an element $\hat{s} \in A = L \otimes_K L$ that encodes the full vector $(S_v)_v$ in its **column decomposition**.

### Step 3: Introducing the Tensor Algebra $A = L \otimes_K L$

The tensor algebra $A$ can be thought of as a formal space where we can write combinations like $\alpha \otimes \beta$ for $\alpha, \beta \in L$, with bilinear operations over $K$.

We fix a $K$-basis $(\beta_u)_{u \in \{0,1\}^\kappa}$ for $L$. Then any element $a \in A$ has a canonical expansion:

\begin{equation}
a = \sum_{u,v \in \{0,1\}^\kappa} k_{u,v} \cdot (\beta_u \otimes \beta_v), \quad k_{u,v} \in K
\end{equation}

This $2^\kappa \times 2^\kappa$ grid of coefficients can be interpreted:
- **Column-wise**: Each $c_v = \sum_u k_{u,v} \beta_u \in L$, giving

\begin{equation}
a = \sum_v c_v \otimes \beta_v
\end{equation}

- **Row-wise**: Each $r_u = \sum_v k_{u,v} \beta_v \in L$, giving

\begin{equation}
a = \sum_u \beta_u \otimes r_u
\end{equation}

This flexibility is exactly what we need: $\hat{s}$ will use its columns to store $S_v$ values, and its rows will later participate in a verification sumcheck.

:::info
### Example: Understanding the Tensor Algebra $A = L \otimes_K L$

Let’s work with:
- $K = \mathbb{F}_2$
- $L = \mathbb{F}_4 = \mathbb{F}_2[\alpha]/(\alpha^2 + \alpha + 1)$, so $[L : K] = 2$ and $\kappa = 1$

We fix the standard $K$-basis for $L$:
\begin{equation}
(\beta_0, \beta_1) = (1, \alpha)
\end{equation}

Then $A = L \otimes_K L$ is a $K$-vector space of dimension $4$, with basis:
\begin{equation}
\{ 1 \otimes 1,\ 1 \otimes \alpha,\ \alpha \otimes 1,\ \alpha \otimes \alpha \}
\end{equation}

Let’s define an element $a \in A$ by choosing $K$-coefficients:

\begin{align}
a &= (1 \otimes 1) + (1 \otimes \alpha) + (\alpha \otimes 1) \\
&= 1 \cdot (1 \otimes 1) + 1 \cdot (1 \otimes \alpha) + 1 \cdot (\alpha \otimes 1) + 0 \cdot (\alpha \otimes \alpha)
\end{align}

So in terms of coefficients $k_{u,v}$, we have:

\begin{equation}
\begin{bmatrix}
k_{00} & k_{01} \\
k_{10} & k_{11}
\end{bmatrix}
= \begin{bmatrix}
1 & 1 \\
1 & 0
\end{bmatrix}
\end{equation}

### Column decomposition

We fix each column index $v$ and form:
\begin{align}
c_0 &= k_{00} \cdot \beta_0 + k_{10} \cdot \beta_1 = 1 \cdot 1 + 1 \cdot \alpha = 1 + \alpha \in L \\
c_1 &= k_{01} \cdot \beta_0 + k_{11} \cdot \beta_1 = 1 \cdot 1 + 0 \cdot \alpha = 1 \in L
\end{align}

So:
\begin{equation}
a = c_0 \otimes \beta_0 + c_1 \otimes \beta_1 = (1 + \alpha) \otimes 1 + 1 \otimes \alpha
\end{equation}

### Row decomposition

We now fix each row index $u$ and compute:
\begin{align}
r_0 &= k_{00} \cdot \beta_0 + k_{01} \cdot \beta_1 = 1 \cdot 1 + 1 \cdot \alpha = 1 + \alpha \in L \\
r_1 &= k_{10} \cdot \beta_0 + k_{11} \cdot \beta_1 = 1 \cdot 1 + 0 \cdot \alpha = 1 \in L
\end{align}

So:
\begin{equation}
a = \beta_0 \otimes r_0 + \beta_1 \otimes r_1 = 1 \otimes (1 + \alpha) + \alpha \otimes 1
\end{equation}

### Summary

We wrote the same $a \in A$ in two ways:

- **Column form**:

\begin{equation}
a = (1 + \alpha) \otimes 1 + 1 \otimes \alpha
\end{equation}

- **Row form**:

\begin{equation}
a = 1 \otimes (1 + \alpha) + \alpha \otimes 1
\end{equation}

Both views contain the same data, just reorganized. This is exactly the kind of flexibility that ring-switching uses to package partial evaluations in column form, then later access them via the rows.
:::

### Step 4: Computing $\hat{s}$ from $t'$ and $r_{\text{suffix}}$

To bundle all $S_v$ into $\hat{s}$, we:

**Step 1: Lift $t'$ into $A$**

\begin{equation}
\varphi_1(t') := 1 \otimes t'(X_0, \dots, X_{\ell - \kappa - 1})
\end{equation}

What does this mean?

We are starting with the polynomial $t'$, which is defined over $L$ and has coefficients $t'(w) \in L$ for each $w \in \{0,1\}^{\ell - \kappa}$. Now, we want to interpret this polynomial as taking values in the *tensor algebra* $A = L \otimes_K L$ rather than just in $L$.

To do that, we *embed* each coefficient $t'(w) \in L$ into $A$ using the **right embedding** $\varphi_1$, which sends any $\alpha \in L$ to the element $1 \otimes \alpha \in A$.

This turns the original $L$-polynomial into an $A$-valued polynomial. So now, instead of assigning each point $w$ a value $t'(w) \in L$, we assign it the value $1 \otimes t'(w) \in A$.

This embedding is important because it lets us manipulate $t'$ inside the richer algebraic space $A$, where we can then evaluate it at left-embedded inputs and later extract structure (like $S_v$ values) from its column decomposition.

**2. Evaluate $\varphi_1(t')$ at the left-embedded suffix point**

\begin{equation}
\hat{s} := \varphi_1(t')(\varphi_0(r_\kappa), \dots, \varphi_0(r_{\ell - 1}))
\end{equation}

We are now evaluating the $A$-valued polynomial $\varphi_1(t')$ at a point in $A^{\ell - \kappa}$, where each input variable $X_i$ is substituted with a *left-embedded* version of the corresponding suffix coordinate $r_i$.

This left embedding is defined as $\varphi_0(r_i) = r_i \otimes 1 \in A$. It injects each $r_i \in L$ into the **first slot** of the tensor algebra.

Since $t'$ is a multilinear polynomial, we can write its evaluation at this embedded point using standard multilinear interpolation:

\begin{equation}
\hat{s} = \sum_{w \in \{0,1\}^{\ell - \kappa}} \text{eqf}(r_{\text{suffix}}, w) \otimes t'(w)
\end{equation}

3. **Substitute the packed definition of $t'(w)$**:

From packing, we know:

\begin{equation}
t'(w) = \sum_{v \in \{0,1\}^\kappa} t(v, w) \cdot \beta_v
\end{equation}

Substitute this into the expression for $\hat{s}$:

\begin{align}
\hat{s} &= \sum_w \text{eqf}(r_{\text{suffix}}, w) \otimes \left( \sum_v t(v, w) \cdot \beta_v \right) \\
&= \sum_v \underbrace{\left( \sum_w t(v, w) \cdot \text{eqf}(r_{\text{suffix}}, w) \right)}_{t(v, r_{\text{suffix}}) = S_v} \otimes \beta_v
\end{align}

But $\sum_w t(v, w) \cdot \text{eqf}(r_{\text{suffix}}, w)$ is simply $t(v, r_{\text{suffix}}) = S_v$.

:::info
### Example: Computing $\hat{s}$ from $t'$ and $r_{\text{suffix}}$

Let’s work with:
- $K = \mathbb{F}_2$
- $L = \mathbb{F}_4 = \mathbb{F}_2[\alpha]/(\alpha^2 + \alpha + 1)$
- Basis: $(\beta_0, \beta_1) = (1, \alpha)$, so $\kappa = 1$
- $\ell = 2$, so the original polynomial $t \in K[X_0, X_1]_{\preceq 1}$
- The packed polynomial $t' \in L[X_0]_{\preceq 1}$

#### Step 1: Define $t$ and compute $t'$

Let $t$ be defined on $B^2$ as:
- $t(0,0) = 1$
- $t(1,0) = 0$
- $t(0,1) = 1$
- $t(1,1) = 1$

Packing over the first variable ($\kappa = 1$), we construct $t'$ over $L$:

\begin{equation}
t'(w_0) = \sum_{v_0 \in \{0,1\}} t(v_0, w_0) \cdot \beta_{v_0}
\end{equation}

So:
- $t'(0) = t(0,0) \cdot 1 + t(1,0) \cdot \alpha = 1 \cdot 1 + 0 \cdot \alpha = 1$
- $t'(1) = t(0,1) \cdot 1 + t(1,1) \cdot \alpha = 1 \cdot 1 + 1 \cdot \alpha = 1 + \alpha$

Thus $t'(X_0) \in L[X_0]$ is the multilinear polynomial with:
- $t'(0) = 1$
- $t'(1) = 1 + \alpha$

#### Step 2: Lift $t'$ into $A$

We now write $\varphi_1(t') = 1 \otimes t'(X_0)$, i.e., each coefficient is placed into $A$ as $1 \otimes t'(w)$.

#### Step 3: Choose an evaluation point

Let’s evaluate at $r = (r_0, r_1) \in L^2$, with:
- $r_{\text{prefix}} = (r_0)$
- $r_{\text{suffix}} = (r_1) = \alpha$

So we compute:
\begin{equation}
\hat{s} = \sum_{w \in \{0,1\}} \text{eqf}(r_1, w) \otimes t'(w)
\end{equation}

Recall that $\text{eqf}(x, 0) = 1 - x$ and $\text{eqf}(x, 1) = x$.

Using this:
- $\text{eqf}(r_1, 0) = 1 - \alpha$
- $\text{eqf}(r_1, 1) = \alpha$

Substitute into the sum:
\begin{align}
\hat{s} &= \text{eqf}(\alpha, 0) \otimes t'(0) + \text{eqf}(\alpha, 1) \otimes t'(1) \\
&= (1 - \alpha) \otimes 1 + \alpha \otimes (1 + \alpha)
\end{align}

We now expand:
\begin{align}
\hat{s} &= (1 - \alpha) \otimes 1 + \alpha \otimes 1 + \alpha \otimes \alpha \\
&= (1 - \alpha + \alpha) \otimes 1 + \alpha \otimes \alpha \\
&= 1 \otimes 1 + \alpha \otimes \alpha
\end{align}

So we’ve computed $\hat{s} \in A$ explicitly.

#### Step 4: Match to partial evaluations $S_0$ and $S_1$

Let’s manually compute $S_v = t(v, r_1)$:
- $S_0 = t(0, \alpha) = t(0,0)(1-\alpha) + t(0,1)\alpha = 1 \cdot (1 - \alpha) + 1 \cdot \alpha = 1$
- $S_1 = t(1, \alpha) = t(1,0)(1-\alpha) + t(1,1)\alpha = 0 \cdot (1 - \alpha) + 1 \cdot \alpha = \alpha$

Now form:

\begin{equation}
\hat{s} = S_0 \otimes \beta_0 + S_1 \otimes \beta_1 = 1 \otimes 1 + \alpha \otimes \alpha
\end{equation}

This matches exactly with our earlier result for $\hat{s}$.

### Summary

We computed $\hat{s}$ in two ways:
1. Directly from $t'$ and $\text{eqf}(r_{\text{suffix}}, w)$,
2. As a sum $\sum_v S_v \otimes \beta_v$ with $S_v = t(v, r_{\text{suffix}})$.

Both give the same result:
\begin{equation}
\hat{s} = 1 \otimes 1 + \alpha \otimes \alpha
\end{equation}

This shows explicitly how $t'$, $r_{\text{suffix}}$, and packing data combine into the $A$-element $\hat{s}$ that encodes all $S_v$ values.
:::

### Final result: The packed partial evaluations

Putting it all together:

\begin{equation}
\hat{s} = \sum_{v \in \{0,1\}^\kappa} S_v \otimes \beta_v
\end{equation}

That is, each $S_v$ appears as the **column** coefficient of $\hat{s}$ with respect to the basis $\beta_v$.

The verifier can now use this $\hat{s} \in A$ to check:

\begin{equation}
t(r) = \sum_{v} S_v \cdot \text{eqf}(r_{\text{prefix}}, v)
\end{equation}

All of this was achieved without the prover ever revealing the individual $S_v$ values.

### Why this works: Algebraic and structural clarity

This entire mechanism relies on the fact that elements of $L$ are viewed as $K$-linear combinations of basis elements. The tensor product $A = L \otimes_K L$ captures this two-sided structure. It allows us to:
- Bundle $2^\kappa$ values into one structured object,
- Evaluate and manipulate them algebraically,
- Recover weighted sums without inspecting each one directly.

The use of left and right embeddings ($\varphi_0$ and $\varphi_1$) ensures that multiplication behaves predictably, allowing the verifier to trust the structure of $\hat{s}$.

This idea — constructing and evaluating a carefully prepared object in $A$ — is the secret of how ring-switching allows small-field evaluations to be verified via large-field commitments.

In the next section, we'll see how the verifier checks that $\hat{s}$ was correctly constructed from the committed $t'$, using sumcheck and final PCS openings.

## The Ring-Switching Protocol: Step-by-Step

We’ve seen how to transform a polynomial $t$ over a small field $K$ into a packed version $t'$ over a larger field $L$, and how the tensor algebra $A = L \otimes_K L$ helps us encode evaluations of $t$. Now, let’s walk through the full **Ring-Switching protocol**.

This protocol, introduced in Construction 3.1 of the Diamond–Posen paper, enables a **Prover** $(P)$ to convince a **Verifier** $(V)$ that a value $s = t(r)$ is correct, for some point $r \in L^\ell$, even though the Verifier only has a commitment to the packed $L$-polynomial $t'$.

The central trick is that instead of revealing all $2^\kappa$ partial evaluations $S_v = t(v, r_{\text{suffix}})$, the Prover sends a single structured object $\hat{s} \in A$ that encodes them all. The Verifier checks that this object was constructed honestly and matches the commitment.

Let’s go step by step.

### Commitment Phase

1. The Prover starts with a multilinear polynomial over the small field:

\begin{equation}
t(X_0, \dots, X_{\ell - 1}) \in K[X]
\end{equation}

2. They **pack** this polynomial by grouping its coefficients using a $K$-basis for $L$. The packed polynomial lives over $L$ and has fewer variables:

\begin{equation}
t' \in L[X_0, \dots, X_{\ell - \kappa - 1}]
\end{equation}

This preserves the same total amount of information, but in a more compact form.

3. The Prover commits to $t'$ using a polynomial commitment scheme over $L$:

\begin{equation}
C_{t'} := \Pi'_L.\text{Commit}(t')
\end{equation}

This commitment $C_{t'}$ is sent to the Verifier and will be used later for proof verification.

### Evaluation Phase: Verifying $t(r) = s_{\text{claimed}}$

The goal is to prove that:

\begin{equation}
t(r_0, \dots, r_{\ell - 1}) = s_{\text{claimed}}, \quad \text{with } r_i \in L
\end{equation}

We split the point $r \in L^\ell$ into two parts:
- $r_{\text{prefix}} = (r_0, \dots, r_{\kappa - 1})$ — the variables that were packed,
- $r_{\text{suffix}} = (r_\kappa, \dots, r_{\ell - 1})$ — the ones remaining after packing.

This split matches the packing step: packing grouped together the values of $t$ across all $r_{\text{prefix}}$, leaving $r_{\text{suffix}}$ as input to $t'$.

By multilinearity, we can recover $t(r)$ by summing over all possible values of the packed variables:

\begin{equation}
t(r) = \sum_{v \in \{0,1\}^\kappa} t(v, r_{\text{suffix}}) \cdot \text{eqf}(r_{\text{prefix}}, v)
\end{equation}

Each value $S_v := t(v, r_{\text{suffix}})$ is a **partial evaluation** where the first $\kappa$ inputs are fixed to $v$ and the rest to $r_{\text{suffix}}$.

### Step 1: Prover Sends $\hat{s} \in A$

To avoid sending each $S_v$ individually, the Prover computes an element in the tensor algebra:

\begin{equation}
\hat{s} := \varphi_1(t')\left( \varphi_0(r_\kappa), \dots, \varphi_0(r_{\ell - 1}) \right)
\end{equation}

This means: lift $t'$ into $A$ by mapping each $t'(w)$ to $1 \otimes t'(w)$, then evaluate at the **left-embedded** point where each $r_i$ becomes $r_i \otimes 1$.

This produces a single object $\hat{s} \in A$ that encodes **all** the $S_v$ values in its structure. The Prover sends $\hat{s}$ to the Verifier.

### Step 2: Verifier Checks the Claimed Evaluation

From earlier, we know that the tensor object $\hat{s}$ must take the form:

\begin{equation}
\hat{s} = \sum_{v \in \{0,1\}^\kappa} S_v \otimes \beta_v
\end{equation}

This is the **column decomposition** of $\hat{s}$ — each $S_v$ is bundled into an $L$-element attached to $\beta_v$.

The Verifier uses this to reconstruct:

\begin{equation}
t(r) = \sum_{v} S_v \cdot \text{eqf}(r_{\text{prefix}}, v)
\end{equation}

So they check whether:

\begin{equation}
s_{\text{claimed}} \stackrel{?}{=} \sum_v S_v \cdot \text{eqf}(r_{\text{prefix}}, v)
\end{equation}

If the check fails, the Verifier rejects. Otherwise, they are convinced that $\hat{s}$ encodes the correct partial evaluations $S_v$.

But the Verifier still needs to check that $\hat{s}$ was computed *honestly* from the committed $t'$.

### Step 3: Honest Computation of $\hat{s}$

Recall that an honest Prover should compute $\hat{s}$ as:

\begin{equation}
\hat{s} = \sum_{w \in \{0,1\}^{\ell'}} \text{eqf}(r_{\text{suffix}}, w) \otimes t'(w)
\end{equation}

This evaluates $t'$ over the suffix and bundles the results into the second tensor slot. But computing or checking this directly inside $A$ is expensive.

So instead, we reduce the problem to a cheaper check over $L$.

### Step 4: Switch to an $L$-Sumcheck

The Verifier picks random batching scalars:

\begin{equation}
r'' = (r''_0, \dots, r''_{\kappa - 1}) \in L^\kappa
\end{equation}

These define a **batched linear combination** of the $A$-object’s rows. We construct:

\begin{equation}
A_{\text{batch}}(w) := \sum_{u \in \{0,1\}^\kappa} \text{eqf}(r'', u) \cdot A_{w,u}
\end{equation}

Here, $A_{w,u}$ are the $K$-coefficients that express $\text{eqf}(r_{\text{suffix}}, w)$ in the basis $(\beta_u)$. This compresses the $A$-valued sum into an $L$-valued polynomial:

\begin{equation}
h(w) := t'(w) \cdot A_{\text{batch}}(w)
\end{equation}

So:

\begin{equation}
\sum_w h(w) = \text{batched version of the } A\text{-sum}
\end{equation}

Now we can verify this sum using the standard $L$-sumcheck protocol.

### Step 5: Run the $L$-Sumcheck

The Verifier computes the expected sum:

\begin{equation}
s_0 := \sum_u R_u \cdot \text{eqf}(r'', u)
\end{equation}

where $R_u$ is the $u$-th row of $\hat{s}$. This compresses the entire tensor object into a single value in $L$.

The Prover and Verifier now run sumcheck to prove that:

\begin{equation}
\sum_w h(w) = s_0
\end{equation}

After $\ell'$ rounds, the Verifier receives:
- A random evaluation point $r'_{\text{eval}} \in L^{\ell'}$
- A claimed value $s_{\ell'} = h(r'_{\text{eval}})$

### Step 6: Final Local Check

The Verifier checks the claimed value locally:

\begin{equation}
s_{\ell'} \stackrel{?}{=} t'(r'_{\text{eval}}) \cdot A_{\text{batch}}(r'_{\text{eval}})
\end{equation}

To do this:
- The Prover sends $s'_{t_\text{eval}} = t'(r'_{\text{eval}})$
- The Verifier computes:

\begin{equation}
A_{\text{batch}}(r'_{\text{eval}}) = \sum_u e_u \cdot \text{eqf}(r'', u)
\end{equation}

Here, $e = \text{eqf}(\varphi_0(r_{\text{suffix}}), \varphi_1(r'_{\text{eval}})) \in A$, and $e_u$ is its $u$-th row in the tensor basis.

### Step 7: Final PCS Opening

The Verifier performs one last check using the PCS:

\begin{equation}
\Pi'_L.\text{VerifyProof}(C_{t'}, r'_{\text{eval}}, s'_{t_\text{eval}}, \pi)
\end{equation}

This confirms that the claimed $t'(r'_{\text{eval}})$ value matches the original commitment.

### Summary

- The Prover starts with a polynomial over $K$ and packs it into a smaller-variable version over $L$.
- They commit to the packed version $t'$ using a large-field PCS.
- To prove $t(r) = s_{\text{claimed}}$, they send a single tensor object $\hat{s} \in A$.
- The Verifier uses a batched $L$-sumcheck to check that $\hat{s}$ was honestly derived from $t'$.
- A final PCS opening confirms the last piece.

This protocol allows us to shift between small-field and large-field representations, combining the efficiency of small-field computation with the succinctness of large-field commitments — the core principle behind Ring-Switching.