Trias网络中的DAG数据结构介绍

区块链常用的是“区块＋链”的数据结构。简单来说，所谓区块，指的是单位时间内由记账者将交易记录整体打一个包，新生区块与上一个区块衔接在一起，形成区块链。比特币，以太坊等项目采用的都是这种方式。

这种链状结构虽然具备比较简单快速确认的优点，但也存在着固有的顽疾。首当其冲的就是链状结构难以提高吞吐量，所以效率一直比较低，整个网络中只能存在一条单链，无法并发执行，如果区块过小，势必造成交易的大幅延迟，而区块如果较大，又会造成数据量膨胀，普通节点用户不堪重负，DDos攻击等问题。此外，还存在能耗问题，安全问题等潜在问题。

DAG（Directed Acyclic Graph，有向无环图）原本是计算机领域的一种常用的数据结构，由于其具备良好的多线程特点，能够将区块链从一维的线状单点写入升级为三维多点并行工作，现在成为区块链世界中越来越重要的发展方向。

一、Trias中的DAG结构

Trais采用双层共识方法，即请求网络吞吐时使用DAG，确认时使用链式结构。因为DAG属于异步通讯方式，如果把事务操作进行异步处理，那么就可以显著的增加网络吞吐量。因此Trias设计了DAG的吞吐缓存共识层。

这里解释一下同步&异步通讯。同步通讯意味着客户端和服务强耦合，与同步通讯相反，异步通讯不要求捆绑所有的服务和层，允许存在一定的时间差。举一个例子，我喊朋友去吃饭，如果是同步通讯，朋友就得放下手中的事情，立刻响应我的请求；而在异步通讯中，则允许朋友忙完手里的事情，再来跟我吃饭。

Trias中的StreamNet就是基于DAG系统的设计，其针对现有区块链系统容易出现双花、重放攻击、交易速度慢、Coordinator的引入导致中心化等问题。以流式图计算为基础，设计出的一套新的DAG共识层。

在StreamNet中，它的每个节点（site）代表一个交易，而有向边则代表交易之间的确认关系。如下图所示，site0表示创世交易（Genesis），理论上讲是100%被确认的交易。在图中，site1表示其中的第一笔交易，被后续的site2，3，4确认。而未被确认的交易我们称之为tip，如site6，就是一个tip。

二、交易的实现过程

假如创世交易Genesis的初始数字资产为5，现在Genesis希望将1个数字资产转账给Alice，并在后续过程中将另外1个数字资产转账给Bob。那么，这个交易过程在StreamNet是如何确认的呢？

在这里，每一笔交易都必须找到两个tip交易来进行确认。例如Genesis转账给Alice的交易确认了Genesis本身，而Genesis在后续转账给Bob的交易则确认了Genesis本身和Genesis转账给Alice的交易。换言之，StreamNet上附着的每一笔交易都要做足够的工作量证明，即PoW。

值得一提的是，虽然同样用到了PoW，但这与比特币挖矿不同。这个过程难度不会随着交易多少而增减，也不会产生“矿工”这个角色。

如果其中某一步产生了差错，如上述过程中，Genesis要把10个数字资产转账给Bob，显然其账户中的数字资产并不够10，正产情况下，这个过程会导致验证失败。倘若选择欺骗，或者篡改数据，就会导致在后续的交易过程中被其他节点拒绝验证。

三、如何选择tip

在StreamNet中有交易速率的概念，用λ来表示。另外，我们用η来表示一笔交易在附着在StreamNet上后有多少时间单位没有被其他交易确认。

在选择tip 上，我们至少要考虑两个层面，一是选择的算法不能太过复杂，否则会影响交易速率λ，二是要尽力照顾到全网中未被确认的交易，不能使一些交易在经过太长时间后仍未被确认。

最基本的选择算法就是从创世交易Genesis开始，对批准它的交易以均等的概率进行游走，直到选出一个tip为止。如上图中Alice要把手中的数字资产转账给Sam，在选择tip时，选择创世交易Genesis转账给Alice和Bob的概率各为1/2。这种算法有一个问题，就是会产生懒交易，即新交易总是批准老交易而不被惩罚。

那么，有什么办法来阻止懒交易呢？或者，什么样的选择算法才是好算法呢？