扩张，扩张，无限扩张 | 突破区块链不可能三角（一）

作者：maxdeath 雇主：上海唯链信息技术有限公司 知乎主页：前面写的是什么

想了半天，加上最近工作变动，这篇文章拖了很久，犹豫再三。 决定结合自己的研究写区块链领域的热点问题——扩容和区块链不可能三角。

看过很多介绍可伸缩性和不可能三角的文章，中英文都有，甚至有一些知名作者或著名研究机构的文章，但都没有一个能很准确地完整解释这个问题。 说白了，几乎每篇文章中总有那么几行让我皱眉：“等等，这写得不对”。 所以，我决定在这里用一个系列来详细解释这个问题。

那么为什么这个比其他的好呢？

其实区块链的可扩展性，也就是不可能三角的问题，是我之前研究的主要方向，也是我一直想写的东西。 不过，说到写正文的时候，我其实想了很久。 犹豫的主要原因是我个人比较抵制在科普文章中加入私货的行为——在我的回答中，我会尽量区分科普部分和个人观点部分，如果我想写科普文章，我会写一些比较中立和经过测试的内容，尽量避免有争议或者没有经过同行评议的创新内容。 而且，既然应该说目前区块链领域的现状是大部分从事科普和媒体的人对区块链技术的专业度不够，而大部分专业的人或多或少都是利益相关者，所以这个定位专栏是为了打造一个“没有兴趣的专业视角”的原创技术栏目，所以我一直在刻意避免成为“利益相关者”而失去科普的中立性（当然这完全是个人的选择问题，以及一些区块链从业者在科普方面做得很好）。

基于以上原因，我一直没有在我的专栏中介绍自己的研究和成果。 一方面，之前的成果还有待完善。 另一方面，我也担心引入不成熟的论据与本专栏背道而驰。 定位。 不过说到底，我现在还是在考虑写这个东西的原因，主要是因为我的论文《VAPOR: a Value-Centric Blockchain that is Scale-out, Decentralized, and Flexible by Design》在刚刚结束的Financial上发表了Crypto 2019 正式发布。 因此，我觉得现在我更有信心去写不可能三角了，同时也介绍一下我对这道题的解法。

为了证明我在区块链可扩展性领域确实有一定的话语权，这里可能还需要介绍一下我的一些工作：

我的第一篇关于区块链无限扩展的论文《Implicit Consensus: Blockchain with Unbounded Throughput》于 2017 年 5 月上传到 arxiv，是最早关于 scale-out 的论文之一。 如果说提交时间，其实比最早的无限扩容解决方案omniledger上传到arxiv的时间早了两天。 但其实也没什么好讲的，因为还没有在学术会议或期刊上正式发表，而且，从现在看来，这个想法似乎还不是很成熟，无限扩展的原因也没有写. 本文的另一个部分工程版本发表在 IFIP Networking 2018，名为 A Blockchain Consensus Protocol With Horizo​​ntal Scalability。

后来，我将本文的共识部分抽象出来进行更严谨的证明，提出了Spontaneous Sharding（自主分片）的概念，并进行了实验室模拟，证明了无限扩展的可能性，即：A Scale-Out Blockchain for Value Transfer with自发分片。 这篇论文发表在 Crypto Valley Conference on Blockchain Technology 2018 上。据主办方称，这次会议是 IEEE 的第一届区块链会议。 虽然是新会议，但影响力远不及相关领域的顶级会议。 名字听起来也是假的，但这次会议确实是一次严肃的学术会议，审稿也很严格。 技术委员会似乎是全明星阵容（主席包括来自康奈尔大学的Emin Gun Sirer教授）。 本次会议投票的原因。

我去年下半年的主要工作是抽象出这个共识算法能够实现无限扩展的原因，为此我提出了“以价值为中心的区块链”的概念和理论结构，并论证了这个结构实际上实现了“价值转移”，即虚拟货币的基本功能，与传统的区块链结构相比具有诸多优势。 最重要的是，它应该自然地无限扩展。 这篇论文终于在去年底被Financial Cryptography and Data Security 2019（FC2019）录用，并于今年2月20日发表，也就是上面提到的那篇。

