cycle_group represents a group Element of the proving system's embedded curve i.e. a curve with a cofactor 1 defined over a field equal to the circuit's native field Composer::FF More...

#include <cycle_group.hpp>

Classes
struct	cycle_scalar
	cycle_scalar represents a member of the cycle curve SCALAR FIELD. This is NOT the native circuit field type. i.e. for a BN254 circuit, cycle_group will be Grumpkin and cycle_scalar will be Grumpkin::ScalarField (BN254 native field is BN254::ScalarField == Grumpkin::BaseField) More...

struct	straus_lookup_table
	straus_lookup_table computes a lookup table of size 1 << table_bits More...

struct	straus_scalar_slice
	straus_scalar_slice decomposes an input scalar into `table_bits` bit-slices. Used in `batch_mul`, which ses the Straus multiscalar multiplication algorithm. More...

Public Types
using	field_t = stdlib::field_t< Composer >

using	bool_t = stdlib::bool_t< Composer >

using	witness_t = stdlib::witness_t< Composer >

using	FF = typename Composer::FF

using	Curve = typename Composer::EmbeddedCurve

using	Group = typename Curve::Group

using	Element = typename Curve::Element

using	AffineElement = typename Curve::AffineElement

using	GeneratorContext = crypto::GeneratorContext< Curve >

using	ScalarField = typename Curve::ScalarField

Public Member Functions
	cycle_group (Composer *_context=nullptr)

	cycle_group (field_t _x, field_t _y, bool_t _is_infinity)
	Construct a new cycle group<Composer>::cycle group object.

	cycle_group (const FF &_x, const FF &_y, bool _is_infinity)
	Construct a new cycle group<Composer>::cycle group object.

	cycle_group (const AffineElement &_in)
	Construct a cycle_group object out of an AffineElement object.

Composer *	get_context (const cycle_group &other) const

Composer *	get_context () const

AffineElement	get_value () const

bool	is_constant () const

bool_t	is_point_at_infinity () const

void	set_point_at_infinity (const bool_t &is_infinity)

void	validate_is_on_curve () const
	On-curve check.

cycle_group	dbl () const
	Evaluates a doubling. Does not use Ultra double gate.

cycle_group	dbl () const

cycle_group	unconditional_add (const cycle_group &other) const
	Will evaluate ECC point addition over `this` and `other`. Incomplete addition formula edge cases are NOT* checked! Only use this method if you know the x-coordinates of the operands cannot collide Standard version that does not use ecc group gate.

cycle_group	unconditional_add (const cycle_group &other) const

cycle_group	unconditional_subtract (const cycle_group &other) const
	will evaluate ECC point subtraction over `this` and `other`. Incomplete addition formula edge cases are NOT* checked! Only use this method if you know the x-coordinates of the operands cannot collide

cycle_group	checked_unconditional_add (const cycle_group &other) const
	Will evaluate ECC point addition over `*this` and `other`. Uses incomplete addition formula If incomplete addition formula edge cases are triggered (x-coordinates of operands collide), the constraints produced by this method will be unsatisfiable. Useful when an honest prover will not produce a point collision with overwhelming probability, but a cheating prover will be able to.

cycle_group	checked_unconditional_subtract (const cycle_group &other) const
	Will evaluate ECC point subtraction over `*this` and `other`. Uses incomplete addition formula If incomplete addition formula edge cases are triggered (x-coordinates of operands collide), the constraints produced by this method will be unsatisfiable. Useful when an honest prover will not produce a point collision with overwhelming probability, but a cheating prover will be able to.

cycle_group	operator+ (const cycle_group &other) const
	Will evaluate ECC point addition over `*this` and `other`. This method uses complete addition i.e. is compatible with edge cases. Method is expensive due to needing to evaluate both an addition, a doubling, plus conditional logic to handle points at infinity.

cycle_group	operator- (const cycle_group &other) const
	Will evaluate ECC point subtraction over `*this` and `other`. This method uses complete addition i.e. is compatible with edge cases. Method is expensive due to needing to evaluate both an addition, a doubling, plus conditional logic to handle points at infinity.

cycle_group	operator- () const
	Negates a point.

cycle_group &	operator+= (const cycle_group &other)

cycle_group &	operator-= (const cycle_group &other)

cycle_group	operator* (const cycle_scalar &scalar) const

cycle_group &	*operator=** (const cycle_scalar &scalar)

bool_t	operator== (const cycle_group &other) const

void	assert_equal (const cycle_group &other, std::string const &msg="cycle_group::assert_equal") const

cycle_group	operator/ (const cycle_group &other) const

Static Public Member Functions
static cycle_group	from_witness (Composer *_context, const AffineElement &_in)
	Converts an AffineElement into a circuit witness.

