Research · Papers · Adders, counters and the heap law · MF-103
Injected carry is exactly the flagship one-gate gap
MC(J_m) = MC(A_{3,m+1}) − 1; J₃₂ = Add32x3Canon33 ∈ {61,62}
Published 2026-08-29
For everyone
Plain summary
Adding three binary numbers is a basic operation in cryptography. In zero-knowledge proof systems, efficiency depends on multiplicative complexity: the number of AND gates (multiplications) needed to compute a circuit over the two-element field GF(2), assuming XOR gates (additions) are free.
This entry proves an exact structural identity: an m-bit three-operand addition with an injected carry, J_m, always requires exactly one less AND gate than standard (m+1)-bit three-operand addition, A_{3,m+1}. For 32-bit words, J_32 locks directly to canonical 33-bit addition: whether J_32 requires 61 or 62 multiplications corresponds directly to the exact multiplicative complexity of A_{3,33}. No 61-gate circuit is in custody, no row savings are claimed, and no formal prior-art sweep has been conducted.
Result
For all integer bit-widths m ≥ 2:
MC(J_m) = MC(A_{3,m+1}) − 1
where MC denotes multiplicative complexity in the GF(2) XOR-free XAG cost model, A_{3,k} is standard k-bit three-operand addition, and J_m is m-bit three-operand addition with an injected carry parameter.
At m = 32:
J_32 = Add32x3Canon33 ∈ {61, 62}
The remaining one-gate uncertainty in the multiplicative complexity of Add32x3Canon33 equals the open one-gate gap in MC(A_{3,33}).
Setting and definitions
The cost model is multiplicative complexity over GF(2), defined as the minimum number of AND nodes in an XOR-AND graph (XAG) with zero-cost linear XOR operations.
- A_{3,k}: Boolean multi-output function computing the sum of three k-bit integers x, y, z over GF(2), returning the full sum with output carry bits.
- J_m: Boolean multi-output function computing the three-operand addition of three m-bit integers with a carry parameter injected into the least significant bit.
- Add32x3Canon33: The 32-bit injected-carry three-operand adder instantiated in the record SHA-256 arithmetic decomposition BOM.
- MC(f): Multiplicative complexity of a multi-output Boolean function f over GF(2).
Method
The identity MC(J_m) = MC(A_{3,m+1}) − 1 and parameter localization were derived by symbolic proof. Structural decomposition in the prover circuit pipeline verified J_32 = Add32x3Canon33.
Small-cell instances were checked and audited via certificate replays:
zkgolf-decomp/reports/PROVER-ICA-PIVOT.mdzkgolf-decomp/reports/SYNTH-H-LOWERBOUND.mdzkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.mdRECORD-BOM.md- Replay and audit logs in
prover-ica-scratch/t-pivot-experiments.json(SHA-25669eca1a49cfa6e0d97112c06d7b959dfb0c942d247842b0f868d9caf87994eae) - Graded audit output in
prover-ica-scratch/pivot-graded-audit.json(SHA-256ef235257b982547f9f570a78f6b0227f82cff94a6ca5fd86c20017bc71efec3a) - Clean replay certificate
prover-ica-scratch/m3-k4.clean.replay.json
Discussion
This result ties the theoretical lower-bound gap of three-operand addition directly to thirty concrete SHA-256 adder blocks.
Registered limits and caveats:
- Circuit custody: A 61-product circuit for J_32 is not in custody. The identity shows J_32 ∈ {61, 62} without providing a constructive 61-gate circuit.
- Row savings: This identity claims no constraint or row savings on its own.
- Compilation prerequisite: Downstream 30-row gains in proof systems require one-for-one ordered identity-C compilation, which this theorem does not establish.
- Prior art and novelty: No claim of priority or novelty is made; a formal prior-art sweep has not been run for this equivalence.
The identity unifies two previously separate questions—the exact multiplicative complexity of injected-carry components and that of standard 33-bit three-operand addition—into a single mathematical fork.
For everyone — the takeaway
What this means
In zero-knowledge proofs, every non-linear gate adds proving cost. Knowing the lowest possible number of multiplications for standard arithmetic helps pin down the ultimate speed limits of cryptographic provers.
This result shows that whether an injected-carry 32-bit adder takes 61 or 62 multiplications corresponds directly to the multiplicative complexity of a standard 33-bit adder. Unifying these questions focuses future synthesis and lower-bound work on a single target across thirty adder blocks in SHA-256 pipelines.
Register references
- Register Entry:
MF-103 - Reports:
zkgolf-decomp/reports/PROVER-ICA-PIVOT.mdzkgolf-decomp/reports/SYNTH-H-LOWERBOUND.mdzkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.mdRECORD-BOM.md- Receipts and Replays:
zkgolf-decomp/prover-ica-scratch/t-pivot-experiments.json(SHA-25669eca1a49cfa6e0d97112c06d7b959dfb0c942d247842b0f868d9caf87994eae)zkgolf-decomp/prover-ica-scratch/pivot-graded-audit.json(SHA-256ef235257b982547f9f570a78f6b0227f82cff94a6ca5fd86c20017bc71efec3a)prover-ica-scratch/m3-k4.clean.replay.json
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 5 receipt files bundled (26 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.