Bulletproof: 适用于机密交易及更多方面的简短证明

基于区块链的加密货币通过维护全球分布式但同步的分类账区块链来实现点对点电子价值转移。任何独立的观察者都可以验证区块链的当前状态以及分类帐上所有交易的有效性。在比特币中，这项创新要求交易的所有细节都是公开的：发送方、接收方和转账金额。一般来说，我们将支付的隐私分为两个属性：（1）匿名性，在交易中隐藏发送者和接收者的身份；（2）保密性，隐藏转移的金额。虽然比特币通过比特币地址与现实世界身份的不可链接性提供了一些弱匿名性，但它缺乏任何机密性。这对比特币来说是一个严重的限制，对于许多用例来说可能是禁止的。如果这意味着他们的工资发布在公共区块链上，员工是否愿意以比特币获得他们的工资？

为了解决交易金额的保密问题，Maxwell [Max16] 引入了机密交易（CT），其中涉及的每笔交易金额都使用对金额的承诺隐藏起来，不让公众看到。这种方法似乎阻止了区块链的公开验证；观察者无法再检查交易输入的总和是否大于交易输出的总和，以及所有交易值是否为正。这可以通过在每笔交易中包含机密交易有效性的零知识证明来解决。

当前关于 CT 零知识证明 [PBF] 的提议要么大得令人望而却步，要么需要可信的设置。两者都不是可取的。虽然可以使用简洁的零知识证明 (SNARK) [BSCG13,GGPR13]，但它们需要可信设置，这意味着每个人都需要相信设置已正确执行。人们可以通过使用 STARK [BSBTHR18] 来避免可信设置，但由此产生的范围证明虽然渐近有效，但实际上比目前提出的解决方案还要大。

如本文所述，没有可信设置的简短非交互式零知识证明在加密货币领域有许多应用。在证明通过网络传输或长期存储的任何分布式系统中，简短证明了总体成本的降低。

应用

我们首先讨论 Bulletproofs 的几个应用程序以及特定于这些应用程序的相关工作。 其他相关工作在第 1.3 节中讨论。

机密交易和 Mimblewimble

比特币和其他类似的加密货币使用基于交易输出的系统，其中每笔交易完全花费之前未花费交易的输出。 这些未花费的交易输出称为 UTXO。
比特币允许将单个 UTXO 用于许多不同的输出，每个输出都与不同的地址相关联。 要花费一个 UTXO，用户必须提供一个签名，或者更准确地说是一个 scriptSig，使交易 SCRIPT 能够评估为真 [BMC`15]。
除了 scriptSig 的有效性外，矿工还验证交易是否花费了之前未花费的输出，并且输入的总和大于输出的总和

Maxwell [Max16] 引入了“机密交易”的概念，其中交易中的输入和输出金额隐藏在 Pedersen 承诺中 [P`91]。
为了实现公开验证，交易包含一个零知识证明，即提交输入的总和大于提交输出的总和，并且所有输出都是正的，即它们位于区间 $[0, 2^n]$， 其中 $2^n$ 远小于组大小。
当前所有机密交易的实现 [Max16, MP15, PBF`, NM`16] 都使用提交值的range proof范围证明，其中证明大小在 n 中是线性的。
这些范围证明是机密交易规模的主要贡献者。 在当前的实现中 [Max16]，只有两个输出和 32 位精度的机密交易是 5.4 KB 字节，其中 5 KB 分配给范围证明。
即使最近进行了优化，范围证明仍将占用 3.8 KB。

我们在第 6 节中展示了 Bulletproofs 大大改进了这一点，即使对于单个范围证明，同时以边际额外成本（64 字节）将范围证明精度加倍。
logarithmic proof对数证明的大小还使证明者能够聚合多个范围证明，例如对于具有多个输出的交易，转换为一个简短的证明。
使用 Bulletproofs，$m$ 范围证明只是单个范围证明上的 $O(log(m))$ 附加群元素。这对于当前形式的机密交易已经很有用，因为大多数比特币交易都有两个或多个输出。
它还提供了一个有趣的机会，可以将来自不同方的多个范围证明聚合为一个证明，例如在 CoinJoin 交易中需要的证明 [Max13]。
在 4.5 节中，我们提出了一个简单有效的 MPC 协议，该协议允许多个用户使用单个聚合范围证明生成单个交易。
用户不必向任何其他参与者透露他们的机密交易价值。

