区块链图结构公式算法解析

图结构算法研究背景

众所周知，现有的共识算法并不完美。以比特币为例，比特币采用的是PoW共识算法，而PoW算法面临着严重的效率问题，而比特币受限于共识算法和区块容量，每分钟只能处理约2000笔交易（一说是每秒7笔，主要取决于交易大小），相对缓慢的速率使得比特币网络上的拥堵成为常事。

比特币的效率瓶颈，主要在于其验证需基于最长链的串行签名。因为在一维度的链状结构中，区块的产生严格按照时间顺序产生，需要上一个区块进行广播后才能产生下一个区块，并且需要所有节点共同认证，而这个过程较为漫长。

为解决这个问题，可以引入图结构DAG，降低了区块产生过程的顺序要求，有利于区块产生过程的并行性，也就是说，可能有两个甚至更多的区块共同产生。

提高并行性将会大大提高计算速率，突破共识算法的效率瓶颈，但同时也会带来产生冗余或错误区块等不良影响，需要进行总的排序和验证对它进行筛选。因此基于DAG的共识算法的关键之处在于节点之间的联系关系和最终正确区块的选择办法。

下面我们分析一些具体的项目算法。

由以色列学者提出，可被视为最基本的DAG共识算法。它和最长链共识算法的唯一区别在于引入了DAG图状结构。区块之间由最基本的父子节点进行连接，并遵循最长链算法，按照区块的时间关系，当链长度相同时选择时间较早的区块。

其效率可以如上图所示，红色代表最优效果，蓝色表示采用图计算的实际效果，绿色代表未采用的效果。

phantom

最大K聚类算法选择区块，其概要可归纳为：只有一个带加入区块的DAG图的反锥面的节点数＜=K，即除该区块链能到达的路径上的区块和能达到该区块的路径上的区块外的其它区块数，该区块才能够加入DAG。

在下图中，加入DAG的是正确区块，标为蓝色，而不加入DAG图的是非正确区块链，即可能是恶意或冗余区块，标注为红色。

以该图为例，比如节点I，I的锥面包括A，B，F，C，D，即能到达的节点数，而反锥面节点即是所有蓝色节点减去锥面节点，只剩下G和J，只有2个。而E，H，K三个被认为是冗余的，不予以采信。

一言以蔽之，一个节点的反锥面越小，该节点与其它节点的联系性越强。其优点在于具有良好的扩展性，但不能保证强的线性排序和livebess。即难度杜绝恶意挖矿，延迟发布的情况，在抵抗这种攻击的能力略显不足。

Specture

区块间也是通过基本连接方式（即父子节点连接方式），主要通过一种区块链投票算法，并优先选择所在锥面节点总数多的区块排在前面，对区块进行总排序，如果两个区块相冲突，它将选择总排序后未知靠前的区块。

对于已经有两个区块，X，Y，是将X还是Y放在前面呢？因为区块6-8可以看到区块X，看不到区块Y，他们会把X排在前面，同样的，区块9-11只能看到区块Y，它们会把区块Y排在前面，区块12根据图结构认为X排在前面，而区块1-5一致认为X在前面是因为结构中更多的区块都认为X应该在前面。

Conflux

该项目算法的连接方式在基本连接的基础上，又加进了索引连接。所谓索引连接，指的是此区块之前发现其他区块（非父子）也会连接在一起，在此基础上也能大幅度提升效率。据悉，清华姚班曾参与一次实验，在亚马逊EC2云用2万台机器节点实验，达到5.76GB/h的吞吐率，每秒实现了6400个交易，吸引了国内外许多资本的关注。

其算法依然是GHOST算法，与以太坊相似，GHOST算法是一种主链选择协议，以包括子树数目最多为基本原则，即根据这条路径从根区块对应链上节点连接的节点总数决定。

Snowflake to Avalanche

该项目区块之间由基本的连接方式（父子区块）所连接，根据随机查询和基于DAG图的二着色的颜色信心值选择正确的交易。

每个节点初始化都是无色的，每个节点随机查询周围的其他节点，对周边节点的颜色（红色或蓝色）进行统计，在查询K次之后，选择颜色统计大的作为自己的颜色，并对改变的颜色信心值加1.

在引入DAG图之后，其中的每个节点在改变颜色的同时，都会更新祖先交易的信心值（加1），并更新祖先提交的优先（perfer）交易。

倘若交易中的所有祖先交易（父节点，或父节点之上的节点）均为优先（prefer），则该交易为强优先，系统随机选择一个节点查询一个交易，如果返回的是强优先交易，则投票数量加1.

当该交易投票数达到一定的阈值，或者交易通过到达一定数量的成功查询，则该交易被判定为正确。

结语

方跃坚副教授对上述5个项目算法进行了简明的介绍，并表示现在的国内外基于图结构的算法研究方兴未艾，还有很多极具创意的新兴算法有待研究。Trias CTO 魏明也指出，现在硅谷的许多投资机构都已经把注意力从人工智能转移到区块链。