分辨DAG与区块链的差异简介！

最近有人问DAG相关的东西，今天说说关于DAG的话题，DAG是一个数据结构名词，有项目用了这种复杂的结构来存储交易数据。

什么是DAG

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

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

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

DAG与区块链

很多人说采用了DAG已经不属于区块链了，因为传统区块链采用“链”式结构，其实传统区块链中存在多条链的分支更类似一棵树，而最终确认的是最长链，也就是在树的结构中找到一条合法的链而已。

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

相比传统链式结构，采用DAG面临的双花问题会非常复杂。根据Byteball的描述，采用了见证人主链概念，维持一条公认的主链作为凭证，而其他分支只要不和主链冲突都可以视为有效交易，DAG可以提升效率，由于其数据结构非常复杂，对编码要求更高，安全性有待观察。后续持续关注DAG结构在新型项目的应用，和大家一起进一步交流。

商业合作

添加时备注“商业合作”