DAG的妙用（三）——比特币协议的扩展

全文字数：5033

阅读时间：15分钟

上周应国内小伙伴的要求，我做了一节线上公开课来跟大家分享时下比较火的DAG技术。由于我之前做过一段时间的研究，也写了两篇公众号的文章，所以对于这块还是颇有心得的。

大多数人在刚开始了解区块链的时候会有一个相同的感觉:就是各种眼花缭乱的新名词如雨后春笋般涌现出来，像是进入了一个异次元的世界。虽说是软件层面的技术，但即使是科班出身的码农也是丈二和尚摸不着头脑，好像自己的CS都白学了。我起初也有这样的困惑，纵然有万千资料，但终究是管中窥豹，无法通达其旨的。后来通过研习代码，总算理清了一条完整的脉络，所以觉得有必要分享出来。

庄子云，“吾生有涯而知也无涯，以有涯随无涯，殆矣”。这句话放在区块链的学习上真是再形象不过了。好不容易搞懂了区块链是怎么回事，现在又出来一个DAG。刚刚看完了POW，现在又冒出来POS，DPOS。似乎区块链这个领域的技术迭代是非常快的。可神奇是，它的落地应用却不多，所以理解起来会更加抽象。其实归根结底还是因为这些知识点过于零散，无法拼凑成一幅完整的画面。而我这个讲座就是把这些碎片化的知识串联起来，从区块链的前世今生开始讲，最后引到DAG。这样一来大家就能看清这幅完整的图画到底是什么。也只有这样我们才能把书越读越薄，以后即使看到再多的新名词，也可以触类旁通，举一反三。

错过这堂讲座的朋友也不要担心，我已经把整个讲座录了下来，点击阅读全文就可以获取完整视频。

在这堂讲座的结尾，有个很热心的朋友纠正了我PPT里的一个错误。下图为那一页的PPT：

我说DAG的目的是为了消除区块和挖矿。其实这种说法还是有失偏颇的。这位朋友提到了一个BlockDAG的概念。那就是DAG和区块技术的一个很好融合。我这两天也好好研究了下，觉得确实很有道理，这也是我今天想给大家讲的东西。

背景

我们知道比特币的POW的本质是通过算力来投票，而最长的那条区块链就代表着最多的算力投入，所以会被当作一个正确的范本来给其他节点拷贝。

这样确实解决了共识的问题，但也牺牲了tps。因为每一个节点在进行挖矿之前，必须要先等其他节点广播完最新的区块，否则自己很有可能在一条注定被废弃的分叉上挖矿，白白浪费了算力。而另一方面，比特币的出块时间被严格控制在10分钟的长度，加上区块的容量限制，导致每秒可处理的交易数只有3-7笔左右。

所以不少有识之士提出，为何我们不能支持更多的并发，同时接受不同节点广播的区块呢？为何我们要等其他节点广播结束，不能立即进行挖矿呢？比如说有1000笔交易，我可以分两次挖矿来存这1000笔，也可以两个节点同时挖矿各存500笔。如下图所示：

（图片1）

图中B1和B2相当于不同节点产生的两个区块。由于每个区块只能存500笔交易，所以必须要分两个区块来存。

左边部分所代表的就是现在比特币的方案：当B1创建了以后，必须要等10分钟，才可以创建B2。所以总共需要20分钟才能完成所有交易的记录。

而右边部分显然代表的是更好的方案：因为单位出块时间内如果允许多个区块同时产生的话，自然就可以比之前的方案节省一半的时间。

可惜这套方案在区块链(Blockchain)的数据结构之下是无法实施的，因为区块链就是一个单链表【1】 ，它不允许分叉。如果要承载这个新的记账模式，就需要在原有的数据结构上做一个延伸，那就是BlockDAG。

BlockDAG

关于DAG的定义，我在之前的“DAG的妙用（一）——记账新方法”里面就有跟大家讲过，这里不再赘述。而我今天想讲的是更直观的一些内容。

其实无论是Blockchain还是BlockDAG，那都是很抽象的东西。如果说Blockchain是一串连在一起的箱子，那BlockDAG就可以想象成一张网，如下图所示：

（图片2，来源于PHANTOM和GHOSTDAG的论文）

图中的Genesis就是创世区块，之后从B到M的所有点都是区块。你会发现这些区块都直接或间接指向创世区块。这个跟IOTA【2】的DAG概念何其相似！

