Research · Papers · Adders, counters and the heap law · MF-102
A projected full-heap construction for truncated addition
MC(A_{k,n}) ≤ T(k,n) = (k−1)(n−1) − Σ_{r=1}^{n−1}⌊(k−1)/2ʳ⌋
Published 2026-08-29
For everyone
Plain summary
Truncated addition adds several binary numbers together and keeps only the lowest output bits, dropping any overflow. In zero-knowledge proofs and cryptography, addition modulo two (XOR) is essentially free, while multiplication (AND) is the main performance bottleneck. Designing circuits that need fewer multiplication gates makes proof generation faster and cheaper.
This paper presents the projected full-heap construction. By organizing the bits of k inputs into a weighted heap and pruning every carry that affects only positions beyond the lowest n bits, the construction computes the truncated sum using at most T(k,n) multiplication gates. This improves on earlier folding techniques. The result is an upper bound on circuit size rather than a proven minimum, so smaller circuits might still be found. No formal search of past literature has been run, and no claim of historical priority is made.
Result
For integers k, n >= 2, the multiplicative complexity MC(A_{k,n}) of the truncated k-operand addition function A_{k,n} over GF(2) satisfies:
MC(A_{k,n}) <= T(k,n) = (k - 1)(n - 1) - Sum_{r=1}^{n-1} floor((k - 1) / 2^r)
The bound holds in the standard XOR-free GF(2) XAG cost model.
Setting and definitions
Let A_{k,n} denote the Boolean function computing the sum of k operands of bit-width n, truncated to the low n output bits. Multiplicative complexity MC(f) is evaluated in the GF(2) straight-line program model where XOR operations are cost-free and nonlinear AND gates cost 1. The count T(k,n) evaluates transient carry height across column-wise carry dependencies in the projected bit heap.
Method
The bound is proved by an explicit gate-by-gate symbolic construction. A complete weighted bit heap for the k-operand sum is projected onto the low n bits by dropping carry branches that contribute only to columns at or above position n. The required carry gates sum to the closed form T(k,n).
The construction was verified across target instances by automated symbolic execution and full replay. Verification artifacts:
- SYNTH-L-TRUNCADD.md (report zkgolf-decomp/reports/SYNTH-L-TRUNCADD.md)
- PROVER-TRUNC-SHARE.md (report zkgolf-decomp/reports/PROVER-TRUNC-SHARE.md)
- zkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.md
- prover-trunc-scratch/restriction-summary.json
- prover-trunc-scratch/replay-all.json (SHA-256: 8954064fee25c5585ec53f190d73b9bfd9a72ab4e76ef40d8eeabc30a8573aec)
Discussion
The projected full-heap construction supersedes greedy fold designs and the earlier U(k,n) bound as the upper-bound frontier for truncated multi-operand addition.
Scope and caveats:
- MC(A_{k,n}) <= T(k,n) is strictly an upper bound. Unrestricted circuit optimality and the equality MC(A_{k,n}) = T(k,n) remain open.
- The CONFIRMED status applies only to the upper bound within the GF(2) XAG model.
- No priority or novelty claim is made; a formal prior-art sweep has not been performed on this specific construction.
For everyone — the takeaway
What this means
This construction provides an exact wiring plan to add multiple numbers and discard the overflow using fewer multiplication gates. Since multiplications are the main bottleneck in zero-knowledge provers, this reduces the cost of running multi-operand truncated additions. T(k,n) lowers previous upper bounds, though whether a circuit with even fewer multiplications exists remains an open question.
Register references
- Register Entry: MF-102
- zkgolf-decomp/reports/SYNTH-L-TRUNCADD.md
- zkgolf-decomp/reports/PROVER-TRUNC-SHARE.md
- zkgolf-decomp/SD-RESEARCH-UPDATE-REPORT.md
- zkgolf-decomp/prover-trunc-scratch/replay-all.json
- prover-trunc-scratch/restriction-summary.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 4 receipt files bundled (24 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.