Crate p3_binary_field 

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:

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:

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:

CARGO_TARGET_DIR=target/portable RUSTFLAGS="-C target-feature=-aes" cargo test -p p3-binary-field --release

Part of Plonky3, dual-licensed under MIT and Apache 2.0.

Modules

poly_basis

Raw polynomial coordinates for GF(2^128) modulo x^128 + x^7 + x^2 + x + 1.

Structs

BinaryChallenger

A challenger for a binary tower field, driven by a challenger over bytes.

BinaryField2

The binary tower field GF(2^2).

BinaryField4

The binary tower field GF(2^4).

BinaryField8

The binary tower field GF(2^8).

BinaryField16

The binary tower field GF(2^16).

BinaryField32

The binary tower field GF(2^32).

BinaryField64

The binary tower field GF(2^64).

BinaryField128

The binary tower field GF(2^128).

ByteMatrix

An F_2-linear map on a byte, held the way the affine-byte instruction reads it.

Gf2

The prime field GF(2) = {0, 1}, with addition given by XOR and multiplication by AND.

Ghash128

The binary field GF(2^128) modulo x^128 + x^7 + x^2 + x + 1.

LinearizedPoly8b

An F_2-linear map written as sum_j c_j x^(2^j).

M128

A 128-bit block of bits.

M256

A 256-bit block of bits.

M512

A 512-bit block of bits.

PackedGf2

Several independent elements of GF(2), one per bit of a block of storage.

PackedRijndael8b

A block of elements of the AES field, held as plain consecutive bytes.

Poly64

The binary field GF(2^64) modulo x^64 + x^4 + x^3 + x + 1.

Poly192

GF(2^192), as three coordinates over GF(2^64) in the basis 1, y, y^2.

Rijndael8b

The binary field GF(2^8) modulo x^8 + x^4 + x^3 + x + 1.

Traits

Divisible

A block that is exactly several narrower blocks laid end to end, part 0 lowest.

TowerLevel

One level of the Wiedemann tower, GF(2^(2^k)), in whichever basis carries it.

Underlier

A fixed-width block of bits, addressed as an array of words.

Word

The machine integer a bit kernel shifts and masks.

Type Aliases

PackedGf2x8

Eight elements of GF(2), one per bit of a byte.

PackedGf2x16

Sixteen elements of GF(2), one per bit of a 16-bit word.

PackedGf2x32

Thirty-two elements of GF(2), one per bit of a 32-bit word.

PackedGf2x64

Sixty-four elements of GF(2), one per bit of a 64-bit word.

PackedGf2x128

One hundred and twenty-eight elements of GF(2), one per bit of a 128-bit block.

PackedGf2x256

Two hundred and fifty-six elements of GF(2), one per bit of a 256-bit block.

PackedGf2x512

Five hundred and twelve elements of GF(2), one per bit of a 512-bit block.