Sum-check protocol

[Al-Kindi-0]

Describe your changes

Implements the sum-check protocol for use in the virtual bus as in #1182 .

Checklist before requesting a review

• Repo forked and branch created from next according to naming convention.
• Commit messages and codestyle follow conventions.
• Relevant issues are linked in the PR description.
• Tests added for new functionality.
• Documentation/comments updated according to changes.

[Al-Kindi-0]

I have addressed most of the feedback but for the ones related to the evaluation domain. The reason for this is that we will be moving to the coefficient in a subsequent PR and we can implement most of the feedback as part of that PR.

[plafer]

Should we just close in PR in favor of #1307?

[Al-Kindi-0]

The implementation has now moved to using the coefficient form for the round polynomial instead of the evaluation one. With this change, we avoid having to deal with evaluation domains. Also, regarding CompositionPolyQueryBuilder, I had to revert back to the previous implementation which had the trait generic over the field. The reason been that for the following typical use case, the previous approach didn't work as (maybe there is a workaround I am not aware of)

/// A [`FinalQueryBuilder`] for the sum-check verifier used for the final sum-check.
#[derive(Default)]
struct GkrMergeQueryBuilder<E> {
    gkr_eval_point: Vec<E>,
    merge_rand: Vec<E>,
}

impl<E: FieldElement> CompositionPolyQueryBuilder<E> for GkrMergeQueryBuilder<E> {
    fn build_query(&self, openings_claim: &FinalOpeningClaim<E>, evaluation_point: &[E]) -> Vec<E> {
        let eq_at_gkr_eval_point = EqFunction::new(self.gkr_eval_point.clone());
        let mut rand_sumcheck = self.merge_rand.clone();
        rand_sumcheck.extend_from_slice(evaluation_point);
        let eq = eq_at_gkr_eval_point.evaluate(&rand_sumcheck);
        let mut query = openings_claim.openings.clone();
        query.push(eq);
        query
    }
}

As for closing this PR, I agree. I think that there no outstanding comments left here. The review for the change to coefficient form could be done in the other PR.

[plafer]

Closing; let's move all discussion to #1307

[plafer]

Reopening - @Al-Kindi-0 could you merge your recent commits into #1307, and then close this one?

[Al-Kindi-0]

Reopening - @Al-Kindi-0 could you merge your recent commits into #1307, and then close this one?

Done! I will now close this.