Paper 2022/1530

Multivariate lookups based on logarithmic derivatives

Ulrich Haböck, Orbis Labs, Polygon Labs

Logarithmic derivatives translate products of linear factors into sums of their reciprocals, turning zeroes into simple poles of same multiplicity. Based on this simple fact, we construct an interactive oracle proof for multi-column lookups over the boolean hypercube, which makes use of a single multiplicity function instead of working with a rearranged union of table and witnesses. For single-column lookups the performance is comparable to the well-known Plookup strategy used by Hyperplonk+. However, the real power of our argument unfolds in the case of batch lookups when multiple columns are subject to a single-table lookup: While the number of field operations is comparable to the Hyperplonk+ lookup (extended to multiple columns), the oracles provided by our prover are much less expensive. For example, for columns of length 2^12, paper-pencil operation counts indicate that the logarithmic derivative lookup is between 1.5 and 4 times faster, depending on the number of columns.

Note: Clarified the trade-off between algebraic degree and the number of commitments, previously expressed by two protocol variants. Discussion of Polygon Miden’s bounded multiplicity encoding.

Available format(s)
Cryptographic protocols
Publication info
Lookup argumentsInteractive Oracle ProofsSNARKs
Contact author(s)
uhaboeck @ polygon technology
2023-03-31: last of 2 revisions
2022-11-04: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ulrich Haböck},
      title = {Multivariate lookups based on logarithmic derivatives},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1530},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.