DAG Blockchain技术讲解——Byteball原理解析（二）

Byteball的共识算法

主链

在Byteball中，从任何一个顶端单元出发到达创世单元的最优路径称为候选主链（Candidate Mainchain）。最优路径通过选择最优父单元产生，选择策略用于保证整个网络的安全性。不同的候选主链会在某个单元位置交叉（最差的情况是在创世单元交叉），该交叉点称为稳定点（Stable Point）。对于所有候选主链，从稳定点到创世单元的路径完全相同，该路径称为稳定主链（Stable Mainchain）。稳定主链是一条确定的路径，从候选路径变为稳定主链是一个从不确定逐渐变成确定的过程。后续讨论中，如果没有明确区分，主链一般指的是候选主链。

DAG中的每个单元要么直接位于主链上，要么经过较短的路径就能到达主链，主链可以形象地看作是一条连接着许多侧面道路的高速公路。一个单元一旦进入DAG中，它所在的主链也相应确定，因为后续单元只能作为其子单元，而无法更改其父单元。

给定一条主链，与之相关的所有单元均可以在此基础上进行排序，其序号称为主链序号（MCI, Main Chain Index）。创世单元的MCI为0，依次加1直到链尾。对于不在主链上的单元，其MCI等于主链上最先包含（直接或者间接）该单元的那个单元的MCI。MCI代表了从主链视角来看单元在DAG中的总序，对于发生冲突的双花交易，MCI较小的单元为有效单元。

最优父单元的选择策略

• 单元级别：由当前单元出发至创世单元的最长路径长度定义为单元级别（unit level）

• 见证级别：从当前单元开始沿主链回溯，并对路径中不同见证人进行计数（相同见证人只计数1次），当遇到的见证人数足够多时（超过大多数的已知见证人）停止回溯；然后计算停止位置的单元级别，将其称作当前单元的见证级别（witnessed level）。

最优父单元的选择策略由以下三部分组成：

1、在选择最优父单元时，见证级别最高的父单元为最优父单元；

2、如果见证级别相同，则单元级别最低的作为最优父单元；

3、如果两者都相同，则选择单元哈希值（base64编码）更小的作为最优父单元。

那么，从顶端单元出发，只需要递归地在其父单元中选取最优父单元即可形成主链。在上述选择策略中，见证人成为了某个单元看待历史的视角，每个单元可以维护自己的见证人列表，也可以通过witnesslistunit引用其它单元的见证人列表。

• 单元兼容：如果两个单元的见证人列表差别最多一项，则称这两个单元兼容

在选择最优父单元时，仅可以从与当前单元兼容的父单元中进行选择，以保证看待历史视角的连续性。不兼容的父单元仍然被承认，但是他们不能成为最优父单元。特别地，在发出新单元时，如果与所有顶端单元都不兼容，则应从上一级别的父单元中进行选择。

双花问题

在用户地址发出新单元时，要求相同地址发布的所有单元应当直接或间接包含该地址之前所有的单元，即相同地址的所有单元连通（有序或连续）。

• 双花交易：相同地址发出的任何无序的交易都视为双花交易，即使它们没有使用相同的输出，也可称为冲突交易或者矛盾交易。

因此，在相同地址的所有单元都连通的情况下，在路径上出现较早的交易为有效交易。如果有攻击者特意制造出双花交易，那么可以通过主链序号来解决，主链序号较小的交易为有效交易。

上图给出了一种攻击场景，攻击者制造出一条影子链，并在上面发布双花交易。当影子链接入到真实的DAG中时，根据最优父单元选择策略，影子链上的见证人个数少，因此它不会成为主链的一部分，从而解决了这种场景下的双花问题。值得注意的是，如果大多数见证人与攻击者合谋，并在其影子链上发布单元，则攻击者有可能攻击成功。

单元成为稳定点的条件

根据上面的分析可知，所有候选主链在稳定点之后到达创世单元的路径完全相同，即稳定主链成为最终状态。这也意味着，从稳定主链上单元直接或间接包含的那些单元也将无法再被篡改。因此，只要随着新单元的不断加入，稳定点可以不断地向后扩展，且不同的用户节点的稳定点扩展方式保持一致，则全网的所有用户节点可以实现共识。

对于所有单元，如果只保留其与其最优父单元的连接，则DAG将退化为一棵树T，所有的候选主链只可能从这棵树中产生。下面根据稳定点是否具有多个子单元分两种情况对稳定点的扩展方式进行讨论。

• 当前主链：在DAG中，从不同顶端单元出发具有不同的候选主链，从见证级别最高的顶端节点出发的候选主链称为当前主链（Current Mainchain）。

假设当前稳定点的见证人列表为W，单元级别为l，它只有一个子单元，如上图所示。以W作为见证人列表，从当前主链的顶端节点进行回溯，直到遇见W中的大部分见证人，记录这些见证人发出的单元中的最小见证级别，记作minwl。如果minwl>l，则扩展当前稳定点至其子单元，否则不进行扩展。由于大部分见证人已经在当前主链上了，后续这些见证人发布的单元将继续支持当前路径，从而使得稳定点可以向前扩展。

假设当前稳定点具有多个子单元，如上图所示。在当前稳定点的所有子单元中（除了位于当前主链的子单元），找出见证级别大于当前稳定点的子单元，并将其中最大的单元级别记为maxl。也就是说，除了当前主链外，当前稳定点其它分支上的单元见证级别将不超过maxl。如果minwl>maxl，那么稳定点可以沿当前主链向前扩展。

随着稳定点的不断前进，稳定主链及其相关单元的状态被最终确定下来。只要DAG中的单元相同，其形成的主链和稳定点也是相同的。因此，不同的用户节点，只要最终收到相同的单元，它们最终将达到一致的状态。

（原标题：DAG Blockchain之Byteball原理解析（二））

来源：

创业不易，用心坚持，希望您多多支持！

打赏

感谢您的支持，我会继续努力的!

扫码打赏

打开支付宝扫一扫，即可进行扫码打赏哦