突破区块链不可能三角(三) — POS与POW-DAG | 深入浅出区块链 | 技术博客 | 问答社区 - JOYK Joy of Geek, Geek News, Link all geek

突破区块链不可能三角(三) — POS与POW-DAG

系列三 - POS与POW-DAG

本系列文章：

在上篇中，我们主要讨论了 POW 为什么不可扩展，以及如何实现可扩展的 POW。我们再来把逻辑捋一捋：

POW 是个公平的基于算力的随机产生方法，然而，它的有效性是建立在时间的基础上的，也就是说，在计算成功挖出区块的概率时，不仅仅要考虑你的算力在总算力的比例 m，还要考虑你有效挖矿的时间 t。换句话说，虽然我们总说如果恶意节点不拥有超过 50% 的算力时没法攻击比特币，然而，这里并没有考虑到时间 t。也就是说，这里的 50% 是建立在诚实节点都在有效挖矿的基础上的。
那么，什么是有效挖矿呢？在比特币的 POW 里，只有在最长链上挖矿才叫有效挖矿。如果而每当一个合法区块挖出的时候，实际上拥有合法区块的链就成了最长链。而这个时候，哪怕你由于没来的及收到新区块而在原来的区块上多挖了一秒钟，你其实都在无效挖矿。但是对于比特币 POW 而言，从一开始就没有想过要避免无效挖矿的情况。它做的事情就是让无效挖矿损失的算力相比于所需要的总算力可以忽略，于是我们仍旧有接近 50% 的安全性。
那么，在什么时候这些浪费的算力不可忽略了呢？有两种情况，a）当浪费的算力增加的时候；b）当目标算力降低的时候。当增大区块的时候，由于区块所需同步的时间变长，于是从一个矿工发布有效区块开始，其他还没有来得及完成同步的矿工无效挖矿的时间也变长，于是，更多的算力被浪费了。而减小区块间隔，也就是相当于降低目标难度。两者都会使浪费的算力在总算力中所占的比重增加，导致 POW 算法的安全性下降。

3.5 这里我们需要注意的是 —— 并不是只有当分叉的时候才代表了算力被浪费，也就是说说，即便不考虑分叉，随着输出的增加，安全性也会下降。但实际上对于安全性更严重的伤害是分叉，因为分叉会导致一定比例的算力会被浪费在孤块上。无论是何者，我们都看到了同一个结论——算力被浪费的比例随着区块大小 B（大约）增加而增加，随着区块间隔 s（大约）增加而减少，而 B/s 却恰恰是比特币的输出。于是，比特币 POW 的缺陷是 —— 比特币的安全性和输出成反比，随着输出不断增大，比特币 POW 的安全性无限趋近于 0。
于是，想要获得更高的输出，我们需要改进比特币的 POW 算法，使得矿工能够更加有效的挖矿，即，去掉 POW 对于有效挖矿的限制。那么，如何能够更加有效地挖矿呢？在 POW 中，只有在最长链上挖矿才是有效挖矿，即，只有先同步最新的区块，即，同步所有交易，才能进行有效挖矿，而等到挖矿出了新区快，才能开始对于新区块的同步，也就是说这两个的关系是互相依赖的。
因此，想要改进比特币 POW，我们要去掉 POW 的安全性对于同步交易的依赖，也就是说，必须把交易的传输和 POW 脱钩。再换个说法，就是绝对不应该对矿工的挖矿有同步整个账本的限制。

以上，就是扩展比特币 POW 的推理过程。应该说，里面的每一环都是必要的——也就是说，任何用 POW 做共识的算法，都需要考虑这些问题，也都会受到一样的限制。

然后，我们讨论了两种将传输和 POW 并行的思路：

