Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Member Functions | Private Attributes | List of all members
bb::stdlib::straus_lookup_table< Builder > Class Template Reference

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

#include <straus_lookup_table.hpp>

Public Types

using field_t = stdlib::field_t< Builder >
 
using Curve = typename Builder::EmbeddedCurve
 
using Group = typename Curve::Group
 
using Element = typename Curve::Element
 
using AffineElement = typename Curve::AffineElement
 

Public Member Functions

 straus_lookup_table ()=default
 
 straus_lookup_table (Builder *context, const cycle_group< Builder > &base_point, const cycle_group< Builder > &offset_generator, size_t table_bits, std::optional< std::span< AffineElement > > hints=std::nullopt)
 Construct a new straus lookup table object.
 
cycle_group< Builder > read (const field_t &index)
 Given an _index witness, return straus_lookup_table[index]
 

Static Public Member Functions

static std::vector< Element > compute_native_table (const Element &base_point, const Element &offset_generator, size_t table_bits)
 Compute the output points generated when computing the Straus lookup table.
 

Private Attributes

Builder * _context
 
size_t rom_id = 0
 
OriginTag tag {}
 

Detailed Description

template<typename Builder>
class bb::stdlib::straus_lookup_table< Builder >

straus_lookup_table computes a lookup table of size 1 << table_bits

for an input base_point [P] and offset_generator point [G], where N = 1 << table_bits, the following is computed:

{ [G] + 0.[P], [G] + 1.[P], ..., [G] + (N - 1).[P] }

The point [G] is used to ensure that we do not have to handle the point at infinity associated with 0.[P].

For an HONEST Prover, the probability of [G] and [P] colliding is equivalent to solving the dlog problem. This allows us to partially ignore the incomplete addition formula edge-cases for short Weierstrass curves.

When adding group elements in batch_mul, we can constrain+assert the x-coordinates of the operand points do not match. An honest prover will never trigger the case where x-coordinates match due to the above. Validating x-coordinates do not match is much cheaper than evaluating the full complete addition formulae for short Weierstrass curves.

Note
For the case of fixed-base scalar multipliation, all input points are defined at circuit compile. We can ensure that all Provers cannot create point collisions between the base points and offset generators. For this restricted case we can skip the x-coordiante collision checks when performing group operations.
straus_lookup_table uses Ultra ROM tables if available. If not, we use simple conditional assignment constraints and restrict the table size to be 1 bit.

Definition at line 44 of file straus_lookup_table.hpp.

Member Typedef Documentation

◆ AffineElement

template<typename Builder >
using bb::stdlib::straus_lookup_table< Builder >::AffineElement = typename Curve::AffineElement

Definition at line 50 of file straus_lookup_table.hpp.

◆ Curve

template<typename Builder >
using bb::stdlib::straus_lookup_table< Builder >::Curve = typename Builder::EmbeddedCurve

Definition at line 47 of file straus_lookup_table.hpp.

◆ Element

template<typename Builder >
using bb::stdlib::straus_lookup_table< Builder >::Element = typename Curve::Element

Definition at line 49 of file straus_lookup_table.hpp.

◆ field_t

template<typename Builder >
using bb::stdlib::straus_lookup_table< Builder >::field_t = stdlib::field_t<Builder>

Definition at line 46 of file straus_lookup_table.hpp.

◆ Group

template<typename Builder >
using bb::stdlib::straus_lookup_table< Builder >::Group = typename Curve::Group

Definition at line 48 of file straus_lookup_table.hpp.

Constructor & Destructor Documentation

◆ straus_lookup_table() [1/2]

template<typename Builder >
bb::stdlib::straus_lookup_table< Builder >::straus_lookup_table ( )
default

◆ straus_lookup_table() [2/2]

template<typename Builder >
bb::stdlib::straus_lookup_table< Builder >::straus_lookup_table ( Builder *  context,
const cycle_group< Builder > &  base_point,
const cycle_group< Builder > &  offset_generator,
size_t  table_bits,
std::optional< std::span< AffineElement > >  hints = std::nullopt 
)

Construct a new straus lookup table object.

Table is a length N = 1 << table_bits ROM-array containing the points: { [G] + 0.[P], [G] + 1.[P], ..., [G] + (N - 1).[P] }

Template Parameters
Builder
Parameters
context
base_point
offset_generator
table_bits

Definition at line 51 of file straus_lookup_table.cpp.

Member Function Documentation

◆ compute_native_table()

template<typename Builder >
std::vector< typename straus_lookup_table< Builder >::Element > bb::stdlib::straus_lookup_table< Builder >::compute_native_table ( const Element &  base_point,
const Element &  offset_generator,
size_t  table_bits 
)
static

Compute the output points generated when computing the Straus lookup table.

When performing an MSM, we first compute all the witness values as Element types (with a Z-coordinate), and then we batch-convert the points into affine representation AffineElement This avoids the need to compute a modular inversion for every group operation, which dramatically cuts witness generation times

Template Parameters
Builder
Parameters
base_point
offset_generator
table_bits
Returns
std::vector<typename straus_lookup_table<Builder>::Element>

Definition at line 27 of file straus_lookup_table.cpp.

◆ read()

template<typename Builder >
cycle_group< Builder > bb::stdlib::straus_lookup_table< Builder >::read ( const field_t &  _index)

Given an _index witness, return straus_lookup_table[index]

Performs a ROM read which costs one gate. If _index is constant, we convert it to a witness constrained to equal the constant value.

Template Parameters
Builder
Parameters
_index
Returns
cycle_group<Builder>

Definition at line 142 of file straus_lookup_table.cpp.

Member Data Documentation

◆ _context

template<typename Builder >
Builder* bb::stdlib::straus_lookup_table< Builder >::_context
private

Definition at line 65 of file straus_lookup_table.hpp.

◆ rom_id

template<typename Builder >
size_t bb::stdlib::straus_lookup_table< Builder >::rom_id = 0
private

Definition at line 66 of file straus_lookup_table.hpp.

◆ tag

template<typename Builder >
OriginTag bb::stdlib::straus_lookup_table< Builder >::tag {}
private

Definition at line 67 of file straus_lookup_table.hpp.

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