【理解 PLONK - 3 - lookup】 by 郭宇老师@安比实验室 05/09

[Demian101]

视频地址：

https://706community.notion.site/Plonk-Lookup-argument-89aedd901a39469599e43ff7016d0245

Quick notes

(github 排版有大问题，推荐 .md 版本)

lookup.md

PLONK: Lookup Argument

• 尽量去实现一下，能让自己写更多的电路进去

plonk -> TurboPLONK -> UltraPLONK

• PLONK 的加法门 Additive gate is not free （和 R1CS 相比）
  • 初看是个不好的东西
• TurboPLONK： 引入了多项式门
  • 多项式可以写得更复杂一点： ${x_1}^3+2{x_2}^2 +x_3$ ----- degree 是 3
• UltraPLONK：
  • 自定义门： $t(x_1, x_2)$ ，$x_1, x_2$ 只要满足一张表即可。在这张表里可以任意 Arbitrary pre-defined
  • table 是提前共识好的一张表（Prover 和 Verifier 都知道）
    • Verifier 知道映射值，但不知道原始值
    • Verifier 不知道哪一行被用到
  • 问题：Prover 如何证明这张表，如何证明 $x_1,x_2,x_3$ 属于这张表？
    • 自然想到：Merkle Tree （或者说 Vector commitment)
      • Vector commitment：要证明一个元素在一个 Merkle Tree 里面（这是 visible position）
    • 但是 lookup：是 Invisible position 的
      • 不能让你知道元素的位置。否则 Witness 就暴露了
      • 比较像：set membership Argument （set membership 就是看一个值在不在一个集合里面）

Halo2 —— lookup

（single column，假设这个表只有一列）

• Prover: $\vec{f} = (f_0, f_1,f_{m-1})$

• Verifier: $\vec{t}=(t_0, t_1,t_{n-1}$ （共识向量）

  • P 想证的是：${f_i} \in_{set}{t_j}^{N-1}_{j=0}$
  • f 中的任何一个元素都在 t 里面
  • 但是 f 中的元素是可以重复的
    • 如果 f 中的重复元素消掉，那么 f 是 t 的子集

• P 要构造 2 个辅助向量（auxiliary vector）：

  • ① $\vec{f}'$ => is reorder of $\vec{f}$

    • 举例：$\vec{t} = (1,2,3,4,5,6)$
    • $\vec{f} = (3,2,1,2,4,2)$
    • 对 $\vec{f}$ reorder 产生 $\vec{f}'$
      • $\vec{f}' = (1,2,2,2,3,4)$ ( 按照在 t 中的顺序)

  • ② $\vec{t}'$ => is reorder of $\vec{t}$

    • 有点 tricky：是根据 $\vec{f}'$ 的顺序去排列 $\vec{t'}$
    • 先从不重复的开始（让其一一对应）
      • $\vec{t}' = (1,2,_,_,3,4)$ 5,6 没着落 --- 放到横线上
      • $\vec{t}' = (1,2,{\color{green}5,6},3,4)$

  • 引出：$\color{red}\forall i: \quad f_i' =t_i' \quad or \quad f_i' =f_{i-1}'$

  • 

  • 插值：$f'(x) = f_0'\cdot L_0(X) + f_1'\cdot L_1(X)+...+ f_{N-1}'\cdot L_{N-1}(X)$

    • $L_{i}(X) = \frac{Z_{H}(X)}{L'(\omega_i) \cdot (x- \omega_i)}$

  • 插值：$t'(x) = t_0'\cdot L_0(X) + t_1'\cdot L_1(X)+...+ t_{N-1}'\cdot L_{N-1}(X)$

  • 有约束：

    • $(f'(X)- t'(X)) \cdot (f'(X) - f'(\omega^{-1} \cdot X)) =0, \quad a\forall x \in H$

    • 但是还不够，因为这个是 Prover 构造的，Prover 可以构造：

      • $f'(X) = (7,7,7,7,7,7,7)$ 永远满足左式的右边 $f'(\omega^{-1} \cdot X)) =0$

    • 

    • 接下来需要证明：

      • $\vec{f'}$ is a Permutation of $\vec{f}$
      • $\vec{t'}$ is a Permutation of $\vec{t}$

    • Permutation Argument reduce 到 multiset equality Argument

      • （这俩的区别：多了个序号
      • Permutation Argument：pre-defined $\sigma(\cdot)$
      • Multiset equality Argument : some unknown $\sigma(\cdot)$

    • Construct an accumulator vector $\vec{Z}$

      • $Z_0 =1$ ; $Z_{i+1} = Z_i \cdot \frac{f_i'+ \gamma_1}{f_i+ \gamma_1} \cdot \frac{t_i'+ \gamma_2}{t_i+ \gamma_2}$ 带着 $t(x)$ 也一起做

    • $Z(X) = Z_0 \cdot L_0(X) + Z_1 \cdot L_1(X) + ...+ Z_{N-1} L_{N-1}(X)$

    • $L_0(X) \cdot (Z(X)-1) =0$

    • $Z(\omega \cdot x) \cdot (f(x) + \gamma_1 )\cdot(t(x) + \gamma_1 ) - Z(X) .... $

      • [TODO]

    • 

多列：

多 table：

• 4-bit XOR
• 8-bit XOR
  • 多加一列：table-selector