领袖选择：用挖矿决定出块者而不是内容，即交易。这样的话，有效挖矿就不对同步所有交易做要求了，而只是“所有节点能够同步当前正确的出块者”，而这点是容易做到的。然而，它的缺陷是，对于恶意出块者的作恶行为没有约束力。因为如果我们仍旧依照“发现恶意交易就不接受并且分叉”的逻辑来执行的话，就相当于又使 POW 依赖于交易的同步了。因此，我们只有两个选择——a）通过一些方法来惩罚恶意出块者；b）保证出块者不作恶。前者就是 Bitcoin-NG 所采用的方法——如果前面有出块者作恶，那么后面的出块者可以通过某些特殊的交易拿走之前出块者的所有奖励。而后者则不能只选取一个出块者，而是需要选取很多出块者，即某个委员会。例如，我们选取前 20 个区块的区块发布者（即前二十个成功算出目标哈希值的矿工）作为委员会。然后委员会内部通过 BFT 算法决定一个区块。这里需要考虑的问题是，首先委员会不能有超过 1/3 的恶意节点（因为要做 BFT），而这点只能通过概率保证，例如，当整个网络中恶意算力不超过 1/4 的时候，我们可以通过大数定理保证选出 20 个矿工他们其中恶意的矿工数量超过 1/3 的可能性非常小，然而，我们却没法说如果我们只选 4 个矿工，那么一定最多有一个矿工是恶意的。因此，最终这个委员会的大小决定了系统的容错性，委员会越大，容错性越高，但由于要做 BFT，因此延迟会更大。
将非最长链上的算力也纳入有效算力。这点，我们介绍了 GHOST。在 GHOST 之中，最长链共识被改成了最重子树共识，而矿工不限定只指向前一个区块，而可以指向其他看到的深度为 1 的孤块，即下图这种结构：

这里我们比较的是“子树”的“重度”，也就是区块的数量，代表了算力。根据这个规则，最下端攻击者的子树并不如上面的子树重，而 4B 的子树是最重的子树。

从有效挖矿的角度讲，GHOST 的意义是：即便矿工没有及时完成对于最新块的同步，并且导致你在别人之后才挖出了区块，你的算力也不会浪费，同时，也不容易导致后续分叉，造成算力的浪费。

然而，GHOST 仍旧不是最优的做法，因为如果同步所需要的时间超过了一个区块间隔，你挖出的区块仍旧可能无法被纳入最重链，于是算力仍旧被浪费了。因此，如果从之前安全性和输出的角度考虑画一条曲线的话，GHOST 在输出不高的情况下安全性和比特币 POW 一样，然后，随着输出提高，然后，在很小的一个区间内，比特币的安全性下降但是 GHOST 的安全性不变。也就是说，GHOST 能够将输出提升到这个区间。再之后，随着输出继续增加，GHOST 和比特币 POW 的曲线是没有什么区别的，最终都会变成 0。

然而，我们可以把 GHOST 的思路推广开来——例如，我们可以允许节点接受深度为 2 的孤块，继而是深度为 3 的孤块……最终，让所有挖出的区块都不会浪费，都能贡献给系统的安全性。从结果上来看，我们将会无限扩大 GHOST 那个安全性不随输出变化的区间，最终得到一个安全性不依赖于输出的算法。而从实现方法上看，其实这样的系统，就是一个 DAG。

之所以我又花了这么大的篇幅又唠叨了一边比特币可扩展性的问题，是因为 POS 和 POW-DAG 的可扩展性以及他们采用的方法在很大程度上就是前文中可扩展比特币 POW 算法的自然演化版，我们先从 POS 说起。

权益证明 POS

在前文中我们也看到了，可扩展 POW 的算法基本上都是 3-4 年前甚至更早的了。原因很简单 —— 在学术界，大多数人都转向了 POS。在这里，我们先略过许可与非许可之争以及 POW 和 POS 之争，所以我先不去详述 POS 和 POW 的优劣（这个我可能最近会单开一篇谈一谈）。但是事实就是，在学术界的非许可链的共识算法这个问题上，大部分更新的算法都选择了 POS。

POS，权益证明，顾名思义，就是相对于 POW 的“算力越高，挖出快的概率越大”的方法，改成“钱越多，挖出块的概率越大”。然而，相对于说 POW 我们就会想到比特币 POW 不同，POS 并不是仅仅指某一种算法，而是这一类用权益作为权重进行出块者选取的方法。

在这里，我就跳过早期 peercoin 和 NXT 的 POS，也跳过 DPOS 以及以太坊 Casper，我们只从输出的角度简单地叙述几个比较典型并且有比较严谨的学术论文的，基于随机数的 POS：Snow White，Ouroboros，Algorand 和 Dfinity。

