Trias中基于流式图的DAG结构

服务器

浏览数:199

2019-8-22

在此前的文章:“Trias网络如何用DAG提升吞吐量”中,我们简要介绍了Trias中DAG的基本数据结构(StreamNet)和交易的实现过程。与链式结构相比,DAG结构的交易速率得到了显著的提升,但随之而来的问题是,如何选择未被确认过的新交易(tip)呢?

如果采用基本的随机游走算法,会导致新的交易批准老的交易而不被惩罚;而如果采用超权重算法的话,比如给不同的交易设置一个权值,又会造成新交易始终优先批准高权值交易,很多权值较低的交易永远也得不到确认。

一、DAG中的交易共识

目前交易的确认在StreamNet中主要有三种方式:

· 第一种方式:所有tip覆盖到的公共节点是被完全确认的。举一个例子,下图中,tip1引用或间接引用的交易为蓝线条和黄线条覆盖,而tip2引用或间接引用的交易为黄线条覆盖。那么被tip1和tip2共同覆盖到的就是标绿的交易,也就是被完全确认的交易。

· 第二种方式:系统每隔1分钟会发送一个Coordinator的tip附着在StreamNet上,这个tip被称之为里程碑(milestone),所有被Coordinator引用的交易都是被确认的。

· 第三种方式: 蒙特卡洛随机游走(MCMC)方式,即使用基本的随机tip选择算法来选择一个tip,如果一个交易被这个tip引用,那么它的可信度便增加1,经过N次选择后如果有M次被引用到了,那么其可信度便是M/N。

二、StreamNet主要算法

· 基于中心度的去COO起点选择算法

现阶段,在DAG中选择tip的时候,不会从创世交易开始,而是会简单的以某个Coordinator作为起点出发来选择tip ,这就会造成一个中心化的问题。所以在设计StreamNet的时候,首先要考虑的问题就是如何弱化COO而实现真正的分布式DAG,所以我们需要找到一个共识的交易作为起点,而不是由中心化节点强制规定的Coordinator作为起点。

在此我们选择Katz中心度作为选择起点的标准。因为StreamNet中的交易是不断进入到网络中的,如果每一笔新交易的选择都重新计算一次Katz中心度的话,那计算量会非常大,因此我们采用增量算法来计算:

其中,A表示交易之间的链接关系,k次方表示k阶链接矩阵,α表示重要性权值向量,I是一个全部为1的矩阵。

值得注意的是,在计算的结果中,我们并不需要寻找到Katz中心度最大的交易,因为这永远是创世交易(Genesis),所以我们应该在Katz中心度和离当下时间最近的交易中找到这个初始节点。

· 考虑边信息的交易权值算法

双花问题的一个典型场景便是侧链攻击,攻击者往往会在短时间内发出多个交易快速增长侧链,并在它们相互之间进行批准,一系列的欺骗性侧链可能就会导致双花成功。

为阻止这种情况发生,我们在两个approve交易之间会做加权的set join,而这个权值的判定由边的信息所确定,而边的信息则由时间来确认。通过使用边的信息来对交易进行重调,从而将攻击效应进行衰减,维护了网络的平稳运行。

· 基于流式图计算的权值更新算法

静态的图算法在更新节点权值的时候,需要从初始节点开始从头计算每个节点的权值,这个计算的复杂度是非常高的。而如果我们把静态计算的信息缓存起来,只在新的tip加入的时候更新已经缓存的信息,那么新tip加入时计算的复杂度将会大大降低。 

三、结语

现在DAG的方案已经陆续从研讨走向落地,业界有很多新颖的DAG方案正在被提出,从技术角度来说,DAG或许会对现有的区块链项目带来一次冲击,一定程度上改变现有的区块链设计思维。

DAG具有速度快,吞吐量高的优势,随着越来越多项目参与到DAG的生态发展中来,长期看来,DAG是非常有前景的机制。Trias作为首先采用DAG技术的公链,创造性的设计了基于DAG的吞吐缓存层,从理论和现实率先做出了突破,在公链之争中占得先机。

作者:Trias