1樓：小羊開門吶是我
DAG：Directed Acyclic Graph，中文意為「有向無環圖」。
有向無環圖是一種儲存資料的方式。「有向」指所有資料順著同一方向儲存；「無環」指資料結構間不構成迴圈。像條毛線織的圍巾，可以一直編下去。
為什麼要連線、標箭頭？因為使用者每發起一筆交易，必須驗證之前的兩筆交易。
這很像讓乙個孤兒自己選擇養父母。DAG是孤兒的世界，每筆交易天生是孤兒，但養父母不能隨便亂選，他們必須根正苗紅，否則孤兒自己就不會被下一代選為父母，不被選擇意味著從此消失。如果一筆交易不被後來的交易所驗證，它就會變成真正的孤兒，從此在賬本裡失去合法性。
DAG是一種資料儲存結構，從它被發明的30多年來一直都有人使用，本身並沒有問題。但它和區塊鏈的區別在於DAG沒有傳統意義上的共識，每筆交易的可信與否取決於相信這筆交易的人數。
所以採用DAG技術的核心問題在於如何保護全網達成的一致。
2樓：Outlier
推薦看看:
譯文:DAGfans/TranStudy
標下重點:
1. DAG只是乙個資料結構, 或者說賬本的儲存結構, 而非很多人理解的共識, 類似於區塊鏈是資料結構, 但是POW是共識;
2. DAG解決的核心問題是孤塊率.
解釋下: 提高吞吐量很直觀的方法就是提高出塊率或者增加區塊大小, 這個很好理解, 但是帶來的問題就是會提高孤塊率. 也就是在乙個出塊週期內滿足要求, 但是因為最終在最長鏈的競爭中被淘汰的區塊.
(這裡以位元幣為例, 但是只要是競爭出塊, 不管是什麼樣的淘汰規則, 總是會產生類似的問題).
淘汰機制帶來的直接後果就是算力浪費, 因為被淘汰的區塊也是礦工花了同樣的電量計算出來, 但是得不到任何獎勵(以太會有叔塊獎勵, 其實是已經算是DAG了, 是改良版的GHOST, 所以可以看到以太的出塊率能到15s). 其次就是導致中心化, 因為這種這種競爭機制會造成算力門檻不斷提高, 普通使用者的計算能力幾乎是沒有可能出塊了, 只有加入礦池, 但是這樣反而會加劇中心化的程度; 最後就是高孤塊率會降低安全性, 因為如果分叉太多, 單條分叉聚集的算力會降低, 所以推翻最長鏈的成本會降低, 可能遠不需要51%;
所以我們需要乙個擁抱孤塊率的資料結構, 這就是DAG存在的價值
3. DAG是區塊鏈的泛化, 站在DAG的角度而言, 區塊鏈是限定只有單個父子的特殊DAG
4. DAG的好處: 高確認時間,高吞吐量, 高去中心等
5. (個人觀點): DAG體現出了一種合作的思維, 區塊鏈體現的是一種競爭的思維. 而前者我認為是更加符合中本聰的初衷. 不知道中本聰在設計位元幣的時候有沒有想到礦池?
回答下常見質疑:
Q: DAG沒有解決Every node process every transactions. 即DAG還是要每個節點處理所有交易.
A: 首先我覺得這樣說有點不公平, 擴容是多種方案並舉的, DAG因為專注在資料結構層面, 但是可以和一層擴容比如分片和二層擴容比如閃電網路結合的, 之間並不衝突. 其次這種說法也不完全對, DAG確實需要校驗和儲存所有交易, 但是這些工作都不算是吞吐量的瓶頸, 可以腦補下, 如果把你的家用頻寬跑滿和CPU跑滿, 不停地接受區塊, TPS可以到多少 ?
雖然達不到無限擴容, 但是是不是已經非常誇張高? 如果還不滿意, 可以再考慮和分片或者分層.
Q: DAG 就是不安全的
A: 我不知道這種說法的理由是什麼? 我只能猜測這個說法是基於, 我之前提到的, 把位元幣的最長鏈規則和DAG結合的場景.
如果是這樣, 確實因為被推翻的算力可能遠不需要51%, 是有安全問題. 但是DAG的本質是資料結構, 最長鏈規則是屬於共識的範疇, 如果我們用更適合DAG的共識協議, 比如說基於最重鏈的GHOST, SPECTRE和PHANTOM等, DAG的安全係數能達到跟位元幣相同的程度.
Q: DAG 只能中心化解決
A: 這個說法我也不知道理由是什麼, 我猜測可能是目前知名的專案都有中心化的問題. 比如BYTEBALL的固定見證人, IOTA的coordinator.
這個其實首先是以偏概全了, 通過我們的分析, DAG作為資料結構跟是不是中心化本身沒有必然關係, 而且DAG如果有良好的實現, 會更加去中心. 目前的中心化問題乙個原因是專案的實現, 比如說雪球; 二個是專案的運營階段決定的, 比如說IOTA.
多提一下IOTA的coordinator, 首先我也認可這是一種中心化的權宜之計, 但是這個跟DAG技術無關的. 理論上, 這個問題任何專案都有, 即使位元幣也存在, 位元幣在創立的時候本身是沒有知名度的, 雖然是公網, 等於也是私挖, 這樣才積累了大量的算力, 等逐漸知名了, 有價值了, 被推翻的難度就很大了. 大家腦補下, 如果位元幣是今天區塊鏈這麼火的背景下誕生的, 中本聰敢這麼玩麼?
Cardano要先通過Byron 階段穩定下, 也是這麼考慮的, 這個總不算DAG吧. IOTA之所以會運營了三年還需要通過中心化的方法穩定安全性, 我的觀點主要應該是和其免手續費經濟模型有關, 無法激勵大量礦工去執行全節點.
3樓：文文文文
首先科普一下基礎 DAG 共識
1. 主鏈
主鏈是在指定單元所的 DAG 圖中沿著子-父鏈結找到乙個單鏈，可以把所有單元都關聯在一起。我們從任意乙個頂點開始，都可以構建一條主鏈。如果以相同的規則在兩個不同的頂點選擇主鏈，這兩條主鏈在回溯過程中一旦相交，它們會在交點之後完全重合。
重合部分稱為穩定主鏈，最壞的情況，兩條主鏈在創世單元相交。所有的單元要麼直接在這條穩定主鏈之上，要麼從穩定主鏈上的單元沿著 DAG 的邊緣通過少量的跳躍可以到達。因此穩定主鏈可以在兩個衝突的無序單元之間建立總序。
首先，給直接位於穩定主鏈上的單元做個索引，創世單元索引為 0，創世單元的子單元索引為1，以此類推，沿著穩定主鏈給主鏈上的所有單元分配索引。對於不在穩定主鏈上的單元，我們找到第乙個直接或間接引用此單元的主鏈單元。這樣，就給每乙個單元分配了乙個主鏈索引（MCI）。
然後，給定兩個單元，擁有較小 MCI 的單元被認為是更早生成的。如果兩個單元的 MCI 恰好相同並且存在衝突，則擁有較小雜湊值的單元有效。
主鏈構建過程實際上是最優父單元選擇演算法的遞迴呼叫過程。最優父單元通過比較可選路徑中公證單元的數量（相同公證人發出的單元記一次）來選擇。公證單元由證人發出，證人可以是非匿名期參與社群並擁有良好信譽的人，或是主動維護網路健康發展的組織。
雖然期望他們誠實行事，但完全信任任何乙個證人是不合理的，因此會同時選擇多個不同的證人。
2. 雙重支付問題
雙重支付交易：相同位址發出的任何無序的交易都視為雙重支付交易，即使它們沒有使用相同的輸出，也可稱為衝突交易或者矛盾交易。在使用者位址發出新單元時，要求相同位址發布的所有單元應當直接或間接包含該位址之前所有的單元，即相同位址的所有單元連通（有序或連續）。
因此，在相同位址的所有單元都連通的情況下，在路徑上出現較早的交易為有效交易。如果有攻擊者特意製造出雙重支付交易，那麼可以通過主鏈序號來解決，主鏈序號較小的交易為有效交易。假設攻擊者製造出一條影子鏈，並在上面發布雙重支付交易。
當影子鏈結入到真實的 DAG 中時，根據最優父單元選擇策略，影子鏈上的證人個數少，因此它不會成為主鏈的一部分，從而解決了這種場景下的雙重支付問題。值得注意的是，如果大多數證人與攻擊者合謀，並在其影子鏈上發布單元，則攻擊者有可能攻擊成功。
3. 交易確認
當獲得新的單元時，每乙個節點會持續追蹤自身的當前主鏈（MC），好像他們將要基於當前的所有無子單元構建新單元。不同節點各自的當前 MC 也許不同，因為它們有可能看到不同的非穩定單元集合。而當新單元到達時，當前 MC 會不斷變化。
然而，當前 MC 的足夠老的那部分會保持不變。
未來所有的 MC 在回溯時將會匯集某個 MC 單元，這個 MC 單元以及之前的所有MC 單元都是穩定的，不會因為新單元的到來而改變。事實上，創世單元是乙個天然的初始穩定節點。假設我們已經基於當前的非穩定單元集合構造了一條當前 MC，並且這條鏈上已經有一些之前認定穩定的節點，也就是說未來的當前 MC 都被相信會在這個點或早於這個點匯集，然後就沿同一條路徑回溯。
如果我們能找到乙個方法，把這個穩定點向遠離創世單元的方向推進，就可以根據數學歸納法證明這個穩定點存在。而被這個穩定點所引用的單元將獲得確定的 MCI，包含在這些單元中的所有訊息也將被確認。
學習資料結構有什麼用？
秋葉 換種說法吧,你初中學過的勾股定律,二次函式,概率 高中學的集合,指數對數,立體幾何,統計,各種不等式在95 以上的人在以後的工作生活中,都用不到.但是這社會的發展,大部分就是靠的那5 的人,所以才會被寫入教材資料結構和演算法也是一樣,95 的程式設計師也是用不到的,但是有的人是想當那5 的 如...
資料結構到底有什麼用
就是很多經典問題，你自己做呢，也不是做不出來，就是程式冗雜效率低。資料結構和演算法呢，就是告訴你優秀畢業生的高分作業的套路，你呢，搞清楚ta們的套路，下次遇到的時候借鑑，站在巨人的肩膀上 寒鴿兒 程式 資料結構 演算法，廣義上的資料結構是資料在計算機中的物理儲存和資料之間的邏輯結構。據此定義，陣列也...
初學資料結構，怎麼理解書上的這句話？
Judd 我的觀點是計算機類書籍一定不能看中文翻譯版。比如截圖裡集合的 complement 翻譯為取餘，不知道譯者是上哪學的高中。可以看看抽象代數，把 ADT 理解成乙個代數系統，也可以看看 Haskell 的 type class。 Cyandev 面向介面 協議 程式設計，ADT 是對於集合型...