最近在学习tangle共识算法。IOTA是第三代公有分布式账本,基于有向无环图结构。IOTA中将这种DAG称之为缠结Tangle。
严格来讲，Tangle（中文翻译为缠结）并不属于区块链技术。因为Tangle系统没有矿工将交易打包成区块这样一个过程，而且Tangle网络也不是区块链的链式网络，而是由一个个的交易组成的DAG网络（DirectedAcyclic Graph，有向无环图）结构。之所以将Tangle作为一种和PoW、PoS、DPoS等并列的共识机制来谈，主要是因为Tangle也是一种重要的，实现去中心化的，分布式账本结构的技术。业内比较知名的，采用Tangle技术的加密货币有IOTA和Byteball。
传统共识算法在物联网环境下的缺陷
工作量证明（PoW）和权益证明（PoS）这两种传统的共识算法都工作在“单链”架构上；这样会导致在账本中只有主链上的区块才是被认为是有效的，而分叉的区块被认为是非法且无效的。为了减少分叉并使区块链网络中的节点账本信息统一，共识算法必须降低区块生成的速率。
导致的瓶颈
以上的问题导致了算法的性能瓶颈：
- 交替吞吐量受限：区块生成速率低加之区块容量有限，导致了采用这两种传统共识算法的区块链系统往往每秒只能处理几至几十笔交易（比特币每秒至多能处理7 笔交易，以太坊每秒至多能处理15笔），无法承载物联网以指数增长的节点和需求。
- 交易共识时延大：为了保障系统中数据的安全，在交易加入区块链后，必须累积足够的后续区块才算达成共识，但由于区块生成速率低，达成共识需要花费较长时间（比特币系统需要累积6 个区块才算达成共识，平均花费60 分钟；以太坊系统需要累积12 个区块才算达成共识，平均花费3 分钟）
- 除了这两个问题外，为了保证单链结构账本的安全性，单个区块需要包含足够大的算力或者币龄，这就导致了：参与共识的成本高：只有算力大或资产多的节点才有权力生成区块；而物联网场景中，节点的算力资源通常十分有限，而给每个节点都提供充足资产的代价也太高。
- 交易手续费昂贵：由于参与共识的成本高，生成区块只能由资源丰富的矿工来完成。由此，进行交易的节点需要提供交易手续费作为矿工的酬劳，以激励它们进行工作，这对于微交易居多的物联网场景来讲是一种极大的负担。
基于有向无环图的共识算法
基本概念
基于有向无环图(Directed Acyclic Graph，DAG)共识算法（简称DAG 共识）采用了DAG 结构的账本来代替传统单链结构的账本，可解决传统共识算法（比如PoW、PoS 和PBFT）在物联网应用中的所固有缺陷。基于DAG 的账本即为分叉式的账本，这种结构在传统的共识算法中被认为是非法的，因为它可能引发双花的问题。但DAG 共识利用了一些有效的算法（比如：马尔可夫链蒙特卡罗算法、虚拟投票算法等）来解决基于DAG 的账本中的双花问，使节点只要验证了之前的旧区块便可随时将新区块随时接入到账本中，因而区块生成速率不再受限制，可实现极大的交易吞吐量。另外，由于DAG 共识的区块接入成本低，在DAG 共识中所有节点即为交易发送者，也为交易处理者，无需再为专门的矿工提供手续费。高交易吞吐量、低接入成本、可扩展性强以及零手续费正是物联网场景所需要而PoW、PoS 和PBFT 不能同时具备的，因此，DAG 共识更具有应用于物联网这种微交易频繁的场景的潜力。常见的DAG 共识有缠结(Tangle)、哈希图(Hashgraph)、字节雪球(Byteball)等。其中缠结是第一个提出且专门致力于物联网应用的DAG 共识，目前其顶层系统IOTA 的市值也排在基于DAG 的账本之首。
缠结是专门为物联网产业而提出的加密货币IOTA所采用的共识算法。如图所示，缠结采用了基于DAG 的账本来储存交易，以实现极大的交易吞吐量。在缠结中，节点处理两个旧区块并进行少量工作量证明可随时将新区块接入账本，由于这个共识过程资源消耗小，因此网络中所有节点都有能力自己处理自己的交易，而交易达成共识的速度，也会随着网络负载（指网络中新区块数量）的增大而变快。在介绍共识过程之前，先对缠结中的一些基本概念进行说明：
(1) 区块和边缘区块：图中的每一个区块都由网络中的某个节点所发出，用于存储自身的交易。除了交易外，区块中还包含数字签名、所认证区块的哈希值、随机数等。边缘区块(tips)为已经接入图中但未被认证过的区块，图中H和I为当前状态的边缘区块。
(2) 直接验证和间接验证：图中的所有的有向边都代表某个区块直接验证了所指向的区块是否合法，比如：图中H和C之间的箭头表示H直接认证了C。如果某两个区块之间存在多跳的有向路径，则称为间接认证，比如：图中I 间接确认了E。
(3) 自身权重和累积权重：一个区块自身的权重（简称自重）与将该区块接入至账本中所作出的工作量成比例。一个区块的累积权重则定义为该区块的自重再加上那些直接或间接认证该区块的区块的自重和。新加入区块直接或间接认证某个区块都会将其自重累加到被认证区块的累积权重上。一个区块的累积权重越大，被篡改的几率就会越低。
(4) 共识阈值：由系统所设定，当一个区块的累积权重达到系统给定的阈值，则被认为是达成了共识。阈值的设定会影响共识时延（达成共识的速度）和系统的安全性。
共识过程和MCMC算法
如果网络中的节点想要将一个新区块接入账本中进行分布式存储，即让所有节点承认此区块有权存在于该分布式账本中，节点需完成如下操作：第一，创建一个新区块加入自己的交易，并利用自己的私匙为交易的输入签名，防止其在广播过程中被篡改。第二，根据马尔可夫链蒙特卡罗(Markov Chain Monte Carlo，MCMC)算法（后文介绍）选择两个边缘区块，并验证这两个区块中的交易是否与账本中的其他交易冲突。
这里选择边缘区块的原因：
第一是为了保证新加入的区块得到及时认证。
第二是为了间接验证更多的区块，从而提高共识效率。
第三，寻找一个随机数，使得区块头的哈希值满足目标值，然后将区块广播至网络中；与PoW类似之处在于区块的生成都需要完成一定的工作量，不同之处在于缠结工作量较小，主要用于防止女巫攻击。
第四，当其余节点收到该区块时，会根据数字签名和随机数来判断该区块是否合法，如果合法，将区块加入自己的本地账本中。
第五，一个新区块加人账本中后，需要等待后续到来的区块对其加以认证，使其累积权重不断增加。累积权重越大被篡改的几率越低。
第六，区块的累积权重达到共识阈值，区块中的交易被全网节点认为是一笔成功的交易。
MCMC 算法：在生成新区块时，节点需要利用MCMC 算法选择两个边缘区块加以认证。MCMC 算法工作原理如下：将N 个质点独立放置于累积权重为某一特定区间中的旧区块上，让质点往边缘区块的方向进行独立离散时间随机游走。在游走过程中，质点会倾向于从累积权重更大的区块通过，最后抵达边缘区块，质点停留数量最多的两个区块即为被选中区块。也就是说MCMC 算法会选中基于DAG 的账本中累积权重较大的分支，丢弃那些累积权重较小的分支，以达到抵御双花攻击的目的。
缠结共识的缺陷
(1) 交易共识时延变大：在缠结中，旧区块必须由新区块进行认证以增加其累积权重，当达到足够的累积权重时，才达到共识。而在交易到达率低时，节点创建新区块的频率会减小，使得旧区块累积权重增长缓慢，最终导致交易长时间无法达成共识。
(2) 系统安全受到极大影响：在交易到达率低时，使用算力的诚实节点会减少，攻击者算力与有效的诚实节点算力
拉近。如果攻击者在此时发动双花攻击并利用自己的算力不断认证包含双花交易的区块，那么包含双花交易区块的累积权重将更有可能超越包含合法交易的区块。