Research · Papers · Adders, counters and the heap law · MF-131
Classification of One-Word XOR-Mask Transports for Four-Word Addition
Affine transport exists iff 2^(n-2)|M and 2^(n-2)|Δ; componentwise affine correction exists iff 2^(n-2)|M and Δ ≡ M (mod 2^(n-1)).
Published 2026-09-04
For everyone
Plain summary
Adding four fixed-width binary numbers requires expensive logic gates to resolve carries. In zero-knowledge circuits, linear operations like XOR cost nothing, so circuit designers look for ways to repair an existing addition result after flipping bits in one input word and shifting a constant. This repair rule is called an affine transport.
This work classifies every case where such a repair is possible for four-word addition. For words of three or more bits, an affine transport exists if and only if both the bit mask and the constant shift are multiples of one-fourth the maximum word value. Only four mask values qualify. For two-bit words, every combination of mask and shift can be repaired for free. The proof applies strictly to single-word modifications and does not cover changes across multiple inputs or repairs that introduce nonlinear gates.
Result
Let n ≥ 3 be the word width, and let q = 2^(n-2). For four-word addition modulo 2^n with a fixed literal, an XOR mask M ∈ {0, ..., 2^n - 1} applied to one input word, and an integer literal shift Δ:
Under the public-output affine family in the GF(2) XAG (XOR-free) cost model:
- A black-box affine transport over the primary inputs and the public source-output word exists if and only if q | M and q | Δ.
- A componentwise affine correction exists if and only if q | M and Δ ≡ M (mod 2^(n-1)).
- The valid masks permitting correction are precisely M ∈ {0, q, 2q, 3q}.
- At word width n = 2, every pair (M, Δ) admits an affine transport.
Setting and definitions
The problem operates in the GF(2) XOR-and-inverter graph (XAG) metric, where XOR and NOT gates carry zero cost.
- Word width and modulo: Words are elements of Z / 2^n Z represented as n-bit vectors. The base circuit computes the modular sum of four n-bit words, including a fixed literal constant.
- One-word XOR masking: A selected primary input word x is replaced by x ⊕ M, where M is an n-bit mask and ⊕ denotes bitwise XOR.
- Literal modification: The constant addition term shifts by an integer value Δ modulo 2^n.
- Black-box affine transport: An affine map over GF(2) that recovers the modified sum from the primary inputs and the source output word without adding multiplicative (AND) nodes.
- Componentwise affine correction: A transport where each output bit is reconstructed by an affine function of the matching source bit and input bits.
Method
The classification was established by analyzing carry chain propagation under bitwise XOR shears using exact synthesis. Proof artifacts and verification scripts are recorded in three receipts:
zkgolf-decomp/free-04-scratch/mask-shear.receipt.json(SHA-2566fc0ecd39ff42b1ce33a12629ab3ce8ae1d2cbb2d1016bb0dca624d873ca99f8),zkgolf-decomp/free-04-scratch/output-mixing.receipt.json(SHA-256f3dbd73e460a5235ef54ab17b5ed0db8db798ce997dd6671abc2fa53d295f1cc),zkgolf-decomp/free-04-scratch/mask-shear.verify.json(SHA-25639adaf19bf5c586f98f0f086839d80b55ccd7ef018685fedabdb361cf5bd5a3d).
These artifacts verify the necessity and sufficiency of q | M and q | Δ for n ≥ 3, the congruence Δ ≡ M (mod 2^(n-1)) for componentwise corrections, and the unconstrained solvability of the n = 2 case. The result holds evidence tier P + FC + FR and is validated in zkgolf-decomp/FREE-04.md and zkgolf-decomp/FREE-VERIFY.md.
Discussion
The theorem delineates the boundary of zero-cost linear reuse for four-word adders subject to single-input bit shears and literal shifts.
Scope boundaries:
- Single-word focus: Applies only to single-word input masking. Multi-word affine preprocessing remains unclassified.
- Affine transport restriction: Covers only linear transport maps; it does not address architectures using hidden nonlinear catalysts or auxiliary non-free gates.
- Complexity bounds: Classifies the existence of transports within the affine family without asserting fixed-constant lower bounds.
- Dimensional transition: Establishes a structural split between n = 2 (all pairs admit transports) and n ≥ 3 (restricted to the four multiples of 2^(n-2)).
For everyone — the takeaway
What this means
You can only repair a modified four-word addition for free if the changes are confined to the top two bit positions. For any word width of three bits or more, exactly four mask patterns allow you to reuse the original addition output without paying for new nonlinear gates. Any bit flip lower down the word breaks the carry chain beyond what linear logic can fix.
Register references
- Entry ID: MF-131
- Sources:
zkgolf-decomp/FREE-04.md,zkgolf-decomp/FREE-VERIFY.md - Receipts:
zkgolf-decomp/free-04-scratch/mask-shear.receipt.json(SHA-2566fc0ecd39ff42b1ce33a12629ab3ce8ae1d2cbb2d1016bb0dca624d873ca99f8)zkgolf-decomp/free-04-scratch/output-mixing.receipt.json(SHA-256f3dbd73e460a5235ef54ab17b5ed0db8db798ce997dd6671abc2fa53d295f1cc)zkgolf-decomp/free-04-scratch/mask-shear.verify.json(SHA-25639adaf19bf5c586f98f0f086839d80b55ccd7ef018685fedabdb361cf5bd5a3d)
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 5 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.