permutation performance — 2026-10-09

Work package P of the proof-system repair: make the hemera permutation and its 2-to-1 node compression fast on Apple Silicon and in portable Rust, without changing an output bit. Branch perf/permutation-neon on 23f3bbc (hemera 0.3.1).

Machine: Apple M4 Max (12 P + 4 E cores), 48 GiB, macOS 26.4.1, rustc 1.95.0 (Homebrew), default release profile (no LTO, no target-cpu). The machine was shared with other sessions throughout: load average 8–19 during every measurement below. macOS offers no core pinning; absolute numbers carry ±10 % run-to-run noise, which is why the final comparison alternates binaries (§3).

1. bit-exactness

Every optimised path is compared on canonical values against reference.rs, a frozen oracle that keeps the 0.3.1 arithmetic and round order but computes x⁻¹ by plain square-and-multiply over the bits of p−2 (the definition, independent of any addition chain). rs/tests/differential.rs, release build, HEMERA_DIFF_N default 10⁶:

Inputs include non-canonical representatives ([p, 2⁶⁴)), all-zero and all-p states, and edge limbs (0, 1, p−1, p, p+1, 2⁶⁴−1, 2³², 2³²−1). Plus 100 000 states checking that permute_traced and StepSponge end bit-identical (raw limbs) to permute. Total ≈ 3.7 × 10⁶ randomized inputs, 0 mismatches, 6.8 s on all cores. The same test passes with the portable arithmetic forced on aarch64 (RUSTFLAGS="--cfg hemera_portable"), and in a debug build (10⁴ per family, overflow checks on). The pinned vectors (rs/tests/vectors.rs) and all 247 unit tests pass unchanged.

Output representation: permute, permute_traced and the last StepSponge round now return canonical limbs. The 0.3.1 code could return a limb in [p, 2⁶⁴) (field-equal, probability ≈ 2⁻³² per limb); the consumers found (hash output encoding, the wgsl GPU test, zheng execution/hash.rs and ccs/root.rs) read canonical values. Goldilocks * Goldilocks returns the same representative as before, bit for bit.

2. steps, measured during development

examples/bench.rs (median of N timed batches) and examples/split.rs (median of 41). Single runs under load, so read the trend, not the last digit. "batch" = 1024 independent permutations through the best API at that step.

Breakdown at step 5 (split, median): single = full rounds 413 + partial rounds 2 347; batched = full rounds 388 + partial rounds 348 ns per permutation. Replacing the S-box by the identity (throwaway build) put the batched linear layers at 130 ns (external) and 196 ns (internal), so batched inversion costs ≈ 150–210 ns per permutation.

Goldilocks multiplication (scratch harness, 10⁷ random pairs checked per variant)

The latency form is ~7.7 cycles at the measured ~3.9 GHz: umulh (3) + shift + subtract + add + select. The borrow branch fires when lo < hi_hi < 2³² (≈ 2⁻³² per product); Plonky3's Goldilocks reduction makes the same choice. It is a data-dependent branch in a hash that also runs keyed; the constant-time form costs ≈ 0.3 ns per serial multiply (≈ +16 × 70 × 0.3 ns ≈ +0.34 µs per single permutation). Recorded here so the trade is visible.

NEON (examples/neon_mul.rs)

aarch64 NEON has no 64×64→128 multiply; a 2-lane Goldilocks product takes four umull plus carry and reduction logic (~29 vector instructions). Checked equal to the scalar product on 10⁶ random pairs.

NEON emulation is ~2× slower per lane than scalar, and adding NEON lanes beside scalar chains did not raise total throughput in either mix measured. Lane parallelism is therefore done as scalar interleave (ILP) in a structure-of-arrays layout, which the kernel does for 2/4/8/16 lanes. NEON for the addition-only external layer (≈ 130 ns of 720 per batched permutation) was not attempted; the ceiling of that change is below 18 %.

honeycrisp

honeycrisp/acpu/src/field/goldilocks.rs offers gl_mul (inline mul+umulh, then the same reduction as 0.3.1) and gl_mul_batch (4 interleaved scalar chains). No vector or matrix-unit field multiply exists there to use; gl_mul reduces exactly like the 0.3.1 row of the table above, which the shipped forms beat (acpu itself was not benchmarked). Not used.

nebu

strata/nebu/rs/field.rs::reduce128 is the 0.3.1 reduction (table above). Side finding, outside this package: a standalone copy of nebu/rs/algebra_impl.rs dot + its local reduce128 (lines 73–117) returns the wrong value for 10 000 of 10 000 random length-4 inputs (the u128 accumulator wraps after two products, and hi.wrapping_mul(ε) is only correct for hi < 2³²). Measured on the copy, not on nebu itself.

3. final numbers (alternating binaries)

Baseline = origin/main 23f3bbc with the same bench (batch APIs as plain loops). aarch64 = this branch. portable = this branch with --cfg hemera_portable (no asm; the code path non-aarch64 targets get). Five alternating rounds × 31 runs each, median of the five medians, ns per operation. Load average 9–17.

