区块链之DAG和DHT的深度探讨
鱼卷少年
基于区块链技术而产生的数字加密货币发展到如今，已有了三代的更新。
第一代，区块链+PoW。
第二代，区块链+PoS以及区块链+DPOS。
第三代，区块链+DAG，还有区块链+DHT。
第一代的数字货币以比特币、莱特币、以太坊（大都会分叉之前）等为典型，都是基于区块链技术，交易的确认通过工作量来证明（PoW），也就是通过挖矿的方式来实现。
第二代的数字货币以升级后的以太坊（大都会分叉之后）为典型，同样基于区块链技术，但是工作证明采取权益证明的方式(PoS)，可以理解为股票中的分红机制。
第三代的数字货币有IOTA和ByteBall(字节雪球)，没有采用区块链技术（或者说是新型的区块链技术），而是全新的DAG技术，在技术层面是一次革新。
目前应用DHT技术的主要应用包括：BitTorrent，Git，Storm Botnet，Freenet,
Yacy，IPFS和Holochain。前五种应用都属于传统互联网技术应用，后面两种涉及到目前大热的区块链行业。
该技术跳出了区块链的概念束缚，没有区块，准确的说，DAG还有DHT是和区块链并列的一种技术。也许要想打破区块链的不可能三角问题（可扩展性、安全、去中心化的平衡），就必须跳出区块链的本身，在其他技术里寻找答案，进而取代和革新区块链。
今天主要来讲讲DAG技术，以及与IPS运用的DHT技术间的深度探讨。
DAG和区块链
那DAG是什么呢？在数据结构的图论中，图分为有向图和无向图两大类，在有向图中进一步进行约束形成了DAG（有向无环图），所谓无环是指它是由集合的顶点和有向边构成，每条边连接一个顶点到另一个，这样，假如顶点A开始，沿着有序的边，最终循环回再次到A是不可能的（不存在环路）。
区块链是一个单一链式结构，而DAG已经是图的概念了。区块链通过区块（可以包含许多笔交易）通过每个区块对前区块的hash值包含进而链接起来。在DAG中，去掉了区块，每一笔交易发出后在验证时包含之前的比较新的交易hash，通过这种方法验证之前的交易，同时链接进图状结构，以待后面的交易链接并验证和确认。
很显然，相比较区块链而言，DAG的可扩展性变得更好，处理能力会大幅度提升。区块链在处理交易的时候，必须全网达成共识才能出块。而DAG不必全网达成共识，只需要后面链接的交易来确认即可。因为不需要单独的矿工通过挖矿来验证和确认交易，所以DAG就没有矿霸垄断算力的风险，可以更好的去中心化，转账手续费用也更低（甚至没有手续费）。
既然DAG可以比传统区块链结构更高效、更去中心化，那么DAG的安全性就是我们重点考察的方面了。我们知道，比特币区块链通过UTXO的设计巧妙的解决的双花问题。并且区块链的单一链式结构，在验证方面保证了必须全网共识才能确认交易有效，这就进一步避免了双花问题的产生。
而且通过POW（工作量证明）共识机制保证了如果想修改之前的交易必须拥有51%以上的算力才能做到。以太坊等其他区块链系统也继承了比特币区块链的安全性优势。很显然，DAG系统更加复杂，其安全性究竟如何呢？
IOTA是针对物联网领域的区块链项目，其应用的就是DAG技术。我们以IOTA项目的共识算法来分析和简单了解一下IOTA是如何解决双花问题的。
IOTA的DAG叫做Tangle（纠缠）。如果向Tangle中加入一笔新的交易，该交易必须引用之前的最新的没有被确认的2笔交易。
假如红色代表冲突交易（可能是双花），绿色代表新加入的交易。如下图:
从上图我们可以看到，新加入的交易在验证过程中，会发现存在两笔有冲突的交易。这样，IOTA系统就发现了这个存在问题的两笔交易。然后由交易的随机选择（和确认的累积权重）确定一个有效，另外一个无效。引用无效交易的的后续交易会被重新加入Tangle参与验证。
这里可以明确几点：
1 随着新加入的交易越来越多，新的交易选择引用之前交易是一定会引用到两个冲突交易的；
2 交易被确认次数越多（简单理解就是深度越深），这个交易越安全。通过一个确认比率就可以认定该笔交易是合法有效的。
从某方面来说，DAG技术确实突破了传统区块链，带来了很多优势。但是DAG相比较区块链的设计更为复杂，因此其共识算法的安全性还有待于长时间的实际验证，并且代码的安全性也需要团队有出色的代码编写和审计能力。
DAG vs Blockchain
那么相比于比特币等传统的区块链，这种机制有什么好处？
我们将从两个主要方面进行比较：
1）数据结构：通过DAG，每一笔交易就可以看作是一个区块，没有容量限制的问题，每一个区块有多个指向，拓展性强，因此能够实现数字货币较高的交易吞吐量（通过平行验证）。并且参与者越多，整个系统也会变得越来越安全和快速，确认时间会缩短，交易也完成的越来越快。
2）共识机制：区块链中添加下一个区块需要多方进行竞争，并获取区块奖励或交易手续费。正因如此，共识和交易生成是分离开的，并且由网络的一小部分人来完成，通常会设置较高门槛（就像比特币一样），这样会导致进一步的中心化（算力垄断）。
在DAG系统中，交易者本身就是矿工，网络中的每位参与者都能进行交易并且积极参与共识。通过这种方式，验证就能同步进行，网络能够保持完全去中心化，不需要矿工传递信任，也不需要支付交易手续费。
DHT和区块链
DHT的全称是Distributed
Hash Table，即分布式哈希表技术，是一种分布式的存储方法。这种分布式网络不需要中心节点服务器，而是每个客户端负责一个小范围的路由，并负责存储一小部分数据，从而实现整个DHT网络的寻址和存储。在区块链世界中，利用DHT可以实现众多节点的网络发现，实现各个节点在去中心化场景中的互联，DHT是非常重要的P2P网络技术之一。
DHT网络还在于关键字最接近的节点上复制备份冗余信息，避免了单一节点失效问题。形象地，我们可以把整个DHT网络想象成一个大城市，那么每个客户端，就好比城市里各个角落的地图碎片，上面绘制了附近区域的地形情况，把这些地图碎片汇总后，整个城市的全貌也就出来了。
DHT是P2P网络(结构化P2P)核心路由算法，主要是利用一致性hash，把节点和资源都表示成一个hash值，放入到这个大的hash环中，每个节点负责路由靠近它的资源。
重要概念
node：负责P2P路由信息，P2P网络的组网就是它来负责
peer：负责管理资源，生成种子文件，发布资源信息
nodeid：节点的唯一标识，是一个160bit的hash值
infohash：资源的唯一标识，也是一个160bit的hash值，其和nodeid使用同一个算法
距离：距离是两个hash值进行异或(XOR)操作后的值，值越小，距离越近
节点和资源的距离： nodeid XOR infohash
两个节点之间的距离：nodeid1 xor nodeid2
种子文件：对某个资源的描述文件，种子文件包括了资源的infohash(160bit)、资源所在机器（nodeId IP PORT）、离资源所在机器最近的N个机器（nodeid IP PORT）列表
典型场景
1.新节点加入网络
新安装的P2P客户端是一个孤立的节点，和其他节点都无联系，怎么加入P2P网络呢？需要有一个种子文件，种子文件中有多个该P2P网络中的node信息，根据种子文件中的节点列表，连接到P2P网络，并获取路由信息,获取最靠近本新节点的节点列表
2.发布资源
生成资源的Infohash，查找和infohash距离最近的N个Node，向这N个node广播新资源信息，告诉这些节点，我有某某资源，节点生成了资源，不过其路由信息不在这个节点上(也不在离这个节点的最近的M节点上)，而是在和资源infohash最近的N个node上
3.查找某个资源
找到最靠近资源的N个node(使用nodeid xor infohash来计算距离远近)，向这些node发送资源查询信息，如果有这个资源的详细信息，就返回给客户端，否则返回离资源更近的node列表给客户端，直到查询到资源提供者信息，如果没查到信息，且没有更近的node了，那就说明这个资源没有提供者，如果找到node信息(nodeid,ip,port)后,向这个node请求资源
实现DHT的技术有很多种，常见的有：Chord, Pastry, Kademlia等。我们熟知的BT及BT的衍生派（Mainline, Btspilits, Btcomet,uTorrent…），eMule及eMule各类Mods(verycd, easy emules, xtreme…)等P2P文件分享软件都是基于该算法来实现DHT网络的，BT采用Python的Kademlia实现叫作khashmir，eMule采用C++的Kademlia实现干脆就叫作Kad，当然它们之间有些差别，但基础都是Kademlia。
简单地说，DHT就是一种分布式的存储和寻址技术。通过DHT数据结构它把KEY 和VALUE用某种方式对应起来。使用hash()函数把一个KEY值映射到一个index上：hash(KEY) = index。
这样就可以把一个KEY值同某个index对应起来。然后把与这个KEY值对应的VALUE存储到index所标记的存储空间中。这样，每次想要查找KEY所对应的VALUE值时，只需要做一次hash()运算就可以找到了。以上就是寻址过程。
现在来讲讲基于DHT结构的区块链— —IPS
IPS也采用了DHT作为全网分布式账本存储和寻址技术。提到账本ledger就不得不提到Blockchain区块链技术，区块链简单说就是分布式记账技术，全网统一一个版本的账本，各个全节点node的账本全网一致，也就是每个参与者都复制一份账本，并通过gossip技术实时更新。
那么区块链面临的scaling扩容问题的症结就在于此，全网同步一份相同的账本，有多少个节点就有多少个账本的复本，复本的存储空间和更新所耗费的带宽是对资源的浪费。
IPS的革新之处在于将全网账本分布式的存储在各个参与的节点上，并通过DHT寻址技术保证账本的完整性integrity和可检索性retrievability。也许我还没有说清楚区别的关键所在。
IPS上的账本和Blockchain一样是全网统一一个版本的账本，但这个账本的存储不是每人一份复本，而是只有一份正本，在存储网络中，每个节点只会保存一部分区块数据。用户节点只需要保存最长的60个区块和对应的Hash以及对应叔区块。
在IPS上每人（或者说每一个设备）都是一个节点，也就是每个节点都会存储固定大小的数据，并不会随着系统运行的时间的增长而增大，因为会发生增长的数据只会存在于DHT中，而DHT网络会随着加入网络的客户端的增加可以很轻易的进行水平扩展。
IPS在结构上实现了区块无线扩展的可能性，与此同时，任何一笔交易不会超过2秒，因为1秒是IPS出块的间隔。
既然区块数据是存储到DHT中，而不需要再广播到系统中的每一个节点，那么就不太需要考虑网络带宽造成的区块扩容上限瓶颈，那么在区块进行打包的时候就可以将此刻之前发生的所有交易都打包到一个区块里。
然后将区块的Hash值广播出去，而Hash的长度永远是固定的，需要消耗的网络带宽也永远是固定的。这样每一笔交易的延迟基本就是区块打包的间隔时间。因此IPS会将出块的间隔时间控制在1秒钟，从而使交易的延迟最多不超过2秒。
每个节点存储的账本都是唯一的，并且是必要的，相对于Blockchain，极大的降低了复本占用的空间和带宽，同时还保留了区块链的优势（如：不可篡改）。
同时，IPS在世界各地建立了多个安全节点来存储完整数据，以便在有问题发生在DHT网络中时自动执行数据恢复，所有以前的事务都可以包装在最新的块中。
喜欢这篇文章的读者可以关注个人的微信公众号哟。（ID:鱼卷少年）
