proof_system::plonk::widget::EllipticKernel< Field, Getters, PolyContainer > Class Template Reference

Core class implementing elliptic curve point addition. It is enhanced to handle the case where one of the points is automatically scaled by the endomorphism constant β or negated. More...

#include <elliptic_widget.hpp>

Static Public Member Functions
static std::set< PolynomialIndex > const &	get_required_polynomial_ids ()
static void	accumulate_contribution (PolyContainer &polynomials, const challenge_array &challenges, Field &quotient, const size_t i=0)
	Computes the single linear term for elliptic point addition.

Static Public Attributes
static constexpr size_t	num_independent_relations = 4
static constexpr uint8_t	quotient_required_challenges = CHALLENGE_BIT_ALPHA
static constexpr uint8_t	update_required_challenges = CHALLENGE_BIT_ALPHA

Detailed Description

template<class Field, class Getters, typename PolyContainer>
class proof_system::plonk::widget::EllipticKernel< Field, Getters, PolyContainer >

Core class implementing elliptic curve point addition. It is enhanced to handle the case where one of the points is automatically scaled by the endomorphism constant β or negated.

TODO(#429): based on the ultra honk relation consistency test, the below expressions differ slightly from what is actually implemented. (Mostly sign errors; some incorrect terms)

The basic equation for the elliptic curve in short weierstrass form is y^2 == x^3 + a * x + b.

The addition formulas are: λ = (y_2 - y_1) / (x_2 - x_1) x_3 = λ^2 - x_2 - x_1 = (y_2 - y_1)^2 / (x_2 - x_1)^2 - x_2 - x_1 = ((y_2 - y_1)^2 - (x_2 - x_1) * (x_2^2 - x_1^2)) / (x_2 - x_1)^2

If we assume that the points being added are distinct and not invereses of each other (so their x coordinates differ), then we can rephrase this equality: x_3 * (x_2 - x_1)^2 = ((y_2 - y_1)^2 - (x_2 - x_1) * (x_2^2 - x_1^2)) Let's say we want to apply the endomorphism to the (x_2, y_2) point at the same time and maybe change the sign of y_2:

(x_2, y_2) = (β * x_2', sign * y_2') x_3 * (β * x_2' - x_1)^2 = ((sign * y_2' - y_1)^2 - (β * x_2' - x_1) * ((β * x_2')^2 - x_1^2))

Let's open the brackets and group the terms by β, β^2, sign:

x_2'^2 * x_3 * β^2 - 2 * β * x_1 * x_2' * x_3 - x_1^2 * x_3 = sign^2 * y_2'^2 - 2 * sign * y_1 * y_2 + y_1^2 - β^3

• x_2'^3 + β * x_1^2 * x_2' + β^2 * x_1 * x_2'^2 - x_1^3

  β^3 = 1 sign^2 = 1 (at least we always expect sign to be set to 1 or -1)

  sign * (-2 * y_1 * y_2) + β * (2 * x_1 * x_2' * x_3 +x_1^2 * x_2') + β^2 * (x_1 * x_2'^2 - x_2'^2 * x_3) + (x_1^2 * x_3 + y_2'^2 + y_1^2 - x_2'^3 - x_1^3) = 0 This is the equation computed in x_identity and scaled by α

  Now let's deal with the y equation: y_3 = λ * (x_3 - x_1) + y_1 = (y_2 - y_1) * (x_3 - x_1) / (x_2 - x_1) + y_1 = ((y_2 - y_1) * (x_3 - x_1) + y_1 * (x_2 - x_1)) / (x_2 - x_1)

  (x_2 - x_1) * y_3 = (y_2 - y_1) * (x_3 - x_1) + y_1 * (x_2 - x_1)

Let's substitute (x_2, y_2) = (β * x_2', sign * y_2'):

β * x_2' * y_3 - x_1 * y_3 - sign * y_2' * x_3 + y_1 * x_3 + sign * y_2' * x_1 - y_1 * x_1 - β * y_1 * x_2' + x_1

• y_1 = 0

Let's group:

sign * (-y_2' * x_3 + y_2' * x_1) + β * (x_2' * x_3 + y_1 * x_2') + (-x_1 * y_3 + y_1 * x_3 - x_1 * y_1 + x_1 * y_1) = 0

Template Parameters

Field	Field being used for elements
Getters	A class that implements retrieval methods for PolyContainer
PolyContainer	Container with polynomials or their simulation

Member Function Documentation

accumulate_contribution()

template<class Field , class Getters , typename PolyContainer >

static void proof_system::plonk::widget::EllipticKernel< Field, Getters, PolyContainer >::accumulate_contribution ( PolyContainer &  polynomials, const challenge_array &  challenges, Field &  quotient, const size_t  i = 0  )

inlinestatic

Computes the single linear term for elliptic point addition.

Parameters

polynomials	Polynomial container or simulator
challenges	Challenge array
linear_terms	Output array
i	Gate index

---

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

• src/barretenberg/plonk/proof_system/widgets/transition_widgets/elliptic_widget.hpp