Research · Papers · What rank-one constraints can express · MF-158
Classification of relations implemented by single-row R1CS over F_p
A single row A·B = C over F_p with m witnesses implements one of 4 types: F^n, {q=0}, {L≠0}∪({L=0}∩{q=0}), or {x : Δ(x) is a square}.
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proof circuits often rely on Rank-1 Constraint Systems (R1CS), which chain together equations of the form A · B = C. When building these circuits, designers can add hidden helper variables to express complex rules. This entry classifies every relation a single R1CS row can enforce over a prime field F_p, no matter how many helper variables it uses.
Every single-row relation falls into one of four rigid geometric shapes: the entire space, the roots of a quadratic equation that factors into two lines, an open affine set joined with a quadratic intersection, or the inputs where a quadratic polynomial yields a square. This rigidity forces sharp gaps in what one row can build. For instance, on a single exposed variable over F_p with p >= 13, no single row can accept an input count strictly between 2 and (p-3)/2.
Result
Let F_p be a prime field. Let x ∈ F_p^n denote the vector of exposed variables, and let w ∈ F_p^m denote auxiliary witness variables. Consider a single R1CS constraint row
A(x, w) · B(x, w) = C(x, w)
where A, B, and C are affine forms over F_p. The implemented relation R ⊂ F_p^n is the existential projection
R = {x ∈ F_p^n : ∃ w ∈ F_p^m, A(x, w) · B(x, w) = C(x, w)}.
The single-row R1CS classification theorem shows that R belongs to exactly one of four geometric types:
- R = F_p^n.
- R = {x ∈ F_p^n : q(x) = 0}, where deg q <= 2 and the homogeneous quadratic part of q factors into two F_p-linear forms.
- R = {x ∈ F_p^n : L(x) ≠ 0} ∪ ({x ∈ F_p^n : L(x) = 0} ∩ {x ∈ F_p^n : q(x) = 0}), where L is an affine form and deg q <= 2.
- R = {x ∈ F_p^n : Δ(x) is a square in F_p}, where deg Δ <= 2.
The theorem yields two structural corollaries:
- Corollary A (Size gap): For n = 1 and p >= 13, any implemented relation R ⊂ F_p satisfies either |R| <= 2 or |R| >= (p-3)/2.
- Corollary B (Two-variable point isolation impossibility): For p >= 5, no single-row R1CS system implements R ⊂ F_p^2 with |R| ∈ {1, 2}.
Additionally, the classification establishes a reduction lemma: every k-row R1CS system is equivalent to an R1CS system with at most 3k witness variables, bounding unconstrained witness allocations to a finite search space. The classification also supplies an exact one-row decision criterion for Boolean-promise gadgets (Theorem 5).
Setting and definitions
An R1CS instance over F_p with n exposed variables and m witness variables consists of affine form triples (A_i, B_i, C_i) for i = 1, ..., k, mapping F_p^(n+m) to F_p. The system implements a relation R ⊂ F_p^n via the existential projection onto F_p^n of the common solution set where A_i(x, w) · B_i(x, w) = C_i(x, w) for all i.
An affine form L(x) over F_p^n is a polynomial of degree at most 1. A quadratic form q(x) over F_p^n has degree at most 2; its quadratic part splits over F_p if it factors as L_1(x) · L_2(x) for linear forms L_1, L_2. An element y ∈ F_p is a square if z^2 = y for some z ∈ F_p.
Method
The classification is proved by complete algebraic case analysis over the coefficients of A, B, and C with respect to w (evidence tier P). The reduction lemma bounds the rank of witness contributions in any single row by 3, reducing arbitrary witness allocation m to an equivalent system with m <= 3.
The analytical result was verified computationally (evidence tier FC) by exhaustive enumeration of one-row, one-witness systems:
- At p = 5, testing all 5^9 constraint configurations yielded 32 distinct relations covering sizes {0, 1, 2, 3, 4, 5}.
- At p = 7, testing all 7^9 = 40,353,607 configurations yielded 93 distinct relations of sizes in {0, 1, 2, 3, 4, 6, 7}. Size 5 was absent, matching the size gap in Corollary A.
Receipts are in zk/REPORT.md §3, zk/one_row_census.py, and one_row_census.json.
Discussion
The classification establishes an exhaustive taxonomy of single-row R1CS expressiveness over prime fields. Free existential witness quantification (MF-006) cannot generate arbitrary subsets under one constraint because the geometric projection of a single bilinear form is bounded.
The prior-art status is APPARENTLY-NEW / PARTIAL. Finite-field quadric geometry is classical, but characterizing unconstrained witness projections as an R1CS expressiveness taxonomy is new to the arithmetization literature.
The classification covers single-row systems (k = 1) over F_p. Multi-row systems (k >= 2) generate intersections and projections of these basic sets, expanding expressiveness. Even so, the reduction lemma guarantees that for any fixed k, the effective witness dimension remains bounded by 3k.
For everyone — the takeaway
What this means
Zero-knowledge circuits translate computation into multiplication checks. Designers often add hidden helper variables to pack more behavior into fewer constraints.
This theorem proves that adding helper variables to a single row hits a hard wall: three helper variables can express anything an infinite number can. Because single rows can only produce four geometric patterns, many compact gadget designs are provably impossible and require at least two rows.
Attribution and prior art
Prior art: This appears to be a new, partial result applying elementary algebraic geometry to a single quadratic equation. We have not found this specific case in prior literature on Rank-1 Constraint System (R1CS) expressiveness classifications.
Register references
- Entry ID: MF-158
- Related entry: MF-006
- Receipt artifacts:
zk/REPORT.md§3,zk/one_row_census.py,one_row_census.json
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 3 of 3 receipt files bundled (13 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.