Research · Papers · The SHA-256 record and exact synthesis · MF-141
Full linear rank of multiplicative rows in the SHA-256 leader circuit
Rank of 22,215 product equations modulo affine forms is 22,215/22,215 over GF(2); no linear product row elimination exists.
Published 2026-09-04
For everyone
Plain summary
SHA-256 generates digital fingerprints for data. In zero-knowledge proof systems, proving that a SHA-256 hash was calculated correctly gets expensive quickly, and the total cost depends on how many multiplications the circuit requires. Developers often try to shrink circuits by looking for redundant multiplication steps that can be rebuilt out of simpler combinations of existing ones.
This study analyzes the benchmark SHA-256 circuit, which uses 22,215 multiplication gates. Testing every linear relationship between these gates in binary arithmetic shows that all 22,215 are completely independent. You cannot remove or reconstruct any single multiplication by linearly combining the others. While this rules out simple linear shortcuts, it still leaves room for optimizations based on nonlinear mathematical redesigns.
Result
Flattening the pinned Lean 4.28 SHA-256 leader circuit yields 22,215 multiplicative rows of the form v_out + A*B, with A and B affine forms over GF(2). Sorted-parity normalization identifies 22,215 distinct unordered factor pairs and zero duplicates.
The linear rank of these 22,215 product equations modulo affine forms over GF(2) is 22,215 of 22,215. No row in the leader circuit can be eliminated through a GF(2)-linear combination of the remaining product equations modulo affine forms.
Setting and definitions
The analysis operates in the GF(2) XOR-and-graph (XAG) and R1CS setting on the flattened SHA-256 leader arithmetization pinned in Lean 4.28.
Each multiplicative constraint has the form v_out + A*B = 0, where v_out is an output wire and A, B are GF(2)-affine combinations of circuit wires. Sorted-parity normalization maps each product A*B to the canonical representation of its unordered factor pair modulo affine parity. Linear row elimination corresponds to identifying non-trivial GF(2)-linear dependencies among the normalized quadratic terms A*B modulo the subspace of affine forms.
Method
The deterministic algebraic pipeline executed as follows:
- Circuit extraction: extracted all 22,215 multiplicative rows from the pinned Lean 4.28 SHA-256 leader circuit.
- Normalization: applied sorted-parity normalization across all factor pairs, verifying that no duplicate unordered pairs exist.
- Linear elimination: ran exact GF(2) Gaussian elimination with first-occurrence pivots and triangular elimination.
- Schur complement: cleared the remaining dense submatrix using a 140-column targeted Schur complement.
The computation established a full rank of 22,215 out of 22,215 over GF(2). Complete execution traces and intermediate certificates reside in zkgolf-decomp/UNIT4-FREE03-PROGRESS.log and its scratch directory.
Discussion
This result rules out literal normalized product reuse and linear product row elimination modulo affine forms for the SHA-256 leader circuit.
The boundary of this negative result is strict: it applies only to linear combinations of existing product equations. It does not restrict nonlinear refactorizations, algebraic degree reductions, or alternative non-affine factor decompositions of the SHA-256 state update.
The status was initially unlabelled because a platform subscription limit terminated the execution seat before generating a standalone summary report, but the underlying proof certificates and logs remained intact in the execution log. The register records no prior-art position.
For everyone — the takeaway
What this means
Linear algebraic tricks cannot cut down the 22,215 multiplication gates in the benchmark SHA-256 circuit. Every multiplication step provides unique information that can't be rebuilt by adding up other steps. To make SHA-256 proofs smaller and faster, designers will need to discover entirely new, nonlinear formulations of the hash function rather than searching for linear redundancies.
Register references
- MF-141
- zkgolf-decomp/UNIT4-FREE03-PROGRESS.log
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 0 of 1 receipt files bundled (1 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.