您当前位置: 首页> 资讯> 工程上DAG算法是如何实现共识的
有向无环图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中的交易顺序达成一致,并形成一个块,简单来说这些交易顺序是通过协商确定的,一旦确定不可更改。这样,分布式中的每一个账本根据相同的交易顺序向下演化世界状态,最终可以保持账本的一致性。