Skip to main content
Multilinear extensions (MLEs) are the central data structure in sumcheck-based proof systems like Jolt. They provide a way to represent discrete functions over the boolean hypercube as smooth polynomials over a field.

​
Definition

A function f ⁣:{0,1}v→Ff \colon \{0,1\}^v \to \mathbb{F} defined on the vv-dimensional boolean hypercube has a unique multilinear extension (MLE) f~ ⁣:Fv→F\tilde{f} \colon \mathbb{F}^v \to \mathbb{F}: the unique polynomial of degree at most 1 in each variable that agrees with ff on all 2v2^v boolean inputs. Concretely, the MLE is defined as: f~(x1,…,xv)=∑b∈{0,1}vf(b)⋅∏i=1v(bi⋅xi+(1−bi)(1−xi))\tilde{f}(x_1, \dots, x_v) = \sum_{b \in \{0,1\}^v} f(b) \cdot \prod_{i=1}^{v} \bigl(b_i \cdot x_i + (1 - b_i)(1 - x_i)\bigr) The product term ∏i=1v(bi⋅xi+(1−bi)(1−xi))\prod_{i=1}^{v} \bigl(b_i \cdot x_i + (1 - b_i)(1 - x_i)\bigr) is the equality polynomial eq~(x,b)\widetilde{\textsf{eq}}(x, b), which equals 1 when x=bx = b on the boolean hypercube and interpolates smoothly elsewhere.

​
Role in Jolt

MLEs are used throughout Jolt’s proving system:
  • The sumcheck protocol operates over multilinear polynomials
  • Essentially all witness data in Jolt is represented as MLEs
  • Committed polynomials in the execution trace are MLEs

​
Representation

An MLE over vv variables is stored as a vector of n=2vn = 2^v evaluations over the boolean hypercube {0,1}v\{0,1\}^v. The ii-th entry of this vector stores f(b)f(b) where bb is the binary representation of ii. Indexing convention: Jolt uses big-endian indexing, where the most significant bit of ii corresponds to x1x_1.

​
Variable Binding

Given f~(x1,…,xv)\tilde{f}(x_1, \dots, x_v) represented by n=2vn = 2^v evaluations, binding the most significant variable to a challenge r∈Fr \in \mathbb{F} produces a new MLE f~′(x2,…,xv)=f~(r,x2,…,xv)\tilde{f}'(x_2, \dots, x_v) = \tilde{f}(r, x_2, \dots, x_v) represented by n/2n/2 evaluations. For each index i∈{0,…,n/2−1}i \in \{0, \dots, n/2 - 1\}: E′[i]=E[i]+r⋅(E[i+n/2]−E[i])E'[i] = E[i] + r \cdot (E[i + n/2] - E[i]) where E[i]=f~(0,b)E[i] = \tilde{f}(0, b) and E[i+n/2]=f~(1,b)E[i + n/2] = \tilde{f}(1, b) for the same suffix bb. This operation takes a single O(n)O(n) pass through the evaluation vector.

​
Binding Order

Which variable gets bound in each round is determined by the BindingOrder:
  • HighToLow: Most significant variable first (pairs left/right halves)
  • LowToHigh: Least significant variable first (pairs even/odd entries)
For LowToHigh binding, the formula becomes: E′[i]=E[2i]+r⋅(E[2i+1]−E[2i])E'[i] = E[2i] + r \cdot (E[2i+1] - E[2i])

​
Implementation in Jolt

The MLE implementations live in jolt-core/src/poly/. All are unified under the MultilinearPolynomial<F> enum, which dispatches binding and evaluation to the appropriate concrete type.

​
DensePolynomial

DensePolynomial<F> is the straightforward representation: a Vec<F> of 2v2^v field elements. This is the baseline MLE type used when coefficients are full-sized field elements. Binding operates in-place on the evaluation vector: 
// HighToLow order
let (left, right) = self.Z.split_at_mut(n);
left.iter_mut().zip(right.iter()).for_each(|(a, b)| {
    *a += r * (*b - *a);
});

// LowToHigh order
for i in 0..n {
    self.Z[i] = self.Z[2 * i] + r * (self.Z[2 * i + 1] - self.Z[2 * i]);
}
Both orders have parallel variants (bind_parallel) using Rayon for performance.

​
CompactPolynomial

CompactPolynomial<T, F> stores coefficients as small scalars of type T (such as bool, u8, u16, u32, u64, u128, i64, i128) rather than full field elements. This is the “pay-per-bit” representation that makes Dory commitments efficient. The polynomial maintains two storage vectors:
  • coeffs: Vec<T> - Original small-scalar coefficients (immutable after construction)
  • bound_coeffs: Vec<F> - Field elements materialized lazily on the first bind
On the first bind, coefficients are promoted from small scalars to field elements using overflow-safe arithmetic: 
// For a pair (a, b) of small scalars:
match a.cmp(&b) {
    Ordering::Equal => a.to_field(),
    Ordering::Less  => a.to_field() + r * (b - a).to_field(),
    Ordering::Greater => a.to_field() - r * (a - b).to_field(),
}
After this first bind populates bound_coeffs, subsequent binds operate on field elements identically to DensePolynomial.

​
Specialized Representations

Jolt includes several specialized MLE types that exploit structure in witness polynomials:
  • OneHotPolynomial: Stores only the index of the single nonzero entry per cycle rather than a dense vector of 0s and 1s. Used for read/write address polynomials.
  • RaPolynomial: A state machine that lazily materializes address polynomials across sumcheck rounds, keeping memory proportional to the address-space size rather than full trace length until final rounds.
  • RLCPolynomial: Represents a random linear combination of multiple polynomials. Dense components are eagerly combined; one-hot components are combined lazily during evaluation.
  • EqPolynomial: The equality MLE eq~(r,⋅)\widetilde{\textsf{eq}}(r, \cdot), commonly used as a building block in sumcheck and MLE evaluation.

​
The Equality Polynomial

The eq~\widetilde{\text{eq}} MLE is used throughout Jolt. It is the MLE of the function eq ⁣:{0,1}m×{0,1}m→F\text{eq} \colon \{0, 1\}^m \times \{0, 1\}^m \to \mathbb{F} defined as: eq(r,x)={1if r=x0otherwise\text{eq}(r,x) = \begin{cases} 1 & \text{if } r = x \\ 0 & \text{otherwise} \end{cases} The explicit formula for the MLE is: eq~(r,x)=∏i=1log⁡(m)(ri⋅xi+(1−ri)⋅(1−xi))\widetilde{\text{eq}}(r,x) = \prod_{i=1}^{\log(m)} (r_i \cdot x_i + (1 - r_i) \cdot (1 - x_i)) where r,x∈{0,1}log⁡(m)r, x \in \{0,1\}^{\log(m)}.

​
Further Reading

For a more formal introduction to multilinear extensions, see Section 3.5 of Proofs, Arguments, and Zero Knowledge by Justin Thaler.

Build docs developers (and LLMs) love

Get started for freeTalk to us