Declaring Columns

The central objects of a constraint system

All data on which we impose constraints lives in columns. A column can contain arbitrary non-deterministic values decided by the prover. A column can contain values deterministically derived from other columns. The non-deterministic columns we call "committed" columns, while the deterministic columns we call "virtual" columns. Finally there's a third type of column called a "transparent" column that holds values not decided by the prover, not derived from other columns, but simply plain values already known by the verifier.

Every column has size some power of 2, and has values in some tower field. Along with a name, it is the logarithmic size of the column and the tower level of its values that defines the shape of the column.

We will use the terms "columns" and "oracles" interchangeably. The word "column" implies a matrix or table of values. Currently, however, we have no explicit notion of a table in the constraint system. Instead of creating an explicit table, we create a collection of columns all of the same height, and impose constraints on them, imagining if helpful that together these columns form a table.

We expand on the three types of columns and how to declare them.

Committed Columns

To declare a committed column we need a name (say my_col), a logarithmic size for the column (say n_vars), and a tower level (say BinaryField32b::TOWER_LEVEL). Then we write

let oracle = builder.add_committed("my_col", n_vars, BinaryField32b::TOWER_LEVEL);

where oracle is the usize value identifying the column. To add multiple committed columns at once there's the builder method add_committed_multiple. All we've done is declared that a column of this shape will be committed by the prover. The prover will still need to populate the column with values.

Virtual Columns

To declare a virtual column we must specify from which previously declared columns it is derived, and exactly how it is (deterministically) derived.

Binius currently supports six types of virtual oracles, and each one can be created by calling a method on the builder passing in the dependency oracles and relevant metadata.

Linear combination with or without offset. Builder methods add_linear_combination and add_linear_combination_with_offset create a new oracle by taking a list of oracle, coefficient pairs (and optionally an offset). While the coefficients live in F, the linear combination oracle is regarded to live in the smallest subfield that can fit all input oracles and all input coefficients. For example, if we write
```
let linear_comb = builder.add_linear_combination(
    "linear comb",
    n_vars,
    [(oracle_1, F::one()), (oracle_2, F::one())],
);
```
then the oracle linear_comb will be the sum of oracles oracle_1 and oracle_2 and be located in whichever field is larger between those of these two oracles.
Packed. Packing means a column in one tower field is transformed into a column over a larger tower field, where every block of adjacent 1 << log_degree elements of the small tower in the unpacked column are regarded as one element of the large tower in the packed column. The packed column is 1 << log_degree times smaller in height than the unpacked column, but has elements 1 << log_degree times larger than those of the unpacked column.

Suppose we have an oracle bits that takes values in BinaryField1b, and we wish to pack every adjacent 32 bits into one BinaryField32b element. Then we can write
```
let packed = builder.add_packed("32-bit packed", bits, 5);
```
Projected. Projection means that we interpret a column as a multilinear polynomial and we plug in arguments for a subset of the variables. In other words, we partially evaluate the polynomial. We don't, however, allow an arbitrary subset of variables to be set, but rather limit to the first variables or the last variables in the list of multilinear polynomial variables. For example, suppose we wish to take a column whole_col and project to the second quarter of the column to get a new column second_quarter_col of one fourth the height. We can do so with
```
let second_quarter_col = builder.add_projected(
    "second_quarter_col",
    whole_col,
    vec![F::zero(), F::one()],
    ProjectionVariant::LastVars,
);
```
Repeated. We can take one column base and create a larger column by concatenating together many copies of the base column. Here we'll create a repeated column with eight (1 << 3) copies of base.
```
let repeated = builder.add_repeating("repeated", base, 3)
```
Shifted. Shifting means we take a column, chop it up into blocks of a certain size, and shift each block by a certain amount. Shifting has three variants: logical left, logical right, and circular left. A circular right shift can be achieved by a circular left shift.

Suppose we wish to split into blocks of size 32 bits, and shift each block logically left by 1 bit. Doing so can be seen as treating each block as a 32-bit integer and multiplying it by 2 modulo 1 << 32.
```
let shifted = builder.add_shifted("shifted", base, 1, 5, ShiftVariant::LogicalRight);
```
ZeroPadded. Zero padding naturally means taking one column and padding it with zero values to a potentially larger column. For an oracle unpadded we can pad it up to size 1 << n_vars provided this size is at least the size of the un-padded oracle.
```
let padded = builder.add_zero_padded("padded", unpadded, n_vars);
```

For details on creating virtual polynomials, for example to see what checks are applied to parameters, see MultilinearOracleSet.

Transparent Columns

Transparent columns are columns known to the verifier. Whereas committed and virtual columns are opaque and the verifier holds only a "handle" to them via commitments, transparent columns are fully transparent to the verifier.

There are many specialized transparent constructions in Binius transparents that are easily created. For example, suppose we wish to take a field element and create a column with values had by taking consecutive powers of the elements. The transparent powers lets us do this.

Suppose we choose the element to be the generator gen of the multiplicative group of the field BinaryField16b.

let gen = BinaryField16b::MULTIPLICATIVE_GENERATOR;

For column log size n_vars we make

let powers = binius_core::transparent::powers::Powers::new(
    n_vars,
    gen.into(),
);

and then declare the transparent polynomial passing in our powers object.

let transparent = builder.add_transparent("powers of B16 gen", powers)?;

This transparent oracle can now appear in constraints. Here we have created a structured transparent oracle using Binius transparents. See making transparents for the case of making an unstructured transparent oracle filled with arbitrary values.