Support custom implementations of Trace LDE

[irakliyk]

Currently, Trace LDE is implemented as a concrete struct (see here). It might be good to instead define as a trait and provide a default implementation (similar to what we did with RandomCoin recently). Making it a trait would make the structure more flexible and allow for custom implementations of Trace LDE which might be more suitable for various use cases (i.e., long-running provers where memory may not need to be allocated/de-allocated all the time, or provers which outsource LDE computations to hardware etc.).

The trait could look something like this:

pub trait TraceLde {
    type BaseField: StarkField;
    type HashFn: ElementHasher<BaseField = Self::BaseField>;

    /// Takes main trace columns as input, interpolates them into polynomials in coefficient form,
    /// evaluates the polynomials over the LDE domain, and commits to the polynomial evaluations.
    ///
    /// Returns a tuple containing the column polynomials in coefficient from and the commitment
    /// to the polynomial evaluations over the LDE domain.
    fn set_main_trace(
        main_trace: &ColMatrix<Self::BaseField>,
    ) -> (ColMatrix<Self::BaseField>, <Self::HashFn as Hasher>::Digest);

    /// Takes auxiliary trace segment columns as input, interpolates them into polynomials in
    /// coefficient form, evaluates the polynomials over the LDE domain, and commits to the
    /// polynomial evaluations.
    ///
    /// Returns a tuple containing the column polynomials in coefficient from and the commitment
    /// to the polynomial evaluations over the LDE domain.
    fn add_aux_segment<E: FieldElement<BaseField = Self::BaseField>>(
        aux_trace: &ColMatrix<E>,
    ) -> (ColMatrix<E>, <Self::HashFn as Hasher>::Digest);

    /// Reads current and next rows from the main trace segment into the specified frame.
    fn read_main_trace_frame_into(
        &self,
        lde_step: usize,
        frame: &mut EvaluationFrame<Self::BaseField>,
    );

    /// Reads current and next rows from the auxiliary trace segment into the specified frame.
    fn read_aux_trace_frame_into<E: FieldElement<BaseField = Self::BaseField>>(
        &self,
        lde_step: usize,
        frame: &mut EvaluationFrame<E>,
    );

    /// Returns trace table rows at the specified positions along with Merkle authentication paths
    /// from the commitment root to these rows.
    fn query(&self, positions: &[usize]) -> Vec<Queries>;

    /// Returns the number of rows in the execution trace.
    fn trace_len(&self) -> usize;

    /// Returns blowup factor which was used to extend original execution trace into trace LDE.
    fn blowup(&self) -> usize;
}

Creating an instances of TraceLde would be handled by the prover. To do this, we'd need to add the following to the Prover trait:

pub trait Prover {
    ...
    type TraceLde: TraceLde<BaseField = Self::BaseField>,

    fn new_trace_lde(&self, trace_info: &TraceInfo, blowup: usize) -> Self::TraceLde;
}

This structure can be further improved by abstracting away evaluations frame behind an associated and replacing read_* methods with some sort of a frame iterator (which would be helpful for #80). But I'm leaving this for a separate issue.

[irakliyk]

Closed by #207.