Generate the plookup tables used for the RHO round of the Keccak hash algorithm. More...

#include <keccak_rho.hpp>

Static Public Member Functions
static std::array< bb::fr, 2 >	get_rho_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, 3 >	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_rho_renormalization_table (BasicTableId id, const size_t table_index)
	Generate plookup table that normalizes a TABLE_BITS-slice of a base-11 integer and extracts the msb.

static MultiTable	get_rho_output_table (const MultiTableId id=KECCAK_NORMALIZE_AND_ROTATE)
	Create the Rho 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 = 3

static constexpr size_t	MAXIMUM_MULTITABLE_BITS = 8

static constexpr std::array< size_t, 25 >	ROTATIONS

static constexpr uint64_t	RHO_NORMALIZATION_TABLE [3]

Detailed Description

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>
class bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >

Generate the plookup tables used for the RHO round of the Keccak hash algorithm.

Keccak has 25 hash lanes, each represented as 64-bit integers. The RHO round performs a left-rotation on each lane, by a fixed rotation value defined by the ROTATIONS arrray

We evaluate Keccak in-circuit using a base-11 sparse integer representation of each hash lane:

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

This allows us to replace binary operations (XOR, AND) with algebraic ones, combined with plookup tables. (see keccak_chi.hpp for comments on this).

At this point in the algorithm, each hash lane 'quasi-bit' is in the range [0, 1, 2].

The RHO lookup tables are used to perform the following:

Normalize each quasi-bit so that P_out = \sum_{j=0}^63 (b_i mod 2) * 11^i
Perform a left-rotation whose value is defined by a value in the ROTATIONS array
Extract the most significant bit of the non-rotated normalized output

The most significant bit component is required because we use this table to normalize XOR operations in the IOTA round and the sponge_absorb phase of the algorighm. (Both IOTA and sponge_absorb are followed by the THETA round which requires the msb of each hash lane)

Rotations are performed by splitting the input into 'left' and 'right' bit slices (left slice = bits that wrap around the 11^64 modulus of our base-11 integers) (right slice = bits that don't wrap)

Both slices are fed into a Rho plookup table. The outputs are stitched together to produce the rotated value.

We need multiple Rho tables in order to efficiently range-constrain our input slices.

The maximum number of bits we can accommodate in this lookup table is MAXIMUM_MULTITABLE_BITS (assume this is 8) For example take a left-rotation by 1 bit. The right-slice will be a 63-bit integer. 63 does not evenly divide 8. i.e. an 8-bit table cannot correctly range-constrain the input slice and we would need additional range constraints. We solve this problem by creating multiple Rho lookup tables each of different sizes (1 bit, 2 bits, ..., 8 bits).

We can stitch together a lookup table sequence that correctly range constrains the left/right slices for any of our 25 rotation values

Template Parameters

TABLE_BITS	The number of bits each lookup table can accommodate
LANE_INDEX	Required by get_rho_output_table to produce the correct MultiTable

Definition at line 60 of file keccak_rho.hpp.

Member Function Documentation

◆ generate_rho_renormalization_table()

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

static BasicTable bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::generate_rho_renormalization_table	(	BasicTableId	id,
		const size_t	table_index
	)

inlinestatic

Generate plookup table that normalizes a TABLE_BITS-slice of a base-11 integer and extracts the msb.

Parameters

id
table_index

Returns: BasicTable

Definition at line 173 of file keccak_rho.hpp.

◆ get_column_values_for_next_row()

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

static std::array< uint64_t, 3 > bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::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, 2], 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, 3> the columns of the plookup table

Definition at line 141 of file keccak_rho.hpp.

◆ get_rho_output_table()

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

static MultiTable bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::get_rho_output_table ( const MultiTableId id = KECCAK_NORMALIZE_AND_ROTATE )

inlinestatic

Create the Rho 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.

Representing the RHO lookup as a sequence of accumulating sums is tricky because of rotations.

For example, imagine our input is a 32-bit integer A represented as: A = A3.11^24 + A2.11^16 + A1.11^8 + A0, and our output is a 32-bit integer B = B3.11^24 + B2.11^16 + B1.11^8 + B0

In this example, we want to normalize A and left-rotate by 16 bits.

Our lookup gate wire values will look like the following:

Row	C0	C1	C2
0	A3.11^24 + A2.11^16 + A1.11^8 + A0	B1.11^8 + B0	A0.msb()
1	A3.11^16 + A2.11^8 + A1	B1	A1.msb()
2	A1311^8 + A2	B3.11^8 + B2	A2.msb()
3	A3	B3	A3.msb()

Finally, an addition gate is used to extract B = 11^32 * C1[0] + C1[2]

We use the above structure because the plookup protocol derives lookup entries by taking:

 Colunn1 = W1[i] + Q1 . W1[i + 1]
 Colunn2 = W2[i] + Q2 . W2[i + 1]

Where Q1, Q2 are constants encoded in selector polynomials. We do not have any spare selector polynomials to apply to W1[i] and W2[i] :(

i.e. we cannot represent the column C1 as a sequence of accumulating sums whilst performing a bit rotation! The part of A that wraps around past 11^64 must be represented separately vs the part that does not.

Parameters

id

Returns: MultiTable

Definition at line 237 of file keccak_rho.hpp.

◆ get_rho_renormalization_values()

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

static std::array< bb::fr, 2 > bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::get_rho_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 93 of file keccak_rho.hpp.

◆ get_scaled_bases()

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

static constexpr std::array< uint64_t, TABLE_BITS > bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::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 117 of file keccak_rho.hpp.

Member Data Documentation

◆ BASE

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

constexpr uint64_t bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::BASE = 11

staticconstexpr

Definition at line 63 of file keccak_rho.hpp.

◆ EFFECTIVE_BASE

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

constexpr uint64_t bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::EFFECTIVE_BASE = 3

staticconstexpr

Definition at line 68 of file keccak_rho.hpp.

◆ MAXIMUM_MULTITABLE_BITS

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

constexpr size_t bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::MAXIMUM_MULTITABLE_BITS = 8

staticconstexpr

Definition at line 72 of file keccak_rho.hpp.

◆ RHO_NORMALIZATION_TABLE

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

constexpr uint64_t bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::RHO_NORMALIZATION_TABLE[3]

staticconstexpr

Initial value:

Definition at line 79 of file keccak_rho.hpp.

◆ ROTATIONS

template<size_t TABLE_BITS = 0, size_t LANE_INDEX = 0>

constexpr std::array<size_t, 25> bb::plookup::keccak_tables::Rho< TABLE_BITS, LANE_INDEX >::ROTATIONS

staticconstexpr

Initial value:

= {
        0, 1, 62, 28, 27, 36, 44, 6, 55, 20, 3, 10, 43, 25, 39, 41, 45, 15, 21, 8, 18, 2, 61, 56, 14,
    }

Definition at line 75 of file keccak_rho.hpp.

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

src/barretenberg/stdlib_circuit_builders/plookup_tables/keccak/keccak_rho.hpp

Static Public Member Functions

Static Public Attributes

Detailed Description

Member Function Documentation

◆ generate_rho_renormalization_table()

◆ get_column_values_for_next_row()

◆ get_rho_output_table()

◆ get_rho_renormalization_values()

◆ get_scaled_bases()

Member Data Documentation

◆ BASE

◆ EFFECTIVE_BASE

◆ MAXIMUM_MULTITABLE_BITS

◆ RHO_NORMALIZATION_TABLE

◆ ROTATIONS