# Faster Elliptic-Curve FFTs with Affine GLV Batches and Mixed-Radix Codelets

This engineering page describes Zakura's ongoing work on the
elliptic-curve FFT used during Halo 2 proving-key generation. Its focus is the transform itself: why PLONK's evaluation-form
polynomials make Halo 2 need it, how Cooley–Tukey factors it, and how
mixed-radix FFTW-style codelets reduce its scalar-multiplication count. The
human-facing title is “Fastest ecFFT in the West”, a deliberate reference to
FFTW (“Fastest
Fourier Transform in the West”); the body prose is plainer than the title.
Neither the human page nor this alternate names pull requests or tracks the
merge status of individual changes.

## Why proving-key setup matters

Before an application can prove a transaction or private vote, it generates a
proving key for the relevant circuit. In Zakura's profiling of representative
workloads, that setup has been roughly 30% of the total time to build the key
and create the proof. Until shortly before
Ironwood the transaction builder rebuilt the Orchard proving key for every
transaction; after Zakura reported it, an upstream librustzcash fix caches one
key per circuit version. Caching does not make setup free: the first proof in
a process still pays it, as do command-line tools, tests, new circuit
versions, and applications building a verifying key independently.

The expensive step is not circuit-specific: Orchard's `ProvingKey::build`
first constructs Halo 2's polynomial-commitment parameters, and the curve FFT
happens inside that construction, before any circuit key generation. Halo 2
parameter generation is local and deterministic, hashing public labels into
curve points. It is not a trusted-setup ceremony.

## Why Halo 2 needs a curve FFT

