Dependent R1CS

In dependent R1CS, the constraint matrices are functions of all public values: both the public input and the verifier challenges. This lets public computations become matrix coefficients. We compare it with fixed-matrix split-witness R1CS, then apply it to lookups and bignum arithmetic.

Throughout, let p be prime, let e \geq 1, and put q = p^{e}. Write {\mathbb{F}}_{p} for the prime field of order p and {\mathbb{F}}_{q} for its degree-e extension, with a fixed embedding {\mathbb{F}}_{p} \subseteq {\mathbb{F}}_{q}. All R1CS matrices and witness coordinates are over {\mathbb{F}}_{p}; extension-field values are represented by e base-field coordinates in a fixed basis. Let \| denote concatenation of column vectors, and let \odot denote coordinatewise multiplication. The public input is {\text{𝕩}} \in {\mathbb{F}}_{p}^{n_{\text{pub}}}; it does not include the constant-one coordinate, which we prepend explicitly.

R1CS

The leading 1 allows each matrix row to encode an affine linear form in the public input and witness. The matrices are public and fixed before the input and witness are chosen.

Extension Field Embedding

In the LogUp protocol below, it will be useful to verify constraints in an extension {\mathbb{F}}_{q} of {\mathbb{F}}_{p}. Let e be the extension degree such that q = p^{e}, let \theta_{1},\ldots,\theta_{e} be a basis of \frac{{\mathbb{F}}_{q}}{{\mathbb{F}}_{p}}. Then an element a \in {\mathbb{F}}_{q} is represented by coordinates \mathbf{a} \in {\mathbb{F}}_{p}^{e} such that

a = \sum_{i \in \lbrack e\rbrack}a_{i}\theta_{i}.

Addition is simply coordinate wise addition in {\mathbb{F}}_{p}. Multiplication in {\mathbb{F}}_{q} is a bilinear map over coordinates in {\mathbb{F}}_{p}^{e}. Witness-constant multiplication is implemented by partial evaluation of the bilinear map, turning it into a e \times e linear map in {\mathbb{F}}_{p}. For witness-witness multiplication, let r be the rank of the bilinear map, then there exist matrices U,V \in {\mathbb{F}}_{p}^{r \times e} and W \in {\mathbb{F}}_{p}^{e \times r} such that for each a,b,c \in {\mathbb{F}}_{q} the identity a \cdot b = c is equivalent to

\mathbf{c} = W\left( (U\mathbf{a}) \odot (V\mathbf{b}) \right)

over {\mathbb{F}}_{p}. Since multiplication is surjective, W has rank e and we can permute the matrices as

\begin{aligned} U & = \begin{pmatrix} U_{0} \\ U_{1} \end{pmatrix} & V & = \begin{pmatrix} V_{0} \\ V_{1} \end{pmatrix} & W & = \begin{pmatrix} W_{0} & W_{1} \end{pmatrix} \end{aligned}

such that W_{0} \in {\mathbb{F}}_{p}^{e \times e} is invertible. Then the rank-one constraints are

\begin{aligned} \left( U_{0}\mathbf{a} \right) \odot \left( V_{0}\mathbf{b} \right) & = W_{0}^{- 1}\mathbf{c} - W_{0}^{- 1}W_{1}\mathbf{z} \\ \left( U_{1}\mathbf{a} \right) \odot \left( V_{1}\mathbf{b} \right) & = \mathbf{z} \end{aligned}

where \mathbf{z} are a r - e auxiliary values to be committed per multiplication.

Furthermore for e \leq \frac{p}{2} + 1 it follows that r = 2e - 1 by a result from Winograd–de Groote. We will only consider field extensions where this holds true. Hence extension field multiplication takes e - 1 additional witnesses and 2e - 1 constraints.

Split-witness R1CS

In split-witness R1CS, the prover fixes one part of the witness before receiving a verifier challenge and chooses the remaining part afterwards. The matrices stay fixed; the challenge enters as additional public coordinates in the assignment.

For each fixed challenge this is an ordinary R1CS check. The additional structure is the timing of the witness choices. Omitting \text{𝕣} from the assignment without making the matrices depend on it would leave the challenge unused by the check.

Dependent R1CS

We can instead let all public values select the matrices: the public input as well as the challenge. The matrix-valued functions, rather than their evaluations, are fixed in advance, before either the public input or challenge is chosen.

Here neither the public input nor the challenge needs to appear in \mathbf{w}: their contributions can be encoded in the matrices, including their constant column. In particular, split-witness R1CS is a special case: add the public-input and challenge columns” contributions at ({\text{𝕩}},{\text{𝕣}}) to the constant column, then remove those columns. The resulting matrix entries are affine functions of ({\text{𝕩}},{\text{𝕣}}). More general dependence on both arguments is allowed by the definition; any polynomial-degree bounds in \text{𝕣} needed for a soundness argument must be specified separately, with \text{𝕩} held fixed.

Acceptance versus soundness

These acceptance relations do not by themselves guarantee a sound proof system for an intended language L. Write R_{\text{𝕣}}\left( {\text{𝕩}},{\text{𝕨}}_{1},{\text{𝕨}}_{2} \right) for either randomized acceptance relation. In the ideal model where commitments fix witness vectors, perfect completeness requires that for each {\text{𝕩}} \in L there is a single {\text{𝕨}}_{1} such that every challenge \text{𝕣} admits a completing witness {\text{𝕨}}_{2}.

An information-theoretic soundness error of at most \varepsilon requires that, for every {\text{𝕩}} \notin L and every first witness {\text{𝕨}}_{1} fixed before the challenge,

\Pr\limits_{{\text{𝕣}} \in {\mathbb{F}}_{p}^{k}}\left\lbrack \exists{\text{𝕨}}_{2} \in {\mathbb{F}}_{p}^{n_{2}}:R_{\text{𝕣}}\left( {\text{𝕩}},{\text{𝕨}}_{1},{\text{𝕨}}_{2} \right) \right\rbrack \leq \varepsilon.

The probability is over a uniform challenge. The order matters: the second witness may adapt to the challenge, but the first may not. A concrete protocol additionally needs binding commitments and a proof that enforces this relation on the committed values; its security and efficiency require their own analysis.

Challenge fields and security target

All soundness statements below concern the ideal model of fixed committed values and exact enforcement of the displayed relations. They quantify over every first witness, including malicious ones, and over all possible second witnesses chosen after the challenges. All repetitions use the same first witness. A concrete commitment-and-proof construction must separately account for binding, relation enforcement, and any Fiat–Shamir reduction.

