The ZK Chronicles: Lookup Arguments

After our little detour on some interesting domains, it's time to take it back into proving system terrain.

Under our belts, we now have three pivotal protocols, and we've ended our three-part progression on setups: trusted per-circuit with Groth16, trusted universal with PLONK, and we topped it off with the transparent setup of STARKs.

In addition, we've now covered three different arithmetization strategies. Which, if you recall, are different mechanisms to turn either arithmetic circuits or the state transition functions of STARKs into a set of polynomial constraints that we can flesh out into a proving system. And so we did, using pretty much all our accrued knowledge, and got some really interesting results!

These arithmetizations are at the very core of modern ZK, and trying to get the most out of them in order to build better mechanisms is an idea very much worth pursuing. And in particular, there's one really clever strategy we still need to explore that adds lots of expressivity into the mix, in a way that may seem rather odd: to search for values in tables.

What the fridge?

I know it sounds weird. But let me reassure you: this ability opens the door for some exotic options, and has quietly become one of the most important primitives in any ZK toolkit.

Time to talk about lookup arguments then!

The Problem with Arithmetic

There's no shadow of a doubt that the three arithmetizations we've seen up until now (R1CS, Plonkish, and AIR) are very powerful. Circuits can represent just about any computation, and mapping those onto a set of polynomial constraints is quite natural because both models speak the same arithmetic language. In a way, it's as if the conversion works for free, meaning both representations have roughly the same complexity.

But the biggest strength of arithmetic circuits is also their biggest downside: they are great at expressing arithmetic, but kinda suck at expressing everything else. The moment we step outside this world of arithmetic, things get painful pretty fast.

Let me try to convince you with a basic example: say we want to prove that a value $x$ is a valid byte. That is, that its value is between $0$ and $255$. Sounds easy, right?

It's not.

To represent such a range constraint, you'd typically do a bit decomposition: introduce eight witness bits $b_0, \ldots, b_7$, and assert that each one of them is either $0$ or $1$:

$$b_i \cdot (1 {-} b_i) = 0 \quad \forall i = 0...7$$

You'd also have to assert that they add up to $x$:

$$\sum_{i=0}^{7} 2^i \cdot b_i = x$$

That's a total of nine constraints for a single byte check.

And you can imagine that this only gets worse if you try to operate on those bytes. Want to compute an $\textrm{XOR}$? Sure! All you need is to do a bit decomposition of both inputs, perform $\textrm{XOR}$ bit by bit, and then reconstruct the output - that's around thirty constraints for something that feels like it should be a single operation.

Now extrapolate this to every single byte operation in a standard hash function like SHA256. Or for every instruction in a virtual machine. And oh boy, the number of constraints just explodes, and quickly becomes unmanageable.

Again, this all happens because the arithmetic circuit model is built for polynomial operations, and it handles those very efficiently. But for everything else, using a circuit can feel like fighting against the very nature of the things we're trying to represent.

There has to be a better way.

So, what can we do about this?

Lookin' it Up

Well, not everything that we prove about some secret witness has to be an arithmetic relationship! We've seen some other kinds of arguments in the form of inner product arguments, so perhaps we can come up with something useful for our current situation.

Here's an idea then. Suppose we have a public table of values, and let's denote it $T$. We can try something pretty straightforward: to prove that some secret value $x$ appears in $T$.

At first, this might sound weird, or maybe even a little pointless, given the crazy stuff we've been through. However, this happens to be just perfect for our previous byte example: all we have to do is define $T = \{0, 1, 2, \ldots, 255\}$. With that, instead of nine constraints and eight witness bits, all you have to do is to prove a single claim: that $x$ is listed in $T$!

Extending this to our second example is a bit trickier, but it can also be done: for byte-wise $\textrm{XOR}$, you can define $T$ to be all valid triples $(a, b, a \oplus b)$ for $a, b \in \{0, \ldots, 255\}$. It's a much bigger table ($256^2$ rows total), but if we manage to prove some tuple $(a, b, c)$ appears in $T$, we're done in a single step!

We can even go ahead and generalize this idea: for any computation, just precompute a table of valid inputs and outputs, and replace expensive arithmetic constraints with a single claim about table membership.

And so, to be precise, we have to define a couple things. We'll need:

