bb::GenericLookupRelationImpl< Settings, FF_ > Class Template Reference

Generic implementation of a log-derivative based lookup relation. More...

#include <generic_lookup_relation.hpp>

Public Types
using	FF = FF_
using	PolynomialStructure = LookupPolynomialStructure< Settings >

Static Public Member Functions
static constexpr size_t	compute_lookup_term_product_degree ()
	Compute the degree of the product of lookup terms.
static constexpr size_t	compute_table_term_product_degree ()
	Compute the degree of the product of table terms.
static constexpr size_t	compute_second_subrelation_degree ()
	Compute the degree of the second subrelation.
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.
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 index, typename AllEntities >
static Accumulator	lookup_read_counts (const AllEntities &in)
	Get the number of times a particular table value has been looked up.
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 &params)
	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 &params)
	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 &params, const FF &scaling_factor)
	Compute generic log-derivative lookup subrelation accumulation.

Static Public Attributes
static constexpr size_t	NUM_LOOKUP_TERMS = Settings::NUM_LOOKUP_TERMS
static constexpr size_t	NUM_TABLE_TERMS = Settings::NUM_TABLE_TERMS
static constexpr size_t	LOOKUP_TUPLE_SIZE = Settings::LOOKUP_TUPLE_SIZE
static constexpr size_t	LOOKUP_TERM_ACCUMULATED_DEGREE = compute_lookup_term_product_degree()
static constexpr size_t	TABLE_TERM_ACCUMULATED_DEGREE = compute_table_term_product_degree()
static constexpr size_t	FIRST_RELATION_PARTIAL_LENGTH
static constexpr size_t	SECOND_RELATION_PARTIAL_LENGTH
static constexpr size_t	LENGTH = std::max(FIRST_RELATION_PARTIAL_LENGTH, SECOND_RELATION_PARTIAL_LENGTH)
static constexpr std::array< size_t, 2 >	SUBRELATION_PARTIAL_LENGTHS { LENGTH, LENGTH }
static constexpr std::array< bool, 2 >	SUBRELATION_LINEARLY_INDEPENDENT = { true, false }

Detailed Description

template<typename Settings, typename FF_>
class bb::GenericLookupRelationImpl< Settings, FF_ >

Generic implementation of a log-derivative based lookup relation.

The following is a generic implementation of a log-derivative based lookup relation that allows the implementor to highly customize the lookup operations performed. For ease of use, the struct implements a default lookup argument with column batching, see below for more details.

The implementor is expected to provide two template parameters:

• FF_: the base field over which the relation is defined
• Settings: a struct that defines parameters and methods that allow the customization of the lookup relation.

Write \(f_1, \ldots, f_n\) for the columns to be looked up, and \(t_1, \ldots, t_m\) for the table columns. The relation implements the log-derivative lookup argument for two cases:

• BASIC_LOOKUP/BASIC_TABLE: LOOKUP_TUPLE_SIZE := n = m and we wish to look up the multiset \(\{(f_1(x), \ldots, f_n(x)) : x \in H_N\}\), where \(H_N\) is the hypercube of size N, from the table \(\{(t_1(y), \ldots, t_n(y)) : y \in H_N\}\). In this case, we perform the lookup by batching together the \(f_i\)'s and the \(t_i\)'s: we define \(f(x) = \sum_i f_i \cdot Y^i\), \(t(x) = \sum_i t_i \cdot Y^i\), and we check the existence of a function \(\text{counts} : B_N \rightarrow F\) such that

  \[ \sum_{x \in H_N} \frac{1}{\gamma - f(x, \beta)} = \sum_{x \in H_N} \frac{\text{counts}(x)}{\gamma - t(x, \beta)} \]

• CUSTOMIZED_LOOKUP/CUSTOMIZED_TABLE: We allow looking up values that are computed arbitrarily from \(\{f_1, \ldots, f_n\}\) from values that are computed arbitrarily (and possibly in a different way) from \(\{t_1, \ldots, t_m\}\).

