Research · Papers · What rank-one constraints can express · MF-161
Row complexity of n-bit range checks and u32 addition in R1CS
n-bit range check takes n rows (lower n exact for n <= 2); u32 add takes [32,33] rows with carry-booleanity fusion ruled out by conic counts
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proof systems convert computations into equations called Rank-1 Constraint Systems (R1CS). Each equation, or row, increases proving cost. Two of the most common circuit operations are checking that an integer fits in n bits and adding two 32-bit numbers. Standard circuits use n + 1 rows for an n-bit check.
This paper proves that an n-bit range check needs exactly n rows. Expressing the top bit as a linear combination of the input and lower bits saves one row because R1CS computes linear combinations without new equations. Adding two 32-bit integers takes either 32 or 33 rows with 31 allocated variables. The 1-row gap cannot be closed by merging the carry check and a bit check into one degree-two equation: the point counts of degenerate conics over finite fields cannot equal the four required values. The upper bounds match optimized implementations, while the lower bounds establish their algebraic limits.
Result
For an n-bit integer range check in R1CS over F_p:
- Row complexity is upper-bounded by n rows and n - 1 witness allocations via folded Num2Bits.
- Row complexity is lower-bounded by n rows. This bound is unconditional for n ∈ {1, 2} and conditional for n ≥ 3 on transferring the Bézout bound from the algebraic closure to F_p (ML-080).
For 32-bit unsigned integer addition (u32 add) in R1CS over F_p:
- Row complexity is upper-bounded by 33 rows with 31 witness allocations.
- Row complexity is lower-bounded by 32 rows, inherited from the output range check.
- Carry-booleanity fusion in a single R1CS constraint is impossible: any R1CS constraint whose quadratic part factors as a product of two linear forms has an F_p-point count in {0, p-1, p, 2p-1, 2p, p^2}, which cannot equal the 4-point target set {0, 1} × {0, 2^32}.
Setting and definitions
Let F_p be a prime field. An R1CS system over F_p consists of constraints of the form (sum_i u_i w_i) · (sum_i v_i w_i) = (sum_i w_i w_i), where w is an extended witness vector containing the constant 1, public inputs, and allocated intermediate variables.
An n-bit range check enforces x ∈ {0, ..., 2^n - 1} on an exposed variable x. A u32 addition gadget takes exposed inputs a, b ∈ {0, ..., 2^32 - 1} and enforces r = (a + b) mod 2^32 with r ∈ {0, ..., 2^32 - 1}.
Method
The n-row upper bound for the n-bit range check allocates n - 1 witness variables b_0, ..., b_{n-2} ∈ F_p. The most significant bit is an affine linear combination: b_{n-1} := (x - sum_{i=0}^{n-2} 2^i b_i) / 2^{n-1} Because affine combinations cost zero rows in R1CS, b_{n-1} requires no allocation. The circuit then enforces n booleanity constraints: b_i · (b_i - 1) = 0 for each i ∈ {0, ..., n-1} This yields n rows and n - 1 witness allocations.
The lower bound applies intersection theory: k R1CS rows define a variety whose projection onto an exposed variable has at most 2^k isolated solutions in the algebraic closure by refined Bézout bounds. For n = 1, 2, this yields an unconditional lower bound of n rows (MF-158, Corollary A). For n ≥ 3, the lower bound is n rows assuming the Bézout bound transfers to F_p points (ML-080).
For u32 addition, the gadget defines the linear remainder form L := a + b - r, allocates 31 witness bits for r, derives r_31 as a free linear combination, and applies 32 booleanity constraints on r_i. A carry constraint L · (L - 2^32) = 0 brings the total to 33 rows and 31 witness allocations.
The impossibility of 32-row u32 addition via carry-booleanity fusion follows from conic point counting over F_p. An R1CS constraint in two variables (b, L) takes the form L_1(b, L) · L_2(b, L) = L_3(b, L), defining a quadric curve in F_p^2. When the quadratic homogeneous part factors into linear forms L_1, L_2, the variety is reducible or degenerate over F_p. The point count |C(F_p)| belongs to {0, p-1, p, 2p-1, 2p, p^2}. Fusing the carry check with a bit check requires the constraint to vanish on precisely the 4 points of {0, 1} × {0, 2^32} in (b, L)-space. For p > 5, 4 ∉ {0, p-1, p, 2p-1, 2p, p^2}, which excludes single-row fusion.
Discussion
Prior art status is PARTIAL. Folded Num2Bits and the standard carry constraint are standard circuit engineering folklore. The contribution here is the formal lower bounds and the geometric obstruction ruling out carry-row elimination through constraint fusion.
The n-row lower bound for n-bit range checks is unconditional for n ∈ {1, 2} and conditional for n ≥ 3 on ML-080. The u32 addition row complexity lies in [32, 33]. Whether a 32-row gadget exists through non-conic or non-separable multi-variable constraints outside standard carry-booleanity fusion remains open.
For everyone — the takeaway
What this means
Every constraint in a zero-knowledge circuit adds prover and verifier work. Range checks and integer additions are among the most frequent operations in practical circuits. Checking an n-bit number takes exactly n constraints; folding the top bit into an unconstrained linear combination saves one row over textbook decompositions. For 32-bit addition, the cost is either 32 or 33 constraints, and algebraic geometry shows the carry check cannot simply be merged into a bit check.
Attribution and prior art
Prior art: This result is partial: the constructions follow standard practice, but the corresponding lower bounds have not yet been located.
Register references
- Register Entry: MF-161
- Candidate Receipts:
zk/BANK-CANDIDATES.md(ZK-C-06, ZK-C-07) - System Report:
zk/REPORT.md - Referenced Entries: MF-158 (Corollary A), ML-080
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 2 of 2 receipt files bundled (20 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-04
- 2026-09-04Published on this site.