• Obviously, a table $T = (t_1, t_2, \ldots, t_n)$, which is a public list of tuples.
• And a lookup vector $f = (f_1, f_2, \ldots, f_m)$, which is the prover's witness values, each of which must appear somewhere in $T$.

With just those definitions, our problem can be framed very cleanly: the prover wants to convince the verifier that $f$ is a subvector of $T$ - which, in plain English, means that every element of $f$ appears in $T$.

Repetitions are allowed here: the same table entry can be looked up many times!

Only that... we still don't really know how to do that!

How do we actually prove this claim? How do you convince a verifier through a cryptographic argument, that some witness value appears in a public table?

Well, that's exactly the job of a lookup argument!

A Simple Argument

Let's start small. Imagine our table $T$ only has one column, so that $T = (t_1, ..., t_n)$ is just a vector of field elements. Turns out there's a nice way to encode membership of that table into a polynomial:

$$Z_T(X) = \prod_{t \in T}(X {-} t)$$

By construction, each of the elements in the table is a root of this polynomial $Z_T(X)$. So if $f_i$ belongs to the table, then that means it's also gonna be a root of $Z_T(X)$, and we can use a familiar trick: $(X {-} f_i)$ should perfectly divide $Z_T(X)$:

$$Z_T(X) = Q(X) \cdot (X {-} f_i)$$

Thus, imagine a situation where the prover commits to $Q(X)$, and the verifier checks at a random challenge $\alpha$ (of course, leveraging oracle access to $Q(X)$):

$$Z_T(\alpha) \stackrel{?}{=} (\alpha {-} f_i) \cdot Q(\alpha)$$

No need to commit to $Z_T(X)$, since the table is public! The verifier can construct that polynomial on their own.

It's pretty much the same flavor of argument we've seen for other QAP-style relations. Clean, familiar, and... it doesn't really scale.

Yeah. And the problem is actually pretty simple: if we had to prove membership of many elements (a whole vector of lookup values $f$), but we had to do it one at a time, that would require many checks of these polynomial identities!

We'd get that pesky linear scaling we've been trying to avoid all along.

You might be tempted to ask "hey, but can't we sort of batch those checks?". And you'd be partially right. We could in theory take all the $f_i$ lookup values, and if all of them truly belong in $T$, then we could say that $Z_T(X)$ is perfectly divisible by a vanishing polynomial of the form:

$$V(X) = \prod_{i=1}^{m} (X {-} f_i)$$

Only that we immediately hit another brick wall: what about repetitions? Because of how we constructed $Z_T(X)$, we can only divide by each term $(X {-} f_i)$ once, so we really don't have a way to prove that some value $f_i$ appears more than once in the table $T$.

So yeah, it's not a trivial problem to solve!

And by the way, it only gets harder when $T$ has more than one column.

Essentially, we need an argument that somehow batches all $m$ membership claims into a single check, without choking on repeated lookups. But where do we even begin to look for ideas? What kind of sorcery do we have to conjure to get this to work?

Well, sometimes the solutions to the hardest problems hide in simple ideas, as is the case for the next argument.

Plookup

The first widely adopted lookup argument was Plookup, introduced by Gabizon and Williamson in their 2020 paper. It was designed to integrate directly with PLONK's existing permutation argument infrastructure - which, as we'll soon learn, is no coincidence.

Plus, I've already hinted at this before!

Plookup tackles this table membership problem not with heavy algebraic machinery, but by doing something even little kids can do: sorting things!

But why would sorting matter at all? Let's try to make some sense out of this with a simple example.

Imagine we grab a table $T$ with only $5$ elements, and we sort it from lowest to highest (in value), ending up with a list $(T_1, T_2, T_3, T_4, T_5)$. Now, say we want to check whether $f_1$ belongs in this table. Because the list is already sorted, we can try to slot this value into the ordered list. Say the number lands between $T_2$ and $T_3$, like so:

Click to zoom

We can immediately say something about this insertion. You see, if $f_1$ does belong in the table, then it must equal either $T_2$ or $T_3$. Any other $f_1$ value that happens to sit between $T_2$ and $T_3$ clearly does not belong in the table at all!

Sure, it's not a Sherlock-level observation, but it's just enough for us to build an argument around it, for a simple reason. Note that we can insert as many lookups as we want, and all of them should behave exactly the same: if they belong to the table, they will cause a repetition in the sequence.

