您当前位置: 首页> 资讯> 工程上DAG算法是如何实现共识的

热门标签

热门动态

工程上DAG算法是如何实现共识的

作者:链大全 日期:2018-10-16 18:11:00


有向无环图DAG,图论/算法中有时也称为有向无环图DAG ( Directed Acyclic Graph)。所谓有向无环图是指:任意一条边有方向,且不存在环路的图。首先它是一个有向图,其次这个有向图的任意一个顶点出发都没有回到这个顶点的路径,是为有向无环;
 

DAG不一定能转化为树,但是树一定是一个DAG;
 

DAG可以执行拓扑排序。

 

生活和工程中的许多事例都能转化为DAG模型,比如:

 

有n个矩形,大小不同,导致有些矩形能够嵌套进另一些矩形。告诉你这些矩形的长和宽,让你找出尽可能多的矩形,使它们能依次嵌套在下一个矩形内。乍一看这个问题和DAG没有任何关系。但是仔细想想,如果一个矩形能够嵌套在另一个矩形内,那不就正好有一条[边]连接着这两个矩形(矩形看作顶点)吗?也就是一个矩形的边指向另一个矩形的边。同时一个矩形显然是无法自身嵌套自身的,所以可证明无环。因此,这是个DAG。

 

工程上是如何实现以DAG算法为共识的。

 

我们今天来看下具体的业务流程,从一笔交易的发起,到交易入块的整个逻辑。

 

 

DAG的实现

 

1、我们启动一个ethereum节点和一个DAG节点,它们之间是通过proxy进行连接。

 

2、ethereum调用proxy把交易传到DAG节点,DAG节点调用Core的AddTransctions把收到的交易加入到transactionpool里。

 

3、gossip心跳检测到需要发起gossip,便会创建一个新的event,把transactionpool的交易全部打包到event里,然后插入到Store里。

 

4、随机选取一个peer,发起gossip,从目标peer拉取自己不知道对方知道的event,并把自己知道的event传给对方。

 

5、拿到对方返回的event,调用Core的EventDiff来合并Event,并增加pedding区的Event,然后执行RunConsensus,来DivideRounds,调用DecideFame决定famous witnesses。

 

6、通过多次的gossip,famous witnesses被确定,然后调用FindOrder去决定roundReceived和consensusTimestamp,然后排序。

 

7、调用handleNewConsensusEvents取出新共识过的event,并把里面的交易打包到一个块里,清空pedding区。

 

8、把区块返回到ethereum,ethereum执行区块里的交易,并把账本状态返回到DAG,DAG把账本状态入块,然后签名,再把签名广播到其他DAG节点,其他DAG节点收到签名,验证无误,与自己的签名合并入块,再把自己的签名广播。

 

DAG主链(哈希图谱)逻辑

 

DAG共识与pow共识最大的区别在于,交易顺序的确定,以太坊中是单个矿工说了算,矿工可以根据自己的挖矿策略(交易手续费的高低)来决定一个块中包含哪些交易,然后通过哈希算力争夺记账权。而哈希图谱中,hash graph 通过gossip协议在对一个round中的交易顺序达成一致,并形成一个块,简单来说这些交易顺序是通过协商确定的,一旦确定不可更改。这样,分布式中的每一个账本根据相同的交易顺序向下演化世界状态,最终可以保持账本的一致性。