基于图结构的共识算法研究

昕阳小编 100 0

在Trias与“北大软微八组件协同创新实验室”联合举办的学术沙龙上,北大方副教授分享《基于图结构DAG(Directed Acylic Graphs)对共识算法的价值的思考》。

基于图结构的共识算法研究-第1张图片-昕阳网

以下是方教授这次带来分享的内容:

众所周知,现有的共识算法并不完善。以比特币为例。比特币使用PoW共识算法,面临严重的效率问题。但比特币受限于共识算法和块容量,每分钟只能处理2000笔左右的交易(比如说每秒7笔交易,主要看交易规模)。相对较慢的速率使得比特币网络上的拥塞成为常事。比特币的效率瓶颈在于其基于最长链串行签名的验证。因为在一维链式结构中,块是严格按照时间顺序生成的,需要广播完最后一个块才能生成下一个块,需要所有节点一起认证,这是一个漫长的过程。为了解决这个问题,可以引入图结构DAG,降低了块生成过程的顺序要求,有利于块生成过程的并行性,即可能同时生成两个或两个以上的块。提高并行性会大大提高计算速度,突破一致性算法的效率瓶颈,但也会带来一些冗余或错误块等不良影响,需要对其进行一般的排序和验证来筛选。因此,基于DAG的一致性算法的关键在于节点之间的关系和最终正确块的选择方法。接下来我们来分析一些具体的项目算法。

是由以色列学者提出的,可以看作是最基本的DAG一致性算法。它与最长链一致性算法的唯一区别是引入了DAG图结构。块由最基本的父子节点连接,遵循最长链算法。根据块的时间关系,当链长相同时,选择时间较早的块。

基于图结构的共识算法研究-第2张图片-昕阳网

其效率可以上图所示。红色代表最佳效果,蓝色代表使用图计算的实际效果,绿色代表未使用的效果。

最大k聚类算法选择块,其总结可以概括为:只有当有块加入的DAG图的逆锥的节点数<=k时,即除了区块链可达的路径上的块和可达该块的路径上的块之外的其他块的个数才能加入DAG。在下图中,添加到DAG的正确数据块标记为蓝色,而未添加到DAG图中的不正确区块链标记为红色,即可能是恶意数据块或冗余数据块。

基于图结构的共识算法研究-第3张图片-昕阳网

以此图为例。比如节点I的圆锥包括A,B,F,C,D,即可达节点数,而逆圆锥节点是所有蓝色节点减去圆锥节点,只剩下G和J,只有两个。e,H,K H和K被认为是多余的,将不被接受。总之,一个节点的倒锥越小,该节点与其他节点的联系就越强。它的优势在于扩展性好,但不能保证强线性排序和livebess。即难以杜绝恶意挖矿和延迟发布,抵御此类攻击的能力略显不足。

块之间也是以一种基本的方式(即父子节点连接)连接,主要是通过区块链投票算法,优先选择锥形节点数量多的块排在第一位,一般情况下对块进行排序。如果两个块有冲突,它会选择总排序前未知的块。已经有X和Y两个块了,是先放X还是先放Y?因为6-8块能看到X块,看不到Y块,所以会把X放在前面。同样,9-11块只能看到Y块,他们会把Y块放在前面。块12根据图结构认为X在前面,而块1-5同意X在前面是因为结构中更多的块认为X应该在前面。

基于图结构的共识算法研究-第4张图片-昕阳网

本项目算法的连接方式是在基本连接的基础上,增加了索引连接。所谓索引连接,就是在这个块之前找到其他块(非亲子)连接在一起,在这尚力财经小编2022个基础上,效率也可以大大提高。 据悉,清华姚班曾参与亚马逊EC2云2万机器节点的实验,实现了5.76GB/h的吞吐率,实现了每秒6400笔交易,吸引了众多国内外资本的关注。算法还是幽灵算法,类似以太坊。GHOST算法是一种主链选择协议,其基本原理是包含最大数量的子树,即根块对应链上的节点所连接的节点总数是根据这条路径确定的。

项目块通过基本连接方式(父子块)连接,根据随机查询和基于DAG图的两种颜色的颜色置信度值选择正确的事务。每个节点初始化都是无色的。每个节点随机查询周围的其他节点,统计周围节点的颜色(红色或蓝色)。查询k次后,它选择颜色统计量最大的颜色作为自己的颜色,对改变后的颜色的置信度值加1。引入DAG图后,其中的每个节点都会更新祖先事务的置信度值(加1)和祖先提交的perfecter事务。如果一个事务中的所有祖先事务(父节点或父节点之上的节点)都是优先的,则该事务是强优先的,并且系统随机选择一个节点来查询一个事务。如果它返回一个强烈首选的交易,投票数增加1。当交易中的投票数达到一定阈值,或者交易通过一定次数的成功查询,则判定交易正确。

方副教授对以上五个项目的算法进行了简单介绍,并表示基于图结构的算法研究在国内外方兴未艾,还有很多有创意的新算法有待研究。Triacto魏明还指出,现在硅谷的许多投资机构已经将注意力从人工智能转移到区块链。即使是现在,仍有许多人认为区块链等于投机,其实不然。和人工智能、云计算、大数据一样,区块链是近几年的新技术,但被外界赋予了太多的金融属性。Trias将继续与北京大学软微工程研究所合作举办区块链研讨会技术沙龙。也欢迎更多有识之士参与进来,分享自己的知识和见解。谢谢你。

原创|方整理|陈政制作| Trias团队

标签: 2022

抱歉,评论功能暂时关闭!

微信号已复制,请打开微信添加咨询详情!