snark侧链方案，可让以太坊网络实现17000tps的交易吞吐量

译者按：此前以太坊创始人Vitalik根据ZK-SNARKs技术提出的500tps扩容方案，引发了社区对区块链扩容的更多思考，而此后由以太坊研究者Barry Whitehat，Alex Gluchowski，Harry R，Yondon Fu和Philippe Castonguay共同提出的snark侧链方案，更是号称可让以太坊网络实现17000 tps 的交易吞吐量。那这种方案究竟是怎么回事呢？本文试图给出答案。

原文作者：BarryWhitehat， Alex Gluchowski， HarryR ， Yondon Fu， Philippe Castonguay

一、概述

本文介绍了一种基于snark的侧链方案，它要求每次状态转换恒定的gas，其不依赖于每次转换过程中包含的交易数。这限制了snark大小的可扩展性，其在经济上是可证明的，这与之前提出的gasBlockLimit/gasPerTx提议（注：以太坊创始人vbuterin提出的500tps扩容方案）不同。

如果出现了一个恶意运营者（最坏的情况下），系统会退化为一种链上通证，而恶意的运营者将无法窃取人们的资金。

如果数据变得不可用，运营者可以被替换，我们可以回滚到之前的有效状态（根据现有用户的请求），然后通过新的运营者继续该状态的运行。

二、系统角色

系统当中有两种角色

1.创建交易以更新状态的用户；

2.使用snark的运营者，他们会将这些交易聚合为单个链上状态更新；

他们使用智能合约来进行交互。系统在默克尔树（merkle tree）中有一个 item列表，它将公钥（所有者）与不可替代通证联系起来。

通证可以被撤回，但机会只有一次。

2.1、在snark交易中

用户创建交易，以更新通过链外方式发送给运营者的通证所有权。该运营者创建的证明包含：

·之前的状态；

·交易集；

通过newState码，我们可以验证EVM虚拟机中的证明，当且仅当证明是有效的时候，系统会更新这个默克尔根（merkle root）；

2.2、优先队列

用户还可以通过智能合约层请求一次取回操作。如果运营者无法在给定的时间内服务这个队列，我们就假定数据不可用。由此，这个运营者会受到惩罚，而系统会开始寻找新的运营者。

两次取出相同的leaf（子叶）是不可能的，因为每次取出时，系统会存储已经退出的leaf（子叶），并检查未来所有退出的leaf（子叶）；

2.3、运营者拍卖活动

如果先前的运营者已经遭到了惩罚，系统会开始搜索新的运营者，而这是通过拍卖活动来实现的，其中用户可以通过投标的方式竞选运营者。

经过一段时间后，新的运营者将根据最新侧链状态的最高出价（高于某个最小出价）被选出。

2.4、回滚

当运营者发生更改时，系统会允许用户退出。要做到这一点的原因在于，在回滚发生时，用户能够拿回某个状态下自己的币。

系统会按状态，排序这些取款操作，并在该状态下回滚链交易，直到新的运营者继续负责状态的更新。

请注意，由于不可能将同一leaf（子叶）撤回两次，所以用户不能从旧状态退出同一leaf（子叶）；

三、讨论

运营者被迫处理优先队列中的请求，否则将遭到惩罚。如果他们拒绝运行系统的snark侧链，他们仍会被迫允许优先队列退出。因此，如果运营者出现了恶意，系统将会退化为一种链上通证。

用户不应该接受一个被传输的leaf（叶交易），除非所有的链数据都是可用的，以便他们知道在最坏的情况下（如果发生了回滚），他们可以成为新的运营者。

成为运营者所拥有的权限，可能超出了普通用户，但只要有一个诚实的运营者想要接管状态，那么用户的钱就会是安全的。此外，在较新的状态投标中，这些运营者的投标相对其他投标都具有优势。

然而，这就允许当前运营者继续连任，因为他们将知道最新状态的数据，并且可竞标最新的状态。

然而，我们可以定一个最低权益，如果他们再次拒绝优先服务，这些运营者会再次遭受惩罚。因此，这样的系统可保证有人会前来处理队列，否则链将回滚到最初的状态，而用户可以在回滚发生时进行退出操作。

不同于无法保证所有状态有效性的Plasma结构，这种设计避免了竞争性撤回，因为snark不允许无效的状态转换。因此，我们可以从具有恶意运营者的场景当中恢复过来，而不必强制所有用户退出（当然，希望退出的用户仍然可以退出）。

四、附录 ：TPS的计算

目前，每个签名需要~500k的constraints，通过优化，我们认为这可以减少到2k constraints；

目前，我们的哈希函数（sha256）每秒消耗50000笔交易。我们可以用消耗1k constraints的佩德森承诺（ pedersen commitments）方案来替代这一点。

如果我们创建自己的29层默克尔树（merkle tree 29 layers），系统就可以容纳536，870，912个子叶（ leaves）。 对于每一笔交易，我们必须：

·确认签名 = 2k constraints

·确认树中的旧叶交易 = 1k * 29 = 29k constraints

·添加新的叶交易，并重新计算根 = 1k * 29 = 29k constraints

这等于每笔交易为60k constraints ；

吴等人所撰写的论文指出，他们可以证明一个10亿gate的 snark；

1000000000 / 60，000 ，则每个snark确认16666笔交易；

