# Introduction to lookup arguments

Lookup arguments are a technique used in zero-knowledge proof systems. It allows to efficiently enforce that certain values computed inside a circuit belong to a predetermined “lookup table.”

## Use cases
* **Range checks / bit decomposition**
* **Boolean constraints**. Enforcing that a witness is exactly 0 or 1 can be done by looking it up in the two‐element table {0,1}.
* **Merkle-Tree and hash path verification**
Instead of re-deriving a hash function step by step, you can table small hash rounds or precompute parts of the compression function.
* **Elliptic-Curve Operations**
EC addition or doubling formulas often involve field inversions and multiplications. By precomputing small sub‐operations into tables (e.g. slope values for a range of inputs), you can replace heavy arithmetic with cheap lookups.

There are two types of lookup arguments:
* indexed ([Lasso](https://eprint.iacr.org/2023/1216.pdf), [Twist and Shout](https://eprint.iacr.org/2025/105.pdf))
* unindexed ([Arya](https://eprint.iacr.org/2018/380.pdf), [Plookup](https://eprint.iacr.org/2020/315.pdf), [Logup](https://eprint.iacr.org/2023/1284.pdf))

## Unindexed lookup arguments
* Setup: table $t \in F^n$, vector $v \in F^m$, v is a subset of t
* Prover wants to prove for each $v_i$ there is some index j such that $v_i = t[j]$

## Indexed lookups

* Prover commited to vectors $a,v \in F^m$
in predetermined table $t \in F^N$ of some field elements
* P wants to prove that for i = 1..m, $v_i = t[a_i]$
$a_i$ are table indices
$v_i$ are values
In a nutshell, table $t$ is preinitialized memory (read only memory)

### Alternative view of indexed lookup arguments:
Let $t$ be a table and $N =2^n$ be its size
$f: \{0,1\}^n \;\longrightarrow\; \mathbb{F}$ - f maps n-bit vector to a field element;
$t[x] = f(x)$, t is indexed by n-bit vector
P commits $a,v \in F^m$ and proves $v_i$ = $t[a_i]$
Example :
* table size is $2^{16}$,
* |F| = $2^{256}$ (prime order)
We intepret field elements in range (0...$2^{16}-1$) as indices of a table $t$
If any index out of this range (0...$2^{16}-1$), the prover will get caught and the verifier will reject

### Naive baseline
Indexed lookup arguments is an efficient SNARK for data parallel computation
Setup: Inputs $(a_1...a_n)$ and outputs $(v_1...v_n)$ are commited
Apply generic SNARK for that (GKR, Marlin etc)


## **Summary**:
* Lookup arguments are ideal for **amortized scenarios**. If you perform a large number of lookups on a table, you can achieve significant cost savings.
* Table‐lookups are much faster than arithmetic gates for non-linear or high-fan-in operations.