Arrays

lib/arrays/ is the container layer that feeds sumcheck: multi-dimensional tables of field elements, their sparse cousins, the affine combinators that drive in-place binding, and the on-the-fly equality polynomial. Every witness, wire, and per-layer polynomial in the prover loop lives in one of these containers.

When to reach for it

You are writing a sumcheck round function by hand and need to bind a variable without allocating — this is the binding primitive.
You are sizing memory: each Dense halves on every binding, so after \log_2 n_0 rounds the object collapses to a scalar. The constants here tell you the peak memory.
You are implementing a new gadget that needs a sparse polynomial (only a few nonzero corners) and want the reference layout.

Design overview

Dense. A heap-allocated row-major 2-D array of field elements with dimensions n_0 (innermost, the bound dimension) by n_1. Binding halves n_0 by replacing each adjacent pair (A[2i], A[2i+1]) with the affine combination r \cdot A[2i+1] + (1 - r) \cdot A[2i]. After \log_2 n_0 bindings, n_0 = 1 and the array is a 1-D slice of length n_1. Dense is the main vehicle for multilinear extensions in sumcheck.

Sparse. A reference implementation that stores only nonzero corners as (p_0, p_1, p_2, \text{value}) tuples. Canonicalisation coalesces duplicate positions; binding updates each tuple’s p_0 and accumulates contributions. Used for small sparse polynomials (circuit structure, selector columns) and as the golden model that Dense binding is tested against.

affine.h. Three helpers that encapsulate the half-and-combine step used across the module:

affine_interpolation(r, f_0, f_1) = r \cdot f_1 + (1 - r) \cdot f_0 — the general case.
affine_interpolation_z_nz(r, f_1) = r \cdot f_1 — specialisation when f_0 = 0.
affine_interpolation_nz_z(r, f_0) = f_0 - r \cdot f_0 — specialisation when f_1 = 0.

The specialisations matter because the prover spends a lot of time binding polynomials with many structural zeros.

Eq, Eqs. The equality polynomial \mathrm{EQ}(x, y) = \prod_i (x_i y_i + (1-x_i)(1-y_i)) evaluates to 1 when x = y and 0 otherwise. The sumcheck prover needs it in a specific form: one variable fixed to a public point, the other ranging over the hypercube. Eq<Field> is an entirely stateless class — it has no data members and exposes only a single static Elt eval(...) method that computes EQ[I, j] on the fly using a running product over logn rounds, so it occupies O(1) space. Eqs<Field> is the stateful companion: a subclass of Dense<Field> that, for a fixed point I, pre-computes and stores the full array EQ[I, j] for all j in [0, n).

API surface

`Dense<Field>`


template <class Field>
class Dense {
 public:
  corner_t n0_;  // innermost (bound) dimension
  corner_t n1_;  // outer dimension
  std::vector<Elt> v_;  // row-major: v_[i1*n0_+i0]
 
  explicit Dense(corner_t n0, corner_t n1);
  explicit Dense(const Field& F);  // 1x1 zero-initialised array
  explicit Dense(corner_t n0, corner_t n1, const Elt p[], size_t ldp);
 
  // Return the element at flat index j.
  Elt at(corner_t j) const;
 
  // Bind the innermost variable to r; halves n0_ in place.
  void bind(const Elt& r, const Field& F);
  void bind(const Elt& r, const Dense& in, const Field& F);
  void bind_all(size_t logv, const Elt r[/*logv*/], const Field& F);
 
  // Reshape: requires n0_ == 1; splits the outer dimension.
  void reshape(corner_t n0);
 
  // Only valid after full binding (n0_ == 1 && n1_ == 1).
  Elt scalar();
 
  std::unique_ptr<Dense> clone() const;
};

`Sparse<Field>`


template <class Field>
class Sparse {
 public:
  // Each nonzero entry in the sparse hypercube.
  struct corner {
    size_t p0, p1, p2;
    typename Field::Elt v;
  };
 
  index_t n_;          // number of active corners
  std::vector<corner> c_;  // corner storage (size n_)
 
  explicit Sparse(index_t n);
 
  void canonicalize(const Field& F);  // sort + coalesce duplicate corners
  void bind(const Elt& r, const Field& F);
  void bind_all(size_t logv, const Elt r[/*logv*/], const Field& F);
  void reshape();
 
  // Only valid after full binding (n_ == 1 with all indices zero).
  Elt scalar();
 
  // Cloning is restricted to tests.
  std::unique_ptr<Sparse> clone_testing_only() const;
};

Affine combinators (`affine.h`)


template <class Field>
typename Field::Elt
affine_interpolation(Elt r, Elt f0, Elt f1, const Field& F);
 
template <class Field>
typename Field::Elt
affine_interpolation_z_nz(Elt r, Elt f1, const Field& F);
 
template <class Field>
typename Field::Elt
affine_interpolation_nz_z(Elt r, Elt f0, const Field& F);

`Eq<Field>`, `Eqs<Field>` (`eq.h`, `eqs.h`)

Eq<Field> is entirely stateless — no constructor, no data members, O(1) space:


template <class Field>
class Eq {
 public:
  // Compute EQ[I, J] over logn rounds for an n-element domain.
  // I[0..logn) and J[0..logn) are the two points in bit-decomposed form.
  static Elt eval(size_t logn, corner_t n,
                  const Elt I[/*logn*/], const Elt J[/*logn*/],
                  const Field& F);
};

Eqs<Field> is the stateful companion — a subclass of Dense<Field> that pre-computes and stores EQ[I, j] for all j at a single fixed point I:


template <class Field>
class Eqs : public Dense<Field> {
 public:
  // Pre-compute EQ[I, j] for all 0 <= j < n, given I[0..logn).
  Eqs(size_t logn, corner_t n, const Elt I[/*logn*/], const Field& F);
 
  corner_t n() const;  // returns n0_ (number of stored values)
 
  // Return a raw vector eq[i] = EQ(G0,i) + alpha * EQ(G1,i) for all i < n.
  static std::vector<Elt> raw_eq2(size_t logn, corner_t n,
                                  const Elt* G0, const Elt* G1,
                                  const Elt& alpha, const Field& F);
};

Memory and binding order

For a Dense with dimensions (n0, n1) consumed by the standard sumcheck round loop:

Peak memory: n0 · n1 field elements at round 0.
After k rounds: (n0 / 2^k) · n1 field elements.
Total arithmetic: \sum_{k} (n0 / 2^k) · n1 = 2 · n0 · n1 \cdot \text{Field op cost}.

Bindings run from innermost (log_w for circuit width) outward (log_c for copy count) in prover_layers.h. Mixing that order breaks the layer’s multilinear structure.

See it used

longfellow-zk/lib/arrays/dense_test.cc — dense_test.cc
longfellow-zk/lib/arrays/sparse_test.cc — sparse_test.cc
longfellow-zk/lib/sumcheck/prover_layers.h — uses Dense and Eq through the entire layered loop.

Sumcheck — the main consumer.
Prime Fields — supplies the element type.
Interpolation — the polynomial companion to these containers.

Arrays

When to reach for it

Design overview

API surface

Dense<Field>

Sparse<Field>

Affine combinators (affine.h)

Eq<Field>, Eqs<Field> (eq.h, eqs.h)