区块链贝勒爷是谁:DAG与区块链简介(从零开始学区块链 184)

  最近有人问DAG相关的东西,今天就来说说关于DAG的话题,DAG是一个数据结构名词,有项目用了这种复杂的结构来存储交易数据,本文只能粗略探讨一下

  如果你还记得大学开设的《数据结构》科目,DAG出现在那本书的最后一章“图论”中,图应该是最复杂的数据结构了,所以当时我们学校并没有教最后一章,只是让感兴趣的人自学,由于后来的工作中最多用到B+树,对于图的学习只是停留在表面,只是记得存储图最好的方式是采用“邻接多重表”这种结构。

  什么是DAG

  图和树一样,是一种数据结构,在计算机科学中往往为了避免复杂的数据结构影响开发和数学建模会将结构进行简化或者约束,比如“树”这种结构其实根据定义也是很复杂的,当时真正用的时候“二叉树”用的最广泛,二叉树就是规定一个根只能有两个叶子。

  所以在图论中,为了简化这种结构,分为有向图和无向图两大类,在无向图中进一步进行约束形成了DAG(有向无环图),所谓无环是指它是由集合的顶点和有向边构成,每条边连接一个顶点到另一个,这样,在一些顶点v开始,沿着有序的边,最终循环回再次到V是不可能的,其实图是树的一种泛化,真正在用的时候一般会通过深度优先或者广度优先规则把图拆成“森林”就是多颗“树”,而DAG图由于规则的定义更容易拆成一颗“树”,这也就是为什么图有很多种,而DAG应用最为广泛的原因。

  

  上图从左到右分别是二叉树、DAG图、和普通有向图的图例,可以在最右侧的图明显看到存在一个“环”,此图可以非常容易的理解什么叫DAG图了。

  DAG与区块链

  目前采用DAG作为存储结构的代表项目有dagcoin、Byteball、Iota,我看过前两个的白皮书,dagcoin和byteball白皮书在DAG部分完全一致看其中一个即可,很多人说采用了DAG已经不属于区块链了,因为传统区块链采用“链”式结构,其实传统区块链中存在多条链的分支更类似一棵树,而最终确认的是最长链,也就是在树的结构中找到一条合法的链而已。

  而采用了DAG结构的项目,为了避免双花问题,还是有所谓的”主链“概念,其实就是经过见证人认定的最短路径了,所以我认为DAG还是应该归类到区块链范畴,其本质没有大的改变,只是采用了DAG结构,效率更好,对于没有”异议“的交易,可以采用DAG进行打包,Byteball将其定义为”球“,图论中有详细的描述,也是为了减少复杂度,如下图:

  

  相比传统链式结构,采用DAG面临的双花问题会非常复杂,根据Byteball的描述,采用了见证人主链概念,维持一条公认的主链作为凭证,而其他分支只要不和主链冲突都可以视为有效交易,我个人认为采用DAG并不能减少目前区块链面临的存储空间问题,当然DAG可以提升效率,由于其数据结构非常复杂,对编码要求更高,安全性有待观察,对于算力攻击问题,我有个担忧,希望与DAG研究深入的人交流,就是传统链式结构,你必须保持持续的算力优势才能更改交易,否则最终长链可以将短期算力优势形成的链废掉,但是采用DAG分块的方式,你只需要在一定时间内的算力保持优先形成一个DAG块,那么是不是今后所有的交易都会继承这个错误呢?

  区块链最让人感兴趣的地方就是不断的创新和敢于利用新技术,当然就数据结构理论从70年代以来基本上没有什么变化,只是传统的软件项目很少利用到这些理论,计算机图形学是我看到的利用复杂数据结构最多的地方,而且商业项目能用到B+树已经是极限了,而区块链的发展让人惊喜,理论联系实际的好榜样!

  最后说一句,区块链技术终究是计算机技术的一种,没有必要将其神话,所有的结构和实现都可以在《数据结构》本科教材中找到,但是要灵活运用在业务场景中,需要取舍和经过实践检验,另外我会持续关注DAG结构在新型项目的应用,有机会和大家进一步交流

  来源:区块链大师 微信号 :DACMaster

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

最新文章

DAG与区块链简介(从零开始学区块链 184)