In both cases, we rephrase the equation check in terms of two relations:

1. \[ I(x) \cdot \prod_{i=1}^{\text{NUM_LOOKUP_TERMS}} \text{lookup_entry}_i(x) \cdot \prod_{i=0}^{\text{NUM_TABLE_TERMS}} \text{table_entry}_i(x) - \text{inverse_exists}(x) = 0 \]

2. \[ \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 \text{lookup_read_count}_i(x) \cdot \frac{1}{\text{table_entry}_i(x)} \]

The first relation ensures that the polynomial \(I\) represents the inverse of the product of the entries to be looked up and the table entries. As this polynomial doesn't need to be defined everywhere, we set the result of the multiplication to be equal to the value of another polynomial: inverse_exist, which is set to 1 only if the inverse must be computed. Note that relation 1) is independent: it must be satisfied at every row in the trace.

The second relation is a dependent relation, it is satisfied only when its values are summed over the entire trace. The result of the sum is the log-derivative expression that bears witness to the validity of the lookup. Note that the lookup and table entries are multiplied by predicates that enable specifying which table lookup/table entries the prover is allowed to use at any given row.

The degrees of the above relations are:

1. The degree of relation 1) is \(\max(1 + \sum \deg(\text{lookup_entries}) + \sum \deg(\text{table_entries}), \deg(\text{inverse_exists}))\)
2. The degree of relation 2) is is \(3 + M\), where \(M = \max(\sum \deg(\text{lookup_entries}) + \sum \deg(\text{table_entries} - \deg(\text{term}_i))\) for \(\text{term}_i\) iterating over all terms. This is because we compute the inverses as:

   \[ \frac{1}{\text{table_entry}_i(x)} = I(x) \cdot \prod_{j \neq i} \text{table_entry}_j(x) \cdot \prod_{j} \text{lookup_entry}_j(x) \]

Note

The predicates involved in relation 2) are assumed to have been constrained to be boolean outside this relation.

Definition at line 242 of file generic_lookup_relation.hpp.

Member Typedef Documentation

FF

template<typename Settings , typename FF_ >

using bb::GenericLookupRelationImpl< Settings, FF_ >::FF = FF_

Definition at line 244 of file generic_lookup_relation.hpp.

PolynomialStructure

template<typename Settings , typename FF_ >

using bb::GenericLookupRelationImpl< Settings, FF_ >::PolynomialStructure = LookupPolynomialStructure<Settings>

Definition at line 245 of file generic_lookup_relation.hpp.

Member Function Documentation

accumulate()

template<typename Settings , typename FF_ >

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >

static void bb::GenericLookupRelationImpl< Settings, FF_ >::accumulate ( ContainerOverSubrelations &  accumulator, const AllEntities &  in, const Parameters &  params, const FF &  scaling_factor  )

inlinestatic

Compute generic log-derivative lookup subrelation accumulation.

The 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 GenericLookupRelationImpl 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
params	Contains beta, gamma relation parameters
scaling_factor	Optional term to scale the evaluation before adding to evals

Definition at line 585 of file generic_lookup_relation.hpp.

compute_inverse_exists()

template<typename Settings , typename FF_ >

template<typename Accumulator , typename AllEntities >

static Accumulator bb::GenericLookupRelationImpl< Settings, FF_ >::compute_inverse_exists ( const AllEntities &  in )

inlinestatic

Get selector/wire switching on (1) or off (0) inverse computation.

Template Parameters

Accumulator	Accumulator type for polynomial evaluations
AllEntities	Type containing all polynomial entities

Parameters

in	All entities

Returns

Accumulator value indicating whether inverse should be computed (1) or not (0)

Definition at line 417 of file generic_lookup_relation.hpp.

compute_lookup_term()

template<typename Settings , typename FF_ >

template<typename Accumulator , size_t lookup_index, typename AllEntities , typename Parameters >

static Accumulator bb::GenericLookupRelationImpl< Settings, FF_ >::compute_lookup_term ( const AllEntities &  in, const Parameters &  params  )

