Overview of this topic:
- log-derivative lookups have better properties than plookup
- if we make both permutation + lookup relations use log derivatives, we can replace our 2 “grand product” polynomials with a single inverse polynomial
See this HackMD for details on how to do lookups via log-derivatives
See this HackMD for details on how to do permutations via log-derivatives
An overview of the vectors/polynomials required for lookups
|grand product vector||num_reads + table_size||-|
|sorted list vector||num_reads + table_size||-|
An overview of the vectors/polynomials required for log derivatives
|inverse vector||max(num_reads, table size)||-|
|counts vector||table size||entries describe # of times a given table entry is read from. values are small|
The log-derivative vectors are smaller
max(num_reads, table_size) vs
(num_reads + table_size), which practically enables larger tables.
The log-derivative vectors are faster to commit to due to the “counts” vector element values being small.
The log-derivative relation contains fractional terms (e.g. (
1 / a_i)). To convert into polynomial algebra the Prover must commit to these inverses.
To reduce the number of inverse commitments, the Prover can commit to the product of all inverses required for a given row.
This increases the degree of the resulting permutation/lookup relation, but is likely an acceptable trade-off vs having multiple inverse commitments.
We can reduce the degree of the combined permutation/lookup relation by modifying the permutation relation to use more precomputed polynomials (see https://hackmd.io/@aztec-network/B1HHr26Pn?type=view for details)