PLONKish 体系：置换论证、lookup 与自定义门

Scope. 本文只展开经典三线 PLONK 的 permutation argument 和原始 plookup 的 sorted-table argument。“PLONKish”在这里是行、列、selector 证明面的统称；Halo2 等后继系统采用不同的 lookup、commitment 与 transcript 细节，不能直接套用下文公式。

这一证明面把 witness 排成 rows 和 columns，由 selectors 指定局部门语义，再用 permutation 与 lookup 处理跨位置关系。三类机制回答同一个问题：

当 witness 被排成列多项式之后，系统如何表达“这些列之间哪些值必须相等、哪些值必须属于某张表、以及每一行到底允许执行什么语义”？

下文分别写出 grand product 的边界、交叉相乘恒等式和 quotient 检查，再说明 custom gate 如何改变度数预算。^{1 2}

PLONKish 证明面长什么样

PLONKish 最先改变的，是 witness 的组织方式。

不同于 QAP 那种更“全局插值后一次性消费”的感觉，PLONKish 更像是把 witness 放进若干列，然后在每一行上施加局部代数条件。设评估域为

\[ H = \{\omega^0, \omega^1, \dots, \omega^{n-1}\}. \]

每一列 witness 被插值成列多项式，例如

\[ a(X),\ b(X),\ c(X), \]

它们在点 \(\omega^i\) 上的值，就是第 \(i\) 行对应列的 witness 值。

Rows, Columns, And Selectors

最经典的门约束可以写成

\[ q_M(X)a(X)b(X)+q_L(X)a(X)+q_R(X)b(X)+q_O(X)c(X)+q_C(X)=0 \]

在所有 \(X \in H\) 上成立。

这里：

• \(a,b,c\) 是 witness columns
• \(q_M,q_L,q_R,q_O,q_C\) 是 selector polynomials

selector 多项式决定每一行激活哪些项。

这个 proving surface 可以拆成：

• 列多项式承载 witness
• selector 多项式承载 gate semantics
• 域点逐行承载局部约束

这比纯 QAP 更适合表达现代系统常见的 copy constraints 和 richer gate semantics。

从 copy constraints 到 permutation argument

经典 PLONK 把 copy constraints 改写成 permutation consistency，避免为每一对复用位置增加一条显式等式。

What Copy Constraints Actually Say

在电路或行列布局里，copy constraint 的含义很朴素：

• 某一行某一列的值，应当等于另一行另一列的值
• 一个逻辑变量在不同 gate 位置复用时，所有出现点必须一致

PLONK 把整组“应该相等的位置”编码进一个排列，再一次性检查全局一致性。

Permutation Encoding

设每个位置都带有一个身份标签 id，例如列编号和行编号的组合。copy constraint 指定了一组置换 \(\sigma\)，把“原始位置标签”映射到“应该与之相等的位置标签”。

于是问题从

这些位置两两相等吗？

改写成

witness values 加上位置标签后，原始序列和置换后序列是否表示同一个 multiset？

这就是 permutation argument 的核心转换。

Grand Product Polynomial

令

\[ N_i=\prod_{w\in\{a,b,c\}}\left(w_i+\beta\,\mathrm{id}_{w,i}+\gamma\right), \]\[ D_i=\prod_{w\in\{a,b,c\}}\left(w_i+\beta\,\sigma_{w,i}+\gamma\right). \]

prover 用 grand-product polynomial \(Z_{\mathrm{perm}}(X)\) 累计这些因子。概念上的递推为

\[ Z_{\mathrm{perm}}(\omega^{i+1}) =Z_{\mathrm{perm}}(\omega^i)\frac{N_i}{D_i}. \]

协议检查交叉相乘后的多项式关系，电路里不需要除法：

\[ F_{\mathrm{perm}}(X)= Z_{\mathrm{perm}}(\omega X)D(X)-Z_{\mathrm{perm}}(X)N(X). \]

它应在 \(H\) 上为零，并与边界

\[ L_0(X)\bigl(Z_{\mathrm{perm}}(X)-1\bigr)=0 \]

一起进入 quotient，其中 \(L_0\) 是点 \(1\) 的 Lagrange basis polynomial。跨最后一行回到第一行的递推使全域乘积闭合；若两侧 multiset 相同，累计乘积回到 1。

\(\beta,\gamma\) 在 wire commitments 固定后生成，用来随机压缩“值 + 位置标签”。prover 构造 \(Z_{\mathrm{perm}}\) 时可能遇到某个 \(D_i=0\)；诚实执行在这种情况下 abort 并重新开始。对已承诺的 witness，坏挑战只占有限个域点，概率可用 Schwartz–Zippel 或直接 union bound 控制。verifier 始终检查上面的交叉乘积恒等式，不能把“分母大概率非零”替代为一个未约束的除法假设。

Key Observation. grand product 把全局 copy consistency 压成一个带起点和闭合条件的 witness polynomial。

Why This Matters

permutation argument 将变量复用收缩成：

• 一个排列编码
• 一个 grand-product witness
• 一组 boundary / transition-like 约束