无论是从可扩展性角度还是实现角度，这几个算法都可以说是可扩展 POW 的领袖选择思路在 POS 中的对应。其中，Snow White 和 Ouroboros 相当于 Bitcoin-NG 的 POS 对应，而 Algorand 和 Dfinity 则是 Hybrid Consensus 和 Byzcoin 的对应。

但是，这里有一个必须要先解释一下的问题——这几个算法的随机数是怎么产生的。

恩……果然这一篇解释不完，所以在这篇里，我们姑且认为有这样一个神（随机预言机，Random Oracle）可以每隔一个时间 t 就提出一个真·随机数，然后，我们可以通过这个随机数和当前账本上每个人拥有的钱数，进行一个带权重的抽签来决定每一轮的出块者……

细心地朋友已经察觉出问题了——

我们在比特币中费那么大力气挖矿不就是为了实现这个么？你现在用一个“神”就把我们打发了？

然而，事实就是这么回事。在我看来，之所以后来学术界纷纷转向 POS，实际上就是看到了这个问题：“这个问题不就是我们研究了很久的随机数的东西么，我们完全可以通过密码学解决，为啥要用又费电又费时的 POW？”

于是，实际上上面的每个 POS 算法，都在某种假设下，从某种程度上实现了这个“神”的功能，因此，我在这里就直接用“神”替代了，而先略过实现的细节。

有了这个“神”之后，我们实际上就不再有之前的烦恼了，也就是，需要并行共识和传输的烦恼，因为我们可以把几乎所有的带宽*时间用于传输和验证而不担心影响系统的安全性。换言之，我们可以采用最简单的级联结构而把区块设置得尽可能大——例如，10 分钟内能够同步多大的区块，就设多大，而不用担心共识的时间不够导致系统安全性下降的问题。

于是，既然我们能够把所有的带宽*时间都用于消息传输了，这些 POS 的算法和可扩展 POW 应该是接近的。

这其中，Snow White 和 Ouroboros 类似 Bitcoin-NG，只有一个领袖负责出块。而 Algorand 和 Dfinity 则类似 Byzcoin 和 Hybrid Consensus，采用一个负责出块的委员会。两者相较，以输出而论，两者各有千秋。前者在一个更诚实和节点更活跃的网络中表现更好，因为在理想状态，这就是一个大家轮流出块的系统，然而，它在节点不活跃或者恶意的情况下容易出现空时段或者分叉的情况导致带宽的浪费，以及相对而言更高的确认时间。后者由于采用委员会，所以这种情况只有在整个委员会不活跃或者恶意的情况下才会出现，因此出现概率会随着委员会人数的提高而降低。然而，委员会之间的通信，通常采用传统 BFT 或者可扩展的 BFT，所需的时间和消息复杂度会带来更高的延迟，乃至相比于将消息广播到全网而言不可忽略（如果人数太多的话）的通信复杂度。这两者的适用场景会有区别，个人认为，对公链而言，由于所处网络环境的复杂性，后者的输出和延迟更加稳定。

POW+DAG

正如前文所说，DAG 是 GHOST 想法的延伸 —— 但是，GHOST 和 DAG 之前还有一个中间步骤：

在 GHOST 中，叔块是只计算算力但不考虑里面包含的数据的。于是，如果我们将 GHOST 的想法继续扩展，我们最终得到的结果是，无论我们如何增加区块大小（或者缩小区块间隔），算力都不会被浪费，于是，我们可以获得比比特币 POW 更高的输出。然而，这个结果只是保证了算力不被浪费，但是用于传播非主链上的区块的带宽还是被浪费了。举个例子，如果我们将区块大小增加到 100MB，于是网络中平均在每个时间段都存在 3 个合法区块。在比特币 POW 中，这种情况会导致算力分散和安全性下降。但如果采用了 GHOST 的模式，这种情况不会发生，但是我们最终需要每 10 分钟传输 300MB 的区块，而最终被保留的只有 100MB 的交易，剩下的部分都被浪费了，这显然不是我们想要的。

于是，如果我们选择也保留这两个区块，我们才得到了理想的 DAG —— 每个矿工只需要：