A PLONK circuit is arranged as rows over a roots-of-unity domain H of size n,
so a circuit column is a polynomial A(X) represented by its evaluations
A(omega^i) = a_i. Halo 2's polynomial commitment key is a vector of curve
generators G_j for the monomial basis: Commit(A) = sum_j [a'_j] G_j over
monomial coefficients a'_j. Rather than inverse-FFT every column before every
commitment, Halo 2 converts the key itself once. With Lagrange basis
polynomials ell_i (ell_i(omega^j) = 1 if i = j, else 0), linearity gives
precomputable generators

G_i^Lag = Commit(ell_i) = (1/n) sum_j [omega^(-ij)] G_j,

so committing to an evaluation vector is Commit(A) = sum_i [a_i] G_i^Lag.
The whole vector of Lagrange generators is an inverse
discrete Fourier transform of the monomial-basis generators.

Computing every output directly needs n scalar multiplications and additions
for each of n outputs, or O(n^2) curve operations. An inverse FFT computes the
same basis conversion in O(n log n); an FFT applies because n is a power of
two and the scalar field contains the required roots of unity.

It is a curve FFT because its values are elliptic-curve points rather than
field or complex values. Linearity still permits the usual FFT decomposition,
using point addition and scalar multiplication; nothing ever multiplies two
curve points together. But a twiddle that would cost one field multiplication
in a field FFT becomes a full variable-base curve scalar multiplication. This
asymmetric cost is why using fewer twiddles matters. The roots of unity and
all points in this setup are public, so variable-time algorithms are
appropriate here; this reasoning does not transfer to secret-dependent scalar
multiplication.

## Cooley-Tukey and the foundational optimization

Radix-2 Cooley-Tukey begins with the even/odd coefficient identity

f(X) = E(X^2) + X O(X^2).

The roots omega^k and omega^(k+n/2) = -omega^k have the same square:

(omega^(k+n/2))^2 = (-omega^k)^2 = omega^(2k).

The half-size polynomials E and O therefore need to be evaluated only once at
omega^(2k). Their results combine as

f(omega^k) = E(omega^(2k)) + [omega^k]O(omega^(2k)) and
f(omega^(k+n/2)) = E(omega^(2k)) - [omega^k]O(omega^(2k)).

Recursively applying this identity produces two size-n/2 transforms followed
by curve-valued butterflies

(L, R) -> (L + [tau]R, L - [tau]R).

The conventional layered eight-point network needs five nontrivial scalar
multiplications: two across its 4-point layer and three across its 8-point
layer.

Before changing that graph, Zakura changed how the scalar multiplications
execute. Pallas and Vesta have a cheap order-three endomorphism phi acting by
a scalar lambda, and GLV decomposes a twiddle tau into roughly half-size
components with tau = a + b*lambda mod q (q is the scalar-field order), so
[tau]P = [a]P + [b]phi(P). The twiddles are public and the same ones repeat
across the blocks of a layer, so the implementation decomposes each distinct
twiddle once and runs the points it multiplies through Eisenstein-recoded
affine ladders in lockstep. Keeping the FFT state affine lets the ladders and
the butterflies share batched field inversions; the butterfly outputs L+R and
L-R share a single denominator. A second round of fused-inversion and
scheduling refinements tightened that structure. The recoding and batch
affine ladder techniques come from Zakura's key-agreement engineering work.

## Codelets and algorithm lineage

FFTW composes large transforms from optimized fixed-size transforms called
codelets. Its `genfft` compiler generates codelets, while its runtime planner
searches for a good composition on the current machine.

Zakura's curve FFT is narrower: its supported sizes, curve, public twiddles,
and unusual scalar-multiplication cost are known. It does not implement an
FFTW-like runtime planner. It selects a fixed factorization from the domain
size and uses exposed DFT8 and DFT16 codelets whose algebra, affine additions,
and scalar schedules are optimized together.

Winograd is an influence on the multiplication-first objective, not the name
of the complete algorithm. The DFT16 codelet has a split-radix shape: one
DFT8 and two odd-root DFT4 transforms. The complete curve FFT uses mixed-radix
Cooley-Tukey with radices eight and sixteen. FFTW supplies the codelet
vocabulary and the idea of composing a large transform from fixed kernels.

## Eight-point codelet

For a primitive eighth root w, define

i = w^2,
c = (w + w^3)/2,
d = (w - w^3)/2.

Then

[w]P + [w^3]Q = [c](P+Q) + [d](P-Q),
[w^3]P + [w]Q = [c](P+Q) - [d](P-Q).

The fused eight-point transform forms shared sums and differences first. It
uses two scalar multiplications by i, one by c, and one by d: four scalar
multiplications instead of radix-2's five, with two additional group
additions. These counts cover the DFT network's twiddle multiplications; the
shared 1/n normalization of the inverse transform is handled separately and
excluded on both sides. All DFT8s in one tier advance through the same affine
substage together. The constants i, c, and d are decomposed once for the
complete transform, and every point using one constant joins the same affine
GLV batch.

## Sixteen-point codelet

The fused 16-point codelet first pairs inputs separated by eight. Its sums
enter a DFT8 and its differences enter two odd-root DFT4 transforms. The
subtransforms share linear combinations, i/c/d scalar schedules, and affine
denominator inversions. Four remaining odd powers of the 16th root use
same-scalar batches.

The per-block counts are cumulative, not additive: plain radix-2 needs 17
nontrivial scalar multiplications per 16-point block, two eight-point codelets
under the top radix-2 layer bring that to 15, and fusing the entire block
brings it to 14. Each of six affine-addition substages runs across every active
DFT16 before the next begins, providing one large inversion batch per
substage.

At n=2048 there are 128 blocks. The bottom four layers therefore fall from
128*17 = 2,176 scalar multiplications (radix-2) to 128*15 = 1,920
(eight-point codelets) to 128*14 = 1,792 (fused): 384 fewer per transform in
total, of which 256 come from the eight-point codelets and 128 from the
fusion. This was the first, bottom-only codelet schedule.

## Mixed-radix codelet tiers

For every transform size 2^k with k >= 6, the current implementation uses
DFT8 and DFT16 as the radices of the complete Cooley-Tukey factorization. In
implementation order from inner to outer, Orchard k=11 uses [8, 16, 16].
k=10 uses [8, 8, 16], k=12 uses [16, 16, 16], and k=13 uses
[8, 8, 8, 16].

The first N-point pass gathers contiguous, locally bit-reversed codelets.
Between tiers, the code applies the Cooley-Tukey diagonal twiddles while
transposing into contiguous codelets for the next radix. One N-point scratch
vector alternates with the output. All codelets in a tier execute one affine
substage before advancing, retaining a large inversion batch.

Equal diagonal twiddles are grouped into the same scalar schedule. A power
cache GLV-decomposes every distinct root-of-unity power once and reuses it
across tiers. Exponents e+N/2 reuse exponent e followed by free point negation;
the N/2 twiddle itself needs only negation.

At k=11, plain radix-2 needs 9,217 nontrivial point-scalar multiplications.
The previous DFT16-bottom schedule needs 8,833, while mixed [8, 16, 16] needs
8,193. This is 640 fewer than the prior codelet schedule and 1,024 fewer than
plain radix-2. It performs 24,576 curve additions, 740 distinct twiddle
decompositions, sixteen sequential affine-addition inversion batches, and four
N-point layout passes.

The path below k=6 remains simpler. k=3 and k=4 are single DFT8/DFT16
codelets. Splitting k=5 as 2*16 does not reduce scalar multiplications and
would add transpose traffic.

## Benchmark results

The reported comparisons use Apple Arm64 benchmark hosts. Three checkpoints
summarize the progression:

- Original projective radix-2: 215.3 ms multicore. Its isolated single-core
  time was not measured; a best-effort reconstruction gives about 588 ms.
- Affine GLV and scheduling immediately before the first codelet: 34.957 ms
  multicore and 138.07 ms single-core.
- Complete stack through the mixed-radix codelets: 28.33 ms multicore and
  120.44 ms single-core.

The single-core baseline estimate subtracts the nearest observed non-FFT
remainder from the original parameter-generation measurement. The optimized
`Params::new(k=11)` and isolated curve FFT measurements were 185.9 ms and
140.66 ms, leaving 45.24 ms. Subtracting that remainder from the original
633.4 ms `Params::new(k=11)` measurement gives 588.16 ms. This is an estimate,
not an isolated benchmark.

The checkpoints imply a 6.16x multicore and estimated 4.26x single-core gain
before codelets, and a 7.60x multicore and estimated 4.88x single-core gain for
the complete stack. From the pre-codelet to final checkpoints, elapsed time is
19.0% lower multicore and 12.8% lower single-core. These are historical
endpoint comparisons, not one continuous A/B campaign. The final checkpoint
also includes intervening GLV refinements, notably the direct one-inversion
2P+D ladder formula; it must not be presented as a pure codelet delta.

The individual controlled comparisons are:

- Affine GLV batches replacing generic projective radix-2: multicore curve
  FFT 215.3 ms to 36.8 ms (5.85x); multicore `Params::new(k=11)` 220.8 ms to
  46.0 ms (4.80x). Single-core `Params::new(k=11)` 633.4 ms to 185.9 ms
  (3.41x).
- Fused inversions and scheduling refinements, relative to the affine GLV
  baseline: multicore curve FFT 36.797 ms to 34.957 ms (5.0% less);
  single-core 140.66 ms to 138.07 ms (about 1.8% less).
- The 8- and 16-point codelets, relative to the scheduling refinements, in
  interleaved A/B/A runs: multicore curve FFT 35.096 ms to 32.998 ms (5.98%
  less); single-core 142.86 ms to 135.94 ms (4.84% less); multicore
  `Params::new(k=11)` 44.361 ms to 42.295 ms (4.66% less); single-core
  187.49 ms to 180.32 ms (3.82% less).
- The mixed DFT8/DFT16 tiers, relative to their immediate stacked parent:
  k=11 multicore curve FFT 31.70 ms to 28.33 ms (10.65%
  less) on one Apple host and 31.68 ms to 28.33 ms (10.57% less) on a second.
  Single-core time fell by 7.32% and 7.45%.

Across Zakura's parameter-generation work through the affine GLV batching,
Orchard `ProvingKey::build` changed from 1.058 s to 135.9 ms with all
workers (7.79x, described as about 8x) and from 2.009 s to 450.9 ms
single-threaded (4.46x). The later codelet work improves the curve-FFT and
`Params::new` components on top of that cumulative proving-key result.
The human article describes the broader result to date as a 10x speedup; the
exact 7.79x figure above is the earlier measured checkpoint it documents.

## Caution

- Do not attribute the cumulative about-8x `ProvingKey::build` result solely
  to codelets. The large gain came from the full
  parameter-generation series, especially affine GLV batching. The codelet
  work itself removes about 6% from the multicore curve FFT and about 4.7%
  from multicore `Params::new` relative to the scheduling-refinement baseline;
  the later mixed-radix schedule removes a further 10.6% from the multicore
  curve FFT relative to its immediate predecessor.
- Do not describe this as a new trusted setup, a consensus change, a
  proof-system change, a classical WFTA, or an FFTW runtime planner. It
  computes the same public generator basis with a mixed-radix arithmetic
  schedule selected from the domain size.
- Neither the human page nor this alternate tracks whether individual changes
  have merged or shipped; do not assert a code status for any of them.

## Primary links

- Upstream librustzcash proving-key caching fix:
  https://github.com/zcash/librustzcash/pull/2730
- PLONK paper: https://eprint.iacr.org/2019/953
- FFTW: https://www.fftw.org/
- FFTW codelet generator documentation:
  https://www.fftw.org/doc/Generating-your-own-code.html
- Cooley and Tukey's algorithm:
  https://research.ibm.com/publications/an-algorithm-for-the-machine-calculation-of-complex-fourier-series
- Winograd's DFT paper:
  https://research.ibm.com/publications/on-computing-the-discrete-fourier-transform
- Duhamel and Hollmann's split-radix paper:
  https://doi.org/10.1049/el:19840012

---

Canonical HTML version: https://zakura.com/engineering/pasta-ecfft/