这里我说说FC。 关于FC，对于不是密码学专业甚至应用密码学专业的人来说可能听起来很奇怪，而且在中科院的排名只是C类（后来才知道有这么一个东西中国科学院排名...）。 然而，这次会议是应用密码学领域最负盛名的会议之一。 而如果要说刚刚在学术界出现时间不长的“区块链”，那么FC无疑应该是区块链领域的顶级会议。 有两个原因。 一是历史原因：FC是最早接受比特币和区块链论文的会议之一，也是第一个加入比特币workshop的会议（相较于近两年的连续会议）相关领域的很多会议都有join the workshop on blockchain, FC早在2014年就加入了Bitcoin Workshop），很多关于比特币的重要论文都在这个会议或BW上发表过，比如selfish mining papers，一篇关于共识算法Ghost的论文，一篇关于比特币的position paper scalability: On scaling decentralized blockchain等。更深层次的原因是本次会议参会人员的研究领域已经与数字货币高度重合比特币数量不是无限制，因此这些人也成为了第一批接受并开始研究的学者学术界的比特币。 到了今年，由于区块链的火爆，已经上升成为金融密码学领域最热门的研究课题，而哪些论文应该在主会上发表，哪些论文应该在BW上发表，其实已经无法界定。 因此，主办方在今年的主会上将BW合并为BW。 第二个原因其实是对第一个原因的补充——到目前为止，FC（和BW）的技术委员会可以说是世界上最懂区块链的一群人，也正是因为如此，对于a 对于区块链的论文，FC是最能收到审稿意见最客观、最有意义的会议，同时也是最容易发现和认可区块链学术贡献的地方。

这是FC2019的网址：

返回主题：缩放，缩放，可缩放，可缩放

以上这些概念无疑是区块链领域的热词，但如果你是严谨的学者，或者只是喜欢深究，想要真正从媒体或白皮书甚至论文中一探究竟。 可扩展性和缩放是什么意思？ 我猜你会被逼疯的，因为许多论文中提到的 Scaling 根本不是一回事。 但如果你恰好不是英文读者，那么这种混淆可能会加剧，因为 Scaling 在不同的语境下可能被翻译为扩张或扩张。 总之，标题中提到的三个词在区块链领域并没有任何确切的定义，在不同的语境下可能有不同的含义，甚至在一些白皮书中，这个词可能没有任何含义。 换句话说，当你在白皮书上看到“这是一个可扩展的区块链”或“解决可扩展性问题”或“可扩展的共识算法”时，没有上下文，你根本不知道它指的是什么。

造成这种情况的原因，我认为是区块链本身是一个没有严格定义的领域，Scalability在各个领域都有不同的定义。 因此，当不同领域的人按照自己的想法定义可扩展性问题，却没有一篇公认的权威论文或教科书做出一个大家都认同的定义时，就变成了现在这个样子——每个人都可以说自己的系统是可扩展的从他们自己的角度来看。 展开。 然后，由于大多数人很难理解这些不同解决方案之间的可扩展性差异，许多概述文章、科普文章和媒体文章混淆了各种可扩展性，从而加剧了混淆。

可扩展的第一个定义——可扩展的 PoW

先说说什么是可伸缩（extensible）。 没有任何限制，这是指随着某个变量y的增长，某个性能x的变化。 如果x可以随着y的增长线性增长，我们就说x是线性可扩展的，或者简单的说是可扩展的。 也就是说，如果我们定了一个很高的目标x，如果我们知道“这种事情只要用某种f方法，然后把y堆起来就可以实现”，那么我们就说这个f方法是可扩展的。

然后，很久以前，人们就已经意识到比特币是不可扩展的——因为他们想提高比特币的 7 TPS，尤其是提高到与传统支付方式相当的输出，比如 10,000 TPS，我们能做的是有限的。 最自然的办法就是增加区块大小或者减少区块间隔，因为即使没有严格的数学分析和证明，人们也知道这是不可能的，因为如果区块增加 1000 倍到一个 ​​G 那么每十分钟一个区块，别说别的了，就是当时的网速也不允许。

但实际上，区块大小和区块间隔受到的限制远不止传输区块的网络速度。 定量分析可以参考上面提到的On Scaling Decentralized Blockchain论文，定性解释是——

在比特币的 PoW 算法中，安全性取决于区块同步速度远小于区块间隔的前提。

比特币安全的前提是——假设所有矿工都是逐利的，那么任何人想要作弊都需要打败50%的算力，因为你必须比别人有更多的算力才能挖出比别人更长的链. 但是，这种竞争公平的前提是作弊者和其他人都在挖同一条链，即全网大部分时间都与当前最长的链同步。 然而，对于比特币来说，情况并不一定如此。 而这就是比特币的PoW不同于传统分布式系统算法的地方——比特币允许网络存在短期的不一致，也就是分叉，即网络中两个不同的节点同时想到两个不同的节点时间。 链是合法的。 这时候，恶意节点想要挖出最长的链，就不需要再和其他人竞争了。 假设一个分叉中的两条链各被50%的算力接受，那么此时只要一个恶意节点拥有超过25%的算力，它就可以挖到下一个区块的概率为超过 50%。 因此，如果比特币总是出现两次分叉，我们其实可以认为比特币的安全性下降了一半。

