區(qū)塊鏈之DAG和DHT的深度探討
魚卷少年
基于區(qū)塊鏈技術而產(chǎn)生的數(shù)字加密貨幣發(fā)展到如今，已有了三代的更新。
第一代，區(qū)塊鏈+PoW片迅。
第二代残邀，區(qū)塊鏈+PoS以及區(qū)塊鏈+DPOS皆辽。
第三代柑蛇，區(qū)塊鏈+DAG，還有區(qū)塊鏈+DHT驱闷。
第一代的數(shù)字貨幣以比特幣耻台、萊特幣、以太坊（大都會分叉之前）等為典型空另，都是基于區(qū)塊鏈技術盆耽，交易的確認通過工作量來證明（PoW），也就是通過挖礦的方式來實現(xiàn)扼菠。
第二代的數(shù)字貨幣以升級后的以太坊（大都會分叉之后）為典型摄杂，同樣基于區(qū)塊鏈技術，但是工作證明采取權益證明的方式(PoS)循榆，可以理解為股票中的分紅機制析恢。
第三代的數(shù)字貨幣有IOTA和ByteBall(字節(jié)雪球)，沒有采用區(qū)塊鏈技術（或者說是新型的區(qū)塊鏈技術）秧饮，而是全新的DAG技術映挂，在技術層面是一次革新。
目前應用DHT技術的主要應用包括：BitTorrent盗尸，Git柑船，Storm Botnet，F(xiàn)reenet,
Yacy泼各，IPFS和Holochain鞍时。前五種應用都屬于傳統(tǒng)互聯(lián)網(wǎng)技術應用，后面兩種涉及到目前大熱的區(qū)塊鏈行業(yè)扣蜻。
該技術跳出了區(qū)塊鏈的概念束縛寸癌，沒有區(qū)塊，準確的說弱贼，DAG還有DHT是和區(qū)塊鏈并列的一種技術蒸苇。也許要想打破區(qū)塊鏈的不可能三角問題（可擴展性、安全吮旅、去中心化的平衡）溪烤，就必須跳出區(qū)塊鏈的本身，在其他技術里尋找答案庇勃，進而取代和革新區(qū)塊鏈檬嘀。
今天主要來講講DAG技術，以及與IPS運用的DHT技術間的深度探討责嚷。
DAG和區(qū)塊鏈
那DAG是什么呢鸳兽？在數(shù)據(jù)結構的圖論中，圖分為有向圖和無向圖兩大類罕拂，在有向圖中進一步進行約束形成了DAG（有向無環(huán)圖）揍异，所謂無環(huán)是指它是由集合的頂點和有向邊構成全陨，每條邊連接一個頂點到另一個，這樣衷掷，假如頂點A開始辱姨，沿著有序的邊，最終循環(huán)回再次到A是不可能的（不存在環(huán)路）戚嗅。
區(qū)塊鏈是一個單一鏈式結構雨涛，而DAG已經(jīng)是圖的概念了。區(qū)塊鏈通過區(qū)塊（可以包含許多筆交易）通過每個區(qū)塊對前區(qū)塊的hash值包含進而鏈接起來懦胞。在DAG中替久，去掉了區(qū)塊，每一筆交易發(fā)出后在驗證時包含之前的比較新的交易hash躏尉，通過這種方法驗證之前的交易侣肄，同時鏈接進圖狀結構，以待后面的交易鏈接并驗證和確認醇份。
很顯然，相比較區(qū)塊鏈而言僚纷，DAG的可擴展性變得更好矩距，處理能力會大幅度提升。區(qū)塊鏈在處理交易的時候怖竭，必須全網(wǎng)達成共識才能出塊锥债。而DAG不必全網(wǎng)達成共識，只需要后面鏈接的交易來確認即可痊臭。因為不需要單獨的礦工通過挖礦來驗證和確認交易哮肚，所以DAG就沒有礦霸壟斷算力的風險，可以更好的去中心化广匙，轉賬手續(xù)費用也更低（甚至沒有手續(xù)費）允趟。
既然DAG可以比傳統(tǒng)區(qū)塊鏈結構更高效、更去中心化鸦致，那么DAG的安全性就是我們重點考察的方面了潮剪。我們知道，比特幣區(qū)塊鏈通過UTXO的設計巧妙的解決的雙花問題分唾。并且區(qū)塊鏈的單一鏈式結構抗碰，在驗證方面保證了必須全網(wǎng)共識才能確認交易有效，這就進一步避免了雙花問題的產(chǎn)生绽乔。
而且通過POW（工作量證明）共識機制保證了如果想修改之前的交易必須擁有51%以上的算力才能做到弧蝇。以太坊等其他區(qū)塊鏈系統(tǒng)也繼承了比特幣區(qū)塊鏈的安全性優(yōu)勢。很顯然，DAG系統(tǒng)更加復雜看疗，其安全性究竟如何呢沙峻？
IOTA是針對物聯(lián)網(wǎng)領域的區(qū)塊鏈項目，其應用的就是DAG技術鹃觉。我們以IOTA項目的共識算法來分析和簡單了解一下IOTA是如何解決雙花問題的专酗。
IOTA的DAG叫做Tangle（糾纏）睹逃。如果向Tangle中加入一筆新的交易盗扇，該交易必須引用之前的最新的沒有被確認的2筆交易。
假如紅色代表沖突交易（可能是雙花）沉填，綠色代表新加入的交易疗隶。如下圖:
從上圖我們可以看到，新加入的交易在驗證過程中翼闹，會發(fā)現(xiàn)存在兩筆有沖突的交易斑鼻。這樣，IOTA系統(tǒng)就發(fā)現(xiàn)了這個存在問題的兩筆交易猎荠。然后由交易的隨機選擇（和確認的累積權重）確定一個有效坚弱，另外一個無效。引用無效交易的的后續(xù)交易會被重新加入Tangle參與驗證关摇。
這里可以明確幾點：
1 隨著新加入的交易越來越多荒叶，新的交易選擇引用之前交易是一定會引用到兩個沖突交易的；
2 交易被確認次數(shù)越多（簡單理解就是深度越深）输虱，這個交易越安全些楣。通過一個確認比率就可以認定該筆交易是合法有效的。
從某方面來說宪睹，DAG技術確實突破了傳統(tǒng)區(qū)塊鏈愁茁，帶來了很多優(yōu)勢。但是DAG相比較區(qū)塊鏈的設計更為復雜亭病，因此其共識算法的安全性還有待于長時間的實際驗證鹅很，并且代碼的安全性也需要團隊有出色的代碼編寫和審計能力。
DAG vs Blockchain
那么相比于比特幣等傳統(tǒng)的區(qū)塊鏈罪帖，這種機制有什么好處道宅？
我們將從兩個主要方面進行比較：
1）數(shù)據(jù)結構：通過DAG，每一筆交易就可以看作是一個區(qū)塊胸蛛，沒有容量限制的問題污茵，每一個區(qū)塊有多個指向，拓展性強葬项，因此能夠實現(xiàn)數(shù)字貨幣較高的交易吞吐量（通過平行驗證）泞当。并且參與者越多，整個系統(tǒng)也會變得越來越安全和快速民珍，確認時間會縮短襟士，交易也完成的越來越快盗飒。
2）共識機制：區(qū)塊鏈中添加下一個區(qū)塊需要多方進行競爭，并獲取區(qū)塊獎勵或交易手續(xù)費陋桂。正因如此逆趣，共識和交易生成是分離開的，并且由網(wǎng)絡的一小部分人來完成嗜历，通常會設置較高門檻（就像比特幣一樣）宣渗，這樣會導致進一步的中心化（算力壟斷）。
在DAG系統(tǒng)中梨州，交易者本身就是礦工痕囱，網(wǎng)絡中的每位參與者都能進行交易并且積極參與共識。通過這種方式暴匠，驗證就能同步進行鞍恢，網(wǎng)絡能夠保持完全去中心化，不需要礦工傳遞信任每窖，也不需要支付交易手續(xù)費帮掉。
DHT和區(qū)塊鏈
DHT的全稱是Distributed
Hash Table，即分布式哈希表技術窒典，是一種分布式的存儲方法蟆炊。這種分布式網(wǎng)絡不需要中心節(jié)點服務器，而是每個客戶端負責一個小范圍的路由崇败，并負責存儲一小部分數(shù)據(jù)盅称，從而實現(xiàn)整個DHT網(wǎng)絡的尋址和存儲。在區(qū)塊鏈世界中后室，利用DHT可以實現(xiàn)眾多節(jié)點的網(wǎng)絡發(fā)現(xiàn)缩膝，實現(xiàn)各個節(jié)點在去中心化場景中的互聯(lián)，DHT是非常重要的P2P網(wǎng)絡技術之一岸霹。
DHT網(wǎng)絡還在于關鍵字最接近的節(jié)點上復制備份冗余信息疾层，避免了單一節(jié)點失效問題。形象地贡避，我們可以把整個DHT網(wǎng)絡想象成一個大城市痛黎，那么每個客戶端，就好比城市里各個角落的地圖碎片刮吧，上面繪制了附近區(qū)域的地形情況湖饱，把這些地圖碎片匯總后，整個城市的全貌也就出來了杀捻。
DHT是P2P網(wǎng)絡(結構化P2P)核心路由算法井厌，主要是利用一致性hash，把節(jié)點和資源都表示成一個hash值，放入到這個大的hash環(huán)中仅仆，每個節(jié)點負責路由靠近它的資源器赞。
重要概念
node：負責P2P路由信息，P2P網(wǎng)絡的組網(wǎng)就是它來負責
peer：負責管理資源墓拜，生成種子文件港柜，發(fā)布資源信息
nodeid：節(jié)點的唯一標識，是一個160bit的hash值
infohash：資源的唯一標識咳榜，也是一個160bit的hash值夏醉，其和nodeid使用同一個算法
距離：距離是兩個hash值進行異或(XOR)操作后的值，值越小贿衍，距離越近
節(jié)點和資源的距離：?nodeid XOR infohash
兩個節(jié)點之間的距離：nodeid1 xor nodeid2
種子文件：對某個資源的描述文件授舟，種子文件包括了資源的infohash(160bit)救恨、資源所在機器（nodeId IP PORT）贸辈、離資源所在機器最近的N個機器（nodeid IP PORT）列表
典型場景
1.新節(jié)點加入網(wǎng)絡
新安裝的P2P客戶端是一個孤立的節(jié)點，和其他節(jié)點都無聯(lián)系肠槽，怎么加入P2P網(wǎng)絡呢擎淤？需要有一個種子文件，種子文件中有多個該P2P網(wǎng)絡中的node信息秸仙，根據(jù)種子文件中的節(jié)點列表嘴拢，連接到P2P網(wǎng)絡，并獲取路由信息,獲取最靠近本新節(jié)點的節(jié)點列表
2.發(fā)布資源
生成資源的Infohash寂纪，查找和infohash距離最近的N個Node席吴，向這N個node廣播新資源信息，告訴這些節(jié)點捞蛋，我有某某資源孝冒，節(jié)點生成了資源，不過其路由信息不在這個節(jié)點上(也不在離這個節(jié)點的最近的M節(jié)點上)拟杉，而是在和資源infohash最近的N個node上
3.查找某個資源
找到最靠近資源的N個node(使用nodeid xor infohash來計算距離遠近)庄涡，向這些node發(fā)送資源查詢信息，如果有這個資源的詳細信息搬设，就返回給客戶端穴店，否則返回離資源更近的node列表給客戶端，直到查詢到資源提供者信息拿穴，如果沒查到信息泣洞，且沒有更近的node了，那就說明這個資源沒有提供者默色，如果找到node信息(nodeid,ip,port)后,向這個node請求資源
實現(xiàn)DHT的技術有很多種球凰，常見的有：Chord, Pastry, Kademlia等。我們熟知的BT及BT的衍生派（Mainline, Btspilits, Btcomet,uTorrent…），eMule及eMule各類Mods(verycd, easy emules, xtreme…)等P2P文件分享軟件都是基于該算法來實現(xiàn)DHT網(wǎng)絡的弟蚀，BT采用Python的Kademlia實現(xiàn)叫作khashmir蚤霞，eMule采用C++的Kademlia實現(xiàn)干脆就叫作Kad，當然它們之間有些差別义钉，但基礎都是Kademlia昧绣。
簡單地說，DHT就是一種分布式的存儲和尋址技術捶闸。通過DHT數(shù)據(jù)結構它把KEY?和VALUE用某種方式對應起來夜畴。使用hash()函數(shù)把一個KEY值映射到一個index上：hash(KEY) = index。
這樣就可以把一個KEY值同某個index對應起來删壮。然后把與這個KEY值對應的VALUE存儲到index所標記的存儲空間中贪绘。這樣，每次想要查找KEY所對應的VALUE值時央碟，只需要做一次hash()運算就可以找到了税灌。以上就是尋址過程。
現(xiàn)在來講講基于DHT結構的區(qū)塊鏈— —IPS
IPS也采用了DHT作為全網(wǎng)分布式賬本存儲和尋址技術亿虽。提到賬本ledger就不得不提到Blockchain區(qū)塊鏈技術菱涤，區(qū)塊鏈簡單說就是分布式記賬技術，全網(wǎng)統(tǒng)一一個版本的賬本洛勉，各個全節(jié)點node的賬本全網(wǎng)一致粘秆，也就是每個參與者都復制一份賬本，并通過gossip技術實時更新收毫。
那么區(qū)塊鏈面臨的scaling擴容問題的癥結就在于此攻走，全網(wǎng)同步一份相同的賬本，有多少個節(jié)點就有多少個賬本的復本此再，復本的存儲空間和更新所耗費的帶寬是對資源的浪費昔搂。
IPS的革新之處在于將全網(wǎng)賬本分布式的存儲在各個參與的節(jié)點上，并通過DHT尋址技術保證賬本的完整性integrity和可檢索性retrievability引润。也許我還沒有說清楚區(qū)別的關鍵所在巩趁。
IPS上的賬本和Blockchain一樣是全網(wǎng)統(tǒng)一一個版本的賬本，但這個賬本的存儲不是每人一份復本淳附，而是只有一份正本议慰，在存儲網(wǎng)絡中，每個節(jié)點只會保存一部分區(qū)塊數(shù)據(jù)奴曙。用戶節(jié)點只需要保存最長的60個區(qū)塊和對應的Hash以及對應叔區(qū)塊别凹。
在IPS上每人（或者說每一個設備）都是一個節(jié)點，也就是每個節(jié)點都會存儲固定大小的數(shù)據(jù)洽糟，并不會隨著系統(tǒng)運行的時間的增長而增大炉菲，因為會發(fā)生增長的數(shù)據(jù)只會存在于DHT中堕战，而DHT網(wǎng)絡會隨著加入網(wǎng)絡的客戶端的增加可以很輕易的進行水平擴展。
IPS在結構上實現(xiàn)了區(qū)塊無線擴展的可能性拍霜，與此同時嘱丢，任何一筆交易不會超過2秒，因為1秒是IPS出塊的間隔祠饺。
既然區(qū)塊數(shù)據(jù)是存儲到DHT中越驻，而不需要再廣播到系統(tǒng)中的每一個節(jié)點，那么就不太需要考慮網(wǎng)絡帶寬造成的區(qū)塊擴容上限瓶頸道偷，那么在區(qū)塊進行打包的時候就可以將此刻之前發(fā)生的所有交易都打包到一個區(qū)塊里缀旁。
然后將區(qū)塊的Hash值廣播出去，而Hash的長度永遠是固定的勺鸦，需要消耗的網(wǎng)絡帶寬也永遠是固定的并巍。這樣每一筆交易的延遲基本就是區(qū)塊打包的間隔時間。因此IPS會將出塊的間隔時間控制在1秒鐘换途，從而使交易的延遲最多不超過2秒懊渡。
每個節(jié)點存儲的賬本都是唯一的，并且是必要的怀跛，相對于Blockchain距贷，極大的降低了復本占用的空間和帶寬柄冲，同時還保留了區(qū)塊鏈的優(yōu)勢（如：不可篡改）吻谋。
同時，IPS在世界各地建立了多個安全節(jié)點來存儲完整數(shù)據(jù)现横，以便在有問題發(fā)生在DHT網(wǎng)絡中時自動執(zhí)行數(shù)據(jù)恢復漓拾，所有以前的事務都可以包裝在最新的塊中。
喜歡這篇文章的讀者可以關注個人的微信公眾號喲戒祠。（ID:魚卷少年）
