Batch Affine Ladders with Eisenstein Recoding

Ironwood, the shielded pool introduced by the NU6.3 upgrade, keeps Orchard's underlying cryptography, and with it Orchard's scanning workload. A wallet discovers its incoming funds by trial decryption, and the expensive step of each trial is key agreement between two values:

Here epk is an ephemeral public key that arrives with a shielded output and varies for every output. ivk is the wallet's incoming viewing key, and it does not change. A wallet might use the same ivk to multiply millions of unrelated points over a period of years.

That is a strange scalar-multiplication workload. Textbook treatments of elliptic-curve multiplication ask how quickly we can compute for one arbitrary scalar and one arbitrary point. Scanning instead hands us a large batch,

writing for the viewing key and for the incoming points, in which every point changes but the scalar is identical.

The curve involved is also unusually helpful. It is Pallas,

over a roughly 255-bit prime field. It has -invariant zero and a cheap order-three endomorphism: multiplying the -coordinate by a suitable cube root of unity gives another point on the curve. That endomorphism is what makes GLV scalar multiplication possible.

But once we are already using GLV, can we exploit the fact that scanning wants hundreds of multiplications by the same scalar at once?

The answer is yes, by moving much more of the computation into affine coordinates and sharing inversions throughout the batch rather than only at the end. Instead of the traditional GLV recoding, we use Eisenstein integer recoding to reduce the number of serial addition stages and ensure that an active column contains only one addition.

In our end-to-end batch trial-decryption benchmarks, the approach we've found comes in 16-20% faster than the current implementation at batch sizes from 64 through 200 outputs.

The usual way to batch scalar multiplications

Suppose we have 128 ephemeral keys and want to compute for all of them. Nothing stops us from running 128 ordinary scalar multiplications independently, and typically each one stays in Jacobian or another projective coordinate system during its main loop.

Projective coordinates exist largely to avoid field inversion.

In affine coordinates , adding or doubling points requires division. For Pallas, a generic affine addition costs approximately

and an affine doubling approximately

where , , and denote a field multiplication, squaring, and inversion. An inversion is vastly more expensive than a multiplication, so paying one at every step would normally be disastrous.

Projective coordinates carry an extra coordinate instead. Each operation costs more multiplications, with representative Jacobian costs around for a doubling and for a mixed addition, but almost every inversion disappears.

At the end, the 128 answers are converted back to affine coordinates together. Montgomery's batch-inversion trick computes inverses using one real inversion and roughly multiplications, so the whole batch pays for only a single true inversion.

GLV already makes each multiplication shorter

Before any batching, there is an important Pallas-specific optimization in play. A straightforward multiplication by a roughly 255-bit scalar takes about 254 point doublings and, for a random scalar, about 127 additions. But Pallas has that cheap endomorphism,

which multiplies the -coordinate by a cube root of unity and acts on the group like multiplication by a known scalar . GLV uses it to write

where and are each only about 127 bits. Then

The two half-sized multiplications share their doubling chain. Instead of roughly 254 doublings, we need roughly 127.

This is not a proposed optimization. pasta_curves already does it, and GLV does not depend on the scalar being fixed. But the fixed scalar makes it especially convenient: recent Orchard code decomposes and recodes the viewing key once, reuses that result across the whole batch, and builds the GLV tables for the varying ephemeral keys with one shared normalization.

Share the inversions inside the multiplication

Montgomery's trick is not limited to final normalization. Given nonzero field elements, it computes all inverses for one real inversion plus roughly three multiplications per element, so with a large enough batch the effective cost of each inverse approaches

That suggests a different strategy. Instead of maintaining 128 independent projective accumulators, maintain 128 affine accumulators, and run the multiplications in lockstep, as one wide ladder.

Suppose the schedule's next operation is a doubling. Every lane needs

and each affine doubling produces exactly one denominator. Collect all 128 denominators, batch-invert them together, and finish all 128 doublings. When the schedule calls for an addition,

do the same thing again. In the large-batch limit, where each shared inverse costs about , the affine costs from earlier approach roughly

for doubling and

for addition. Our implementation uses a fast variable-time inversion that we measure at about 77 multiplication-equivalents on our test platform, so at 128 lanes the leftover term adds only about to each figure. Against the Jacobian costs above, the affine doubling is roughly break-even or slightly worse, but the affine addition becomes substantially cheaper; over the whole ladder, the balance favors affine arithmetic once the batch is wide enough. (The rare scalar schedules that would produce a zero affine denominator are detected from the viewing key alone and fall back to the ordinary ladder.)

The catch: inversion rounds are sequential

Batch inversion only combines inversions that are ready at the same time.

If every lane needs one doubling, those 128 inversions share happily. But if the result of that doubling must then be added to another point, the addition's denominator cannot even be computed until the doubling has finished. That takes another batch-inversion round. And if another addition follows, another round again.

Inside one scalar multiplication, the next division depends on the result of the previous one. The relevant cost is therefore not just the total field arithmetic. It is also the number of times the whole batch must stop, collect denominators, invert, and continue.

