[Future Project] Replace permutation+plookup with log-derivative technique

Overview of this topic:

  1. log-derivative lookups have better properties than plookup
  2. 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)

86 Likes

Hello sir. All the HackMD links are access-restricted, unfortunately I do not have permission to read them.

55 Likes