AztecProtocol / barretenberg

Apache License 2.0
129 stars 78 forks source link

Conventional lookups based on log-derivative #959

Open ledwards2225 opened 3 months ago

ledwards2225 commented 3 months ago

Tldr: Without structured trace? optional. With structured trace? Necessary

Committing to the lookup grand product is one of our highest commitment costs (equivalent to permutation grand product) so converting to log-deriv would be beneficial even without the structured trace optimization. With a structured trace, however, it becomes an unacceptably large cost because it is not constant over "dead" ranges, i.e. it is dense and nontrivial across the full size of the trace. This is in contrast to the permutation grand product which takes constant values in the dead regions and can thus be committed to relatively cheaply via the sorted MSM optimization.