Research · Papers · What rank-one constraints can express · MF-159
Exact R1CS complexity of XOR3 and MAJ3 gadgets
XOR3: (2s - t)·t = 3s - 2t; MAJ3: (4y - t)·t = 6y - t over F_p (p ∉ {2,3}), costing exactly 1 R1CS row with 0 allocations
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proof systems check computations using systems of quadratic equations called Rank-1 Constraint Systems (R1CS). Checking a three-input XOR (which verifies whether an odd number of three inputs are true) or a three-input majority (which verifies whether at least two of three inputs are true) standardly requires two equations and an extra helper variable per bit. This work proves that both functions can be evaluated using exactly one equation and zero helper variables over fields whose characteristic is not 2 or 3. This halves the algebraic cost of these operations in circuits like SHA-256.
Result
Let F_p be a field with characteristic p ∉ {2, 3}. Let a, b, c ∈ F_p satisfy the boolean promise a, b, c ∈ {0, 1}, and let t := a + b + c.
- The three-input XOR relation s = XOR3(a, b, c) is uniquely determined by the single R1CS constraint:
(2s - t)·t = 3s - 2t
- The three-input majority relation y = MAJ3(a, b, c) is uniquely determined by the single R1CS constraint:
(4y - t)·t = 6y - t
Both gadgets require exactly 1 R1CS row and 0 auxiliary allocations. The resulting solutions satisfy s, y ∈ {0, 1}, preserving downstream boolean promises. The 1-row cost is strictly optimal, as 0 rows leaves the output variable unconstrained.
Setting and definitions
In an R1CS instance over F_p, every constraint takes the bilinear form (L_A · w) · (L_B · w) = (L_C · w), where w is the witness vector and L_A, L_B, L_C are linear combinations over F_p. An auxiliary allocation is an additional intermediate entry appended to w beyond the inputs and output.
The inputs a, b, c ∈ F_p carry an external boolean promise enforced by prior circuit constraints, such that a, b, c ∈ {0, 1}. The linear combination t := a + b + c adds no R1CS constraints and evaluates to an integer in {0, 1, 2, 3}.
Method
Rearranging each relation isolates the output variable as a linear function of t.
For XOR3, expanding (2s - t)·t = 3s - 2t yields: (2t - 3)s = t^2 - 2t
Evaluating across all promised sum values t ∈ {0, 1, 2, 3}:
- t = 0: -3s = 0, giving s = 0.
- t = 1: -1s = -1, giving s = 1.
- t = 2: 1s = 0, giving s = 0.
- t = 3: 3s = 3, giving s = 1.
For MAJ3, expanding (4y - t)·t = 6y - t yields: (4t - 6)y = t^2 - t
Evaluating across all promised sum values t ∈ {0, 1, 2, 3}:
- t = 0: -6y = 0, giving y = 0.
- t = 1: -2y = 0, giving y = 0.
- t = 2: 2y = 2, giving y = 1.
- t = 3: 6y = 6, giving y = 1.
Soundness and completeness hold because the leading coefficients 2t - 3 ∈ {±1, ±3} and 4t - 6 ∈ {±2, ±6} are non-zero in F_p when p ∉ {2, 3}, uniquely fixing the output for every valid input combination.
The lower bound is exact: zero constraints leaves the output variable unconstrained, so at least one constraint is required.
Deployed baselines were verified by inspecting source code in the iden3 circomlib repository (sha256/xor3.circom and sha256/maj.circom) and the bkomuves/hash-circuits repository.
Discussion
Soundness requires two explicitly tracked preconditions:
- The inputs a, b, c must carry boolean promises. If an input falls outside {0, 1}, t can produce 2t - 3 = 0 or 4t - 6 = 0, causing division by zero or underconstraining the output.
- The field characteristic p cannot be 2 or 3, as {±2, ±3, ±6} must be invertible in F_p.
Prior art analysis marked this result APPARENTLY-NEW following five literature searches and code inspection of standard libraries. Implementations in iden3 circomlib allocate an intermediate wire mid = b·c followed by an output constraint, consuming 2 rows and 1 allocation per bit. The bkomuves/hash-circuits repository ships two XOR3 variants, each requiring 2 constraints.
A standard SHA-256 round evaluates two 32-wide XOR3 operations and one 32-wide MAJ3 operation. Applying these single-row gadgets halves the constraint and allocation cost for all three gadget families in each round.
For everyone — the takeaway
What this means
Proving systems spend significant compute verifying bitwise cryptographic algorithms like SHA-256. Standard implementations of three-input logic gates take two equations and a helper variable for every bit. These constructions evaluate both three-input XOR and three-input majority using one equation and zero helper variables. As long as inputs are already guaranteed to be bits and the underlying field avoids characteristics 2 and 3, circuits can cut the size and cost of these common building blocks in half.
Attribution and prior art
Prior art: This result is classified as apparently new, the highest novelty rating from our review. This follows an inspection of the two reference libraries most likely to contain it and five targeted literature searches.
Register references
- Register Entry: MF-159
- zk/REPORT.md
- zk/BANK-CANDIDATES.md (entry ZK-C-03)
- wave1-priorart/sources/circomlib-constraint-counts.txt
- iden3 circomlib (
sha256/xor3.circom,sha256/maj.circom, source inspection 2026-09-01) - bkomuves/hash-circuits
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 (22 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.