Research · Papers · What rank-one constraints can express · MF-091
A minimal three-row quadratic constraint system for the inverse-or-default gadget
xy=1-z, xz=0, z(y-d)=0 uniquely defines z=[x=0], y=x⁻¹ (x≠0), y=d (x=0); 3 rows is minimal without auxiliary allocations over |F| ≥ 5
Published 2026-08-29
For everyone
Plain summary
Given an input \(x\) and a fallback \(d\) in a finite field, an inverse-or-default gadget outputs \(z=[x=0]\) and \(y\), where \(y=x^{-1}\) when \(x\ne0\) and \(y=d\) when \(x=0\). The standard approach combines an IsZero gadget with a multiplexer, using three equations and three allocated values, including an internal inverse witness \(u\). The fused design eliminates \(u\), exposing only \(z\) and \(y\) across the same three equations. Compiling both designs with Circom 2.2.3 at optimization levels O0 and O2 preserves the 3-row count while reducing total wires, including the constant, from 6 to 5. For every finite field with at least five elements, three rows are minimal across all quadratic constraint systems without hidden variables. The register records no prior art for this construction.
Result
Let \(x,d\) be field inputs. The fixed interface exposes
\[ z=[x=0], \qquad y= \begin{cases} x^{-1},&x\ne0,\\ d,&x=0. \end{cases} \]
Direct composition of IsZero with a one-row multiplexer allocates \((z,u,y)\) across three rank-one constraints. The inverse witness \(u\) is unique when \(x\ne0\) and unconstrained when \(x=0\). The fused relation eliminates \(u\), using only the two exposed outputs in three rank-one rows:
\[ xy=1-z,\qquad xz=0,\qquad z(y-d)=0. \]
Circom 2.2.3 compiles both circuits to 3 rows under O0 and O2, reducing wire count from 6 to 5 including the constant wire. Over any finite field with at least five elements, three rows are minimal across arbitrary quadratic equations without auxiliary allocations. The fused relation admits a unique witness, exploiting the baseline's zero-fibre freedom to merge allocations without adding rows.
Setting and definitions
Let the base field be any finite field with at least five elements. The bracket \([x=0]\) denotes the zero indicator: 1 if \(x=0\) and 0 otherwise. An allocated signal is an internal variable tracked by the constraint system, and a row is one constraint equation. The baseline allocates exposed outputs \(z,y\) alongside the hidden inverse witness \(u\); the fused system allocates only \(z,y\). The minimality bound permits arbitrary quadratic rows and disallows auxiliary unexposed signals.
Method
Exact algebraic verification on each fibre establishes correctness: when \(x\ne0\), the system forces \(z=0\) and \(y=x^{-1}\); when \(x=0\), it forces \(z=1\) and \(y=d\). Baseline and fused circuits were compiled in Circom 2.2.3 under O0 and O2 to verify row and wire counts. A minimality certificate confirms that no two-row quadratic system without hidden allocations can compute the interface over finite fields of size at least five. The circuit definitions, minimality certificates, and compiler receipts are available in this paper's downloadable evidence pack.
Discussion
The allocation saving applies strictly to the InvOrDefault interface: it removes one auxiliary variable while maintaining three rows, which is proven minimal for any quadratic system lacking hidden signals over finite fields of size at least five. Because the baseline inverse witness is unconstrained at \(x=0\), fusing it into the exposed output \(y\) preserves unique satisfiability without increasing constraint degree. The result does not extend row savings or witness merging to other gadget interfaces. The register records no prior art, and this work claims no historical priority.
For everyone — the takeaway
What this means
A circuit computing an inverse with a zero fallback can discard an internal temporary variable without adding constraint equations. Over finite fields with at least five elements, three equations are the mathematical floor for this interface when no extra hidden signals are introduced. The optimization works by repurposing a variable that was previously arbitrary on the zero branch.
Register references
- Entry: MF-091.
- Receipt artifacts: 01-r1cs-gadget-theory/InvOrDefaultFused.circom; InvOrDefaultBaseline.circom; quadratic_relation_certificate.py and .json; circom_r1cs_receipt.py; circom_compile_receipt.json; circom-build/; circom-build-o2/.
- Prior-art works: the register does not record this.
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 (8 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.