Extension-opening reduction

An opening claim gives a point $r$ and a value $v$, and asks the verifier to check that the committed polynomial evaluates to $v$ at $r$. The verifier knows the commitment, not the full polynomial table.

Extension-opening reduction, or EOR, handles a base-field table opened at an extension-field point. It packs several base-field entries into each extension-field entry, then reduces the original opening claim to a claim about that packed table. The number of table entries falls, but the underlying base-field data stays the same.

The main idea is to compare two ways of reading a two-dimensional table. One path evaluates its columns first. The other packs its rows first. A small table of partial evaluations connects the two paths. Sumcheck checks that connection, and Akita's subsequent opening checks bind its result to the committed witness.

This page starts with one polynomial and one opening. The implementation page explains how Akita combines several openings and selects EOR in a recursive schedule.

A small example

Work over $\mathbb{F}={\mathbb{F}}_5$, so base-field arithmetic is modulo $5$. Use the quadratic extension $\mathbb{E}={\mathbb{F}}_5[\beta ]/({\beta }^2-2)$ with basis $1,\beta$. Every extension-field value has two base-field coordinates. These small fields are only for the example, not a secure parameter choice.

Consider a two-variable table $f(y,w)$. The head bit $y$ selects a column and the tail bit $w$ selects a row:

Packing stores each pair as the two coordinates of one extension-field value. It produces a table $g$ with one variable instead of two.

Now open the original table at $r=(2,\beta )$. Multilinear evaluation uses weights $1-t,t$ for a bit opened at $t$. Evaluating down the two columns at the tail point $\beta$ gives the column partials

$$\begin{array}{rl}{S}_0& =(1-\beta )\cdot 1+\beta \cdot 4=1+3\beta ,\\ S_1& =(1-\beta )\cdot 2+\beta \cdot 3=2+\beta .\end{array}$$

The head point $2$ then gives the original opening value

$$v=(1-2)S_0+2S_1=3+4\beta .$$

Packing uses the fixed weights $1,\beta$, whereas the head evaluation uses $1-2,2$. These are different operations. Indeed, evaluating the packed table at the same tail point gives

$$\tilde{g}(\beta )=(1-\beta )(1+2\beta )+\beta (4+3\beta )=3,$$

which is not $v$. The tilde denotes the multilinear polynomial defined by a Boolean table. EOR must prove a relation between these two representations; it cannot simply replace $f$ by $g$ and keep the opening value.

The general input and packed table

Let $\mathbb{E}$ have degree $k=2^{\kappa }>1$ over $\mathbb{F}$. Fix the canonical $\mathbb{F}$-basis $({\beta }_y{)}_{y\in \{0,1{\}}^{\kappa }}$ used by the field implementation. The basis is public and does not depend on a challenge.

The prover holds an $n$-variable base-field table $f$, where $n\ge \kappa$. Split its indices and opening point into a head of length $\kappa$ and a tail of length $m=n-\kappa$:

$$f:\{0,1{\}}^{\kappa }\times \{0,1{\}}^m\to \mathbb{F},r=(r_{\mathrm{head}},r_{\mathrm{tail}})\in {\mathbb{E}}^n.$$

The incoming claim is $\tilde{f}(r)=v$. Both parties know $r$, $v$, and the commitment before EOR begins. Knowing $v$ does not mean that the claim is already verified.

For equally sized tuples $a,b$, define the equality polynomial

$$\mathrm{eq}(a,b)=\prod _i((1-a_i)(1-b_i)+a_i{b}_i).$$

Its values at Boolean indices are the interpolation weights. Thus

$$\tilde{f}(r)=\sum _{y\in \{0,1{\}}^{\kappa }}\sum _{w\in \{0,1{\}}^m}\mathrm{eq}(r_{\mathrm{head}},y)\mathrm{eq}(r_{\mathrm{tail}},w)f(y,w).\text{\hspace{1em}(1)}$$

The prover packs the head entries at each Boolean tail position:

$$g(w)=\sum _{y}f(y,w){\beta }_y,g:\{0,1{\}}^m\to \mathbb{E}.\text{\hspace{1em}(2)}$$

The table $g$ has $2^m$ extension-field entries in place of $2^n$ base-field entries. It is a lossless representation of $f$, not a separately chosen witness. Akita uses little-endian Boolean order, so the flat entry at $kw+y$ is $f(y,w)$ when the bit strings are read as integers. The prover does not send the full table $f$ or $g$ in the EOR proof.

Send column partials

The prover first computes one partial for each head index:

$$S_y=\tilde{f}(y,r_{\mathrm{tail}})=\sum _w\mathrm{eq}(r_{\mathrm{tail}},w)f(y,w)\in \mathbb{E}.\text{\hspace{1em}(3)}$$

It sends these $k$ extension-field values. The verifier checks their count and tests whether they recover the incoming opening:

$$v\stackrel{?}{=}\sum _y\mathrm{eq}(r_{\mathrm{head}},y)S_y.\text{\hspace{1em}(4)}$$

The verifier can perform this check without knowing $f$. But it only checks consistency with $v$. A dishonest prover could choose unrelated partials that pass Equation (4). The rest of EOR must connect these particular partials to the packed witness.

Derive row partials

Both parties decompose each received column partial in the fixed basis:

$$S_y=\sum _u{S}_{u,y}{\beta }_u,S_{u,y}\in \mathbb{F}.\text{\hspace{1em}(5)}$$

The index $u\in \{0,1{\}}^{\kappa }$ selects a basis coordinate; $y$ still selects a head column. They have the same range but different roles. The coefficients $S_{u,y}$ form a $k$ by $k$ table.

For the example, $S_0=1+3\beta$ and $S_1=2+\beta$ give

In general, repacking the $u$-th row means computing

$${\mathrm{row}}_u=\sum _y{S}_{u,y}{\beta }_y\in \mathbb{E}.\text{\hspace{1em}(6)}$$

This basis transpose has no new prover message. The verifier derives every ${\mathrm{row}}_u$ from the received $S_y$. A row partial is one extension-field value, not a polynomial. Its value is now known, but its claimed relation to the witness remains to be checked.

Build the public factors

To express the row claims in terms of $g$, decompose each tail equality weight in the same basis:

$$\mathrm{eq}(r_{\mathrm{tail}},w)=\sum _u{A}_u(w){\beta }_u,A_u(w)={\mathrm{coord}}_u(\mathrm{eq}(r_{\mathrm{tail}},w))\in \mathbb{F}.\text{\hspace{1em}(7)}$$

Here $w$ is Boolean and ${\mathrm{coord}}_u$ extracts coordinate $u$ in the fixed basis. Every $A_u$ is a public Boolean table. The verifier can compute its entries from $r_{\mathrm{tail}}$ alone, without any witness data. This is why these factors are called transparent.

Substitute Equation (7) into Equation (3). Since $f(y,w)\in \mathbb{F}$, multiplication by $f(y,w)$ scales each basis coordinate without mixing them:

$$S_{u,y}=\sum _w{A}_u(w)f(y,w).\text{\hspace{1em}(8)}$$

Now repack across $y$:

$$\begin{array}{rl}{\mathrm{row}}_u& =\sum _y\left(\sum _w{A}_u(w)f(y,w)\right){\beta }_y\\ & =\sum _w{A}_u(w)\left(\sum _{y}f(y,w){\beta }_y\right)\\ & =\sum _w{A}_u(w)g(w).\end{array}$$

The relation to be proved is therefore

$$\boxed{{\mathrm{row}}_u=\sum _w{A}_u(w)g(w)}\text{for every }u.\text{\hspace{1em}(9)}$$

The verifier derives the left side from the received partials. On the right, the factor $A_u$ is public and the table $g$ is the prover's packed witness. For honest partials, the identity follows by exchanging two sums. In the protocol, it is an obligation to check, not an assumption the verifier makes.

The example makes the exchange visible. The tail weights are $1-\beta$ and $\beta$, so their coordinate tables are

Consequently,

$${\mathrm{row}}_0=g(0)=1+2\beta ,{\mathrm{row}}_1=-g(0)+g(1)=3+\beta .$$

Taking a coordinate after evaluating the columns gives the same result as using that coordinate of the weights on the packed rows.

Batch the row claims

Rather than prove all $k$ row relations separately, the protocol combines them with fresh random weights. After the original claim values and all column partials enter the transcript, it derives a point $\eta \in {\mathbb{E}}^{\kappa }$. Both parties compute

$${\lambda }_u=\mathrm{eq}(\eta ,u),c_{\eta }=\sum _u{\lambda }_u{\mathrm{row}}_u,A_{\eta }(w)=\sum _u{\lambda }_u{A}_u(w).\text{\hspace{1em}(10)}$$

Neither $c_{\eta }$ nor $A_{\eta }$ is sent. The verifier derives $c_{\eta }$ from the received partials and derives $A_{\eta }$ from the public tail point and $\eta$. Equation (9) now gives the single sumcheck claim

