Sector Layer Frontend Tutorial

To express structured layer-wise relationships in Remainder, we can use a Structured GKR Layer, a.k.a "Sector" layer. A Sector layer is defined through an AbstractExpression<F> type, also simply called "Expression" in this tutorial. Expressions can be built by combining MLEs. To refer to an MLE we use the NodeRef<F> values returned by the circuit builder when the respective MLE was added. MLEs can be combined through overloaded binary operators (currently available are +, -, * for addition, subtraction and multiplication respectively), or using a Selector.

Let's walk through a few examples of the usage of Sector layers using Remainder circuit building interface.

Example 1: Multiplying two MLEs

We start with a simple circuit that multiplies two MLEs element-wise: an MLE $V_{1} (z_{0}, z_{1})$ with evaluations (over the boolean hypercube) $[a, b, c, d]$ with an MLE $V_{2} (z_{0}, z_{1})$ with evaluations $[e, f, g, h]$ , to produce the MLE $V_{3} (z_{0}, z_{1}) = V_{1} (z_{0}, z_{1}) \cdot V_{2} (z_{0}, z_{1})$ with evaluations $[a \cdot e, b \cdot f, c \cdot g, d \cdot h]$ .

To express this in Remainder, we can simply write:

#![allow(unused)]
fn main() {
/* ... define the input layer `input_layer` ... */

// Define the input shreds for `V_1` and `V_2`.
let v1 = builder.add_input_shred("MLE 1", 2, &input_layer);
let v2 = builder.add_input_shred("MLE 2", 2, &input_layer);

// Define the Sector layer that performs the multiplication operation.
let v3 = builder.add_sector(v1 * v2); 
}

In this example the input MLEs to the Sector were input shreds, but in general they can be any node appearing in the circuit. We can, for example, follow the above code segment with:

#![allow(unused)]
fn main() {
let v4 = builder.add_sector(&v3 * &v3);
}

which squares the entries of the MLE $V_{3}$ .

Implmentation Note: The reason we're borrowing v3 is an unfortunate quirk of the way the NodeRef<F> type is implemented. It is a wrapper around a weak pointer, and thus not Copy-able. This means that the multiplication operator will try to take ownership of its two operands, and after the first occurance of v3 has moved, the second one will fail with a compile error. To avoid unneseccary cloning, we provide an implementation of the Mul trait for borrowed operands as well (e.g. &NodeRef<F>) to allow developers to use the succinct borrowed syntax we presented above when there is a need to reuse NodeRef<F>s.

Expressions may be combined into a single Sector layer. For example, previously we expressed the relation $V_{4} (z_{0}, z_{1}) = (V_{1} (z_{0}, z_{1}) * V_{2} (z_{0}, z_{1}))^{2}$ using two layers, but we could have equivalently written:

#![allow(unused)]
fn main() {
let v4 = builder.add_sector( (&v1 * &v2) * (&v1 * &v2) );
}

See run_example_1a() in frontend/examples/sector.rs for the full code of the preceeding examples.

Efficiency Note: It's important to note that the two alternative ways of defining v4 presented above result in different circuits, even though they're semantically equivalent. The circuit's structure (number of layers, expression structure etc.) can affect the prover/verifier runtime. Refer to Section 3: GKR Theory for more information.

What would happen if we tried to multiple two MLEs of different sizes? You might expect that element-wise operations are not well defined if the two MLEs are not of the same size, but there is a mathematically natural interpretation for such a formula, which we adopt in Remainder.

Let $V_{1} (z_{0}, z_{1})$ be an MLE on two variables, and $V_{2} (z_{0})$ be an MLE on only one variable. One natural interpretation for the expression $V_{1} \cdot V_{2}$ is an MLE $V_{3} (z_{0}, z_{1})$ on two variables defined by $V_{3} (z_{0}, z_{1}) = V_{1} (z_{0}, z_{1}) \cdot V_{2} (z_{0})$ , i.e. equating the common MLE variables starting from the left.

Viewing the MLEs as evaluation vectors, if $V_{1} = [a, b, c, d]$ and $V_{2} = [e, f]$ , then $V_{3} = [a \cdot e, b \cdot e, c \cdot f, d \cdot f]$ .

See run_example_1b() in frontend/examples/sector.rs for a working example.

Example 2: Spliting MLEs

Recall the first example of a Structured layer we saw in Section 3.1 which performed the operation $V_{2} (z_{0}, z_{1}) = V_{1} (0, z_{0}, z_{1}) \cdot V_{1} (1, z_{0}, z_{1})$ on the 3-variable MLE $V_{1}$ with evaluations $[a, b, c, d, e, f, g, h]$ to produce $[a \cdot e, b \cdot f, c \cdot g, d \cdot h]$ .

With what we've seen so far, it's not clear how to express this relation in Remainder. If we have a NodeRef<F> instance for the $V_{1}$ MLE, it refers by default to the entire MLE. But here, we'd like to refer to a subset of that MLE, in particular one for which a prefix of its variables has been fixed to a certain binary string.

