Research · Papers · Adders, counters and the heap law · MF-104
Verified width-three constructions for nine and ten operands
MC(A_{9,3}) ≤ 10 and MC(A_{10,3}) ≤ 12; both are replayed uppers, not exact values
Published 2026-08-29
For everyone
Plain summary
This entry provides verified circuit designs for truncated addition, where several single-bit inputs are added together and only the three lowest-order bits of the sum are kept. In zero-knowledge proofs and related cryptographic systems, circuit cost comes almost entirely from multiplications (AND gates), while additions (XOR gates) are treated as free.
The new designs compute the three-bit sum of nine inputs using 10 multiplications, and the sum of ten inputs using 12 multiplications. Both designs were tested against their mathematical specifications across their entire input domains: all 2^27 combinations for the nine-input circuit and all 2^30 combinations for the ten-input circuit, with zero mismatches. These numbers are upper bounds established by concrete, working circuits. They are not proved mathematical minimums, and no claim of novelty outside this research program is made because an external prior-art search has not been conducted.
Result
In the GF(2) XOR-AND graph (XAG) cost model:
MC(A_{9,3}) ≤ 10
MC(A_{10,3}) ≤ 12
Both values are replayed upper bounds established by explicit constructions, not exact complexity values.
Setting and definitions
Let A_{n,w} denote the truncated addition function taking n single-bit operands and returning the w lowest-order bits of their integer sum over GF(2). Multiplicative complexity MC(f) is the minimum number of two-input conjunctions (AND gates) needed to evaluate the Boolean function f in an XOR-AND graph over GF(2), with XOR and NOT gates treated as zero cost.
Method
Bounds were established through projected heap synthesis and verified by full-domain exhaustive evaluation.
The verification harness replayed the synthesized circuits across all 2^27 inputs for A_{9,3} and all 2^30 inputs for A_{10,3}, checking every output bit against the reference integer addition specification and logging zero mismatches.
Artifacts and verification receipts in the register:
- Synthesis report:
zkgolf-decomp/reports/PROVER-TRUNC-SHARE.md - Research update report:
zkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.md - Synthesis log:
SYNTH-L-TRUNCADD.md - Restriction summary:
prover-trunc-scratch/restriction-summary.json - Full-domain replay receipt:
zkgolf-decomp/prover-trunc-scratch/replay-all.json(SHA-2568954064fee25c5585ec53f190d73b9bfd9a72ab4e76ef40d8eeabc30a8573aec) - Component SHA-256 for A_{9,3}:
c4acc332867495b621f88506967c8536e9c5eaae13466e9f0a5a0b4a6b87e923 - Component SHA-256 for A_{10,3}:
a40c2668940cc50975c193839dc3051e5de2be5779811ec2de7c132621e34130
The register records the component hashes above from the project reports without printing separate component pathnames.
Discussion
These constructions supersede prior internal bounds of 11 products for A_{9,3} and 13 products for A_{10,3}.
The scope is strictly an upper bound on circuit complexity. The register makes no claim that MC(A_{9,3}) = 10 or MC(A_{10,3}) = 12; lower bounds remain open.
No claim of world-first priority, record status, or novelty outside this program is made, as an external literature sweep has not run.
For everyone — the takeaway
What this means
Multiplications are the main performance bottleneck in zero-knowledge arithmetic circuits. Reducing the multiplication count of common operations lowers the real compute cost of these proof systems.
These results yield verified circuits for nine- and ten-operand truncated addition. Because every input combination was checked exhaustively against standard arithmetic, engineers can drop these 10-product and 12-product circuits into larger systems right away. Whether smaller circuits exist remains an open question.
Register references
- Register Entry: MF-104 (Evidence tier: FR.
zkgolf-decomp/reports/PROVER-TRUNC-SHARE.mdzkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.mdSYNTH-L-TRUNCADD.mdprover-trunc-scratch/restriction-summary.jsonzkgolf-decomp/prover-trunc-scratch/replay-all.json(SHA-2568954064fee25c5585ec53f190d73b9bfd9a72ab4e76ef40d8eeabc30a8573aec)
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 3 receipt files bundled (14 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.