Module sumcheck 

Contains cryptographic algorithms for going through the sumcheck protocol in the context of a GKR prover.

Let P: F^n -> F denote the polynomial Expression used to define some GKR Layer. This means that the value at a certain index b \in {0, 1}^n of the layer is given by P(b). Denote by V: {0, 1}^n -> F the restriction of P on the hypercube.

As part of the GKR protocol, the prover needs to assert the following statement about the multilinear extention \tilde{V}: F^n -> F of V:

    \tilde{V}(g_1, ..., g_n) = r \in F`,
        for some challenges g_1, ..., g_n \in F                    (1)

(Note that, in general, P and \tilde{V} are different functions. They are both extensions of V, but \tilde{V} is a linear polynomial on each of it’s variables).

The left-hand side of (1) can be expressed as a sum over the hypercube as follows:

    \sum_{b_1 \in {0, 1}}
    \sum_{b_2 \in {0, 1}}
        ...
    \sum_{b_n \in {0, 1}}
       \beta(b_1, ..., b_n, g_1, ..., g_n) * P(b_1, b_2, ..., b_n) = r  (2)

where \beta is the following polynomial extending the equality predicate:

    \beta(b_1, ..., b_n, g_1, ..., g_n) =
        \prod_{i = 1}^n [ b_i * g_i + (1 - b_i) * (1 - g_i) ]

The functions in this module run the sumcheck protocol on expressions of the form described in equation (2). See the documentation of compute_sumcheck_message_beta_cascade for more information.

Structs

SumcheckEvals

A type representing the univariate polynomial g_i: F -> F which the prover sends to the verifier in each round of sumcheck. Note that we are using an evaluation representation of polynomials, which means this type just holds the evaluations: [g_i(0), g_i(1), ..., g_i(d)], where d is the degree of g_i.

Enums

InterpError

Error when Interpolating a univariate polynomial.

MleError

Errors to do with the evaluation of MleRefs.

VerifyError

Verification error.

Functions

apply_updated_beta_values_to_evals 🔒

This is the final step of beta cascade, where we take all the “bound” beta values and scale all of the evaluations by the product of all of these values.

beta_cascade

this is how we compute the evaluations of a product of mle refs along with a beta table. rather than using the full expanded version of a beta table, we instead just use the beta values vectors (which are unbound beta values, and the bound beta values) there are (degree + 1) evaluations that are returned which are the evaluations of the univariate polynomial where the “round_index”-th bit is the independent variable.

beta_cascade_no_independent_variable

Similar to beta_cascade, but does not compute any evaluations and simply multiplies the appropriate beta values by the evaluated bookkeeping table.

beta_cascade_step 🔒

This is one step of the beta cascade algorithm, performing (1 - beta_val) * mle[index] + beta_val * mle[index + 1]

evaluate_at_a_point

Use degree + 1 evaluations to figure out the evaluation at some arbitrary point

get_round_degree 🔒

Returns the maximum degree of b_{curr_round} within an expression (and therefore the number of prover messages we need to send)

successors_from_mle_product

this function will take a list of mle refs, and compute the element-wise product of all of their bookkeeping tables along with the “successors.”