bb::plookup::keccak_tables::Theta Class Reference

Generates plookup tables required for THETA round of Keccak hash function. More...

#include <keccak_theta.hpp>

Static Public Member Functions
static std::array< bb::fr, 2 >	get_theta_renormalization_values (const std::array< uint64_t, 2 > key)
	Given a table input value, return the table output value.
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_theta_renormalization_table (BasicTableId id, const size_t table_index)
	Generate plookup table that normalizes a TABLE_BITS-slice of a base-11 integer.
static MultiTable	get_theta_output_table (const MultiTableId id=KECCAK_THETA_OUTPUT)
	Create the THETA MultiTable used by plookup to generate a sequence of lookups.

Static Public Attributes
static constexpr size_t	TABLE_BITS = 4
static constexpr uint64_t	BASE = 11
static constexpr uint64_t	THETA_NORMALIZATION_TABLE [11]

Detailed Description

Generates plookup tables required for THETA round of Keccak hash function.

Keccak has 25 hash lanes, each represented as 64-bit integers. The THETA round performs the following operation on 3 hash lanes:

C0 = A0 ^ A1 ^ A2 ^ A3 ^ A4 C1 = B0 ^ B1 ^ B2 ^ B3 ^ B4 D = C0 ^ ROTATE_LEFT(C1, 1)

We evaluate in-circuit using a base-11 sparse integer representation:

P = \sum_{j=0}^63 b_i * 11^i

In this representation we evaluate CHI via the linear expression

C0 = A0 + A1 + A2 + A3 + A4 C1 = B0 + B1 + B2 + B3 + B4 D = C0 + ROTATE_LEFT(C1, 1)

We use base-11 spare representation because the maximum value of each 'quasi-bit' of D is 10

THETA round uses a plookup table that normalizes the algebraic output.

This can be represented via the 'truth table' for each base-11 quasi-bit:

Algebraic Output	Binary Output
0	0
1	1
2	0
3	1
4	0
5	1
6	0
7	1
8	0
9	1
10	0

i.e. even = 0, odd = 1

Definition at line 58 of file keccak_theta.hpp.

Member Function Documentation

generate_theta_renormalization_table()

static BasicTable bb::plookup::keccak_tables::Theta::generate_theta_renormalization_table ( BasicTableId  id, const size_t  table_index  )

inlinestatic

Generate plookup table that normalizes a TABLE_BITS-slice of a base-11 integer.

Parameters

id
table_index

Returns

BasicTable

Definition at line 171 of file keccak_theta.hpp.

get_column_values_for_next_row()

static std::array< uint64_t, 2 > bb::plookup::keccak_tables::Theta::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.

Parameters

counts

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

Returns

std::array<uint64_t, 2> the columns of the plookup table

Definition at line 142 of file keccak_theta.hpp.

get_scaled_bases()

static constexpr std::array< uint64_t, TABLE_BITS > bb::plookup::keccak_tables::Theta::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 122 of file keccak_theta.hpp.

get_theta_output_table()

static MultiTable bb::plookup::keccak_tables::Theta::get_theta_output_table ( const MultiTableId  id = KECCAK_THETA_OUTPUT )

inlinestatic

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

The THETA round 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, C where A = \sum_{i=0}^7 A_i * 11^8 B = \sum_{i=0}^7 B_i * 11^8 C_i = B_i / 11^8 (to get the most significant bit of B)

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

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

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

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

(where the -11^8 coefficient is 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 242 of file keccak_theta.hpp.

get_theta_renormalization_values()

static std::array< bb::fr, 2 > bb::plookup::keccak_tables::Theta::get_theta_renormalization_values ( const std::array< uint64_t, 2 >  key )

inlinestatic

Given a table input value, return the table output value.

Used by the Plookup code to precompute lookup tables and generate witness values

Parameters

key	(first element = table input. Second element is unused as this lookup does not have 2 keys per value)

Returns

std::array<bb::fr, 2> table output (normalized input and normalized input / 11^TABLE_BITS - 1)

Definition at line 101 of file keccak_theta.hpp.

Member Data Documentation

BASE

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

staticconstexpr

Definition at line 61 of file keccak_theta.hpp.

TABLE_BITS

constexpr size_t bb::plookup::keccak_tables::Theta::TABLE_BITS = 4

staticconstexpr

Definition at line 60 of file keccak_theta.hpp.

THETA_NORMALIZATION_TABLE

constexpr uint64_t bb::plookup::keccak_tables::Theta::THETA_NORMALIZATION_TABLE[11]

staticconstexpr

Initial value:

{
        0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,
    }

Definition at line 63 of file keccak_theta.hpp.

---

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

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