Plonkup中Hash函数设计

本文主要介绍如何结合Plonk的数值电路和 looup 门电路 以最小的约束条件实现Hash函数。

电路示例

通过Blake2 hash中32位word 异或XOR 操作，来展示如何使用 Plonkup 设计电路。

查找表

对于XOR查找表，表中的每一行为： 。 对于32位，查找表需要穷举 和 所有可能的值，查找表需要 行.

为了减少行数，可以将 和 拆成分别拆成四个8位的，则查找表变成 行。

电路

对于32位的XOR操作，需要将32位拆成4个8位的数，即：

计算四个8位的XOR操作，即： ，这四个XOR 门电路为：

然后将结果组合起来，得到最终32拉的结果。先定义一个加法门电路：

用以约束：

然后对位组合的加法门电路即为：

位旋转

对于 ， 其中 和 分别为 和 位，

向左旋转 位，可以得到 ， 可以将 和 分别表示为域中元素，则得到：

，

对于7位的旋转，证明者需要计算：

为了保证 的长度为32位，证明者需要拆分 为8位的块： ， , 通过查找表验证其位长度小于8位，即：

通过以下3个加法门验证8位块计算的准确性：

整合所有约束

采用 8位XOR查找表，对于表达式 ， 其中 分别为32位，可以通过14个约束条件表示：

R1CS 比较

R1CS 优势在于可以在一个约束中，允许无限多的加法操作，缺点在于不支持查找表。对于上面的示例，R1CS 约束需要97个约束条件，Plonkup只有其1/7的门电路。

缺点

查找表会增加证明的计算负担和证明尺寸，对于8位XOR查找表， 已经相当大，若改为4位查找表，则会增加约束条件到26个。

参考

https://anoma.network/blog/hash-functions-in-plonkup/