Plonkup中的哈希函数
深入分析 Plonkup 证明系统中哈希函数的选择和优化，提升证明生成效率。
目录
# Plonkup: Plonk + Plookup
> 对证明系统进行快速概述，并展示如何编写一个电路，该电路计算常见哈希函数的一个小部分，并且通过在算术门的同时加入查找功能，能显著提高效率。
引言
Plonkup 是一个结合了 Plonk 和 Plookup 的新型零知识证明系统，允许 Plonk 的算术门和自定义门与 Plookup 启用的查找门共存。像哈希函数这样昂贵的 zk-SNARK 电路组件，可以通过结合查找和算术来更高效地表达。在本文中，我将快速概述证明系统，并展示如何编写一个电路，该电路计算常见哈希函数的一个小部分，并且通过在算术门的同时加入查找功能，能显著提高效率。
Plonk
Plonk 是由 Gabizon、Williamson 和 Ciobotaru 在 2019 年首次提出的证明系统，它允许进行通用、可更新的可信设置。可信设置是公共数据，在多方计算“仪式”中创建，可用于生成和验证证明。它被称为可信，因为如果所有创建者串通一气，设置就可能被破坏。（如果即使有一个参与者是诚实的，那么设置就是安全的）。
普适性意味着单个可信设置仪式可以被任何特定尺寸以下的电路使用。没有这个特性，每个电路都需要执行一个新的仪式。
可更新性意味着现有的可信设置可以在新的仪式中更新，可能包含新的参与者，只要在任何更新中至少有一个参与者是诚实的，它就是安全的。
这两个特性解决了 zk-SNARK 可信设置中最常见的安全问题，并使合谋变得非常困难。
Plonk 与其他大多数证明系统一样，使用算术电路来表示计算。算术电路使用两个门，$+$和$×$，来表达电路中执行的所有操作。复杂的计算需要许多许多的门来表示，并且可能需要相当长的时间来证明。某些操作，如加密哈希函数中常用的位运算，无法以非常高效的方式表示为算术电路。使用多个哈希函数的电路可以增长到非常巨大的规模，并可能需要几分钟来证明。（这个瓶颈适用于任何使用算术门的证明系统，而不仅仅是 Plonk。）
Plonk 的电路包含两个主要部分：算术门和复制约束。算术门可以通过单个多项式约束轻松检查。复制约束将算术门连接在一起，用于构建一个排列多项式，该多项式可以一次性检查所有复制约束的有效性。
Plookup
Plookup 是 Gabizon 和 Williamson 提出的一种证明系统，与 Plonk 非常相似，但它摒弃了算术电路，而是可以用来证明列表中的每个查询元素是否存在于公共查找表中。
Plookup 不使用算术门，但它有自己的排列多项式，用于检查查找查询是否合法。
通过查找，像范围证明和按位操作这样作为算术电路效率低下的操作，会变得高效得多。
为什么要结合两个协议？
电路中的门数是创建证明所需时间的一个主要因素。我们可能希望在电路中使用的一些操作，根据方法的不同，可以用更少的门来表示。
以异或为例。我们希望在电路中建模的许多加密哈希函数，如 SHA 或 Blake，大量使用异或。要展示三个 8 位值 $a,b$ 和 $c$ 如何使用 Plonk 算术门仅满足 $a oplus b = c$ ，你首先需要使用 16 个门来约束每个输入位，然后使用 8 个更多门执行 8 次单比特异或操作，再使用额外的 7 个门将结果位重新打包，总共需要 31 个门来处理每个异或。
使用一个秩 1 约束系统（R1CS）在这种情况下稍好一些，因为无限加法我们可以用单个秩 1 约束替换最后的 7 个门，总共得到 25 个约束。
然而，使用 Plookup 和一个 8 位的 XOR 查找表，这可以在一个门内完成。
有些其他操作，比如嵌入椭圆曲线上的点加法，仅使用算术门就已经相当高效。为了最大化效率，我们希望在同一电路中使用查找门和算术门。
Plonkup 电路
一个 Plonkup 电路由几个部分组成。
- •线是包含证明者私输入的向量。线可以看作是大型矩阵的列。在这些示例中，我们将使用三条线，分别称为 $a, b$ 和 $c$ 。
- •在这个矩阵中，一行是一个必须满足该行所启用的任何约束的私有输入的元组。
- •选择器是控制每行约束开启或关闭的向量。乘法选择器中索引 47 的 1 表示第 47 行必须满足一个乘法约束，例如 $a_{47} cdot b_{47} = c_{47}$ 。
- •复制约束是简单的方程式，将一行中的条目值与另一行中的值联系起来，比如 $c_1 = a_9$ 。
- •最后，查找表是另一个矩阵，其列数与证明者拥有的线数相同。一个有三列的查找表可以模拟一个具有两个输入和一个输出的函数。模拟函数 $f$ 的查找表中第 $(r, s, t)$ 行意味着 $f(r, s) = t$ 。
一个示例电路
让我们展示如何构建一个小型的 Plonkup 电路，使其能执行有用操作。在 Blake2 哈希算法中，32 位字彼此进行异或操作，并将结果位旋转若干位置。这是一个作为 Plonkup 电路小示例的完美操作。
查找表
由于我们的表模拟异或操作，查找表的有效行将看起来像 $(a, b, a oplus b)$ 。我们需要遍历 $a$ 和 $b$ 的所有可能性。如果 $a$ 和 $b$ 每个都是 32 位，我们将得到一个包含 $2^{32} imes 2^{32}$ 行的查找表。每一行有三个条目，每个条目是某个椭圆曲线标量场的元素，通常为 256 位或更大。对于 256 位条目，我们的表将是瘦削、合理、完全不会打破宇宙的 1.5 泽字节。
所以我们需要让表稍微小一点。让我们将 $a$ 和 $b$ 使用 8 位，这样我们得到的表将有 $2^{16}$ 行，总大小仅为 6 兆字节。如果我们用十进制整数来代替 256 位标量场元素以方便起见，表中的一行示例将是 $(13, 255, 242)$ 。