Therefore, we can see that a nice pattern emerges when we start looking at sequential pairs of elements. If we look at them from left to right, then a valid lookup (one where all the inserted elements actually belong to the table) will generate only two types of pairs:

• A repeated value of the form $(T_i, T_i)$, which means we've hit a lookup match,
• Or a jump into the next valid table element, so $(T_i, T_{i+1})$.

Anything else would immediately signal that at least one lookup value does not belong in the original table.

That's it! We just look at pairs of elements in this set, which Plookup calls a sorted union:

$$s = \text{sort}(f \cup T)$$

By the way, notice that we're working with a single-column table for now. We'll worry about the multi-column case by the end of this section.

Now that's promising! All we need now is a way to turn this newfound insight into an argument.

The Polynomial Identity

To check the consecutive-pair condition, Plookup uses the same tool we used in PLONK's permutation argument: a running product!

As a short refresher, the idea back then was to prove that a multi-set $P$ and a permutation of it $\sigma(P)$ were in fact the same multi-set. So we ran through all such elements in one fell swoop, through a process of accumulation.

The idea is that we can start accumulating checks for each step, in such a way that if everything behaves as expected, everything will cancel out in the end. With one little caveat though: running products work for single field elements, not pairs. But we'll deal with that in a minute!

To apply this running product argument, we need to have two multi-sets to compare.

Remember, multi-sets are just sets where repetition matters.

But in this case, what would those multi-sets be? Let's see:

• The sorted union gives us a set of $n + m {-} 1$ consecutive pairs $(s_i, s_{i+1})$. That one's easy.
• Then, we have the original table, and all our lookup values. The table can be organized into $n {-} 1$ consecutive pairs $(t_i, t_{i+1})$, so that's also pretty straightforward.

What can we do about the $m$ lookup values though? Those seem out of place...

Until we remember we expect all the $f_i$ values to belong to the table, meaning they will generate steps where values repeat! That's the natural way to think about them: as repeating pairs $(f_i, f_i)$!

They are sometimes called degenerate pairs, but really, they are just describing what should happen in the sorted union: a repetition step!

Cool! After adding those, we now have our sets of pairs to compare.

We can now turn our attention to the problem I mentioned earlier: turning these pairs into single field elements. All we need is a way to incorporate both coordinates in a way that distinguishes the order (so that we have a way to distinguish $(a,b)$ from $(b,a)$). So how about we try this:

$$a + \beta \cdot b$$

Folding style!

Nothing too fancy, yet that expression right there acts like a fingerprint for the pair: the $\beta$ weight on $b$ means swapping $a$ and $b$ results in a different value. We also need to throw in an extra random offset $\gamma$ (to avoid edge cases where values happen to be zero), which gives us our full encoding:

$$\gamma + a + \beta \cdot b$$

This is exactly the same fingerprinting idea used in PLONK's permutation argument! Importantly, these random values are challenges sent by the verifier, and they play their usual role of making a cheating prover's life extremely hard.

When we apply this to the repetition pairs $(f_i, f_i)$:

$$\gamma + f_i + \beta \cdot f_i = \gamma + f_i(1 + \beta)$$

Here, the original paper uses a little trick to enable a nice factorization that will keep the final identity clean. The above expression is slightly modified to:

$$\gamma(1+\beta) + f_i + \beta \cdot f_i = (1+\beta)(\gamma + f_i)$$

That helps because the $(1+\beta)$ factor cleanly separates out. It's a key algebraic trick: repeated values produce a nice factored form.

And now that we have our fingerprinting recipe, all that remains is to apply it to both sets of pairs - the table and lookup values on one side, and the sorted union on the other. Collecting all those together will finally give us the polynomial identity we're looking for:

$$(1+\beta)^m \cdot \prod_{i=1}^{m} (\gamma + f_i) \cdot \prod_{i=1}^{n-1} \left(\gamma(1+\beta) + t_i + \beta \cdot t_{i+1} \right) = \prod_{i=1}^{n+m-1} \left(\gamma(1+\beta) + s_i + \beta \cdot s_{i+1} \right)$$

You might want to take a moment to digest that expression. I know it looks scary, but it's really not that complicated. We're just comparing fingerprinted pairs multiplied together: the sorted union on one side (right), and the table and lookup values on the other (left)!

