plookup::keccak_tables::KeccakInput Class Reference

Generates plookup tables used convert 64-bit integers into a sparse representation used for Keccak hash algorithm. More...

#include <keccak_input.hpp>

Static Public Member Functions
static std::array< barretenberg::fr, 2 >	get_keccak_input_values (const std::array< uint64_t, 2 > key)
	Given a table input value, return the table output value.
static BasicTable	generate_keccak_input_table (BasicTableId id, const size_t table_index)
	Generate plookup table that maps a TABLE_BITS-slice of a base-2 integer into a base-11 representation.
static MultiTable	get_keccak_input_table (const MultiTableId id=KECCAK_FORMAT_INPUT)
	Create the KeccakInput MultiTable used by plookup to generate a sequence of lookups.

Static Public Attributes
static constexpr uint64_t	BASE = 11
static constexpr size_t	TABLE_BITS = 8

Detailed Description

Generates plookup tables used convert 64-bit integers into a sparse representation used for Keccak hash algorithm.

Keccak has 25 hash lanes, each represented as 64-bit integers.

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

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

KeccakInput defines the plookup table that maps binary integer slices into base-11 integer slices.

In addition, KeccakInput also is used to determine the value of the most significant (63rd) bit of the input (which is used by stdlib::keccak to more efficiently left-rotate by 1 bit)

Member Function Documentation

generate_keccak_input_table()

static BasicTable plookup::keccak_tables::KeccakInput::generate_keccak_input_table ( BasicTableId  id, const size_t  table_index  )

inlinestatic

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

Parameters

id
table_index

Returns

BasicTable

get_keccak_input_table()

static MultiTable plookup::keccak_tables::KeccakInput::get_keccak_input_table ( const MultiTableId  id = KECCAK_FORMAT_INPUT )

inlinestatic

Create the KeccakInput 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, C where A = \sum_{i=0}^7 A_i * 2^8 B = \sum_{i=0}^7 B_i * 11^8 C_i = B_i >> 7 (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 * 2^i	\sum_{i=0}^7 B_i * 11^i	C_0
\sum_{i=1}^7 A_i * 2^i	\sum_{i=1}^7 B_i * 11^i	C_1
\sum_{i=2}^7 A_i * 2^i	\sum_{i=2}^7 B_i * 11^i	C_2
...	...	...
A^7	B^7	C^7

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

 Colunn1 = W1[i] - 2^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

get_keccak_input_values()

static std::array< barretenberg::fr, 2 > plookup::keccak_tables::KeccakInput::get_keccak_input_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<barretenberg::fr, 2> table output

---

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

• src/barretenberg/proof_system/plookup_tables/keccak/keccak_input.hpp