Log-derivative lookup argument relation for establishing DataBus reads. More...

#include <databus_lookup_relation.hpp>

Classes
struct	BusData

struct	BusData< 0, AllEntities >

struct	BusData< 1, AllEntities >

struct	BusData< 2, AllEntities >

struct	BusData< 3, AllEntities >

struct	BusData< 4, AllEntities >

Public Types
using	FF = FF_

Static Public Member Functions
template<typename T , size_t N>
static constexpr std::array< T, N *NUM_BUS_COLUMNS >	repeat_per_bus (const std::array< T, N > &pattern)

template<typename AllEntities >
static bool	skip (const AllEntities &in)

template<typename Accumulator , size_t bus_idx, typename AllEntities >
static Accumulator	get_read_selector (const AllEntities &in)
	Compute scalar for read term in log derivative lookup argument.

template<typename Accumulator , size_t bus_idx, typename AllEntities , typename Parameters >
static Accumulator	compute_table_term (const AllEntities &in, const Parameters &params)
	Compute write term denominator in log derivative lookup argument.

template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator	compute_lookup_term (const AllEntities &in, const Parameters &params)
	Compute read term denominator in log derivative lookup argument.

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

template<typename FF , size_t bus_idx, typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void	accumulate_subrelation_contributions (ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
	Accumulate the subrelation contributions for reads from a single databus column.

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void	accumulate (ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
	Accumulate the log derivative databus lookup argument subrelation contributions for each databus column.

Static Public Attributes
static constexpr size_t	INVERSE_READ_SUBREL_LENGTH = 6

static constexpr size_t	INVERSE_WRITE_SUBREL_LENGTH = 6

static constexpr size_t	LOOKUP_SUBREL_LENGTH = 6

static constexpr size_t	NUM_SUB_RELATION_PER_IDX = 3

static constexpr std::array< size_t, NUM_SUB_RELATION_PER_IDX >	PER_BUS_SUBREL_LENGTHS

static constexpr std::array< bool, NUM_SUB_RELATION_PER_IDX >	PER_BUS_LIN_INDEPENDENT { true, true, false }

static constexpr std::array< size_t, NUM_SUB_RELATION_PER_IDX *NUM_BUS_COLUMNS >	SUBRELATION_PARTIAL_LENGTHS

static constexpr std::array< bool, NUM_SUB_RELATION_PER_IDX *NUM_BUS_COLUMNS >	SUBRELATION_LINEARLY_INDEPENDENT

Detailed Description

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

Log-derivative lookup argument relation for establishing DataBus reads.

Each column of the databus can be thought of as a table from which we can look up values. The log-derivative lookup argument seeks to prove lookups from a column by establishing the following sum:

\[ \sum_{i=0}^{n-1} q_{\text{logderiv_lookup},i} \cdot \frac{1}{\text{lookup_term}_i} - \text{read_count}_i \cdot \frac{1}{\text{table_term}_i} = 0 \]

where the lookup and table terms are both of the form \(\text{value}_i + \text{idx}_i \cdot \beta + \gamma\). 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). For the table term, the (idx, value) pair comes from the "table" (bus column), and for the lookup term the (idx, value) pair comes from wires 1 and 2 which should contain a valid entry in the table.

Each column of the DataBus requires its own set of subrelations. The column being read is selected via a unique product, i.e. a lookup from bus column \(j\) is selected via \(q_{\text{busread}} \cdot q_j\) (j = 1,2,...).

For each bus column j, the inverse polynomial \(I_j\) stores \(1/(L \cdot T_j)\) at active rows. Inverse correctness is enforced by two separate subrelations gated by disjoint conditions:

Subrelation 1a (Inverse correctness on read rows):

\[ (I_j \cdot L \cdot T_j - 1) \cdot \text{is\_read}_j = 0 \]

Subrelation 1b (Inverse correctness on write rows):

\[ (I_j \cdot L \cdot T_j - 1) \cdot \text{count}_j = 0 \]

Subrelation 2 (Lookup identity):

\[ \sum_{i=0}^{n-1} [\text{is\_read}_j \cdot T_j - \text{count}_j \cdot L] \cdot I_j = 0 \]

At inactive rows (is_read = 0, count = 0), neither (1a) nor (1b) constrains I, but the lookup identity contribution is zero regardless. The prover gets no free degrees of freedom.

Note: Subrelation (2) is "linearly dependent" in the sense that it establishes that a sum across all rows of the execution 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.

Definition at line 61 of file databus_lookup_relation.hpp.

Member Typedef Documentation

◆ FF

template<typename FF_ >

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

Definition at line 63 of file databus_lookup_relation.hpp.

Member Function Documentation

◆ accumulate()

template<typename FF_ >

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >

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

inlinestatic

Accumulate the log derivative databus lookup argument subrelation contributions for each databus column.

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 328 of file databus_lookup_relation.hpp.

◆ accumulate_subrelation_contributions()

template<typename FF_ >

template<typename FF , size_t bus_idx, typename ContainerOverSubrelations , typename AllEntities , typename Parameters >

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

inlinestatic

Accumulate the subrelation contributions for reads from a single databus column.

Three subrelations are required per bus column: (1a) Inverse correctness on read rows: (I*L*T - 1) * is_read = 0 (1b) Inverse correctness on write rows: (I*L*T - 1) * count = 0 (2) Lookup identity (linearly dependent): (is_read*T - count*L) * I = 0

Definition at line 281 of file databus_lookup_relation.hpp.

◆ compute_logderivative_inverse()

template<typename FF_ >

template<size_t bus_idx, typename Polynomials >

static void bb::DatabusLookupRelationImpl< FF_ >::compute_logderivative_inverse	(	Polynomials &	polynomials,
		auto &	relation_parameters,
		const size_t	circuit_size,
		const size_t	start_index = `0`
	)

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 lookup_term and table_term, then \(I_i = (\text{lookup_term}_i \cdot \text{table_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 databus usage.

Definition at line 232 of file databus_lookup_relation.hpp.

◆ compute_lookup_term()

template<typename FF_ >

template<typename Accumulator , typename AllEntities , typename Parameters >

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

inlinestatic

Compute read term denominator in log derivative lookup argument.

Note: No bus_idx required here since inputs to a read are of the same form regardless the bus column

Definition at line 205 of file databus_lookup_relation.hpp.

◆ compute_table_term()

template<typename FF_ >

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

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

inlinestatic

Compute write term denominator in log derivative lookup argument.

Definition at line 184 of file databus_lookup_relation.hpp.

◆ get_read_selector()

template<typename FF_ >

template<typename Accumulator , size_t bus_idx, typename AllEntities >

static Accumulator bb::DatabusLookupRelationImpl< FF_ >::get_read_selector ( const AllEntities & in )

inlinestatic

Compute scalar for read term in log derivative lookup argument.

The selector indicating read from bus column \(j\) is given by \(q_{\text{busread}} \cdot q_j\), where \(j \in \{1, 2, 3, 4, 5\}\).

Definition at line 168 of file databus_lookup_relation.hpp.

◆ repeat_per_bus()

template<typename FF_ >

template<typename T , size_t N>

static constexpr std::array< T, N *NUM_BUS_COLUMNS > bb::DatabusLookupRelationImpl< FF_ >::repeat_per_bus ( const std::array< T, N > & pattern )

inlinestaticconstexpr

Definition at line 84 of file databus_lookup_relation.hpp.

◆ skip()

template<typename FF_ >

template<typename AllEntities >

template<typename FF_ >

constexpr std::array<size_t, NUM_SUB_RELATION_PER_IDX> bb::DatabusLookupRelationImpl< FF_ >::PER_BUS_SUBREL_LENGTHS

staticconstexpr

Initial value:

{
        INVERSE_READ_SUBREL_LENGTH,
        INVERSE_WRITE_SUBREL_LENGTH,
        LOOKUP_SUBREL_LENGTH,
    }

Definition at line 75 of file databus_lookup_relation.hpp.

◆ SUBRELATION_LINEARLY_INDEPENDENT

template<typename FF_ >

constexpr std::array<bool, NUM_SUB_RELATION_PER_IDX * NUM_BUS_COLUMNS> bb::DatabusLookupRelationImpl< FF_ >::SUBRELATION_LINEARLY_INDEPENDENT

staticconstexpr

Initial value:

=

repeat_per_bus(PER_BUS_LIN_INDEPENDENT)

bb::DatabusLookupRelationImpl::repeat_per_bus

static constexpr std::array< T, N *NUM_BUS_COLUMNS > repeat_per_bus(const std::array< T, N > &pattern)

Definition databus_lookup_relation.hpp:84

bb::DatabusLookupRelationImpl::PER_BUS_LIN_INDEPENDENT

static constexpr std::array< bool, NUM_SUB_RELATION_PER_IDX > PER_BUS_LIN_INDEPENDENT

Definition databus_lookup_relation.hpp:81

Definition at line 97 of file databus_lookup_relation.hpp.

◆ SUBRELATION_PARTIAL_LENGTHS

template<typename FF_ >

constexpr std::array<size_t, NUM_SUB_RELATION_PER_IDX * NUM_BUS_COLUMNS> bb::DatabusLookupRelationImpl< FF_ >::SUBRELATION_PARTIAL_LENGTHS

staticconstexpr

Initial value:

=

repeat_per_bus(PER_BUS_SUBREL_LENGTHS)

bb::DatabusLookupRelationImpl::PER_BUS_SUBREL_LENGTHS

static constexpr std::array< size_t, NUM_SUB_RELATION_PER_IDX > PER_BUS_SUBREL_LENGTHS

Definition databus_lookup_relation.hpp:75

Definition at line 95 of file databus_lookup_relation.hpp.

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

src/barretenberg/relations/databus_lookup_relation.hpp

Classes

Public Types

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ FF

Member Function Documentation

◆ accumulate()

◆ accumulate_subrelation_contributions()

◆ compute_logderivative_inverse()

◆ compute_lookup_term()

◆ compute_table_term()

◆ get_read_selector()

◆ repeat_per_bus()

◆ skip()

Member Data Documentation

◆ INVERSE_READ_SUBREL_LENGTH

◆ INVERSE_WRITE_SUBREL_LENGTH

◆ LOOKUP_SUBREL_LENGTH

◆ NUM_SUB_RELATION_PER_IDX

◆ PER_BUS_LIN_INDEPENDENT

◆ PER_BUS_SUBREL_LENGTHS

◆ SUBRELATION_LINEARLY_INDEPENDENT

◆ SUBRELATION_PARTIAL_LENGTHS