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, and {\mathbb{F}}_{p} for the prime field of order p. All R1CS matrices and witness coordinates are over {\mathbb{F}}_{p}. 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.

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.

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}. We will do this by representing {\mathbb{F}}_{q} using vectors of basefield elements by the following theorem:

This is a redundant representation where we use 2e - 1 basefield elements to represent an extension element instead of the minimal e, in return we achieve minimal multiplication complexity. We will use algorithmic search to find an M that maximizes performance. For encoding and random challenges we will fix a basis {\mathbf{θ}}_{1},\ldots,{\mathbf{θ}}_{e} of V.

Cubic extension of Goldilocks

Take p = 2^{64} - 2^{32} + 1 and e = 3, then a suitable M is

\begin{aligned} M & = \begin{pmatrix} \begin{array}{rlrlr} 1 & 0 & 0 & - 1 & 2 \end{array} \\ \begin{array}{rlrlr} 0 & 1 & 0 & - 3 & 4 \end{array} \\ \begin{array}{rlrlr} 0 & 0 & 1 & - 4 & 4 \end{array} \\ \begin{array}{rlrlr} 1 & - 3 & 2 & 0 & - 2 \end{array} \\ \begin{array}{rlrlr} 1 & - 2 & 1 & 1 & - 2 \end{array} \end{pmatrix}. \end{aligned}

The first three columns of M form a basis {\mathbf{θ}}_{1},{\mathbf{θ}}_{2},{\mathbf{θ}}_{3} of V and 1_{{\mathbb{F}}_{q}} = {\mathbf{θ}}_{1} + {\mathbf{θ}}_{2} + {\mathbf{θ}}_{3}.

It is optimal in that its vector product can be computed in the minimal number of +, -, <<1, <<2 operations with a minimal depth of dependency chain for that operation count. For \mathbf{c} = M\mathbf{t} the optimal circuit is:

h  = t3 - t4;   s = t1 + t3;   r = t0 + t4;   d =  s - t2;
c0 =  r -  h;   k =  h << 2;   u = c0 -  d;  c1 =  s -  k;
c2 = t2 -  k;  c4 =  u - c1;  c3 = c4 -  d;

Quintic extension of M31

Take p = 2^{31} - 1 and e = 5, then a suitable M is:

M = \begin{pmatrix} 1 & 0 & 0 & 0 & 0 & - 10 & 21 & 6 & - 5 \\ 0 & 1 & 0 & 0 & 0 & 20 & - 21 & 4 & - 5 \\ 0 & 0 & 1 & 0 & 0 & - 4 & 7 & 12 & - 5 \\ 0 & 0 & 0 & 1 & 0 & 2 & - 3 & 2 & - 5 \\ 0 & 0 & 0 & 0 & 1 & 5 & - 7 & 3 & - 5 \\ 5 & 10 & - 2 & 7 & - 20 & 72 & 0 & 0 & 0 \\ 6 & 6 & - 2 & 6 & - 16 & 0 & 80 & 0 & 0 \\ 3 & - 2 & - 6 & - 7 & 12 & 0 & 0 & - 40 & 0 \\ 2 & - 2 & - 2 & - 14 & 16 & 0 & 0 & 0 & 0 \end{pmatrix}

The first e columns of M form a basis {\mathbf{θ}}_{1},\ldots,{\mathbf{θ}}_{e} of V and 1_{{\mathbb{F}}_{q}} = \sum_{i}{\mathbf{θ}}_{i}.

It can be computed in 48 operations, which are picked to leverage instruction level parallelism. A multiplication \mathbf{c} = M(\mathbf{a} \odot \mathbf{b}) runs in about 5.9\text{ ns} compared to 10.2\text{ ns} for an optimized conventional implementation (an adaptation of Plonky3’s quintic_extension for X^{5} + 2X - 1).

