Struct LogUpGadget 

pub struct LogUpGadget;

Core LogUp gadget implementing lookup arguments via logarithmic derivatives.

The LogUp gadget transforms the multiplicative lookup constraint:

∏(α - a_i)^(m_i) = ∏(α - b_j)^(m'_j)

Into an equivalent additive constraint using logarithmic differentiation:

∑(m_i/(α - a_i)) = ∑(m'_j/(α - b_j))

This is implemented using a running sum auxiliary column s that accumulates:

s[i+1] = s[i] + ∑(m_a/(α - a)) - ∑(m_b/(α - b))

Note that we do not differentiate between a and b in the implementation: we simply have a list of elements with possibly negative multiplicities.

Constraints are defined as:

• Initial Constraint: s[0] = 0
• Transition Constraint: s[i+1] = s[i] + contribution[i]
• Final Constraint: s[n-1] + contribution[n-1] = 0

Implementations

impl LogUpGadget

pub const fn new() -> Self

Creates a new LogUp gadget instance.

Trait Implementations

impl Clone for LogUpGadget

fn clone(&self) -> LogUpGadget

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for LogUpGadget

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for LogUpGadget

fn default() -> LogUpGadget

Returns the “default value” for a type.

impl LookupEvaluator for LogUpGadget

fn eval_local_lookup<AB>(&self, builder: &mut AB, context: &Lookup<AB::F>)

where AB: PermutationAirBuilder,

Mathematical Details

The constraint enforces:

∑_i(multiplicities[i] / (α - combined_elements[i])) = 0

where multiplicities can be negative, and combined_elements[i] = ∑elements[i][n-j] * β^j.

This is implemented using a running sum column that should sum to zero.

fn eval_global_update<AB>( &self, builder: &mut AB, context: &Lookup<AB::F>, expected_cumulated: AB::ExprEF, )

where AB: PermutationAirBuilder,

Mathematical Details

The constraint enforces:

∑_i(multiplicities[i] / (α - combined_elements[i])) = `expected_cumulated`

where multiplicities can be negative, and combined_elements[i] = ∑elements[i][n-j] * β^j.

expected_cumulated is provided by the prover, and the sum of all expected_cumulated for this global interaction should be 0. The latter is checked as the final step, after all AIRS have been verified.

This is implemented using a running sum column that should sum to expected_cumulated.

fn num_aux_cols(&self) -> usize

Returns the number of auxiliary columns needed by this lookup protocol.

fn num_challenges(&self) -> usize

Returns the number of challenges for each lookup argument.

fn eval_lookups<AB>(&self, builder: &mut AB, contexts: &[Lookup<AB::F>])

where AB: PermutationAirBuilder,

Evaluates the lookup constraints for all provided contexts.

impl LookupGadget for LogUpGadget

fn constraint_degree<F: Field>(&self, context: &Lookup<F>) -> usize

We need to compute the degree of the transition constraint, as it is the constraint with highest degree: (s[n + 1] - s[n]) * common_denominator - numerator = 0

But in common_denominator, each combined element e_i = ∑e_{i, j} β^j contributes (α - e_i). So we need to sum the degree of all combined elements to find the degree of the common denominator.

numerator = ∑(m_i * ∏_{j≠i}(α - e_j)), where the e_j are the combined elements. So we have to compute the max of all m_i * ∏_{j≠i}(α - e_j).

The constraint degree is then: 1 + max(deg(numerator), deg(common_denominator))

fn verify_global_final_value<EF: Field>( &self, all_expected_cumulative: &[EF], ) -> Result<(), LookupError>

Evaluates the final cumulated value over all AIRs involved in the interaction, and checks that it is equal to the expected final value.

fn generate_permutation<SC: StarkGenericConfig>( &self, main: &RowMajorMatrix<Val<SC>>, preprocessed: &Option<RowMajorMatrix<Val<SC>>>, public_values: &[Val<SC>], lookups: &[Lookup<Val<SC>>], lookup_data: &mut [LookupData<SC::Challenge>], permutation_challenges: &[SC::Challenge], ) -> RowMajorMatrix<SC::Challenge>

Generates the permutation matrix for the lookup argument.