06. PLONKish 自定义门与查表：Plookup、Halo 2、LogUp、Lasso

1. 为什么 lookup 是现代证明系统的核心

有限域乘加很便宜，但计算机语义大量是非算术的：

• $0\le x<2^{16}$；
• $z=x\mathbin{\mathrm{XOR}}y$；
• opcode 属于合法指令集合；
• byte decomposition；
• S-box、AES/Keccak 小部件；
• memory event 属于另一张表；
• 条件跳转的 selector/flag 合法。

lookup 把复杂关系

\[R(u_0,\ldots,u_{k-1})=1\]

预先列成 table

\[T\subset\mathbb F^k,\]

每行只需证明 query tuple

\[(u_0,\ldots,u_{k-1})\in T.\]

flowchart LR
    Q["witness query<br/>(x,y,z)"] --> L["lookup argument"]
    T["valid table<br/>例如所有 z=x XOR y"] --> L
    L --> O["证明 query 属于 table"]

lookup 的成本与 table 大小、query 数、table 是否固定/可预处理、PCS 类型密切相关。

2. 先把 tuple 随机压成一个字段元素

对 $k$ 列 query，commitments 绑定后采样 $\theta$，定义

\[\operatorname{compress}_\theta (u_0,\ldots,u_{k-1}) =u_0+\theta u_1+\cdots+\theta^{k-1}u_{k-1}.\]

table rows 同样压缩。若两个不同 tuples 压成同一值，则 $\theta$ 是某个次数至多 $k-1$ 的非零多项式的根，所以碰撞概率至多约

\[\frac{k-1}{|\mathbb F|}.\]

必须：

• 先绑定所有 tuple columns，后采样 $\theta$；
• 保持 query/table 列的顺序和 arity 完全一致；
• 多 tables 可加入 table-id/tag 作为额外一列；
• selector-disabled rows 使用协议规定的 dummy tuple，不能随意填零。

压缩后，核心语义化为单列 set membership；具体协议再通过复制 table values、multiplicity columns 或辅助排列，把它归约为某个 multiset equality。

3. Set membership 与 multiset equality

设 query vector

\[f=(f_0,\ldots,f_{m-1})\]

和 table

\[t=(t_0,\ldots,t_{N-1}).\]

目标是

\[\forall i,\quad f_i\in\{t_j\}_j.\]

这里的目标首先是逐项 set membership，不是按原 table multiplicity 定义的 multiset inclusion。query 可以重复使用同一个 table value；例如 table 只列一次 8，而 query 查询两次 8，通常仍应合法。为使用乘积恒等式，lookup argument 会复制/重排 table entries，或引入 multiplicity $m_j$，把上述 membership 语义转换成两个构造出来的 multisets 相等。

转换后的基本恒等式是：

若两个长度相同的 multisets $A,B$ 相等，则对形式变量 $X$

\[\prod_{a\in A}(X-a) = \prod_{b\in B}(X-b).\]

在随机 $X=\gamma$ 检查，可把大集合相等压成一个乘积等式。PLONK permutation 与多种 lookup 都由这个思想演化。

membership 比 equality 多一个难点：table 中未被查询的元素允许缺席，query 中同一 table value 又可重复任意次。排序拼接和 multiplicity columns 正是为补上这层语义差异，而不能直接声称原 query multiset 被原 table multiset 包含。

4. Plookup：排序后的拼接

Plookup 的主要对象：

• query $f$；
• table $t$；
• 把 $f$ 与 $t$ 拼接后，按 table 中的顺序排序得到 $s$。

若每个 $f_i$ 都属于 table 所表示的集合，则 $s$ 中相邻位置只有两种情况：

1. 重复同一个值；
2. 沿 table 顺序从 $t_j$ 前进到 $t_{j+1}$。

例如

\[t=(1,4,8),\qquad f=(8,1,8),\]

排序拼接可为

\[s=(1,1,4,8,8,8).\]

4.1 只检查相邻差分为什么不够

序列

