Per-window plookup tables for the secp256r1 fixed-base scalar multiplication. More...

#include <secp256r1_fixed_base.hpp>

Inheritance diagram for bb::plookup::secp256r1_fixed_base::table:

Public Types
enum	AxisIndex : size_t { AXIS_XLO = 0 , AXIS_XHI = 1 , AXIS_YLO = 2 , AXIS_YHI = 3 }

using	G1 = bb::secp256r1::g1

using	Element = G1::element

using	AffineElement = G1::affine_element

Static Public Member Functions
static constexpr BasicTableId	axis_start_id (AxisIndex axis)
	Maps a per-axis BasicTableId range start to its AxisIndex; used by the create_basic_table dispatch.

static void	init_tables ()
	Precompute the 32 × 256 native points (idempotent, thread-safe). The (limb_a, limb_b) pairs for each axis are derived on demand by the get_*_values functions.

static AffineElement	total_offset ()
	Sum of all per-window offsets (2^0 + 2^1 + ... + 2^31) · H. Subtracted from the chain-add result of the looked-up points to recover u · G in the in-circuit caller.

template<AxisIndex axis, size_t window_idx>
static std::array< bb::fr, 2 >	get_values (std::array< uint64_t, 2 > key)
	Native lookup callback used by BasicTable::get_values_from_key. `axis_window_packed` encodes the window position in the high 32 bits and the axis index in the low 32 bits; key[0] is the 8-bit window byte. Defined out-of-line because the function pointer is stored by BasicTable rather than the templated generators below.

template<AxisIndex axis, size_t window_idx>
static BasicTable	generate_basic_table (BasicTableId id, size_t table_index)
	Construct one BasicTable instance for (axis, window_idx). `id` is the BasicTableId assigned by the caller (= axis_start_id(axis) + window_idx) and `table_index` is the index this table will occupy in the builder's lookup_tables deque.

template<AxisIndex axis>
static BasicTable	generate_basic_table_runtime (BasicTableId id, size_t window_idx, size_t table_index)
	Runtime dispatch helper used by plookup_tables.cpp::create_basic_table. Selects table contents using window_idx and assigns the independently supplied circuit-local table_index.

static MultiTable	get_multitable (MultiTableId id, AxisIndex axis, bool is_lo)
	Construct one of the 10 MultiTables described in the file-header docstring. `is_lo = true` chains windows [0, NUM_WINDOWS_LO); `is_lo = false` chains [NUM_WINDOWS_LO, NUM_WINDOWS). Used by `element::secp256r1_fixed_base_mul` via `plookup_read<C>::get_lookup_accumulators`.

static const AffineElement &	get_entry (size_t window_idx, size_t k)
	Access a precomputed entry. The biggroup caller uses this to compute proving-time hint values (val_a, val_b) before emitting create_lookup_gate calls.

static std::array< bb::fr, 2 >	extract_axis (const AffineElement &point, AxisIndex axis)
	Split an affine point into the (limb_a, limb_b) pair for the requested axis. Used by the BasicTable generators above and by callers that need to set up lookup-gate hint values.

Static Public Member Functions inherited from bb::plookup::Secp256r1FixedBaseParams
static constexpr size_t	window_bits (size_t w)

static constexpr size_t	table_size (size_t w)

Static Private Attributes
static std::array< std::array< AffineElement, TABLE_SIZE_BIG >, NUM_WINDOWS >	native_table

static AffineElement	cached_total_offset

static std::once_flag	init_flag

Additional Inherited Members
Static Public Attributes inherited from bb::plookup::Secp256r1FixedBaseParams
static constexpr size_t	NUM_WINDOWS_LO = 20

static constexpr size_t	NUM_WINDOWS_HI = 18

static constexpr size_t	NUM_WINDOWS = NUM_WINDOWS_LO + NUM_WINDOWS_HI

static constexpr size_t	WINDOW_BITS = 7

static constexpr size_t	WINDOW_BITS_LO_TAIL = 3

static constexpr size_t	WINDOW_BITS_HI_TAIL = 1

static constexpr size_t	TABLE_SIZE_BIG = 1ULL << WINDOW_BITS

static constexpr size_t	TABLE_SIZE_LO_TAIL = 1ULL << WINDOW_BITS_LO_TAIL

static constexpr size_t	TABLE_SIZE_HI_TAIL = 1ULL << WINDOW_BITS_HI_TAIL

static constexpr size_t	NUM_AXES = 4

static constexpr size_t	LO_TAIL_WINDOW = NUM_WINDOWS_LO - 1

static constexpr size_t	HI_TAIL_WINDOW = NUM_WINDOWS - 1

Detailed Description

Per-window plookup tables for the secp256r1 fixed-base scalar multiplication.