static cycle_group	from_constant_witness (Composer *_context, const AffineElement &_in)
	Converts a native AffineElement into a witness, but constrains the witness values to be known constants.

static cycle_group	batch_mul (const std::vector< cycle_scalar > &scalars, const std::vector< cycle_group > &base_points, GeneratorContext context={})
	Multiscalar multiplication algorithm.

static cycle_group	conditional_assign (const bool_t &predicate, const cycle_group &lhs, const cycle_group &rhs)

Public Attributes
field_t	x

field_t	y

Static Public Attributes
static constexpr size_t	STANDARD_NUM_TABLE_BITS = 1

static constexpr size_t	ULTRA_NUM_TABLE_BITS = 4

static constexpr bool	IS_ULTRA = Composer::CIRCUIT_TYPE == CircuitType::ULTRA

static constexpr size_t	TABLE_BITS = IS_ULTRA ? ULTRA_NUM_TABLE_BITS : STANDARD_NUM_TABLE_BITS

static constexpr size_t	NUM_BITS = ScalarField::modulus.get_msb() + 1

static constexpr size_t	NUM_ROUNDS = (NUM_BITS + TABLE_BITS - 1) / TABLE_BITS

static constexpr std::string_view	OFFSET_GENERATOR_DOMAIN_SEPARATOR = "cycle_group_offset_generator"

Detailed Description

template<typename Composer>
class proof_system::plonk::stdlib::cycle_group< Composer >

cycle_group represents a group Element of the proving system's embedded curve i.e. a curve with a cofactor 1 defined over a field equal to the circuit's native field Composer::FF

(todo @zac-williamson) once the pedersen refactor project is finished, this class will supercede stdlib::group

Template Parameters

Composer

Constructor & Destructor Documentation

◆ cycle_group() [1/3]

template<typename Composer >

proof_system::plonk::stdlib::cycle_group< Composer >::cycle_group	(	field_t	_x,
		field_t	_y,
		bool_t	is_infinity
	)

Construct a new cycle group<Composer>::cycle group object.

Parameters

_x
_y
is_infinity

◆ cycle_group() [2/3]

template<typename Composer >

proof_system::plonk::stdlib::cycle_group< Composer >::cycle_group	(	const FF &	_x,
		const FF &	_y,
		bool	is_infinity
	)

Construct a new cycle group<Composer>::cycle group object.

is_infinity is a circuit constant. We EXPLICITLY require that whether this point is infinity/not infinity is known at circuit-construction time and we know this point is on the curve. These checks are not constrained. Use from_witness if these conditions are not met. Examples of when conditions are met: point is a derived from a point that is on the curve + not at infinity. e.g. output of a doubling operation

Template Parameters

Composer

Parameters

_x
_y
is_infinity

◆ cycle_group() [3/3]

template<typename Composer >

proof_system::plonk::stdlib::cycle_group< Composer >::cycle_group ( const AffineElement & _in )

Construct a cycle_group object out of an AffineElement object.

Note: This produces a circuit-constant object i.e. known at compile-time, no constraints. If _in is not fixed for a given circuit, use from_witness instead

Template Parameters

Composer

Parameters

_in

Member Function Documentation

◆ batch_mul()

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::batch_mul	(	const std::vector< cycle_scalar > &	scalars,
		const std::vector< cycle_group< Composer > > &	base_points,
		GeneratorContext	context = `{}`
	)

static

Multiscalar multiplication algorithm.

Uses the Straus MSM algorithm. batch_mul splits inputs into three categories:

point and scalar multiplier are both constant
point is constant, scalar multiplier is a witness
point is a witness, scalar multiplier can be witness or constant

For Category 1, the scalar mul can be precomuted without constraints For Category 2, we use a fixed-base variant of Straus (with plookup tables if available). For Category 3, we use standard Straus. The results from all 3 categories are combined and returned as an output point.

Note

batch_mul can handle all known cases of trigger incomplete addition formula exceptions and other weirdness:

some/all of the input points are points at infinity
some/all of the input scalars are 0
some/all input points are equal to each other
output is the point at infinity
input vectors are empty

offset_generator_data is a pointer to precomputed offset generator list. There is a default parameter point that poitns to a list with DEFAULT_NUM_GENERATORS generator points (32) If more offset generators are required, they will be derived in-place which can be expensive. (num required offset generators is either num input points + 1 or num input points + 2, depends on if one or both of _fixed_base_batch_mul_internal, _variable_base_batch_mul_internal are called) If you're calling this function repeatedly and you KNOW you need >32 offset generators, it's faster to create a generator_data object with the required size and pass it in as a parameter.

Template Parameters

Composer

Parameters

scalars
base_points
offset_generator_data