$$c_{\eta }=\sum _w{A}_{\eta }(w)g(w).\text{\hspace{1em}(11)}$$

For the degree-two example, $\eta$ has one coordinate. The row weights are $1-\eta ,\eta$, giving

$$A_{\eta }(0)=1-2\eta ,A_{\eta }(1)=\eta ,c_{\eta }=(1-\eta ){\mathrm{row}}_0+\eta {\mathrm{row}}_1.$$

The challenge must follow the partials. Otherwise a prover could choose row errors to cancel under already known weights. With the partials fixed first, row errors define a multilinear polynomial in $\eta$; a false collection of rows can still pass at an unlucky challenge, but cannot choose its errors after seeing that challenge.

From a public table to a polynomial

Sumcheck evaluates away from the Boolean cube, so it needs polynomials, not just table entries. Write ${\tilde{A}}_u$, ${\tilde{A}}_{\eta }$, and $\tilde{g}$ for the multilinear extensions of their respective tables. For example,

$${\tilde{A}}_{\eta }(X)=\sum _{w\in \{0,1{\}}^m}\mathrm{eq}(X,w)A_{\eta }(w)=\sum _u{\lambda }_u{\tilde{A}}_u(X).\text{\hspace{1em}(12)}$$

The polynomial ${\tilde{A}}_u$ has coefficients in $\mathbb{F}$. The polynomials ${\tilde{A}}_{\eta }$ and $\tilde{g}$ have coefficients in $\mathbb{E}$. Each has degree at most one in every tail variable. For the example, Equation (12) is just

$${\tilde{A}}_{\eta }(X)=(1-X)(1-2\eta )+X\eta .$$

At an extension-field point $\rho$, evaluate the multilinear extension of the coordinate table. Do not replace ${\tilde{A}}_u(\rho )$ by ${\mathrm{coord}}_u(\mathrm{eq}(r_{\mathrm{tail}},\rho ))$. Coordinate extraction is only $\mathbb{F}$-linear, so it cannot in general move past the extension-field interpolation weights. The verifier computes ${\tilde{A}}_{\eta }(\rho )$ without materializing the full Boolean table.

Reduce the sum to one point

Define

$$P(X)={\tilde{A}}_{\eta }(X)\tilde{g}(X).$$

Each factor is multilinear, so $P$ has degree at most two in each variable. Sumcheck reduces Equation (11) over the $m$ tail variables. It starts with the known target $C_0=c_{\eta }$.

In round $j$, after challenges ${\rho }_0,\dots ,{\rho }_{j-1}$, the honest prover forms the univariate polynomial

$$q_j(T)=\sum _{w_{j+1},\dots ,w_{m-1}\in \{0,1\}}P({\rho }_0,\dots ,{\rho }_{j-1},T,w_{j+1},\dots ,w_{m-1}).\text{\hspace{1em}(13)}$$

The prover sends the round polynomial in the protocol's compressed encoding. The verifier reconstructs a polynomial of degree at most two and checks $q_j(0)+q_j(1)=C_j$. After absorbing that message, the transcript derives ${\rho }_j\in \mathbb{E}$, and both parties set $C_{j+1}=q_j({\rho }_j)$. In Akita, challenges come from the shared transcript rather than a separate verifier message; the schedule also specifies transcript grinding.

After $m$ rounds, the challenge point is $\rho =({\rho }_0,\dots ,{\rho }_{m-1})$. The prover sends a terminal product claim $h$. The verifier checks $h=C_m$ and computes the public factor $\theta ={\tilde{A}}_{\eta }(\rho )$. The remaining obligation is

$$h\stackrel{?}{=}\theta \tilde{g}(\rho ).\text{\hspace{1em}(14)}$$

The sumcheck messages alone do not verify this final witness evaluation. They reduce the original sum claim to Equation (14). If $m=0$, there are no round messages and $\rho$ is empty; the same final product relation still applies.

Bind the result to the committed witness

Akita keeps $h$ and $\theta$ separate. It does not send an independent $\tilde{g}(\rho )$ in the EOR payload, and it does not divide $h$ by $\theta$. The next opening checks must prove Equation (14) for the packed representation of the same incoming committed table. The product relation does not recover an unscaled value when $\theta =0$.

For a nonterminal fold, EvaluationTrace supplies a public linear relation on the fold's opening digits. Akita multiplies its opening weights by $\theta$ and uses $h$ as the target. The fold's source-consistency and commitment relations connect those digits back to the incoming witness. Stage 2 checks the resulting relations together. The terminal path checks the corresponding trace relation directly against its terminal response and has no Stage-2 sumcheck.

