Avoiding Montgomery Reductions

Much of the cost of Zcash's cryptography is arithmetic in finite fields, particularly multiplications, and nearly half the cost of each multiplication is a single operation called Montgomery reduction.

The reduction is a normalization step. The Pasta fields used by Orchard and halo2 keep field elements in Montgomery form; multiplying two of them produces a double-width value, and the reduction is what brings that value back into the form the next operation expects.

Reductions like this do not always have to happen right away. A product only needs to be normalized when something actually consumes it in normalized form. If several products are only going to be added together, they can stay wide and unreduced and share one reduction at the end. If a formula needs a difference of two products, the two multiplications can be fused into a single operation with a single reduction.

We have been applying this idea in several places in Zakura, some inside halo2 and some much lower down, in elliptic-curve arithmetic. Because the improvements target different operations, they combine.

Montgomery representation

The Pasta fields use Montgomery representation to make arithmetic modulo a large prime efficient.

Instead of storing a field element directly, we represent it as

where is a convenient power of two.

Suppose we multiply two represented field elements. Before reduction, the integer product corresponds to . But our field representation is supposed to contain one factor of , not two. A Montgomery reduction removes the extra factor:

So an ordinary field multiplication is really two substantial pieces of work: compute a double-width product, then reduce it back into the field representation.

Usually that is what we want, since the result of one multiplication often feeds straight into another. But consider a sum of products:

The straightforward implementation reduces each multiplication independently:

If all of those products are only going to be added together, this is unnecessary. We can instead keep the double-width products around, add them together there, and reduce once:

The answer is the same, but many Montgomery reductions have become one.

Deferred arithmetic in pasta_curves

This idea is not new to Zakura. Several months ago, Tachyon's Alex Xiong added a deferred feature to pasta_curves, motivated by Ragu, which performs large inner products during polynomial operations.

The interface allows callers to accumulate raw products into a wider representation:

let mut acc = F::Accumulator::default();

for (a, b) in terms {
    F::mul_accumulate(&mut acc, a, b);
}

let result = F::reduce(acc);

For the Pasta fields, the accumulator holds the running sum of unreduced 512-bit products, along with enough additional space to track overflow. Only when the caller is finished does it fold the wide value back down and perform the Montgomery reduction.

That gave Ragu the primitive it needed, and it put a safe, reusable deferred-arithmetic interface in the field library. The natural next question was where else values are being reduced before anything needs them reduced.

Deferring work in halo2

halo2 has plenty of opportunities. A prover spends a large amount of time evaluating polynomial expressions over large domains, and many of those expressions contain weighted sums of products. At a simplified level, an evaluator computes things like

A generic field implementation computes each term * power as a complete field multiplication, so every term pays for its own Montgomery reduction before being added to the result. We changed part of halo2's polynomial evaluator to accumulate those products in the wide pasta_curves representation instead, performing one reduction after the sum is complete. That change by itself reduced end-to-end one-Action Orchard proving latency by about 1.2%.

There are similar opportunities elsewhere in the evaluator. Orchard's constraint expressions contain repeated factors inside larger weighted expressions; recognizing those factors ahead of time both avoids recomputing them and arranges more of the remaining arithmetic as deferred products. Our evaluator now does that, reducing proving latency by another 1.4% in its direct benchmark.

None of this changes the circuit or the proof system. The constraints, keys, transcript and proof encoding are unchanged. We are computing the same field expressions in a better order.

The individual ideas here are not exotic: a cryptographer looking at a large arithmetic expression will naturally look for common factors, Horner forms, common subexpressions, and sums that can share normalization work. What matters in a prover is finding these structures in the real evaluator, arranging the implementation so they compose, and measuring whether the saved field operations actually translate into end-to-end performance. In this case they do, and because the changes are independent, the savings combine.

A difference of products

Curve arithmetic contains many expressions of the form . The ordinary field implementation computes a * b and c * d separately; each produces a complete field element, so each performs its own Montgomery reduction, and the two results are then subtracted. But the intermediate products are never needed individually. The value we want is , so in principle we can form both double-width products, subtract them while they are still unreduced, and reduce once.

This is the same idea as the deferred inner product, but the engineering tradeoff is different. At this size, the general-purpose accumulator does not pay for itself: maintaining the wide value, handling its carry state, and folding it back into range costs more than the one reduction it saves.

A fixed two-product expression admits a better implementation. We added a specialized difference-of-products operation: on Apple AArch64, it forms both raw products and performs a single direct Montgomery reduction, without going through the general accumulator. In isolation, the operation is about 8.3% faster than computing the two field multiplications normally.

We now use it in the -coordinate formulas for projective-affine mixed addition and for XYZZ addition and doubling, and our batch-verifier benchmark measured about 0.49% less CPU time as a result.

The primitive also changes what we look for. A field library normally exposes addition, subtraction, multiplication and squaring, with every multiplication returning a fully reduced element. But the useful unit of computation is sometimes not a multiplication; it is a sum or difference of products, and exposing that structure to the field implementation lets it avoid reductions that the generic sequence of operations is forced to perform.

Fewer reductions

The general rule is to avoid reducing an intermediate value until something actually requires it to be reduced. For long sums of products, that means accumulating in the deferred pasta_curves representation and reducing once. For a small fixed expression like , a specialized fused implementation is better. And in higher-level code such as the halo2 evaluator, it means arranging the computation so that these opportunities are visible in the first place.

Montgomery reduction is necessary; performing one after every multiplication often is not. There are a lot of multiplications in a Zcash prover, verifier and wallet, and we are continuing to look for the reductions between them that we can remove.