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
Log Derivatives
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
| vector | size | comments |
|---|---|---|
| grand product vector | num_reads + table_size | - |
| sorted list vector | num_reads + table_size | - |
An overview of the vectors/polynomials required for log derivatives
| vector | size | comments |
|---|---|---|
| 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.
Combining inverse polynomials
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)