打包交易；
尽量同步新区块并且连上；
挖矿，在挖到之后就把区块发布出去。
然后，最终的结果是，无论是你打包的交易，还是你挖矿的算力，最终都会成为共识的一部分。（这里有个坑，我们一会再说）

我们可以从两个角度来理解 DAG：

第一个角度，从结构上来说，它不再是一条链，而是一个图，但更确切地说，它是一条带子，例如下图：

IOTA（the tangle）的这张图还是很形象的

这张图可以帮助我们对于区块链中 DAG 的样子有一个非常直观的认识 —— 因为 DAG（有向无环图）只是一个定义，但是它的形态却并不止一种。而从这张图上，我们能看出来区块链中 DAG 大概长啥样：

首先，它不是一个链，但是，也不是一个无线变大的如同树状的图，它更像一条带子，而带子长度是时间，而宽度我们可以认为是同一段时间同时产生的区块。
于是，宽度实际上代表了这个 DAG 的输出，当宽度是 1 个区块的时候，我们实际上获得了区块链。而假设宽度是 10 个区块，我们相当于把区块链的输出提高了 10 倍。
与链式结构不同的地方在于，当矿工发布区块的时候，它不需要同步网络中所有的区块，而只需要同步一部分区块就可以了。在这幅图中，是所有在它之前并且直接或间接相连的区块。
于是，在最终，所有的矿工仍旧会对这条带子上的所有交易达成共识，也就是图中浅蓝的部分。这就是我在第一部分中所说的，DAG 并不是无限扩展算法，因为它仍旧要求所有矿工对所有节点达成共识。
最终，一个区块被确认的前提是——它大概率不会被分叉，除非有人拥有超过 50% 算力。

那么，这个带子的宽度由什么决定呢？

答案是网络本身的特性（例如网速，拓扑结构）和区块链本身的参数（例如区块大小，间隔等），而后者，在理想状态下应该被设计成正好能够完全利用整个网络的带宽 —— 这是什么概念呢？我们来换个角度：

假设你是一个矿工，理想的状态是，你一边坐着火车（挖着矿），一边吃着火锅（同步着区块），一边唱着歌（验证着交易），然后矿挖好了发布区块的时候，你正好也把之前你发现的网络中所有的区块同步并且验证完了，而在挖矿期间，你又发现了新的区块正好可以在下一轮挖矿的时候进行同步……

如果所有矿工都处于理想状态，那么，这个网络中的带宽就被全部利用了。

然而，如果有矿工常常出现：火车还在开火锅吃完了，那么就说明带宽并没有被很好的利用，于是我们可以增大区块或者缩小区块间隔来提高输出。这种提高输出放在图里的体现，就是更多（更大）的区块会在同一个时间段被创造出来，于是带子变宽了。

另一个情况是，如果出现大量矿工无法同步所有区块的情况呢？显然，这个时候说明我们需要把输出降低一些。但是，如果我们不降低输出，会发生什么情况呢？

第一，既然网络的容量是一定的，所以最终得到确认的交易数量肯定不会增加。但问题是，因为新增的区块太多，那么对于矿工而言，就很难对于新增的区块达成一致的共识，最终导致的结果，就是——这条带子会变得越来越宽，而不是越来越长。因此，大部分的 DAG 需要对于这样的情况加以限制，所以通常 DAG 会给新挖出的区块以更大的权重，来鼓励这条带子往长而不是往宽的方向发展。同时，这也可以限制恶意节点故意从老区块上建立分叉的行为。

第二，这样的话，那些不能及时同步所有区块的矿工，会由于无法将他们的区块加在最新的区块上，导致他们的区块不能带来足够高的权重（因为太旧了）而被其他节点放弃。最终，这些区块和算力会被浪费。

第三，由于网络中节点的网络状况和算力是不均等的，所以必然有的节点会出现火锅没吃完车停了的情况，有的节点会出现车开着火锅吃完了的情况。因此，最终我们会调节区块链的参数，使得整个带子处于一个两者均衡的状态，以期达到最大的输出和浪费最少的算力。

听起来很好，不是吗？

