The SHA-256 record and exact synthesis

What this programme is about

SHA-256 runs inside zero-knowledge proof systems and secure hardware. In these systems, additions and bitwise XORs are free, while non-linear multiplications dictate the cost, memory, and runtime of verifying computations. Every product gate costs real prover time. The programme seeks the absolute minimum count of non-linear products needed to evaluate the SHA-256 compression function, alongside verifiable circuits that attain that bound. For engineers outside circuit complexity, every saved multiplication gate directly cuts the circuit area, electrical power, and prover latency required to check cryptographic proofs and rollup batches. Establishing provable lower bounds and exact synthesis records tells system designers whether proof systems can shrink further or whether existing circuits have reached their lowest possible gate count.

What has been settled

The programme groups its settled results into three core themes:

The verified leader and circuit rigidity. The verified SHA-256 compilation record stands at 22,215 ordered identity-C rows [MF-108, ML-063]. The register disclaims priority or world-first status beyond this verified artifact, noting that hypothetical 20,531-row figures fail to transfer across fixed constants or compiled constraints MF-108. All 22,215 product equations achieve full linear rank over GF(2) modulo affine forms MF-141, ruling out linear row elimination. Exact scans across fixed structural-XOR classes find no free-row reductions ML-010, and all 20,525 fixed-interface factor components have full rank ML-035. Banked component certificates cover 91.15% of the leader but license zero reductions due to non-additivity ML-067, and consecutive round pairs remain strictly additive ML-069.

Exact tile complexity. The ten-input schedule tile requires exactly six product gates in the acyclic XOR-AND model over GF(2) [MF-001, ML-008]. An extremal degree-six Pluecker obstruction rules out five-product circuits. The exact four-word boundary tile has no p8 circuit ML-025, where the register corrected a scope conflation between unequal-weight binary carries and a separate Add3 pair. Redundant-carry seam chains cost 3c gates, exceeding the 2.875c schedule threshold ML-073.

Gauge growth and refuted allocations. The consecutive-Maj identity holds across all 16 local inputs MF-057. However, because odd cyclic rotation sums are invertible in F2[x]/((x+1)^{2^r}) MF-063, the edge relation has a 32-bit free intermediate with fibre cardinality 2^32 MF-062. A corrective receipt confirmed this gauge coordinate destroys anticipated savings MF-057, refuting the candidate -1,024-row phase via linear gauge growth ML-071. For joint semantic allocations, evaluation hulls eliminate acyclic one-catalyst lifts for JSC-11 ML-072, and candidate cubics miss over 781 million invalid points for JSC-12 ML-046.

What is still open

Several conjectures and structural frontiers remain unresolved across the register:

The stationary p7 route targeting 21,738 remains live-parked ML-023; an unexhausted prefix with 2,018 dead tails and 181,441 blockers leaves global closure unknown. While flat Joint Semantic-Carry systems in 41 coordinates are closed at every budget ML-031, non-flat and chained presentations remain open conjectures [ML-031, ML-037]. The conditional 17,841 arithmetic instance for JSC-11 lacks an adapter, proof, or replay receipt ML-037. All supplied JSC seeds fail quadratic-hull screens, leaving joint two-column relations untested MF-048. Six of 32 degree-eight p7-eligible edges pass the support-cage test, so unrestricted circuit impossibility remains unproven ML-044. Finally, non-flat consecutive-Maj gauge closure lacks validating masks or replay certificates [ML-036, ML-039], and polar-rank searches for JSC-12 leave the rank-six-or-lower subspace unexhausted ML-042.

How to read the evidence

Receipted accounting and exhaustive computation dominate this programme, supported by machine-checked certificates and written proofs. This evidence profile means the negative results, including lower bounds, rank ceilings, and refuted candidate topologies, are definitive over their stated search spaces. Conversely, candidate reductions demand caution: partial-domain solver runs can propose invalid circuits, making full-domain replay mandatory MF-020. A claim in this register only becomes settled when backstopped by full linear rank or exhaustive verification.