阿里云区块链官网:基于图结构的共识算法研究

  在Trias同“北大软微-八分量协同创新实验室”联合开展的学术沙龙上,北京大学方跃坚副教授同大家分享了《基于图结构DAG(Directed Acylic Graphs)对共识算法的价值的思考》。

  

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

  图结构算法研究背景

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

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

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

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

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

  Inclusive blockchain protocols

  由以色列学者提出,可被视为最基本的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 魏明也指出,现在硅谷的许多投资机构都已经把注意力从人工智能转移到区块链。

  即使到现在,还有很多人认为区块链就等于炒币,其实并不然,与人工智能,云计算,大数据一样,区块链也是近年来的一项新技术,只是此前外界赋予了它过多的金融属性。Trias此后会继续和北大软微学院开展区块链研讨技术沙龙,也欢迎更多有识之士参与进来,分享大家的知识和见解,谢谢大家。

  原作 | 方跃坚

  整理 | 郑辰

  出品 | Trias团队

文章内容系本站作者个人观点,不代表本站对其观点赞同或支持,文章的版权归该作者所有。如需转载,请注明文章来源。本文地址:http://www.cis.net.cn/kejikuaixun/43952.html
留言与评论(共有 条评论)
验证码:

最新文章

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

科技快讯
在Trias同“北大软微-八分量协同创新实验室”联合开展的学术沙龙上,北京大学方跃坚副教授同大家分享了《基于图结构DAG(DirectedAcylicGraphs)对共识算法的价值的思考》。以下是方教授带来的此次分享内容:图结构算法研究背景

ShowCoin今晚交易!李笑来、赵东、同道大叔2018年联合首投项目会有多少倍?!!

科技快讯
正文Coin900币新交易所发布公告,将在1月8日18点18分。老王没有记错的话,这应该是李笑来、赵东、同道大叔等2018年开年他们联合搞的第一个项目,。在此之前梳理一下个项目:秀币(ShowCoin)是世界个基于区块链和智能合约的点对点络技术基础之上,针对直播类数字娱乐内容分发服务和产品设计的数字加密虚拟货币。它及围绕它设计的经济体系

合并挖矿——集体利益和51%攻击的灵丹妙药?

科技快讯
那些表面上熟悉挖矿术语的用户,总是认为合并挖矿的概念与池和混合生产相关联。然而,事实并非如此。今天我们将定义术语并找出为什么合并挖矿对年轻区块链和小型矿商都有利。采矿池——利润如何摧毁区块链几年前,在加密

区块链趣评:传统帮会洪门发布洪币,首发价格1美元

科技快讯
一分钟吐槽:韭菜心路历程分享1、传统帮会洪门发布洪币,首发价格1美元传统帮会洪门发布洪币(白皮书已公开)。洪币首发价格1美元,第一阶段发行的洪币将于6月6日开放交易。洪币发行总量为10亿枚,数量恒定,不增发。趣评:大哥别杀我!显

加强版的互联网:区块链引领去中心化2.0

科技快讯
前言:很多加密货币的白皮书都会提到“去中心化”这个热门词,本文将首先从经济学上来展示去中心化的普遍性,分析我们现在经济生活的去中心化现象以及对未来区块链技术去中心化的发展进行展望。如果你在百度上搜索“区块链+去中心化”,那么你可以得到超过五百多万条的搜索结果,并且所有的加密货币在介绍时候都会频繁提到“去中心化

趁着现在,捡一些便宜货吧,11月1日行情分析

科技快讯
还记得一年前,狂人说过一句话,当潮水褪去的时候,才知道谁在裸泳,不知道此时此刻,每个人的心情如何,但我敢肯定的是,懂得控制仓位的人,才最容易稳住心态,希望在未来,每一个坚持下来的人都不再裸泳,看到大势已去的时候能够全身而退,每个人都需要经历熊市才能成长。当牛市的时候,每一次回调都是诱空,

七家国际大公司正在区块链领域上公开招聘

科技快讯
如果你想开始使用目前最有前途的新兴技术之一,那么现在就看看这个在区块链中招聘的雇主名单。现在,区块链的位置可以与21世纪初的一种云技术相媲美。虽然它还没有渗透到公众的意识中,技术和商业部门都在讨论可能的应用程序。从身份认证到能源交易的一切都有可能(而且已经在用这种技术进行了)。马克·柯蒂斯(MarkCurtis)不久前在Si

区块链在物联网中的九大应用体现

科技快讯
当前,物联网产业进入井喷期,连接空间不断扩充,产业发展呈现出“面向行业,以IoT平台使能为基础,寻求SaaS服务与数据变现”的态势,具有巨大的发展潜力。然而现阶段物联网产业发展仍面临诸多挑战,主要表现在面对日益增多的物联网需求,如何提升传统物联网产业能力,确保数据的隐私性、安全性、连续性及交互兼容性。传统物联网产业通常采用

区块链——支付解决方案的前沿技术

科技快讯
PaymentAsia是在东南亚地区领先的电子支付解决方案和电子商务管理公司,并且在全球范围内提供商业支付解决方案。PaymentAsia的洪伟廉表示:“我们决定对区块链进行投资,以保持我们支付解决方案的质量,并帮助商家获得

融数链(FBT)网格化多维数据价值交换生态

科技快讯
Fusionblock致力于打造全球首个数值交换生态系统。借助大数据产业基础,提炼数据为抽象事物对象,打造为解决数据服务工作流及商业流程的生态交易链,是新一代分片分层综合架构下的一个多方事务协同管理,协同操作,跨主体的复杂网格结构商业生态。在现有区块链技术基础之上Fusionblock强化隐私安全,并结合多层次技术与设计创新