circuits/logic/
Arithmetization of boolean logic and fixed-width integer arithmetic in a finite field. The headers in this directory provide the primitives that almost every higher-level Longfellow circuit is built from — gates, bit vectors, adders, multipliers, comparators, routing networks, bit pluckers, and a few associated helpers.
All types live in the proofs:: namespace.
Design overview
Every primitive in this module is templated over two things:
- A
Field— a finite field implementation (e.g.FpGeneric<...>fromalgebra/fp_generic.h, orGF2_128fromgf2k/gf2_128.h). - A
Backend— a tiny object that defines what a “wire value” means and how the gate operations behave.
The module ships two backends:
CompilerBackend— wires are integer IDs; gate operations append nodes to aQuadCircuitbeing compiled.EvaluationBackend— wires carry actual field elements; gate operations compute directly.
The same source code therefore compiles a circuit or evaluates it, depending on which backend is instantiated.
Bit representation
Boolean values are represented in the standard basis: TRUE → 1,
FALSE → 0. A wire-carried bit is a
Logic::BitW — a triple (c0, c1, x)
that represents the affine form c0 + c1 · x. Compile-time constants c0,
c1 let the compiler fold representation changes (for example, the output of
an XOR gate lives in the {−1, +1} “xor basis” until it is evaluated) without
inserting real gates.
Fixed-width integers are arrays of BitW, exposed via
Logic::bitvec<N> with common
widths aliased as v1, v8, v32, v64, v128, v256.
Module map
| Page | Header | Purpose |
|---|---|---|
| Logic | logic.h | Core class: gates, arithmetic, comparators, adders, multipliers, bit-vector ops |
| Backends | compiler_backend.h, evaluation_backend.h | The two backends Logic can be instantiated with |
| Routing | routing.h | Variable-amount shift / unshift networks |
| Memcmp | memcmp.h | Lexicographic byte-array comparison over v8[] |
| BitAdder | bit_adder.h | Field-level embedding for summing bit vectors |
| Counter | counter.h | Typed “counter” element separate from EltW |
| Polynomial | polynomial.h | Powers-of-x, dot-product, and Horner evaluation |
| Pluckers | bit_plucker.h, bit_plucker_constants.h, bit_plucker_encoder.h, unary_plucker.h, unary_plucker_constants.h | Mapping packed field elements to bit wires |
| Unary | unary.h | A[i] = (i == j) and A[i] = (i < j) decoders |
Conventions
- Arguments. Since the introduction of deterministic wire renumbering in
the compiler, function arguments follow standard C++ conventions: plain
const BitW&/const EltW&references. (Historically, all but the last argument wereconst T*— this constraint has been removed.) - Arrays. Raw pointer + length is the baseline API (
BitW a[/*w*/],size_t w).bitvec<N>overloads are provided for compile-time widths. - Assertions.
assert0(x)enforcesx == 0at proof time;assert_eq,assert1,assert_is_bit,assert_implies,assert_sumare thin wrappers over it.