#include <ecc_set_relation.hpp>

Public Types
using	FF = FF_

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

template<typename Accumulator >
static Accumulator	convert_to_wnaf (const auto &s0, const auto &s1)

static auto &	get_grand_product_polynomial (auto &input)

static auto &	get_shifted_grand_product_polynomial (auto &input)

template<typename Accumulator , typename AllEntities , typename Parameters >
static Accumulator	compute_grand_product_numerator (const AllEntities &in, const Parameters &params)
	Performs multiset equality checks for the ECCVM. This faciliates "communication" between disjoint sets of columns, which we view as tables: the Precomputed table, the MSM table, and the Transcript table. This used to be called a strict lookup argument (where every element written was read exactly once.)

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

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void	accumulate (ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters &params, const FF &scaling_factor)
	Expression for the standard arithmetic gate. @dbetails The relation is defined as C(in(X)...) = (q_m * w_r * w_l) + (q_l * w_l) + (q_r * w_r) + (q_o * w_o) + q_c.

Static Public Attributes
static constexpr std::array< size_t, 2 >	SUBRELATION_PARTIAL_LENGTHS

Detailed Description

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

Definition at line 17 of file ecc_set_relation.hpp.

Member Typedef Documentation

◆ FF

template<typename FF_ >

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

Definition at line 19 of file ecc_set_relation.hpp.

Member Function Documentation

◆ accumulate()

template<typename FF >

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >

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

static

Expression for the standard arithmetic gate. @dbetails The relation is defined as C(in(X)...) = (q_m * w_r * w_l) + (q_l * w_l) + (q_r * w_r) + (q_o * w_o) + q_c.

Parameters

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

Definition at line 455 of file ecc_set_relation_impl.hpp.

◆ compute_grand_product_denominator()

template<typename FF >

template<typename Accumulator , typename AllEntities , typename Parameters >

Accumulator bb::ECCVMSetRelationImpl< FF >::compute_grand_product_denominator	(	const AllEntities &	in,
		const Parameters &	params
	)

static

First term: tuple of (pc, round, wnaf_slice), used to determine which points we extract from lookup tables when evaluaing MSMs in ECCVMMsmRelation. These values must be equivalent to the values computed in the 1st term of compute_grand_product_numerator

Second term: tuple of the form (transcript_pc, transcript_Px, transcript_Py, z1) OR (transcript_pc, \beta * transcript_Px, -transcript_Py, z2) for each scalar multiplication in ECCVMTranscriptRelation columns. Here \(\beta\) is a cube root of unity in \(\mathbb f_q\). These values must be equivalent to the second term values in compute_grand_product_numerator

Recall that every element of \(\mathbb F_r\) may be written as \(z_1 + \zeta z_2 = z_1 - \beta z_2\), where the \(z_i\) are 128 bit numbers and \(\zeta = -\beta\) is a sixth root of unity.

Third term: tuple of (pc, P.x, P.y, msm-size) from ECCVMTranscriptRelation. (P.x, P.y) is the claimed output of a multi-scalar-multiplication evaluated in ECCVMMSMRelation. We need to validate that the msm output produced in ECCVMMSMRelation is equivalent to the output present in transcript_msm_output_x, transcript_msm_output_y, for a given multi-scalar multiplication starting at transcript_pc and has size transcript_msm_count.

Note: In the case of an honest prover, (transcript_msm_output_x, transcript_msm_output_y) is the value of the just-completed MSM + OFFSET (as this is what the MSM table computes with to avoid branch logic.)

in transcript_msm_output_x, transcript_msm_output_y, for a given multi-scalar multiplication starting at transcript_pc and has size transcript_msm_count.

Note: In the case of an honest prover, (transcript_msm_output_x, transcript_msm_output_y) is the value of the just-completed MSM + OFFSET (as this is what the MSM table computes with to avoid branch logic.)

Definition at line 296 of file ecc_set_relation_impl.hpp.

◆ compute_grand_product_numerator()

template<typename FF >

template<typename Accumulator , typename AllEntities , typename Parameters >

Accumulator bb::ECCVMSetRelationImpl< FF >::compute_grand_product_numerator	(	const AllEntities &	in,
		const Parameters &	params
	)

static

Performs multiset equality checks for the ECCVM. This faciliates "communication" between disjoint sets of columns, which we view as tables: the Precomputed table, the MSM table, and the Transcript table. This used to be called a strict lookup argument (where every element written was read exactly once.)

ECCVMSetRelationImpl validates the correctness of the "inputs"/"outputs" of the three main algorithms evaluated by the ECCVM. Note that the terminology of "inputs" and "outputs" is purely psychological; they each just name the multiset we are adding to. We alternately use the terminology "numerator source" and "denominator source".

It will be helpful to recall that pc always stands for point-counter. We use the terms interchangably.

FIRST TERM: tuple of (pc, round, wnaf_slice), computed when slicing scalar multipliers into slices.

Numerator source: Precompute table columns (constrained by ECCVMWnafRelation) Denominator source: MSM table columns (constrained by ECCVMMSMRelation)

Note

This ensures the following:

every WNAF slice computed during scalar decomposition must be used exactly once during the MSM computation.

Warning: There is a subtlety in this table, which slightly complicates the abstraction of multiset-equality testing. On the denominator side, when addX == 0 for all X ∈ {1, 2, 3, 4} (automatically forced by add1 == 0), we multiply by 1. On the numerator side, to balance this out, this means that when precompute_select == 0, we must multiply by an additional eccvm_set_permutation_delta, which is the inverse of the fingerprint of the tuple (0, 0, 0). (This corresponds to "removing" the tuple (0, 0, 0) from the left multiset when precompute_select == 0).

