Function kimchi::circuits::lookup::constraints::aggregation

pub fn aggregation<R, F>(
    dummy_lookup_value: F,
    joint_lookup_table_d8: &Evaluations<F, D<F>>,
    d1: D<F>,
    gates: &[CircuitGate<F>],
    witness: &[Vec<F>; 15],
    joint_combiner: &F,
    table_id_combiner: &F,
    beta: F,
    gamma: F,
    sorted: &[Evaluations<F, D<F>>],
    rng: &mut R,
    lookup_info: &LookupInfo,
    zk_rows: usize
) -> Result<Evaluations<F, D<F>>, ProverError>where
    R: Rng + ?Sized,
    F: PrimeField,

Computes the aggregation polynomial for maximum n lookups per row, whose kth entry is the product of terms

(gamma(1 + beta) + t_i + beta t_{i+1}) \prod_{0 <= j < n} ( (1 + beta) (gamma + f_{i,j}) )

\prod_{0 <= j < n+1} (gamma(1 + beta) + s_{i,j} + beta s_{i+1,j})

for i < k.

t_i is the ith entry in the table, f_{i, j} is the jth lookup in the ith row of the witness

for every instance of a value in t_i and f_{i,j}, there is an instance of the same value in s_{i,j} s_{i,j} is sorted in the same order as t_i, increasing along the ‘snake-shape’

whenever the same value is in s_{i,j} and s_{i+1,j}, that term in the denominator product becomes (1 + beta) (gamma + s_{i,j}) this will cancel with the corresponding looked-up value in the witness (1 + beta) (gamma + f_{i,j})

whenever the values s_{i,j} and s_{i+1,j} differ, that term in the denominator product will cancel with some matching (gamma(1 + beta) + t_{i’} + beta t_{i’+1}) because the sorting is the same in s and t. there will be exactly the same number of these as the number of values in t if f only contains values from t.

after multiplying all of the values, all of the terms will have cancelled if s is a sorting of f and t, and the final term will be 1 because of the random choice of beta and gamma, there is negligible probability that the terms will cancel if s is not a sorting of f and t

Panics

Will panic if final evaluation is not 1.