看到这里，大家可能还不明白——比特币不是很少有分叉的吗，一般分叉很快就会消失？ 为什么会出现“比特币大部分时间都是分叉”的情况？

这里我们想一下分叉是怎么来的——当A挖到一个区块的时候，A会第一时间向全网公布这个区块。 知道的人越多，后面就会有越多的人继续挖矿。 ，所以这条链比其他链长的可能性更大，所以这块最终出现在最长链上的可能性更高——而在比特币中，只有最长链上的那块才是最终结果。 但是，如果A的这块还没有被网络中的另一点B收到，B也挖了一块，B在不知道A挖了这块的情况下也会做同样的事情，所以就是A分叉了，网络将分为两部分。 先收到A的区块的会认为A的链更有前途，后面继续挖，反之亦然。 在目前的比特币网络中，一个区块为1M，传输和验证都比较快，所以将一个区块同步到全网所需的时间很短，只有在这期间两个节点同时挖区块才可能被分叉。 因此，如果这个延迟远小于出块间隔，那么分叉的概率就会很小，连续分叉几次的概率就更小了，所以很有可能一个块后分叉就结束了，留下a 深度为1的孤立块。如果我们增加块大小，或者缩短块间隔，使得同步块时间与块间隔的比例不是那么大，那么同步所需的时间会变长，所以出现分叉的可能性会增加。 而如果同步出块时间超过了出块间隔，分叉数量永远不会减少，反而会增加。

块大小的增加导致块传输延迟的增加，因此块延迟/块间隔的比率的增加增加了网络中可能出现分叉的概率。 同理，减少出块间隔也会导致同样的结果。

而如果网络中一直存在分叉，很难收敛，那么总会有人不在最后的最长链上挖矿，那么整个网络的安全性就达不到PoW理论上的50%水平； 不收敛不仅安全性下降，而且交易永远无法确认。

后者不局限于比特币的PoW算法，可以说是区块链的不可能三角或者分布式系统的CAP问题——如果网络速度跟不上区块传播速度，系统无论如何是不可能保证一致的。

但前者是比特币 PoW 算法的局限性。

从这个角度来看，比特币是不可扩展的——因为随着块大小的增加（减少块间隔），它的输出在达到网络速度边界之前不能无限增加，但它会在此之前达到比特币。 币种 PoW 算法本身的安全性已经到了同步依赖的边界。

因此，从同样的角度，我们想改进比特币的PoW算法，让它摆脱安全对同步的依赖，这样我们就可以简单地扩大区块大小（减少区块间隔）来提高输出，直到边界遇到网速的问题，这种尝试被称为“扩展比特币（Scaling Bitcoin）”，而这样的算法可以被称为“可扩展的PoW算法”，因为，相比于比特币的PoW，他们从这个上来说更具可扩展性看法。

此类算法包括Bitcoin-NG、GHOST、Hybrid Consensus等。那么，同级别的可扩展性还包括白雪公主、Ouroboros等采用类比特币PoW结构的PoS，我们将在下一次详细介绍。

可扩展的第二个定义——无限的可扩展性

由此看来，可扩展性的定义似乎没有争议——事实上，在没有区块链、只有比特币的时候，它是可扩展性的第一个定义。

那么“可扩展”这个词什么时候有了新的含义呢？

大概是从传统分布式系统的人开始研究比特币开始的……

在传统的分布式系统中，可扩展性的定义通常是指系统的输出是否可以随着节点数量的增加而线性增加。 如果是这样，它是可扩展的，或者称为水平可扩展。 所以使用这个定义，如果一个区块链系统是可扩展的，那么如果它有 1000 个节点，输出就是 x，然后如果我们添加 1000 个节点，输出应该变成 2x。 比如比特币网络翻倍，那么TPS就应该翻倍。

但是，正如上面所说，比特币不具备这个属性——比特币的算法决定了它的输出是 7 TPS。

因此，比特币不可扩展。

然而，这实际上带来了一个问题——从这个角度来看，即使是第一个定义中的可扩展 PoW 也是不可扩展的。 即使到现在，几乎没有区块链是可扩展的。 这也很好理解——在一个线性可扩展的分布式系统中，之所以每增加一个服务器都能增加相应的输出，是因为新增加的服务器可以独立承担部分任务。

