#include <ecc_point_table_relation.hpp>

Public Types
using	FF = FF_

Static Public Member Functions
template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >
static void	accumulate (ContainerOverSubrelations &accumulator, const AllEntities &in, const Parameters &, const FF &scaling_factor)
	ECCVMPointTableRelationImpl.

Static Public Attributes
static constexpr std::array< size_t, 6 >	SUBRELATION_PARTIAL_LENGTHS { 6, 6, 6, 6, 6, 6 }

Detailed Description

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

ECCVMPointTableRelationImpl.

These relations define the set of point lookup tables we will use in ecc_msm_relation.hpp, to evaluate multiscalar multiplication. For every point [P] = (Px, Py) involved in an MSM, we need to do define a lookup table out of the following points: { -15[P], -13[P], -11[P], -9[P], -7[P], -5[P], -3[P], -[P] } ECCVMPointTableRelationImpl defines relations that define the lookup table.

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 24 of file ecc_point_table_relation.hpp.

Member Typedef Documentation

◆ FF

template<typename FF_ >

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

Definition at line 26 of file ecc_point_table_relation.hpp.

Member Function Documentation

◆ accumulate()

template<typename FF >

template<typename ContainerOverSubrelations , typename AllEntities , typename Parameters >

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

static

ECCVMPointTableRelationImpl.

These relations define the set of point lookup tables we will use in ecc_msm_relation.hpp, to evaluate multiscalar multiplication. For every point [P] = (Px, Py) involved in an MSM, we need to do define a lookup table out of the following points: { -15[P], -13[P], -11[P], -9[P], -7[P], -5[P], -3[P], -[P] } ECCVMPointTableRelationImpl defines relations that define the lookup table.

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.

Row structure

Consider the set of (128-bit scalar multiplier, point, pc) tuples in the transcript columns. The point table columns process one tuple every 8 rows. The tuple with the largest pc value is first. When transitioning between tuple elements, pc decrements by 1.

The following table gives an example for two points. In the table, the point associated with pc = 1 is labelled P. the point associated with pc = 0 is labelled Q.

precompute_pc	precompute_point_transition	precompute_round	Tx	Ty	Dx	Dy
1	0	0	15P.x	15P.y	2P.x	2P.y
1	0	1	13P.x	13P.y	2P.x	2P.y
1	0	2	11P.x	11P.y	2P.x	2P.y
1	0	3	9P.x	9P.y	2P.x	2P.y
1	0	4	7P.x	7P.y	2P.x	2P.y
1	0	5	5P.x	5P.y	2P.x	2P.y
1	0	6	3P.x	3P.y	2P.x	2P.y
1	1	7	P.x	P.y	2P.x	2P.y
0	0	0	15Q.x	15Q.y	2Q.x	2Q.y
0	0	1	13Q.x	13Q.y	2Q.x	2Q.y
0	0	2	11Q.x	11Q.y	2Q.x	2Q.y
0	0	3	9Q.x	9Q.y	2Q.x	2Q.y
0	0	4	7Q.x	7Q.y	2Q.x	2Q.y
0	0	5	5Q.x	5Q.y	2Q.x	2Q.y
0	0	6	3Q.x	3Q.y	2Q.x	2Q.y
0	1	7	Q.x	Q.y	2Q.x	2Q.y

We apply the following relations to constrain the above table:

If precompute_point_transition = 0, (Dx, Dy) = (Dx_shift, Dy_shift)
If precompute_point_transition = 1, (Dx, Dy) = 2 (Px, Py)
If precompute_point_transition = 0, (Tx, Ty) = (Tx_shift, Ty_shift) + (Dx, Dy)

The relations that constrain precompute_point_transition and precompute_pc are in ecc_wnaf_relation.hpp

When precompute_point_transition = 1, the next row corresponds to the beginning of the processing of a new point. We use a multiset-equality check, ecc_set_relation.hpp to validate (pc, Tx, Ty, scalar-multiplier) is the same as something derived from the transcript columns. In other words, the multiset equality check allows the tables to communicate, and in particular validates that we are populating our PointTable with precomputed values that indeed arise from the Transcript columns. (Formerly, we referred to this as a "strict" lookup protocol = every item in the table must be read from once, and only once)