Passing the column check, deriving the rows, and replaying sumcheck are not independent proofs of the original opening. They are successive reductions whose final witness relation must also be checked.

What the prover sends

The following table lists the algebraic data for one opening. The input value $v$ may itself be a claim carried from an earlier protocol stage; it is not a new field in the EOR payload.

In particular, a derived value need not be a verified witness value. The verifier knows ${\mathrm{row}}_u$ after reading the partials, but Equation (9) is still a claim about the hidden table $g$.

The message flow is:

Prover                                         Verifier
  holds f; derives packed table g                knows r, v, commitment
       |
       +---------------- S_y ------------------> checks recombination to v
                                                 derives row_u from S_y

       both derive eta after absorbing the partials
       both compute c_eta and the public factor A_eta

       +------------ round polynomial ---------> checks the round relation
       both derive the next rho coordinate       repeat for each tail bit

       +----------------- h -------------------> checks h = final round claim
                                                 computes theta

       remaining claim: h = theta * g_tilde(rho)
       Akita's opening and commitment checks bind it to the witness

Where Akita uses this reduction

A scheduled fold uses EOR exactly when its opening method is EvaluationTrace and its claim field is a proper extension of its base field. A single-field configuration needs no EOR. A SubringCoefficientPacking fold binds the original extension-valued opening directly and also omits EOR. See Fold path and field geometry.

With multiple claims, Akita runs one shared EOR sumcheck and sends one terminal product $h_i$ for each opening. It uses an early set of coefficients inside EOR and a separate set after the fold's opening payload is fixed. Groups retain their own public points and native tail lengths. The multi-group description explains those two batching steps and the common sumcheck domain.

Structure of the transparent factor

The transparent factor has more structure than an arbitrary dense table. Use the coordinate maps ${\mathrm{coord}}_u$ from Equation (7) and the weights ${\lambda }_u=\mathrm{eq}(\eta ,u)$ from Equation (10). Define the base-field-linear batching map ${\tau }_{\eta }:\mathbb{E}\to \mathbb{E}$ by

$${\tau }_{\eta }\left(\sum _u{a}_u{\beta }_u\right)=\sum _u{\lambda }_u{a}_u.$$

Split the remaining Boolean variables into a prefix and suffix. The equality product splits as

$$\mathrm{eq}(r_{\mathrm{tail}},x)=E_{\mathrm{pre}}(x_{\mathrm{pre}})E_{\mathrm{suf}}(x_{\mathrm{suf}}).$$

On Boolean inputs, the EOR factor can then be written as only [E:F] separable terms:

$$A_{\eta }(x_{\mathrm{pre}},x_{\mathrm{suf}})=\sum _u{\mathrm{coord}}_u\left(E_{\mathrm{pre}}(x_{\mathrm{pre}})\right){\tau }_{\eta }\left({\beta }_u{E}_{\mathrm{suf}}(x_{\mathrm{suf}})\right).\text{\hspace{1em}(15)}$$

A direct multiplication-table expansion would expose [E:F]^2 terms. Expanding only the prefix factor in the fixed basis gives Equation (15).

Equation (15) is first an identity between Boolean tables. During sumcheck, the coordinate tables on its right must be folded as multilinear polynomials. It would be incorrect to evaluate the extension-valued prefix at a non-Boolean challenge and then apply coord_u: the coordinate map is base-field linear, not extension-field linear.

The production prover currently materializes the dense factor. The separable form instead identifies a future small-space execution strategy; see the roadmap.

Code reference

• Shared tensor algebra defines the head split, basis packing, column-to-row transpose, and public factor evaluation. In particular, tensor_equality_factor_eval_at_point evaluates Equation (12), not coordinates of an already evaluated equality.
• Prover tensor tables build the column partials and the dense factor table from the witness.
• Prover orchestration absorbs claims and partials before sampling $\eta$, runs sumcheck, and records the terminal products. The proof type carries partials, sumcheck, and final_claims.
• Verifier replay checks the required payload and shape, recombines partials to $v$, and reconstructs the same row claims and public factors. Fold claim preparation applies the factors to the later evaluation-trace weights.

The tensor and sumcheck tests compare partial recombination with direct evaluation, the row claim with the dense witness-factor sum, and the verifier's factor evaluation with the multilinear extension of the factor table. The verifier replay tests also reject changed partials, missing terminal claims, and EOR payloads that do not match the scheduled method. These tests check the implementation's algebra and rejection paths; they do not replace a soundness analysis of the composed protocol.