Remainder provides a special kind of node to be used during circuit creation to take any node refering to an MLE $V (z_{0}, z_{1}, \dots, z_{n - 1})$ and generate $2^{k}$ NodeRef<F> instances refering to the MLEs $V (k 0, \dots, 0, 0, z_{0}, \dots, z_{n - k - 1}), V (k 0, \dots, 0, 1, z_{0}, \dots, z_{n - k - 1}), \dots, V (k 1, \dots, 1, 1, z_{0}, \dots, z_{n - k - 1})$ for any integer $1 \leq k \leq n$ . Conceptually, a Split node is splitting the MLE's evaluation table into $2^{k}$ parts which can be referenced separately.

Having this tool handy, we can now implement the example from Section 3.1 as follows:

#![allow(unused)]
fn main() {
// The Input MLE [a, b, c, d, e, f, g, h].
let mle = builder.add_input_shred("Input MLE", 3, &input_layer);

// Split the MLE into two halves (k = 1): left = [a, b, c, d] and right = [e, f, g, h].
let [left, right]: [_; 2] = builder.add_split_node(&mle, /* k = */ 1).try_into().unwrap();

// Multiply the two halves together using a sector node and the expression `left * right`,
// producing the output MLE [a*e, b*f, c*g, d*h].
let sector = builder.add_sector(left * right);
}

You can see a full working example in run_example_2() in frontend/examples/sector.rs.

Efficiency Note: A Split node does not get compiled into a GKR layer. It's a construct used only during circuit building to do all the necessary bookkeeping.

Example 3: Using constants in Expressions.

We've seen how to write expressions involving MLEs, but sometimes it's also useful to include constants from the field $F$ we're operating on. For example, the expression $V_{3} (z_{0}, z_{1}) = V_{1} (z_{0}, z_{1}) + 42 \cdot V_{2} (z_{0}, z_{1})$ is a valid Structured layer relationship.

We can express the multiplication by a constant above simply by multiplying v2: NodeRef<F> with a value F::from(42) of type F:

#![allow(unused)]
fn main() {
/* ... create nodes for `v1` and `v2` ... */

let v3 = builder.add_sector(v1 + v2 * F::from(42));
}

It's important to note here that the multiplication needs to happen with the constant on the right. The compiler would reject the expression F::from(42) * v2 in the above context. This is due to subtle quirk of how Rust's operator overloading interracts with Rust's rule of forbidding the implementation of external traits for externals types: in this case F may be a field type defined outside the Remainder crate and std::ops::Mul, an external trait, cannot be implemented for it inside the Remainder crate.

See run_example_3() in frontend/examples/sector.rs for a full working example.

Note: It is also possible to express this relation by adding a constant MLE $V_{const, 42}$ (on zero variables) with evaluation table equal to $[42]$ , and thus expressing $V_{3}$ as: $V_{3} (z_{0}, z_{1}) = V_{1} (z_{0}, z_{1}) + V_{const, 42} () \cdot V_{2} (z_{0}, z_{1})$ . Essentially treating the constant as an input parameter. However this can be inefficient since it complicates the expression to be proven (potentially affecting the prover's/verifier's runtime), as well as increases the size of the generated proof because all the constant values would need to be included in the transcript.

Exmaple 4: Using Selectors in Expressions.

"Selectors", introduced in Section 3.1, are a a structured way to express certain "if-then-else" expressions inside a circuit.

Recall the following linear expression we used as an example in Section 3.1:

$V_{2} (z_{0}, z_{1}) = (1 - z_{0}) \cdot V_{1} (0, z_{1}) \cdot V_{1} (0, z_{1}) + z_{1} \cdot 2 \cdot V_{1} (1, z_{1})$

We argued it represents the transformation $[a, b, c, d] \to [a^{2}, b^{2}, 2 c, 2 d]$ , where each entry of the output MLE is either the square or the double the respective entry of the input MLE, and the choice of operation depends on the index of the value in the evaluation table of the output MLE.

The general construct $(1 - z_{0}) \cdot E_{1} + z_{0} \cdot E_{2}$ , where $E_{1}, E_{2}$ are arbitrary expressions, can be expressed in Remainder using the macro sel_expr!(E_1, E_2) for E_1, E_2: AbstractExpression<F>. The macro produces an expression, which can directly be fed into a Sector node.

All that remains is to use a Split node to get node references to V_1(0, z_1) and V_1(1, z_1), and we can implement $V_{2}$ as:

#![allow(unused)]
fn main() {
/* ... create a node for `v1` ... */

// Split V1 into V1_l(z_1) = V1(0, z_1) and V1_r(z_1) = V1(1, z_1).
let [v1_l, v1_r]: [_; 2] = builder.add_split_node(&v1, 1).try_into().unwrap();

// Selector layer.
let v2 = builder.add_sector(sel_expr!(&v1_l * &v1_l, &v1_r * F::from(2)));
}

See run_example_4() in frontend/examples/sector.rs for a full working example.

The Remainder Book

Sector Layer Frontend Tutorial

Example 1: Multiplying two MLEs

Example 2: Spliting MLEs

Example 3: Using constants in Expressions.

Exmaple 4: Using Selectors in Expressions.