Data Dependencies in Field Multiplication

Counting field operations can miss an important part of cryptographic performance: data dependencies. We split serial multiplication chains into two independent chains, speeding up batch inversion and the wallet-scanning workloads that depend on it.

Two multiplication schedules on one cycle grid. A single dependent chain steps through stages S1, S2 and S3 four times in sequence, drawn faded and still running past a pink finish line; below it two independent chains interleave and finish before that line, with 35% less time set in the field beyond it. — The same four products under two schedules. One dependent chain leaves most of the multiplier idle; two independent chains interleave and clear the pipeline sooner. On the Apple core we measured, two chains cut field-multiplication time by about 35%.

Cryptographic optimization often starts by reducing the number of field or curve operations. That count matters, but it does not determine runtime by itself. Modern CPUs can overlap independent instructions, so performance also depends on which operations must wait for earlier results.

For multiplication-heavy code, the important distinction is between latency and throughput.

Latency is not throughput

Suppose a loop repeatedly updates one accumulator:

The multiplication producing cannot begin until exists. The whole loop runs at the multiplication's dependency latency: the time from starting one multiplication until its result is ready for the next.

Now split the same number of multiplications between two accumulators:

The next update of still depends on the previous , and likewise for , but the two chains do not depend on each other. A superscalar CPU can work on both at once. If the multiplier can accept new independent work before an earlier result is ready, the loop moves from latency toward throughput.

This does not make a field multiplication itself cheaper. It fills multiplier issue slots that the dependency chain would otherwise leave unused. This only helps when the computation can be reorganized into independent chains without adding enough work to erase the gain.

Measuring the gap

We added a simple benchmark that performs 1,024 field multiplications per iteration. The operation count never changes; only the number of independent accumulator chains varies.

With our Apple AArch64 assembly implementation, the results were:

Accumulator chains	Pallas base field (`Fp`)	Vesta base field (`Fq`)
1 dependent chain	10.438 µs	10.423 µs
2 independent chains	6.764 µs	6.776 µs
4 independent chains	6.854 µs	6.862 µs
8 independent chains	6.899 µs	6.924 µs

Two chains finish the same 1,024 multiplications about 35% sooner, corresponding to roughly 1.54× as many multiplications per unit time. Four and eight chains are slightly slower than two. On this core, two chains are enough to expose the available multiplication throughput; making the computation wider does not help.

This microbenchmark shows the opportunity. The benefit to a real workload depends on how much of its time is spent in long multiplication chains and how much extra work is required to split them.

The serial chains inside batch inversion

Here's the simplest place we use this optimization. A field inversion is much more expensive than a multiplication. Montgomery's trick amortizes that cost across a batch. Given nonzero values , we first construct prefix products:

We invert only the final product, then walk backward to recover each . This replaces expensive inversions with one inversion and roughly multiplications.

But both multiplication walks are serial. Every prefix product waits for the one before it, and the backward accumulator has the same dependency. The algorithm removes most of the inversions, but leaves two long, latency-bound multiplication passes.

We can instead assign even-indexed values to one chain and odd-indexed values to another. Let their final products be and . Join them only around the shared inversion:

The two forward walks are independent. So are the two backward walks. The join costs three extra multiplications: one for and two to recover the inverse seeds. Our implementation starts both prefix chains at 1, just as its single-chain loop does, so splitting does not shorten the walks and the join is the only added work.

For large batches, the three multiplications cost far less than the overlap saves. For small batches the chains are too short for the overlap to cover the join, so our general batch-inversion paths keep the single-chain implementation below 32 elements.

This makes batch inversion around 21% faster in our benchmarks.

Where wallet scanning pays for it

As described in our Eisenstein post, we use batch inversion in all of the affine-affine point additions. In that ladder, batch inversion accounts for a meaningful part of the work. A batch of 100 points does not run one inversion at the end; it runs shared inversions throughout roughly 200 serial ladder stages. Those repeated batch inversions account for enough of the ladder that the improvement is visible in the full wallet benchmark.

Combining the Eisenstein ladder with two-lane batch inversion gives a further 6–10% improvement in trial decryption, depending on batch size and architecture. That gain compounds with the 16–20% improvement measured for the Eisenstein ladder over the earlier scanner.

This optimization does not change the higher-level algorithm, so it composes with many other techniques. Exposing independent work gives both LLVM and the processor more freedom to schedule multiplications efficiently. We'll say more in future posts, but the same principle matters to several of our results, including our 20× faster Sinsemilla hashing.