This is where the scalar representation starts to matter in a new way.

Ordinary GLV gives us two digit streams

After GLV, implementations normally treat and as two independent integers and recode each into a sparse signed representation such as wNAF. With the width-4 representation currently used by pasta_curves, each half has a nonzero digit about once every five positions. Across two roughly 127-bit expansions, that means around 51 additions for a random scalar.

Because the viewing key is fixed, the digit pattern is known in advance and identical for every lane, so there is no synchronization problem between lanes. But there is still serial work inside the schedule. Depending on the digits, a column can look like

or

or occasionally

with a multiple of and a multiple of . Every point addition in a column is another sequential batch-inversion round, so if we take this deployed two-wNAF schedule and turn it directly into a batch-affine ladder, the rough count is one doubling round per column plus one round per addition:

The exact number depends on the particular viewing key, but that is the right scale.

This exposes an unusual optimization target. We no longer want a scalar representation that merely minimizes generic point-operation cost. We want one that minimizes the number of serial addition stages.

Recode the two GLV halves together

The two GLV components are usually treated as separate integers, but algebraically they belong together.

The Pallas endomorphism's scalar satisfies

That is the same relation satisfied by an Eisenstein integer . So instead of thinking of as two unrelated integers, regard

as the curve-side realization of the single Eisenstein integer

in the ring . On the curve, is realized by the endomorphism .

We can now recode directly, as a joint width-3 NAF over the Eisenstein integers. The algorithm still looks like wNAF. If is divisible by 2, output zero and divide by 2. Otherwise choose a small Eisenstein digit congruent to modulo 8, subtract it, and then divide by 2.

The important difference is that the digits now have two components. One digit can specify a combination of and at the same time, so there is no longer any such thing as a column with two independent GLV additions.

Why the density improves

The arithmetic of the Eisenstein integers is convenient. The prime 2 remains inert in , so there are four residue classes modulo 2. Only one is divisible by 2. A random Eisenstein integer is therefore "even" with probability , rather than as for an ordinary integer.

At first this sounds worse: there are fewer free zero positions.

The advantage is that a nonzero digit encodes both GLV dimensions at once. Modulo 8 there are

classes not divisible by 2. Once the appropriate nonzero digit is subtracted, the remainder is divisible by 8. That forces the next two binary positions to be zero.

After those two forced zeros, each subsequent position has a chance of also being zero. The expected distance between active digits is therefore

Across the roughly 127-column expansion, with a short bounded tail in edge cases, that gives about 38–39 additions rather than about 51. These are averages over random scalars. For Ironwood scanning the scalar is fixed, so the number that actually matters is the exact expansion of one particular viewing key, and it can be computed once.

Fewer serial rounds

For the batch-affine ladder, the serial-round savings track the addition-count savings directly: roughly 178 rounds become roughly

The additional advantage is structural: an active column now contains exactly one addition, giving every active column the uniform shape exploited below.

The Eisenstein recoding is not what makes the lanes synchronize. The fixed viewing key already gives us a common schedule. What the recoding does is make that common schedule shorter and more regular in precisely the dimension that batched affine arithmetic pays for.

The table-size story is less magical than it first appears

There is another attractive property of the Eisenstein integers. They have six units:

Those symmetries divide the 48 residue classes not divisible by 2 into eight groups of six. Algebraically, that suggests that only eight representative table points are needed.

But the curve operations are not all free. Negating a point is essentially free: it just changes the sign of . Multiplication by , however, is the endomorphism , and its field multiplication for the -coordinate is real work when it sits inside the hot loop.

So there is a tradeoff. We can store only eight representatives and pay for endomorphism rotations as digits are used, or we can store the rotations too. Our implementation does the latter, and cheaply: the three rotations of a representative differ only in their -coordinate, so each table stores 24 -coordinates alongside 8 shared -coordinates, 32 field elements or 1 KiB per input.

Measured as a generic scalar-multiplication trick, then, the Eisenstein recoding is a useful but fairly modest optimization: a handful of point additions, offset somewhat by the larger table and its construction cost. Its real value here is the shape it gives the schedule.

A convenient formula for active columns

Once every active column has the form

we can compute it with a fused formula due to Eisenträger, Lauter, and Montgomery, developed precisely to speed up elliptic-curve scalar multiplication in affine coordinates. Reordering as avoids the doubling and saves a squaring, and the formula never computes the intermediate point's -coordinate, saving a multiplication: approximately

per active column compared with a separate affine doubling and addition.

There is an important limitation: it does not reduce the number of inversion rounds. The formula's second denominator depends on the result of its first stage, so an active column still requires two sequential batch inversions. Those second stages are exactly the extra 38 rounds in the count above; the fused formula saves arithmetic inside the rounds rather than removing them.

So is it actually faster?

Yes. We benchmarked it, end to end, as batch trial decryption against the current GLV implementation. The full change comes in between 16 and 20% faster at batch sizes from 64 through 200 outputs, and between 8.8 and 20.5% faster across all tested sizes from 10 through 200.