# Binary Tower Fields > Binary tower fields from GF(2) to GF(2^256) in Rust, constant-time by default, PMULL on aarch64: the math core of the Hekate engine and its chiplets. - URL: https://oumuamua.dev/primitives/math/binary-tower-fields - Published: 2026-10-04T18:28:41+07:00 - Updated: 2026-10-07T13:34:41+07:00 Hekate's prover, its verifier and every chiplet compute in these fields: trace cells, sumcheck messages and challenges are all tower elements, and [System Architecture](https://oumuamua.dev/hekate/docs/basics/system-architecture#why-binary-fields) shows them inside a proof. The crate also stands alone; its README names sumcheck, GKR-based provers and Binius protocols as uses. Its default features are `std` and `parallel` (Rayon), and without them it builds as `no_std`. ## The tower The tower runs from GF(2^8), the AES field, to GF(2^256), each level twice the width of the one below, and `Bit` embeds GF(2) as a subfield. A level adjoins a root of v² + v + βᵢ, with a fixed constant βᵢ per level, and an element is a (low, high) pair from the level below. | Field | Type | Extension constant β | |:----------|:-----------|:-----------------------------------------------------| | GF(2) | `Bit` | embedded subfield | | GF(2^8) | `Block8` | base field, the AES polynomial | | GF(2^16) | `Block16` | `0x20` in `Block8` | | GF(2^32) | `Block32` | `0x2000` in `Block16` | | GF(2^64) | `Block64` | `0x20000000` in `Block32` | | GF(2^128) | `Block128` | `0x2000000000000000` in `Block64` | | GF(2^256) | `Block256` | `0x20000000000000000000000000000000` in `Block128` | ## Two bases Each field has two representations, and the type system keeps them apart. Recursion is cheap in the tower basis, and the carry-less multiply works in the flat basis, the polynomial basis of the field. A tower value is `F`, a flat value is `Flat`, and mixing them fails to compile. `to_hardware` and `to_tower` convert, and both bases give the same products and sums. ## Examples The three programs below are the README's examples as standalone programs. - `isomorphism.rs` multiplies and adds in both bases and checks that they agree. - `simd.rs` packs four flat `Block32` values into one 128-bit register through `PackableField` and multiplies them lane by lane. - `fft.rs` runs the additive FFT of Gao and Mateer in the Cantor basis: `forward_scalar` evaluates novel-basis coefficients on the 2^log_n points of a subspace, and `inverse_scalar` interpolates them back. ```rust examples/isomorphism.rs:1 use hekate_math::{Block128, HardwareField, TowerField}; fn main() { // Canonical Basis (Tower) let a_tower = Block128::from_uniform_bytes(&[0xaa; 32]); let b_tower = Block128::from_uniform_bytes(&[0xbb; 32]); // Basis Conversion -> Polynomial (Flat) let a_flat = a_tower.to_hardware(); let b_flat = b_tower.to_hardware(); // Hardware-Accelerated Arithmetic let c_flat = a_flat * b_flat; let d_flat = a_flat + b_flat; // Return to Canonical let c_tower = c_flat.to_tower(); let d_tower = d_flat.to_tower(); assert_eq!( c_tower, a_tower * b_tower, "Multiplication Homomorphism failed" ); assert_eq!(d_tower, a_tower + b_tower, "Addition Homomorphism failed"); } ``` ```rust examples/simd.rs:1 use hekate_math::{Block32, Flat, HardwareField, PackableField, TowerField}; fn main() { let data: Vec> = (0..8) .map(|i| Block32::from(i as u32 + 1).to_hardware()) .collect(); process_simd(&data); } fn process_simd(data: &[Flat]) { // Pack hardware-basis scalars into SIMD registers // PackedBlock32 holds 4 elements (128 bits total). let chunk_a = Flat::::pack(&data[0..4]); let chunk_b = Flat::::pack(&data[4..8]); // Vectorized Arithmetic: // Performs 4 parallel field // multiplications in the hardware basis. let result_packed = chunk_a * chunk_b; let mut out_flat = [Block32::ZERO.to_hardware(); 4]; Flat::::unpack(result_packed, &mut out_flat); for i in 0..4 { // Convert back to Canonical let res_tower = out_flat[i].to_tower(); let a_tower = data[i].to_tower(); let b_tower = data[4 + i].to_tower(); assert_eq!(res_tower, a_tower * b_tower, "SIMD multiplication mismatch"); } } ``` ```rust examples/fft.rs:1 use hekate_math::{AdditiveFft, Block16, Flat, HardwareField, TowerField}; use std::error::Error; fn main() -> Result<(), Box> { let log_n = 10u32; let fft = AdditiveFft::::new(log_n)?; // Novel-basis coefficients, hardware (flat) basis let coeffs: Vec> = (0..1u32 << log_n) .map(|i| Block16::from(i).to_hardware()) .collect(); // Coefficients -> evaluations on W_10, in place let mut data = coeffs.clone(); fft.forward_scalar(&mut data)?; // Evaluations -> coefficients fft.inverse_scalar(&mut data)?; assert_eq!(data, coeffs); Ok(()) } ``` The transform takes `Block16` through `Block128`, in scalar and packed forms, each with a coset variant, and buffers of 1 MiB and up run on Rayon, bit-identical to serial. `ReedSolomon` builds a systematic Reed-Solomon code on it, whose codeword starts with the message. ## Constant time The default build is constant-time, and the `table-math` feature trades that for speed. By default, basis conversion runs as bit-sliced matrix multiplication whatever the input, and the carry-less multiply takes constant latency on current microarchitectures. `table-math` replaces the conversions with cached lookup tables, and GF(2^8) multiplication with log and exp tables and a zero-operand branch: keep it for public data, such as a verifier's inputs. The README marks the constant-time property as unproved. ## Formal verification Verus proofs check the arithmetic kernels against a model of GF(2^k): tower multiplication and inversion, the NEON kernels, the constant-time conversions and batch promotes, and the additive FFT. They live in [`verus/`](https://github.com/oumuamua-labs/hekate-math/tree/main/verus), outside the crate build, and rely on axioms the build discharges and on the transcription seams listed in [`TRUSTED_AXIOMS.md`](https://github.com/oumuamua-labs/hekate-math/blob/main/verus/TRUSTED_AXIOMS.md). ## Platforms aarch64 multiplies in hardware, with PMULL and NEON, and x86_64 runs the software path. On aarch64, PMULL sits behind the `aes` target feature, which `aarch64-unknown-linux-gnu` leaves off by default: build with `RUSTFLAGS="-C target-feature=+aes"`, or the flat kernels take the software path, with the same results at lower throughput. ## Performance Measured on Apple M3 Max, table-math build. The default constant-time build is slower on the tower rows and identical on the flat ones. Reproduce with `cargo bench --features table-math` in a `hekate-math` checkout. ### Block128 operations | Operation | Basis | Latency | Implementation | |:---|:---|:---|:---| | Multiplication | Polynomial (flat) | 0.90 ns | PMULL, pipelined | | Multiplication | Tower (canonical) | 16.6 ns | Basis isomorphism and PMULL | | Addition | Any | 1.15 ns | Vectorized XOR | | Inversion, single | Tower | 106.2 ns | Itoh-Tsujii, Fermat's little theorem | | Inversion, batch | Tower | 15.6 ns | Montgomery's trick, SIMD | | Basis conversion, default | Tower and flat | 40.2 ns | Bit-slicing, constant-time | | Basis conversion, fast | Tower and flat | 3.68 ns | Lookup table, variable-time | ### Polynomial arithmetic in GF(2^128) | Operation | Size | Time | Throughput | |:---|:---|:---|:---| | Dense evaluation, tower | 2²⁰ coefficients | 23.7 ms | 675 MiB/s | | Dense evaluation, hardware | 2²⁰ coefficients | 8.37 ms | 1.87 GiB/s | | Batch evaluation, SIMD | 256 × 16384 | 4.44 ms | 945 Melem/s | | Additive FFT, scalar | 2¹⁶ · Block16 | 477.7 µs | 137 Melem/s | | Additive FFT, packed | 2¹⁶ · ×8 lanes | 386.6 µs | 1.36 Gelem/s | | Interpolate MSM | 65536 points | 106.5 µs | 616 Melem/s | | MLE evaluation | 20 variables | 1.00 ms | 1.04 Gelem/s |