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 of the algorighm. (IOTA is 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