.png)
Lookup Argument is an important cryptographic primitive used to prove that elements of one set (or structured objects like polynomials) belong to another precomputed set or structure. It plays a crucial role in zero-knowledge proof systems by enforcing data consistency and constraints without revealing sensitive information.In the context of zkVM applications, the Lookup Argument is used for efficiently verifying the inclusion relationship between inputs and precomputed tables. This is particularly important in the following scenarios:
In the context of zkVM applications, the Lookup Argument is used for efficiently verifying the inclusion relationship between inputs and precomputed tables. This is particularly important in the following scenarios:
Let $P$ be an $n$-variate polynomial over a finite field $F$, given by $P = F\left( x_{1},...,x_{n} \right)$, with degree $d$. Let $S$ be a subset of $F$, and let $r_{1},...,r_{n}$ be randomly chosen from $S$. Then, the probability that the polynomial evaluates to zero is negligible:
$$\Pr\left\lbrack P\left( r_{1},...,r_{n} \right) = 0 \right\rbrack \leq \frac{d}{|S|}$$
In the univariate case, a polynomial of degree $d$ has at most $d$ roots.
Given coefficients $a_{1},...,a_{n}$ of a polynomial over a finite field $F$, coefficients $b_{1},...,b_{n}$ of another polynomial $g$, and a subset $H = \{ x_{1},...,x_{n}\} \subset F$:
1. If the elements of the two sets $\{ a_{i}\},i = 1,...,n$ and $\{ b_{i}\},i = 1,...,n$ are equal (i.e., $a_{i} = b_{i},\forall i \in \lbrack n\rbrack$), then their product values are equal:
$$\prod_{i \in \lbrack n\rbrack}^{}a_{i} = \prod_{i \in \lbrack n\rbrack}^{}b_{i}$$
2. Conversely, if $\prod_{i \in \lbrack n\rbrack}^{}a_{i} = \prod_{i \in \lbrack n\rbrack}^{}b_{i}$, then, according to the Schwartz--Zippel Lemma, a polynomial can be constructed:
$$P\left( X_{1},...,X_{n} \right)\ = \ \prod_{i \in \lbrack n\rbrack}^{}\left( X_{i} - a_{i} \right) = 0$$
The probability that $P\left( X_{1},...,X_{n} \right)$ evaluates to zero over randomly chosen values from $H$ is negligible.
Thus, if $P\left( X_{1},...,X_{n} \right) = 0$, then $\left( b_{1},...,b_{n} \right)$ is a solution, meaning the elements in both sets are equal $a_{i} = b_{i},\forall i \in \lbrack n\rbrack$. Consequently, the polynomials $F$ and $g$ are equal.
By introducing a random number, the product consistency checking principle can be transformed into a more useful tool: multiset equality checking.
Given two vectors $\overrightarrow{a} = \left( a_{1},...,a_{n} \right)$ and $\overrightarrow{b} = \left( b_{1},...,b_{n} \right)$, the goal is to verify whether they contain the same elements, even if they appear in different orders or with different multiplicities.
Reduction from Multiset Equality to Product Consistency: The verifier $V$ selects a random number $\gamma \in F$ and checks the following equality for the randomly transformed vectors $a'\ = \ a + \gamma$, $b'\ = \ b + \gamma$ (where $\gamma$ is added to all coordinates):
$$\prod_{i \in \lbrack n\rbrack}^{}\left( a_{i} + \gamma \right) = \prod_{i \in \lbrack n\rbrack}^{}\left( b_{i} + \gamma \right)$$
By the Schwartz-Zippel Lemma, unless $a'$ and $b'$ are identical multisets, the probability that the above equation holds is negligible.
The prover $P$ sends a degree-$d$ polynomial to a trusted third party $I$ (using $P$'s polynomial commitment). After the protocol execution, the verifier $V$ queries the trusted third party $I$: does the degree-$d$ secret input polynomial defined on the set $H$ satisfy a specific property with respect to the publicly known precomputed polynomial? This is equivalent to $V$ checking whether a quotient polynomial exists, which is the same as verifying the correctness of a randomly opened point. Given fixed integers $d,D,t,l$ and a set $H \subset F$:
The verifier $V$ then queries the trusted third party $I$ to check whether the polynomials $f_{1},...,f_{t},g_{1},...,g_{l}$ satisfy a given functional relation over $H$:
$$F(X) = G\left( \alpha,X,h_{1}\left( v_{1}(X) \right),...,h_{M}\left( v_{M}(X) \right) \right) \equiv 0$$
where $h_{i} \in \{ f_{1},...,f_{t},g_{1},...,g_{l}\}$, $G \in F_{d}\left\lbrack X,X_{1},...,X_{M} \right\rbrack$, and $v_{1},...,v_{M} \in F_{d}\lbrack X\rbrack$, ensuring $F \in F_{< D}\lbrack X\rbrack$ (equivalent to verifying the existence of a quotient polynomial).
Once the verifier $V$ receives the result from the trusted third party $I$, it either accepts or rejects.
In the polynomial protocol above, let $H$ be a multiplicative subgroup of order $N$ with generator $g$. For $i \in \lbrack N\rbrack$, define the $i$-th Lagrange polynomial $L_{i} \in F_{< N}\lbrack X\rbrack$ satisfying:
For $x \in H$, requiring $L_{i}(x)f(x) = 0$ is equivalent to $f\left( g^{i} \right) = 0$.
For integers $n,d$, and vectors $f \in F^{n},t \in F^{d}$, the notation $f \subset t$ means that $\{ f_{i}\}_{i \in \lbrack n\rbrack} \subset \{ t_{i}\}_{i \in \lbrack d\rbrack}$.
Let $H = \{ g,...,g^{n + 1} = 1\}$ be a multiplicative subgroup of order $n + 1$.
If $f \subset t$ and the order of elements in $F$ matches their order in $t$, we say that $F$ is partitioned by $t$.
Given vectors $f \in F^{n},t \in F^{d},s \in F^{n + d}$, we define the following two bivariate polynomials $F(\beta,\gamma)$ and $G(\beta,\gamma)$:
$$F(\beta,\gamma)\ = \ (1 + \beta)^{n} \cdot \prod_{i \in \lbrack n\rbrack}^{}\left( \gamma + f_{i} \right)\prod_{i \in \lbrack d - 1\rbrack}^{}\left( \gamma(1 + \beta) + t_{i} + \beta \cdot t_{i + 1} \right)$$
$$G(\beta,\gamma)\ = \ \prod_{i \in \lbrack n + d - 1\rbrack}^{}\left( \gamma(1 + \beta) + s_{i} + \beta \cdot s_{i + 1} \right)$$
Theorem: $F \equiv G$ if and only if $f \subset t$ and $s = (f,t)$ is partitioned by $t$.
Proof:
1. Case 1: If $f \subset t$ and $s = (f,t)$ is partitioned by $t$:
2. Case 2: If $F \equiv G$:
By combining Case 1 and Case 2, the theorem is proven.
Precomputation: A public and correct table polynomial: $t \in F_{< n + 1}\lbrack X\rbrack$. The lookup table is expressed using polynomial values.
Prover's Input: A secret polynomial: $f \in F_{< n}\lbrack X\rbrack$. The witness is expressed using polynomial values.
1. Polynomial Combination and Partitioning Let $s \in F^{2n + 1}\ $be the combination of polynomials $f\ $and $t$ as $s = (f,t)$ , partitioned by $t$ .\Using two polynomials $h_{1},h_{2} \in F_{< n + 1}\lbrack X\rbrack$ , the polynomial $s$ is expressed as:
$$h_{1}\left( g^{i} \right) = s_{i},\quad i \in \lbrack n + 1\rbrack,\quad h_{2}\left( g^{i} \right) = s_{n + i},\quad i \in \lbrack n + 1\rbrack.$$
2. Polynomial Commitment The prover $P$ computes polynomials $h_{1},h_{2}$ and sends them to the trusted third party $I$ ; ( $P$ commits to $s$ or $h_{1},h_{2}$ using polynomial commitments).
3. Random Number Generation The verifier $V$ selects random numbers $\beta,\gamma \in F$ and sends them to the prover $P$ .
4. Aggregation Polynomial The prover $P\ $computes a polynomial $Z \in F_{< n + 1}\lbrack X\rbrack$ and the function values of the binary polynomial aggregation $F(\beta,\gamma)/G(\beta,\gamma)$ , satisfying the following properties:
$$Z(g) = 1,$$
$$Z\left( g^{i} \right) = \frac{(1 + \beta)^{i - 1} \cdot \prod_{j < i}^{}\left( \gamma + f_{j} \right) \cdot \prod_{1 < j < i}^{}\left( \gamma(1 + \beta) + t_{j} + \beta \cdot t_{j + 1} \right)}{\prod_{1 < j < i}^{}\left( \gamma(1 + \beta) + s_{j} + \beta \cdot s_{j + 1} \right)\left( \gamma(1 + \beta) + s_{n + j} + \beta \cdot s_{n + j + 1} \right)},$$
$$Z\left( g^{n + 1} \right) = 1.$$
The prover $P$ then sends $Z$ to the trusted third party $I$ .
5. Consistency Verification The verifier $V$ checks whether $Z$ satisfies the following consistency conditions (for $x \in H$ ):
$$L_{1}(x)\left( Z(x) - 1 \right) = 0,$$
$$\left( x - g^{n + 1} \right)Z(x)(1 + \beta) \cdot \left( \gamma + f(x) \right)\left( \gamma(1 + \beta) + t(x) + \beta \cdot t(g \cdot x) \right) =$$
$$\left( x - g^{n + 1} \right)Z(g \cdot x)\left( \gamma(1 + \beta) + h_{1}(x) + \beta \cdot h_{1}(g \cdot x) \right)\left( \gamma(1 + \beta) + h_{2}(x) + \beta \cdot h_{2}(g \cdot x) \right),$$
$$L_{n + 1}(x)\left( h_{1}(x) - h_{2}(g \cdot x) \right) = 0,$$
$$L_{n + 1}(x)\left( Z(x) - 1 \right) = 0.$$
If all four conditions hold, the verifier accepts; otherwise, it rejects.
Security and Proof Length Analysis
Thus, when $F \equiv G$ , it follows that $f \subset t$ . This demonstrates that the prover's witness exists in the publicly correct dataset, ensuring the correctness of input-output constraints and verifying the correctness of the prover's computation.
The Lookup Argument has extensive applications in zero-knowledge proofs, including:
The Lookup Argument is a fundamental component of modern cryptographic protocols, enabling efficient and secure membership proofs. By leveraging polynomial commitments, random challenges, and witness generation, it ensures the soundness, completeness, and privacy of the protocol. It plays a crucial role in constructing scalable, robust, and secure zero-knowledge proof systems.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions about the article, you can contact the ZKM team on discord: discord.com/zkm
Lookup Argument is an important cryptographic primitive used to prove that elements of one set (or structured objects like polynomials) belong to another precomputed set or structure. It plays a crucial role in zero-knowledge proof systems by enforcing data consistency and constraints without revealing sensitive information.In the context of zkVM applications, the Lookup Argument is used for efficiently verifying the inclusion relationship between inputs and precomputed tables. This is particularly important in the following scenarios:
In the context of zkVM applications, the Lookup Argument is used for efficiently verifying the inclusion relationship between inputs and precomputed tables. This is particularly important in the following scenarios:
Let $P$ be an $n$-variate polynomial over a finite field $F$, given by $P = F\left( x_{1},...,x_{n} \right)$, with degree $d$. Let $S$ be a subset of $F$, and let $r_{1},...,r_{n}$ be randomly chosen from $S$. Then, the probability that the polynomial evaluates to zero is negligible:
$$\Pr\left\lbrack P\left( r_{1},...,r_{n} \right) = 0 \right\rbrack \leq \frac{d}{|S|}$$
In the univariate case, a polynomial of degree $d$ has at most $d$ roots.
Given coefficients $a_{1},...,a_{n}$ of a polynomial over a finite field $F$, coefficients $b_{1},...,b_{n}$ of another polynomial $g$, and a subset $H = \{ x_{1},...,x_{n}\} \subset F$:
1. If the elements of the two sets $\{ a_{i}\},i = 1,...,n$ and $\{ b_{i}\},i = 1,...,n$ are equal (i.e., $a_{i} = b_{i},\forall i \in \lbrack n\rbrack$), then their product values are equal:
$$\prod_{i \in \lbrack n\rbrack}^{}a_{i} = \prod_{i \in \lbrack n\rbrack}^{}b_{i}$$
2. Conversely, if $\prod_{i \in \lbrack n\rbrack}^{}a_{i} = \prod_{i \in \lbrack n\rbrack}^{}b_{i}$, then, according to the Schwartz--Zippel Lemma, a polynomial can be constructed:
$$P\left( X_{1},...,X_{n} \right)\ = \ \prod_{i \in \lbrack n\rbrack}^{}\left( X_{i} - a_{i} \right) = 0$$
The probability that $P\left( X_{1},...,X_{n} \right)$ evaluates to zero over randomly chosen values from $H$ is negligible.
Thus, if $P\left( X_{1},...,X_{n} \right) = 0$, then $\left( b_{1},...,b_{n} \right)$ is a solution, meaning the elements in both sets are equal $a_{i} = b_{i},\forall i \in \lbrack n\rbrack$. Consequently, the polynomials $F$ and $g$ are equal.
By introducing a random number, the product consistency checking principle can be transformed into a more useful tool: multiset equality checking.
Given two vectors $\overrightarrow{a} = \left( a_{1},...,a_{n} \right)$ and $\overrightarrow{b} = \left( b_{1},...,b_{n} \right)$, the goal is to verify whether they contain the same elements, even if they appear in different orders or with different multiplicities.
Reduction from Multiset Equality to Product Consistency: The verifier $V$ selects a random number $\gamma \in F$ and checks the following equality for the randomly transformed vectors $a'\ = \ a + \gamma$, $b'\ = \ b + \gamma$ (where $\gamma$ is added to all coordinates):
$$\prod_{i \in \lbrack n\rbrack}^{}\left( a_{i} + \gamma \right) = \prod_{i \in \lbrack n\rbrack}^{}\left( b_{i} + \gamma \right)$$
By the Schwartz-Zippel Lemma, unless $a'$ and $b'$ are identical multisets, the probability that the above equation holds is negligible.
The prover $P$ sends a degree-$d$ polynomial to a trusted third party $I$ (using $P$'s polynomial commitment). After the protocol execution, the verifier $V$ queries the trusted third party $I$: does the degree-$d$ secret input polynomial defined on the set $H$ satisfy a specific property with respect to the publicly known precomputed polynomial? This is equivalent to $V$ checking whether a quotient polynomial exists, which is the same as verifying the correctness of a randomly opened point. Given fixed integers $d,D,t,l$ and a set $H \subset F$:
The verifier $V$ then queries the trusted third party $I$ to check whether the polynomials $f_{1},...,f_{t},g_{1},...,g_{l}$ satisfy a given functional relation over $H$:
$$F(X) = G\left( \alpha,X,h_{1}\left( v_{1}(X) \right),...,h_{M}\left( v_{M}(X) \right) \right) \equiv 0$$
where $h_{i} \in \{ f_{1},...,f_{t},g_{1},...,g_{l}\}$, $G \in F_{d}\left\lbrack X,X_{1},...,X_{M} \right\rbrack$, and $v_{1},...,v_{M} \in F_{d}\lbrack X\rbrack$, ensuring $F \in F_{< D}\lbrack X\rbrack$ (equivalent to verifying the existence of a quotient polynomial).
Once the verifier $V$ receives the result from the trusted third party $I$, it either accepts or rejects.
In the polynomial protocol above, let $H$ be a multiplicative subgroup of order $N$ with generator $g$. For $i \in \lbrack N\rbrack$, define the $i$-th Lagrange polynomial $L_{i} \in F_{< N}\lbrack X\rbrack$ satisfying:
For $x \in H$, requiring $L_{i}(x)f(x) = 0$ is equivalent to $f\left( g^{i} \right) = 0$.
For integers $n,d$, and vectors $f \in F^{n},t \in F^{d}$, the notation $f \subset t$ means that $\{ f_{i}\}_{i \in \lbrack n\rbrack} \subset \{ t_{i}\}_{i \in \lbrack d\rbrack}$.
Let $H = \{ g,...,g^{n + 1} = 1\}$ be a multiplicative subgroup of order $n + 1$.
If $f \subset t$ and the order of elements in $F$ matches their order in $t$, we say that $F$ is partitioned by $t$.
Given vectors $f \in F^{n},t \in F^{d},s \in F^{n + d}$, we define the following two bivariate polynomials $F(\beta,\gamma)$ and $G(\beta,\gamma)$:
$$F(\beta,\gamma)\ = \ (1 + \beta)^{n} \cdot \prod_{i \in \lbrack n\rbrack}^{}\left( \gamma + f_{i} \right)\prod_{i \in \lbrack d - 1\rbrack}^{}\left( \gamma(1 + \beta) + t_{i} + \beta \cdot t_{i + 1} \right)$$
$$G(\beta,\gamma)\ = \ \prod_{i \in \lbrack n + d - 1\rbrack}^{}\left( \gamma(1 + \beta) + s_{i} + \beta \cdot s_{i + 1} \right)$$
Theorem: $F \equiv G$ if and only if $f \subset t$ and $s = (f,t)$ is partitioned by $t$.
Proof:
1. Case 1: If $f \subset t$ and $s = (f,t)$ is partitioned by $t$:
2. Case 2: If $F \equiv G$:
By combining Case 1 and Case 2, the theorem is proven.
Precomputation: A public and correct table polynomial: $t \in F_{< n + 1}\lbrack X\rbrack$. The lookup table is expressed using polynomial values.
Prover's Input: A secret polynomial: $f \in F_{< n}\lbrack X\rbrack$. The witness is expressed using polynomial values.
1. Polynomial Combination and Partitioning Let $s \in F^{2n + 1}\ $be the combination of polynomials $f\ $and $t$ as $s = (f,t)$ , partitioned by $t$ .\Using two polynomials $h_{1},h_{2} \in F_{< n + 1}\lbrack X\rbrack$ , the polynomial $s$ is expressed as:
$$h_{1}\left( g^{i} \right) = s_{i},\quad i \in \lbrack n + 1\rbrack,\quad h_{2}\left( g^{i} \right) = s_{n + i},\quad i \in \lbrack n + 1\rbrack.$$
2. Polynomial Commitment The prover $P$ computes polynomials $h_{1},h_{2}$ and sends them to the trusted third party $I$ ; ( $P$ commits to $s$ or $h_{1},h_{2}$ using polynomial commitments).
3. Random Number Generation The verifier $V$ selects random numbers $\beta,\gamma \in F$ and sends them to the prover $P$ .
4. Aggregation Polynomial The prover $P\ $computes a polynomial $Z \in F_{< n + 1}\lbrack X\rbrack$ and the function values of the binary polynomial aggregation $F(\beta,\gamma)/G(\beta,\gamma)$ , satisfying the following properties:
$$Z(g) = 1,$$
$$Z\left( g^{i} \right) = \frac{(1 + \beta)^{i - 1} \cdot \prod_{j < i}^{}\left( \gamma + f_{j} \right) \cdot \prod_{1 < j < i}^{}\left( \gamma(1 + \beta) + t_{j} + \beta \cdot t_{j + 1} \right)}{\prod_{1 < j < i}^{}\left( \gamma(1 + \beta) + s_{j} + \beta \cdot s_{j + 1} \right)\left( \gamma(1 + \beta) + s_{n + j} + \beta \cdot s_{n + j + 1} \right)},$$
$$Z\left( g^{n + 1} \right) = 1.$$
The prover $P$ then sends $Z$ to the trusted third party $I$ .
5. Consistency Verification The verifier $V$ checks whether $Z$ satisfies the following consistency conditions (for $x \in H$ ):
$$L_{1}(x)\left( Z(x) - 1 \right) = 0,$$
$$\left( x - g^{n + 1} \right)Z(x)(1 + \beta) \cdot \left( \gamma + f(x) \right)\left( \gamma(1 + \beta) + t(x) + \beta \cdot t(g \cdot x) \right) =$$
$$\left( x - g^{n + 1} \right)Z(g \cdot x)\left( \gamma(1 + \beta) + h_{1}(x) + \beta \cdot h_{1}(g \cdot x) \right)\left( \gamma(1 + \beta) + h_{2}(x) + \beta \cdot h_{2}(g \cdot x) \right),$$
$$L_{n + 1}(x)\left( h_{1}(x) - h_{2}(g \cdot x) \right) = 0,$$
$$L_{n + 1}(x)\left( Z(x) - 1 \right) = 0.$$
If all four conditions hold, the verifier accepts; otherwise, it rejects.
Security and Proof Length Analysis
Thus, when $F \equiv G$ , it follows that $f \subset t$ . This demonstrates that the prover's witness exists in the publicly correct dataset, ensuring the correctness of input-output constraints and verifying the correctness of the prover's computation.
The Lookup Argument has extensive applications in zero-knowledge proofs, including:
The Lookup Argument is a fundamental component of modern cryptographic protocols, enabling efficient and secure membership proofs. By leveraging polynomial commitments, random challenges, and witness generation, it ensures the soundness, completeness, and privacy of the protocol. It plays a crucial role in constructing scalable, robust, and secure zero-knowledge proof systems.
Subscribe to the ZKM Blog to stay updated with the latest research by ZKM. If you have any questions about the article, you can contact the ZKM team on discord: discord.com/zkm
