bb::LogDerivLookupRelationImpl< FF_ > Class Template Reference

#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)
template<typename Accumulator , size_t index, typename AllEntities >
static Accumulator	lookup_read_counts (const AllEntities &in)
template<typename Accumulator , size_t write_index, typename AllEntities , typename Parameters >
static Accumulator	compute_write_term (const AllEntities &in, const Parameters &params)
template<typename Accumulator , size_t read_index, 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)
	Log-derivative style lookup argument for conventional lookups form tables with 3 or fewer columns.

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< size_t, 3 >	TOTAL_LENGTH_ADJUSTMENTS
static constexpr std::array< bool, 3 >	SUBRELATION_LINEARLY_INDEPENDENT = { true, false, true }

Detailed Description

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

Definition at line 19 of file logderiv_lookup_relation.hpp.

Member Typedef Documentation

FF

template<typename FF_ >

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

Definition at line 21 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

Log-derivative style lookup argument for conventional lookups form tables with 3 or fewer columns.

The identity to be checked is of the form

\sum{i=0}^{n-1} \frac{read_counts_i}{write_term_i} - \frac{q_lookup}{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. (The table entries must be 'derived' from wire values in this way since the stored witnesses are actually successive accumulators, the differences of which are equal to entries in a table. This is an efficiency trick to avoid using additional gates to reconstruct full size values from the limbs contained in tables).

In practice this identity is expressed in terms of polynomials by defining a polynomial of inverses I_i = \frac{1}{read_term_i\cdot write_term_i} then rewriting the above identity as

(1) \sum{i=0}^{n-1} (read_counts_i\cdot I_i\cdot read_term_i) - (q_lookup\cdot I_i\cdot write_term_i) = 0

This requires a second subrelation to check that polynomial I was computed correctly. For all i, it must hold that

(2) I_i\cdot read_term_i\cdot write_term_i - 1 = 0

Note that (1) is 'linearly dependent' in the sense that it holds only as a sum across the entire execution trace. (2) on the other hand holds independently at every row. Finally, note that to avoid unnecessary computation, we only compute I_i at indices where the relation is 'active', i.e. on rows which either contain a lookup gate or table data that has been read. For inactive rows i, we set I_i = 0. We can thus rewrite (2) as

(2) I_i\cdot read_term_i\cdot write_term_i - is_active_i

where is_active = q_lookup + read_tags - q_lookup\cdot read_tags

and read_tags is a polynomial taking boolean values indicating whether the table entry at the corresponding row has been read or not. the last (third) subrelation consists of checking that the read_tag is a boolean value we argue that this is enough for the soundness of the relation. note that read_tags is not constrained to be related to the readcounts values. however, if the read_tags are assured to be 0 or 1, the only thing a cheating prover could do is to skip over an inversion when are not supposed to skip over it. we argue that this does not give the prover any advantage, as it would only mean an element from the lookup table is removed. this means that if a proof verifies, we still have that the provers set is a subset of the lookup table, as the only freedome the prover has is to make the lookup table smaller. the boolean check is still necessary, as otherwise has_inverse, is a leanier function of read_tags, and the the prover can set it to zero (by picking a non-binary value for read_tags) even when we have a read gate in the row.

Note

This relation utilizes functionality in the log-derivative library to compute the polynomial of inverses

Definition at line 251 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

Definition at line 72 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 172 of file logderiv_lookup_relation.hpp.

compute_read_term()

template<typename FF_ >

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

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

inlinestatic

Definition at line 118 of file logderiv_lookup_relation.hpp.

compute_write_term()

template<typename FF_ >

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

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

inlinestatic

Definition at line 91 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 68 of file logderiv_lookup_relation.hpp.

lookup_read_counts()

template<typename FF_ >

template<typename Accumulator , size_t index, typename AllEntities >

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

inlinestatic

Definition at line 83 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 61 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 45 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 26 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 24 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 25 of file logderiv_lookup_relation.hpp.

SUBRELATION_LINEARLY_INDEPENDENT

template<typename FF_ >

constexpr std::array<bool, 3> bb::LogDerivLookupRelationImpl< FF_ >::SUBRELATION_LINEARLY_INDEPENDENT = { true, false, true }

staticconstexpr

Definition at line 43 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 29 of file logderiv_lookup_relation.hpp.

TOTAL_LENGTH_ADJUSTMENTS

template<typename FF_ >

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

staticconstexpr

Initial value:

{
        2, 
        2, 
        2, 
    }

Definition at line 37 of file logderiv_lookup_relation.hpp.

WRITE_TERMS

template<typename FF_ >

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

staticconstexpr

Definition at line 22 of file logderiv_lookup_relation.hpp.

---

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

• src/barretenberg/relations/logderiv_lookup_relation.hpp