DAG 似乎只是一个简单的对于链式结构的扩展而已，我们减弱了链式结构中输出和安全性的相关性，最终能够通过调节参数，近似地利用所有的网络容量，达到接近最优的输出。

看上去，我们在这期间没有牺牲掉任何东西，不是么？

可惜，答案是否定的。

DAG 中的定序问题

其实，区块链以及一切 BFT 算法，除了要对内容（区块）达成共识，也必须对于这些内容的先后顺序达成共识。换句话说，顺序也是共识中不可缺少的一部分。

在 PBFT 中，两轮的通信中第一轮就是定序。

对于比特币 POW 而言，由于采用链式结构，所以定序和共识是同时进行的——当一个矿工引用了前一个区块的时候，自然而然就表明了这两个区块之间的顺序。

但在 DAG 中，虽然所有节点最终对于所有区块会达成共识，同时由于图的有向性，对于一条支链上的所有区块是有共识的，但是，如果两个区块互相之间并不能直接相连，那么两个区块之间的顺序是没有共识的，例如：

这里，6，7，8 之间的顺序就是不定的

可能有人会问：顺序有这么重要吗？

答案是：在有些时候，可能没这么重要，这也是为什么 IOTA 号称“用于 IOT”，因为他们自己很清楚 IOTA 的算法 tangle 是无法定序的，于是，就无法用于数字货币。

因为，数字货币需要定序才能决定两笔冲突的交易哪笔合法哪笔非法 ——

之前已经提到过，从 GHOST 到 DAG 的重要一步是，我们需要把同时产生的多个区块的交易全部纳入共识。这其中不可避免的两个问题是：

重复的交易会降低输出，这个我们一会再说。
冲突的交易，例如一个交易 X 说 A 把钱付给了 B，一个交易 X'说 A 把钱付给了 C，这两个冲突的交易都纳入共识的话，我们必然需要一个一致性的算法来判定哪个是真的，而这就必然涉及到顺序的问题，可是如果所有的节点无法对两者的顺序达成共识，也就无法对于这两笔交易的合法性达成共识。而无法对于合法性达成共识的结果，就代表这两笔交易永远无法得到确认，换句话说就是达不到活性。

这是一个非常麻烦的问题，目前为止，有两个思路：

思路一：通过后面区块的拓扑结构来定序

这是 GHOST 的小组一直在尝试的方法，从 SPECTRE 到 PHANTOM 他们都采用了区块虚拟投票的方法，即，由后面的区块来决定谁先谁后。

他们设计了一种投票机制，来使投票的结果可以快速收敛到某一边——假设由于出现时间先后或者由于随机的原因，后面连着含有交易 X 的区块略多于连着含有 X'的区块，那么，这个算法会保证结果会随着时间增长越来越压倒性地偏向 X，最终迅速地收敛至 X。

但是这个设计的问题在于，没法保证投票的结果一定会偏向向某一边——尤其是恶意节点可以通过很少的算力就去维持两边的平衡。

SPECTRE 对于这个问题的解决方案是：不解决。

SPECTRE 做出了这样一个假设：这是一个虚拟货币，如果 X 和 X'同时出现，那么 A 一定在短时间内签署了两笔冲突的交易，那么他是恶意节点。于是，我们没必要保证这样的交易的活性。也就是说，如果恶意节点想要一直通过平衡两条差不多重的分支来让别人无法确认两笔交易谁合法的话，那就随它去，反正这是恶意节点的交易。

而那些诚实节点发出的交易，我们可以保证活性，并且确认任何两笔交易之间的先后顺序。

但这个假设就造成了 SPECTRE 的局限性使他无法作为图灵完备的区块链系统的算法，因为在那里面，我们需要全序性。因为智能合约也许需要判定两个不同的人发布的消息的先后。

于是 Phantom 和 BlockDAG 都致力于基于投票来解决这个问题，他们主要的思路是希望能够证明诚实的网络组成的图一定会有某些特性，并且，可以用之前的虚拟投票方法来定序。但一些恶意节点创造出来想要破坏全序性的分支一定不具备这些特性。于是，我们只需要通过某种判别方法筛出那些恶意节点创造出的分支。

然而，目前他们给出的判别方法还是有问题。而且，从某种角度看，它实际上就是复杂化的第二种思路：