Tables back the Pedersen-style fixed-base multiplication used by element::secp256r1_fixed_base_mul in biggroup_secp256r1.hpp.

The scalar u is sliced little-endian into 7-bit "big" windows plus one short tail window per half. For window index w ∈ [0, NUM_WINDOWS), entry k ∈ [0, table_size(w)) holds the point P_{w,k} := k · 2^(bit_offset(w)) · G + 2^w · H where G is the secp256r1 generator, H is the precomputed "biggroup table offset generator", and bit_offset(w) is the cumulative bit position of window w (sum of window_bits over [0, w)). Adding 2^w · H to every entry per-window keeps the entries distinct across windows so the in-circuit chain-add of the looked-up points never hits an incomplete-addition edge case for honest inputs. The aggregate offset (2^NUM_WINDOWS − 1) · H is constant and is subtracted off at the end of the in-circuit computation.

Each point P_{w,k} is split across four basic tables, one per binary-basis limb axis:

XLO: (x_limb_0, x_limb_1)
XHI: (x_limb_2, x_limb_3)
YLO: (y_limb_0, y_limb_1)
YHI: (y_limb_2, y_limb_3)

The bigfield prime-basis limb (x mod p / y mod p) is recomputed in-circuit from the four binary limbs by the caller, trading 2 add gates per coordinate per window for 8192 fewer preprocessed table rows.

Window scheme is 7-bit dominant with short tails: the bigfield's lo half (136 bits) is sliced into 19 × 7-bit "big" windows plus 1 × 3-bit lo-tail; the hi half (120 bits) is sliced into 17 × 7-bit "big" windows plus 1 × 1-bit hi-tail. That gives 36 × 7-bit windows in total (table size 128 each) plus two small tail tables (size 8 for lo-tail, size 2 for hi-tail). All inter-window boundaries are 7-bit aligned, so the MultiTable column-1 step is uniformly 128 — only the per-window slice_sizes vector encodes the tail bit-widths.

Four contiguous BasicTableId ranges (NUM_WINDOWS = 38 IDs each) are reserved in types.hpp; ID SECP256R1_FIXED_BASE_<AXIS>_0 + w is the table for axis AXIS, window w. The two tail positions within each range are also exposed as named indices LO_TAIL_WINDOW = NUM_WINDOWS_LO - 1 and HI_TAIL_WINDOW = NUM_WINDOWS - 1 for use by window_bits/table_size.

Per-axis the 38 BasicTables are bundled into two MultiTables — one over the 20 lo windows and one over the 18 hi windows (4 × 2 = 8 MultiTableIds: SECP256R1_FIXED_BASE_<AXIS>_<LO|HI>). Columns 2/3 use step 0 so each window's C2/C3 entries are the per-window (limb_a, limb_b) pair (no accumulation).

Table data is precomputed once (under std::call_once) at the first lookup. Total preprocessed rows: 4 · (19 · 128 + 8 + 17 · 128 + 2) = 18,472 — down from 32,768 with uniform 8-bit windows.

Definition at line 59 of file secp256r1_fixed_base.hpp.

Member Typedef Documentation

◆ AffineElement

using bb::plookup::secp256r1_fixed_base::table::AffineElement = G1::affine_element

Definition at line 63 of file secp256r1_fixed_base.hpp.

◆ Element

using bb::plookup::secp256r1_fixed_base::table::Element = G1::element

Definition at line 62 of file secp256r1_fixed_base.hpp.

◆ G1

using bb::plookup::secp256r1_fixed_base::table::G1 = bb::secp256r1::g1

Definition at line 61 of file secp256r1_fixed_base.hpp.

Member Enumeration Documentation

◆ AxisIndex

enum bb::plookup::secp256r1_fixed_base::table::AxisIndex : size_t

Enumerator
AXIS_XLO
AXIS_XHI
AXIS_YLO
AXIS_YHI

Definition at line 65 of file secp256r1_fixed_base.hpp.

Member Function Documentation

◆ axis_start_id()

static constexpr BasicTableId bb::plookup::secp256r1_fixed_base::table::axis_start_id ( AxisIndex axis )

inlinestaticconstexpr

Maps a per-axis BasicTableId range start to its AxisIndex; used by the create_basic_table dispatch.

Definition at line 75 of file secp256r1_fixed_base.hpp.

◆ extract_axis()

std::array< bb::fr, 2 > bb::plookup::secp256r1_fixed_base::table::extract_axis	(	const AffineElement &	point,
		AxisIndex	axis
	)

static

Split an affine point into the (limb_a, limb_b) pair for the requested axis. Used by the BasicTable generators above and by callers that need to set up lookup-gate hint values.