We may sample challenges in {\mathbb{F}}_{q}, where q = p^{e}. Each such challenge is encoded by e public coordinates over {\mathbb{F}}_{p}, so the challenge length k in the R1CS definitions counts base-field coordinates. The constructions displayed below use e = 1, hence q = p; their soundness theorems also cover the extension versions. We explain their base-field encoding costs at the end. Increasing e increases the number of challenge points, but changes neither the characteristic p nor the native modulus governing integer wraparound.

Our target is algebraic soundness error at most 2^{- 128}. We allocate at most 2^{- 129} to polynomial identity testing and at most 2^{- 129} to lookup checks. These are explicit finite-field probabilities, not a claim that one field element automatically supplies 128 bits of security. We assume independent, exactly uniform challenges in the stated sampling domains; a biased sampler needs its own error analysis.

Lookups

LogUp

Both R1CS variants support LogUp arguments for lookups. LogUp makes use of logarithmic derivatives to turn products into sums:

To apply LogUp, it is preferable to work with a degree e extension field {\mathbb{F}}_{q} of {\mathbb{F}}_{p}. Let \theta_{1},\ldots,\theta_{e} be a basis for {\mathbb{F}}_{q}/{\mathbb{F}}_{p}, then we can pack tuples into elements of {\mathbb{F}}_{q}\lbrack Y\rbrack. We use m = \left\lceil \frac{d}{e} \right\rceil packed blocks, with zero padding:

\begin{aligned} a_{i}(Y) & = \sum_{j \in \lbrack 0,m\rbrack}\sum_{k \in \lbrack e\rbrack}a_{i(je + k)}\theta_{k}Y^{j} & t_{i}(Y) & = \sum_{j \in \lbrack 0,m\rbrack}\sum_{k \in \lbrack e\rbrack}t_{i(je + k)}\theta_{k}Y^{j} \end{aligned}

Packing is injective because the \theta_{k} are linearly independent over {\mathbb{F}}_{p}. The lookup relation then becomes equivalent to proving the following identity in {\mathbb{F}}_{q}\lbrack X,Y\rbrack:

\begin{aligned} \prod_{i \in \lbrack N\rbrack}\left( X - a_{i}(Y) \right) & = \prod_{i \in \lbrack T\rbrack}\left( X - t_{i}(Y) \right)^{m_{i}} \end{aligned}

where m_{i} is the nonnegative integer multiplicity assigned to table row i, with \sum_{i}m_{i} = N. If table rows repeat, assign each query occurrence to one matching row. Assume N < p. Since both sides are monic in X and degree N, we can apply \operatorname{\mathcal{D}}_{X} over the coefficient field {\mathbb{F}}_{p(Y)} to both sides and get the equivalent rational relation

\sum_{i \in \lbrack N\rbrack}\frac{1}{X - a_{i}(Y)} = \sum_{i \in \lbrack T\rbrack}\frac{m_{i}}{X - t_{i}(Y)}.

Split-witness R1CS

To encode the protocol in split-witness R1CS, commit to a_{ij} and \mu_{i} in {\text{𝕨}}_{1}. The verifier samples \mathbf{r} = \left( \gamma_{1},\ldots,\gamma_{e},\delta_{1},\ldots,\delta_{e} \right). Where \gamma_{i},\delta_{i} are taken to be the base \theta coordinates of \gamma,\delta. We optionally omit \delta when m = 1.

Define m packed blocks for each query and table row, zero padding missing values. For b \in \lbrack 0,m):

\begin{aligned} A_{i,b} & = \sum_{k \in \lbrack e\rbrack}a_{i(be + k)}\theta_{k} \\ T_{i,b} & = \sum_{k \in \lbrack e\rbrack}t_{i(be + k)}\theta_{k} \end{aligned}

We will now continue in extension field constraints, using the R1CS extension field embedding mentioned before to turn constraints back into basefield constraints.

First we compress the queries and tables. We generate m powers of \delta such that h_{b} = \delta^{b}, with h_{0} = 1 and h_{1} = \delta already provided:

\begin{aligned} h_{b} & = h_{b - 1}\delta & & (b = 2,\ldots,m - 1) \end{aligned}

This requires \max(m - 2,0) extension field witnesses and witness-witness multiplications. We can then compress the rows as linear combinations. First we compute N(m - 1) intermediate values

\begin{aligned} Z_{ib} & = A_{ib}h_{b} & & (i = 1,\ldots,N,b = 1,\ldots,m - 1) \end{aligned}

Then define A'_{i},T'_{i} as linear combinations

\begin{aligned} A'_{i} & = A_{i0} + \sum_{b \in \lbrack m - 1\rbrack}Z_{ib} & & (i = 1,\ldots,N) \\ T'_{i} & = T_{i0} + \sum_{b \in \lbrack m - 1\rbrack}T_{i,b}h_{b} & & (i = 1,\ldots,T). \end{aligned}

where the bottom sum is linear because the T_{i,b} are constants, making these constant-witness multiplications.

Now commit to extension field values u_{1},\ldots,u_{N} and v_{1},\ldots,v_{T}, enforcing

\begin{aligned} \left( \gamma - A'_{i} \right)u_{i} & = 1 & & (i = 1,\ldots,N), \\ \left( \gamma - T'_{j} \right)v_{j} & = \mu_{j} & & (j = 1,\ldots,T), \\ \sum_{i \in \lbrack N\rbrack}u_{i} & = \sum_{i \in \lbrack T\rbrack}v_{i}. \end{aligned}

Let K = \max(m - 2,0) + N(m - 1) + N + T then this requires after embedding n_{1} witnesses in {\text{𝕨}}_{1}, n_{2} witnesses in {\text{𝕨}}_{2}, and R constraints where

\begin{aligned} n_{1} & = dN + T & n_{2} & = (2e - 1)K & R & = (2e - 1)K + e. \end{aligned}

Grouping

When d \leq e the compressed row values T'_{i} are constant. This allows us to improve the arithmetization by grouping table elements. Consider two table elements

v = \frac{\mu_{1}}{\gamma - t_{1}} + \frac{\mu_{2}}{\gamma - t_{2}}

currently these are computed with two witness values v_{1},v_{2} and two extension multiplications, we can optimize this. First observe v is a rational function in \gamma:

