Note for bus in stwo 2 - Shuang's Crypto Notes

continue from this blog

Table of Contents

Another thought: proving everying thing together and logup by stwo as extra.

Building LogUp trace

basic steps:

logup trace generator, size is determined.

let mut logup_gen = LogupTraceGenerator::new(log_size);

generate columns that is associated with this logup trace generator

let mut col_gen = logup_gen.new_col();

write fraction, building accumulator column

for vec_row in 0..(1 << (log_size_payload - LOG_N_LANES)) {
                let p = bitreverse_multiplicity_col.data[vec_row];
                let left_values: Vec<PackedM31> = left_cols
                    .iter()
                    .map(|col| col.data[vec_row]) // Extract data at vec_row
                    .collect();
                let q: PackedSecureField = lookup_elements.combine(&left_values);

                col_gen.write_frac(vec_row, p.into(), q);
            }

finalized col

logup_gen.finalize_last();

Notes on Logup trace generation

the columns that are associated to a Logup trace generator is the columns that in one logup proof, namely, they belongs to the same relation to give a logup proof, in powdr setting, this means the columns should include all the payloads in the same bus id.
logup_gen.finalize_last() outputs (trace, sum), trace is of this form

ColumnVec<CircleEvaluation<SimdBackend, BaseField, BitReversedOrder>>

it is the witness columns that can be added directly to tree_builder.extend_evals(), like how the constant columns and stage 0 witnesses are built

you can build logup trace with different size, each logup trace is a relationship, at the end append all the ColumnVec generated together, and the same as other witness columns, append them to a tree builder and commit.

Refactoring: give up logupAtRow that is defined by stwo, using its essential constraint constraint construction for extension field

notes for the reason of the refactoring:

LogupAtRow limitation: one logup relation one machine

logupAtRow – which is used by adding logup constraint by:

 eval.add_to_relation(0,RelationEntry::new(
                        &self.lookup_elements,
                        multiplicity.into(),
                        &payload,
                    ));

— it can only has one logup per machine, as how the logup is built here:

from above, with one trace (built for one merkle tree), it iterator all the columns apart from the last, to add a constraint, it consider these columns should represent the same thing, and the last batch column is different, and the last one create one extension columns with offset [-1,0], no matter how many logup relationship you want to build, it only build build one extension field with [-1,0]

so if use LogupAtRow from stwo, only one logup relation is accepted by a machine.

loguAtRow essentially use the eval.add_constraint, the same interface to build constraint for original field, but the return is extension field, this is the generic type that add_constraint function can accept.

so I can just build extension columns and constraint for them as

// build columns that contains elements in extension field
let frac_column=eval.next_extension_interaction_mask(4, [0]);

eval.add_constraint::<<E as EvalAtRow>::EF>(frac_column[0].clone() -multiplicity_ef);

one bus need one merkle tree, and one interation index.