barretenberg icon indicating copy to clipboard operation
barretenberg copied to clipboard

Conventional lookups based on log-derivative

Open ledwards2225 opened this issue 10 months ago • 0 comments

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.

ledwards2225 avatar Apr 22 '24 19:04 ledwards2225