v = \frac{\mu_{1}\left( \gamma - t_{2} \right) + \mu_{2}\left( \gamma - t_{1} \right)}{\left( \gamma - t_{1} \right)\left( \gamma - t_{2} \right)} = \frac{\left( \mu_{1} + \mu_{2} \right)\gamma - \left( \mu_{1}t_{2} + \mu_{2}t_{1} \right)}{\gamma^{2} - \left( t_{1} + t_{2} \right)\gamma + t_{1}t_{2}}

then we compute \gamma^{2} that is shared for all table rows, and compute v using auxiliary witness u and constraints

\begin{aligned} u & = \left( \mu_{1} + \mu_{2} \right)\gamma \\ \left( \gamma^{2} - \left( t_{1} + t_{2} \right)\gamma + t_{1}t_{2} \right)v & = u - \left( \mu_{1}t_{2} + \mu_{2}t_{1} \right). \end{aligned}

The fist constraint is a scalar-extension multiplication, requiring e constraints after embedding in the basefield and no auxiliary witnesses. This saves e - 1 constraints and witness after embedding.

In general, for grouping k table rows, define polynomials

\begin{aligned} G(X) & = \prod_{i \in \lbrack k\rbrack}\left( X - t_{i} \right) & H(X) & = \sum_{i \in \lbrack k\rbrack}\mu_{i}\frac{G(X)}{X - t_{i}}. \end{aligned}

then we constrain G(\gamma)v = H(\gamma). We need k - 1 auxiliary witnesses to compute H(\gamma), but only scalar-extension constraints to compute them. After computing k - 1 powers of \gamma, this saves (e - 1)(k - 1) witnesses and constraints after embedding for each group of k table entries assuming d = 1. When d > 1 the t_{i} are no longer basefield and the intermediate values will occupy more and more of the extension field, diminishing the returns at larger groups.

Dependent R1CS

In dependent R1CS we start again with t_{ij} constant, a_{ij},\mu_{i} in {\text{𝕨}}_{1} and we receive \gamma,\delta. This time however, constraints can contain coefficients that are functions of \gamma,\delta.

Compressing rows becomes a linear combination, which can be inlined in further constraints:

\begin{aligned} A'_{i} & = \sum_{b \in \lbrack 0,m - 1\rbrack}\sum_{k \in \lbrack e\rbrack}a_{i(be + k)}\theta_{k}\delta^{b} \\ T'_{i} & = \sum_{b \in \lbrack 0,m - 1\rbrack}\sum_{k \in \lbrack e\rbrack}t_{i(be + k)}\theta_{k}\delta^{b} \end{aligned}

We can also precompute coefficients

