ZKSwap团队解读Plookup原理Ⅰ

最近的的一条新闻引起了 ZKSwap 团队的注意——Zcash 表示将在最近的升级版本中引入 Halo2，一个不需要可信设置的 ZKP 算法，不仅具备较高的性能，而且还为隐私支付提供了可扩展的架构。因垂丝汀！那就让我们来研究研究到底算法到底是怎么设计的。

原来，一开始这个算法叫 Halo，采用的 Sonic 算法里提到的 polynomial IOP 方案，在此方案的基础上实现了 recursive proof composition without a trusted setup。但是，Zcash 团队发现，它还不够快，应该寻找一个更快的 polynomial IOP 方案来替代之，比如 Marlin? Plonk?

效率最好的应该属于 Plonk 了，并且它赋予了“基于特定应用需求设计高效实现”的巨大灵活性，这对于开发一个更高效的 Halo 版本至关重要。在研读 Halo2 设计说明书时，看到了这句话 “The arithmetization used by Halo 2 comes from?PLONK, or more precisely its extension UltraPLONK that supports custom gates and lookup arguments. We'll call it?UPA?(UltraPLONK arithmetization).”

果然，没有最有效，只有更有效。

“Halo2 uses the following lookup technique, which allows for lookups in arbitrary sets, and is arguably simpler than Plookup.”

看来，不研究 Plookup，很难了解 Halo2 了。接下面，我们将分两篇文章讲解：

Plookup 的原理

Plookup 能和 Plonk 碰撞出什么火花

Plookup 原理

首先，让我们一下 Plookup 的设计思想：“we precompute a lookup table of the legitimate (input, output) combinations; and the prover argues the witness values exist in this table.”

提前计算一个由有效的(input, output) 组成的 lookup table；

Prover证明 witness 存在这个表里；

看起来 prover 只需要证明合法的 witness 的存在一个预先计算的 lookup table 中，而不是通过电路计算来证明合法的witness存在，如果前者效率更高，那么理论上就可以减少电路的规模。接下来，让我们来剖析一下 Plookup 的具体原理：

概念：

正整数：n, d

向量：f ? Fn, t ? Fd

关系：f ? t ?{fi}i?[n] ? {ti}i?[d]注：t 中的每个元素在f中至少出现一次，t 中无重复元素

循环群：H = {g,…,gn+1 = 1}，阶为 n+1 注：对于多项式 f ? F<n[X], f~i ~= f(gi) f is sorted by t：当f ? t时，f 中的元素顺序和 t 中的一样，即：对于任意 i < i`，满足 fi < fi` 那么：若tj = fi ; tj` = fi`则：j < j`对于：f ? Fn, t ? Fd, s ? Fn+d，定义二元多项式F，G：

F ≡ G 当且仅当：

f ? t 即：t 中的所有元素至少在 f 中出现一次

s is (f, t) sorted by t 即：s 是 f 和 t 的并集，并且 s 里的元素顺序与 t 相同

根据 Schwartz-Zippel 定理，可知只有条件 1, 2 都满足的时候，多项式 F，G 满足：

主要方案：

Preprocessed polynomials: t ? F<n+1[X]， as lookup values

Inputs: f ? F<n[X]

Protocol:

a. 令 s := (f, t) ? F2n+1 sorted by t

b. P 设置多项式 h1,h2 ? F<n+1[X]，满足: h1(i) = si, h2(i) = sn+i i ? [n+1]，并发送给可信第三方 I

c. V 随机选择参数 β、γ，发送给 P

d. P 计算多项式 Z ? F<n+1[X]，形如：

i. Z(g) = 1; ii. For ?2 ≤ i ≤ n Z(gi) =(1 + β)i-1Πj<i(? + fj)Π1≤j<i(?(1 + β) + tj + βtj+1) / Π1≤j<i (?(1 + β) + sj + βsj+1)(?(1 + β) + sn+j + βsn+j+1)

e. P 发送多项式 Z 给 I

f. V 检查 Z，符合以下条件：

i. L1(x)(Z(x) - 1) = 0 ?// 首项为 1 ii. ?(x – gn+1)Z(x) (1 + β)(? + f(x))(?(1 + β) + t(x) + β·t(x·g)) = ? (x – gn+1)Z(x·g)(?(1 + β) + h1(x) + β·h1(x·g))(?(1 + β) + h2(x) + β·h2(x·g)) //在 2 ≤ x ≤ n 范围内确保多项式 Z 的有效形式 iii. ?Ln+1(x)(Z(x) - 1) = 0 // 分子分母所有元素相乘，Z(gn+1) ?= 1 ?f ? t iv. ?Ln+1(x)(h1(x) – h2(x·g)) = 0 // 保证 h1(gn+1) = h2(g) 代表着整个s

扩展到 Vector Lookups

假设，存在多个多项式 f1, f2,…,fw ? F<n[X]，以及一lookup tables t* ? (Fw)d，我们想校验对于任意 j，(f1(j), f2(j),…,fw(j)) ? t*。

大致的过程：

用多项式的形式表示 lookup tables t* := {t1, t2,…tw}

用随机数 a 进行压缩，a 来自 V

用压缩后的 f 和 t 进行 f ? t 的证明，过程如上所示

f ? t ?j ? [n], (f1(j), f2(j),…,fw(j)) ? t*

安全性由 Schwartz-Zippel 保证

扩展到 Multiple Tables

上一小节展示了 多个多项式 f => 1 个 table 的场景，现在考虑下多个多项式 f => 多个 tables 的场景，思想比较简单：

把多个 tables 整合成一个 table

新增一列表示 table 索引，用于指示，对于不同的 i 取值，其多项式集合的值 f 在哪个子表里 如下图所示：

更优的 Range Check

可以观察到的是，如果我们把 lookup tables 里的值设置成连续的值，比如 ti = i -1，那么其实此协议久变成了校验 f ? {0,…d - 1}，证明复杂度仅仅为 5n ?+ 2，假设 d = n + 1。具体的协议这里不在具体描述，如果已经理解上述协议的话，理解这个应该不难。

结语

本文描述了 plookup 的具体原理及思想，下一篇文章，将描述 plookup 到底能给 plonk 提供什么帮助。

—-

编译者/作者：ZKSwap

玩币族申明：玩币族作为开放的资讯翻译/分享平台，所提供的所有资讯仅代表作者个人观点，与玩币族平台立场无关，且不构成任何投资理财建议。文章版权归原作者所有。