机密交易实现可用于侧链 [PBF]、私有区块链 [And17] 和流行的注重隐私的加密货币 Monero [NM16]。 所有这些实现都将受益于 Bulletproofs。
在撰写本文时，比特币拥有来自 2200 万笔交易的大约 5000 万个 UTXO（参见 statoshi.info）。 使用比特币的 52 位表示，可以覆盖从 1 satoshi 到 2100 万比特币的所有值，这导致使用当前系统的范围证明数据大约为 160GB。
使用聚合的 Bulletproofs，所有 UTXO 的范围证明将需要不到 17GB，大小减少约 10 倍

Mimblewimble

最近，有人提议对机密交易进行改进，称为 Mimblewimble [Jed16,Poe]，可进一步节省成本。

Jedusor [Jed16] 意识到 Pedersen 对 0 的承诺可以被视为 ECDSA 公钥，并且对于有效的机密交易，输出、输入和交易费用之间的差异必须为 0。因此，构建机密交易的证明者可以签名以输出和输入的差异作为公钥的交易。这一小改动消除了对 scriptSig 的需求，极大地简化了机密交易的结构。
Poelstra [Poe] 进一步完善和改进了 Mimblewimble，并表明这些改进可以实现一个大大简化的区块链，其中所有花费的交易都可以被修剪，新节点可以有效地验证整个区块链，而无需下载任何旧的和花费的交易。
随着进一步优化，这会导致高度压缩的区块链。它仅包含一小部分区块头以及剩余的未花费交易输出和随附的范围证明以及每笔交易不可修剪的 32 字节。 Mimblewimble 还允许在将交易发送到区块链之前进行聚合。

Mimblewimble 区块链随着 UTXO 集的大小而增长。
使用 Bulletproofs，它只会随着具有未花费输出的交易数量而增长，这远小于 UTXO 集的大小。
总体而言，Bulletproofs 不仅可以替代机密交易中的范围证明，而且还可以帮助 Mimblewimble 成为一个实用的方案，其区块链比当前的比特币区块链小得多。

Provisions 协议

Dagher et al. [DBB`15] 引入了 Provisions 协议，该协议允许比特币交易所证明它们具有偿付能力，而无需透露任何额外信息。
该协议主要依靠范围证明来防止交易所插入带有负余额的假账户。
这些占用超过 13GB 的范围证明是为具有 200 万客户的大型交易所提供近 18GB 证明大小的主要贡献者。
样张大小实际上与客户数量呈线性关系。
由于在该协议中，一方（交易所）必须同时构建多个范围证明，因此第 4.3 节中的通用 Bulletproofs 协议是 Provisions 中使用的 NIZK 证明的自然替代品。
使用第 6 节中列出的证明大小，我们获得范围证明在我们的协议中将占用不到 2 KB。
此外，证明的其他部分可以使用第 5 节中的协议进行类似压缩。
然后证明将由每个客户的一个承诺主导，大小为 62 MB。这大约比目前实施的规定小 300 倍。

可验证洗牌 verifiable shuffle

考虑两个提交值列表 $x_1,...,x_n$ 和 $y_1,...,y_n$ 。目的是证明第二个列表是第一个列表的排列。
这个问题称为可验证洗牌 verifiable shuffle。
它在投票 [FS01,Nef01]、混合网络 [Cha82] 和偿付能力证明 [DBB`15] 中有许多应用。
Neff [Nef01] 给出了可验证 shuffle 的实际实现，后来对其进行了改进 [Gro03,GI08a]。 Neff [Nef01] 给出了可验证 shuffle 的实际实现，后来对其进行了改进 [Gro03,GI08a]。
目前最有效的 shuffle [BG12] 的大小为 $O(\sqrt{n})$。

Bulletproofs 可用于创建大小为 $O(\log{n})$ 的可验证洗牌。
这两个commitment列表作为第 5 节中电路协议的输入。
回路可以通过对两个列表进行排序然后检查它们是否相等来实现混洗。
排序回路可以使用 $O(n\cdot\log{n})$ 乘法来实现，这意味着证明大小将仅为 Oplogpnqq。
这比以前提出的协议小得多。
鉴于 Bulletproofs 的具体效率，使用 Bulletproofs 进行可验证的 shuffle 在实践中将非常有效。
构建证明并验证它只需要$n$的线性时间。