点的含义

起始点

路径走向

BlockDAG

区块

创世区块

所有区块都直接或间接指向创世区块

IOTA DAG

交易

创世交易

所有交易都直接或间接确认创世交易

其实天底下的DAG都是如出一辙，因为DAG只是有别于链表的一种数据结构而已，它代表的仅是数据的存储方式。比如说我有一堆箱子要放在一个房间里，我可以排成一排，也可以叠起来。但无论怎么放，房间就是这么大。所以根据自己的需要，我有不同的摆放方式。如果我想方便查找，那就摆成一排，如果是要节省空间，那就叠起来。而数据结构就好比是这些箱子的摆放方式。

针对BlockDAG，有一些特定的术语，以区块H为例：

G = 图中所有区块的集合

past(H) = 从H开始，直接或间接指向的区块的集合 = {C,D,E,Genesis}

future(H) = 直接或间接指向H的集合 = {J,H,K,M}

anticone(H) = 除了Past(H)和Futrue(H)之外的所有区块 = {B,F,I,L}

tips(G) = 末端区块的集合 = {M,J,L}

虽然有了DAG这个数据结构，但那仅仅是万里长征第一步。因为最关键的问题还没解决：如何判断图中哪些区块是可信的？

这就是共识协议解决的问题。对于IOTA DAG来讲，它的共识协议是Tangle【2】。至于BlockDAG，它必然也有自己的共识协议。

基于BlockDAG上的共识协议——PHANTOM

我们仔细观察下就会发现，单链表事实上也是DAG的一种，所以BlockDAG上的共识协议可以看作是Blockchain上比特币协议的一种扩展。基于BlockDAG的共识协议有许多：例如SPECTRE，PHANTOM，GHOST等等。这次我以PHANTOM为例给大家介绍一下它具体的运作机制。

我们先来看下挖矿规则：

和比特币的区块链一样，它也是基于POW，所以在创建区块之前必须求解一个复杂的哈希函数（SHA256），使输出的哈希值满足一定的范围。唯一不一样的是：它的区块头可能包含了多个区块的哈希值，来指向过去不同的区块。如下图所示：

（图片3）

图中我对Blockchain和BlockDAG做了一个比较：对于BlockDAG来说，每个节点会以当前收到的DAG图为基准，它所指向的区块就在图的末端——tip(G)。由于分叉是可以被接受的，所以每个节点无需等待“最新版本”的发布，就可以立即进行挖矿。这一点相较于区块链自然会具备更高的tps。

可是俗话说林子大了什么鸟都有，即使大家都遵守以上挖矿规则，也不能保证每个节点都是诚实可靠的。若要存心作恶，那完全可以私自挖矿，去记录一些虚假交易，并且屏蔽掉其他好节点的区块。如果这样的话，我们如何区分哪些区块来自好节点，哪些来自坏节点呢？

在设计这个分类算法之前，我们必须要假设整个矿工社群50%以上的节点都是诚实可靠的。事实上任何去中心化架构都必须以此为大前提，否则根本玩不转。

除了这个大前提以外，我们还需要确定可允许的分叉个数。假设它为k，那说明至多只能有k个分叉。如果实际分叉数为k+1，那其中某条分叉就会被认为来自坏节点。如何定k的值是个问题。如果k值定太大，那就会增大容错率，如果k值太小就会牺牲tps。在k=0的时候就变成了区块链。所以tps和容错率是一对矛盾，我们必须要在两者之间找到一个平衡点。在这里我们选择k=3。

有了这两个前提以后，我们再定投票机制。和比特币一样，我们用算力进行投票。不同的是，选择标准不再是看哪条链最长，而是看图中哪个子集包含最多相互联通的区块，并且满足k值的要求。

我把满足k值要求的子集称为k-cluster。对于一个子集是否为k-cluster，PHANTOM给出了一个明确的数学定义：

A subset S ⊆ G is called a k-cluster, if ∀B ∈ S : |anticone (B) ∩ S| ≤ k.

简单来说，就是这个子集里任何区块的anticone和子集本身的交集不能超过k。有了这个定义以后，我们就可以通过一个标准的算法来判断这个子集是否为k-cluster。而我们的目标就是在所有满足条件的子集里，找出最大的那个。

