作者 | 刘春明3 N. ], ]! r. a2 X
& B7 T$ Z& v: K9 N' m6 D  }
DAG（有向无环图）是一种非线性数据结构，可以替代区块链，用于分布式账本的存储。这种结构在并发的场景下有更好的性能表现，但在实际应用中会面临更多的技术挑战。
+ c: P4 P, k/ i2 e2 ~7 _2 n
5 E, X' B) f* c# C, {其中，最大的挑战在于，基于DAG结构实现智能合约，要比基于区块链结构困难得多。
  v, @( J) q4 \0 d+ I. W' q本文将讨论DAG和区块链这两种账本结构，在加密货币和智能合约两个场景下的不同，以及如何基于DAG来实现智能合约。8 m( _' [+ G; a  Q
在谈什么是DAG之前，让我们先从最简单的场景出发——加密货币。加密货币是一个分布式数据库，存储了每个账户的余额信息。在加密货币网络上运行着很多台计算机，这些计算机称为节点（Node）。每一个节点都会存储一份关于账户余额的数据，这份数据通常被称为「状态」（State）。
/ J6 Q0 L/ _0 I与传统的中心化银行系统不同，这种分布式账本要求所有节点对状态达成某种共识。或者说，对任意一个账户来说，要求这个网络上每台计算机所存储的余额都是一致的。8 n5 p) b. J5 q9 V0 N4 ]' i* x1 t
由于状态的数据量比较大，在网络上传输全部数据非常困难，因此，在这种系统中，往往只传输那些能够引起状态变化的事件，也就是「交易」（Transaction）。
) k( l, P! F+ y想想看，你的钱不会无缘无故的增加或减少，只有在别人向你付款，或者你向别人付款的时候，账户余额才会发生变化。因此，只要知道一个账户所有历史转账（Transfer）记录，就可以很容易计算出当前的余额。6 Y0 w# o5 i' g( W8 O) F
在加密货币系统中，所有发生过的转账交易，都记录在一个被称为「账本」（Ledger）的数据结构中。这种账本通过密码学的方式进行了某种加密，使得每一个节点都可以验证自己获取的账本数据是不是被篡改过。: C$ D( D2 `/ Q; R6 h6 A/ f. a
###区块链和DAG
# d6 H  F8 R% T$ S) [说完了加密货币，那么它跟DAG有什么关系呢？
0 k  K* [+ o/ k首先，要知道区块链是一种经典的账本结构，广泛应用于比特币、以太坊等去中心化系统。它将一组交易打包成区块(Block)，通过哈希引用将区块组织成一个链式结构。$ L% q7 o. n) B1 N5 B: Y
而DAG是在区块链的基础上扩展出来的另外一种账本结构。在DAG账本中，一个区块通常只包含一个交易，它们彼此之间通过哈希引用，构成一种有向图结构，并且保证图中不存在环路。
! y7 L; L5 l( e$ J) r6 XDAG账本有很多不同的变体。例如，任意一个交易均引用两个其他交易作为其前驱节点，所构成的DAG被称为「Tangle」，应用于IOTA等项目；在另外一种DAG结构中，交易被组织成若干条链，并通过一些成对的交易彼此链接，这种DAG被称为「Block Lattice」，应用于Nano、Vite等项目。
, a* i' b. _' R8 g) k! |然而，大部分人没有意识到，事实上，区块链结构也是DAG的一个特例。
9 `$ r) {0 e6 V8 W: y$ b8 p1 l8 ?/ g; [) q% ^* D
基于不同数据结构来组织账本# z' @) Z. q* {9 R% e
基于区块链的加密货币
9 g  g5 E2 U+ t9 n3 w! _, U! C4 R5 {那么问题来了，假如每个节点拿到的账本是完全一样的，那么根据这个账本计算出来的状态是否也完全一样呢？
( P: ^/ o& b0 d8 l6 o6 x首先来看区块链这种结构。在这种结构中，所有的交易都是有序的，改变任何两个交易的顺序，都会破坏区块链的哈希引用关系，从而破坏账本的有效性。
/ K5 ~' D+ e6 M0 ~1 X: e因此，无论在哪个节点上进行计算，从同一个初始状态出发，经历同样的转账交易序列，总会产生相同的结果。看起来非常完美，不是吗？
2 p4 Y8 {- q5 q. Z- b5 W无论是比特币还是以太坊，节点之间不需要传输和比较庞大的状态数据，只需要就账本数据达成共识就行了。账本中所包含的信息，就足够一个节点计算出正确的状态了。) l- X5 B, |! D, ^8 e) E. S

$ q# @, J2 M! C基于区块链账本的加密货币% ?2 A( C: l" t0 w5 A8 v; A- }
基于DAG的加密货币
' g; t9 q/ |2 ?0 g3 ?& |我们再来看看DAG账本，是不是还具有这样的特性。好运气还在，在DAG账本中，虽然一些交易之间的顺序从账本中已经获取不到了，但这些顺序并不影响节点计算状态。
/ p. p( A0 v0 h  Z0 Q" Q因为加密货币中的状态计算，都是对余额的加减运算，这些运算是满足交换律的，只要保证任何账户的余额不小于0，交易的先后是无所谓的。
! I7 P/ J* g+ e: u) z; q0 l3 i因此，无论如何遍历DAG账本，最终计算的账户余额数据都一样，也就是说，任何节点都可以通过DAG账本来恢复正确的状态。
) x: M! f+ c' [3 z7 A& v) \5 R$ n, C3 A5 M
基于DAG账本的加密货币2 w, M; v$ V* x
###基于DAG的智能合约/ P7 ^2 H3 s( A/ V/ d1 E
看完了加密货币，我们再来看看智能合约。. s) ]5 s! s3 p+ c* w
在现实世界中，很多应用场景不像加密货币那样只记录一个余额就足够了。例如飞机票预订应用，在状态中需要记录一个航班上每一个座位的归属。这个时候，交易也不再仅仅表示转账了，可能包含任何对智能合约的请求数据，例如一张机票的预订请求。6 W6 O3 o- B% {) Y
这个时候，改变两个交易的先后顺序，就有可能产生不同的状态。想想看，如果Alice和Bob都尝试去预订同一班飞机上的同一个座位，那么这个座位将归属于先预订的那个人。& ]3 A6 z5 k+ z6 w6 B) ^  ~
在智能合约的场景下，好运气终结了，交易之间不再完全满足交换律了。这就迫使我们不得不去认真对待账本中每个交易之间的顺序。# F/ h$ v5 S; q0 c  }  W