Returns: cycle_group<Composer>

◆ checked_unconditional_add()

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::checked_unconditional_add ( const cycle_group< Composer > & other ) const

Will evaluate ECC point addition over *this and other. Uses incomplete addition formula If incomplete addition formula edge cases are triggered (x-coordinates of operands collide), the constraints produced by this method will be unsatisfiable. Useful when an honest prover will not produce a point collision with overwhelming probability, but a cheating prover will be able to.

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

◆ checked_unconditional_subtract()

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::checked_unconditional_subtract ( const cycle_group< Composer > & other ) const

Will evaluate ECC point subtraction over *this and other. Uses incomplete addition formula If incomplete addition formula edge cases are triggered (x-coordinates of operands collide), the constraints produced by this method will be unsatisfiable. Useful when an honest prover will not produce a point collision with overwhelming probability, but a cheating prover will be able to.

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

◆ dbl()

template<typename Composer >
requires IsUltraArithmetic<Composer>

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::dbl

Evaluates a doubling. Does not use Ultra double gate.

Evaluates a doubling. Uses Ultra double gate.

Template Parameters

Composer

Returns: cycle_group<Composer>

Template Parameters

Composer

Returns: cycle_group<Composer>

◆ from_constant_witness()

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::from_constant_witness	(	Composer *	_context,
		const AffineElement &	_in
	)

static

Converts a native AffineElement into a witness, but constrains the witness values to be known constants.

When performing group operations where one operand is a witness and one is a constant, it can be more efficient to convert the constant element into a witness. This is because we have custom gates that evaluate additions in one constraint, but only if both operands are witnesses.

Template Parameters

Composer

Parameters

_context
_in

Returns: cycle_group<Composer>

◆ from_witness()

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::from_witness	(	Composer *	_context,
		const AffineElement &	_in
	)

static

Converts an AffineElement into a circuit witness.

Somewhat expensive as we do an on-curve check and _is_infinity is a witness and not a constant. If an element is being converted where it is known the element is on the curve and/or cannot be point at infinity, it is best to use other methods (e.g. direct conversion of field_t coordinates)

Template Parameters

Composer

Parameters

_context
_in

Returns: cycle_group<Composer>

◆ operator+()

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::operator+ ( const cycle_group< Composer > & other ) const

Will evaluate ECC point addition over *this and other. This method uses complete addition i.e. is compatible with edge cases. Method is expensive due to needing to evaluate both an addition, a doubling, plus conditional logic to handle points at infinity.

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

◆ operator-() [1/2]

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::operator-

Negates a point.

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

◆ operator-() [2/2]

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::operator- ( const cycle_group< Composer > & other ) const

Will evaluate ECC point subtraction over *this and other. This method uses complete addition i.e. is compatible with edge cases. Method is expensive due to needing to evaluate both an addition, a doubling, plus conditional logic to handle points at infinity.

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

◆ unconditional_add()

template<typename Composer >
requires IsUltraArithmetic<Composer>

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::unconditional_add ( const cycle_group< Composer > & other ) const

Will evaluate ECC point addition over *this and other. Incomplete addition formula edge cases are NOT checked! Only use this method if you know the x-coordinates of the operands cannot collide Standard version that does not use ecc group gate.

Will evaluate ECC point addition over *this and other. Incomplete addition formula edge cases are NOT checked! Only use this method if you know the x-coordinates of the operands cannot collide Ultra version that uses ecc group gate.

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

◆ unconditional_subtract()

template<typename Composer >

cycle_group< Composer > proof_system::plonk::stdlib::cycle_group< Composer >::unconditional_subtract ( const cycle_group< Composer > & other ) const

will evaluate ECC point subtraction over *this and other. Incomplete addition formula edge cases are NOT checked! Only use this method if you know the x-coordinates of the operands cannot collide

Template Parameters

Composer

Parameters

other

Returns: cycle_group<Composer>

◆ validate_is_on_curve()

template<typename Composer >

void proof_system::plonk::stdlib::cycle_group< Composer >::validate_is_on_curve

On-curve check.

Template Parameters

Composer

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

src/barretenberg/stdlib/primitives/group/cycle_group.hpp
src/barretenberg/stdlib/primitives/group/cycle_group.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ cycle_group() [1/3]

◆ cycle_group() [2/3]

◆ cycle_group() [3/3]

Member Function Documentation

◆ batch_mul()

◆ checked_unconditional_add()

◆ checked_unconditional_subtract()

◆ dbl()

◆ from_constant_witness()

◆ from_witness()

◆ operator+()

◆ operator-() [1/2]

◆ operator-() [2/2]

◆ unconditional_add()

◆ unconditional_subtract()

◆ validate_is_on_curve()