bb::plookup::keccak_tables::KeccakOutput Class Reference

Converts a base-11 sparse integer representation into a regular base-2 binary integer. Used by the Keccak hash algorithm to convert the output of the algorithm into a regular integer. More...

#include <keccak_output.hpp>

Static Public Member Functions
static constexpr std::array< uint64_t, TABLE_BITS >	get_scaled_bases ()
	Precompute an array of base multipliers (11^i for i = [0, ..., TABLE_BITS - 1]) Code is slightly faster at runtime if we compute this at compile time.
static std::array< uint64_t, 2 >	get_column_values_for_next_row (std::array< size_t, TABLE_BITS > &counts)
	Get column values for next row of plookup table. Used to generate plookup table row values.
static BasicTable	generate_keccak_output_table (BasicTableId id, const size_t table_index)
	Generate plookup table that maps a TABLE_BITS-slice of a base-11 integer into a base-2 integer.
static MultiTable	get_keccak_output_table (const MultiTableId id=KECCAK_FORMAT_OUTPUT)
	Create the KeccakOutput MultiTable used by plookup to generate a sequence of lookups.

Static Public Attributes
static constexpr uint64_t	BASE = 11
static constexpr uint64_t	EFFECTIVE_BASE = 2
static constexpr size_t	TABLE_BITS = 8
static constexpr uint64_t	OUTPUT_NORMALIZATION_TABLE [2] { 0, 1 }

Detailed Description

Converts a base-11 sparse integer representation into a regular base-2 binary integer. Used by the Keccak hash algorithm to convert the output of the algorithm into a regular integer.

Definition at line 22 of file keccak_output.hpp.

Member Function Documentation

generate_keccak_output_table()

static BasicTable bb::plookup::keccak_tables::KeccakOutput::generate_keccak_output_table ( BasicTableId  id, const size_t  table_index  )

inlinestatic

Generate plookup table that maps a TABLE_BITS-slice of a base-11 integer into a base-2 integer.

Parameters

id
table_index

Returns

BasicTable

Definition at line 94 of file keccak_output.hpp.

get_column_values_for_next_row()

static std::array< uint64_t, 2 > bb::plookup::keccak_tables::KeccakOutput::get_column_values_for_next_row ( std::array< size_t, TABLE_BITS > &  counts )

inlinestatic

Get column values for next row of plookup table. Used to generate plookup table row values.

Input counts is an array of quasi-bits that represent the current row. Method increases counts by 1 and returns the plookup table column values.

(a bit tricky to compute because each quasi-bit ranges from [0, 1], but we're working with base-11 numbers. i.e. unlike most of our lookup tables, the 1st column is not uniformly increasing by a constant value!)

Parameters

counts

The current row value represented as an array of quasi-bits

Returns

std::array<uint64_t, uint64_t> first and second columns of plookup table (3rd column is 0)

Definition at line 65 of file keccak_output.hpp.

get_keccak_output_table()

static MultiTable bb::plookup::keccak_tables::KeccakOutput::get_keccak_output_table ( const MultiTableId  id = KECCAK_FORMAT_OUTPUT )

inlinestatic

Create the KeccakOutput MultiTable used by plookup to generate a sequence of lookups.

Keccak operates on 64-bit integers, but the lookup table only indexes TABLE_BITS bits.

i.e. multiple lookups are required for a single 64-bit integer.

If we group these lookups together, we can derive the plookup column values from the relative difference between wire values.

i.e. we do not need to split our 64-bit input into TABLE_BITS slices, perform the lookup and add together the output slices

Instead, e.g. for TABLE_BITS = 8 we have inputs A, B where A = \sum_{i=0}^7 A_i * 11^8 B = \sum_{i=0}^7 B_i * 2^8

Our plookup gates will produce a gates with the following wire values:

W1	W2	W3
\sum_{i=0}^7 A_i * 2^i	\sum_{i=0}^7 B_i * 11^i	0
\sum_{i=1}^7 A_i * 2^i	\sum_{i=1}^7 B_i * 11^i	0
\sum_{i=2}^7 A_i * 2^i	\sum_{i=2}^7 B_i * 11^i	0
...	...	...
A^7	B^7	0

The plookup protocol extracts the 1st and 2nd lookup column values by taking:

 Colunn1 = W1[i] - 11^8 . W1[i + 1]
 Colunn2 = W2[i] - 2^8 . W2[i + 1]

(where the -11^8, -2^8 coefficients are stored in a precomputed selector polynomial)

This MultiTable construction defines the value of these precomputed selector polynomial values, as well as defines how the column values are derived from a starting input value.

Parameters

id

Returns

MultiTable

Definition at line 160 of file keccak_output.hpp.

get_scaled_bases()

static constexpr std::array< uint64_t, TABLE_BITS > bb::plookup::keccak_tables::KeccakOutput::get_scaled_bases ( )

inlinestaticconstexpr

Precompute an array of base multipliers (11^i for i = [0, ..., TABLE_BITS - 1]) Code is slightly faster at runtime if we compute this at compile time.

Returns

constexpr std::array<uint64_t, TABLE_BITS>

Definition at line 41 of file keccak_output.hpp.

Member Data Documentation

BASE

constexpr uint64_t bb::plookup::keccak_tables::KeccakOutput::BASE = 11

staticconstexpr

Definition at line 25 of file keccak_output.hpp.

EFFECTIVE_BASE

constexpr uint64_t bb::plookup::keccak_tables::KeccakOutput::EFFECTIVE_BASE = 2

staticconstexpr

Definition at line 30 of file keccak_output.hpp.

OUTPUT_NORMALIZATION_TABLE

constexpr uint64_t bb::plookup::keccak_tables::KeccakOutput::OUTPUT_NORMALIZATION_TABLE[2] { 0, 1 }

staticconstexpr

Definition at line 33 of file keccak_output.hpp.

TABLE_BITS

constexpr size_t bb::plookup::keccak_tables::KeccakOutput::TABLE_BITS = 8

staticconstexpr

Definition at line 31 of file keccak_output.hpp.

---

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

• src/barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_output.hpp