PLONK + PLOOKUP

1. 引言

在区块链网络中，交易经年不断积累，因此区块链的存储量不断无限增长。在Dusk Network中，自举时间线性增长，且受零知识证明验证计算量的限制。在适当的时候，这意味着自举可能需要几天甚至几周的时间。

这就是为什么我们正在研究一个全新的自举过程，使加入网络的新节点能够快速与最新状态同步。使用此过程，新节点不需要验证单个交易，这将导致自举时间为分钟/小时，而不是天/周。

为此，Dusk Network中设计了一个过程，使client能将相应交易证明的计算委托给某server，而不暴露相应的secret key。整个委托过程，使得我们能拥有超轻的类似Metamask的钱包，同时能使用协议所提供的所有功能。在具体实现过程中，将设定多个常量，如：

• length of the epoch
• length of the bid/stake lock-up time

Dusk-network团队在PLOOKUP的实现上取得了重大进展，可将现有的gadgets与PLOOKUP集成，减少gadgets中门的数量。同时，Dusk-network团队也将致力于实现新的gadgets，这种新的gadgets必须依赖于PLOOKUP。

PLOOKUP的主要价值在于：

• 可加速现有circuit的proving time；
• 为线下的附加创新特性提供了基础，如recursive proof verification。

PLONK+PLOOKUP用于circuit证明，底层关键技术点涉及有：

• 1）PLONK的核心技术为：grand product check

• 2）PLOOKUP的核心技术为：multiset-equality check

• 3）circuit证明中常用到：permutation check

• 4）PLOOKUP中引入了：Table lookup

接下来将介绍这些底层关键技术之间的关系。

2. Grand product check VS Multiset-equality check

PLONK的核心技术为：

• grand product check

所谓grand product check，是指：

• public info：commitments to polynomials f , g f,g f,g over a finite field F \mathbb{F} F，及 a subset H = { x 1 , ⋯   , x n } ⊂ F H=\{x_1,\cdots,x_n\}\subset \mathbb{F} H={x1​,⋯,xn​}⊂F
• private info：多项式 f , g f,g f,g。
• 待证明relation： ∏ i ∈ [ n ] a i = ∏ i ∈ [ n ] b i \prod_{i\in[n]}a_i=\prod_{i\in[n]}b_i ∏i∈[n]​ai​=∏i∈[n]​bi​，其中 a i = f ( x i ) , b i = g ( x i ) a_i=f(x_i),b_i=g(x_i) ai​=f(xi​),bi​=g(xi​)。

在PLONK论文中指出，当 H H H为a multiplicative subgroup时，可高效实现相应证明。

此文讨论的长为 n n n的vector a ⃗ \vec{a} a ，在协议的实际实现中，均为Prover会对多项式 f f f进行commit，其中 f ( x i ) = a i f(x_i)=a_i f(xi​)=ai​。

PLOOKUP的核心技术为：

• multiset-equality check

借助少量的randomness，可将grand product check 转换为更强大的primitive——the multiset equality check：

• 已知两个vector a ⃗ = ( a 1 , ⋯   , a n ) , b ⃗ = ( b 1 , ⋯   , b n ) \vec{a}=(a_1,\cdots,a_n),\vec{b}=(b_1,\cdots,b_n) a =(a1​,⋯,an​),b =(b1​,⋯,bn​)，check两者是否具有相同的元素，计算相应的重复值，顺序可以不对应。

如 ( 1 , 1 , 2 , 3 ) (1,1,2,3) (1,1,2,3) 与 ( 2 , 1 , 1 , 3 ) (2,1,1,3) (2,1,1,3) 是multiset-equal的，但是与 ( 1 , 2 , 3 , 3 ) (1,2,3,3) (1,2,3,3)或 ( 1 , 1 , 2 , 4 ) (1,1,2,4) (1,1,2,4)都不是 multiset-equal的。

2.1 由 multiset-equality check 到 grand product check

Verifier发送随机值 γ ∈ F \gamma\in\mathbb{F} γ∈F，然后run the grand product check on the randomly shifted vectors a ⃗ ′ = a ⃗ + γ , b ⃗ ′ = b ⃗ + γ \vec{a}'=\vec{a}+\gamma,\vec{b}'=\vec{b}+\gamma a ′=a +γ,b ′=b +γ（即对所有元素都加 γ \gamma γ。）

这样，就可将multiset-equality check转换为 如下grand product check： ∏ i ∈ [ n ] ( a i + γ ) = ∏ i ∈ [ n ] ( b i + γ ) \prod_{i\in[n]}(a_i+\gamma)=\prod_{i\in[n]}(b_i+\gamma) ∏i∈[n]​(ai​+γ)=∏i∈[n]​(bi​+γ)

3. Permutation check VS Multiset check

Permutation是指：

• public info：permutation σ : [ n ] → [ n ] \sigma:[n]\rightarrow [n] σ:[n]→[n]
• private info： a ⃗ , b ⃗ \vec{a},\vec{b} a ,b
• 待证明relation： b ⃗ = σ ( a ⃗ ) \vec{b}=\sigma(\vec{a}) b =σ(a )，即对于每一个 i i i，有 b i = a σ ( i ) b_i=a_{\sigma(i)} bi​=aσ(i)​。

