Optimize addmod/submod chains by deferring modular reduction

[PavelKopyl]

Summary

For field arithmetic common in cryptographic code (elliptic curves, hash functions), consecutive addmod operations can be replaced with cheaper plain add/sub instructions, deferring the modular reduction to the end of a chain, or eliminating it entirely for intermediate values, as long as overflow and underflow are statically prevented.

Background

The EVM addmod opcode costs 8 gas vs. 3 gas for add. In tight cryptographic loops (e.g. scalar multiplication on a 254-bit curve like BN254), the modular reduction on every addition dominates gas cost. However, canonical reduction, keeping every intermediate value strictly less than the prime, is not required at every step. It is sufficient to:

• Prevent 256-bit overflow: ensure the accumulated value never wraps around
• Prevent underflow on subtraction: ensure the minuend is always greater than the subtrahend before applying sub

If both invariants hold, plain integer arithmetic produces a result that is congruent modulo the prime, and a single reduction can be applied lazily at the end of the chain or at a convergence point (e.g. before a multiplication).

Optimization rules

1. Addition chain: replace addmod with add

For a chain of n additions where each operand is at most k bits wide:

 x = addmod(a₀, a₁, P)                                                                                                                                       
 x = addmod(x,  a₂, P)                                     
 ...                                                                     

Rewrite as:

x = add(a₀, a₁)
x = add(x,  a₂)
 ...                                                                                                                                                         
x = mod(x, P)   // single reduction at the end (or elide if not needed)

Overflow guard: the chain is safe when k + ⌈log₂(n)⌉ ≤ 256. For 128-bit field elements, up to 2^128 consecutive additions fit in 256 bits — far beyond any practical chain length. For 254-bit curves (BN254, Pasta), chains of up to 4 additions are overflow-free without any reduction.

2. Subtraction: inject a compile-time multiple of the prime

A naive a - b mod P may underflow when a < b. Instead of submod, emit:

// a - b  ≡  a + (kP) - b  (mod P)
// where kP is chosen at compile time so that kP - b ≥ 0 for all possible b
x = add(a, kP)   // kP precomputed as a constant
x = sub(x, b)

For example, with k = 4 and b < P, we have 4P - b > 3P > 0, which is always representable in 256 bits for primes up to ~254 bits.

Expected benefit:

Replacing addmod (8 gas) with add (3 gas) saves 5 gas per operation.