Refactor LogUp-GKR

[irakliyk]

Following up on some recent discussions, I think it would make sense to refactor how LogUp-GKR is integrated into this library. Specifically, instead of assuming that we are dealing with a generic GKR protocol, we should use a concrete implementation of the GKR-LogUp protocol. This means that Winterfell would contain the following:

• Implementations of GKR-LogUp prover/verifier (including the sum-check prover/verifier).
• Logic for building Lagrange kernel column and adding it to the auxiliary trace.
• Logic for building the s column (or the columns which can emulate the s column).

The handling/manipulation of Lagrange kernel column and the s column should be completely transparent to the user (i.e., the user should not need to know about them).

The LogUp-GKR prover/verifiers should be generic over LogUpGkrEvaluator which would describe the exact parameters and constraints for a LogUp-GKR instance. Conceptually, it could look like so:

pub trait LogUpGkrEvaluator {
    /// Defines the base field of the evaluator.
    type BaseField: StarkField;

    /// Public inputs need to compute the final claim.
    type PublicInputs: ToElements<Self::BaseField> + Send;

    /// Defines the query for this evaluator.
    ///
    /// This is intended to be a simple struct which would not require allocations.
    type Query<E: FieldElement<BaseField = Self::BaseField>>;

    /// Gets a list of all oracles involved in LogUp-GKR; this is intended to be used in construction of
    /// MLEs.
    fn get_oracles(&self) -> Vec<LogUpGkrOracle<Self::BaseField>>;

    /// Returns the number of random values needed to evaluate a query.
    fn get_num_rand_values() -> usize;

    /// Builds a query from the provided main trace frame and periodic values.
    ///
    /// Note: it should be possible to provide an implementation of this method based on the
    /// information returned from `get_oracles()`. However, this implementation is likely to be
    /// expensive compared to the hand-written implementation. However, we could provide a test
    /// which verifies that `get_oracles()` and `build_query()` methods are consistent.
    fn build_query<E>(&self, frame: &EvaluationFrame<E>, periodic_values: &[E]) -> Self::Query<E>
    where
        E: FieldElement<BaseField = Self::BaseField>;

    /// Evaluates the provided query and writes the results into the numerators and denominators.
    ///
    /// Note: it is also possible to combine `build_query()` and `evaluate_query()` into a single
    /// method to avoid the need to first build the query struct and then evaluate it. However:
    /// - We assume that the compiler will be able to optimize this away.
    /// - Merging the methods will make it more difficult avoid inconsistencies between
    ///   `evaluate_query()` and `get_oracles()` methods.
    fn evaluate_query<F, E>(
        &self,
        query: &Self::Query<F>,
        rand_values: &[E],
        numerator: &mut [E],
        denominator: &mut [E],
    ) where
        F: FieldElement<BaseField = Self::BaseField>,
        E: FieldElement<BaseField = Self::BaseField> + ExtensionOf<F>;

    /// Computes the final claim for the LogUp-GKR circuit.
    ///
    /// The default implementation of this method returns E::ZERO as it is expected that the
    /// fractional sums will cancel out. However, in cases when some boundary conditions need to
    /// be imposed on the LogUp-GKR relations, this method can be overridden to compute the final
    /// expected claim.
    fn compute_claim<E>(&self, inputs: &Self::PublicInputs, rand_values: &[E]) -> E
    where
        E: FieldElement<BaseField = Self::BaseField>;
}

pub enum LogUpGkrOracle<E: StarkField> {
    CurrentRow(usize),
    NextRow(usize),
    PeriodicValue(Vec<E>),
}

Then, LogUp-GKR prove/verify functions could look something like:

/// This will likely be somewhere in the prover crate.
pub fn prove<E: FieldElement>(
    trace: &ColMatrix<E::BaseField>,
    evaluator: &impl LogUpGkrEvaluator<BaseField = E::BaseField>,
    public_coin: &mut impl RandomCoin<BaseField = E::BaseField>,
) -> (LogUpGkrProof, LogUpGkrRandElements<E>) {
    todo!("implement")
}

/// This will likely be somewhere in the verifier crate.
fn verify<E: FieldElement>(
    proof: &LogUpGkrProof,
    evaluator: &impl LogUpGkrEvaluator<BaseField = E::BaseField>,
    public_coin: &mut impl RandomCoin<BaseField = E::BaseField>,
) -> Result<LogUpGkrRandElements <E>, VerifierError> {
    todo!("implement")
}

An open question is how LogUpGkrEvaluator integrates into the Air trait. A couple of options that come to mind:

We could make Air trait imply LogUpGkrEvaluator trait - e.g., something like this:

pub trait Air:
     LogUpGkrEvaluator<BaseField = Self::BaseField, PublicInputs = Self::PublicInputs>     
    + Send
    + Sync 
{

}

We could make LogUpGkrEvaluator an associated type of the Air trait - e.g., something like this:

pub trait Air: Send + Sync {

  type LogUpGkrEvaluator: LogUpGkrEvaluator<BaseField = Self::BaseField, PublicInputs = Self::PublicInputs>;

}

These approaches probably have their own pros and cons, and also there may be a different approach altogether. So, I think it will require a bit of experimentation to figure out what works best.

Also, there are probably quite a few structs/functions which are shared across LogUp-GKR prover/verifier. Some of them could naturally go into the math crate (e.g., MultiLinearPoly, inner_product()), but others may not fit there. So, we may consider creating a separate crate for these (e.g., winter-sumcheck) or some of them may naturally fit into the air crate (e.g., LogUpGkrRandElements, LogUpGkrProof).