c_{i} = \frac{1}{\gamma - T'_{i}}

Then we take N extension field witnesses u_{i} and enforce the constraints

\begin{aligned} \left( \gamma - A'_{i} \right)u_{i} & = 1 & & (i = 1,\ldots,N), \\ \sum_{i \in \lbrack N\rbrack}u_{i} & = \sum_{i \in \lbrack T\rbrack}\mu_{j}c_{i}. \end{aligned}

After embedding this requires n_{1} witnesses in {\text{𝕨}}_{1}, n_{2} witnesses in {\text{𝕨}}_{2}, and R constraints where

\begin{aligned} n_{1} & = dN + T, & n_{2} & = (2e - 1)N, & R & = (2e - 1)N + e. \end{aligned}

In particular, the only table-size cost is in committing to \mu_{i} in {\text{𝕨}}_{1}.

Range checks with a shared table

Fix a single public table \mathcal{T} = \left\{ 0,\ldots,B - 1 \right\} with B = 2^{c}, and assume p > 2B. To constrain the canonical integer representative of x \in {\mathbb{F}}_{p} to 0 \leq x < R for a public 1 \leq R < B, put C = B - R and look up both x \in \mathcal{T},\quad x + C \in \mathcal{T}. The first lookup gives 0 \leq x < B. Then 0 \leq x + C < 2B < p, so the second lookup is equivalent to x + C < B, or x < R. Thus the same table supports arbitrary smaller intervals, not just powers of two. To check L \leq h < L + R, use x = h - L. The shifted queries are linear forms in the same witness and require no separate query-value witnesses. Multiplicities count both queries, and both must be included in the soundness budget N.

Spread operation

Combining the two contributions

With s repetitions, separate lookups need 2s inverse witnesses and rows. Instead include a first-witness element z and enforce once x(x + C) = z. For each evaluation challenge \gamma, supply one second-witness element r_{\gamma} and impose r_{\gamma}\left( \gamma^{2} - \gamma(2x + C) + z \right) = 2\gamma - 2x - C. The factor multiplying r_{\gamma} and the right-hand side are linear forms in the witness with public challenge-dependent coefficients, so this is one rank-1 row. Away from poles it enforces r_{\gamma} = \frac{1}{\gamma - x} + \frac{1}{\gamma - x - C}. Use r_{\gamma} as the pair’s contribution to the shared LogUp sum. The product z and the queries are fixed before the challenges; the product equation is enforced only once, independently of the number of repetitions. Since C \neq 0 in {\mathbb{F}}_{p}, a query pole makes the left-hand factor zero and the right-hand side nonzero, so this particular paired check rejects query poles.

Excluding shared multiplicities and sum rows, and counting x itself, separate checks cost one first-witness element, 2s second-witness elements, and 2s rows. The combined check costs two first-witness elements, s second-witness elements, and s + 1 rows. Thus it saves s - 1 total witness elements and s - 1 rows. The two-query soundness bound is unchanged; combining the contributions does not halve N.

For c = 16 and s = 3, the local costs of these encodings are

The Boolean encoding represents the value directly as a linear form in its bits; a separately stored value would also need a reconstruction equation. Among these local encodings, Boolean bits minimize witness size for 1 \leq b \leq 4; the combined check is preferable for 5 \leq b \leq 15, breaking the witness tie at b = 5 by using fewer rows. A full 16-bit range needs only one query. These comparisons exclude shared table costs and do not optimize pairing across different values.

Pairing arbitrary scalar queries

A fixed offset is not required. For any two first-witness scalar queries a,b, include their product z in the first witness and enforce ab = z. For each challenge use r_{\gamma}\left( \gamma^{2} - \gamma(a + b) + z \right) = 2\gamma - a - b. Away from poles this gives r_{\gamma} = \frac{1}{\gamma - a} + \frac{1}{\gamma - b}, because (\gamma - a)(\gamma - b) = \gamma^{2} - \gamma(a + b) + ab. Both query values may be unrelated private witnesses. They must contribute to the same scalar lookup sum; for challenge-dependent tuple compressions, their product is not generally a fixed first-witness value, so the same cost claim does not apply directly.

For two independently stored queries, the paired encoding costs three first-witness elements, s second-witness elements, and s + 1 rows, versus two, 2s, and 2s for separate checks. Again it saves s - 1 witness elements and rows. An unpaired last query can use the original inverse equation. These savings are relative to the displayed separate-query encoding, not a lower bound over all possible encodings.

Grouping three or more scalar queries

Pairing is a special case of grouping an arbitrary number k of fixed scalar queries. Define the monic polynomial G(X) = \prod_{i = 1}^{k}\left( X - a_{i} \right). Its logarithmic derivative is G'\frac{X}{G(X)} = \sum_{i = 1}^{k}\frac{1}{X - a_{i}}. Construct and constrain the coefficients of G using auxiliary first-witness values, before any evaluation challenges. For each base-field challenge \gamma, supply one second-witness element r_{\gamma} and enforce r_{\gamma}G(\gamma) = G'(\gamma). Both G(\gamma) and G'(\gamma) are linear forms in the constrained coefficients with public challenge-dependent weights. Thus the evaluation takes one rank-1 row regardless of k. The coefficient-construction circuit still has to be paid for, once across all repetitions. Coefficients that are already linear forms in existing witnesses need no separately stored values or reconstruction rows. The contribution r_{\gamma} replaces the group’s individual inverses in the shared sum.

Size one is the base case. For one query a, take G(X) = X - a and G'(X) = 1. There are no coefficient-construction products or auxiliary witnesses: the evaluation row is simply r_{\gamma(\gamma - a)} = 1.

Size two. For queries a,b, introduce the single product u = ab. Then G(X) = X^{2} - (a + b)X + u, and the evaluation row is r_{\gamma\left( \gamma^{2} - (a + b)\gamma + u \right)} = 2\gamma - a - b. Thus coefficient construction takes one row and one auxiliary witness.

Size three. For a triple a,b,c, three auxiliary products suffice: u = ab,\quad v = (a + b)c,\quad w = uc. They give G(X) = X^{3} - (a + b + c)X^{2} + (u + v)X - w, and the evaluation row is r_{\gamma}\left( \gamma^{3} - (a + b + c)\gamma^{2} + (u + v)\gamma - w \right) = 3\gamma^{2} - 2(a + b + c)\gamma + u + v. All three product equations are enforced once; only the evaluation row repeats.

Size four. For four queries a,b,c,d, five products suffice. Put \sigma = a + b and \tau = c + d, which are linear forms, and introduce u = ab,\quad v = cd,\quad w = \sigma\tau,\quad z = uv,\quad h = (u - \sigma)(v - \tau). Then G(X) = X^{4} - (\sigma + \tau)X^{3} + (u + v + w)X^{2} - (z + w - h)X + z. The identity z + w - h = u\tau + v\sigma is the usual three-product formula for multiplying the nonmonic parts of two quadratics. This avoids storing any additional coefficient witnesses.

Larger small groups. Reuse monic factors A(X) = X^{j} + A_{0}(X) and B(X) = X^{k - j} + B_{0}(X) constructed for disjoint subgroups. Their product is A(X)B(X) = X^{k} + X^{j}B_{0}(X) + X^{k - j}A_{0}(X) + A_{0}(X)B_{0}(X). Only the last term requires new products. It has degree at most k - 2. Choose k - 1 distinct public points t_{0},\ldots,t_{k - 2} \in {\mathbb{F}}_{p} and introduce the k - 1 product witnesses y_{\ell} = A_{0}\left( t_{\ell} \right)B_{0}\left( t_{\ell} \right),\quad\ell = 0,\ldots,k - 2. Each equation is one rank-1 row, because evaluations of the previously constructed factors are linear forms in existing witnesses. Reconstruct the polynomial by the public Lagrange formula A_{0}(X)B_{0}(X) = \sum_{\ell = 0}^{k - 2}y_{\ell}\prod_{v \neq \ell}\frac{X - t_{v}}{t_{\ell} - t_{v}}, where the product ranges over the other interpolation points. All resulting coefficients remain linear forms; interpolation needs no extra witnesses or rows. These points are deterministic, not additional challenges. The construction requires p \geq k - 1, which holds for every field and group size in the table below.

Let C_{k} denote the smallest construction cost within this recursive family. Dynamic programming gives C_{1} = 0,\quad C_{k} = \min\limits_{1 \leq j < k}\left( C_{j} + C_{k - j} + k - 1 \right). Each construction row introduces one auxiliary first-witness value, so there are C_{k} auxiliary witnesses and k + C_{k} first-witness values including the queries. For example, size five combines sizes two and three with four new products; size eight combines two size-four circuits with seven new products.

These are the best constructions established here for unrelated query values within the stated family, not a claim of published best-known bounds or globally optimal multiplicative complexity. For fixed {\mathbb{F}}_{p}, they can be precomputed by group size independently of the table, challenge, and repetition count. Special query structure, such as fixed offsets or repeated values, can permit cheaper circuits. The field characteristic and availability of interpolation points also matter.

For s = 3 independent base-field repetitions, these explicit constructions have the following costs. Counts include the k independently stored query values, all auxiliary products, and the grouped evaluation witnesses, but exclude shared table multiplicities and sum rows.

Pairs, triples, and quadruples therefore all attain two rows and three witness elements per query in these constructions. A triple avoids the higher cost of a pair followed by a singleton. Larger groups still need only one evaluation witness per repetition, but can lose that saving in coefficient construction; increasing the number of repetitions makes their shared preprocessing more attractive.

In general, if coefficient construction takes C_{k} rows and A_{k} auxiliary witness elements, the grouped costs are C_{k} + s rows and k + A_{k} + s witness elements. Compared with separate queries, the savings are s(k - 1) - C_{k} rows and s(k - 1) - A_{k} witnesses. When every preprocessing row is a multiplication introducing one auxiliary value, A_{k} = C_{k}. These are costs of explicit arithmetic circuits, not optimality claims for arbitrary group sizes.

As with pairs, the preprocessing above assumes challenge-independent scalar queries. Applying it directly to newly randomized tuple compressions would not make their coefficient-construction costs reusable across repetitions. The one-row evaluation counts also assume base-field challenges; extension-field equations require their native-field encoding.

Tuple lookups

For a table of d-tuples {\text{𝕥}}_{j} \in {\mathbb{F}}_{p}^{d} and query tuples {\text{𝕒}}_{i} \in {\mathbb{F}}_{p}^{d}, define the random linear compression

h_{\rho}\left( {\text{𝕒}}_{i} \right) = a_{i,1} + \sum_{\ell = 2}^{d}\rho_{\ell}a_{i,\ell}.

The first witness contains all dN query coordinates and the T multiplicities. After this commitment, sample the coefficients \rho_{2},\ldots,\rho_{d} and \gamma independently and uniformly, in a single challenge round. Apply the scalar LogUp check to h_{\rho}\left( {\text{𝕒}}_{i} \right) and h_{\rho}\left( {\text{𝕥}}_{j} \right). For example, lookup pairs \left( a_{i},b_{i} \right) in a table of pairs \left( t_{j},f\left( t_{j} \right) \right) certify evaluations of the tabulated function f.

With fixed matrices, products of challenge coordinates and witness coordinates are not matrix coefficients. Introduce (d - 1)N second-witness entries z_{i,\ell} and constraints

\rho_{\ell}a_{i,\ell} = z_{i,\ell}\quad(i = 1,\ldots,N;\ell = 2,\ldots,d).

The query inverse row becomes

\left( \gamma - a_{i,1} - \sum_{\ell = 2}^{d}z_{i,\ell} \right)u_{i} = 1.

For a hardcoded table, h_{\rho}\left( {\text{𝕥}}_{j} \right) is already a linear form in the challenge coordinates, so its table row needs no additional products. If the table is instead supplied through public inputs, the fixed-matrix encoding also needs (d - 1)T product entries and rows to compute \rho_{\ell}t_{j,\ell}.

Dependent matrices need neither kind of product entry. They directly encode the query rows

\left( \gamma - a_{i,1} - \sum_{\ell = 2}^{d}\rho_{\ell}a_{i,\ell} \right)u_{i} = 1

using the \rho_{\ell} as matrix coefficients, and the final sum row uses coefficients c_{j}({\text{𝕩}},\rho,\gamma) = \frac{1}{\gamma - h_{\rho}\left( {\text{𝕥}}_{j} \right)}. As before, matrix evaluation rejects table poles by replacing the final row with an impossible constraint.

For a hardcoded table, n_{1} = dN + T, and the costs are

• Split witness: n_{2} = dN + T, n = 2dN + 2T, and m = dN + T + 1.

• Dependent: n_{2} = N, n = (d + 1)N + T, and m = N + 1.

The saving in both n and m is now (d - 1)N + T. A public-input table adds (d - 1)T to the split-witness counts but does not change the dependent counts. These are costs of the explicit constructions above, not lower bounds for all possible encodings.

Repeating only the evaluation point while keeping the same compression gives the bound \delta + (1 - \delta)\eta^{s}, not \left( \delta + (1 - \delta)\eta \right)^{s}: compression collisions would remain shared across repetitions. For d = 1, use the scalar theorem without compression.

Bignums

Fix r \geq 1 and let E \in {\mathbb{Z}}\left\lbrack Y_{0},\ldots,Y_{r - 1} \right\rbrack be a fixed polynomial expression. We want to prove

E\left( a_{0},a_{1},\ldots,a_{r - 1} \right) = 0\quad\text{ over }{\mathbb{Z}},

where the integers a_{i} are represented by limbs in a fixed radix \beta. The expression may contain additions, products, powers, and integer constants; modular multiplication is one example. Dependent R1CS lets us evaluate the limb polynomials without introducing witnesses for the evaluations themselves. The remaining nonlinear cost depends on the arithmetic circuit for E.

Integer and polynomial representations

The native field is {\mathbb{F}}_{p}. Fix an integer radix 2 \leq \beta < p and limb counts k_{i} \geq 1. Represent each integer and its associated limb polynomial by

a_{i} = \sum_{j = 0}^{k_{i} - 1}a_{i,j}\beta^{j},\quad A_{i(X)} = \sum_{j = 0}^{k_{i} - 1}a_{i,j}X^{j},\quad a_{i} = A_{i(\beta)}.

Each limb has a specified integer range and is encoded in {\mathbb{F}}_{p}. Unsigned limbs in \lbrack 0,\beta) represent nonnegative integers; signed limbs allow negative integers and redundant representations. In either case the enforced ranges must give each limb an unambiguous integer representative. The expression E, its integer coefficients, the limb counts, and the radix are fixed before the challenges. Public operands have public limb polynomials; all private limbs belong to the first witness.

Substitution gives a univariate integer polynomial

F_{\mathbb{Z}}(X) = E\left( A_{0}(X),\ldots,A_{r - 1}(X) \right),\quad F_{\mathbb{Z}}(\beta) = E\left( a_{0},\ldots,a_{r - 1} \right).

Fix a degree bound D \geq 1 for F_{\mathbb{Z}}. For example, writing E(Y) = \sum_{\nu}c_{\nu}\prod_{i = 0}^{r - 1}Y_{i}^{\nu_{i}}, it suffices that every monomial with c_{\nu} \neq 0 satisfies

\sum_{i = 0}^{r - 1}\nu_{i\left( k_{i} - 1 \right)} \leq D.

In particular, total degree d and at most k limbs per input give \deg F_{\mathbb{Z}} \leq d(k - 1). We may pad to a larger D, including D = 1 for a constant expression. This degree is the degree after limb substitution, not just the degree of E.

The desired equation is F_{\mathbb{Z}}(\beta) = 0. It does not require F_{\mathbb{Z}} to be the zero polynomial. By division by the monic polynomial X - \beta, it is equivalent to an integer carry polynomial H_{\mathbb{Z}} satisfying

F_{\mathbb{Z}}(X) = (\beta - X)H_{\mathbb{Z}}(X),\quad H_{\mathbb{Z}}(X) = \sum_{j = 0}^{D - 1}h_{j}X^{j}.

Writing F_{\mathbb{Z}}(X) = \sum_{j = 0}^{D}f_{j}X^{j} and setting h_{- 1} = h_{D} = 0, the coefficient equations are

f_{j} + h_{j - 1} = \beta h_{j}\quad(j = 0,\ldots,D).

The coefficients f_{j} are determined by E and the operand limbs; they need not be materialized as witnesses. Their integer bounds can be derived algebraically. For example, if |a_{i,j}| \leq B_{i,j}, define B_{i(X)} = \sum_{j}B_{i,j}X^{j}. The coefficient of X^{j} in \sum_{\nu}|c_{\nu}|\prod_{i}B_{i(X)}^{\nu_{i}} bounds |f_{j}|. Tighter bounds may exploit the particular expression.

One random evaluation

Let F \in {\mathbb{F}}_{p}\lbrack X\rbrack be the reduction of F_{\mathbb{Z}} modulo p. The prover commits to all private operand limbs and all coefficients of a carry polynomial H \in {\mathbb{F}}_{p}\lbrack X\rbrack of degree at most D - 1. For an honest witness, H is the reduction of H_{\mathbb{Z}}. Only then does the verifier sample a uniform \alpha \in {\mathbb{F}}_{q} and check

E\left( A_{0}(\alpha),\ldots,A_{r - 1}(\alpha) \right) = (\beta - \alpha)H(\alpha).

Here E, the operand polynomials, and \beta are interpreted through their reductions modulo p and the embedding into {\mathbb{F}}_{q}. Each A_{i(\alpha)} = \sum_{j}\alpha^{j}a_{i,j} and H(\alpha) is a linear form in first-witness coefficients. For e = 1, these are ordinary base-field linear forms whose coefficients go directly into the dependent matrices. For e > 1, each evaluation is represented by e such coordinate forms.

Evaluating E still requires its arithmetic circuit. Intermediate gate values may be supplied in the second witness, provided every gate is constrained. Over the base field, one multiplication gate takes one rank-1 row, and the final equality is linear in the gate outputs and carry coefficients; it may sometimes be folded into the last multiplication row. Public-only calculations and multiplication by public values can be absorbed into matrix coefficients. There is no general one-row claim for an arbitrary polynomial expression. Extension-field multiplication gates require a base-field encoding as discussed below.

With fixed split-witness matrices, the operand and carry evaluations can instead be computed by Horner recurrences in the second witness. Dependent matrices remove those recurrences from the constraints, while retaining the multiplications needed to evaluate E.

A nonzero polynomial can vanish at every point of a small field: X^{p} - X does so on {\mathbb{F}}_{p}. Base-field repetition cannot detect such an identity failure. An extension can make the degree bound useful without changing the coefficient field. When 0 < D < q, a sufficient repetition count for error at most 2^{- \lambda} is

s \geq \left\lceil {\frac{\lambda}{\log_{2}}\left( \frac{q}{D} \right)} \right\rceil.

The carry coefficients must be fixed before \alpha. Otherwise, in a single evaluation with e = 1 and \alpha \neq \beta, the prover could choose a constant H after the challenge to satisfy the equation for arbitrary operands. The degree bound alone would not prevent that attack.

From a field identity to an integer equality

The randomized check detects a failure of the polynomial identity over {\mathbb{F}}_{p}. Even when that identity holds, it initially gives only

f_{i} + h_{i - 1} - \beta h_{i} \equiv 0\operatorname{mod}p.

To lift such an equation to the integers, we must give its operands consistent integer representatives and bound its integer residual strictly between - p and p. The only multiple of p in that interval is zero. A sufficient condition is

|f_{i}| \leq L_{i},\quad|h_{i}| \leq K_{i},\quad L_{i} + K_{i - 1} + \beta K_{i} < p,

with K_{- 1} = K_{D} = 0. The L_{i} are derived from limb bounds, and the carry bounds must be enforced. The chosen carry bounds must also contain the honest carries.

If every coefficient equation lifts, multiplying them by \beta^{i} and summing cancels the carries and gives F_{\mathbb{Z}}(\beta) = 0 over the integers. These bounds concern the whole residual. Bounding each side separately by p is not sufficient.

Grouping carry checks

We need not range-check every carry. Take a block of g coefficients starting at a. Multiply its coefficient equations by 1,\beta,\ldots,\beta^{g - 1} and add. The internal carries cancel, giving

\sum_{j = 0}^{g - 1}\beta^{j}f_{a + j} + h_{a - 1} = \beta^{g}h_{a + g - 1}.

This equation follows from the field polynomial identity, so it adds no evaluation rows. Only its incoming and outgoing carries need integer bounds. A sufficient condition for lifting the block equation is

\sum_{j = 0}^{g - 1}\beta^{j}L_{a + j} + K_{a - 1} + \beta^{g}K_{a + g - 1} < p.

Choose block boundaries 0 = t_{0} < t_{1} < \ldots < t_{J} = t. Range-check only the boundary carries h_{t_{j} - 1}; carries inside each block remain unrestricted field elements. If each block meets its bound, the lifted equations telescope to

\sum_{i = 0}^{t - 1}f_{i}\beta^{i} = \beta^{t}h_{t - 1}.

Covering all coefficients, with t = D + 1 and terminal carry h_{D} = 0, proves the full integer equality. Larger blocks save carry range checks, but their residual bounds grow with powers of \beta, limiting the block size relative to the native field.

Stopping early with CRT

There is a second stopping rule. The full field polynomial identity already gives F_{\mathbb{Z}}(\beta) \equiv 0\operatorname{mod}p by substituting X = \beta. Lifting only the low blocks through coefficient t - 1 gives

F_{\mathbb{Z}}(\beta) \equiv 0\operatorname{mod}\beta^{t}.

Since p is prime and 2 \leq \beta < p, the moduli p and \beta^{t} are coprime. The Chinese remainder theorem therefore gives

p\beta^{t} \mid F_{\mathbb{Z}}(\beta).

If the operand bounds additionally imply |F_{\mathbb{Z}}(\beta)| < p\beta^{t}, this forces F_{\mathbb{Z}}(\beta) = 0 over the integers. We can stop checking carry ranges as soon as this global bound holds. The higher carry coefficients still belong to the first witness and the polynomial evaluation, but need no range checks for this argument. No additional native-field multiplication row is needed: divisibility by p already follows from the full polynomial identity.

For a general expression E, derive a bound |E\left( a_{0},\ldots,a_{r - 1} \right)| \leq B_{E} from the operand ranges and choose t with B_{E} < p\beta^{t}. This global magnitude bound and the local coefficient bounds serve different purposes. The global bound alone does not justify omitting a block’s no-wrap condition.

The modulus in the local and global integer bounds is the native prime p, even if the evaluation challenges lie in {\mathbb{F}}_{q}. Replacing it by q = p^{e} when e > 1 would be unsound. Completeness additionally requires that the chosen boundary ranges contain the honest integer carries; when they do, the carry identity itself has perfect completeness.

Range checks and costs

The lookup construction above supplies the range checks. To prove 0 \leq x < 2^{v}, decompose x into bounded chunks, look up each chunk in the corresponding public range table, and enforce the linear reconstruction. Signed carries can be shifted into a nonnegative interval before decomposition. The reconstruction must define an unambiguous integer encoding in the native field; non-power-of-two bounds may require an additional comparison.

With a shared public range table, each chunk uses one inverse witness and one lookup row, plus the shared sum row and first-witness multiplicities. Linear reconstruction rows and any comparisons must also be counted. Grouping and CRT can reduce the number of carry chunks that need these checks. Each repetition also pays for the arithmetic circuit evaluating E and its final carry equation. Those costs depend on the expression and on which operands are public.

The total soundness error includes both the polynomial-test error and the range-lookup error. All range-checked values, their decompositions, and lookup multiplicities must be committed before the relevant challenges. Bounds established by earlier operations can be reused, and redundant or signed limb representations are possible, but their integer interpretation and the resulting local and global bounds must remain explicit. The row counts here describe the algebraic construction, not a benchmark of a complete bignum proof system.

Example: modular multiplication

Take five integer inputs \left( a_{0},a_{1},a_{2},a_{3},a_{4} \right) = (U,V,M,Q,R) and the expression

E(U,V,M,Q,R) = UV - MQ - R.

For M > 0, its vanishing proves UV = MQ + R. A canonical remainder additionally requires 0 \leq R < M. With k \geq 2 limbs for each integer, the substituted polynomial is

F_{\mathbb{Z}}(X) = A_{0}(X)A_{1}(X) - A_{2}(X)A_{3}(X) - A_{4}(X),\quad\deg F_{\mathbb{Z}} \leq D = 2k - 2.

For base-field challenges and public M, the value A_{2}(\alpha) is public, so the evaluation check is one rank-1 row:

A_{0}(\alpha)A_{1}(\alpha) = A_{2}(\alpha)A_{3}(\alpha) + A_{4}(\alpha) + (\beta - \alpha)H(\alpha).

If M is private, introduce a second-witness entry z and use two rows:

\begin{aligned} A_{2}(\alpha)A_{3}(\alpha) & = z, \\ A_{0}(\alpha)A_{1}(\alpha) & = z + A_{4}(\alpha) + (\beta - \alpha)H(\alpha). \end{aligned}

Thus s base-field repetitions cost s identity rows for a public modulus, or 2s rows and s additional witness entries for a private modulus, excluding range and reconstruction checks. With unsigned limbs in \lbrack 0,\beta), the uniform coefficient bound L_{i} = 2{k(\beta - 1)}^{2} + (\beta - 1) suffices. Also |UV - MQ - R| < \beta^{2k}, so p\beta^{t} \geq \beta^{2k} is a sufficient CRT stopping condition. The concrete parameter tables below specialize the general construction to this expression.