r00 = t5 - t6;     r01 = t4 - t7;     r02 = r00 - t6;    r03 = t6 + t8;
r04 = r02 + r01;   r05 = t8 - t7;     r06 = r02 << 2;    r07 = t7 + r00;
r08 = t7 << 3;     r09 = t2 + r08;    r10 = t3 - r07;    r11 = r05 << 2;
r12 = r00 << 4;    r13 = t1 + r12;    r14 = r03 + r11;   r15 = r00 << 2;
r16 = r10 - r04;   r17 = r07 - r06;   r18 = r16 - r07;   r19 = r04 + r15;
r20 = r13 - r04;   r21 = r09 - r06;   r22 = t0 - r09;    r23 = r17 << 1;
r24 = r22 + r23;   r25 = r21 - r19;   r26 = r21 - r14;   r27 = r19 - r14;
r28 = r20 + r18;   r29 = r20 << 2;    r30 = r24 + r28;   r31 = r24 + r26;
r32 = r25 << 2;    r33 = r27 + r18;   r34 = r18 << 3;    r35 = r20 + r27;
r36 = r33 + r32;   r37 = r30 << 1;    r38 = r30 << 2;    r39 = r31 - r29;
r40 = r29 + r34;   r41 = r39 - r36;   r42 = r37 + r38;   r43 = r37 - r34;
r44 = r43 - r40;   r45 = r41 + r43;   r46 = r42 - r41;   r47 = r42 + r32;
c = [r31, r35, r26, r33, r27, r46, r47, r45, r44];

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 - 1\rbrack}\sum_{k \in \lbrack e\rbrack}a_{i(je + k)}\theta_{k}Y^{j} & t_{i}(Y) & = \sum_{j \in \lbrack 0,m - 1\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}}_{q}(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 only e output coordinates. 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} A'_{i}u_{i} & = \gamma u_{i} - 1 & & (i = 1,\ldots,N), \\ \sum_{i \in \lbrack N\rbrack}u_{i} & = \sum_{i \in \lbrack T\rbrack}\mu_{i}c_{i}. \end{aligned}

When d < e the values A'_{i} are in a subspace of {\mathbb{F}}_{q} and the multiplication can potentially be embedded with fewer constraints. In particular for d = 1 the A'_{i} are basefield scalars and only e constraints are required. For a generic power basis \theta_{i} = \theta^{i - 1} we can suffice with e + d - 1 constraints.

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} & = \left( e + \min(d,e) - 1 \right)N, & R & = n_{2} + e. \end{aligned}

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

Grouping

We can again optimize further by grouping contributions. This time the table side is already fully eliminated, but we can now apply the grouping to the query side. Let v be the sum of a group of k query terms:

\begin{aligned} v & = \sum_{i \in \lbrack k\rbrack}\frac{1}{X - a_{i}} \end{aligned}

Then it suffices to construct

\begin{aligned} G(X) & = \prod_{i \in \lbrack k\rbrack}\left( X - a_{i} \right) \end{aligned}

and constrain v as

\begin{aligned} G(\gamma)v & = G'(\gamma). \end{aligned}

For example for k = 2 we have G(X) = X^{2} - \left( a_{1} + a_{2} \right)X + a_{1}a_{2}. Commit to z in {\text{𝕨}}_{1} and v in {\text{𝕨}}_{2} and constrain

\begin{aligned} a_{1}a_{2} & = z, \\ \left( \gamma^{2} - \left( a_{1} + a_{2} \right)\gamma + z \right)v & = 2\gamma - a_{1} - a_{2}. \end{aligned}

For d = 1 the first constraint is scalar and can be embedded with a single basefield variable and constraint. For 1 < d < e other embeddings may exist that perform better than 2e - 1. In particular for d = 2 and a power basis \theta_{i} = \theta^{i - 1} we have

\left( a_{11} + a_{12}\theta \right)\left( a_{21} + a_{22}\theta \right) = a_{11}a_{21} + \left( a_{11}a_{22} + a_{12}a_{21} \right)\theta + a_{12}a_{22}\theta^{2.}

Range Checks

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

\begin{aligned} x & \in \mathcal{T}, & x + C & \in \mathcal{T}. \end{aligned}

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 a_{ij}. Multiplicities count both queries, and both must be included in the soundness budget N.

Recommended Parameters

Recommended LogUp parameters for \log_{2}p \approx 256,64,32 (e.g. Bn254 scalar field, Goldilocks, M31/BabyBear), 128 bit algebraic soundness and completnes, no grinding. Costs is in \left( n_{1},n_{2},R \right) and assumes final constraints and partial groups are ammortized. Query values are assumed already represented in the witness. The safe bound assumes m = 1.

Integer embedding

The limb-polynomial method follows xJsnark which checks multiplication identities at sufficiently many fixed evaluation points. The randomized carry-polynomial check used here follows the approach presented by Ivo Kubjas for gnark in his August 2023 talk. We formulate it for dependent R1CS and combine it with the grouped carry bounds and CRT lifting described below.