Remember that, at a high level, we're just comparing two multi-sets, only that we do it through their encoded pairs.

One nice way to assimilate why this works is to imagine what happens when a prover tries to sneak some lookup value that does not belong in the table ($f_i \notin T$). In that case, the sorted union will contain one invalid step. How is this captured by the identity? In that the left-hand side will not contain such an invalid step (neither the $f_i$ nor $(t_i, t_{i+1})$ terms will match), and the two products will most likely (with really high probability) be different!

Amazing stuff indeed.

The last piece of the puzzle is the same trick used for the permutation argument: the prover doesn't just compute this identity, but rather encodes it into polynomials, and proves it using the PLONK framework.

You might want to re-check how the $Z(X)$ polynomial was constructed!

In short: the sorted vector $s$ is committed to, the identity is baked into a polynomial constraint, and a single divisibility constraint is checked at a random point! And that certifies that all $m$ lookup queries are satisfied, all in a single extra argument that's attached to the usual PLONK workflow.

Quite elegant in the end, isn't it?

Plookup Limitations

While useful in practice, this technique is far from perfect, and there are two particular situations where it begins to show its seams.

The first is multi-column tables. If you recall, we assumed $T$ to be a list of field elements, which corresponds to a single-column table. Real tables tend to have more than one column though.

Just look at our XOR example from earlier, where each row has three elements of the form $(a, b, a \oplus b)$.

Plookup can't sort tuples directly, so we have to compress each row into a single field element first. The standard trick is a random linear combination using another verifier challenge $\alpha$:

$$\hat{t}_i = t_i^{(1)} + \alpha \cdot t_i^{(2)} + \alpha^2 \cdot t_i^{(3)}$$

Then you apply Plookup on the compressed single-column table $\hat{T}$. It works, but the sorted union now depends on $\alpha$, meaning the prover can't sort until after the challenge arrives. And the more columns you have, the more inconvenient this gets.

The second problem we have to account for is when we have multiple tables. If a circuit uses several distinct lookup tables (say, one for range checks and another for bitwise XOR), there's no natural way to combine them. Each table needs its own sorted union, its own commitment, and its own product identity. This is fine for a few tables, but the costs do stack up when we have several tables to deal with.

Neither of these is a strong dealbreaker, but they do add friction. Plus, getting here was a lot of work, and now we're faced with these limitations.

If only there were a simpler way...

LogUp

Maybe if we take a step back, we'll find some answers.

If you recall, the whole reason we went through the running product was because when we tried the usual trick of building QAP-style polynomial identities, everything fell apart because repeated lookups were a problem.

Remember? We tried building the polynomial:

$$Z_T(X) = \prod_{t \in T} (X {-} t)$$

And said that for each value $f_i$ that matches a table entry $t_i$, we could only divide $Z_T(X)$ by $(X {-} f_i)$ once. That thwarted our efforts back then, but we can also take it as a hint: maybe working with roots is not the way!

Okay, that's an interesting thought! But if roots are the wrong tool, what's the alternative?

We know full well that we need to deal with repetitions of lookups, or what's usually called the multiplicity of a lookup value. So instead of trying to divide a polynomial, how about we try to simply do the counting?

How? Well, consider the term $1/(X {-} f_i)$. Imagine this term works as sort of a vote for the value $f_i$. When a lookup value should appear more than once, each appearance adds a vote, and when we sum over all the lookup values, values that appear multiple times naturally accumulate more weight. And if we group by table entry instead, each $t_v$ should collect exactly $m_v$ votes - its multiplicity!

$$\sum_{i=1}^{m} \frac{1}{X {-} f_i} = \sum_{v=1}^{n} \frac{m_v}{X {-} t_v}$$

That's the shift, really: instead of working with products and roots, we just use sums and reciprocals!

As it turns out, this is actually the basic idea of an alternative to Plookup proposed a couple years later by Haböck in their paper on multivariate lookups, now commonly known as LogUp.

One important thing to note here is that the identity from before does not use polynomials. Instead, it's a rational function identity, and as such, it will have some new properties that we must take into account.

Rational functions behave somewhat differently than usual. We can't seem to evaluate the function at any $X = t_v$, because we'd be dividing by $0$. This type of point is called a pole, and it's pretty much the opposite of what a root is: it forces us to avoid evaluating at those special points, because the quotient will not be defined.

