Binary Fields (GF(2^k))
Longfellow’s binary-field layer provides GF(2^{128}) arithmetic, a generic polynomial type over \mathrm{GF}(2), and the Lin-Chung-Han 2014 FFT that operates natively on binary towers. The main production consumer is the polynomial MAC gadget in circuits/mac/; the LCH14 transform is the fast alternative to characteristic-zero FFT when the working field is \mathrm{GF}(2^k).
When to reach for it
- You are evaluating a polynomial MAC over bytes as a linear-probing check —
circuits/mac/mac_circuitdelegates here. - You want a ZK-friendly MAC / hash that avoids large-integer arithmetic — binary fields let you pack 128 bits per multiplication instead of working at the bit level.
- You are building a binary-tower proof system and need the LCH14 basis for low-degree interpolation and extension.
Design overview
The module has three layers:
GF(2^{128}) representation. Field elements are polynomials of degree < 128 with coefficients in \mathrm{GF}(2). Internally GF2_128 always uses SIMD: N = gf2_128_elt_t is the platform-native 128-bit SIMD type (__m128i via pclmulqdq on x86-64, poly64x2_t via PMULL on ARM). The exposed element type is struct Elt { N n; }, which wraps the raw SIMD value. GF2Poly<2> (two uint64_t limbs) is used only internally during inversion — it is not a drop-in portability fallback for GF2_128.
Multiplication uses carryless (clmul) multiplication plus reduction modulo the fixed irreducible polynomial. Inversion uses a modified extended Euclidean algorithm adapted to keep the running remainder “odd” (lowest bit set), which avoids special-case branches and stays constant-time in the scalar loop.
Subfield basis. GF2_128 maintains a configurable subfield basis — by default \mathrm{GF}(2^{4}) embedded as 16 basis elements — stored as an LU-decomposed matrix. of_scalar(i) maps a log_bits-bit integer to the corresponding subfield element by row-echelon lookup, and sample_subfield draws uniformly from it. This matters for the MAC gadget: witness bytes are 8-bit, the subfield covers them, and the field operations run in the full \mathrm{GF}(2^{128}) only when combining.
LCH14. The Lin-Chung-Han 2014 construction provides an additive (rather than multiplicative) FFT over \mathrm{GF}(2^k). Unlike a classical FFT that needs a multiplicative root of unity, LCH14 uses a linearised polynomial basis \{W_i\} adapted to the subfield tower. Precomputed twiddle factors are the normalised W_i(\beta_j) values. The class offers forward, inverse, and bidirectional transforms; its chief consumer is the LCH14 Reed-Solomon research path (lch14_reed_solomon.h) which plays the same role as the prime-field Reed-Solomon, but over binary fields.
API surface
GF2_128 — the field
class GF2_128 {
public:
using N = gf2_128_elt_t; // platform-native 128-bit SIMD type
struct Elt { N n; }; // exposed element type wrapping the SIMD value
Elt zero() const;
Elt one() const;
Elt of_scalar(uint64_t i) const; // via subfield basis
std::optional<Elt> of_bytes_field(const uint8_t ab[/*kBytes*/],
bool base_only = true) const;
void to_bytes_field(uint8_t out[/*kBytes*/], const Elt&) const;
void add(Elt&, const Elt&) const; // XOR
void sub(Elt&, const Elt&) const; // same as add
void mul(Elt&, const Elt&) const; // clmul + reduce
void invert(Elt&) const; // extended Euclidean
Elt sample(
const std::function<void(size_t n, uint8_t buf[])>& fill_bytes) const;
Elt sample_subfield(
const std::function<void(size_t n, uint8_t buf[])>& fill_bytes) const;
static constexpr size_t kBytes = 16;
static constexpr size_t kBits = 128;
static constexpr bool kCharacteristicTwo = true;
};GF2Poly<N> — internal polynomial type
template <size_t N> // N 64-bit limbs
struct GF2Poly {
uint64_t limb[N];
// XOR-add, clmul-multiply, shift, degree-reduction helpers.
};GF2_128 always uses the SIMD path via gf2_128_elt_t. GF2Poly<2> is used internally during inversion (the extended-Euclidean algorithm operates on unpacked N1 = GF2Poly<2> values) and as a reference implementation inside tests. It is not a portability fallback that replaces GF2_128 on platforms without SIMD.
LCH14 — binary-tower FFT
template <class Field> // Field = GF2_128 (or smaller tower)
class LCH14 {
public:
static constexpr size_t kSubFieldBits = Field::kSubFieldBits;
explicit LCH14(const Field& F); // precomputes ŵ_i(β_j) table
void FFT (size_t l, size_t coset, Elt B[/* 1 << l */]) const; // forward
void IFFT(size_t l, size_t coset, Elt B[/* 1 << l */]) const; // inverse
void BidirectionalFFT(size_t l, size_t k,
Elt B[/* 1 << l */]) const; // truncated
};Inputs are arrays of 2^l field elements; transforms are in-place. The constructor takes only the field reference and precomputes the normalised basis table ŵ_i(β_j); the maximum supported l is Field::kSubFieldBits. FFT and IFFT take a coset offset; BidirectionalFFT takes k, the split point between “time”-domain and “frequency”-domain samples. Method names are uppercase.
Why GF(2^128)?
Bit-level operations (hashing, MAC, byte packing) are awkward in a prime field — every byte boundary costs constraint bits. A characteristic-two field of the right size makes the natural operation (XOR of 128-bit words) free and turns the nonlinear part (polynomial multiplication over \mathrm{GF}(2)) into a single field multiply. For the circuits/mac/ gadget, this means the MAC verification fits in a handful of constraints per byte rather than dozens, which is the difference between a feasible and infeasible proof. For binary-tower proof systems more generally, LCH14 replaces the prime-field FFT as the bulk-polynomial primitive; that path is experimental in Longfellow but the primitives are here.
See it used
longfellow-zk/lib/gf2k/gf2_128_test.cc— gf2_128_test.cclongfellow-zk/lib/gf2k/lch14_test.cc— lch14_test.cclongfellow-zk/lib/circuits/mac/mac_reference.h— native reference for the MAC gadget.
Related
- MAC Gadget — the primary in-circuit consumer.
- Prime Fields — the characteristic-zero alternative.
- Reed-Solomon — the prime-field code whose LCH14 analogue lives here.