# p3-binary-field
Characteristic-2 field arithmetic as a building block toward binary-field SNARKs.
The crate carries two representations of `GF(2^128)`, which are the same field seen in two
bases:
- the Wiedemann tower `GF(2) ⊂ GF(4) ⊂ … ⊂ GF(2^128)`, whose levels are subfields of one
another;
- the polynomial basis of `x^128 + x^7 + x^2 + x + 1`, the GHASH modulus.
Key items:
- `Gf2` — the base field `GF(2)`
- `BinaryField2`, `BinaryField4`, `BinaryField8`, `BinaryField16`, `BinaryField32`, `BinaryField64`, `BinaryField128` — the tower levels, each a quadratic extension of the one below
- `HasSubfield<BinaryField2>` for `BinaryField128` — `GF(4)` as a subfield of `GF(2^128)`, with a slice membership test and `GF(4)` scalars applied without a product
- `Ghash128` — `GF(2^128)` in the GHASH polynomial basis, with `From` conversions to and from the widest tower level, and an `Algebra<BinaryField128>` action whose results stay in the polynomial basis
- `PackedGhash128` — the SIMD packing, two elements per register on `avx2` and four on `avx512f`,
in both cases only when `vpclmulqdq` is also enabled, so it is absent from the rendered docs
- `BasedVectorSpace` / `ExtensionField` between every pair of byte-aligned tower levels, in the tower basis
- `BinaryChallenger` — Fiat–Shamir over a byte challenger; every bit pattern is a field element, so no rejection sampling is needed
- Carryless-multiply fast paths on x86-64 (`pclmulqdq`, `vpclmulqdq`) and AArch64 (`aes`), with a software backend everywhere else
## Which representation to use
With hardware carryless multiplication, a 128-bit tower product converts both operands into
polynomial coordinates and converts the result back.
Each conversion reads sixteen operand-indexed table entries.
`Ghash128` works directly in polynomial coordinates and avoids those conversions.
Its SIMD packings process two or four independent elements per register.
Dot products accumulate unreduced polynomials and reduce the sum once.
What it gives up is the subfield structure: `GF(2^8)`, `GF(2^16)`, `GF(2^32)` and `GF(2^64)`
are byte-aligned inside the tower representation and are not inside this one.
Code that needs the subfield structure — ring switching, small-field witnesses — wants the
tower. Code that only needs a large binary field — challenges, folding, transforms — wants
`Ghash128`.
## Conventions
Little-endian targets only. The tower-basis coefficients of an element are borrowed in place
as a slice of the level below, which is sound only where the byte layout coincides with the
numeric representation; a compile-time assertion rejects big-endian targets.
`from_u64` and the other `PrimeCharacteristicRing` integer constructors go through the prime
subfield `GF(2)`, so they carry the parity of their argument rather than its bit pattern:
`from_u64(2)` is zero. `from_le_bytes` and `interpolation_node` are the bit-pattern
constructors.
`TowerLevel` exposes the tower structure and typed generator multiplication.
The tower levels are unpacked: `Packing` is `Self` at every one of them, because a tower
product is table lookups that no vector unit widens. Only `Ghash128` has a packing; its
polynomial slice kernels process independent SIMD products while preserving the scalar field
layout.
GHASH coordinates assign the coefficient of `x^i` to bit `i` of the backing integer.
NIST GCM blocks assign `x^0` to the leftmost bit instead.
For a block written as a big-endian integer, reverse all 128 bits before constructing an element.
The field arithmetic alone is not an AES-GCM implementation.
## Timing and backend selection
GHASH multiplication, squaring, square roots, and dot products use no operand-indexed tables.
Their software multiplication assumes constant-time integer multiplication on the target CPU.
GHASH inversion, tower arithmetic, and conversions between the two bases use operand-indexed tables.
These operations are not constant-time and should not process secrets when cache or timing leakage matters.
Hardware GHASH inversion uses five precomputed maps, totaling 320 KiB of read-only tables.
Software GHASH inversion uses the tower norm instead, and does not compile those tables.
Hardware dispatch is selected at compile time, so this `no_std` crate performs no CPU checks
inside scalar arithmetic. `poly_basis::HAS_HARDWARE_CLMUL` describes that compiled choice.
The default `aarch64-apple-darwin` target enables `aes` (including PMULL); generic AArch64 Linux
and baseline x86-64 use the portable tower fallback.
For a binary intended for the build machine, enable its instructions with:
```sh
RUSTFLAGS="-C target-cpu=native" cargo test -p p3-binary-field -p p3-binary-dft
```
For a binary deployed only to CPUs supporting the named feature:
```sh
RUSTFLAGS="-C target-feature=+aes" cargo build --release --target aarch64-unknown-linux-gnu
RUSTFLAGS="-C target-feature=+pclmulqdq" cargo build --release --target x86_64-unknown-linux-gnu
```
Use the baseline target when distributing to heterogeneous CPUs. To exercise the portable
AArch64 path explicitly:
```sh
CARGO_TARGET_DIR=target/portable RUSTFLAGS="-C target-feature=-aes" cargo test -p p3-binary-field --release
```
Part of [Plonky3](https://github.com/Plonky3/Plonky3), dual-licensed under MIT and Apache 2.0.