\[s'=(1,5,5,5,8,8)\]

也可能拥有与 table 类似的非零差分集合，却包含非法值 5。必须同时绑定相邻 pair 的顺序，而不只是差值。

4.2 randomized adjacent pairs

Plookup 使用随机 $\beta,\gamma$ 压缩相邻 pair。为简化，假设 query/table 都 padding 到长度 $n$，$s$ 长度 $2n$。核心 product identity 形如

\[\begin{aligned} &(1+\beta)^n \prod_{i=0}^{n-1}(\gamma+f_i) \prod_{i=0}^{n-2} \bigl(\gamma(1+\beta)+t_i+\beta t_{i+1}\bigr)\\ &\qquad= \prod_{i=0}^{2n-2} \bigl(\gamma(1+\beta)+s_i+\beta s_{i+1}\bigr). \end{aligned}\]

右边每个相邻 pair：

• 若 $s_i=s_{i+1}=f_j$，factor 可与左侧 query factor 及 $1+\beta$ 对应；
• 若 $(s_i,s_{i+1})=(t_j,t_{j+1})$，factor 与 table-transition 对应。

随机 $\beta$ 绑定 pair 的顺序，$\gamma$ 把 multiset factors 随机平移。

4.3 从大乘积到 grand product

长度 $2n$ 的 $s$ 常拆成两个 degree-$<n$ polynomials $h_1,h_2$。prover 再构造 accumulator $Z$，逐行更新“左侧 factors / 右侧 factors”，约束：

• $Z$ 的局部 recurrence；
• 起点为 1；
• 终点为 1；
• $h_1,h_2$ 的边界拼接连续；
• sorted rows 与原 query/table commitments 的 product relation。

挑战顺序是可靠性的组成部分。$h_1,h_2$ 由 query/table 决定，但必须在用于检验其 randomized product identity 的 $\beta,\gamma$ 产生前承诺；随后才根据这些挑战构造并承诺 $Z$：

\[\operatorname{commit}(f,t,h_1,h_2) \longrightarrow(\beta,\gamma) \longrightarrow\operatorname{commit}(Z).\]

固定 table 的 commitment 可以预先进入 VK，但 dynamic table 仍必须在这条 transcript 边界之前绑定。若先泄露 $\beta,\gamma$，prover 就可能针对单个随机点适配辅助排列，而不必绑定一个真正的 sorted concatenation。

flowchart LR
    F["queries f"] --> C["concat(f,t)"]
    T["table t"] --> C
    C --> S["按 table 顺序排序为 s"]
    S --> H["拆成 h_1,h_2"]
    H --> HC["承诺 h_1,h_2"]
    HC --> BG["采样 β,γ"]
    BG --> Z["构造并承诺 grand product Z"]
    Z --> V["PLONK vanishing argument"]

verifier 不检查 prover 用哪种排序算法；它检查上述 randomized identity。若 identity 成立，除小概率碰撞外，$s$ 必须具有所需结构。

5. Halo 2 的 subset argument

Halo 2 Book 描述的 lookup 与 Plookup 目标相同，但辅助排列不同。记：

• $A$：query column；
• $S$：table column；
• $A’,S’$：prover 提供的排列；
• $Z$：证明 $(A’,S’)$ 分别是 $(A,S)$ 的排列 accumulator。

一个简化的 permutation rule：

\[\begin{aligned} Z(\omega X) \cdot(A'(X)+\beta) \cdot(S'(X)+\gamma) = Z(X) \cdot(A(X)+\beta) \cdot(S(X)+\gamma). \end{aligned}\]

这里也不能只承诺原始 $A,S$。正确依赖是先承诺 prover 生成的辅助排列 $A’,S’$，再采样 $\beta,\gamma$，最后构造并承诺 accumulator $Z$：

\[\operatorname{commit}(A,S,A',S') \longrightarrow(\beta,\gamma) \longrightarrow\operatorname{commit}(Z).\]

$A,S$ 若是 tuple expressions，tuple-compression challenge $\theta$ 还必须晚于组成它们的原始 columns commitments；不同挑战承担不同绑定职责，不能合并成一个“任意随机数”。

排列后要求每个 $A’_i$：

• 要么等于本行 $S’_i$；
• 要么等于上一行 $A’_{i-1}$。

多项式约束：

\[\bigl(A'(X)-S'(X)\bigr) \bigl(A'(X)-A'(\omega^{-1}X)\bigr)=0,\]

并在第一行加

\[L_0(X)\bigl(A'(X)-S'(X)\bigr)=0.\]

5.1 归纳直觉

• 第一行 query 必须与一个 table value 相等；
• 后续若 query 改变，必须重新与本行 table value 相等；
• 若不改变，可重复前一个合法 query；
• $A’$ 是 $A$ 的 permutation，所以所有原 queries 都被覆盖。

flowchart TB
    R0["A'_0 = S'_0"] --> R1{"下一行 A'_i"}
    R1 -->|"等于 A'_(i-1)"| REP["重复已合法值"]
    R1 -->|"不相等"| NEW["必须 A'_i = S'_i"]
    REP --> R1
    NEW --> R1

5.2 tuple、tags 与 expressions

Halo 2 把多列以随机 $\theta$ 压缩为一列；query 可以是 column rotations 的表达式，不一定先物化为 advice column。多张 table 可加入 tag column。固定 table commitments 可在 key generation 时预计算。

5.3 blinding rows

最后若干 rows 用随机值实现 ZK，就不能继续强制 lookup recurrence。Halo 2 使用 $q_{\mathrm{last}},q_{\mathrm{blind}}$ 关闭 usable-domain 外的约束，并单独处理 $Z$ 的末端为 0/1 等 completeness 条件。把理论简化版直接套到这些 rows 会破坏 perfect completeness 或 ZK。

6. LogUp：对乘积取对数导数

设 query multiset 为 ${a_i}$，distinct table values 为 ${t_j}$，每个 table value 被查询 $m_j$ 次。multiset equality 是

\[\prod_i(X-a_i) = \prod_j(X-t_j)^{m_j}.\]

对形式多项式取 logarithmic derivative：

\[\frac{P'(X)}{P(X)} = \sum_i\frac1{X-a_i}.\]

于是得到

\[\boxed{ \sum_i\frac1{X-a_i} = \sum_j\frac{m_j}{X-t_j} }\]

这就是 LogUp 的核心。它用一个 table multiplicity column $m_j$ 代替显式排序后的巨大拼接。

6.1 在随机挑战点评估

commit queries 与 table multiplicities 后采样 $\gamma$，检查

\[\sum_i\frac1{\gamma-a_i} -\sum_j\frac{m_j}{\gamma-t_j} =0.\]

若两个 rational functions 不同，它们只在有限多个 $\gamma$ 上偶然相等。挑战通常放在安全扩域，且需处理 $\gamma=a_i$ 或 $t_j$ 的小概率退化。

6.2 特征不回绕与扩域的不同职责

上述推导在有限特征下还有一个不能省略的前提。若基域 characteristic 为 $p$，multiplicity 在代数约束中只表示模 $p$ 的值；例如

\[\frac{p}{X-t}=0 \qquad\text{in characteristic }p.\]

因此“非法次数”和“合法次数”若相差 $p$，LogUp 倒数和无法区分它们。更直接地，$(X-t)^p$ 的形式导数在 characteristic $p$ 中为零，所以不能不加条件地从 logarithmic derivatives 相等推出原 characteristic polynomials 相等。

协议必须给 multiplicities 一个整数高度上界并在 AIR 中约束每行 count 遵守它。一个通用充分条件是总查询次数上界 $M_{\max}<p$。在多个 AIR/bus 的记号中，若第 $i$ 个 AIR 有 $h_i$ 行，每行查询 count 的绝对值上界为 $w_i$，可使用 Plonky3 当前检查的条件

\[\boxed{ \sum_i w_i h_i<p }.\]

这保证任何 table entry 的诚实 multiplicity 都不可能绕过 characteristic。只在 host 端声明 $w_i$ 还不够：AIR 必须实际约束 selector/count 的布尔性、范围或互斥性，使每行确实满足该 bound。

把 $\gamma$ 放进扩域 $\mathbb F_{p^k}$ 扩大的是随机挑战空间，可降低 tuple fingerprint collision、错误 rational identity 的根事件以及 denominator 命中零的概率；但

\[\operatorname{char}(\mathbb F_{p^k})=p,\]

所以扩域完全不能修复 multiplicity wrap。两类职责必须同时满足，不能用“挑战在大扩域”替代 $\sum_iw_ih_i<p$。

6.3 如何变成低次约束

为 query denominator 加 inverse witness

\[u_i(\gamma-a_i)=1,\]

为 table denominator 加

\[v_j(\gamma-t_j)=1.\]

然后检查

\[\sum_i u_i-\sum_jm_jv_j=0.\]

在 AIR/flat AIR 中可用 running-sum columns：

\[R_{i+1}=R_i+\frac{p_i}{q_i},\]

把每行 fractions 局部累计，最终各 components 的 claimed sums 相消。

flowchart LR
    Q["queries a_i"] --> F1["fractions 1/(γ-a_i)"]
    T["table t_j + multiplicity m_j"] --> F2["fractions m_j/(γ-t_j)"]
    F1 --> S["running sums / sumcheck"]
    F2 --> S
    S --> Z["总和为 0"]

6.4 LogUp 的优势与代价

优势：

• 不需要对 query+table 做排序；
• 多 columns / components 可共享 lookup challenge；
• table multiplicities 对大量重复查询很自然；
• 很适合 STARK/flat AIR 的多表连接。

代价：

• 每个 denominator 需要 inverse relation 或 batch fraction machinery；
• 小字段通常需要扩域 challenge 来压低随机碰撞概率；
• 另须独立证明 multiplicity height 不到 characteristic，扩域不会消除 field wrap；
• 重复 table entries 的 multiplicity 归属需要明确规则；
• 多组件 terminal sums 的绑定与 correlated soundness 需要正式分析。

S-two 的 lookup 体系使用 LogUp 风格连接 components 和预处理表。

7. Plookup 与 LogUp 是同一恒等式的两种视角

设

\[P_A(X)=\prod_i(X-a_i),\qquad P_T(X)=\prod_j(X-t_j)^{m_j}.\]

• Plookup/permutation 风格直接证明 $P_A=P_T$，通过 grand product 局部化；
• LogUp 证明

\[\frac{P_A'}{P_A} = \frac{P_T'}{P_T}.\]

在第 6.2 节的 total multiplicity $<p$ / no-wrap 前提下，若两边都是首一且 degree/常数关系正确，对数导数相等才意味着两个多项式只差常数，进而相等。若允许 degree 达到 $p$，对数导数还会丢失 $p$ 次幂信息，不能只靠首一性完成这一步。协议还需约束总 multiplicity/边界来消除常数与 degree 歧义。

这是很有用的统一视角：

flowchart TB
    M["multiset equality"] --> P["characteristic polynomial<br/>乘积相等"]
    P --> G["grand product<br/>Plookup / permutation"]
    P --> D["logarithmic derivative<br/>LogUp"]

8. Range check 的实际构造

8.1 一个 byte

证明

\[0\le b<256\]

只需 lookup

\[b\in\{0,1,\ldots,255\}.\]

8.2 32-bit word

分解

\[x=b_0+2^8b_1+2^{16}b_2+2^{24}b_3,\]

对四个 $b_i$ 做同一个 byte table lookup，再用一条线性约束重组。也可用 running sum：

\[z_{i+1}=\frac{z_i-b_i}{2^8}, \qquad z_0=x,\quad z_4=0.\]

若只做重组而没查 $b_i$ 范围，prover 可用任意字段元素伪造“字节”。

即使四个 byte lookup 都成立，上式首先仍是字段等式。要把 $x$ 当作一个唯一的无符号 32-bit 整数，还要保证 canonical integer embedding 不发生模 $p$ aliasing。若

\[p>2^{32}-1,\]

且 $x$ 也被约束为这四个 bytes 的 canonical 重组，则右侧落在 $[0,2^{32}-1]$，字段等式唯一对应所需整数。若 $p\le2^{32}-1$，一个 base-field element 根本不能无歧义承载所有 u32：相差 $p$ 的整数会映到同一个字段元素。此时应把 32-bit word 保持为多个 limbs，并对 carries/borrows 与每个 limb 的范围做约束，或使用有完整 range/no-wrap 证明的 non-native representation。

running-sum 里的除以 $2^8$ 也是乘以字段逆元，不会自动获得整数整除语义；byte range、端点 $z_4=0$ 以及上述表示范围必须联合成立。

8.3 为什么不直接 bit-decompose

32 个 bits 每个需

\[b_i(b_i-1)=0\]

和重组约束。lookup 可以用更少 rows/constraints，但 table materialization、lookup auxiliary columns 和 PCS openings 也有固定成本。小电路或少量 range checks 未必 lookup 更划算。

9. Custom gates 与 lookup 的取舍

方法	适合	主要代价
普通乘加门	稀疏、简单算术	rows 多
high-degree custom gate	固定代数关系、频繁复用	quotient degree 增大
小表 lookup	range、XOR、小 S-box	table rows + lookup argument
LogUp 多表	zkVM components、重复查询	inverse/running-sum columns
大表专用 argument	巨型固定/结构化 table	preprocessing、PCS/sumcheck 复杂度

最优设计常混合：custom gate 处理代数核心，lookup 处理范围/位操作，permutation/LogUp 连接跨区域数据。

10. Caulk、Caulk+ 与 Baloo：table 很大时

Plookup/Halo 2 lookup 的 prover 通常至少线性处理 table。若 table 有 $N=2^{32}$ 项、实际只有 $m$ 次查询，无法物化全部表。

10.1 Caulk

Caulk 基于 position-hiding vector commitment 和 table preprocessing。论文给出的 batch membership prover 复杂度为

\[O(m^2+m\log N),\]

proof 常数级、verifier 约 $O(\log\log N)$，代价是 table 的 $O(N\log N)$ 预处理与 $O(N)$ 存储。

10.2 Caulk+

Caulk+ 简化子协议，使在线 prover 的渐近成本去掉对 $N$ 的依赖，仍需相应预处理/commitment 假设。

10.3 Baloo

Baloo 目标是 prover 对 query 数近线性且与 table size 独立，并支持 commit-and-prove subtable。它适合大固定表，但使用的 SRS、pairing/vector commitment、预处理和实现成熟度要单独评估，不能只按渐近式替换 Halo 2 lookup。

11. Lasso 与 Jolt：利用结构化巨表

Lasso 面向 indexed lookup：

\[a_i=T[b_i].\]

其核心使用 sparse multilinear polynomial commitments 与 sumcheck。可把关系理解为：

\[M\mathbf t=\mathbf a,\]

其中 $M$ 每行是一个 one-hot vector，选择 table 的一个位置。对 decomposable table，Lasso 可避免与完整 table size 线性相关的成本。

Jolt 用它把 ISA 指令执行主要表达成对巨大但结构化指令表的 lookup。理论 table 甚至可远大于可物化范围；高效性来自 table function 的 decomposition，而不是实际生成所有 rows。

Lasso 属 multilinear/sumcheck 路线，可与 PLONKish/R1CS SNARK 组合，但数学和 Plookup 的单变量排序 grand product 不同。

12. 方案比较

方案	是否排序	table 成本直觉	polynomial 空间	典型强项
Plookup	是，排序拼接	至少线性 table	单变量	PLONKish 通用 lookup
Halo 2 subset	排列 + adjacency	至少线性 table	单变量	expressions、tags、动态表
LogUp	否	table multiplicity 线性	单变量/多变量均可适配	多表 AIR、重复查询
Caulk/Baloo	否	重预处理，在线次线性/独立	commitment-specific	巨大固定表
Lasso	否	利用稀疏/可分解结构	multilinear	巨型结构化 table、zkVM

这里的“线性”没有说明 field ops、group ops、hashes 与 memory 的常数。真实选型必须看完整 stack。

13. Lookup 的 zero-knowledge

lookup auxiliary data 可能泄露：

• sorted queries $s$ 直接暴露 witness 分布；
• multiplicity column 暴露每个 table value 使用次数；
• accumulator evaluations 可能形成 witness 的函数；
• query 启用模式可能泄露控制流。

ZK 版本需要：

• 对 auxiliary polynomials 加合法 blinding；
• reserved rows / dummy lookups；
• commitment hiding 或 protocol-level masking；
• 模拟 sorting/multiplicities/openings 的联合分布。

仅对原 advice columns 盲化，而不盲化 lookup permutations/multiplicities，并不足够。

14. 边界与常见陷阱

1. tuple-compression challenge 是否在所有 tuple columns commitments 后？
2. table/query 的列顺序、tag、selector 与 padding dummy 是否一致？
3. sorted concatenation 的两半边界是否约束连续？
4. grand product 是否同时约束起点、末端与 recurrence？
5. Halo 2 adjacency 的第一行 base case 是否存在？
6. blinding rows 上 lookup constraints 是否正确关闭并有末端条件？
7. LogUp denominator 为零时的 completeness 处理是什么？
8. multiplicity 是否可能在字段 characteristic 下 wrap，table duplicates 如何解释？
9. fixed table preprocessing 是否绑定到正确 VK/version？
10. dynamic table 是否也被承诺并纳入 challenge transcript？
11. lookup argument 是否隐藏 sorted values / multiplicities？
12. 大表方案的 SRS/storage/preprocessing 是否被 benchmark 遗漏？

15. 自测

1. 为什么随机 tuple compression 要晚于 column commitments？
2. 对 $t=(1,4,8)$、$f=(8,1,8)$ 构造一个合法 sorted concatenation。
3. 用归纳法证明 Halo 2 adjacency rules 使每个 $A’_i$ 属于 $S’$。
4. 从 characteristic polynomial equality 推导 LogUp 倒数和。
5. 为 16-bit range check 设计 byte lookup + reconstruction。
6. 什么时候高次 custom gate 可能比 lookup 更便宜？

参考

• Gabizon、Williamson，Plookup
• Halo 2 Book：Lookup Argument
• Haböck，Multivariate Lookups Based on Logarithmic Derivatives
• Plonky3 lookup：multiplicity height/no-wrap 检查
• Zapico 等，Caulk
• Zapico 等，Baloo
• Setty、Thaler、Wahby，Lasso
• Arun、Setty、Thaler，Jolt
• Starknet S-two Book：Lookups

---

上一篇：PLONK 完整协议 · 下一篇：STARK 执行轨迹与 AIR / ALI · 返回：总目录