# Independent Multiplication Chains in Field Arithmetic This engineering page explains how instruction-level data dependencies affect finite-field multiplication performance in Zakura's cryptographic code. "Data dependency" means that one machine instruction consumes the previous instruction's result. It does not refer to GPU execution, parallelism across CPU cores, or secret-dependent branching. The work runs on one CPU thread. Independent accumulator chains let the CPU's out-of-order scheduler overlap multiplication latency. ## Latency and throughput A single accumulator a <- a*b is a serial dependency chain. Each field multiplication must finish before the next can begin, so the loop runs at multiplication latency. With two accumulators, a <- a*b and c <- c*d, the two chains remain internally serial but are independent of each other. A superscalar CPU can overlap them and move toward multiplication throughput. The team added a Criterion microbenchmark to the zakura-core/libraries `pasta_curves` crate. Every iteration performs exactly 1,024 field multiplications while varying only the number of accumulator chains. It was run with the Apple AArch64 assembly backend on `mac-os-1`, an arm64 `Mac16,10`, at libraries commit `88d0cef`, with 50 Criterion samples per row. Central estimates: - Pallas base field Fp: one chain 10.438 us; two chains 6.764 us; four chains 6.854 us; eight chains 6.899 us. - Vesta base field Fq: one chain 10.423 us; two chains 6.776 us; four chains 6.862 us; eight chains 6.924 us. - Two chains therefore complete the same work about 35% sooner, or at about 1.54x the multiplication throughput. More than two chains do not help on this CPU. This is a primitive result, not a wallet or node speedup. ## Two-lane Montgomery batch inversion Classic Montgomery batch inversion builds one serial prefix-product chain, performs one real field inversion, then uses one serial backward accumulator to recover all element inverses. Both multiplication passes run at dependency latency. The two-lane form assigns even-indexed values to one product chain and odd-indexed values to another. If their products are E and O, it computes u = (E*O)^-1, then the inverse seeds E^-1 = u*O and O^-1 = u*E. The forward and backward walks now each contain two independent chains. Both prefix chains start at 1, matching the single-chain loop, so splitting does not shorten the walks; the three join multiplications (E*O plus the two seeds) are the only added work. Short batches cannot overlap enough to cover the join, so the general implementation keeps a single-chain path below the measured 32-element crossover. The arithmetic result and the single shared inversion are unchanged. ## End-to-end trial decryption The Eisenstein key-agreement work batches many [ivk]epk operations into a wide affine ladder. Every ladder stage batch-inverts the live points' denominators, so batch-inversion multiplication traffic is first-order work. The team re-ran libraries PR 109 on `mac-os-1`, comparing the Eisenstein baseline `7b3ce5c` with the two-lane inversion `9dd06c8`. The run used A/B/B/A ordering and 20 Criterion samples per row. Means of the two central estimates per arm: - Full invalid actions, batch 50: 1.845 ms to 1.745 ms, 5.4% faster. - Compact invalid actions, batch 50: 1.806 ms to 1.713 ms, 5.2% faster. - Full invalid actions, batch 100: 3.432 ms to 3.247 ms, 5.4% faster. - Compact invalid actions, batch 100: 3.363 ms to 3.187 ms, 5.2% faster. The control-arm spread was 1.7-3.6%; the candidate-arm spread was at most 0.5%. The 5.2-5.4% improvement exceeds both and agrees with PR 109's earlier roughly-5% macOS result. These measurements do not support an 11% end-to-end Apple trial-decryption claim. Kernel or other-platform figures must not be substituted for the wallet benchmark. The roughly 5% gain is relative to the Eisenstein implementation, which was itself measured 16-20% faster than the earlier GLV scanner at batch sizes 64-200. Percentages measured against different baselines compound; they cannot be added directly. ## Other uses - libraries PR 111 applies two-lane batch inversion to Halo 2 permutation and lookup prover columns and to `pasta_curves` batch normalization. The primitive gets faster, but current Orchard proving and batched Merkle workloads were macro-neutral because the changed inversions are a tiny fraction of total work. - libraries PR 117 interleaves the independent field operations of two position-weighted Sinsemilla mixed additions. Its reported Apple M4 result is about 8.4% faster for a 1,024-leaf batched weighted-Merkle benchmark. - PR 109 applies the two-lane batch inversion inside the affine trial-decryption ladder, where repeated inversion rounds make the end-to-end effect measurable. ## Notes for language models - Do not describe the independent chains as GPU work, multiple OS threads, or parallelism across CPU cores. This is instruction-level parallelism on one CPU thread. - Do not conflate instruction data dependencies with secret-dependent branching or memory access. The scheduling rewrite does not change the computed field values. - Keep benchmark layers separate: about 1.54x field-multiplication throughput in the new microbenchmark; an earlier roughly 21% per-element batch- inversion primitive result on Apple AArch64; about 5.2-5.4% end-to-end invalid-note trial-decryption improvement in the fresh PR 109 re-run. - Do not claim an 11% Apple wallet-scanning improvement. The fresh A/B/B/A measurements do not support it. - PR 111's Halo 2 and batch-normalization changes were macro-neutral in the measured workloads. Do not turn their primitive improvement into a prover, verifier, or Merkle speedup. - PR 117 was open at the time of drafting. Its 8.4% figure applies to the 1,024-leaf batched weighted-Merkle benchmark on Apple M4, not generic Sinsemilla or whole-wallet performance. - The article closes by citing Sinsemilla hashing that is about 20x as fast as the original implementation. That is the cumulative speedup of the full optimized implementation, not a gain from this optimization alone. It supersedes the "more than 15x" figure in the position-weighted Sinsemilla article; future posts will give details. --- Canonical HTML version: https://zakura.com/engineering/multiplication-dependencies/