Barretenberg
The ZK-SNARK library at the core of Aztec
Loading...
Searching...
No Matches
Public Types | Public Member Functions | Static Public Member Functions | Public 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::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_straus_lookup_table_hints (const Element &base_point, const Element &offset_generator, size_t table_bits)
 Compute the output points generated when computing the Straus lookup table.
 

Public Attributes

size_t _table_bits
 
Builder * _context
 
std::vector< cycle_group< Builder > > point_table
 
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::straus lookup table object.

Constructs a table_bits lookup table.

If Builder is not ULTRA, table_bits = 1 If Builder is ULTRA, ROM table is used as lookup table

Template Parameters
Builder
Parameters
context
base_point
offset_generator
table_bits

Definition at line 57 of file straus_lookup_table.cpp.

Member Function Documentation

◆ compute_straus_lookup_table_hints()

template<typename Builder >
std::vector< typename straus_lookup_table< Builder >::Element > bb::stdlib::straus_lookup_table< Builder >::compute_straus_lookup_table_hints ( 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 28 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]

Template Parameters
Builder
Parameters
_index
Returns
cycle_group<Builder>

Definition at line 146 of file straus_lookup_table.cpp.

Member Data Documentation

◆ _context

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

Definition at line 64 of file straus_lookup_table.hpp.

◆ _table_bits

template<typename Builder >
size_t bb::stdlib::straus_lookup_table< Builder >::_table_bits

Definition at line 63 of file straus_lookup_table.hpp.

◆ point_table

template<typename Builder >
std::vector<cycle_group<Builder> > bb::stdlib::straus_lookup_table< Builder >::point_table

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

Definition at line 66 of file straus_lookup_table.hpp.

◆ tag

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

Definition at line 67 of file straus_lookup_table.hpp.

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