! ]' ^5 O! q" t' D7 ]' D基于DAG账本(Tangle)的智能合约, e# H' s# n. O8 w! ^3 e
那么，到底哪些交易是必须进行排序的，而哪些交易不用关注顺序呢？最理想的情况是，写一个函数，可以根据系统中部署的智能合约逻辑，判断任何两个交易顺序是否会影响最终状态。8 I0 N$ I' M& `! @
假如有这样的函数存在，我们就可以在构造DAG账本时，知道哪些交易之间必须建立一个哈希引用。或者通俗的说，在表示DAG账本的图中，明确的知道哪些圆圈之间必须加一个箭头连接起来。5 ~! F& B( Q# u& F! V
不过遗憾的是，这个的函数的计算量非常大，无法用于现实的系统。所以我们只能放弃这种“完美”的方案，采用另一种更为简单粗暴的方法。
; W1 z, z' s% [* \6 O###构造对智能合约友好的DAG
# t2 w, J; `' O! z- z为了给出一个简单的交易排序规则，我们需要对系统做一些限制。
6 X+ z4 L7 e% i2 ^首先，我们将系统的状态，或者称“世界状态”，看作是由每个账户的状态组合而成的。其中任何两个账户的状态都是独立的，不会互相影响。一个用户的余额不会根据另一个用户余额的变动而发生改变，一个合约的数据也不会受另一个合约影响。( i, z% W/ X3 W( g1 N! u
然后，我们限制每一个交易只能影响一个账户的状态。比如转账交易，在我们的方案中，一个交易要么使某一个账户余额减少，要么使某一个账户余额增加，而不能同时改变两个账户的余额。也就是说，转账交易被拆分成“出账交易”和“入账交易”。同样的，智能合约调用的交易也被拆分成“请求交易”和“响应交易”。
5 j) N6 H3 r6 X% I4 K3 O$ w& D有了上面两条限制，排序规则就变得简单了：那些影响同一个账户状态的交易之间必须进行排序；另外，一对「请求交易」和「响应交易」也必须满足请求交易在响应交易之前。
9 s3 y2 ~# N; K  ^5 u/ Z按照这种规则进行排序的DAG账本，每个账户都有一组有序的交易，或者说每个账户都拥有一条自己的区块链，称之为「账户链」。另外，不同的账户链之间也会通过一对请求-响应交易之间的顺序建立起联系。这种结构的DAG就是前文提到的「Block Lattice」。
, h8 H% Z% T% {! a! C* d
% x/ u# W8 `* j2 i# s- v+ f  F基于DAG账本(Block Lattice)的智能合约
. o) _6 s- x- L3 ^8 y9 F基于这样的账本结构，你会发现，世界又恢复了秩序。无论以什么样的顺序遍历DAG账本，只要遵循账本中记录的交易顺序，总可以计算出同样的世界状态。
7 T/ k: U- i! I# g8 T0 D3 A这也是Vite等项目选择这种结构作为账本的原因。而采用Tangle结构实现智能合约，就必须引入另外一套排序规则。这在逻辑上相当于在原来DAG结构之外，针对同一组交易，另外建立一个不同的DAG结构，专门服务于智能合约，增加了工程实现上的难度。! k- v9 M0 v- X& G! t
###结束语% [+ j# Q- s( X. t1 r7 i  f8 b
本文简要描述了去中心化系统中的不同账本结构，以及基于DAG结构实现加密货币和智能合约的区别。
7 X9 Q1 N7 V( p$ k最后总结出一种在工程上易于实现智能合约的DAG结构。