|
barretenberg
|
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. | |
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.
|
inlinestatic |
Generate plookup table that maps a TABLE_BITS-slice of a base-11 integer into a base-2 integer.
| id | |
| table_index |
|
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!)
| counts | The current row value represented as an array of quasi-bits |
|
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.
| id |
|
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.
1.9.6