接下来我们就可以来设计分类算法，来把好节点和坏节点的区块都区分出来。既然好节点的区块集就是图中最大的k-cluster子集，那剩下来的部分自然就来自坏节点。所以算法的核心就是找出最大的k-cluster子集。

如何找出最大的k-cluster子集(k=3)？

如果要把所有的3-cluster子集找出来，最后再挑出最大的，无疑是一种很低效的做法。因为总共有2n种情况需要遍历，其中n为DAG的区块总数。在n比较大的情况下，显然是无法完成的任务。

为了提高效率，这里使用了一种贪心算法（Greedy Algorithm）来进行优化，命名为GHOSTDAG。贪心算法在图论上应用非常广泛，尤其是在分类和标记这块，绝大多数情况下都能以最快的速度给出最优解。只有在少数情况下出现次优解，但也只会发生在最优与次优解很接近的情况下。

在实际情况中，坏节点的数量不会到一半，甚至连接近都没有可能。所以坏节点分叉的区块数目肯定会比好节点少很多。也就是说最优解是占据绝对优势的，自然用贪心算法是绰绰有余。

算法步骤如下，以图2为例：

• 首先我们要给DAG图的每一个区块进行打分。分值相当于它直接或间接指向的区块个数，也就是past(B)。如下图所示：

（图片4）

• 从分值最大的区块开始，依次递进把总分最大的路径选出。如果遇相同分值，则随机选取一条路径。如下图所示：

（图片5）

• 上一步选出来的最大值路径是一条单链，所以一定满足3-cluster。接着我们在此基础之上把其余的区块加进去，直至获得最高分值的3-cluster子集。

  我们可以看到除了标记蓝框的区块以外，最高分的就是J了。 接下来我们就看能不能把J包括进去。

  我们已知当前的S = {Genesis, D, H, K, M}, 根据定义可获得anticone(J) = {I,L}。所以anticone (J) ∩ S = ɸ。这显然是满足3-cluster的，于是我们把J加入S里。如下图所示：

（图片6）

• 上一步我们获得新的S = {Genesis, D, H, K, M J}，所以剩下来就数区块L的分值最高。但由于anticone(L) ∩ S = {H, K, M, L}， |anticone (L) ∩ S| = 4 > 3，所以L需要被排除在外，我们于是标记为红色，如下图所示：

（图片7）

• 如法炮制，我们依此类推可以获得红框与蓝框的分类。其中标蓝框的区块就是最大3-cluster子集，也就是好节点产生的区块，会被我们保留。而剩下标红框的就是坏节点产生的分叉，会被我们自动抛弃。如下图所示：

（图片8）

交易的选择

理解了PHANTOM的共识算法以后，我们可以标记出好节点与坏节点产生的区块。但是还剩下一个问题没解决：矿工到底如何选择哪些交易放在区块里？

有人会说这难道还用问吗，当然是看谁给的交易费高咯。

这个策略在区块链里面是没毛病的。因为它不允许分叉，所以每个区块里的交易费都是该矿工独享的，没有其他人过来来抢。在这种情况下，当然是优先选择高交易费来最大化自己的利润。

但是这个策略用在BlockDAG里就有问题了。因为DAG是允许并发的，如果大家都选择最高的交易费，那很有可能在同一时间内，好几个区块记录的都是相同的交易！比如图1中，假设1-1000笔交易中前500个交易的手续费是最高的，那这两个区块存的肯定都是1-500，如下图所示：

（图片9）

但交易费只付一次，所以必然有一个矿工是没法获得交易费的。而且从效率角度来说，DAG高tps的优势自然也荡然无存。

好在矿工是非常理性的，假设自己有50%的概率会失去交易费的话，那自然会选择一种更加稳妥的策略来确保自己的收益。

为了提升自己的期望收益，矿工会选择一些未记录的交易放在区块里，所以这也变相避免了交易冲突的问题，最终会让DAG高tps的特点得到淋漓尽致的发挥。这种更加偏协作化的策略无论对矿工，还是对用户来说都是最有利的。

总结

总的来说，PHANTOM的共识协议可以确保BlockDAG的高tps。作为比特币协议的扩展，确实给去中心化的解决方案带来一丝曙光。本文也是DAG系列的最后一个章节，自此我们的DAG之旅也暂时告一段落了。以后会给大家讲一些新的区块链解决方案，探讨一下还有哪些技术可以让区块链更高效。