Research · Papers · What rank-one constraints can express · MF-160
Exact R1CS Row Counts and Allocation-Independent Lower Bounds for Basic Gadgets
R1CS row counts: IsZero = 2, AND_n = OR_n = 2 for all n ≥ 3, XOR4 = 2 over F_p (p ≥ 7), with no 1-row systems possible.
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proof systems let someone prove a statement is true without exposing the underlying private data. To do this, programs are compiled into systems of arithmetic constraints called Rank-1 Constraint Systems, or R1CS. Computational cost scales directly with the number of constraint rows in the system. Circuit designers rely on small standard building blocks, called gadgets, to test whether a value is zero, run logical AND or OR checks across many inputs, or add bits.
Standard libraries like circomlib have long used two-row designs for these gadgets, but whether they could fit into a single row remained an open question. This work proves exact lower bounds on row counts for basic gadgets over large prime fields. Checking whether an input is zero strictly requires at least two rows, as do wide AND and OR operations across any number of inputs. The textbook implementations are already optimal, so no compiler can shrink their row count further.
Result
Over a prime field F_p with characteristic p >= 7, the exact minimal R1CS constraint row counts for standard arithmetic gadgets are:
- IsZero: Exactly 2 rows and 1 auxiliary witness allocation. The relation Γ0 = {(0,1)} ∪ {(x,0) : x != 0} admits no 1-row R1CS realization for any number of witness allocations. Combined with the impossibility of helper-free IsZero at any row count (ML-050), the tuple (2 rows, 1 allocation) sits at the unconstrained Pareto minimum on both axes. The bound transfers directly to IsEqual.
- AND_n and OR_n: Exactly 2 rows and 1 auxiliary witness allocation for all input arities n >= 3, independent of n.
- XOR4: Exactly 2 rows.
- Additional exact gadget counts:
- Booleanity check: 1 row.
- Non-zero assertion (x != 0): 1 row (requiring 1 auxiliary witness, MF-162).
- 2-bit range check: 2 rows.
- Multiplexer/selector with booleanity: 2 rows.
- Full adder: 2 rows in standard form, reducing to 1 row with a linear carry-out interface.
Setting and definitions
Let F_p be a finite field of prime order p >= 7. An R1CS constraint over F_p with input variables x, output variables y, and auxiliary witness variables w has the standard form:
(⟨a, v⟩) · (⟨b, v⟩) = ⟨c, v⟩
where v = (1, x, y, w) is the combined assignment vector, and a, b, c ∈ F_p^(dim v). The row count of an R1CS gadget is the number of such quadratic constraints. The allocation count is dim w.
A linear form L(x) over the inputs is free, incurring zero constraint rows. The gadget IsZero maps input x to z ∈ {0, 1} with z = 1 if x = 0 and z = 0 if x != 0. The relation graph is Γ0 = {(0,1)} ∪ {(x,0) : x != 0}.
For a multilinear polynomial P(b_1, ..., b_n), the top multilinear coefficient c_top(P) denotes the coefficient of the monomial b_1 · b_2 · ... · b_n.
Method
- IsZero lower and upper bound:
- Upper bound: The standard construction enforces x · u = 1 - z and x · z = 0 using 2 rows and 1 auxiliary witness allocation u. When x = 0, the second constraint holds vacuously and the first forces z = 1. When x != 0, the first forces u = x^(-1) and the second forces z = 0.
- Lower bound: A 1-row R1CS constraint has form L_1(x, z, w) · L_2(x, z, w) = L_3(x, z, w). By the MF-158 algebraic characterization over F_p (p >= 7), the solution variety of a single quadratic equation cannot project onto Γ0 over the (x, z) coordinates for any finite choice of witness functions w_k(x).
- AND_n and OR_n allocation-independent bounds:
- Upper bound: For Boolean inputs b_1, ..., b_n ∈ {0, 1}, the linear form L_AND = (sum from i=1 to n of b_i) - n vanishes if and only if b_1 = ... = b_n = 1. Evaluating IsZero on L_AND computes the n-ary AND. Similarly, evaluating IsZero on L_OR = sum from i=1 to n of b_i tests whether all inputs are 0, yielding the negated n-ary OR. Free linear forms keep both gadgets at 2 rows and 1 witness allocation for all n >= 3.
- Lower bound: For a single row L_1 · L_2 = L_3 with affine forms L_j over b_1, ..., b_n, the product L_1 · L_2 has multilinear degree at most 2, giving c_top(L_1 · L_2) = 0 for all n >= 3. The target n-ary AND polynomial has multilinear degree n with top coefficient c_top(B · AND_n) = B(1, 1, ..., 1) != 0 for any non-zero scalar multiplier B. No single R1CS row can enforce n-ary AND or OR for n >= 3.
- Interface fusion:
- The standard full adder uses 2 rows (one for the sum bit, one for the carry bit). If the downstream consumer takes a linear carry-out representation, carry computation absorbs into the arithmetic sum row, shrinking the gadget to 1 row via boundary fusion (MF-091).
Discussion
Textbook libraries like circomlib have long used these two-row constructions, but lacked matching lower bounds proving their minimality. MF-160 establishes those lower bounds across the core gadget catalog.
The analysis separates arithmetization over large fields F_p from GF(2) (the F2 face in MF-058, MF-059, and MF-060). Over F_p, free linear combinations over large characteristic make the sum (sum from i=1 to n of b_i) the critical primitive that bounds n-ary operations to an allocation-independent cost of 2 rows.
The bounds also rule out trade-offs between row count and auxiliary witness allocations in IsZero. Because ML-050 shows helper-free IsZero is impossible at any row count, the standard circomlib design reaches the simultaneous minimum on both Pareto axes: 2 rows and 1 allocation.
For everyone — the takeaway
What this means
R1CS-based proof systems spend most of their constraint budgets on recurring primitives like zero checks, multiplexers, and wide logic gates. Proof generation and verification costs track row counts directly, so compilers try to shrink every gadget.
These bounds prove that standard library implementations cannot be compressed further. Testing for zero or evaluating an n-input AND gate fundamentally requires at least two rows. Circuit compilers can treat these 2-row figures as hard limits.
Attribution and prior art
Prior art: This result is partial: the gadgets rely on standard implementations from circomlib, but no proofs were found showing that these R1CS row counts are optimal.
Register references
- Register Entry: MF-160
- Related Register Entries: MF-058, MF-059, MF-060, MF-091, MF-158, MF-162, ML-050
- Artifact Sources:
zk/BANK-CANDIDATES.md(ZK-C-02, ZK-C-04, ZK-C-05),zk/REPORT.md - Prior Art: circomlib standard library (partial prior art: textbook gadget implementations without optimality proofs)
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.