与传统数据库不同，区块链在某种程度上几乎肯定需要多个节点来存储相同的数据（传统分布式数据库中人们称之为异地多活，冗余设计），否则就失去了去中心化性，因此在某种程度上，它不能达到多几个节点增加输出的效果。 除非，它必须做出一定的安全牺牲或可信假设，这就是人们常说的“区块链不可能三角”。

因此，很多人批评追求这种可扩展性——他们认为以牺牲安全性和去中心化为代价一味追求高产出将失去区块链的意义。

然而，即便如此，高产出的吸引力依然巨大——区块链出现后，人们总是将区块链比作互联网，将公链比作未来的互联网独角兽。 但是，如果区块链做不到这样的可扩展性，它的产出最终还是会受制于网络，无论如何也撑不住互联网独角兽的场景。 为了区分这种可扩展性与前面提到的可扩展性，在区块链共识算法的语境下，这被称为scale-out，即无限扩展。

一般来说，目前可以实现无限扩容的方法有两种——链下技术和分片。 前者本身不在不可能三角的框架内。 从我的角度来说，更多的是区分区块链作为可信中介，然后根据不同的应用和场景，再考虑不同区块链的特点，一种链下的解决方案，可借用区块链提出。 比如链下支付通道，其实就是储值卡在区块链场景下的映射，是小额高频交易的一种解决方案。 从理论上讲，链下技术和链上技术最大的区别在于 BFT 的一致性（见前文），而链上技术需要共识算法来保证交易的一致性（虽然可能需要安全性或去中心化） . 做出妥协），而链下技术本身的交易共识算法并不重要，而是取决于链下解决方案本身的设计以及双方根据场景进行的链下协商。

然而，在学术界，通常不会用scale-out这个词来描述链下算法——因为我之前说过，链下算法自然是scale-out的，所以没有必要用这个词来描述它们. 因此，一般来说，scale-out是一种sharding算法。 属于这一类的算法有Omniledger、Chainspace、王家平先生的Monoxide，还有工程化的Ethereum sharding和Rchain。 我的方案VAPOR从结果可以看出也是零散的，只是原理不一样。 这些，我会在最后一部分详细说明。

从这个角度来看，两者似乎与另外两个流行概念的定义非常相似，即“第二层（链下扩展）”和“第一层（链上扩展）”方案，但在其实，第一层和第二层的概念并不是我们这里考虑的无限扩容，而是从“是否改变主链算法”或者“是否将交易移至链下”的角度出发通过链上抵押 所以，其实除了分片，很多都不是“无限可扩展”，而只是“可扩展”，也就是我们的第一个定义，接下来要讲的第三个定义，方案也叫一级方案。

其中，最容易混淆的是DAG（Directed Acyclic Graph）。 由于一些DAG项目的宣传以及很多人对DAG结构的直观印象造成的误解，在很多评论文章中将DAG与碎片化并列，认为是可以无限扩展的——然而，DAG只是一个概念，DAG区块链的方法有很多，比如GHOST、BLOCKDAG、SPECTRE、PHANTOM、Swirld Hashgraph、IOTA、Byteball、Conflux等等。 虽然DAG在理论上有无限扩展的可能，但目前的具有特定算法（只是一个概念）的DAG方案都不是无限可扩展的，而只是可扩展的。

可扩展性的第三个定义——可扩展BFT

现在，如果将第一类可扩展性称为“可扩展”，将第二类称为“无限扩展”，似乎“可扩展”一词没有歧义。

但是，其实我们还有第三个概念，就是我之前介绍的BFT-like算法。

在我之前的文章中，我主要关注拜占庭容错问题和一些重要的拜占庭容错算法。 其中，我们介绍了一个重要的拜占庭容错算法PBFT（Practical Byzantine Fault Tolerance），还介绍了它的消息复杂度为O(N^2)，即如果要对一个消息（一个事务）达成共识)，需要先将消息广播给网络中的每一个节点（O(N)消息复杂度），然后为了防止恶意节点配合恶意消息发布者故意在网络中传播假消息造成不一致，而每个节点都需要将收到的消息重新广播一遍，所以消息复杂度为O(N^2)。

O(N^2)是什么概念？ 我们用可扩展性的概念来分析一下——假设每个节点的带宽为c，那么整个网络的总吞吐​​量上限为cN。 那么，消息复杂度为O(N^2)的概念就是，如果你将节点数量增加一倍，那么整个网络的带宽将增加一倍，但所需的资源将增加四倍。 也就是说，传统的 BFT 不仅不可扩展，而且是可扩展的对立面。 因此，采用BFT算法的区块链的共识节点基本上只有十几个或几十个。

