Research · Papers · What rank-one constraints can express · ML-080
Limitations and obstructions in R1CS gadget arithmetization over F_p
Range check bounds have rationality gaps for n ≥ 3, u32 addition [32,33] has conic obstruction, XOR3/MAJ3 requires p ∉ {2,3} and boolean inputs
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proof systems translate programs into systems of quadratic equations called Rank-1 Constraint Systems (R1CS) over a prime field F_p. Engineers build small components called gadgets to handle basic operations like bit checks, addition, and logic gates. This entry catalogs mathematical obstructions and unstated assumptions across standard gadget lower bounds.
The n-row lower bound for checking that a number fits in n bits is unconditionally proved only for n <= 2; for larger values, it relies on an unproved transfer of geometric intersection bounds to finite field points. For 32-bit addition, attempting to fuse carry bits into boolean constraints hits a geometric obstruction on conic curves, keeping the row count at 33 instead of 32. Compact single-row XOR3 and MAJ3 gadgets work only if inputs are already guaranteed to be boolean and the field characteristic p is not 2 or 3.
Result
The register catalogs five structural obstructions and open gaps in R1CS arithmetization over F_p:
- Rationality gap: The n-row lower bound for the n-bit range check (MF-161) is unconditional only at n <= 2. For n >= 3, establishing the bound requires transferring the refined Bézout count from the algebraic closure to F_p-points, which remains unproved.
- 32-bit addition bracket: The u32 addition bracket [32,33] cannot be closed to 32 rows by fusing the carry row into a booleanity row due to a conic point-count obstruction. A 32-row system requires a different constraint structure.
- Characteristic and input promise requirements: One-row XOR3 and MAJ3 gadgets (MF-159) require p > 2^{n+1} - 1-type non-degeneracy, concretely p ∉ {2,3} for coefficient sets {±1,±3} and {±2,±6}. Their soundness proofs assume boolean-promised inputs; unpromised inputs break completeness.
- Toolchain compilation status: No .r1cs compilation receipt exists. The baseline counts of 2 rows from circomlib derive from source inspection rather than compiled outputs from circom --r1cs.
- Absence of two-row classification: There is no two-row classification theorem. MF-158 applies only to one row. A verdict of "= 2" represents a one-row impossibility result paired with an explicit two-row construction, not a complete two-row characterisation.
Setting and definitions
Let F_p denote a finite prime field of characteristic p. A Rank-1 Constraint System (R1CS) over F_p is a system of quadratic equations of the form (A · z) * (B · z) = (C · z), where A, B, C are linear combinations of the witness vector z and * denotes scalar multiplication in F_p.
- n-bit range check: A gadget enforcing that a given field element represents an integer in [0, 2^n - 1].
- u32 addition: A gadget checking unsigned 32-bit addition modulo 2^32, using 32 bit-level constraints and carry propagation.
- XOR3 and MAJ3 gadgets: One-row constraint formulations enforcing three-input XOR and majority functions over field elements.
- Boolean-promised inputs: An operational precondition where input variables are constrained to {0, 1} ⊂ F_p before gadget evaluation.
Method
Findings derive from analyzing algebraic geometry bounds in R1CS systems recorded in zk/REPORT.md §§5–6 and zk/BANK-CANDIDATES.md ZK-C-06..08. The rationality obstruction was isolated by evaluating where refined Bézout intersection counts over algebraically closed fields fail to transfer to F_p rational points. The u32 addition obstruction was identified by calculating point counts on algebraic conics formed by fusing carry and booleanity relations. Modulus constraints and boolean input dependencies for XOR3/MAJ3 were evaluated via completeness of linear combinations over coefficient sets {±1,±3} and {±2,±6}. Circomlib row counts were assessed directly from source code inspection.
Discussion
The register notes several explicit caveats and scope limitations: Multiple gadget bounds omit necessary input promises and algebraic closure transfer arguments.
- Rationality transfer: The range check lower bound for n >= 3 remains open pending a proof that Bézout intersection counts over the algebraic closure transfer to F_p rational points without spurious solutions.
- Input promises: Single-row XOR3/MAJ3 constructions are not self-contained bit checkers. If inputs lack prior boolean constraints, completeness fails.
- Characteristic limits: One-row gadgets fail over fields where p ∈ {2,3}.
- Experimental validation: No compiled .r1cs receipts were generated because the working environment lacked network access and the circom toolchain.
- Classification scope: Multi-row optimality claims are not full algebraic characterisations because a two-row classification theorem does not exist.
For everyone — the takeaway
What this means
Zero-knowledge circuits run faster with fewer mathematical constraints, but theoretical minimum row counts sometimes depend on hidden algebraic assumptions. Some lower bounds assume theorems from continuous geometry that are not yet proved for finite fields, certain carry-bit shortcuts fail because of the geometry of conic curves, and compact logic gates break if inputs are not pre-checked or if the field characteristic is 2 or 3. Recognizing these constraints prevents soundness flaws in circuit design.
Register references
- Entry: ML-080
- Related register entries: MF-158, MF-159, MF-161
- Receipts and source files: zk/REPORT.md §§5–6, zk/BANK-CANDIDATES.md ZK-C-06..08
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.