Darlin: 基于Marlin的携证明数据方案

翻译自：https://zkproof.org/2021/09/29/darlin-recursive-proofs/ 

作者：Ulrich Haböck 

译者：Kurt Pan

在这篇博文中，我们描述了Darlin，一个递归 zk-SNARK，我们将使用它来构建Latus侧链，即Horizen的Zendoo^[1]生态里的简洁区块链。

Latus 侧链是可配置的特定用途区块链，用户可以在 Zendoo 主链及其加密货币 ZEN 的帮助下以分布式方式定制和自启动。Latus 侧链带有其当前状态的简洁证明，该证明将由一组精心策划的“SNARKers”（即以ZEN 得到补偿的节点）递归形成。如果您对 Zendoo 生态系统的细节以及 Zendoo 侧链和主链之间如何交换代币感兴趣，可以查看我们关于Zendoo^[2]及其激励机制Latus Incentive Scheme^[3]的论文.

Marlin 是一种用于R1CS的zk-SNARK，Darlin 是 Marlin 的递归友好变体。像许多第二波 SNARK 一样，Marlin 是在任何安全的多项式承诺方案上模块化构建的。我们的设计选择很大程度上受到 Halo 的影响，从中我们学到了很多关于如何限制验证者计算时间，以及如何在没有可信设置的情况下构建高效递归方案的知识。

Darlin方案最重要的基石是：

• 与 Halo 1 和 2 一样，我们使用 “离散对数”多项式承诺方案 ，该方案不需要可信设置，并允许椭圆曲线（例如 Pasta 曲线）普通大小的循环(cycles)。
• 我们使用 Halo 的策略来聚合离散对数的“困难部分”。我们进一步推广了他们的策略，分摊二元多项式的赋值检查到 Marlin 的“内部和校验”中出现的二元多项式的线性组合（见下文）。这种公开聚合方案跨电路工作，即它随递归中使用的电路数量上增长，但同时仍保持证明大小紧凑。

我们估计内部和校验聚合在树状递归中速度提高了大约 30%，适用于我们的具有入度 2的方案，对于其他的纯线性方案也适用。细节请参阅我们关于Darlin^[4]的论文。

接下来我们粗略介绍递归 SNARKs 和聚合方案，并解释上面提到的内部和校验聚合。

1SNARKs...

SNARK 是证明给定大型计算已被执行的简洁证明。所讨论的计算通常被形式化为有限域上的算术电路（即具有加法门和乘法门的电路），并且该电路在某些给定输入上的可满足性可被转换为多项式的代数世界中。多项式有一个奇妙的特性，即它们在小集合上的值蕴含它们在整个定义域上的值（如果它们的次数与有限域的大小相比很小）。这种局部确定性被 SNARK 所利用，SNARK 将此类多项式上的代数等式归约到仅在几个（通常是单个）随机挑战点上进行“局部”检查。

证明者当然必须进行大量计算。它计算阶与电路一样大的多项式，并计算这些多项式的承诺，这通常涉及椭圆曲线中昂贵的多标量乘法。在实践中，像 Groth16、Marlin 甚至 Plonk 这样的 SNARK 能够在普通的现成计算机上在大约 1 分钟内处理超过一百万个门的电路，但对于更大的电路，证明生成在时间和内存方面都变得越来越昂贵。

2...和递归证明

递归 SNARK 证明先前有效证明的存在。为此由 SNARK 处理的算术电路也实现了先前证明的验证者。而这个先前的证明可能会再次证明再先前有效证明的存在，依此类推。

这在理论上是可以的，但在实践中，递归受到许多技术限制的阻碍。（我们不会在这篇简短的博文中详细讨论模拟算术或曲线循环问题）。特别的，基于离散对数承诺方案的透明 SNARKs 面临一个大问题：虽然证明本身是一段简洁的数据，但其验证成本很高（或“不简洁”）。要检验离散对数多项式承诺的赋值证明，必须执行多项式本身大小的多标量乘法。在递归中，这会导致电路规模不断扩大（除非将离散对数承诺方案与另一种承诺方案结合使用）——这阻碍了无限递归的进行。

3聚合方案

在关于Halo^[5]的开创性论文中，Bowe 等人引入了一种全新的方法来处理递归中昂贵的离散对数验证者。他们指定这种结构的离散对数验证者中的一部分（多标量乘法部分），并允许在一个简洁的质询 - 响应协议（ 即一种聚合协议）的帮助合并多个这些部分。尽管约简后的实例（聚合器或累加器）的验证仍然很昂贵，但它只是一次昂贵的检验，可以替代聚合器随着时间的推移吸收的所有昂贵部分。因此，如果在更长的时间内递归聚合，与捆绑在一个递归证明中的大量电路相比，最终的检验会变得简洁。

自从他们的发现以来，聚合方案就成为了一个充满活力的研究课题。很快就出现了更激进的聚合方案，例如来自Boneh 等人的方案^[6]，其累积了加法多项式承诺原像的完全长度；以及Bünz 等人的方案^[7]，他们遵循类似的想法聚合一个R1CS的全长解。