而且我在之前关于BFT的文章里也说了，一开始大家觉得这个O(N^2)的消息复杂度没有什么问题，因为一开始觉得不实用，二来，即使有，PBFT也只是考虑用在安全条件比较严苛的分布式数据库中，并没有考虑区块链这样的大型网络场景。

然而，当区块链出现，人们开始重新审视BFT时，O(N^2)的消息复杂度就完全没有用了。 因此，人们开始考虑一种更“可扩展”（你看，又是这个词）的BFT算法，即消息复杂度为O(N)的BFT算法。 这样的 BFT 算法有很多，包括 Honeybadger、Byzcoin、Hyperledger-Iroha、Elastico，甚至 Algorand 和 Avalanche 的 BFT 部分都属于这一类。 它们确实是“Blockchains using (more) scalability BFT”，然而，当一些地方简单地强调其优势时，他们会说“可扩展”或简单地称其为“可扩展”，当谈到“区块链”时，它与第一个混用可扩展PoW的类型，虽然，后面我们会介绍，两者最终的效果其实是一样的，但是，如果你想更深入的理解这个问题，你需要知道，可扩展PoW和可扩展BFT的起源并不是相同。

可扩展性的第3.5个定义——比特币扩容

此外，还有 3.5 类可扩展性，即比特币扩展方案——例如大块和隔离见证。

之所以选择 3.5 类，是因为不管怎样，它们只是提高了一些输出，而根本没有解决可扩展性问题。 不过扩展本身也是英文可扩展的，而且从历史的角度来看，这两个方案确实是扩展的第一步，因为——

大区块 —> 多分叉 —> 采用 GHOST —> 可扩展的 PoW

隔离见证 —> 解决比特币的可变性问题 —> 促进链下解决方案的实施 —> 无限扩展

因此，从这个角度来看，说这两个方案对比特币进行了扩容也无可厚非——但归根结底，比特币真正的升级也只是止步于这第一步。

不同定义之间的关系

看到这里，是不是很多自以为已经理解了可扩展性问题的人更加迷茫了——

想知道什么是可扩展的区块链就一定要知道这个东西的由来吗？ 有没有更简单的方法来了解“可扩展区块链”的作用以及当您看到它时它的性能如何？

其实很简单——

首先，3.5类只有两个方案。 大区块和隔离见证可以先排除，因为这两种方案基本上只是以“扩容”的名义出现，只有很不专业的地方才会用“可扩容”。 " 将其与其他可扩展算法进行比较。

其次，目前如果能标榜自己“无限可扩展”，基本不会把自己介绍成“可扩展”。 如果这里仍有疑虑，请记住分片和链下技术不应与其他“可扩展”解决方案进行比较，因为这两种解决方案更具可扩展性，即在大型网络中。 中的输出更高比特币数量不是无限制，但在安全性或中心化方面会做出一些妥协。 更基本的区别是——看这些算法是否要求每个节点记录每笔交易以保证一致性，如果是这样，消息复杂度至少是O(N)，所以当节点加入网络时，这时，产量肯定不会增加。 而如果要无限扩展，就必须有一些交易是不需要广播到全网的。

那么，所有剩下的可扩展算法，也就是我们定义中的第一类和第三类，其实都是以同样的方式结束，达到同样的可扩展性，即O(N)的消息复杂度。 那么，两者的输出最终只会受到网络速度和响应延迟的制约。 最终更好的算法大概会在实验室环境下达到1000TPS的数量级，当然最后还要看算法的优劣。 并且达到了优化的程度，但是在实验室环境下模拟的大型网络的延迟其实比实际水平要好很多，所以在现实中，随着网络的扩大，输出不随着节点数量增加。 想象一下——随着网络变大，输出几乎肯定会下降。

这其中最让人迷惑的是DAG，但是我们之前已经介绍过这类算法，无论是工业界的IOTA，学术界的Swirld Hashgraph还是Phantom和Conflux，无论是在一些媒体还是文章中，或者他们是如何介绍的自己的白皮书，请记住它们是严格“可扩展”的共识算法，而不是“无限可扩展”。

在下一篇文章中，我们将重点介绍此处第一个和第三个定义中的可扩展解决方案，它们的共性以及当前面临的挑战。 后面会介绍一些DAG算法和分片算法，最后介绍一下自己的工作。 这一次，我会争取尽快更新...