SECOND TERM: tuple of (pc, P.x, P.y, scalar-multiplier), linking scalar mul requests to their WNAF decompositions.

Numerator source: Precompute table columns (constrained by ECCVMWnafRelation and ECCVMPointTableRelation) Denominator source: Transcript table columns (constrained by ECCVMTranscriptRelation)

The numerator is gated by precompute_point_transition == 1 (once per 128-bit scalar mul in the precompute table). The denominator is gated by transcript_mul == 1 (once per MUL opcode in the transcript, which can contribute up to two 128-bit scalar muls via z1 and z2).

Note

This ensures the following:

every scalar multiplication requested in the transcript (with a non-zero scalar and non-infinity base point) has a corresponding entry in the precompute table.

THIRD TERM: tuple of (pc, P.x, P.y, msm-size), linking MSM outputs to their claimed values in the transcript.

Numerator source: MSM table columns (constrained by ECCVMMSMRelation) Denominator source: Transcript table columns (constrained by ECCVMTranscriptRelation)

The numerator is gated by msm_transition == 1 (once per completed MSM). The denominator is gated by transcript_msm_transition == 1.

Note

This ensures the following:

the MSM output computed in the MSM table matches the MSM output claimed in the transcript.
the MSM size and starting point counter are consistent between the two tables.

Template Parameters

FF
AccumulatorTypes

Parameters

in
relation_params
index

Returns: ECCVMSetRelationImpl<FF>::template Accumulator<AccumulatorTypes>

First term: tuple of (pc, round, wnaf_slice), computed when slicing scalar multipliers into slices, as part of ECCVMWnafRelation.

There are 4 tuple entries per row of the Precompute table. Moreover, the element that "increments" is 4 * precompute_round, due to the fact that the Precompute columns contain four "digits"/slices per row.

Note: We only add this tuple if precompute_select == 1. Otherwise, we add a the tuple (0, 0, 0).

Second term: tuple of (pc, P.x, P.y, scalar-multiplier), used in ECCVMWnafRelation and ECCVMPointTableRelation.

ECCVMWnafRelation validates the sum of the wnaf slices associated with point-counter equals scalar-multiplier. ECCVMPointTableRelation computes a table of muliples of [P]: { -15[P], -13[P], ..., 15[P] }. We need to validate that the scalar-multiplier and [P] = (P.x, P.y) come from MUL opcodes in the transcript columns; in other words, that the wNAF expansion of the scalar-multiplier is correct.

Note: We only add the tuple to the multiset if precompute_point_transition == 1.

Third term: tuple of (pc, P.x, P.y, msm-size) from ECCVMMSMRelation. Third term: tuple of (pc, P.x, P.y, msm-size) from ECCVMMSMRelation. (P.x, P.y) is the output of a multi-scalar-multiplication evaluated in ECCVMMSMRelation. We need to validate that the same values (P.x, P.y) are present in the Transcript columns and describe a multi-scalar multiplication of size msm-size, starting at pc. multi-scalar multiplication of size msm-size, starting at pc.

If msm_transition_shift == 1, this indicates the current row is the last row of a multiscalar multiplication evaluation. The output of the MSM will be present on (msm_accumulator_x_shift, msm_accumulator_y_shift). The values of msm_accumulator_x_shift, msm_accumulator_y_shift, msm_pc, msm_size_of_msm must match up with equivalent values transcript_msm_output_x, transcript_msm_output_y, transcript_pc, transcript_msm_count present in the Transcript columns.

Checking msm_size is correct (it is tied to the pc) is necessary to make sure the msm_pc increments correctly after it completes an MSM.

Definition at line 71 of file ecc_set_relation_impl.hpp.

◆ convert_to_wnaf()

template<typename FF_ >

template<typename Accumulator >

static Accumulator bb::ECCVMSetRelationImpl< FF_ >::convert_to_wnaf	(	const auto &	s0,
		const auto &	s1
	)

inlinestatic

Definition at line 49 of file ecc_set_relation.hpp.

◆ get_grand_product_polynomial()

template<typename FF_ >

static auto & bb::ECCVMSetRelationImpl< FF_ >::get_grand_product_polynomial ( auto & input )

inlinestatic

Definition at line 59 of file ecc_set_relation.hpp.

◆ get_shifted_grand_product_polynomial()

template<typename FF_ >

static auto & bb::ECCVMSetRelationImpl< FF_ >::get_shifted_grand_product_polynomial ( auto & input )

inlinestatic

Definition at line 60 of file ecc_set_relation.hpp.

◆ skip()

template<typename FF_ >

template<typename AllEntities >

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

inlinestatic

Definition at line 26 of file ecc_set_relation.hpp.

Member Data Documentation

◆ SUBRELATION_PARTIAL_LENGTHS

template<typename FF_ >

constexpr std::array<size_t, 2> bb::ECCVMSetRelationImpl< FF_ >::SUBRELATION_PARTIAL_LENGTHS

staticconstexpr

Initial value:

Definition at line 21 of file ecc_set_relation.hpp.

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

src/barretenberg/relations/ecc_vm/ecc_set_relation.hpp
src/barretenberg/relations/ecc_vm/ecc_set_relation_impl.hpp

Public Types

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Typedef Documentation

◆ FF

Member Function Documentation

◆ accumulate()

◆ compute_grand_product_denominator()

◆ compute_grand_product_numerator()

◆ convert_to_wnaf()

◆ get_grand_product_polynomial()

◆ get_shifted_grand_product_polynomial()

◆ skip()

Member Data Documentation

◆ SUBRELATION_PARTIAL_LENGTHS