Log-derivative lookup argument relation for establishing lookup reads from tables with 3 or fewer columns. More...

#include <logderiv_lookup_relation.hpp>

Public Types
using	FF = FF_

Static Public Member Functions
template<typename AllEntities >
static bool	skip (const AllEntities &in)

template<typename AllValues >
static bool	operation_exists_at_row (const AllValues &row)
	Does the provided row contain data relevant to table lookups; Used to determine whether the polynomial of inverses must be computed at a given row.

template<typename AllEntities >
static auto &	get_inverse_polynomial (AllEntities &in)

template<typename Accumulator , typename AllEntities >
static Accumulator	compute_inverse_exists (const AllEntities &in)
	Compute the Accumulator whose values indicate whether the inverse is computed or not.

template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator	compute_write_term (const AllEntities &in, const Parameters &params)

template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator	compute_read_term (const AllEntities &in, const Parameters &params)

template<typename Polynomials >
static void	compute_logderivative_inverse (Polynomials &polynomials, auto &relation_parameters, const size_t circuit_size)
	Construct the polynomial I whose components are the inverse of the product of the read and write terms.

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void	accumulate (ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
	Accumulate the subrelation contributions for reads from a lookup table.

Static Public Attributes
static constexpr size_t	WRITE_TERMS = 1

static constexpr size_t	INVERSE_SUBRELATION_LENGTH = 5

static constexpr size_t	LOOKUP_SUBRELATION_LENGTH = 5

static constexpr size_t	BOOLEAN_CHECK_SUBRELATION_LENGTH

static constexpr std::array< size_t, 3 >	SUBRELATION_PARTIAL_LENGTHS

static constexpr std::array< bool, 3 >	SUBRELATION_LINEARLY_INDEPENDENT

Detailed Description

template<typename FF_>
class bb::LogDerivLookupRelationImpl< FF_ >

Log-derivative lookup argument relation for establishing lookup reads from tables with 3 or fewer columns.

lookup argument seeks to prove lookups from a column by establishing the following sum:

\sum_{i=0}^{n-1} q_{logderiv_lookup}_i * (1 / write_term_i) + read_count_i * (1 / read_term_i) = 0

where write_term = table_col_1 + \gamma + table_col_2 * \eta_1 + table_col_3 * \eta_2 + table_index * \eta_3 and read_term = derived_table_entry_1 + \gamma + derived_table_entry_2 * \eta_1 + derived_table_entry_3 * \eta_2

table_index * \eta_3, with derived_table_entry_i = w_i - col_step_size_i\cdot w_i_shift (read note for explanation). This expression is motivated by taking the derivative of the log of a more conventional grand product style set equivalence argument (see e.g. https://eprint.iacr.org/2022/1530.pdf for details).

In practice, we must rephrase this expression in terms of polynomials, one of which is a polynomial I containing (indirectly) the rational functions in the above expression: I_i = 1/[(read_term_i) * (write_term_i)]. This leads to two subrelations. The first demonstrates that the inverse polynomial I is correctly formed. The second is the primary lookup identity, where the rational functions are replaced by the use of the inverse polynomial I. These two subrelations can be expressed as follows:

(1) I_i * (read_term_i) * (write_term_i) - 1 = 0

(2) \sum_{i=0}^{n-1} [q_{logderiv_lookup} * I_i * write_term_i + read_count_i * I_i * read_term_i] = 0

To not compute the inverse terms packed in I_i for indices not included in the sum we introduce a witness called inverse_exists, which is zero when either read_count_i is nonzero (a boolean called read_tag) or we have a read gate. This is represented by setting inverse_exists = 1- (1- read_tag)*(1- is_read_gate). Since is_read_gate is only dependent on selector values, we can assume that the verifier can check that it is boolean. However, if read_tag (which is a derived witness), is not constrained to be boolean, one can set the inverse_exists to 0, even when is_read_gate is 1, because inverse_exists is a linear function of read_tag then. Thus we have a third subrelation, that ensures that read_tag is a boolean value. (3) read_tag * read_tag - read_tag = 0 Further constraining of read_tags and read_counts is not required, since by tampering read_tags a malicious prover can only skip a write_term. This is disadvantagous for the cheating prover as it reduces the size of the lookup table. Hence, a malicious prover can not abuse this to prove an incorrect lookup. Note: Subrelation (2) 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.

Note: The "real" table entries must be 'derived' from wire values since instead of storing actual values in wires we store successive accumulators, the differences of which are equal to entries in a table. This is an efficiency trick for the case where entires of the "real" table correspond to limbs of a value too large to be supported by the lookup table. This way we avoid using additional gates to reconstruct full size values from the limbs contained in tables. See the documentation in method bb::plookup::get_lookup_accumulators()).

Definition at line 65 of file logderiv_lookup_relation.hpp.

Member Typedef Documentation

◆ FF

template<typename FF_ >

using bb::LogDerivLookupRelationImpl< FF_ >::FF = FF_

Definition at line 67 of file logderiv_lookup_relation.hpp.

Member Function Documentation

◆ accumulate()

template<typename FF_ >

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >

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

inlinestatic

Accumulate the subrelation contributions for reads from a lookup table.

Three subrelations are required per bus column, first to establish correctness of the precomputed inverses, second to establish the validity of the read, third establishes that read_tags is a boolean value.

Parameters

accumulator	transformed to `evals + C(in(X)...)*scaling_factor`
in	an std::array containing the fully extended Accumulator edges.
params	contains beta, gamma, and public_input_delta, ....
scaling_factor	optional term to scale the evaluation before adding to evals.

Definition at line 256 of file logderiv_lookup_relation.hpp.

◆ compute_inverse_exists()

template<typename FF_ >

template<typename Accumulator , typename AllEntities >

static Accumulator bb::LogDerivLookupRelationImpl< FF_ >::compute_inverse_exists ( const AllEntities & in )

inlinestatic

Compute the Accumulator whose values indicate whether the inverse is computed or not.

This is needed for efficiency since we don't need to compute the inverse unless the log derivative lookup relation is active at a given row. We skip the inverse computation for all the rows that read_count_i == 0 AND read_selector is 0

Note: read_tag is constructed such that read_tag_i = 1 or 0. We add a subrelation to check that read_tag is a boolean value

Definition at line 121 of file logderiv_lookup_relation.hpp.

◆ compute_logderivative_inverse()

template<typename FF_ >

template<typename Polynomials >

static void bb::LogDerivLookupRelationImpl< FF_ >::compute_logderivative_inverse	(	Polynomials &	polynomials,
		auto &	relation_parameters,
		const size_t	circuit_size
	)

inlinestatic

Construct the polynomial I whose components are the inverse of the product of the read and write terms.

If the denominators of log derivative lookup relation are read_term and write_term, then I_i = (read_term_i*write_term_i)^{-1}.

Note: Importantly, I_i = 0 for rows i at which there is no read or write, so the cost of this method is proportional to the actual number of lookups.

Definition at line 216 of file logderiv_lookup_relation.hpp.

◆ compute_read_term()

template<typename FF_ >

template<typename Accumulator , typename AllEntities , typename Parameters >

static Accumulator bb::LogDerivLookupRelationImpl< FF_ >::compute_read_term	(	const AllEntities &	in,
		const Parameters &	params
	)

inlinestatic

Definition at line 164 of file logderiv_lookup_relation.hpp.

◆ compute_write_term()

template<typename FF_ >

template<typename Accumulator , typename AllEntities , typename Parameters >

static Accumulator bb::LogDerivLookupRelationImpl< FF_ >::compute_write_term	(	const AllEntities &	in,
		const Parameters &	params
	)

inlinestatic

Definition at line 141 of file logderiv_lookup_relation.hpp.

◆ get_inverse_polynomial()

template<typename FF_ >

template<typename AllEntities >

static auto & bb::LogDerivLookupRelationImpl< FF_ >::get_inverse_polynomial ( AllEntities & in )

inlinestatic

Definition at line 109 of file logderiv_lookup_relation.hpp.

◆ operation_exists_at_row()

template<typename FF_ >

template<typename AllValues >

static bool bb::LogDerivLookupRelationImpl< FF_ >::operation_exists_at_row ( const AllValues & row )

inlinestatic

Does the provided row contain data relevant to table lookups; Used to determine whether the polynomial of inverses must be computed at a given row.

In order to avoid unnecessary computation, the polynomial of inverses I is only computed for rows at which the lookup relation is "active". It is active if either (1) the present row contains a lookup gate (i.e. q_lookup == 1), or (2) the present row contains table data that has been looked up in this circuit (lookup_read_tags == 1, or equivalently, if the row in consideration has index i, the data in polynomials table_i has been utlized in the circuit).

Definition at line 102 of file logderiv_lookup_relation.hpp.

◆ skip()

template<typename FF_ >

template<typename AllEntities >

static bool bb::LogDerivLookupRelationImpl< FF_ >::skip ( const AllEntities & in )

inlinestatic

Definition at line 86 of file logderiv_lookup_relation.hpp.

Member Data Documentation

◆ BOOLEAN_CHECK_SUBRELATION_LENGTH

template<typename FF_ >

constexpr size_t bb::LogDerivLookupRelationImpl< FF_ >::BOOLEAN_CHECK_SUBRELATION_LENGTH

staticconstexpr

Initial value:

=

3

Definition at line 72 of file logderiv_lookup_relation.hpp.

◆ INVERSE_SUBRELATION_LENGTH

template<typename FF_ >

constexpr size_t bb::LogDerivLookupRelationImpl< FF_ >::INVERSE_SUBRELATION_LENGTH = 5

staticconstexpr

Definition at line 70 of file logderiv_lookup_relation.hpp.

◆ LOOKUP_SUBRELATION_LENGTH

template<typename FF_ >

constexpr size_t bb::LogDerivLookupRelationImpl< FF_ >::LOOKUP_SUBRELATION_LENGTH = 5

staticconstexpr

Definition at line 71 of file logderiv_lookup_relation.hpp.

◆ SUBRELATION_LINEARLY_INDEPENDENT

template<typename FF_ >

constexpr std::array<bool, 3> bb::LogDerivLookupRelationImpl< FF_ >::SUBRELATION_LINEARLY_INDEPENDENT

staticconstexpr

Initial value:

= { true ,
                                             false ,
                                             true  }

Definition at line 82 of file logderiv_lookup_relation.hpp.

◆ SUBRELATION_PARTIAL_LENGTHS

template<typename FF_ >

constexpr std::array<size_t, 3> bb::LogDerivLookupRelationImpl< FF_ >::SUBRELATION_PARTIAL_LENGTHS

staticconstexpr

Initial value:

{
        INVERSE_SUBRELATION_LENGTH,      
        LOOKUP_SUBRELATION_LENGTH,       
        BOOLEAN_CHECK_SUBRELATION_LENGTH 
    }

Definition at line 75 of file logderiv_lookup_relation.hpp.

◆ WRITE_TERMS

template<typename FF_ >

constexpr size_t bb::LogDerivLookupRelationImpl< FF_ >::WRITE_TERMS = 1

staticconstexpr

Definition at line 68 of file logderiv_lookup_relation.hpp.

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

src/barretenberg/relations/logderiv_lookup_relation.hpp

Public Types

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ FF

Member Function Documentation

◆ accumulate()

◆ compute_inverse_exists()

◆ compute_logderivative_inverse()

◆ compute_read_term()

◆ compute_write_term()

◆ get_inverse_polynomial()

◆ operation_exists_at_row()

◆ skip()

Member Data Documentation

◆ BOOLEAN_CHECK_SUBRELATION_LENGTH

◆ INVERSE_SUBRELATION_LENGTH

◆ LOOKUP_SUBRELATION_LENGTH

◆ SUBRELATION_LINEARLY_INDEPENDENT

◆ SUBRELATION_PARTIAL_LENGTHS

◆ WRITE_TERMS