A Scalable Drop in Replacement for Merkle Trees
演讲者: Benedikt Bünz
日期: October 6, 2018
记录者: Bryan Bishop
译者: Ajian
标签: Proof systems
Media: https://www.youtube.com/watch?v=IMzLa9B1_3E&t=3520
一种马上可用且可扩展的默克尔树替代品
https://twitter.com/kanzure/status/1048454406755168257
开场白
哈咯。声音测试。没问题。
我今天准备讲讲 UTXO 的累加器（accumulators）。前面的两场演讲给本演讲做了很好的铺垫。本演讲涉及的工作是我和 Ben Fisch（他今天也在这里）和 Dan Boneh 的联合成果。我还希望给 Stanford Blockchain Conference（曾用名 BPASE）打个广告，这个会将在 2019 年 1 月在斯坦福召开。无论你是否要去演讲，你都应该去看看。
UTXO
UTXO 集的膨胀是一个日益严重的问题。今天上午我们已经听过了关于 UTXO 集合中的粉尘（译者注：指面额过于微小，因此无法单独花费的 UTXO）。我们已经有大约 6000 万个 UTXO。这里面的问题，我们在前几场演讲中已经听过了：区块链在存储 UTXO 上是非常低效的结构，如果我要下载一个旧区块，那么我需要知道当前区块与该旧区块之间的所有区块头。如果我想下载一笔旧交易并检查这笔交易是否已经花掉了，并且我只知道最新的区块，那么我需要检查从该交易到最新交易之间的所有交易，看看有没有哪一笔花费了它。
UTXO 承诺
有人提议用 UTXO 承诺来解决这个问题。就像我们刚刚听过的，每个区块都包含一个对最新状态（例如当前的 UTXO 集状态）的承诺。这里的想法是，利用共识规则来保证区块头中包含一个事实上正确的 UTXO 承诺。轻客户端将能够检查这个承诺。如果我想说服一个轻客户端某个 UTXO 是存在的，那么我需要给 TA 一个证据，证明它在最新的 UTXO 集承诺所涵盖的数据中。我们可以使用这种思路，将所有人都变成一个轻客户端。
默克尔树
实现这种思路的经典办法是 “默克尔树”。默克尔树的建构方法就像这样。我可以给你一个包含证据，证明 UTXO 集中含有某些东西；在生成包含证据时，需要 log(n) 次哈希计算，而且我可以在某些时候更新证据，每次更新都是 log(n)。
无状态的全节点
这样一来，我就能建构一种无状态的全节点，它不需要存储完整的 UTXO 集。这是怎么工作的呢？当我要发送一笔交易的时候，我必须提供一个证据，证明我的交易在花费一个还没有被花过的币。在当前，矿工用自己的 UTXO 集检查我的交易。但在这种设计中，由用户自己证明自己的币还没被花费过。因此，矿工将不必存储 UTXO 集，就能直接检查一笔交易是否被花费过。这很有趣。
默克尔树的问题
但这种方法有一些问题。主要的问题是，如果每一笔交易都要附加这些包含证据，它们的体积会变得非常大。每一笔交易都需要包含证据，那么区块链会需要额外的 160 GB 空间。并且，在验证区块链时，你需要做许多昂贵的检查。在 Peter Todd 提到这一点时，他提议仅对非常老旧的交易使用这种方法，而大部分交易不应该被逼迫使用这种技术。
RSA 累加器
那么，我想讲讲 RSA 累加器，它是默克尔树的一种替代。我们需要选择一个 RSA 模量，它是一个很大的数（N），是两个大质数（p，q）的乘积。我们还需要一种哈希函数，将任意元素映射成质数。然后，我们从群（the group）（ZN，译者注）中选出一个元素（下文称为 “g”，译者注）来初始化一个累加器（即定义累加器的初始值 $A_0 = g$ ，译者注）。
这种累加器要怎么用呢？假设我们要在集合中加入一些东西。这种累加器是对某个集合的一个简短的的承诺。如果我们想要给一个累加器加入一些东西，我们就以被加入的元素为幂次，求累加器原值的幂，即 Add(Ai, x)=AiH(x)。要是我们需要删去一些东西，我们就以被删元素的倒数为幂次，求累加器原值的幂，即 Del(Ai, x)=Ai1/+H(x)。这里实际上都需要把元素哈希成质数，但在演讲剩下的时间里我会假设每一个元素都是一个质数。这是可以做到的。
如果我要表示一个 UTXO 集 S，那么相应的累加器的值就是 g 的幂，次数为 S 中所有元素的乘积。这种累计器的一个很好的属性是，不必管元素添加的顺序，这种次序是完全可交换的。它还有其它很好的特性。
累加器证据
这种累加器的包含证据是非常简单的，只需要求累加器的现值（A）的被证明元素（x）的倒数次幂（A1/x）。这可以通过使用一个陷门（trapdoor），或者说构建累加器的秘密值（p，q），来计算；我们可以优化这一点。不然，你就得知道整个集合，才能计算出来。如果累加器是诚实地构造的，那么这样的计算会给累加器的现值消去一定的幂次，从而依然得到一个有效的累加器值。在 RSA 群有安全证明，如果 x 不在集合中，你是没办法做这样的操作的。
我们也可以创造出非包含证据，相对要复杂一些，所以我在这里就跳过这些细节了，你可以直接看大屏幕（译者注：Exclusion(A, x): A = gu ; a · x + b · u = gcd(x, u)=1）。它使用了 bazooko 系数。详见 LiLiXue07。你可以作非常高效的无状态更新。我可以高效地告诉你：无论哪一笔交易或者什么东西加入集合或者从集合中移除，我都可以相应地更新我的证据。在我们的论文中，我们说明了可用的方法。
RSA 需要受信任的启动设置吗？
你可能已经听过了这些东西，并且认为，这是没用的，因为 RSA 累加器需要一次受信任的启动设置。要由谁来执行这个受信任的启动设置？“受信任的启动设置” 又是什么意思呢？
问题就在于 N 是 p 和 q 的乘积；如果某人知道 p 和 q，那 TA 就可以完全攻破整个方案，并欺骗你，让你以为某个元素在某个累加器中（即使这并非事实）。而且，累加器的高效删除需要一个陷门。传统的方案假设了有一个累加器管理员，来做这些事。另外，你有可能可以直接找出 N（Ron Rivest 假设）。
的确有一些时候，可以产生没有人知道陷门的 N，例如，Ron Rivest 一开始创建了一个 RSA 难题，并且他删除了 p 和 q，如果你信任他（他可是那么著名的密码学家，还是图灵奖得主呢），那么你就可以使用他给出的 N 值。又或者，有一家很老的公司，他们现在破产了，他们在一个硬件模块中保存了一个私钥，而这个模块在这家公司破产的时候毁坏了。也许这样的 N，你也是可以合理使用的。但这可能还不够好。
类群
BW88 和 L12 两篇论文提议使用 “类群（Class groups）”。类群是一个令人惊讶的数学概念，最初由高斯（Gauss）提出 …… 这是一个二次方根数领域的类群（it’s a class group of quadratic number fields），这其中的想法是，这是一个不明阶数的群，所以你不知道这个群中有多少个数。它的属性类似于 RSA，但并不要求受信任的启动设置。类群的元素比 RSA 元素稍微短一点，大概是其长度的一半。
RSA 累加器前沿
如果只考虑包含证明，RSA 累加器的证据是固定大小的，无论累加器覆盖了多少数据。证据将一直是 3000 比特。当集合的体积大于 4000 个元素时，RSA 包含证据比默克尔包含证据要好。而且，它还有 “动态无状态添加” 特性，就是你可以给累加器增加元素，而无需知晓整个集合。你可以把这个用在去中心化存储中；一个完全验证的节点不需要存储，用户会维护自己的 UTXO 和相应的包含证明。
这里的提升空间在于聚合以及批处理包含证明：要是我有许多个证据，我怎么聚合它们呢？另外，我们能实现无状态删除吗，也就是在不知道整个集合时，为累加器删除元素？验证速度还能更快吗？
聚合包含证据
假设我们有同一个累加器的两个包含证据。事实证明，我们可以利用叫做 “Shamir 技巧” 的方法，创建别的东西 —— 你想要检查的这两个元素的一个包含证据。只要我们能对两个元素实现，那么我们就能对任意数量的元素实现。把一个区块中的所有包含证据都合并成一个 —— 而不是让每一笔交易都附带一个默克尔证据或者一个 RSA 包含证据。所以，我们不需要前面说的额外的 160 GB 的存储空间，只需要 1.5 kB，你甚至可以打印在一张纸上。
无状态的删除
如果我有一个陷门，我就能做到高效删除。但要是我们没有呢？我们改变一下模型：我们假设每次我们想要删除某些元素的时候，我们实际上都有一个可用的包含证据。什么时候我们需要从 UTXO 集中删除东西？无非是某一个 UTXO 被花费的时候。但在它被花费的时候，用户总要提供相应的包含证据。那么，累加器的下一个值将正好等于这个证据；为什么这么说呢？因为这个证据就是 g^(u/x) ，相等于把 x 从集合中消去了。也即，证据恰好就是累加器现值删去被证明的元素后得到的值。因此我们可以把累加器的值设为这个证据的值。在区块链中，情形稍有区别，因为我们会有许多笔交易，因此有许多个对应于同一个累加器值的包含证据。这里，我们又可以利用前面提到的同一种技巧 —— 把所有包含证据合并成一个包含证据，然后更新我们的累加器。这就是我们实现无状态删除的办法，所以我们可以实现批量删除功能。即使我们只有对同一个累加器值的多个证据，也能一次性删除它们。
太慢了？
RSA 有点慢，它比哈希计算要慢。如果你的设置是一个 2000 比特的 RSA，那么每秒只能做 219 次更新。这有点慢，尤其是对完全同步（full sync）来说，你需要更新整个区块链，因此需要检查所有这些证据，同步会变得非常慢。聚合技术只能降低证据的体积，不能节约验证时间。
对于类群，现在还没用基准测试，但它已经用在 “可验证延迟函数（verifiable delay functions）” 中了。Chia 项目刚刚推出了一个比赛，你可以尝试加速类群的计算或尝试打破它们，我记得奖金好像是 10 万美元。我们很快会更清楚这些东西实际上有没有用、安不安全。
Wesolowski 证据（Wesolowski 2018）
我们可以用 Wesolowski 证据来减低验证时间，这是在可验证延迟函数的开发者产生的技术。你也可以使用幂计算证据（proof of exponentiation）。使用 128 比特的大数除法（也即幂计算证据的验证），相比于直接验证，是显著的加速（大约快上 5000 倍）。
快速区块验证
现在我们也可以实现快速的区块验证。假设我是一个矿工，我希望组装我的区块。基于区块链的最新状态，累加器的最新状态，我可以使用无状态删除技术，从累加器中移除一批元素 …… 也就是移除所有被花费的 UTXO …… 然后给累加器加入新的假以，然后我组装新的区块，它依然有区块头，以及相应的交易，可能还有一个 BLS 签名（这是 一种小体积的签名）。然后，它还有两个值，一个是上一个累加器值移除所有被花费的 UTXO（集合为 “s”）之后得到的值（称为 “半路值”），另一个是半路值加上所有新产生的 UTXO （集合为 “n”）之后得到的值（称为 “完全值”），以及它们的幂计算证据。
那么，完全验证节点现在需要做什么呢？TA 必须验证 BLS 签名（这可以很快），然后验证两个幂计算证据（在现实中也非常快）。你只需要检查，从上一个累加器值删去 s 是否可以得到半路值，从半路值加上 n 是否可以得到新的累加器值（完全值），即可。
性能
那么这一套技术的表现如何？请谨慎看待我提供的数字。
我在我的 macbook 笔记本电脑上使用标准的 java 库做了测试。使用默克尔数，对 6400 万个元素的集合生成一个包含证据需要大概 20 次哈希计算，是 8.5 微秒。要是我使用新的 Wesolowski 证据，验证它只需要 0.3 微秒，这比默克尔树快很多。至于类群，我们不知道。会更快还是更慢？类群的体积更小，但也说不准更快还是更慢。在 Pieter Wuille 实现之前，我们很难估计。
向量承诺
“向量承诺” 类似于累加器。你也可以使用默克尔树来实现。这是一种对某一个向量的承诺，所以我可以在某个位置开启它，然后告诉你这个向量在位置 x 有一个值。我们开发了一种新的向量承诺，之前也有来自 RSA 的向量承诺，但验证将需要几 GB 的内存，或者内存会线性增长，而我们的方案不需要内存，所以更加高效。
简短的 IOP
像 STARK 这样的零知识证明技术 …… 或者说叫做 “IOP” 的零知识证明技术类，大体上，是证明者为更长的证据创造一个更短的承诺，然后验证者请求一些索引，证明者发送相应的证据以及默克尔证据，证明在位置 x，证据就是这个数值，然后验证者可以接受或拒绝。问题在于，默克尔路径本身非常大，我们可以用向量承诺来替代，然后我们可以聚合向量承诺，将它缩减到几 kB，而不是大量的默克尔证据。可以将证据体积缩减到 …… 这些数字都来自于一种设定，很难获得真实的数字，因为你要看设定是什么样的。对于一个比较大的设定，你可以将证据的体积从几百缩减到几十。这会渐渐逼近以 log(n) 的缩减比率 。所以证据可以变短。
Q&A
（无）