The Logup-GKR Protocol

1. Overflow

The Logup-GKR protocol constructs and verifies lookup arguments using rational polynomials. First, the Logup lookup argument is defined by the equation \( \sum \frac{m(X)}{f(X)} = \sum \frac{1}{t(X)}, \) where $t(X)$ is a public lookup table represented as $t(X) = \prod (X - t_i)$, and $m(X)$ and $f(X)$ describe the occurrence of elements in the table. Secondly, a Sumcheck protocol is invoked over the two rational polynomials $\frac{m(X)}{f(X)}$ and $\frac{1}{t(X)}$ for efficient verification. Finally, the Sumcheck protocol for each rational polynomial is reduced to the Generalized Knowledge Representation (GKR) protocol, allowing recursive verification of these polynomials in multiple layers, ensuring correctness and integrity in the final evaluation.

1. Logup Lookup Argument \( \sum \frac{m(X)}{f(X)} = \sum \frac{1}{t(X)}. \)
   $t(X)$ represents a public list (lookup table) such that $t(X) = \prod(X-t_i)$;
   $m(X)$ represents the occurrence of each element $t_i \in f(X)$;
   $f(X)$ represents the lookup table, and $f(X) = \prod(X-f_i)$.
2. Then, invoke the Sumcheck protocol over each rational polynomial $\frac{m(X)}{f(X)}$ and $\frac{1}{t(X)}$.
3. Reduce each rational polynomial Sumcheck protocol to the GKR protocol.

2. Idea of Reduction

Fraction addition is crucial in the context of rational polynomials. Given two fractions $\frac{a_0}{b_0}$ and $\frac{a_1}{b_1}$, their sum is computed as follows:\[ \frac{a_0}{b_0} + \frac{a_1}{b_1} = \left(\frac{a_0 b_1 + a_1 b_0}{b_0 b_1}\right) \]This addition rule is applied in the recursive structure of polynomial evaluations. In the context of a circuit, suppose we have a sum of rational polynomials,\( \sum_{x \in H_k} \frac{p(x)}{q(x)} = c, \) where $H_k = +1, -1^k$ is a set of input values. At level 0 of the circuit, the output is set to $c$, and at level $n$, the input layer is also set to $c$. The polynomials $p_n(x)$ and $q_n(x)$ represent the evaluation of $p(x)$ and $q(x)$ at the input layer. In subsequent layers, the evaluation of $p_k(x)$ and $q_k(x)$ is recursively calculated by combining the values from the next layer using the fraction addition rule, allowing for efficient checking and verification of the overall structure.

Definition: Fraction Addition: $\frac{a_0}{b_0} + \frac{a_1}{b_1}$ equals
$(a_0, b_0) + (a_1, b_1) = (a_0 \cdot b_1 + a_1 \cdot b_0, b_0 \cdot b_1)$

1. Suppose \( \sum_{x \in H_k} \frac{p(x)}{q(x)} = c \ (H_k := x: +1, -1^k) \)
2. The output at level 0 of the circuit is set to $c$, and at level $n$, the input layer is also set to $c$.
   At level $n$, $p_n(x), q_n(x) = (p(x), q(x))_n$.
   At level 0, $\frac{p_0}{q_0} = \sum_{x \in H_k} \frac{p(x)}{q(x)}$.
3. Recursively check the inputs of each layer. The check at level $k$ is as follows:
   \[ p_k(x) = p_{k+1}(x,+1) \cdot q_{k+1}(x,+1) + p_{k+1}(x,-1) \cdot q_{k+1}(x,-1) \]\[ q_k(x) = q_{k+1}(x,+1) \cdot q_{k+1}(x,-1) \]

3. GKR Reduction

