Research · Papers · The SHA-256 record and exact synthesis · ML-067
Limits of SHA-256 row reduction from banked component certificates
Banked certificates cover 20,248 of 22,215 SHA-256 rows but license 0 reductions due to non-additivity and a 1,967-row component deficit
Published 2026-09-04
For everyone
Plain summary
Zero-knowledge proofs often represent the SHA-256 hash function as a grid of computational rows, where fewer rows mean faster verification. One strategy attempts to shrink the full circuit by proving minimum row counts for isolated sub-circuits and storing the results as formal certificates.
This entry shows that assembling the current collection of component certificates yields zero row savings for full SHA-256. While existing certificates cover 20,248 out of 22,215 baseline rows (about 91.15%), 1,967 rows remain uncertified. Furthermore, row counts inside separate sub-circuits do not simply add together when the parts are wired together. The certification catalog remains a valid baseline reference, but directly chaining these certificates cannot reduce full SHA-256 row counts.
Result
Direct composition of banked component certificates licenses 0 row reductions for the unrestricted SHA-256 compression map in the GF(2) XAG (XOR-free) cost model.
The banked component ledger covers 20,248 out of 22,215 leader rows (91.1456%), with 7,692 rows established as locally exact at leader price. However, the fixed-decomposition ledger retains a 1,967-row component deficit, and local component floors do not compose additively across component boundaries.
Setting and definitions
The setting evaluates the SHA-256 compression function under the GF(2) XAG (XOR-free) cost model against a 22,215-row leader baseline.
- Banked component ledger: The repository of verified complexity certificates for isolated SHA-256 subroutines.
- Locally exact rows: The 7,692 rows where component certificates match the exact cost of the corresponding subroutines in the leader implementation.
- Component deficit: The 1,967 leader rows in the fixed decomposition that lack banked component certificates.
Method
The ledger was audited against the certificate repository recorded in zkgolf-decomp/REDEPLOY-CERTIFICATION.md across all 22,215 leader rows. Sub-circuit interfaces were evaluated under GF(2) XAG rules for the existence of direct-sum or cross-boundary composition theorems.
Discussion
The negative verdict applies strictly to immediate row reductions derived by composing existing component certificates. It does not invalidate individual sub-circuit certificates or the broader certify-not-beat program.
Two structural barriers block reduction:
- Ledger deficit: An uncertified margin of 1,967 rows of the baseline circuit remains outside the banked ledger.
- Non-additivity: In the unrestricted GF(2) XAG setting, component complexity floors are not additive across component interfaces, and no banked direct-sum theorem bridges these sub-circuit boundaries.
The register records no prior-art position.
For everyone — the takeaway
What this means
Optimizing pieces of a circuit in isolation does not guarantee a smaller complete system. Even though more than 91% of SHA-256 has verified modular proofs, the missing sections and boundary interactions stop these local counts from lowering the total cost. The catalog remains a verified reference baseline, but lowering SHA-256 row counts requires analyzing the full circuit across component boundaries rather than chaining separate certificates.
Register references
- Entry ML-067
- Receipt artifact:
zkgolf-decomp/REDEPLOY-CERTIFICATION.md
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.