这使得列式 witness layout 和复用变量之间的关系变得非常可扩展。

Lookup：把表成员关系压成 multiset relation

permutation argument 处理位置复用；表成员关系还需要 lookup。典型对象包括：

• range check
• byte decomposition
• 固定 opcode table
• 某种预定义函数关系表

如果不用 lookup，而只靠普通门去表达这些关系，row count 往往会爆炸。

Why Plain Gates Hurt

以 range check 为例。若想证明某个值 \(x\) 在 \([0, 2^8)\) 内，仅用普通低次数门去展开，通常需要很多 bit-decomposition 或 carry constraints。逻辑没错，但门数和列布局压力会很大。

lookup 改为证明：

witness 中的查询值全部出现在承诺的合法表中。

Table Membership As Multiset Equality

原始论文先把 table padding 到 \(n+1\) 个值，把 \(n\) 个查询记为

\[ f_1,\dots,f_n, \]

并把固定表记为

\[ t_1,\dots,t_{n+1}. \]

lookup 把

\[ \{f_i\} \]

属于表的关系重写成 multiset inclusion。具体构造彼此并不通用；下面只写原始 plookup 的核心对象。

prover 按 table 的既定次序排列 \(f\Vert t\)，得到 \(2n+1\) 个值 \(s_1,\ldots,s_{2n+1}\)；重复查询放在对应表项旁边。这里的“排序”来自公开 table order，并未假设有限域自带大小关系。

