Research · Papers · What rank-one constraints can express · MF-177
Estimated SHA-256 R1CS constraint reduction via XOR3 and MAJ3 gadgets
SHA-256 R1CS constraint count estimated to decrease from 28,528 to 19,688 over F_p (-30.99%) using one-row XOR3/MAJ3 gadgets
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proof systems let someone prove a computation, like running a SHA-256 hash, was done honestly without revealing private inputs. In Rank-1 Constraint Systems (R1CS), computations become sets of quadratic equations over a prime field, where the total row count dictates proving time. This entry estimates that swapping compact one-row equations in for 3-input XOR (XOR3) and 3-input majority (MAJ3) functions drops the SHA-256 R1CS count from the Circomlib baseline of 28,528 rows to 19,688 rows, saving 8,840 rows (30.99%). This reduction is an arithmetic template estimate, not a verified circuit. It lacks compiler verification, witness generation on test vectors, and a formal proof that witness solutions over the field are unique.
Result
Over a prime field F_p with characteristic p not in {2, 3}, substituting candidate one-row algebraic gadgets for XOR3 and MAJ3 into the SHA-256 compression circuit yields an estimated R1CS constraint count of 19,688 rows, down 8,840 rows (-30.99%) from the Circomlib baseline of 28,528 rows.
The 8,840-row saving breaks down as:
- Message schedule (48 words, t = 16..63): 52 rows and 51 allocations saved per word, totaling 2,496 rows across 48 words.
- Compression rounds (64 rounds): 99 rows and 96 allocations saved per round, totaling 6,336 rows across 64 rounds.
Setting and definitions
The cost model is R1CS row count over F_p, distinct from multiplicative complexity over GF(2).
The candidate one-row algebraic relations from MF-159 are:
- XOR3 gadget: (2s - t) * t = 3s - 2t
- MAJ3 gadget: (4y - t) * t = 6y - t
The baseline comparison is the Circomlib SHA-256 implementation at 28,528 R1CS constraints.
Method
Constraint counts come from template-level component arithmetic logged in wave2-zk-gadgets/sha256_r1cs_ledger.json and evaluated via wave2-zk-gadgets/zk_gadgets_sha256.py.
Component replacements:
- Message schedule (words t = 16..63):
- sigma0: 61 to 32 rows.
- sigma1: 54 to 32 rows.
- 4-operand adder: 35 to 34 rows using a folded range check.
- Word total: 52 rows saved per word across 48 words, yielding 2,496 rows saved.
- Compression rounds (rounds 0..63):
- Sigma0: 64 to 32 rows.
- Sigma1: 64 to 32 rows.
- Maj: 64 to 32 rows.
- Additions: 105 to 102 rows.
- Round total: 99 rows saved per round across 64 rounds, yielding 6,336 rows saved.
Total rows saved: 2,496 + 6,336 = 8,840. Total estimated constraints: 28,528 - 8,840 = 19,688.
Discussion
Two caveats govern the result:
- Template estimate only: The 8,840-row saving is an analytical estimate from component templates, not a compiled circuit. No Circom compilation, R1CS circuit export, or witness generation against standardized test vectors (such as an empty message) has been run.
- Unproven witness uniqueness: A formal proof of field witness uniqueness over F_p for prime characteristics p not in {2, 3} remains open.
The analysis predicts row savings on paper but does not certify an executable, sound R1CS circuit.
For everyone — the takeaway
What this means
Standard hash functions like SHA-256 are major bottlenecks in zero-knowledge proofs because they require tens of thousands of R1CS constraints. Using one-row algebraic relations for 3-input bitwise operations could cut SHA-256 constraint costs by nearly 31%. For circuit engineers, this points to a clear optimization route. Still, because this is an uncompiled template estimate without uniqueness proofs, it cannot run in production circuits until verified in a compiler and tested against reference inputs.
Attribution and prior art
Prior art: This result is compared against the Circomlib baseline of 28,528 R1CS constraints.
Register references
- Register Entry MF-177
- Register Entry MF-159 (candidate one-row algebraic relations)
- Circomlib SHA-256 baseline
- wave2-zk-gadgets/sha256_r1cs_ledger.json
- wave2-zk-gadgets/zk_gadgets_sha256.py
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 (3 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.