Polynomials don't really have poles, and that's the reason we haven't had to talk about them until now!

There's also another quick way to reason about the identity from before: if even one $f_i \notin T$, the left side has an extra pole at $f_i$. The right side does not have that, and so the identity fails.

And so, by allowing ourselves to explore this new domain of rational functions, we're able to encode the multiplicity, which lets us check the whole thing through a single clean expression!

The mathematical machinery behind LogUp actually comes from logarithmic derivatives, and a classical identity that turns products of linear factors into sums of their reciprocals. It's not magic, but there's no need for us to dwell on those details.

I guess one thing we might have questions about is whether working with these rational functions is as easy as it was with polynomials. After all, we had the FFT to make life easier, and that's no longer the case with rational functions.

Good thing we don't plan on evaluating rational functions at all!

You see, we can cross-multiply to clear the denominators, which yields a familiar polynomial identity. And we know how to work with those: just evaluate both sides at a random challenge point $\alpha$, and let Schwartz-Zippel do its usual magic.

There's just one extra detail to take into account: the multiplicity vector $\{m_v\}$ is also part of the prover's witness, since the $f_i$ values are private. So the prover commits to it alongside the lookup values, and the verifier can later independently verify that the total lookups match their expected number:

$$\sum_v m_v = m$$

As if all that wasn't already amazing, LogUp hits us with one extra ace up its sleeve: multiple tables compose naturally! Instead of managing separate sorted unions, sorted vectors, and product identities per table, you just add more fractional sums to the same identity:

$$\sum_i \frac{1}{X {-} f_i^{(1)}} + \sum_i \frac{1}{X {-} f_i^{(2)}} = \sum_v \frac{m_v^{(1)}}{X {-} t_v^{(1)}} + \sum_v \frac{m_v^{(2)}}{X {-} t_v^{(2)}}$$

You just add up "more votes", so to speak!

And that is the real payoff of stepping outside polynomial land: rational functions speak the language of counting in a way products simply can't.

This gives us a much cleaner foundation, and unsurprisingly, it's the main reason LogUp has largely replaced Plookup in modern proof systems, with systems like Plonky3 being built around it.

With all that praise, it wouldn't be too crazy to think that this is the end of the story for lookup arguments.

However, there's one thing we've been quietly assuming throughout: that the tables $T$ are small enough that working with their explicit representations is feasible. This is true for byte-range checks, or 16-bit XOR tables.

But let's push it a bit further: what about CPU-scale operations? In that case, we might have tables that need to encode every valid 64-bit operation, so the sizes easily explode into the range of $2^{128}$.

Clearly, working with explicit representations of these tables is no longer feasible. So this kind of lookup will require a different approach.

We'll return to this in due time, but just know - this is not the end of the story!

Summary

Lookup arguments represent an interesting spin on our journey, as their very existence is motivated by the limitations of what has been our bread and butter thus far: arithmetic constraints.

Perhaps the most important lesson we've learned today has been to not fight against the very nature of things. Non-arithmetic operations are better treated with non-arithmetic methods, and in particular, the table treatment works wonderfully.

This opens the door for all kinds of non-arithmetic operations (like bitwise evaluation, or hashes) to be included into the mix, making the computations we want to build proofs for all the richer.

By now, lookup arguments are ubiquitous: every serious proof system framework (Plonky3, Halo2, etc.) treats them as first-class citizens. They integrate into the PLONK family as one more polynomial identity alongside the wire commitments, and into the STARK family as an additional LogUp identity besides the AIR constraint system.

The end result is a very expressive ZK toolkit, where hash functions, bitwise operations, and similar constructions no longer require hundreds of constraints.

And I think that's really amazing.

While they play a major role in making modern ZK practical, lookup arguments can't solve everything.

We've already mentioned that large tables are particularly cumbersome to work with. But there are other situations that may prove problematic.

For example, what happens when a computation is too large to fit in a single proof? Or when you want to run the same computation many times, and aggregate the results? Or when you want to verify a proof inside another proof?

Don't tell me that last one didn't blow your mind!

These questions all have a common answer. In fact, it involves a technique you've already seen, albeit in a different form.

So next time, we're gonna need to do some folding! See you there!