inlinestatic

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
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 499 of file generic_lookup_relation.hpp.

compute_lookup_term_product_degree()

template<typename Settings , typename FF_ >

static constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::compute_lookup_term_product_degree ( )

inlinestaticconstexpr

Compute the degree of the product of lookup terms.

Returns

Accumulated degree of all lookup terms

Definition at line 263 of file generic_lookup_relation.hpp.

compute_second_subrelation_degree()

template<typename Settings , typename FF_ >

static constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::compute_second_subrelation_degree ( )

inlinestaticconstexpr

Compute the degree of the second subrelation.

Iterate over all terms and compute the maximum of the sum of the degree of all terms minus the degree of the term we are currently looking at. The degree of the subrelation is the maximum plus 3 to account for the inverse polynomial, the read count, and the table term predicate.

Definition at line 317 of file generic_lookup_relation.hpp.

compute_table_term()

template<typename Settings , typename FF_ >

template<typename Accumulator , size_t table_index, typename AllEntities , typename Parameters >

static Accumulator bb::GenericLookupRelationImpl< Settings, FF_ >::compute_table_term ( const AllEntities &  in, const Parameters &  params  )

inlinestatic

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
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 538 of file generic_lookup_relation.hpp.

compute_table_term_product_degree()

template<typename Settings , typename FF_ >

static constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::compute_table_term_product_degree ( )

inlinestaticconstexpr

Compute the degree of the product of table terms.

Returns

Accumulated degree of all table terms

Definition at line 288 of file generic_lookup_relation.hpp.

get_inverse_polynomial()

template<typename Settings , typename FF_ >

template<typename AllEntities >

static auto & bb::GenericLookupRelationImpl< Settings, FF_ >::get_inverse_polynomial ( AllEntities &  in )

inlinestatic

Get the inverse permutation polynomial.

This method needs to return a non-const reference because it's used to compute the value of the inverse polynomial

Template Parameters

AllEntities

Type containing all polynomial entities

Parameters

in	All entities

Returns

Non-const reference to the inverse polynomial

Definition at line 403 of file generic_lookup_relation.hpp.

get_lookup_term_predicate()

template<typename Settings , typename FF_ >

template<typename Accumulator , size_t lookup_index, typename AllEntities >

static Accumulator bb::GenericLookupRelationImpl< Settings, FF_ >::get_lookup_term_predicate ( const AllEntities &  in )

inlinestatic

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 (must be less than NUM_LOOKUP_TERMS)
AllEntities	Type containing all polynomial entities

Parameters

in	All entities

Returns

Accumulator containing the predicate for the specified lookup term

Definition at line 457 of file generic_lookup_relation.hpp.

get_table_term_predicate()

template<typename Settings , typename FF_ >

template<typename Accumulator , size_t table_index, typename AllEntities >

static Accumulator bb::GenericLookupRelationImpl< Settings, FF_ >::get_table_term_predicate ( const AllEntities &  in )

inlinestatic

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 (must be less than NUM_TABLE_TERMS)
AllEntities	Type containing all polynomial entities

Parameters

in	All entities

Returns

Accumulator containing the predicate for the specified table term

Definition at line 477 of file generic_lookup_relation.hpp.

lookup_read_counts()

template<typename Settings , typename FF_ >

template<typename Accumulator , size_t index, typename AllEntities >

static Accumulator bb::GenericLookupRelationImpl< Settings, FF_ >::lookup_read_counts ( const AllEntities &  in )

inlinestatic

Get the number of times a particular table value has been looked up.

We assume lookup read counts are independent columns and therefore do not allow customization of this method to the implementor.

Template Parameters

Accumulator	Accumulator type for polynomial evaluations
index	Index of the table term (must be less than NUM_TABLE_TERMS)
AllEntities	Type containing all polynomial entities

Parameters

in	All entities

Returns

Accumulator containing the read count for the specified table term