科技快讯
最近有人问DAG相关的东西,今天就来说说关于DAG的话题,DAG是一个数据结构名词,有项目用了这种复杂的结构来存储交易数据,本文只能粗略探讨一下如果你还记得大学开设的《数据结构》科目,DAG出现在那本书的最后一章“图论”中,图

范爷被处逾8亿追罚,税务管控区块链能做些什么

科技快讯
小崔“手撕”范冰冰三个月之后,范冰冰被处以超过8亿元的罚款及追缴款已是实锤。各行各业偷税漏税事件屡见不鲜,近几年兴起的区块链技术有望重整依法纳税之风。今日,新华社记者从国税总局及江苏省税务局处获悉,范冰冰“阴阳合同”一案已经查清,范冰冰的确利用拆分合同的方式偷逃个人所得税,根据法

360爱得钻(AD钻)是什么及爱得钻邀请码!

科技快讯
「爱得钻」由360商业产品团队开发,是一个基于区块链技术的商业化探索。「爱得钻」用区块链的方式将用户的个人信息价值及注意力权证化,以去中心化的形式实现广告主信息与用户注意力之间的直接连接,并将广告营销中原本分成给中

行业的生态搭建者,开放共赢计划成就中小数字货币交易所

科技快讯
最近币市处在熊市之中,加密货币市值不断缩水,但是各大主流及新兴交易所却动作频频,时不时给人带来一些惊喜。2018年6月19日,国内最老牌的加密货币交易所之一OKEx发布公告:启动加密货币交易所共赢计划。市场迅速做出反应,当天OKEx的平台代币OKB暴涨34%。1:交易所共赢计划什么是OKEx的交易所共赢计划?一句话概括就是连锁交易挖矿。怎么

可信智能合约平台Trias获得NGC Fund I 数百万美元投资

科技快讯
近日,可信智能合约平台Trias获得NGCFundI数百万美元投资,并与NGC建立业务合作关系。作为兼容原生应用程序的新一代智能合约运行平台,Trias旨在定义支持通用应用程序的新一代公链体系,并在此基础上构建可信赖的通用应用程

玉溪红塔集团褚时健(云南红塔褚时健还在吗)

科技快讯
据可靠消息称,原红塔集团有限公司和玉溪红塔烟草(集团)有限责任公司董事长、褚橙创始人褚时健去世,享年91岁。网易号外证实的消息显示,褚时健是在今日中午于玉溪市人民医院过世,追悼会日期目前待定。个人履历:燃情年代1928年1月23日,

交易数字资产需要练习,就像弹钢琴一样要练习

科技快讯
在你做研究,或者只是随意浏览币圈文章的时候,有没有看到过这样的标题:如何通过交易比特币购买你的第一辆宝马如何通过投资某某币环游世界如何通过某某黄金法则让你财富自由好吧,太多了。我看到有人说:“今天刚辞掉工作,要全职交易比特币。”这样的事情让我感到不安,因为他们只瞄准容易受骗的人,只有一个目标,尽快拿到钱。他们都非常确

区块链终于有机会赶超加密货币

科技快讯
从组织上讲,这仍然是区块链的早期阶段。如今,人们还只是刚刚开始探索区块链和分布式账本技术的潜在影响。例如,IBM商业价值研究所(IBMInstituteforBusinessValue)和牛津经济学院(OxfordEconomics)最近对1,314名汽车

OKEx再现巨额爆仓,币圈暴跌一夜回到解放前

科技快讯
2018年9月5日北京时间17:45分,币圈老大比特币和老二以太坊开始下跌,市场本以为是正常的回调之际,不到几分钟的时间,币圈开始全线大跌,比特币1小时跌了300美元,以太坊1小时跌破接近20美元,其余币种大幅很快接近10%的幅度,后续小幅反弹调整后继续大跌,今早更是出现大

比特币的未来:基于当前发展的判断

科技快讯
(原标题:大起大落比特币:疯涨之下的冷思考)近期,比特币价格结束近3个月以来的连续飙涨,开启大起大落模式,但价值仍可与黄金相比拟。比特币价格7月4日亚盘高位整固。BITSTAMP公布的报价显示,比特币/美元(XBT/USD)震荡后冲高,一度触及2580水平,当日亚盘持续走高至2600附近。尽管自诞生以来,比特币本身是否存在价值一直都有较