基于Plookup实现Sha256和Keccak

1. 引言

在AztecProtocol的 Barretenberg 中，基于plookup table实现了Sha256 constraint system，该plookup table针对的为：

• majority function： m a j ( x , y , z ) = ( x ∧ y ) ⊕ ( x ∧ z ) ⊕ ( y ∧ z ) maj(x,y,z)=(x\wedge y)\oplus (x\wedge z)\oplus (y\wedge z) maj(x,y,z)=(x∧y)⊕(x∧z)⊕(y∧z)
• choose function： c h ( x , y , z ) = ( x ∧ y ) ⊕ ( ¬ x ∧ z ) ch(x,y,z)=(x\wedge y)\oplus (\lnot x\wedge z) ch(x,y,z)=(x∧y)⊕(¬x∧z)

2. majority plookup table xyzmaj(x,y,z)x+y+z0000000101010010111210001101121101211103 3. choose plookup table xyzchoose(x,y,z)x+2y+3z0000000113010020111510001101041101311116 4. 抽象

将2和3中的plookup table中的第4列中的majority和choose函数 统一抽象为logical 函数 l o g ( x , y , z ) log(x,y,z) log(x,y,z)，将最后一列的运算抽象为algebraic encoding函数 a l g ( x , y , z ) alg(x,y,z) alg(x,y,z)。 目标为，寻找transformation f f f 实现 a l g → l o g alg\rightarrow log alg→log。

详细的抽象思路为：

• 1）对于所有的arguments c c c in ( x , y , z ) (x,y,z) (x,y,z)，由二进制 c = ∑ c i 2 i c=\sum c_i2^i c=∑ci​2i表示 转为 由sparse c s p a r s e = ∑ c i b i c_{sparse}=\sum c_ib^i csparse​=∑ci​bi表示，其中 b b b用于防止algebraic encoding函数中的值溢出即可，如对于majority函数，可令 b = 4 b=4 b=4；而对于choose函数，可令 b = 7 b=7 b=7。 实际实现时，可将 c c c split为合适size的chunks，来mapping each chunk to sparse representation separately (通过查表实现)，然后take linear combination of transformed chunks。
• 2）不再直接对 ( x , y , z ) (x,y,z) (x,y,z)进行逻辑运算，而是对其sparse encodings ( x s p a r s e , y s p a r s e , z s p a r s e ) (x_{sparse}, y_{sparse}, z_{sparse}) (xsparse​,ysparse​,zsparse​)进行algebraic操作。对于majority和choose，其algebraic operations仅为简单的linear combinations，仅需一个single PLONK gate即可实现。
• 3）normalization：将结果有sparse form转换为binary form，即将each chunk [ 0 ; b − 1 ] [0;b-1] [0;b−1] map为 { 0 , 1 } \{0,1\} {0,1}，通过上面定义的one-to-one f f f 函数即可实现。

以上抽象，可在两个维度实现更紧凑的constraint systems：

• 1）减少所使用的table数量：由为每个基础逻辑操作（如 ∧ , ¬ , ⊕ \wedge,\lnot,\oplus ∧,¬,⊕等）定义不同tables，改为，仅需定义2个table——一个用于将number转换为sparse form，另一个用于将sparse from转换为number。
• 2）可减少所需用到的gate总数。

不过，以上抽象对事情进行了简化。实际Sha256 hash运算中包含了复杂的逻辑运算和circular rotations。以上抽象适于表达复杂的逻辑运算，但是不适于表达circular rotations。

AztecProtocol的 Barretenberg 中，为了解决circular rotations运算，引入了几种不同的tables来做rotation and convertion to sparse form in one fell swoop。该策略适于（尽管仍然不太理想）当Sha256中the number of different rotation moduli is rather small，但是当用于Keccak时有严重的障碍，因为在Keccak中要求each of 25 lanes is shifted by unique modulus。

sparse algebraic encoding for x x x in base b b b 表示为： x = ∑ i n x i b i x=\sum_{i}^{n}x_ib^i x=∑in​xi​bi 其中每个 x i ∈ [ 0 , c − 1 ] x_i\in[0,c-1] xi​∈[0,c−1]。 事实上，对 b b b的选择仅限制要求： all separate chunks x i x_i xi​ should be uniquely decodable and retrieved from x x x，即： map ( [ 0 , c − 1 ] × n ) → F : ( x 0 , ⋯   , x n ) → ∑ i n x i b i ([0,c-1]\times n)\rightarrow \mathbb{F}:(x_0,\cdots,x_n)\rightarrow \sum_{i}^{n}x_ib^i ([0,c−1]×n)→F:(x0​,⋯,xn​)→∑in​xi​bi 为injective。

最简单的方式是选择 b = c b=c b=c，但实际上，可令 b = c + 1 b=c+1 b=c+1或 b = 2 c b=2c b=2c等等，只要 x = ∑ i n x i b i x=\sum_{i}^{n}x_ib^i x=∑in​xi​bi 不会wrap around modulus p p p of field F \mathbb{F} F。 但是，若令 b = g b=g b=g， g g g为root of unity of order n n n，尽管其会force x x x wrap around p p p（从而不满足injective条件），但是却对rotations超级友好： g n = 1 , g i ≠ 1 , ∀ i < n g^n=1,g^i\neq 1, \forall i