而验证一个snark，就需要50万的gas，而以太坊每个区块可以有800万gas。这意味着每个区块，我们可容纳16个这样的snark；

也就是说，每个区块理论上可以容纳 16666 * 16 = 266656笔交易；

266656 / 15 = 每秒 17777笔交易；

我们可通过创建更大的集群来达到更高的tps；

注：运行硬件以达到这个速率，可能会是相当昂贵的，但同时其回报也远远小于当前区块的奖励。

五、社区评论

fleupold回复：

关于回滚期间的退出问题，我有些不解：

“barryWhiteHat： 当运营者发生更改时，系统允许用户退出。要做到这一点的原因在于，在回滚发生时，用户能够拿回某个状态下自己的币。”

这是否意味着在发生回滚后，你能够退出在某个区块（不再是链的一部分）中得到的币（例如，假设我们回滚到第42个区块，我们能够退出在44个区块中得到的币）？

假设第44个区块的数据不可用，有人能够证明退出是有效的吗？

barryWhiteHat答：

在回滚过程中，你将有机会从状态44退出你的币。如果你错过了这个机会，你会丢失掉你的币，而币的发送者将重新获得它的所有权。

一旦你退出了一个 leaf（子叶），那么同一个 leaf（子叶）就无法再次退出，即使我们回滚到它被退出之前；

kaibakker回复说：

我真的很喜欢这个项目的进展情况，这个项目的github代码可以在这里找到：

https://github.com/barryWhiteHat/roll_up 。

下面我来探讨一个问题：你如何确保一个诚实者随时准备成为一名运营者？怎样的收费才是有意义的？

作为一名运营者，他是需要付出一定成本的：

·用于snark计算和数据可用性的服务器成本；

·验证和提现的Gas成本；

运行者可以通过以下的方式收回这些成本：

·存入和提现费；

·交易费；

·无需信任的利息（通过PETH或者DAI利息最大可达到0.5%）

对于一个新的运营者来说，有利可图是很重要的，否则没有人会为此付出代价。如果没有人愿意成为运营者，费用可以适当地增加。

以当前gas价格为例：

假设一名运营者希望每小时更新一次snark。他每年在gas上的花费大约为0.50$ × 24 × 356 = 3560 + 812 = 4372美元，他每年要处理50000笔存款和提现交易，假设这名运营者每提现一次只需支付0.1美元，这就需要额外的5000美元成本，而服务器的成本又需要4000美元，而他如果预计的利润为每年5628美元。

那他预计的收入总额就要达到20000美元，他需要对每笔存款交易收取0.3美元，或者3倍的以太坊gas费用，这样他的业务才是可持续的。这个问题可能是有趣的。

barryWhiteHat回复：

“怎样的收费才是有意义的？”

这取决于用途。我希望它能够应用于不可替代通证、去中心化媒体以及一堆其它应用。文章中我们没有具体讨论到费用。如果你想按每笔交易收取费用，你可以使用存款费或取款费的方式（当然不包括优先队列，这意味着你的取款费必须比优先队列费用要低，以防止费用避免问题的发生），你可能需要用到plasma debit这类技术。目前，我不知道哪种方式最有意义。我想看到一些充分使用的情况。

“你如何确保一个诚实者随时准备成为一名运营者？”

他们不需要诚实，我们只是需要有人挺身而出，最好的办法，似乎就是付钱给他们。当然，这也取决于用例。

MihailoBjelic：

@barryWhiteHat 为你们之前以及现在的工作致敬！

“barryWhiteHat：系统在默克尔树（merkle tree）中有一个item列表，其将公钥（所有者）与不可替代通证联系起来。”

可以说说，为什么整个设计是基于NFT吗，你们是否认为它对于公钥-余额模型（当然会有一些修改）也是有效的呢？

barryWhiteHat：

余额（Balance）模型是很棘手的，因为你可以通过将余额（Balance）从一个leaf（子叶）移动到另一个leaf（子叶），从而实现取出相同的余额（Balance）两次。

我们可以尝试并建立plasma debit，以增加可调节的余额（Balance）。但这需要我们更多的思考。

MihailoBjelic：

对不起，我没有看懂你所说的话。你怎么能把你的balance转移到另一个leaf（子叶）上，你不是只有一个代表你账户（及其余额）的 leaf吗？或许你的思路是用到了SMT？如果你有时间，请查看@jieyilong的帖子：通过链上智能合约实现的链外Plasma状态验证 （你可以只阅读“Plasma状态构造”和“概率Plasma状态验证”部分的内容）。我在思考类似的东西，但使用的是SNARK，而不是随机抽样？

barryWhiteHat：

不确定我们是否在同一个频道。这是我的回答，希望它能回答你提出的问题。

“你怎么能把你的余额（balance）转移到另一个leaf（子叶）上，你不是只有一个代表你账户（及其余额）的 leaf吗？”

如果你无法移动leaf之间的余额（balance），那么你就没有账户余额，因为余额永远都不会改变。如果你不能移动 leaf之间的余额（不包括plasma debit），那么你拥有的只是一个输入输出模型。

“我在思考类似的东西，但使用的是SNARK，而不是随机抽样？ ”

我快速地浏览了一下，如果你想验证整棵默克尔树（ merkle tree）的完整性，为什么不验证每笔交易呢？对一棵大默克尔树进行证明，这需要大量的哈希，而这是相当昂贵的。