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

全文数：5033

阅读时间：15分钟

上周，应国内小伙伴的要求，我做了一个在线公开课，给大家分享一下当下很火的DAG技术。 由于之前做过一段时间的研究，在公众号上写过两篇文章，所以这方面的经验还是比较多的。

大多数人在刚开始了解区块链时都有同样的感受：各种眼花缭乱的新名词如雨后春笋般涌现，仿佛进入了另一个维度的世界。 虽然是软件层面的技术，但即使是专业出身的coder，还是被张二和尚看的一头雾水，就好像他的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。

块DAG

关于DAG的定义，在之前的“”中已经给大家讲过了，这里不再赘述。 今天要讲的是更直观的东西。

其实Blockchain和BlockDAG都是很抽象的东西。 如果说区块链是一系列相连的盒子，那么BlockDAG可以想象成一个网络，如下图所示：

（图2，来自PHANTOM和GHOSTDAG的论文）

图中的Genesis是创世区块，从B点到M点都是区块。 你会发现这些区块直接或间接指向创世区块。 这和IOTA[2]的DAG概念是多么的相似啊！

点意义

初始点

路径方向

块DAG

堵塞

创世区块

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

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) 和 Future(H) 之外的所有块 = {B,F,I,L}

tips(G) = 端块集 = {M,J,L}

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

这是共识协议解决的问题。 对于 IOTA DAG比特币的作用和用途，其共识协议是 Tangle [2]。 至于BlockDAG，它肯定也有自己的共识协议。

基于 BlockDAG 的共识协议 - PHANTOM

仔细观察我们会发现，单链表其实就是DAG的一种，所以BlockDAG上的共识协议可以看作是比特币协议在区块链上的扩展。 基于 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 簇。 对于一个子集是否为k-cluster，PHANTOM给出了明确的数学定义：

子集 S ⊆ G 称为 k-簇，如果∀B ∈ S : |anticone (B) ∩ S| ≤ k。

简单的说，这个子集中任意块的反锥与子集本身的交集不能超过k。 有了这个定义，我们就可以使用标准算法来判断这个子集是否是一个k-cluster。 而我们的目标是在所有满足条件的子集中找到最大的一个。

接下来，我们可以设计一个分类算法来区分好节点和坏节点的块。 由于好节点的块集是图中最大的k-cluster子集，剩下的部分自然来自于坏节点。 所以算法的核心是找到最大的k-cluster子集。

如何找到最大的 k-cluster 子集（k=3）？

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

为了提高效率，采用贪心算法（Greedy Algorithm）进行优化，命名为GHOSTDAG。 贪心算法广泛应用于图论，特别是在分类和标记方面。 在大多数情况下，他们能够以最快的速度给出最优解。 次优解仅在少数情况下出现，但仅当最优解和次优解非常接近时才会出现。

实际情况下，坏节点的数量不会是一半，甚至几乎不可能连上。 因此，坏节点分叉出的区块数量肯定会比好节点少很多。 也就是说最优解有绝对优势，自然用贪心算法绰绰有余。

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

(图4)

(图5)

(图6)

(图7)

(图8)

交易选项

了解了 PHANTOM 的共识算法后，我们就可以标记好节点和坏节点产生的区块。 但仍然存在一个问题：矿工究竟如何选择将哪些交易包含在一个区块中？

有人会说不用问了，当然要看高昂的手续费是谁出的。

这种策略在区块链中很好。 因为不允许分叉，每个区块的交易手续费都是矿工独享的，没有其他人来抢。 在这种情况下，当然优先考虑选择高交易费用来最大化你的利润。

但是这种策略在 BlockDAG 中使用时是有问题的。 因为DAG是允许并发的，如果每个人都选择最高的交易手续费，很有可能几个区块同时记录同一笔交易！ 例如在图1中，假设1-1000笔交易中的前500笔交易手续费最高，那么这两个区块必须存储1-500，如下图所示：

(图9)

但是交易费只交一次，所以肯定有矿工拿不到交易费。 而且从效率上看，DAG的高​​tps优势自然没有了。

幸运的是，矿工是非常理性的。 假设他们有 50% 的概率损失交易手续费，他们自然会选择更安全的策略来保证自己的利润。

矿工为了增加自己的预期收益，会选择一些没有记录的交易放在区块里，这样也变相的避免了交易冲突的问题，最终让DAG的高​​tps的特性得到发挥。 这种更具协作性的策略对矿工和用户都是最有利的。

总结

总的来说，PHANTOM的共识协议可以保证BlockDAG的高​​tps。 作为比特币协议的延伸，它确实给去中心化的解决方案带来了一线希望。 本篇也是DAG系列的最后一章，我们的DAG之旅到此告一段落。 以后我会跟大家讲一些新的区块链解决方案，讨论还有哪些技术可以让区块链更高效。

相关文章：

【1】

【2】

挡君子

以散文般的代码风格征服各大世界500强企业，坚信不会唱歌的作家不是好码农。 曾经闭关研究过比特币的10000码比特币的作用和用途，最后修成正果，瞬间成佛。

科技|投资|文学|鸡汤