The x⁷ RF 6+6 / RP 48 shape (profile-v2 proposal, hemera PR #15) through the same kernel (split, placeholder constants — cost only): single 1 375 ns, batched 1 242 ns per permutation. Against the live profile: half the single-permutation latency (no 70-deep inverse chain), 1.7× the batched cost (48 partial rounds × 16 multiplications against 16 × ~25).

4. lens WHIR verify

Permutations counted with a throwaway counter (hemera, not committed) in one Whir::verify, rate 1/16, lens feat/rs-whir-pcs 8f188a9:

Verify time, three lens binaries alternated five times (15 runs each, median of medians, load 13–19):

"lens batching" is a throwaway lens diff (not committed): merkle::verify hashes each level's nodes with one hash_node_batch call, and WHIR's check_opening hashes a round's opened leaves with one hash_leaf_batch call. cargo test --release -p cyber-lens-rspcs (28 tests: completeness to 2²⁰, wrong-claim rejection, bit-flip scans, cheating prover) passes with it.

Projection by count × cost (cost per permutation from §3: single 2.93 µs, batched 0.80 µs; non-hash residual = baseline verify − 530 or 2 467 × 4.15 µs = 0.41 ms at 2¹⁰, 1.69 ms at 2²⁰):

The ≤ 1 ms target holds at 2¹⁰ once lens adopts the batch calls; at 2²⁰ it does not.

5. what limits further speedup

• single permutation, live profile: the partial rounds are one serial chain, 16 × (69 squarings/multiplications of the inverse + 1 multiply-add) ≈ 1 100 dependent multiplications at ≈ 2.0 ns = 2.2 µs of the 2.75–2.93 µs. The chain depth is ≥ 64 for any exponentiation (log₂ p); 69 is within 5 of that bound. A further cut needs a non-exponentiation inverse (binary GCD / safe-gcd — not evaluated) or the x⁷ profile (§3: 1.38 µs).
• batched: instruction throughput. A Goldilocks product is 9–13 scalar instructions (no 64-bit modular multiply, no useful NEON form); a batched permutation retires ≈ 14 k instructions. Full rounds are 512 S-box multiplications; partial rounds 15 internal-diagonal multiply-adds per round — the diagonal entries are full 64-bit values, so no shift-and-add form exists (the Poseidon2 reference picks small diagonals; changing them changes the hash).
• lens: transcript and PoW permutations (61 / 215) are serial; the non-hash verifier work (sumcheck, folding, Fp3 arithmetic) is ≈ 0.4 ms at 2¹⁰ and ≈ 1.7 ms at 2²⁰ by the residual estimate — at 2²⁰ that alone exceeds 1 ms. The verifier is single-threaded; spreading the 2 252 batchable permutations at 2²⁰ across cores is the remaining hashing lever (≈ 1.8 ms single-core; not measured).

6. constant-time kernel for secret input (added 2026-10-09)

Decision (coordinator): keep the branchy fast multiplication for public hashing; every path that can see secret input runs a constant-time kernel, chosen by the entry point and not by the caller. The list of entry points is in specs/api.md § constant time: keyed_hash, derive_key, the new hash_secret (= hash, constant time — mudra's domain_scalar hashes secret entropy with plain hash today), the hashers behind them and their XOF readers, and permute_ct.

Implementation: rs/src/backend.rs — the kernel is generic over Fast and Ct arithmetic. Ct multiplies in 13 aarch64 instructions with both reduction fix-ups as csel (no branch by construction), adds and canonicalises with masks; the portable form uses masks. Zero lanes in the batch inversion are masked rather than branched on in both backends, and Goldilocks +, − and as_canonical_u64 are now mask-based (same bits; the sponge absorbs and encodes secret input with them).

Checks:

• rs/tests/constant_time.rs: permute_ct = permute, raw limbs, on 10⁶ random states (edge values and non-canonical limbs included); hash_secret, hash, keyed_hash, derive_key and a secret XOF against a reference sponge on reference::permute, 10⁵ random inputs each. 0 mismatches; also with --cfg hemera_portable and in debug.
• Disassembly of the compiled permute_ct (release, aarch64 asm path 2 354 lines; portable path 2 043 lines): 19 / 22 conditional branches, every one comparing a loop counter with a constant (round loops, the 15- and 33-squaring runs, the every-third-squaring interleave counter, the 15-row loop); every indexed memory access uses a row counter. No branch or address depends on a field value. This is an inspection of one compiler output (rustc 1.95.0), not a guarantee for other compilers — the asm multiply is the part that holds by construction.

Cost (examples/bench.rs, 5 runs × 31, median of medians, ns, load 9–30):

The constant-time single permutation is still faster than the 0.3.1 fast one (4 146 ns, §3). Its multiplication is ≈ 9 cycles on the serial chain against 7–8 for the fast form (the borrow fix-up returns to the dependency chain).

reproduce

cargo test  --release -p cyber-hemera --test differential -- --nocapture
cargo test  --release -p cyber-hemera --test constant_time -- --nocapture
cargo run   --release -p cyber-hemera --example bench [-- runs]
cargo run   --release -p cyber-hemera --example split
cargo run   --release -p cyber-hemera --example neon_mul
RUSTFLAGS="--cfg hemera_portable" cargo test --release -p cyber-hemera   # portable path