虽然这些方法显著加快了递归速度，但它们具有较大的证明尺寸，该证明尺寸是否可被接受依赖于于应用。在 Latus 侧链的背景下，我们需要保持较小的证明大小，因为我们不能依赖在实践中可能无法满足的网络假设。

4聚合 Marlin 的内部和校验

除了对离散对数验证者之外，Bowe 等人还 引入了另一种聚合方案，但没有像对离散对数验证者的那样受到关注。该方案允许合并 Sonic 的二元多项式的赋值证明，该多项式对要证明的电路进行编码。我们自问如何将他们的策略应用到 Marlin，它比 Sonic 性能更好，但使用了三个二元多项式 来表示电路。（这些多项式对应于描述电路的 R1CS 的矩阵 。）一种简单的方法是将 Halo 的原理分别应用于三个矩阵，但这种方法不能扩展。如果递归由几个不同的电路组成，如 Latus 侧链的情况，则成本太高。下文解释了我们如何做得更好。

5Marlin的内部和校验

Marlin 的很大一部分是在致力于对一个随机线性组合（如下）在一个随机点的赋值证明。其中 和 依赖于协议运行。

为此，Marlin 将这样的赋值证明归约到一个对的单变量 “和校验”论证（所谓的内部和校验）的赋值证明。在一个循环子群上，其大小和矩阵中的非零项一样大。在实践中，根据电路的类型，该大小大约是约束数量的 2-4 倍，内部和校验消耗了整个证明时间的 50-75%。

6单电路聚合

和Marlin的内部和校验不同，我们聚合如下形式的实例：

其中是由 和系数所描述的多项式的（非隐藏）承诺。检验这种内部和校验聚合器是昂贵的，需要计算声称的多项式 并检验 确实是其承诺.

现在假设

是另一个来自之前证明的这种实例，上面的和当前证明相关。（注意声称的多项式是在不同的点和出的不同线性组合的“部分”。)

基本原理与离散对数的困难部分类似。要检验承诺背后的公开多项式，可以在随机挑战点对其进行探测，并将打开值与预期值进行比较。然而预期值并非从一些公共数据简洁地计算出来的，而是再次表示为另一个承诺的多项式的值，在处的水平切片。

• 步骤1：验证者采样一个随机点 并要求证明者提供 “过渡多项式” 和的承诺, 记为。并要求证明者展示他们的打开和和 相关，通过

和

其中我们记 为承诺在点的打开。观察到事实上是的承诺，于是其在的打开实际上是，因此 背后的多项式在被与随机点处探测时返回期望的值。这以极大概率证明了背后的多项式正是所声称的那个。同样的论证对也成立。

到目前为止，我们在验证者的所需努力方面还没有改进。检验 和 携带所声称的多项式与检查初始 和 一样昂贵。但是，当前实例共享相同的点 。我们使用这一事实通过类似于步骤 1 的另一轮来压缩它们：

• 步骤2: 验证者随机采样标量 ，并要求证明者提供对多项式

的承诺，并伴随一个线性组合在新点处的打开和新承诺在“旧”点的打开相等的证明，

注意到背后期望的多项式是：

其中

同样，如果确实携带 和相关的多项式，那么它打开为正确的值，于是随机线性组合在被在随机点上探测时会返回期望的值。因此以很高的概率 和背后的多项式是所期望的那些。

最终，新的聚合器为：

其中 如上计算。

7跨电路推广

多电路情况是单电路情况的直接推广。

对一系列电路的聚合器跟踪如下跨电路线性组合：

通过分别对每一个电路的随机系数  （这里是的R1CS矩阵 )。

如上所述，跨电路聚合对于具有较大递归节点集合的方案很有用。例如Latus 侧链的区块证明是一个动态排列的 Merge-2、Merge-1 和各种不同基的证明树。更多详细信息请参阅Darlin^[8]论文。

8零知识

Darlin 节点在需要保护私有见证数据时以零知识模式运行。在许多应用中零知识是合适的，例如受保护的交易、零知识审计或任何其他类型的私有状态转换的正确性证明。如果您对 Zendoo 生态系统在何处应用零知识感兴趣，可以阅读我们的 Zendoo^[9] 论文。

9还有什么？

Darlin^[10]证明系统还进行了一些其他调整。我们介绍了一种处理单变量和校验论证的替代方法，这是一种受 Plonk 影响的“上同调”论证系统。这个论证系统确实依赖于单独的阶的上界（及其证明），并允许达到更轻量的信息论协议概念。

我们还对 R1CS 矩阵使用了稍微不同的算术化。（在 zk-proof 研讨会期间，我们了解到我们并不是唯一在做这点的人。Lunar^[11] 使用了相同的算术化——我们要感谢 Anaïs Querol 有趣的讨论！）

我们相信 Darlin 可能对其他以递归证明为目标但仍希望保留 R1CS 和小证明尺寸的项目有用。我们很好奇 Darlin（一旦我们的实现准备就绪）和基于 Plonk 的递归方案（例如 Halo 2 或 Mina's Pickles）的性能比较。

参考资料