Definition at line 67 of file secp256r1_fixed_base.cpp.

◆ generate_basic_table()

template<table::AxisIndex axis, size_t window_idx>

BasicTable bb::plookup::secp256r1_fixed_base::table::generate_basic_table	(	BasicTableId	id,
		size_t	table_index
	)

static

Construct one BasicTable instance for (axis, window_idx). id is the BasicTableId assigned by the caller (= axis_start_id(axis) + window_idx) and table_index is the index this table will occupy in the builder's lookup_tables deque.

Definition at line 102 of file secp256r1_fixed_base.cpp.

◆ generate_basic_table_runtime()

template<table::AxisIndex axis>

BasicTable bb::plookup::secp256r1_fixed_base::table::generate_basic_table_runtime	(	BasicTableId	id,
		size_t	window_idx,
		size_t	table_index
	)

static

Runtime dispatch helper used by plookup_tables.cpp::create_basic_table. Selects table contents using window_idx and assigns the independently supplied circuit-local table_index.

Definition at line 147 of file secp256r1_fixed_base.cpp.

◆ get_entry()

static const AffineElement & bb::plookup::secp256r1_fixed_base::table::get_entry	(	size_t	window_idx,
		size_t	k
	)

inlinestatic

Access a precomputed entry. The biggroup caller uses this to compute proving-time hint values (val_a, val_b) before emitting create_lookup_gate calls.

Definition at line 136 of file secp256r1_fixed_base.hpp.

◆ get_multitable()

MultiTable bb::plookup::secp256r1_fixed_base::table::get_multitable	(	MultiTableId	id,
		AxisIndex	axis,
		bool	is_lo
	)

static

Construct one of the 10 MultiTables described in the file-header docstring. is_lo = true chains windows [0, NUM_WINDOWS_LO); is_lo = false chains [NUM_WINDOWS_LO, NUM_WINDOWS). Used by element::secp256r1_fixed_base_mul via plookup_read<C>::get_lookup_accumulators.

Definition at line 193 of file secp256r1_fixed_base.cpp.

◆ get_values()

template<table::AxisIndex axis, size_t window_idx>

std::array< bb::fr, 2 > bb::plookup::secp256r1_fixed_base::table::get_values ( std::array< uint64_t, 2 > key )

static

Native lookup callback used by BasicTable::get_values_from_key. axis_window_packed encodes the window position in the high 32 bits and the axis index in the low 32 bits; key[0] is the 8-bit window byte. Defined out-of-line because the function pointer is stored by BasicTable rather than the templated generators below.

Definition at line 93 of file secp256r1_fixed_base.cpp.

◆ init_tables()

void bb::plookup::secp256r1_fixed_base::table::init_tables ( )

static

Precompute the 32 × 256 native points (idempotent, thread-safe). The (limb_a, limb_b) pairs for each axis are derived on demand by the get_*_values functions.

Definition at line 17 of file secp256r1_fixed_base.cpp.

◆ total_offset()

table::AffineElement bb::plookup::secp256r1_fixed_base::table::total_offset ( )

static

Sum of all per-window offsets (2^0 + 2^1 + ... + 2^31) · H. Subtracted from the chain-add result of the looked-up points to recover u · G in the in-circuit caller.

Definition at line 61 of file secp256r1_fixed_base.cpp.

Member Data Documentation

◆ cached_total_offset

table::AffineElement bb::plookup::secp256r1_fixed_base::table::cached_total_offset

staticprivate

Definition at line 155 of file secp256r1_fixed_base.hpp.

◆ init_flag

std::once_flag bb::plookup::secp256r1_fixed_base::table::init_flag

staticprivate

Definition at line 156 of file secp256r1_fixed_base.hpp.

◆ native_table

std::array< std::array< table::AffineElement, table::TABLE_SIZE_BIG >, table::NUM_WINDOWS > bb::plookup::secp256r1_fixed_base::table::native_table

staticprivate

Definition at line 154 of file secp256r1_fixed_base.hpp.

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

src/barretenberg/stdlib_circuit_builders/plookup_tables/secp256r1_fixed_base.hpp
src/barretenberg/stdlib_circuit_builders/plookup_tables/secp256r1_fixed_base.cpp

Public Types

Static Public Member Functions

Static Private Attributes

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ AffineElement

◆ Element

◆ G1

Member Enumeration Documentation

◆ AxisIndex

Member Function Documentation

◆ axis_start_id()

◆ extract_axis()

◆ generate_basic_table()

◆ generate_basic_table_runtime()

◆ get_entry()

◆ get_multitable()

◆ get_values()

◆ init_tables()

◆ total_offset()

Member Data Documentation

◆ cached_total_offset

◆ init_flag

◆ native_table