1. Overflow

Logup-GKR协议使用有理多项式构建和验证查找论证。首先，通过方程$\sum\frac{m(X)}{f(X)}=\sum\frac{1}{t(X)}$定义Logup查找论证，其中$t(X)$是一个公共查找表，表示为$t(X) = \prod(X - t_i)$，而$m(X)$和$f(X)$描述了表中元素的出现次数。其次，对两个有理多项式$\frac{m(X)}{f(X)}$和$\frac{1}{t(X)}$调用Sumcheck协议，以进行高效验证。最后，将每个有理多项式的Sumcheck协议归约为广义知识表示（GKR）协议，允许在多个层级中递归验证这些多项式，确保最终评估的正确性和完整性。

1. Logup查找论证 $\sum\frac{m(X)}{f(X)}=\sum\frac{1}{t(X)}$：

   • $t(X)$表示一个公共列表（查找表），其中$t(X)=\prod(X - t_i)$；
   • $m(X)$表示每个元素$t_i \in f(X)$的出现次数；
   • $f(X)$表示查找表，且$f(X)=\prod(X - f_i)$。

2. 然后对每个有理多项式$\frac{m(X)}{f(X)}$ 和 $\frac{1}{t(X)}$调用Sumcheck协议。

3. 将每个有理多项式的Sumcheck协议协议归约为GKR协议。

2. 归约思想

分数加法在有理多项式的上下文中非常重要。给定两个分数$\frac{a_0}{b_0}$和$\frac{a_1}{b_1}$，它们的和可以按以下方式计算：

$$ \frac{a_0}{b_0} + \frac{a_1}{b_1} = \left(\frac{a_0 \cdot b_1 + a_1 \cdot b_0}{b_0 \cdot b_1}\right) $$

这个加法规则在多项式评估的递归结构中被应用。在电路上下文中，假设我们有一个有理多项式的和，$\sum_{x \in H_k} \frac{p(x)}{q(x)} = c$，其中$H_k = {+1, -1}^k$是输入值的集合。在电路的第0层，电路的输出设置为$c$，而在第$n$层，输入层也设置为$c$。多项式$p_n(x)$和$q_n(x)$表示输入层上$p(x)$和$q(x)$的评估。在后续的层级中，通过使用分数加法规则，递归地将来自下一个层级的值组合起来，从而高效地检查和验证整个结构。

定义： 分数加法：$\frac{a_0}{b_0} + \frac{a_1}{b_1}$ 等于 $(a_0,b_0) + (a_1,b_1) = (a_0 \cdot b_1 + a_1 \cdot b_0, b_0 \cdot b_1)$

1. 假设 $\sum_{x \in H_k} \frac{p(x)}{q(x)} = c\ (H_k := {x : {+1, -1}^k})$

2. 电路的第0层是电路的输出，并设为$c$，第$n$层是输入层，也设为$c$。

   • 在第$n$层，$p_n(x), q_n(x) = (p(x), q(x))$。
   • 在第0层，$\frac{p_0}{q0} = \sum{x \in H_k} \frac{p(x)}{q(x)}$。

3. 递归地检查每一层的输入。第$k$层的检查如下： $$ pk(x) = p{k+1}(x,+1) \cdot q{k+1}(x,+1) + p{k+1}(x,-1) \cdot q_{k+1}(x,-1) $$
   $$ qk(x) = q{k+1}(x,+1) \cdot q_{k+1}(x,-1) $$

3. GKR归约

在这个过程中，证明者首先在第$k=0$层声称$p_1(+1)$、$p_1(-1)$、$q_1(+1)$和$q_1(-1)$的值。证明者并不是提供这四个值，而是使用$p_1(x)$和$q_1(x)$的线性函数，给出$p_1(r_0)$和$q_1(r_0)$，其中，$r_0 = 1 - \mu_0$（$\mu_0$由证明者选择）。对于每一层$k: 1 \leq k \leq n - 1$，$pk(x)$依赖于$p{k+1}(x)$，$qk(x)$依赖于$q{k+1}(x)$，并且这些值根据以下方程递归检查： $$ pk(x) = \sum{y \in H_k} Lk(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)) $$

$$ qk(x) = \sum{y \in H_k} Lk(x, y) \cdot q{k+1}(y, +1) \cdot q_{k+1}(y, -1) $$

其中，$Lk(x, y)$可以由验证者局部评估。证明者需要证明$p{k+1}(y, +1)$、$q{k+1}(y, +1)$、$p{k+1}(y, -1)$和$q_{k+1}(y, -1)$被正确评估。验证者首先发送一个随机挑战$r_k$并检查两个方程的Sumcheck协议。然后，验证者发送第二个挑战$\lambda_k$来组合两个Sumcheck协议$p_k(r_k) + \lambda_k \cdot q_k(r_k)$。这个过程一直持续到最后一层$k = n - 1$，在这一层，验证$p_n(x) = p(x)$和$q_n(x) = q(x)$的正确性。

1. 在第$k = 0$层，证明者声称$p_1(+1)$、$p_1(-1)$、$q_1(+1)$和$q_1(-1)$的值。证明者使用$p_1(x)$和$q_1(x)$的线性函数，给出$p_1(r_0)$和$q_1(r_0)$，其中$r_0 = 1 - \mu_0$（$\mu_0$由证明者选择）。
2. 对于每一层$k: 1 \leq k \leq n - 1$，$pk$依赖于$p{k+1}$，$qk$依赖于$q{k+1}$，递归检查以下方程： $$ pk(x) = \sum{y \in H_k} Lk(x, y) · (p{k+1}(y, +1) \cdot q{k+1}(y, -1) + p{k+1}(y, +1)\cdot q_{k+1}(y, -1)) $$ $$ qk(x) = \sum{y \in H_k} Lk(x, y) · q{k+1}(y, +1)\cdot q_{k+1}(y, -1) $$ 对于$Lk(x, y)$，验证者可以局部评估。证明者需要展示$p{k+1}(y, +1)$、$q{k+1}(y, +1)$、$p{k+1}(y, -1)$、$q_{k+1}(y, -1)$的正确评估。 首先，验证者发送随机挑战$r_k$并检查以下两个方程的Sumcheck协议： $$ pk(x) = \sum{y \in H_k} L_k(rk, y) \cdot (p{k+1}(y, +1) \cdot q{k+1}(y, -1) + p{k+1}(y, +1)\cdot q_{k+1}(y, -1)) $$ $$ qk(x) = \sum{y \in H_k} L_k(rk, y) \cdot q{k+1}(y, +1)\cdot q_{k+1}(y, -1) $$ 然后，验证者发送一个随机挑战$\lambda_k$，用于将两个累加和 $p_k(r_k)+\lambda_k\cdot{q_k(r_k)}$ 进行线性组合。直到最后一轮，即 $ k = n - 1$ （即输入层），并确保 $p_n(x) = p(x)$ 和 $q_n(x) = q(x)$ 。