Module gate_helpers 

Helper functions used in the gate sumcheck algorithms.

Enums

GateError

Error handling for gate mle construction.

Functions

compute_fully_bound_binary_gate_function 🔒

Similar to compute_fully_bound_identity_gate_function, this function uses the “Rothblum” trick in order to evaluate the fully bound gate function in a streaming fashion.

compute_fully_bound_identity_gate_function 🔒

Compute the fully bound identity gate function, which is f_1(g, u) where the output gate label variables are fully bound to the claim on the layer and the input gate label variables are fully bound to the round challenges from sumcheck.

compute_sumcheck_message_data_parallel_gate

Compute the sumcheck message for a binary gate specified by the BinaryOperation.

compute_sumcheck_message_data_parallel_identity_gate 🔒

Get the evals for a binary gate specified by the BinaryOperation. Note that this specifically refers to computing the prover message while binding the dataparallel bits of a IdentityGate expression.

compute_sumcheck_message_no_beta_table

Compute sumcheck message without a beta table.

evaluate_mle_product_no_beta_table 🔒

Given (possibly half-fixed) bookkeeping tables of the MLEs which are multiplied, e.g. V_i(u_1, …, u_{k - 1}, x, b_{k + 1}, …, b_n) * V_{i + 1}(u_1, …, u_{k - 1}, x, b_{k + 1}, …, b_n) computes g_k(x) = \sum_{b_{k

fold_binary_gate_wiring_into_mles_phase_1 🔒

This function uses the “Rothblum”-inspired sumcheck trick in order to evaluate the necessary MLEs as defined in https://eprint.iacr.org/2019/317.pdf for phase 1 of binary gate sumcheck messages.

fold_binary_gate_wiring_into_mles_phase_2 🔒

This function uses the “Rothblum”-inspired sumcheck trick in order to evaluate the necessary MLEs as defined in https://eprint.iacr.org/2019/317.pdf for phase 2 of binary gate sumcheck messages.

fold_wiring_into_beta_mle_identity_gate 🔒

The folding occurs by first iterating through the nonzero gates, and computing the value \beta(g, z) for each output label z and the challenge point g. Instead of computing the \beta value from scratch, we take inspiration from the Rothblum sumcheck trick to just multiply by the inverses and points necessary to go from one beta value to the next. This conserves memory by not having to store the entire table (which is done to achieve linear computation) while continuing to achieve amortized linear computation for each progressive beta value as opposed to the O(log(n)) method used to compute it from scratch.

index_mle_indices_gate

Index mle indices for an array of mles.