|
| template<typename AllValues > |
| static bool | operation_exists_at_row (const AllValues &row) |
| | Check if we need to compute the inverse polynomial element value for this row.
|
| |
| template<typename AllEntities > |
| static auto & | get_inverse_polynomial (AllEntities &in) |
| | Get the inverse permutation polynomial (needed to compute its value)
|
| |
| template<typename Accumulator , typename AllEntities > |
| static Accumulator | compute_inverse_exists (const AllEntities &in) |
| | Get selector/wire switching on (1) or off (0) inverse computation.
|
| |
| template<typename Accumulator , size_t lookup_index, typename AllEntities > |
| static Accumulator | get_lookup_term_predicate (const AllEntities &in) |
| | Extract predicate enabling looking up a given lookup term at this row.
|
| |
| template<typename Accumulator , size_t table_index, typename AllEntities > |
| static Accumulator | get_table_term_predicate (const AllEntities &in) |
| | Extract predicate enabling looking up a given table term at this row.
|
| |
| template<typename Accumulator , size_t lookup_index, typename AllEntities , typename Parameters > |
| static Accumulator | compute_lookup_term (const AllEntities &in, const Parameters ¶ms) |
| | Compute the value of the lookup term at a given index.
|
| |
| template<typename Accumulator , size_t table_index, typename AllEntities , typename Parameters > |
| static Accumulator | compute_table_term (const AllEntities &in, const Parameters ¶ms) |
| | Compute the value of a table term at a given index.
|
| |
| template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters > |
| static void | accumulate (ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters ¶ms, const FF &scaling_factor) |
| | Compute generic log-derivative set permutation subrelation accumulation.
|
| |
template<typename Settings, typename FF_>
class bb::GenericPermutationRelationImpl< Settings, FF_ >
Implementation of a generic permutation relation.
Implementation of a generic permutation relation that uses a log-derivative argument to prove that elements in two columns of the execution trace are equal. The strategy is to use the lookup log-derivate argument with read counts (i.e., number of times the lookup terms are looked up) equal to 1. This enforces the sets we are comparing to be permutations of one another. The relation is composed of two subrelations, the first is equal to the first subrelation in GenericLookupRelationImpl. The second one is the modification of the second subrelation of the generic lookup in which we hard-code the read counts to 1:
\[
\sum_{i=0}^{\text{NUM_LOOKUP_TERMS}} \text{lookup_entry_predicate}_i(x) \cdot \frac{1}{\text{lookup_entry}_i(x)}
- \sum_{i=0}^{\text{NUM_TABLE_TERMS}} \text{table_entry_predicate}_i(x) \cdot \frac{1}{\text{table_entry}_i(x)}
\]
- Note
- The predicates involved in the second subrelation are assumed to have been constrained to be boolean outside this relation.
Definition at line 68 of file generic_permutation_relation.hpp.
template<typename Settings , typename FF_ >
template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
| static void bb::GenericPermutationRelationImpl< Settings, FF_ >::accumulate |
( |
ContainerOverSubrelations & |
accumulator, |
|
|
const AllEntities & |
in, |
|
|
const Parameters & |
params, |
|
|
const FF & |
scaling_factor |
|
) |
| |
|
inlinestatic |
Compute generic log-derivative set permutation subrelation accumulation.
he generic log-derivative lookup relation consists of two subrelations. The first demonstrates that the inverse polynomial I has been computed correctly. The second establishes the correctness of the lookups themselves based on the log-derivative lookup argument. Note that the latter subrelation is "linearly dependent" in the sense that it establishes that a sum across all rows of the exectution trace is zero, rather than that some expression holds independently at each row. Accordingly, this subrelation is not multiplied by a scaling factor at each accumulation step. See the documentation for GenericPermutationRelationImpl for the definition of the subrelations.
- Template Parameters
-
| ContainerOverSubrelations | Container type for accumulating subrelation contributions |
| AllEntities | Type containing all polynomial entities |
| Parameters | Type containing relation parameters |
- Parameters
-
| accumulator | transformed to evals + C(in(X)...)*scaling_factor |
| in | an std::array containing the fully extended Accumulator edges. |
| relation_params | contains beta, gamma, and public_input_delta, .... |
| scaling_factor | optional term to scale the evaluation before adding to evals. |
Definition at line 275 of file generic_permutation_relation.hpp.
template<typename Settings , typename FF_ >
template<typename Accumulator , size_t lookup_index, typename AllEntities , typename Parameters >
Compute the value of the lookup term at a given index.
- Template Parameters
-
| Accumulator | Accumulator type for polynomial evaluations |
| lookup_index | Index of the lookup term to compute (kept for compatibility with lookups, always 0) |
| AllEntities | Type containing all polynomial entities |
| Parameters | Type containing relation parameters (beta, gamma) |
- Parameters
-
| in | All entities |
| params | Relation parameters |
- Returns
- Accumulator containing the computed lookup term value
Definition at line 202 of file generic_permutation_relation.hpp.
template<typename Settings , typename FF_ >
template<typename Accumulator , size_t table_index, typename AllEntities , typename Parameters >
Compute the value of a table term at a given index.
- Template Parameters
-
| Accumulator | Accumulator type for polynomial evaluations |
| table_index | Index of the table term to compute (kept for compatibility with lookups, always 0) |
| AllEntities | Type containing all polynomial entities |
| Parameters | Type containing relation parameters (beta, gamma) |
- Parameters
-
| in | All entities |
| params | Relation parameters |
- Returns
- Accumulator containing the computed table term value
Definition at line 235 of file generic_permutation_relation.hpp.
template<typename Settings , typename FF_ >
template<typename Accumulator , size_t lookup_index, typename AllEntities >
Extract predicate enabling looking up a given lookup term at this row.
- Template Parameters
-
| Accumulator | Accumulator type for polynomial evaluations |
| lookup_index | Index of the lookup term (kept for compatibility with lookups, always 0) |
| AllEntities | Type containing all polynomial entities |
- Parameters
-
- Returns
- Accumulator containing the predicate for the specified lookup term
Definition at line 159 of file generic_permutation_relation.hpp.
template<typename Settings , typename FF_ >
template<typename Accumulator , size_t table_index, typename AllEntities >
Extract predicate enabling looking up a given table term at this row.
- Template Parameters
-
| Accumulator | Accumulator type for polynomial evaluations |
| table_index | Index of the table term (kept for compatibility with lookups, always 0) |
| AllEntities | Type containing all polynomial entities |
- Parameters
-
- Returns
- Accumulator containing the predicate for the specified table term
Definition at line 181 of file generic_permutation_relation.hpp.
template<typename Settings , typename FF_ >
We apply the power polynomial only to the first subrelation.
The first subrelation establishes correspondence between the inverse polynomial elements and the terms. The second relation computes the inverses of individual terms, which are then summed up with sumcheck
Definition at line 102 of file generic_permutation_relation.hpp.
1.9.8