Composing the checks

There is no factor for the number of integer expression equations in this bound: every identity is checked, and a single fixed false one suffices. They may share evaluation points. This does not justify replacing all their equations by one unchecked aggregate. Similarly, separately checked lookup batches can be bounded by the worst batch error when all must accept and every batch is fixed before its challenges. A sum bound is also valid, but is unnecessary in that setting.

These are interactive algebraic bounds for a fixed first commitment. To obtain a complete 128-bit security claim, the outer protocol must allocate its own binding and proof-soundness errors, and a Fiat–Shamir version needs a reduction that accounts for adversarial transcript queries. The parameter example below leaves algebraic slack below 2^{- 128}; it does not certify an unspecified commitment or proof system.

Concrete parameters for 128-bit algebraic soundness

We use the following prime fields. The BN254 value is the scalar modulus, as defined by arkworks, rather than the curve’s coordinate-field modulus:

p_{BN254} = 21888242871839275222246405745257275088548364400416034343698204186575808495617.

The other primes are p_{\text{Goldilocks}} = 2^{64} - 2^{32} + 1, p_{M31} = 2^{31} - 1, and p_{\text{BabyBear}} = 2^{31} - 2^{27} + 1. These agree with the field definitions in Plonky3 Goldilocks, Mersenne31, and BabyBear.