Definition at line 437 of file generic_lookup_relation.hpp.

operation_exists_at_row()

template<typename Settings , typename FF_ >

template<typename AllValues >

static bool bb::GenericLookupRelationImpl< Settings, FF_ >::operation_exists_at_row ( const AllValues &  row )

inlinestatic

Check if we need to compute the inverse polynomial element value for this row.

Template Parameters

AllValues

Type containing all polynomial values at a given row

Parameters

row	All values at row

Returns

true if the inverse polynomial should be computed at this row, false otherwise

Definition at line 388 of file generic_lookup_relation.hpp.

Member Data Documentation

FIRST_RELATION_PARTIAL_LENGTH

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::FIRST_RELATION_PARTIAL_LENGTH

staticconstexpr

Initial value:

=
        std::max(LOOKUP_TERM_ACCUMULATED_DEGREE + TABLE_TERM_ACCUMULATED_DEGREE + 1,
                 Settings::INVERSE_EXISTS_POLYNOMIAL_DEGREE) +
        1

Definition at line 365 of file generic_lookup_relation.hpp.

LENGTH

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::LENGTH = std::max(FIRST_RELATION_PARTIAL_LENGTH, SECOND_RELATION_PARTIAL_LENGTH)

staticconstexpr

Definition at line 371 of file generic_lookup_relation.hpp.

LOOKUP_TERM_ACCUMULATED_DEGREE

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::LOOKUP_TERM_ACCUMULATED_DEGREE = compute_lookup_term_product_degree()

staticconstexpr

Definition at line 360 of file generic_lookup_relation.hpp.

LOOKUP_TUPLE_SIZE

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::LOOKUP_TUPLE_SIZE = Settings::LOOKUP_TUPLE_SIZE

staticconstexpr

When performing a basic lookup, we batch columns for efficiency. This constant represents the number of columns to be batched together. For example, it would be 1 for a range constraint lookup, 3 for a XOR lookup.

Note

For simplicity of implementation, we assume that all basic lookups use the same tuple size.

Definition at line 256 of file generic_lookup_relation.hpp.

NUM_LOOKUP_TERMS

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::NUM_LOOKUP_TERMS = Settings::NUM_LOOKUP_TERMS

staticconstexpr

Definition at line 247 of file generic_lookup_relation.hpp.

NUM_TABLE_TERMS

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::NUM_TABLE_TERMS = Settings::NUM_TABLE_TERMS

staticconstexpr

Definition at line 248 of file generic_lookup_relation.hpp.

SECOND_RELATION_PARTIAL_LENGTH

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::SECOND_RELATION_PARTIAL_LENGTH

staticconstexpr

Initial value:

=
        compute_second_subrelation_degree() + 1

Definition at line 369 of file generic_lookup_relation.hpp.

SUBRELATION_LINEARLY_INDEPENDENT

template<typename Settings , typename FF_ >

constexpr std::array<bool, 2> bb::GenericLookupRelationImpl< Settings, FF_ >::SUBRELATION_LINEARLY_INDEPENDENT = { true, false }

staticconstexpr

Definition at line 379 of file generic_lookup_relation.hpp.

SUBRELATION_PARTIAL_LENGTHS

template<typename Settings , typename FF_ >

constexpr std::array<size_t, 2> bb::GenericLookupRelationImpl< Settings, FF_ >::SUBRELATION_PARTIAL_LENGTHS { LENGTH, LENGTH }

staticconstexpr

Definition at line 375 of file generic_lookup_relation.hpp.

TABLE_TERM_ACCUMULATED_DEGREE

template<typename Settings , typename FF_ >

constexpr size_t bb::GenericLookupRelationImpl< Settings, FF_ >::TABLE_TERM_ACCUMULATED_DEGREE = compute_table_term_product_degree()

staticconstexpr

Definition at line 361 of file generic_lookup_relation.hpp.

---

The documentation for this class was generated from the following file:

• src/barretenberg/relations/generic_lookup/generic_lookup_relation.hpp