For every row, we use a lookup protocol in ecc_lookup_relation.hpp to write the following tuples into a lookup table:

(pc, 15 - precompute_round, Tx, Ty)
(pc, precompute_round, Tx, -Ty)

The value 15 - precompute_round describes the multiplier applied to P at the current row. (this can be expanded into a wnaf value by taking 2x - 15 where x = 15 - precompute_round) . The value precompute_round describes the negative multiplier applied to P at the current row. This is also expanded into a wnaf value by taking 2x - 15 where x = precompute_round.

The following table describes how taking (15 - precompute_round) for positive values and (precompute_round) for negative values produces the WNAF slice values that correspond to the multipliers for (Tx, Ty) and (Tx, -Ty):

Tx	Ty	x = 15 - precompute_round	2x - 15	y = precompute_round	2y - 15
15P.x	15P.y	15	15	0	-15
13P.x	13P.y	14	13	1	-13
11P.x	11P.y	13	11	2	-11
9P.x	9P.y	12	9	3	-9
7P.x	7P.y	11	7	4	-7
5P.x	5P.y	10	5	5	-5
3P.x	3P.y	9	3	6	-3
P.x	P.y	8	1	7	-1

Validate Dx, Dy correctness relation

When computing a point table for point [P] = (Px, Py), we require [D] (Dx, Dy) = 2.[P] If all other relations are satisfied, we know that (Tx, Ty) = (Px, Py) i.e. (Dx, Dy) = 2(Px, Py) when precompute_round_transition = 1.

Double formula: x_3 = 9x^4 / 4y^2 - 2x y_3 = (3x^2 / 2y) * (x - x_3) - y

Expanding into relations: (x_3 + 2x) * 4y^2 - 9x^4 = 0 (y3 + y) * 2y - 3x^2 * (x - x_3) = 0

If precompute_round_transition = 0, (Dx_shift, Dy_shift) = (Dx, Dy)

1st row is empty => don't apply if lagrange_first == 1

Valdiate (Tx, Ty) is correctly computed from (Tx_shift, Ty_shift), (Dx, Dy). If precompute_round_transition = 0, [T] = [T_shift] + [D].

Add formula: x_3 = (y_2 - y_1)^2 / (x_2 - x_1)^2 - x_2 - x_1 y_3 = ((y_2 - y_1) / (x_2 - x_1)) * (x_1 - x_3) - y_1

Expanding into relations: (x_3 + x_2 + x_1) * (x_2 - x_1)^2 - (y_2 - y_1)^2 = 0 (y_3 + y_1) * (x_2 - x_1) + (x_3 - x_1) * (y_2 - y_1) = 0

We don't need to check for incomplete point addition edge case (x_1 == x_2); the only cases this would correspond to are y2 == y1 or y2 == -y1. Both of these cases may be ruled out as follows.

y2 == y1. Then 2P == kP, where k∈{1, ..., 13}, which of course cannot happen because the order r of E(Fₚ) is a large prime and P is already assumed to not be the neutral element.
y2 == -y1. Again, then -2P == kP, k∈{1, ..., 13}, and we get the same contradiction.

Definition at line 30 of file ecc_point_table_relation_impl.hpp.

Member Data Documentation

◆ SUBRELATION_PARTIAL_LENGTHS

template<typename FF_ >

constexpr std::array<size_t, 6> bb::ECCVMPointTableRelationImpl< FF_ >::SUBRELATION_PARTIAL_LENGTHS { 6, 6, 6, 6, 6, 6 }

staticconstexpr

Definition at line 28 of file ecc_point_table_relation.hpp.

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

src/barretenberg/relations/ecc_vm/ecc_point_table_relation.hpp
src/barretenberg/relations/ecc_vm/ecc_point_table_relation_impl.hpp

Public Types

Static Public Member Functions