Research · Papers · What rank-one constraints can express · MF-162
Witness power, degree collapse, and allocation walls over large prime fields
{x : x != 0} needs 1 witness, XOR3/MAJ3 degree collapse breaks MF-013 over F_p, and primitive walls hold against arbitrary allocations
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proof systems convert computations into systems of quadratic equations over large prime fields. This entry establishes three structural properties of those systems.
First, auxiliary helper variables (witnesses) provide qualitative expressive power. Checking whether a variable is non-zero takes exactly one equation when given a single helper variable, but is impossible with any number of equations if helper variables are forbidden.
Second, polynomial degree does not lower-bound equation counts over large prime fields. Certain three-input operations, such as three-way parity and majority, have cubic polynomial formulas but can be enforced with a single quadratic equation and zero helper variables by clearing a linear denominator. Binary parity-degree bounds from characteristic 2 do not carry over to prime fields.
Third, basic arithmetic primitives hit strict constraint floors that cannot be lowered no matter how many helper variables are allocated.
Result
Let F_p denote a large prime field, and consider Rank-1 Constraint Systems (R1CS) over F_p. The following structural theorems hold:
- Minimal witness separation: The relation {x ∈ F_p : x != 0} in a single exposed variable is satisfiable with exactly 1 constraint row and 1 witness variable via x·u = 1. Without witness variables, {x != 0} cannot be represented by any finite number of R1CS rows, because any witness-free system in one variable over F_p defines either all of F_p or an algebraic set of size at most 2.
- Degree collapse: Multilinear-degree-3 functions, specifically 3-input XOR (XOR3) and 3-input Majority (MAJ3), are realizable in R1CS with exactly 1 degree-2 constraint equation and 0 witness allocations by dividing the target relation by an input-dependent linear form. Consequently, polynomial degree does not lower-bound relational constraint counts over F_p, and the characteristic-2 parity-degree conjecture MF-013 does not transfer to F_p.
- Allocation walls: The following exact constraint lower bounds hold against an arbitrary number of witness allocations:
- Booleanity check: 1 row
- IsZero test: 2 rows
- 2-bit range check: 2 rows
- n-input conjunction (AND_n): 2 rows
- n-input disjunction (OR_n): 2 rows
- Multiplexer / selector: 2 rows
- Full adder: 2 rows
Setting and definitions
Let F_p be a prime field of large characteristic. An R1CS instance over F_p is a system of bilinear constraints:
(a_i · w) · (b_i · w) = c_i · w
where w contains the constant 1, public input and output variables (exposed variables), and private auxiliary variables (witness allocations). The row count is the number of constraints.
A relation R(x) on exposed variables is witness-free if w contains only 1 and x.
A degree collapse occurs when a relation R(x, y) for a function y = f(x) of multilinear polynomial degree d > 2 is enforced by a quadratic system without auxiliary variables by clearing an input-dependent linear denominator across the equality.
Method
Results are cataloged under Evidence tier P in zk/BANK-CANDIDATES.md (ZK-C-08) and zk/REPORT.md.
For witness separation, the inversion constraint x·u = 1 gives the upper bound. The lower bound follows from univariate polynomial geometry over F_p: a single degree-2 constraint in one variable without witnesses vanishes on all of F_p or has at most two roots. Any finite conjunction cuts out either F_p or at most 2 points, whereas |{x != 0}| = p - 1 > 2.
For degree collapse, explicit single-row witness-free quadratic forms for XOR3 and MAJ3 derived in MF-159 clear a non-vanishing linear factor across the Boolean domain {0,1}^3, reducing the multilinear cubic polynomial to a single quadratic equation.
For allocation walls, the exact lower bounds for booleanity, IsZero, 2-bit range checks, AND_n, OR_n, selectors, and full adders were proved invariant under arbitrary extension of the witness allocation vector.
Discussion
In characteristic 2, non-zero testing and parity constraints track strict polynomial-degree gradations. Over F_p, the multiplicative group F_p* enables single-witness inversion (x·u = 1), creating a separation where witness-free representation is impossible.
Degree collapse shows that algebraic degree in F_p[x_1, ..., x_n] does not lower-bound R1CS row counts: an implicit relation can be strictly cheaper than explicit polynomial evaluation of its function. The parity-degree bound in MF-013 is therefore restricted to characteristic 2. While degree-based bounds fail over F_p, the allocation walls establish unconditional lower bounds against arbitrary witness additions.
For everyone — the takeaway
What this means
Circuit designers on large prime fields cannot use standard polynomial degree to prove that a subcircuit requires multiple constraints. Functions that look cubic as formulas can collapse into a single quadratic constraint without helper variables.
Helper variables do provide essential power: basic operations like non-zero testing cannot be expressed without them. But that power hits hard limits. Core primitives like adders, selectors, and zero-tests have rigid row minimums that no amount of helper variable allocation can bypass.
Attribution and prior art
Prior art: PARTIAL / INTERNAL.
Register references
- Entry MF-162
- MF-013 (CONJECTURE)
- MF-159
zk/BANK-CANDIDATES.md(ZK-C-08)zk/REPORT.md
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.