Skip to content

Populating Columns

What it takes to make the witness

Once a column is declared, the prover can populate the column with data. When populating a committed column the prover is free to supply arbitrary values. When populating a virtual column, however, the prover must follow the definition of the virtual column in terms of other columns and supply the correct values.

Only the prover (not the verifier) will fill columns with data, and only the prover will have access to the witness to do so. Accessing the witness can be done in a block of the form

if let Some(witness) = builder.witness() {
    // work with witness to populate columns
}

Everything done to populate columns takes place in such a code block.

To initialize the data for a declared column we call new_column on the witness, passing in the oracle id for the column and the tower level type parameter. The unique tower level type parameter with which the column was declared is expected here, it is not a free type parameter. For example, to create the column for the transparent oracle declared on the previous page, we write

let mut entry_builder = witness.new_column::<BinaryField16b>(transparent);

upon which a new vector of data is created and made accessible through this entry_builder. We can cast the column into a mutable slice of a desired type, type u8 for example, as

let mut_slice = entry_builder.as_mut_slice::<u8>();

Lastly we can populate this mutable slice, and for the case of transparent which is supposed to contain consecutive powers of BinaryField16b multiplicative generator gen, we do so as follows. Rather than casting to u8 values, we'll actually simply cast into BinaryField16b values by omitting the type parameter. Then we'll iterate across the slice computing and writing consecutive powers.

entry_builder.as_mut_slice()
    .iter_mut()
    .zip(std::iter::successors(Some(base), |&prev| Some(prev * base)))
    .for_each(|(dest, src)| *dest = src);

This process works fine when we are populating committed and transparent columns. When we are populating virtual columns we may not have the values of the dependency oracles immediately available. Even if we did, it is good practice to access them through the witness assuming the dependency columns are already populated. The witness contains an entry for every column created, and we can access the relevant entry to get access to the values of the corresponding column.

Suppose we need to read the values underlying transparent in order to populate some dependent virtual oracle. Then we create a witness_entry to give us access to the transparent oracle.

let witness_entry = witness.get::<BinaryField16b>(transparent)?;

Given the witness entry, there are a couple ways to access the underlying data. We can cast into a slice of type T if T implements Pod.

let u16_vals = witness_entry.as_slice::<u16>();

Or we can cast into a slice of packed field elements as

let packed_b16_vals: &[PackedType<U, BinaryField16b>] = witness_entry.packed();

where the type annotation is only for clarity. There is also another way to access the packed values. We can access them as packed but over an extension field. Doing so is called repacking the values.

let repacked: &[PackedType<U, BinaryField64b>] = witness_entry.repacked::<BinaryField64b>();

Here we have repacked the values underlying transparent from BinaryField16b packed elements into BinaryField64b packed elements.

To demonstrate where repacking is useful, suppose we wish to take oracle transparent with values in BinaryField16b and create a packed virtual oracle with values in BinaryField64b.

let packed_transparent = builder.add_packed("packed_transparent", transparent, 2);

Instead of creating a new column for packed_transparent and copying over the data underlying transparent, we can take that data already available in repacked, and use the witness set method to assign this repacked data to packed_transparent.

witness.set::<BinaryField64b>(repacked);

In practice, populating columns is the more cumbersome side of constraint programming. Programming the constraints themselves is more convenient as we explore next.