- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
Generates plookup tables required for CHI round of Keccak hash function. More...
#include <keccak_chi.hpp>
Static Public Member Functions | |
| static std::array< bb::fr, 2 > | get_chi_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_chi_renormalization_table (BasicTableId id, const size_t table_index) |
| Generate the CHI plookup table. | |
| static MultiTable | get_chi_output_table (const MultiTableId id=KECCAK_CHI_OUTPUT) |
| Create the CHI MultiTable used by plookup to generate a sequence of lookups. | |
Static Public Attributes | |
| static constexpr uint64_t | CHI_NORMALIZATION_TABLE [5] |
| static constexpr uint64_t | BASE = 11 |
| static constexpr uint64_t | EFFECTIVE_BASE = 5 |
| static constexpr uint64_t | TABLE_BITS = 6 |
Generates plookup tables required for CHI round of Keccak hash function.
Keccak has 25 hash lanes, each represented as 64-bit integers. The CHI round performs the following operation on 3 hash lanes:
A ^ (~B & C)
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
2.A - B + C + Q
Where Q is the precomputed constant \sum_{i=0}^63 11^i
This can be represented via the 'truth table' for each base-11 quasi-bit:
| A | B | C | Algebraic Output |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 2 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 3 |
| 1 | 0 | 1 | 4 |
| 1 | 1 | 0 | 2 |
| 1 | 1 | 1 | 3 |
CHI round uses a plookup table that normalizes the algebraic output back into the binary output.
| Algebraic Output | Binary Output |
|---|---|
| 0 | 0 |
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | 0 |
In addition we also use the CHI lookup table to determine the value of the most significant (63rd) bit of the output
for all M in [0, ..., TABLE_BITS - 1] and K in [0, 1, 2, 3, 4], the column values of our lookup table are:
Column1 value = \sum_{i \in M} \sum_{j \in K} 11^i * j] Column2 value = \sum_{i \in M} \sum_{j \in K} 11^i * CHI_NORMALIZATION_TABLE[j]] Column3 value = Column2 / 11^8
Definition at line 64 of file keccak_chi.hpp.
|
inlinestatic |
Generate the CHI plookup table.
This table is used by Composer objects to generate plookup constraints
| id | a compile-time ID defined via plookup_tables.hpp |
| table_index | a circuit-specific ID for the table used by the circuit Composer |
Definition at line 172 of file keccak_chi.hpp.
|
inlinestatic |
Create the CHI MultiTable used by plookup to generate a sequence of lookups.
The CHI 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 | C_0 |
| \sum_{i=1}^7 A_i * 11^i | \sum_{i=1}^7 B_i * 11^i | C_1 |
| \sum_{i=2}^7 A_i * 11^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] - 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.
| id |
Definition at line 239 of file keccak_chi.hpp.
|
inlinestatic |
Given a table input value, return the table output value.
Used by the Plookup code to precompute lookup tables and generate witness values
| key | (first element = table input. Second element is unused as this lookup does not have 2 keys per value) |
Definition at line 89 of file keccak_chi.hpp.
|
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, 3, 4], 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 |
Definition at line 137 of file keccak_chi.hpp.
|
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.
Definition at line 113 of file keccak_chi.hpp.
|
staticconstexpr |
Definition at line 71 of file keccak_chi.hpp.
|
staticconstexpr |
Definition at line 67 of file keccak_chi.hpp.
|
staticconstexpr |
Definition at line 76 of file keccak_chi.hpp.
|
staticconstexpr |
Definition at line 79 of file keccak_chi.hpp.
1.9.8