Limb and carry parameters

For the modular-multiplication expression E(U,V,M,Q,R) = UV - MQ - R, consider integers represented with at least 2048 bits of capacity. Use k = \left\lceil \frac{2048}{w} \right\rceil limbs of radix \beta = 2^{w}, with all operand and quotient limbs in \lbrack 0,\beta). These ranges can represent the usual quotient when 0 \leq U,V < M < \beta^{k}. We require a separate comparison for a canonical remainder.

Use the conservative coefficient and signed-carry bounds

L = 2{k(\beta - 1)}^{2} + (\beta - 1),\quad K = \left\lceil \frac{L}{\beta - 1} \right\rceil = 2k(\beta - 1) + 1.

The honest carries satisfy |h_{i}| \leq K: from h_{- 1} = 0, the recurrence gives |h_{i}| \leq \frac{L + K}{\beta} \leq K inductively. Enforce |h_{i}| \leq K only at the selected boundaries. For blocks of at most g coefficients, it suffices to check

L\sum_{j = 0}^{g - 1}\beta^{j} + K + \beta^{g}K < p.

For the CRT stopping point choose the smallest integer t \geq 0 with p\beta^{t} \geq \beta^{2k}. Partition the lowest t coefficients into blocks of size g, with a shorter final block if needed. The following choices satisfy both inequalities with exact integer arithmetic:

For M31 and BabyBear, for example, L = 33293055, K = 130561, and the single-coefficient residual bound is 66847232, below both native primes. A two-coefficient block fails this conservative bound. Extension challenges do not permit larger blocks under the same bounds. These are feasible choices, not an optimization of limb size or range-check cost. Here CRT saves one checked carry for M31 and BabyBear, and no checked boundaries for BN254 and Goldilocks compared with full grouping. The full chain’s terminal carry is already the fixed zero; the benefit of stopping earlier depends on the parameters and any tighter operand bounds.

Comparison: repetitions in the native field

Assume at most N = 2^{20} lookup queries in a batch and T = 256 table entries. This includes a shared byte-range table. Every listed characteristic exceeds N. We use independent repetitions of the lookup, with fresh compression coefficients for tuple lookups and evaluation points sampled uniformly outside the public compressed table. The conservative one-repetition bound

\theta = \frac{N + 2T - 1}{p - T}

covers tuple lookups and also upper-bounds scalar lookup error. All sampling domains here are nonempty. With base-field challenges, take the smallest positive repetition counts satisfying

\left( \frac{D}{p} \right)^{s_{\text{poly}}} \leq 2^{- 129},\quad\theta^{s_{\text{lookup}}} \leq 2^{- 129}.

The last column is - \log_{2}\left( \left( \frac{D}{p} \right)^{s_{\text{poly}}} + \theta^{s_{\text{lookup}}} \right), rounded down to one decimal place. The two error budgets and their sum are checked with exact rational arithmetic, independently of the rounded display. Increasing the lookup workload or polynomial degree requires recomputing the counts. These lookup repetitions reuse the first-witness multiplicities but each need their own inverse witnesses and constraints.