In this process, the prover first claims the values of $p_1(+1)$, $p_1(-1)$, $q_1(+1)$, and $q_1(-1)$ at level $k=0$. Instead of providing these four values, the prover uses a linear function of $p_1(x)$ and $q_1(x)$ to give $p_1(r_0)$ and $q_1(r_0)$, where $r_0 = 1 - \mu_0$ (with $\mu_0$ chosen by the prover). For each layer $k: 1 \le k \le n-1$, $p_k(x)$ depends on $p_{k+1}(x)$, and $q_k(x)$ depends on $q_{k+1}(x)$, and these values are recursively checked according to the following equations:\[ p_k(x) = \sum_{y \in H_k} L_k(x,y) \cdot (p_{k+1}(y,+1) \cdot q_{k+1}(y,-1) + p_{k+1}(y,+1) \cdot q_{k+1}(y,-1)) \]\[ q_k(x) = \sum_{y \in H_k} L_k(x,y) \cdot q_{k+1}(y,+1) \cdot q_{k+1}(y,-1) \]

Here, $L_k(x,y)$ can be locally evaluated by the verifier. The prover needs to demonstrate that $p_{k+1}(y, +1)$, $q_{k+1}(y, +1)$, $p_{k+1}(y, -1)$, and $q_{k+1}(y, -1)$ are correctly evaluated. The verifier first sends a random challenge $r_k$ and checks the Sumcheck protocol for the two equations. Then, the verifier sends a second challenge $\lambda_k$ to combine the two Sumcheck protocols $p_k(r_k) + \lambda_k \cdot q_k(r_k)$. This process continues until the final round $k = n-1$ (the input layer), ensuring that $p_n(x) = p(x)$ and $q_n(x) = q(x)$.

1. At level $k = 0$, the prover claims the values $p_1(+1)$, $p_1(-1)$, $q_1(+1)$, and $q_1(-1)$. The prover uses a linear function of $p_1(x)$ and $q_1(x)$ to give $p_1(r_0)$ and $q_1(r_0)$, where $r_0 = 1 - \mu_0$ (with $\mu_0$ chosen by the prover).
2. For each layer $k: 1 \le k \le n-1$, $p_k$ depends on $p_{k+1}$, and $q_k$ depends on $q_{k+1}$, recursively checking the following equations:\[ p_k(x) = \sum_{y \in H_k} L_k(x,y) \cdot (p_{k+1}(y,+1) \cdot q_{k+1}(y,-1) + p_{k+1}(y,+1) \cdot q_{k+1}(y,-1)) \]\[ q_k(x) = \sum_{y \in H_k} L_k(x,y) \cdot q_{k+1}(y,+1) \cdot q_{k+1}(y,-1) \]

For $L_k(x,y)$, it can be locally evaluated by the verifier. The prover needs to show the correct evaluation of $p_{k+1}(y, +1)$, $q_{k+1}(y, +1)$, $p_{k+1}(y, -1)$, and $q_{k+1}(y, -1)$. First, the verifier sends a random challenge $r_k$ and checks the Sumcheck protocol for the following two equations:\[ p_k(x) = \sum_{y \in H_k} L_k(r_k,y) \cdot (p_{k+1}(y,+1) \cdot q_{k+1}(y,-1) + p_{k+1}(y,+1) \cdot q_{k+1}(y,-1)) \]\[ q_k(x) = \sum_{y \in H_k} L_k(r_k,y) \cdot q_{k+1}(y,+1) \cdot q_{k+1}(y,-1) \]Then, the verifier sends a random challenge $\lambda_k$ to linearly combine the two sums $p_k(r_k) + \lambda_k \cdot q_k(r_k)$. This process continues until the last round, $k=n-1$ (the input layer), and ensures that $p_n(x) = p(x)$ and $q_n(x) = q(x)$.

Conclusion

The Logup-GKR protocol offers an efficient and robust approach for verifying complex computations involving rational polynomials. By leveraging the powerful Sumcheck protocol and reducing it to the Generalized Knowledge Representation (GKR) protocol, it allows for recursive and verifiable evaluation of polynomial expressions across multiple layers. This multi-layer verification ensures the correctness and integrity of the final results, while minimizing the computational overhead for the prover. The use of fraction addition and local checks by the verifier strengthens the protocol's reliability, making it suitable for a wide range of applications that require scalable and secure proof systems, such as zero-knowledge proofs in cryptographic systems. Ultimately, the Logup-GKR protocol provides a solid foundation for efficient, verifiable computation in distributed systems.

Subscribe to the ZKM Blog to stay updated with the latest research by ZKM.
Explore the ZKM Docs
Start building with ZKM GitHub
‍Follow the ZKM X