Pluckers

A bit plucker maps a set S ⊂ F of size 2^k to k single-bit output wires. It exists because feeding a k-bit value into a circuit as k single-bit inputs is expensive: every input either has to be sent to the verifier or committed. Packing the same information into one field element and plucking it apart inside the circuit shrinks the input surface — and so shrinks the proof — at the cost of a small in-circuit polynomial.

This page covers the three related types:

• BitPlucker<Logic, LOGN> — the plucker itself.
• BitPluckerEncoder<Field, LOGN> — the out-of-circuit encoder that produces inputs a BitPlucker can consume.
• UnaryPlucker<Logic, NJ> — a plucker that decodes a one-hot index instead of bits.
• EltMuxer<Logic, N, PP> — a runtime-array multiplexer built on the same interpolation trick.
• Point constants — the evaluation points shared by all of the above.

BitPlucker<Logic, LOGN>

Header: circuits/logic/bit_plucker.h

template <class Logic, size_t LOGN>
class BitPlucker {
 public:
  static constexpr size_t kN = 1 << LOGN;
  static constexpr size_t kNv32Elts  = (32u  + LOGN - 1u) / LOGN;
  static constexpr size_t kNv128Elts = (128u + LOGN - 1u) / LOGN;
  static constexpr size_t kNv256Elts = (256u + LOGN - 1u) / LOGN;
 
  using PolyN        = Poly<kN, Field>;
  using v32          = typename Logic::v32;
  using v256         = typename Logic::v256;
  using packed_v32   = std::array<EltW, kNv32Elts>;
  using packed_v128  = std::array<EltW, kNv128Elts>;
  using packed_v256  = std::array<EltW, kNv256Elts>;
 
  explicit BitPlucker(const Logic& l);
 
  typename Logic::template bitvec<LOGN> pluck(const EltW& e) const;
 
  v32 unpack_v32(const packed_v32& v) const;
 
  template <typename T, typename PackedT>
  T unpack(const PackedT& v) const;
 
  template <typename T>
  static T packed_input(const Logic& lc);
};

How it works

The constructor precomputes LOGN polynomials plucker_[k] via Lagrange interpolation. For each bit position k, plucker_[k] is the polynomial that evaluates to (i >> k) & 1 on the 2^LOGN points X[i] defined by bit_plucker_point.

pluck(e) evaluates each plucker_[k](e), asserts the result is a bit, and packages the bits as a bitvec<LOGN>. When e was encoded as bit_plucker_point<Field, 2^LOGN>()(i, F) for some i ∈ [0, 2^LOGN), the output is the bits of i.

Packed unpacking

unpack<T, PackedT>(v) splits an array of packed EltWs into a bitvec by calling pluck on each element and concatenating the bits. unpack_v32 is the common specialization for 32-bit values.

packed_input<T>(lc) is the convenience for reading a packed-input std::array<EltW, …> from the backend’s input stream — useful at the top of a circuit that consumes packed SHA-style 32-bit words.

Circuit cost

The header carries empirical measurements of the depth / wire / term counts for LOGN = 1 … 8. Excerpt:

Reproduce via BitPlucker.PluckSize in bit_plucker_test.cc.

BitPluckerEncoder<Field, LOGN>

Header: circuits/logic/bit_plucker_encoder.h

Out-of-circuit counterpart to BitPlucker. It encodes raw bits into field elements laid out so that the matching BitPlucker decodes them correctly.

template <class Field, size_t LOGN>
class BitPluckerEncoder {
 public:
  using packed_v32  = std::array<Elt, kNv32Elts>;
  using packed_v128 = std::array<Elt, kNv128Elts>;
  using packed_v256 = std::array<Elt, kNv256Elts>;
 
  explicit BitPluckerEncoder(const Field& F);
 
  Elt encode(size_t i) const;                        // plucker point for index i
 
  packed_v32 mkpacked_v32(uint32_t j);                // SHA-256 helper
 
  template <typename T>
  T pack(uint8_t bits[/*n*/], size_t n);              // generic packer
};

pack consumes n raw uint8_t bit values (LSB at index 0), groups them in chunks of LOGN, and encodes each chunk via bit_plucker_point.

UnaryPlucker<Logic, NJ>

Header: circuits/logic/unary_plucker.h

Decodes a one-hot indicator rather than a packed bit-string.

template <class Logic, size_t NJ>
class UnaryPlucker {
 public:
  static constexpr size_t kN = NJ + 1;                 // extra point decodes to all zeroes
 
  explicit UnaryPlucker(const Logic& l);
 
  typename Logic::template bitvec<NJ> pluck(const EltW& e) const;
};

pluck(e) returns a bitvec<NJ> whose j-th bit is 1 iff e was encoded as the j-th plucker point. The extra + 1 point (index NJ) decodes to all-zeroes — useful as an explicit “no match” sentinel.

EltMuxer<Logic, N, PP>

Header: circuits/logic/bit_plucker.h (lives alongside BitPlucker).

template <class Logic, size_t N, size_t PP = N>
class EltMuxer {
 public:
  EltMuxer(const Logic& l, const EltW arr[/*N*/]);
 
  EltW mux(const EltW& ind) const;
};

Given an N-element runtime EltW array and a runtime index ind encoded at the i-th plucker point, returns arr[i].

Unlike BitPlucker, the coefficient array here depends on EltW inputs, so the constructor precomputes it by running the Lagrange basis multiplied by arr. Once constructed, mux(ind) is a single dot product with powers_of_x(ind). This is the right trade-off when the same array must be muxed many times with different indices.

• N — array length.
• PP — the parameter passed to bit_plucker_point<Field, PP>(), which controls the evaluation set. Defaults to N, yielding the points { −(N−1), −(N−3), …, (N−3), (N−1) } (i.e. 2·i − (N−1) for i = 0…N−1). Override to share points with an external encoder.

Point constants

Headers: circuits/logic/bit_plucker_constants.h, circuits/logic/unary_plucker_constants.h.

template <class Field, size_t N>
struct bit_plucker_point {
  Elt operator()(uint64_t bits, const Field& F) const;   // 2*bits - (N - 1)
};
 
template <class Field, size_t NJ>
struct unary_plucker_point {
  static constexpr size_t kN = NJ + 1;
  Elt operator()(size_t j, const Field& F) const;        // bit_plucker_point<Field, kN>()(j, F)
};

Both are stateless functors. bit_plucker_point returns 2 · bits − (N − 1), which produces the centered, odd-spaced evaluation set used throughout this module. unary_plucker_point delegates to it with N = NJ + 1 and checks j ≤ NJ at runtime.