For a public modulus, the base-field multiplication identity therefore costs respectively 1, 3, 6, or 6 rows per modular multiplication, excluding all range-check and reconstruction costs. A private modulus doubles these identity-row counts. For example, 17 separately checked public-modulus multiplications cost 17, 51, 102, or 102 identity rows; their range lookups must still fit the stated total query budget or be split into separately checked batches.

P-256 multiplication over Goldilocks

This subsection records the base-field repetition cost comparison; its lookup counts are not the selected single-sample extension encoding. For a smaller, concrete workload, take the native prime p = 2^{64} - 2^{32} + 1 and the public P-256 coordinate-field modulus M = 2^{256} - 2^{224} + 2^{192} + 2^{96} - 1. Prove UV - MQ - R = 0 with canonical inputs and remainder, and a nonnegative 256-bit quotient. A finite parameter search favors \beta = 2^{16}, sixteen limbs, and two-coefficient carry groups when a 16-bit range table is shared. The polynomial degree is D = 30. Three independent base-field repetitions of each argument suffice for the 128-bit algebraic soundness target with at most 2^{20} lookup queries per batch.

Check the fifteen boundary carries h_{1},h_{3},\ldots,h_{29}, covering the lowest thirty coefficients. The global bound |UV - MQ - R| \leq M2^{256} - 1 permits stopping after twenty-nine coefficients; covering one more makes the grouping cheaper. The other fifteen carry coefficients remain unrestricted native-field witnesses. Both arithmetic limbs and bounded carries can be linear forms in their range-check chunks, avoiding separate packed witnesses and reconstruction rows.

We choose uniform signed 32-bit ranges for all fifteen checked carries. Write each as h_{2j + 1} = - 2^{31} + x_{j} + 2^{16}y_{j},\quad 0 \leq x_{j},y_{j} < 2^{16},\quad j = 0,\ldots,14. Each carry is a linear form in two lookup witnesses; no separate packed carry or Boolean range bits are needed. All block residuals lie strictly between - p and p under these ranges.

Assume the inputs already have compatible, range-checked canonical representations. Include new quotient and remainder limbs, and enforce canonical reduction using a range-checked slack S with R + S = M - 1. There are 78 lookup queries: 48 chunks for Q,R,S and thirty carry chunks. Three repetitions cost 234 inverse witnesses and rows. Add fifteen Boolean addition carries, sixteen linear comparison rows, and three polynomial identity rows. The chosen construction costs 268 rows and 342 witness elements per multiplication, comprising 108 first-witness and 234 second-witness elements. Three lookup sum rows and 65536 first-witness table multiplicities are shared across the batch. The fifteen Boolean addition carries belong to the canonical-remainder comparison, not the polynomial carry ranges.

Nonuniform carry ranges can save two rows, but introduce thirteen Boolean range witnesses and special offsets. Uniform ranges use eight fewer first-witness elements; their five additional lookup queries require fifteen more inverse witnesses across the three repetitions, so the total witness is seven elements larger. We choose the uniform encoding for its simpler construction.

These multiplication counts and the parameter search below use separate inverse witnesses for each lookup query. They do not yet apply the paired scalar-query optimization from the range-check section.

Table sharing matters. A standalone multiplication that also proves both inputs canonical takes 525 rows and 66164 witness elements with the chosen uniform parameters, including the table. Optimizing standalone witness size instead selects 14-bit arithmetic limbs, a 7-bit table, and groups of three coefficients: 1000 rows and 1373 witness elements. These counts use the explicit scalar LogUp and slack-comparison encodings above.

The search in scripts/optimize-p256-goldilocks.py enumerates limb widths 1–32, table widths 1–16, and carry groupings by dynamic programming. It tests minimum or chunk-rounded dyadic carry ranges with left, right, or centered offsets, and audits every candidate’s integer and soundness bounds with exact arithmetic. These are optima within that finite family, not lower bounds over all modular-arithmetic circuits or claims about measured prover runtime.

Extension-field parameters

Our lookup protocol uses one uniform extension-field evaluation. For the byte-table workload above, independent-coefficient tuple compression has error at most \frac{N + 2T - 1}{q}; scalar lookups have error at most \frac{N + T - 1}{q}. If the polynomial identity also uses one evaluation, the smallest extension degrees meeting both 2^{- 129} budgets are

These degrees specify abstract finite fields {\mathbb{F}}_{q} of size q = p^{e}; an implementation must choose and fix an irreducible polynomial and a basis before the challenges. Quadratic Goldilocks or quartic M31/BabyBear extensions would require repetition or a separately analyzed computational grinding budget; we use the larger degrees to keep one sample. For T = 256, the honest-rejection probability is at most \frac{256}{q}. The polynomial-compression protocol at the start of the lookup section additionally requires its tuple-width term in the soundness budget.

An extension equation is not one native-field rank-1 row. In a fixed basis, each extension element has e base-field coordinates and public extension multiplication is an {\mathbb{F}}_{p}-linear map. Multiplication of two unknown extension values is bilinear: a generic encoding uses e^{2} base-field product witnesses and rows, followed by e linear rows to enforce the extension equation. Better multiplication formulas or the particular shape of a query can reduce this cost. The earlier one-row and witness-count claims apply to e = 1; they must not be reused unchanged for extension checks. Operand and carry coefficients remain in the native field, while extension-valued inverse and intermediate witnesses use coordinate vectors.

Extensions trade extra coordinates and multiplication work for fewer independent evaluations. They cannot remove the LogUp restriction N < p, the integer no-wrap inequalities, or the need to bind all first-witness coefficients before the challenges.