思路二：确定一条主链

实际上，如果我们能够确定一条主链，我们就可以很容易地根据主链和一套确定性的规则来对所有区块定序了。

然而，确定主链并不容易——因为 DAG 是长这样的：

如果网络均匀分布的话，那么我们大概率得到的是 n 条几乎差不多长而且匀速增长的链，想要从中确认一条主链，实际上几乎和定序一样难。除非我们能够在算法上进行一些改动，让算法能够更容易收敛出一条主链。但是，在这样的 DAG 结构中，需要收敛出一条主链就代表着矿工需要优先同步主链，而不能同步的节点就面临算力被浪费的风险。从这个角度讲，在这种 DAG 结构下，想要追求定序也可以，但是代价是输出的降低。

在这方面，Prism 在这种结构上做出了改进——它从结构上把 DAG 拆解开，然后用传统的链式结构生成主链，然后用类似 DAG 的结构进行出块。从一种角度讲，它解决了 DAG 的定序问题，但是从另一种角度讲，它又很像 Bitcoin-NG，唯一的区别就是 micro block 不再由领袖生成，而是由各个节点生成再用 DAG 的形式连在主链上……

而这就为 POW-DAG 和可扩展 POW，建立了一座桥梁。

DAG 的重复交易问题

DAG 中绕不开的另一个问题，是重复交易。尤其是在比特币这种所有矿工共享交易池的系统里，如果每个节点都自行往外捞交易打包的话，那么必然会出现“矿工生成的区块中有大量重复交易”的情况，这就完全失去了我们采用 DAG 把一条链变成一条带子的意义——诚然，每个时间间隔达成共识的区块从一块变成三块，从 100MB 变成 300MB，但是如果这 300MB 之中每个交易都被打包了三遍，那区块链的实际输出等于没变，反而需要储存和传输的数据多了三倍。

于是有人会问：重复率会有这么高么？

但是实际上，如果沿用比特币现在的交易池结构的话，重复率几乎一定是这么高的，因为所有矿工都用同样的规则从同一个池子里捞交易——而这样的话，其实输出不仅几乎没有提升，反而还要造成储存空间的浪费（因为重复交易也需要被传输和储存才能验证区块是否合法）。

所以，采用 DAG 的时候矿工必须同时采用一个不一样的交易选取机制——要么，取消交易池，把每个节点就近或者随机分给一个矿工负责打包交易；要么，矿工需要采用随机的方式从交易池里捞交易。

但两者其实都只能治标，不能治本——

前者会造成中心化。换句话说，如果接受你交易的矿工下线或者恶意，又甚至说它单纯地能力不行，都会导致你的交易无法被确认，那么结果就是你还是需要把你的交易广播给更多的矿工，于是再次造成重复交易。

后者则需要做一个“矿工会诚实地随机从池子里选取交易的假设”，但这个和“理性矿工应该优先选择交易费高的交易”是相悖的。如果严格约束前者，会同时损害矿工和交易者的利益，因为矿工有可能会无法获得最优的交易费，而交易者也无法通过提高交易费来保证自己的交易更快被矿工打包。因此，这招更像是在“交易市场”中采取“计划经济”的手段来强制分配资源。

但无论如何，重复交易对于 DAG 输出的影响都是巨大的——即便作为交易者，你只把你的交易多发给一个矿工作为备用方案，都会导致 50% 的交易重复，即输出下降 50%，或者说，千辛万苦提高了的网络使用率，就这样被抹去了 50%。

（大家有没有想起一个人？）

IOTA 作为最早的 DAG 之一，自然想过这个问题，所以它取消了区块和矿工的设定，让交易者自行进行 POW 和上传交易。然而，这种做法不仅带来了更严重的安全隐患，同时引入了另一个导致重复交易的设定——tangle 算法里假设诚实节点会努力提高自己的交易被接受的速度，甚至可以继续在自己的交易后面连上空交易来增加自己交易被别人引用的几率，这其实是变相地在鼓励交易者为交易浪费更多的带宽。

但是，IOTA 的有一点思路是没错的——如果在某个场景下，矿工本身不是从池子里捞交易而是自己生成交易并打包上链的话，那么这就不存在重复交易的问题。