📺 Today’s recommended deep-dive video: https://www.youtube.com/watch?v=qv_5dF2_C4g

Scaling ZKVMs with Logarithmic Derivatives: An Introduction to LogUp

Traditional lookup arguments often struggle with the sheer volume of columns required by modern zero-knowledge virtual machines. By shifting the mathematical foundation from products to sums using logarithmic derivatives, we can drastically reduce the overhead of range checks and hash functions.

Core Question: How can logarithmic derivatives transform multiplicative multiset checks into additive ones to optimize batch column lookups?

Highlights

• Transitioning from product-based to sum-based arguments simplifies the proof of multiset equality and inclusion.
• LogUp specifically addresses the “batch column lookup” problem where dozens or hundreds of columns require identical range checks.
• The protocol eliminates the need for complex binary encoding of multiplicities, which was a significant bottleneck in older protocols like Plookup.
• Practical implementations in Plonky2 show savings of approximately 50 extra columns in wide-trace ZKVM environments.

⏱️ Reading time: approx. 8 minutes · Saves you about 24 minutes vs. watching.

Want to take notes while watching? Click the image below and let AI Notebook capture the key points for you 👇

The Evolution of Lookup Arguments

From Permutations to Membership

Most zero-knowledge proofs rely on multiset checks to ensure that two sequences contain the same elements, regardless of their specific order.

In a standard permutation argument, we construct virtual polynomials that encode the sequence elements as roots; if the sequences are permutations of one another, the polynomials must be identical. To verify this efficiently without having the prover calculate high-degree polynomials, we challenge them at a random point and reduce the problem to an identity of product bases. This works perfectly when the two sets are the same size, but the problem becomes more complex when dealing with lookups.

Lookups are slightly more subtle because the witness sequence and the table sequence are rarely the same length, necessitating the use of multiplicities. We must prove that every element in the witness belongs to the table, even if it appears hundreds of times or not at all.

💡 Digging Deeper

Q: Why are virtual polynomials used instead of standard polynomials?
A: Virtual polynomials allow the prover to avoid the high cost of computing the full polynomial expansion, relying instead on random challenges to prove identity.

Q: What is a “multiset check” in this context?
A: It is a proof that two sets contain the same elements with the same number of occurrences, even if the order of those elements differs.

Q: How does Plookup handle multiplicities?
A: It typically uses a binary representation of multiplicities, which involves committing to multiple bit-columns and results in a complex, multi-step proof process.

The LogUp Breakthrough

The Power of the Logarithmic Derivative

The core innovation of LogUp involves using the logarithmic derivative—a concept from basic calculus—to convert complex products into simple additive sums. This formal derivative, defined as $P'(x)/P(x)$, essentially transforms the zeros of a polynomial into simple poles that can be summed linearly.

This mathematical shift is crucial because addition is significantly easier to handle than multiplication within an interactive oracle proof (IOP) framework.

When we consider the derivative of a product, the result is the sum of the derivatives of its factors divided by the factors themselves. In the context of lookups, this means we can prove membership by finding a sequence of multiplicities where the sum of poles in the witness matches the sum of poles in the table. This bypasses the need for the complex binary encoding of multiplicities required by older protocols. Because we are dealing with sums, the degree of the polynomial does not increase when we aggregate multiple columns, which is a major efficiency gain.

💡 Digging Deeper

Q: How does the “rule of the chain” apply here?
A: In formal calculus, the derivative of the log of a function is 1 over the function times the internal derivative; LogUp applies this discrete version to polynomial identities.

Q: What is the primary benefit of “additive multiplicity”?
A: It allows multiple witness columns to be combined into a single sum-check without the multiplicative degree blow-up that usually complicates batching.

Q: Does this require specific commitment schemes like KZG?
A: While it can leverage KZG, the protocol is generic and can be used with various polynomial commitment schemes, including those used in Plonky2.

Practical Performance and Implementation

Batching and Column Reduction

For modern ZKVMs like the Zero system or systems using hash chips like Tip5, the prover often faces 70 to 200 columns that require the same range checks. In these “batch column lookup” scenarios, traditional methods like Plookup become extremely expensive, as they require maintaining high-degree polynomials or numerous auxiliary columns to track state across the joint union of all columns.

LogUp allows these many columns to “fall together” into a single sum-check without increasing the overall degree of the polynomial.

Empirical results suggest that LogUp can save approximately 50 extra columns of trace compared to previous state-of-the-art methods in wide-trace environments. This efficiency has led to its integration into the Plonky2 codebase, providing a tangible performance boost for developers building scalable ZK applications. By reducing the number of committed columns, we directly reduce the prover’s computational burden and the resulting proof size.

💡 Digging Deeper

Q: Is LogUp restricted to univariate provers?
A: No, while the Plonky2 implementation is univariate, the underlying math was developed with multivariate settings in mind and can be adapted to either.

Q: What is the trade-off between degree and column count?
A: Provers can choose to increase the degree of the constraints to further reduce the number of auxiliary columns, or vice versa, depending on the specific hardware constraints.

Q: How does the “sum-check” aspect work?
A: Instead of a running product, the protocol uses a running sum of rational functions, which are then cleared of denominators to be proven as standard polynomial identities.

Key Takeaways

LogUp represents a significant shift in how we approach lookups in zero-knowledge proofs. By moving away from the “geometric” or product-based approach of Plookup and embracing the additive properties of logarithmic derivatives, the protocol achieves much better scaling for wide-trace ZKVMs. This is particularly relevant for operations like 16-bit range checks or lookup-based hashes, where the same table is referenced across hundreds of witness columns.

The reduction in auxiliary columns—roughly 50 columns in common ZKVM configurations—directly translates to faster prover times and less memory consumption. As these protocols move from theoretical papers into production-ready codebases like Plonky2, they enable a new generation of more efficient and scalable decentralized applications.

Q&A

Q1: What inspired the name “LogUp”?
A: It is a shorthand for “Logarithmic Derivative Lookup,” created because the technical name was too long for frequent discussion.

Q2: How does LogUp handle values that appear in the witness but not the table?
A: The protocol ensures that if a value has a non-zero multiplicity in the witness, it must have a corresponding entry in the table; otherwise, the sum-check identity will fail.

Q3: Is the multiplicity sequence difficult for the prover to calculate?
A: Not particularly. The prover simply counts how many times each table entry appears across all witness columns, which is a linear-time operation.

Q4: Does LogUp improve proof verification time or just prover time?
A: It primarily improves prover time by reducing the commitment overhead, though the reduction in columns can also lead to smaller proofs and slightly faster verification.

Q5: Can LogUp be used for vector lookups (multiple columns at once)?
A: Yes, the protocol is easily generalized to “batch column lookups” or vector lookups by merging the columns into a joint representation before applying the logarithmic derivative.

Q6: How does LogUp compare to newer techniques like CQ (Cached Quotients)?
A: While LogUp focuses on reducing columns in the standard trace, techniques like CQ leverage the linearity of KZG for “huge” tables. They are complementary rather than strictly competitive.

Q7: Is the Plonky2 implementation of LogUp public?
A: Yes, the implementation by William at Polygon/Zero is available in the public Plonky2 repository.