基于DAG的IOTA共识算法
基于DAG的IOTA共识算法
摘 要：针对传统区块链和⽐特币在⾼并发交易受限的问题，研究⼈员提出了⼀种基于有向⽆环图的新型加密货币。通过介绍该物联⽹⾏业加密货币IOTA的数学基础——⽤于存储交易的有向⽆环图，对其进⾏⼀定的了解。这种新型加密货币的分布式⽹络主要特征被称为tangle，同时讨论了IOTA协议中所使⽤的共识策略和算法。
关键字：DAG；IOTA；FPC-BI；共识算法；拜占庭问题
背景介绍
整个加密货币⾏业围绕着如何打开去中⼼化世界的⼤门，让⼈们能够在不依赖第三⽅的情形下安全交易，研究⼈员相继提出了多种分布式账本技术。分布式账本类似于⼀种同步数据库，记录着⽹络参与者之间的价值转移，整个账本记录着有效交易的历史，并且不可篡改。区块链是当前分布式账本最主要的实现形式之⼀，但当前区块链中存在⼀个核⼼问题：可扩展性瓶颈。具体⽽⾔，区块链的吞吐量严重不⾜，且交易确认也较为缓慢，这些因素极⼤地限制了它的实际应⽤，同时它固有的⼯作量证明机制和⾼额的交易费使其⽆法满⾜⼩额交易的⽀付。正如没有⼈愿意为买⼀杯咖啡⽽等上⼀个⼩时来确认交易成
功，之后还需⽀付⼏倍于咖啡的⼿续费。此外，区块链本⾝的⼯作量证明机制也导致了⼤量的能源消耗，⽐特币⼀年的挖矿耗电量已经超越伊拉克全国⼀年的耗电量，这些问题的发⽣让⼈们不得不去思考新的系统和新的机制。
在图论中，若有向图G=V,E对于任意顶点v∈V，从该点出发⽆法找到有序路径P=e1,e2,…∈E回到v，那么就称这个有向图为DAG（Direct acyclic graph，有向⽆环图）。DAG原本是计算机领域⼀种常⽤数据结构，因为独特的拓扑结构所带来的优异特性，经常被⽤于处理动态规划、导航中寻求最短路径、数据压缩等多种算法场景。在2015年Sergio Demian Lerner提出新的基于DAG的链式结构，可以替代区块链⽤于分布式账本的存储。
这种结构打破了区块链的固有思维，可以让每⼀笔发⽣的交易⽴即上链，并且通过新的共识算法约束整个⽹络。由于DAG不受必须将交易加⼊区块链末端的限制，把同步记账提升为异步记账，因此具有良好的⾼并发特性，是区块链从容量到速度的⼀次⾰新，被认为是能够解决传统区块链的可扩展⾏问题的具有前景的研究⽅向。
在区块链这种经典的账本结构中，通常将⼀组交易打包成区块(Block)，通过哈希引⽤将区块组织成⼀个链式结构。在DAG账本中，⼀个区块通常只含有⼀个交易，他们彼此之间通过哈希引⽤，构成⼀种有向图结构，并且图中不存在环路。
区块链DAG
单元Block（区块）TX（交易）
拓扑由区块组成单链，只能按照出块时间依次写⼊由交易单元组成的⽹络，可以异步并发写⼊交易
粒度每个区块单元记录多个⽤户的多笔交易每个单元记录单个⽤户交易
IOTA是⼀个基于物联⽹（Internet of things ,IoT）⽽⽣的区块链项⽬。严格来说，IOTA不是“区块链”，因为它没有区块，也不是链式结构。IOTA提出了基于DAG的分布式账本结构，这种结构就是所谓的Tangle。
IOTA原理
Tangle⽹络结构
在IOTA中，节点是存有缠结（Tangle）所有信息的设备，没有矿⼯和⽤户的区分，即所有节点都将参与协商。节点只执⾏不需要太多计算能⼒的基本操作（例如存储分类账单、验证事务）。⽤户能以最⼩的成本建⽴节点，并参与⽹络共识，增强⽹络的安全性。Tangle作为IOTA使⽤的基于DAG的基础数据结构，它构建的基本规则为：为了加⼊Tangle，每笔交易必须验证和赞成批准已有的两笔交易。验证是指⽤户校验交易的签名，即它们的PoW（Power of work，⼯作证明），并确保不会与任何先前交易（直接或间接引⽤的）发⽣冲突。如果所选的tips是合法的，则⽤户通过引⽤它们来添加新的交易。
两个新的交易加⼊⽹络中。Tangle中的交易分为3类：绿⾊框表⽰已经被⽹络以很⾼的确定性确认了的交易（已达成共识的交易，共识是关于概率的确认，同区块链中永远不会有100%的确定性）；蓝⾊框表⽰部分确定的交易（还没有达成共识的交易）；灰⾊框（末梢交易tips）代表未经验证的交易。通过叠加新交易的验证路径可知，交易n被新加⼊的多个tips共同验证确认，则它在tangle中变得更加深⼊，成为完全确认的交易。
在更多交易添加到 Tangle 的情况下，这种⼆对⼀、前瞻性⽀付的共识可加强交易的有效性。由于共识是由交易确定的，因此理论上，如果有⼈可以⽣成三分之⼀的交易，那么他就可以说服⽹络中的其余部分，使得他的⽆效交易变成有效的，这时 IOTA 就会在⼀个称为“协调器（The Coordinator）”的中⼼节点上对⽹络中的所有交易做复核，并向整个分布式⽹络发布⾥程碑交易。⾥程碑的主要作⽤是确
定共
识，Tangle 运⽤⼀个简单的规则：当且仅当⼀笔交易被⾥程碑所引⽤，则该交易得到确认。⼀旦交易量⾜够⼤并达到⼀定规模，使得个⼈难以创建三分之⼀交易量，协调器就会被从中移除。
IOTA中的核⼼数据结构具有⾼度的可扩展性，提供多处可以附加交易，避免了单点附加新的交易的限制。 ⽤户可以继续在Tangle的各个地⽅附加新交易，⽽⽆需等待其他交易确认。
共识机制和算法
由于⽹络中交易的传播有延迟，在同⼀时刻每个节点未必拥有相同账本状态。这使得在验证的时候，可能会有多个互相有冲突的交易加⼊到Tangle 中。在发⽣冲突时，节点需要决定哪些交易最终应被视为有效，即他们需要就那些冲突的交易达成共识。
在处理冲突交易中，IOTA使⽤了Tip（尖端）选择算法和投票机制。节点间相互通信，以便在有冲突
交易时决定接受哪些交易。快速概率共识（Fast Probabilistic Connsus within Byzantine Infrastructures ,FPC-BI）是⼀种通信复杂度低的协议，它允许⼀组随机节点通过投票的⼿段对⼀位变量值达成共识。元胞⾃动机⽅法从模拟结果来看似乎更快，然⽽该⽅案缺乏严格的证明，因此后⽂不再赘述。这两种解决⽅案可以看作是不同的投票机制的⾮互斥实现，它们可以组合使⽤来构建⼀个健壮的框架。
Tip选择算法
TSA（Tip lection algorithm）是⼀个基于马尔科夫链蒙特卡洛⽅法的随机游⾛算法，诚实节点⽤随机⾏⾛（random walk）的⽅法来选择有效交易加⼊tangle⽹络，如图4所⽰。在相当⼤的随机区间放置N个粒⼦，也称作随机游⾛者，它们独⽴的向末梢交易tips进⾏随机游⾛，最先到达tip的两个随机游⾛所选中的交易作为申请验证的候选⼈。当交易y赞成了交易x，则随机游⾛的转移依据概率Pxy：
Pxy=exp-αHx-Hyz:z~xexp-αHx-Hy-1
其中，其中 α>0 是权重参数，Hx 是当前交易的累计权重，即交易x直接或间接验证（赞成）的交易数量。对于懒惰tips⽽⾔，因为它验证了过早的交易，因此累计权重远⼤于应有的Pxy⽽不会被选择；对攻击者tips⽽⾔，累计的权重远⼩于tangle主链中的，所以随机⾏⾛⼀般不会跳⼊攻击者建⽴的交易链。
该⽅法只有在诚实交易占多数的假设下有效。此外，该⽅法解决冲突速度缓慢，这会导致选择“错误”分⽀的交易，从⽽需要进⾏重新添加（reattachments）。所以IOTA运⽤投票表决来加速节点间交易的确认。
FPC-BI共识算法
投票机制能够确保在被攻击的情况下共识的安全性。节点查询其他节点对当前分布账本的看法，根据得到的其他节点观点的⽐例调整⾃⼰，在经过⼏轮询问后，决定⾃⼰账本的内容。当有冲突时，从分布式账本的初始状态开始执如下：考虑⼀个交易v，如果在给定的时间内节点没有看到有其他交易从同
⼀地址花费，我们说该节点喜欢交易 v；否则，节点不喜欢交易 v。我们会定期对缠结中的每个交易应⽤投票⽅案，每个节点都会询问⼀些邻居的状态。在投票后，⼀个交易要么被节点所喜欢，要么被⼀个节点肯定不喜欢，直到这种状态不会改变。我们希望保持单调性，如果⼀个节点喜欢交易u，那么它就喜欢交易 u 赞同的任何交易，如果节点不喜欢交易 v 那么它不喜欢赞同交易 v 的任何交易。实现这⼀点，我们可以放⼼地假设我们只喜欢交易 v 当我们喜欢它的所有前锥体形，如果我们不喜欢 v 那么我们不喜欢它的所有后锥体。
若赞成交易，则赞成该交易验证批准的所有交易；若不赞成交易，则舍弃验证该交易的所有交易。
FPC算法针对拜占庭问题的情况，假设部分节点被对⼿控制，这个对⼿要么想延迟共识，要么想破坏共识。
模型定义
1. 节点知晓⽹络中所有的参与者，并和它们进⾏通信。节点在达成共识中，会进⾏多轮查询，在每轮中⼏点会询问k个节点当前的意见。
所有节点都会回应询问；
2. 1-qn个节点是诚实的。诚实节点是指我们认为遵守系统指定的协议规则的参与者，并且节点⼤部分应是诚实的；
3. 假设对⼿节点是⽆所不知的。虽然这个假设看起来有点极端，但要注意，这些节点可以更频繁地查询诚实节点，以了解⽹络的当前状
态；另外，即使以某种⽅式不允许“太频繁”的查询，对⼿仍然可以通过分析特定诚实节点与所有邻居节点的交互历史来推断关于该节点的意见。对⼿节点可以分为谨慎的对⼿和鲁莽的对⼿。在同⼀轮询问中，谨慎的敌对节点会对所有查询持有相同的意见，⽽鲁莽的对⼿则会给出不⽤的回应；
4. 在每⼀轮查询中，所有参与者会使⽤⼀个随机数，假设这些随机数是由可信源提供的，⽽不是由对⼿控制的；
5. 不存在中⼼节点“监督”整个⽹络，即⽹络不知何时达成共识并停⽌。因此每个节点需⾃发的决定。
参数设定
该协议依赖⼀组整数和实数参数：
1. 1∕2<a≤b<1，第⼀轮查询的阈值；
2. β∈0,1∕2，随后轮次查询的阈值；
3. m0∈N为冷静期；
4. l∈N，表⽰⼀个节点具有相同意见的连续轮数(当冷却期结束时)，在此之后，它将成为最终结果。
算法协议过程可以描述为：在第⼀轮中每个诚实的节点j随机的查询其他节点k次（重复和⾃我询问均可）并记录它接收到的1-opinions意见的数⽬为η1j；随机变量X1~Ua,b对所有节点可⽤；诚实的节点遵循若k-1η1j≥X1，则决定意见为1否则意见
为0。在随后的m轮次进⾏同样的询问，但随机变量的取值范围为Xm~Uβ,1-β。当⼀个诚实的节点在冷静期结束后连续l轮中都得到相同的意见，则最终意见可以确定。
FPC依赖于随机查询的思想，在某些情况下⾜以获得良好的性能，⽽且由于消息的⼩复杂性，协议变得可扩展。这种随机性的另⼀个优点是在不太可靠的⽹络和不可避免的动荡(节点连接和离开)情况下的鲁棒性。
IOTA的应⽤领域
IOTA作为突破性应⽤的基础技术，在改变智能汽车、全球贸易和供应链、⼯业物联⽹、电⼦健康、智慧城市、海关与边境管理以及数字⾝份等领域都将发挥重要的作⽤。
数据是机器经济和互联世界中最基本的要素之⼀，它是数据-信息-知识-智慧（DIKW）⾦字塔的基础。在接下来的⼗年中，将有超过750亿个连接的设备以不同的⽅式进⾏交互，我们将看到历史上⽆与伦⽐的数据激增。这些设备将促进机器经济发展，从存储到电⼒和传感器数据的所有交易都将在此进⾏。然⽽绝⼤多数数据仍被锁定在所谓的数据孤岛中。数据孤岛不会或很少会在⾃⼰的封闭环境之外共享数据。IOTA基⾦会启动了“数据市场”项⽬，作为概念证明（PoC）和开放式创新⽣态系统。随着数据流在各个孤岛上激增并在相互之间传递价值，传统的价值链将过渡为价值⽹络。这种范例的管理将更加复杂，迫使企业重新考虑其作为这些⽣态系统⼀部分的竞争优势。数据市场将成为交换数据，货币化数据流并提供新的智能业务模型基础。
⽂件是在各⽅之间传输信息和合同的重要⼿段。若能可靠地证明⽂档没有从建⽴状态更改过，将有助
于确保各⽅之间的信任。IOTA技术可⾃动检查来⾃受信任来源（Tangle）的下载⽂件，并在⽂件不同的情况下警告⽤户。
能源供应通常是⾃动化的，但是⽀付系统的集成成本很⾼，并且通常需要⼈⼯⼲预。通过使⽤IOTA创建点对点（P2P）能源⽹格，可以⾃动进⾏电⼒传输和该电⼒的⾃动付款。这种⾃动化使基础架构更加动态，更易于更新。捷豹路虎近⽇测试发布了基于IOTA的联⽹汽车服务，车主可以通过让车辆⾃动向导航提供商或地⽅交管部门报告有效的道路状况数据（如交通拥堵或坑洼）来获得积分，并⽤其实现⽀付通⾏费、停车费和智能充电等费⽤。
供应链中的⼤多数可回收资产不会被跟踪，或仅被⼿动跟踪，这⼀过程由于低回报率，延迟以及与追踪这些项⽬相关的⾼成本⽽造成效率低下和经济损失。因此，⼤量资产不会流回给所有者，⽽是被提供给竞争对⼿或被低效回收或处置。为了解决这些问题，IOTA驱动的解决⽅案将为每个资产提供独特的数字⾝份，包括当前拥有它的组织的位置和⾝份，所有这些都可以通过简单的移动应⽤程序查看和管理。例如，在玻璃制造业中，玻璃架是可回收的资产。该资产⽤于将玻璃从玻璃⽣产商（资产所有者）运送到分销商。玻璃分销商可能会使⽤它们将其他玻璃运送到窗户制造商，⽽不是将玻璃架退还给玻璃⽣产商。然后，窗户制造商可能会⽤它来将窗户交付给他们的客户。IOTA提供了⼀种解决⽅案，可以⽆缝收集和共享有关可回收资产的信息，⽽⽆需集成任何专有系统。
显⽰了简化的利益相关者以及每个利益相关者在接触可退还资产时应执⾏的不同操作。其中虚线表⽰可退回资产的路径，绿⾊圈代表利益相关者，紫⾊圈代表可退回资产的所有者。
总结
IOTA作为⾯向IOT的分布式协议在基⾦会的研发和发展下，已经有了⼴泛的应⽤。在IOTA中为了达成共识，将FPC和元细胞⾃动机等算法和机制进⾏相互结合，通过学习研究相关⽂献，掌握分布式与并⾏计算的前沿知识并拓展了研究思路。同时我们可以看到在IOTA项⽬中仍开发了Chrysalis、Coordicide、BeeNode、Firefly、Wallet library等新技术和⼯具，我们将在以后进⾏对这些理论与技术进⾏跟踪研究。
参考⽂献
[1]⾼政风，郑继来，汤舒扬，龙宇，刘志强，刘振,⾕⼤武.基于DAG的分布式账本共识机制研究.软件学报,2020, 31(4):1124–1142.
[2]刘开放，付绍静，苏⾦树，张富成.⾯向物联⽹多域协同的IOTA区块链优化⽅案[J].信息⽹络安全,2020,20(10):41-48.
[3]江航. DAG链上的共识机制与均衡[D].哈尔滨⼯业⼤学,2019.
[4]Popov S, Buchanan W J. FPC-BI: Fast Probabilistic Connsus within Byzantine Infrastructures[J]. Journal of Parallel and Distributed Computing, 2020, 147:77-86.
出⾃⼩⽩的学校课程结课报告，参考了IOTA⽩⽪书和相关论⽂，是对⽹络上的资料进⾏的搜集整合以及翻译，供对IOTA尚未了解的⼩伙伴进⾏学习交流。因个⼈学识与理解原因有可能会有错漏，敬请谅解。