Fix radix 2 \leq \beta < p and limb counts k_{i} \geq 1 and offsets L_{i} \in {\mathbb{Z}}. Let a_{1},\ldots,a_{r} \in {\mathbb{Z}} be integers such that

L_{i} \leq a_{i} < L_{i} + \beta^{k_{i}}.

Represent each integer by limbs a_{ij} \in \lbrack 0,\beta), represented in circuit modulo p and with ranges checked. Then we can represent a_{i} and its associated limb polynomial as

\begin{aligned} A_{i}(X) & = L_{i} + \sum_{j \in \left\lbrack 0,k_{i} - 1 \right\rbrack}a_{ij}X^{j}, & a_{i} & = A_{i}(\beta). \end{aligned}

Let E \in {\mathbb{Z}}\left\lbrack Y_{1},\ldots,Y_{r} \right\rbrack be a fixed polynomial expression. We want to prove

\begin{aligned} E\left( a_{1},\ldots,a_{r} \right) & = 0 & & \text{ over }{\mathbb{Z}}. \end{aligned}

Substituting the limb polynomials gives a univariate integer polynomial

F(X) = E\left( A_{1}(X),\ldots,A_{r}(X) \right),

where F(\beta) = E\left( a_{1},\ldots,a_{r} \right). Fix a degree bound D \geq 1 for F. Our goal is now to prove F(\beta) = 0 over \mathbb{Z}. Equivalently, we can prove there exist a polynomial H \in {\mathbb{Z}}\lbrack X\rbrack with \deg H \leq D - 1 such that

\begin{aligned} F(X) & = (\beta - X)H(X) & & \text{ over }{\mathbb{Z}}. \end{aligned}

This suggest a protocol: fix F and H, draw independent uniform random challenges \gamma_{1},\ldots,\gamma_{s} \in {\mathbb{F}}_{p}, and constrain the s identities

\begin{aligned} F\left( \gamma_{i} \right) & = \left( \beta - \gamma_{i} \right)H\left( \gamma_{i} \right) & & \text{ over }{\mathbb{F}}_{p}. \end{aligned}

By Schwartz–Zippel this proves with soundness error (D/p)^{s}, that

\begin{aligned} F(X) & = (\beta - X)H(X) & & \left( \operatorname{mod}p \right). \end{aligned}

In particular this proves F(\beta) = 0\left( \operatorname{mod}p \right). To go from \operatorname{mod}p to \mathbb{Z} we will also certify F(\beta) = 0\left( \operatorname{mod}\beta^{t} \right) with t such that \left| {F(\beta)} \right| < p\beta^{t}. By the Chinese Remainder Theorem it then follows that F(\beta) = 0 in \mathbb{Z}.

Write F(X) = f_{0} + \cdots + f_{D}X^{D}, showing F(\beta) = 0\left( \operatorname{mod}\beta^{t} \right) suffices to show

\begin{aligned} \sum_{i \in \lbrack 0,t - 1\rbrack}f_{i}\beta^{i} & = 0 & & \left( \operatorname{mod}\beta^{t} \right) \end{aligned}

as the higher terms of f_{i} do not contribute. Write H(X) = h_{0} + \cdots + h_{D - 1}X^{D - 1} with h_{- 1} = h_{D} = 0. From the polynomial identity \operatorname{mod}p we have coefficient relations

\begin{aligned} f_{i} + h_{i - 1} & = \beta h_{i} & & \left( \operatorname{mod}p \right) & & \left( i \in \lbrack 0,D\rbrack \right). \end{aligned}

For a block i = a,\ldots,b, let g = b - a + 1. Multiplying each coefficient relation by \beta^{i - a} and adding them gives

\begin{array}{rlr} \sum_{i \in \lbrack a,b\rbrack}f_{i}\beta^{i - a} + h_{a - 1} - \beta^{g}h_{b} = 0 & & \left( \operatorname{mod}p \right). \end{array}

Given bounds on f_{i} and h_{i} as

\begin{aligned} \left| {\sum_{i \in \lbrack a,b\rbrack}f_{i}\beta^{i - a}} \right| & < B, & \left| h_{a - 1} \right| & < K_{\text{in}}, & \left| h_{b} \right| & < K_{\text{out}}, \end{aligned}

