- Generated by
1.9.8
|
Barretenberg
The ZK-SNARK library at the core of Aztec
|
Namespaces | |
| namespace | aes128_tables |
| namespace | blake2s_tables |
| namespace | dummy_tables |
| namespace | ecc_generator_tables |
| namespace | fixed_base |
| namespace | keccak_tables |
| namespace | sha256_tables |
| namespace | sparse_tables |
| namespace | uint_tables |
Classes | |
| struct | BasicTable |
| A basic table from which we can perform lookups (for example, an xor table) More... | |
| struct | FixedBaseParams |
| Parameters definitions for our fixed-base-scalar-multiplication lookup tables. More... | |
| struct | LookupHashTable |
| A map from 'entry' to 'index' where entry is a row in a BasicTable and index is the row at which that entry exists in the table. More... | |
| struct | MultiTable |
| Container for managing multiple BasicTables plus the data needed to combine basic table outputs (e.g. limbs) into accumulators. Does not store actual raw table data. More... | |
| class | ReadData |
| Container type for lookup table reads. More... | |
Functions | |
| const MultiTable & | get_multitable (const MultiTableId id) |
| Return the multitable with the provided ID; construct all MultiTables if not constructed already. | |
| ReadData< bb::fr > | get_lookup_accumulators (const MultiTableId id, const fr &key_a, const fr &key_b, const bool is_2_to_1_lookup) |
| Given a table ID and the key(s) for a key-value lookup, return the lookup accumulators. | |
| BasicTable | create_basic_table (const BasicTableId id, const size_t index) |
| BasicTable bb::plookup::create_basic_table | ( | const BasicTableId | id, |
| const size_t | index | ||
| ) |
Definition at line 258 of file plookup_tables.cpp.
| ReadData< bb::fr > bb::plookup::get_lookup_accumulators | ( | const MultiTableId | id, |
| const fr & | key_a, | ||
| const fr & | key_b, | ||
| const bool | is_2_to_1_lookup | ||
| ) |
Given a table ID and the key(s) for a key-value lookup, return the lookup accumulators.
In general the number of bits in original key/value is greater than what can be efficiently supported in lookup tables. For this reason we actually perform lookups on the corresponding limbs. However, since we're interested in the original values and not the limbs, its convenient to structure the witnesses of lookup gates to store the former. This way we don't have to waste gates reaccumulating the limbs to compute the actual value of interest. The way to do this is to populate the wires with 'accumulator' values such that the first gate in the series contains the full accumulated values, and successive gates contain prior stages of the accumulator such that wire_i - r*wire_{i-1} = v_i, where r = num limb bits and v_i is a limb that explicitly appears in one of the lookup tables. See the detailed comment block below for more explanation.
| id | |
| key_a | |
| key_b | |
| is_2_to_1_lookup |
A multi-table consists of multiple basic tables (say L = 6).
[ ] [ ] [ ]| |[ ][ ]| |[ ]
M ≡ | B1 || B2 || B3 || B4 || B5 || B6 | [ ]| |[ ][ ]| |[ ] [ ] [ ] |̐ |̐ |̐ |̐ |̐ |̐ s1 s2 s3 s4 s5 s6
Note that different basic tables can be of different sizes. Every lookup query generates L output slices (one for each basic table, here, s1, s2, ..., s6). In other words, every lookup query adds L lookup gates to the program. For example, to look up the XOR of 32-bit inputs, we actually perform 6 individual lookups on the 6-bit XOR basic table. Let the input slices/keys be (a1, b1), (a2, b2), ..., (a6, b6). The lookup gate structure is as follows:
+—+--------------------------------—+-------------------------------—+--------------------------------—+ | s | key_a | key_b | output | |—+--------------------------------—+-------------------------------—+--------------------------------—| | 6 | a6 + p.a5 + p^2.a4 + ... + p^5.a1 | b6 + q.b5 + qq.b4 + ... + q^5.b1 | s6 + r.s5 + r^2.s4 + ... + r^5.s1 | | 5 | a5 + p.a4 + ...... + p^4.a1 | b5 + q.b4 + ...... + q^4.b1 | s5 + r.s4 + ...... + r^4.s1 | | 4 | a4 + p.a3 + ... + p^3.a1 | b4 + q.b3 + ... + q^3.b1 | s4 + r.s3 + ... + r^3.s1 | | 3 | a3 + p.a2 + p^2.a1 | b3 + q.b2 + q^2.b1 | s3 + r.s2 + r^2.s1 | | 2 | a2 + p.a1 | b2 + q.b1 | s2 + r.a1 | | 1 | a1 | b1 | s1 | +—+--------------------------------—+-------------------------------—+--------------------------------—+
Note that we compute the accumulating sums of the slices so as to avoid using additonal gates for the purpose of reconstructing the original inputs/outputs. I.e. the output value at the 0th index in the above table is the actual value we were interested in computing in the first place. Importantly, the structure of the remaining rows is such that row_i - r*row_{i+1} produces an entry {a_j, b_j, s_j} that exactly corresponds to an entry in a BasicTable. This is what gives rise to the wire_i - scalar*wire_i_shift structure in the lookup relation. Here, (p, q, r) are referred to as column coefficients/step sizes. In the next few lines, we compute these accumulating sums from raw column values (a1, ..., a6), (b1, ..., b6), (s1, ..., s6) and column coefficients (p, q, r).
For more details: see https://app.gitbook.com/o/-LgCgJ8TCO7eGlBr34fj/s/-MEwtqp3H6YhHUTQ_pVJ/plookup-gates-for-ultraplonk/lookup-table-structures
Definition at line 173 of file plookup_tables.cpp.
| const MultiTable & bb::plookup::get_multitable | ( | const MultiTableId | id | ) |
Return the multitable with the provided ID; construct all MultiTables if not constructed already.
The multitables are relatively light objects (they do not themselves store raw table data) so the first time we use one of them we simply construct all of them (regardless of which of them will actually be used) and store in MULTI_TABLES array.
| id | The index of a MultiTable in the MULTI_TABLES array |
Definition at line 147 of file plookup_tables.cpp.
1.9.8