在 \(n+1\) 点域 \(H'=\{g,g^2,\ldots,g^{n+1}\}\) 上，两列采用带一个重叠点的切分：

\[ h_1(g^i)=s_i, \qquad h_2(g^i)=s_{n+i}. \]

因此 \(h_1(g^{n+1})=h_2(g)=s_{n+1}\)。对 \(i=1,\ldots,n\)，定义

\[ N_i=(1+\beta)(\gamma+f_i) \left(\gamma(1+\beta)+t_i+\beta t_{i+1}\right), \]\[ D_i= \left(\gamma(1+\beta)+h_{1,i}+\beta h_{1,i+1}\right) \left(\gamma(1+\beta)+h_{2,i}+\beta h_{2,i+1}\right). \]

概念上的递推是

\[ Z_{\mathrm{lookup}}(g^{i+1}) =Z_{\mathrm{lookup}}(g^i)\frac{N_i}{D_i}. \]

论文在 \(H'\) 上检查四组条件。用 \(L_1,L_{n+1}\) 表示点 \(g,g^{n+1}\) 的 Lagrange basis polynomials：

\[ L_1(X)\bigl(Z_{\mathrm{lookup}}(X)-1\bigr)=0, \]\[ \begin{aligned} &(X-g^{n+1})Z_{\mathrm{lookup}}(X)N(X)\\ ={}&(X-g^{n+1})Z_{\mathrm{lookup}}(gX)D(X), \end{aligned} \]\[ L_{n+1}(X)\bigl(h_1(X)-h_2(gX)\bigr)=0, \]\[ L_{n+1}(X)\bigl(Z_{\mathrm{lookup}}(X)-1\bigr)=0. \]

因子 \(X-g^{n+1}\) 将终点排除在递推之外，两个 \(L\) 项分别固定 grand product 的起点和终点，第三条等式锁定 \(h_1,h_2\) 的重叠点。省略任一边界都会留下自由度。\(\beta,\gamma\) 产生零分母时采用与 permutation argument 相同的 abort 分析。

上面保留的是 standalone plookup 的原始 \(H'\) 索引。把它嵌入 PLONK 时，协议要把 padding、末行 selectors 与 shift 重新对齐到共享 circuit domain。下文用 \(H,\omega\) 代表已完成这一步的集成版本，不声称原论文的 \(H'\) 可原样与三线 PLONK 拼接。

Plookup Transcript 顺序

把 permutation 与 lookup 放进同一份 Fiat–Shamir transcript，可以看到每个挑战约束什么：

1. transcript 先吸收 circuit、公开输入、固定表 commitments 和 domain separator。
2. prover 承诺 challenge-independent 的 wire columns、查询列 \(f\) 与重排列 \(h_1,h_2\)。
3. transcript 导出各 argument 域分离的 \(\beta,\gamma\)；prover 据此构造并承诺 \(Z_{\mathrm{perm}},Z_{\mathrm{lookup}}\)。
4. transcript 导出组合挑战 \(\alpha\)，prover 构造 quotient polynomial 并承诺其 degree-bounded chunks。
5. 所有 quotient commitments 固定后导出随机点 \(\zeta\notin H\)，打开 \(\zeta\) 和相应 shift 点 \(\omega\zeta\) 处所需的 wire、selector、grand-product 与 quotient 值。
6. 最后的 batching challenge 将同一点或不同点的 PCS opening claims 合并；它必须晚于所有待合并 evaluations。

如果把 \(\beta,\gamma\) 放在 \(h_1,h_2\) 承诺之前，prover 可以针对随机压缩选择排列；如果把 \(\zeta\) 放在 quotient commitment 之前，prover 只需修补一个已知点。transcript 顺序由这些适应性攻击决定。

lookup 会增加列、排序对象、grand product 和 openings。它是否比基础门便宜，要结合 table width、查询次数、quotient degree 与 PCS 成本判断。

从局部恒等式到 Quotient 与批量开点

记门约束为 \(F_{\mathrm{gate}}(X)\)，把 permutation 与 lookup 的递推、起点和末行 selector 项依次记为 \(F_{\mathrm{perm}},F_{\mathrm{pbd}},F_{\mathrm{lookup}},F_{\mathrm{lbd}}\)。在挑战 \(\alpha\) 下形成

\[ F_{\mathrm{all}}(X)=F_{\mathrm{gate}}(X) +\alpha F_{\mathrm{perm}}(X) +\alpha^2F_{\mathrm{pbd}}(X) +\alpha^3F_{\mathrm{lookup}}(X) +\alpha^4F_{\mathrm{lbd}}(X). \]

每一项都应在 \(H\) 上为零，所以

\[ T(X)=\frac{F_{\mathrm{all}}(X)}{Z_H(X)}, \qquad Z_H(X)=X^n-1 \]

应为多项式。若 \(T\) 的度数超过 PCS 的单多项式上限，prover 按 \(X^n\) 分块承诺；验证点处再重组成 \(T(\zeta)\)。实现通常在更大的 coset 上计算 quotient evaluations，以避开 \(Z_H=0\) 的原域点。协议则在所有 commitments 固定后抽取 \(\zeta\)，并拒绝 \(\zeta\in H\)。

verifier 在 \(\zeta\) 处检查

\[ F_{\mathrm{all}}(\zeta)=T(\zeta)Z_H(\zeta), \]

同时需要 \(Z_{\mathrm{perm}}(\omega\zeta)\) 与 \(Z_{\mathrm{lookup}}(\omega\zeta)\) 来核对递推。PCS 最后证明这些 evaluations 确实来自先前承诺的多项式。随机线性 batching 降低 opening 数量，但不会补回漏写的边界 selector，也不会自动保证 quotient 的声明度数；这些条件必须由协议单独约束。

Custom Gates 的度数与布局成本

custom gates 允许一行承载比基础乘加门更丰富的语义。

Packing More Semantics Per Row

比如一个 custom gate 可以在一行里表达：

• 某种特定线性组合
• 一次 range chunk relation
• 一次椭圆曲线加法局部约束
• 一小段 hash round 的局部语义

这会减少总 row 数，因为同样的 computation 被压进更丰富的每行语义里。

Degree, Selectors, And Prover Cost

表达力越强，系统通常要支付以下几类代价：

• quotient polynomial degree 上升
• selector 多项式更复杂
• witness 列布局更紧张
• prover 在构造和开点这些对象时成本更高

因此，custom gate 会直接改变 proving surface 的工程平衡点。

如果一个 gate 设计得太激进，虽然 row count 下降了，但 quotient degree 可能上升，最终导致证明大小、开点复杂度或者实现难度反而更糟。

Why This Becomes A System Design Problem

在更一般的 PLONKish 后继系统中，设计者经常需要权衡：

• advice / fixed / instance columns 怎么排
• 哪些关系值得做 custom gate
• 哪些关系更适合做 lookup
• copy constraints 和 lookup constraints 会不会互相挤压布局

这些选择共同构成约束 DSL 的设计工作。

统一视角：一切都在重写约束接口

现在把这三者放回同一个表面。

Permutation Argument

它处理的是：

不同位置上的值必须是同一个逻辑变量。

实现方式是 permutation encoding + grand product。

Lookup

它处理的是：

witness 值必须属于某个合法表。

实现方式是 multiset relation，常常也会借用 grand-product or sorting machinery。

Custom Gates

它处理的是：

每一行到底允许表达多丰富的局部语义。

实现方式是 selector-polynomial design，加上对 degree / columns / prover cost 的控制。

“PLONKish”的共性在于一套 row/column based proving surface：

• witness 被摆进列
• gate semantics 由 selectors 决定
• copy constraints 由 permutation argument 管
• table membership 由 lookup relation 管
• 系统表达力与 proving 成本由 custom gate 设计压平衡

Scope Boundary. 这套共同词汇不保证后继协议共享同一 grand product、lookup relation、PCS 或安全证明。

Summary

如果只记住 PLONKish 支持 permutation、lookup、custom gates，这还只是 feature list。更有用的总结是：

1. witness surface 被固定成 rows、columns 和 selector polynomials
2. copy constraints 被重写成 permutation relation
3. permutation relation 被压成 grand-product polynomial
4. table membership 被重写成 lookup multiset relation
5. custom gates 决定每一行到底能塞多少语义，并同时改变 degree、布局和 prover cost

工程问题可以表述为：如何设计约束接口，在表达复杂语义的同时控制 quotient degree、列数、FFT 与 PCS opening 成本。

下一篇进入 IPA / Halo / Nova / folding 时，这种“系统设计空间”的感觉还会更强，因为递归和 accumulation 会进一步把 proving surface 从静态约束推向跨 proof-state 的接口设计。

References