then it is sufficient for the bounds to sattisfy

B + K_{\text{in }} + \beta^{g}K_{\text{out }} < p,

for this block relation to also holds in \mathbb{Z}. Partition the coefficient 0,\ldots,t - 1 into blocks with satisfying bounds, then multiplying each block by \beta^{a} and summing results in the relation, valid over \mathbb{Z},

\sum_{i \in \lbrack 0,t - 1\rbrack}f_{i}\beta^{i} - \beta^{t}h_{t - 1} = 0.

from this it follows F(\beta) = 0\left( \operatorname{mod}\beta^{t} \right) and hence F(\beta) = 0 in \mathbb{Z}. Let’s summarize this in a concise protocol description:

Let n_{E} and R_{E} be the R1CS witness and constraints required for evaluating the expression E(\mathbf{y}) = z as an R1CS relation with {\mathbb{F}}_{p} arguments (excluding input and output witnesses).

Then in split-witness R1CS the total cost excluding the inputs is that of range checking and of s times evaluating A_{i\left( \gamma_{j} \right)}, H\left( \gamma_{j} \right) and E. Assuming Horner evaluation, the cost is:

\begin{aligned} n_{1} & = n_{1\text{ range}} + D \\ n_{2} & = n_{2\text{ range}} + s\left( n_{E} + \sum_{i \in \lbrack r\rbrack}\left( k_{i} - 1 \right) + D \right) \\ R & = R_{\text{range }} + s\left( R_{E} + \sum_{i \in \lbrack r\rbrack}\left( k_{i} - 1 \right) + D \right). \end{aligned}

In dependent R1CS, evaluating in \gamma_{j} is a linear operation and the cost shrinks to

\begin{aligned} n_{1} & = n_{1\text{ range}} + D \\ n_{2} & = n_{2\text{ range}} + sn_{E} \\ R & = R_{\text{range }} + sR_{E}. \end{aligned}

Large constants can force B \geq p in step 2. To solve this, a large constant can be provided as a public limb polynomial A_{i}(X). In split-witness R1CS the A_{i}\left( \gamma_{j} \right) evaluations require additional constraints. In dependent R1CS the A_{i}\left( \gamma_{j} \right) are provided directly as a constants.

Modular arithmetic embedding

Given modulus m > 0 (not necessarily prime), a modular ring {\mathbb{K}} = {\mathbb{Z}}/m{\mathbb{Z}}, inputs a_{1},\ldots,a_{r} \in {\mathbb{K}} and a polynomial expression E \in {\mathbb{K}}\left\lbrack Y_{1},\ldots,Y_{r} \right\rbrack. Lift a_{i} and E to the integers as \widetilde{a_{i}} and \widetilde{E} using integer representatives (e.g. natural \lbrack 0,m) or balanced \lbrack - \left\lfloor \frac{m}{2} \right\rfloor,\left\lceil \frac{m}{2} \right\rceil)). Introduce quotient Q \in {\mathbb{Z}} then the lifted expression E' is

E'\left( \widetilde{\mathbf{a}},m,Q \right) = \widetilde{E}(\widetilde{\mathbf{a}}) - mQ.

The vanishing of E' on \widetilde{\mathbf{a}} proves that E vanishes on \mathbf{a}, and whenever E vanishes on \mathbf{a} we have m~|~\widetilde{E}(\widetilde{\mathbf{a}}) and E' vanishes on \widetilde{\mathbf{a}},m,Q with

Q = \frac{\widetilde{E}(\widetilde{\mathbf{a}})}{m}.

If any of m and the inputs are public, then their integer representative limb polynomials are also public. Limb bounds uniquely determine an integer, but do not ensure that it is the canonical integer representative. For that, additional constraints may be required (e.g. \widetilde{a_{i}} < m for the natural representation).

Recommended Parameters

Recommended integer embedding parameters for 128 bit algebraic soundness and completnes, no grinding. The benchmark workload is either ECDSA signature verification in a 256, 384, or 521 bit prime field (approximated as 1400, 2100 and 2800 field multiplications respectively) or RSA signature verification with a 2048, 3072, or 4096 bit modules (approximated as 17 modular multiplications).

For \log_{2}p \approx 256 (BN254 scalar field):

For \log_{2}p \approx 64 (Goldilocks):

For \log_{2}p \approx 32 (M31 or BabyBear):