关于为何permutation checks为SNARKs的核心组成，查看PLONK及其它SNARK论文便可知。

3.1 由 permutation check 到 multiset check

观察以下vectors of pairis： ( ( a i , i ) ) i ∈ [ n ] ((a_i,i))_{i\in[n]} ((ai​,i))i∈[n]​ 和 ( b i , σ ( i ) ) i ∈ [ n ] (b_i, \sigma(i))_{i\in[n]} (bi​,σ(i))i∈[n]​

当且仅当 b ⃗ = σ ( a ⃗ ) \vec{b}=\sigma(\vec{a}) b =σ(a )时，以上两者为multiset-equal的。

但是，我们希望可reduce为multiset check on vectors of elements，而不是vectors of pairs。为此，引入随机值 β \beta β，定义新的vector a ⃗ ′ , b ⃗ ′ \vec{a}',\vec{b}' a ′,b ′ 为： a i ′ = a i + β ⋅ i , b i ′ = b i + β ⋅ σ ( i ) a_i'=a_i+\beta\cdot i,b_i'=b_i+\beta\cdot \sigma(i) ai′​=ai​+β⋅i,bi′​=bi​+β⋅σ(i)

若以上vectors of pairs为 not multiset equal的，则大概率 a ⃗ ′ \vec{a}' a ′和 b ⃗ ′ \vec{b}' b ′也不是multiset equal的。 因此，仅需对 a ⃗ ′ \vec{a}' a ′ 和 b ⃗ ′ \vec{b}' b ′ 做multiset check就足够了。

3.2 由 permutation check 到 grand product check

在Stephanie Bayer和Jens Groth 2012年论文《Efficient Zero-Knowledge Argument for Correctness of a Shuffle》中，首次实现了 由permutation check 到 grand product check 的reduction，详细可参看系列博客：

• Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（1）
• Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（2）
• Efficient Zero-Knowledge Argument for Correctness of a Shuffle学习笔记（3）

4. Table lookup VS Multiset check

table lookup 操作是 zk-SNARK实现中的一个非常有用的操作。

以XOR举例，假设有3个vectors of field elements a ⃗ = ( a 1 , ⋯   , a n ) , b ⃗ = ( b 1 , ⋯   , b n ) , c ⃗ = ( c 1 , ⋯   , c n ) \vec{a}=(a_1,\cdots,a_n),\vec{b}=(b_1,\cdots,b_n),\vec{c}=(c_1,\cdots,c_n) a =(a1​,⋯,an​),b =(b1​,⋯,bn​),c =(c1​,⋯,cn​)，想要check： 对于每一个 i ∈ [ n ] i\in[n] i∈[n]， a i , b i , c i a_i,b_i,c_i ai​,bi​,ci​均为8-bit string，且 c i = a i ⊕ b i c_i=a_i\oplus b_i ci​=ai​⊕bi​，其中 ⊕ \oplus ⊕为bitwise XOR。

传统的SNARK方案需要很多arithmetic constraints： 需要对于每一组tuple ( a i , b i , c i ) (a_i,b_i,c_i) (ai​,bi​,ci​)分解为二进制位表示，然后再进行bitwise XOR。

而借助Lookup table，相应的解决方案变为：

• 1）预计算XOR操作对应的truth table T T T。 T T T的长度为： 2 8 ∗ 2 8 = 2 16 2^8*2^8=2^{16} 28∗28=216，包含了3个向量 ( T 1 , T 2 , T 3 ) (T_1,T_2,T_3) (T1​,T2​,T3​)之间的关系。【可将 T T T看成是矩阵，其每行元素为tuple ( T 1 , T 2 , T 3 ) (T_1,T_2,T_3) (T1​,T2​,T3​)，共有 2 16 2^{16} 216行，且其中 ( T 1 , i , T 2 , i , T 3 , i ) (T_{1,i},T_{2,i},T_{3,i}) (T1,i​,T2,i​,T3,i​) 遍历所有可能的输入/输出组合。】相应的结构体设计可为：

/// Construct a Generic lookup table over a bi-variate function
pub struct Generic(HashMap); //以两个输入组合为Key，以输出结果为value

【注意，在SNARK上下文中， a ⃗ , b ⃗ , c ⃗ \vec{a},\vec{b},\vec{c} a ,b ,c 通常对应的是witness polynomials for which only for some i i i's we wish to check a XOR relation。 具体实现可参见PLOOKUP论文section 4.1节的方法： 借助“selectors” 来combine different tables and gates。【借助selectors j j j，实际实现的就是按不同的门类型（不同的逻辑操作）统一归类。】 详细也可参看博客 PLOOKUP 中 “6. 扩展为多个多项式 f 1 , ⋯   , f w ∈ F < n [ X ] f_1,\cdots,f_w\in\mathbb{F}_{