Byteball技术剖析之一：DAG账本与最优树

在众多的基于DAG（有向无环图）技术的区块链项目中，Byteball项目的技术白皮书写得最为详尽。个人认为几乎所有的在Byteball项目之后提出的区块链DAG项目，都得益于Byteball的技术白皮书。其下载地址为： https://byteball.org/Byteball.pdf

虽然Byteball技术白皮书用了较长的篇幅、非常详尽地论述了DAG技术，但真正值得分析、总结、借鉴的技术核心，其实只有两点：

1、MainChain（主链，简写为MC）的生成算法；

2、基于主链索引号（Main Chain Index，简写为MCI）的交易定序算法；

弄明白这两点技术核心之后，结合对比特币和以太坊的深刻认知，任何人都可以自由发挥，自创武功，自成一家，设计出独具特色的区块链新项目。

然而领悟这两点技术核心之前，先得储备一些基础知识。因此，我计划写出一系列的文章，每篇以单点突破的方式，尽可能地以「比Byteball白皮书更容易读懂」的方式，逐步完成对它的技术剖析。

DAG账本的构成：

在Byteball的设计方案中，交易数据作为顶点V，哈希指针作为有向边E，从时间角度来看，先产生的交易会被后续产生的交易通过哈希指针引用，通过这种方式产生DAG账本。在其他同类技术项目中，顶点V不一定是单独的交易（Tx-DAG），而可能是由多笔交易构成的区块（Block-DAG），但是这些项目的整体设计思路及数据结构与Byteball是极其类似的。

在比特币和以太坊的链式系统中，矿工节点会对一笔交易进行全网广播，然后包含了该笔交易的区块会被再次广播，交易数据被广播了两次，显得有些冗余。并且在链式系统中，同一时刻不同矿工节点产生的多个合法区块中，最终只能有一个被系统接纳，交易并发处理能力与系统吞吐量难以提升，经常会发生交易拥堵。在以Byteball为代表的DAG系统中，以交易数据作为顶点V，无需对交易做二次广播，节省了网络资源与处理时间，增加了系统的交易吞吐量与交易并发度。

引用即确认：

由于网络传输延迟，不同的计算机节点很难同时、同步接收到同一笔交易数据，因此后续产生的交易应当尽可能多地引用之前未被引用的合法交易，未能通过验证的不合法交易会被丢弃。当前交易引用之前的交易，也就等同于对之前的交易进行了确认。

交易顶点与哈希指针构成DAG

最优父指针与最优树：

依据「引用即确认」的原理，除了创世顶点（G）之外，其他每个顶点在创建的时候，都会尽可能多地引用之前的节点（父顶点）。使用Byteball设计的特定选择算法，可以从每个顶点的多个父指针中选出唯一的最优父指针（下图中加黑加粗的箭头线边），这样就可以从DAG账本中提取出一个最优树。

由DAG生成的最优树

从这个最优树中，可以找出唯一的一条主干链（MainChain）。需特别注意的地方是：这条主干链不一定是最长的枝干（不符合比特币最长链算法），也不一定是最重的子树（不符合以太坊GHOST算法）。

在下图中，创世顶点G及其下面挂载的紫色顶点构成的子树，由于不符合主干链的要求，虽然长度和重量都可以占优势（继续添加更多的紫色顶点和子分支就能做到最长、最重），但并没有被选择为主干链。而G及其后面的黄色顶点构成的子树，才是主干链。

Byteball采用Witnesses见证人模式，设计了主干链和最优父指针的选择算法，可参考后续的技术剖析文章。

最优树的主干链