Claire: 8月8日，我們做了一個題為『DAG 的前世今生(一)』的主題分享，得到很多朋友的熱烈關注和討論，不少同道中人也因此加入了【魔笛手社區】。今天，主講嘉賓吳岷先生會繼續『DAG 的前世今生(二)』的主題分享，進一步闡述BlockDAG的更多技術細節，難點，解決方法和工具，務求令大家對BlockDAG有更深入的瞭解，歡迎大家在稍後的Q&A 部分提出問題深入探討。現在有請吳岷先生……
min : 大家好，我是Min Wu，今天主題分享是解釋如何從區塊鏈擴展到區塊圖。 Github的鏈接是: https://github.com/soteria-dag/soterd
今天的分享是主要針對開發者的，有不少程序員才懂得俚語（黑話）哦。我儘量用通俗易懂的方式來分享，爭取大家都能受益。
上一期Ming Guo講過了“DAG的前世今生（一）“，鏈接在這裡，https://news.huoxing24.com/20190812204900103888.html，我們快速的回顧一下。
1: Soteria 是“內生去中心化經濟體”（SSDE - Self Sustainable Decentralized Economy）的基礎設施技術。
2: Soteria正在開發一套整體解決方案，以解決當前一代區塊鏈的一些緊迫問題，同時為其預想的去中心化經濟體提供足夠的功能集 - 例如基於區塊圖(blockDAG)的可擴展的吞吐量。
3: DAG 叫作有向無環圖。
4: BlockDAG叫做區塊圖。BlockDAG和TransactionDAG有極大的區別，具體看上期分享中有關交易DAG的部分。
5: Soteria DAG 實際上是比特幣中本聰共識算法的擴展，使其具有包容性，並在保證安全性的基礎上提供了靈活彈性的可擴展特性。
區塊圖是長這個樣子的：
在這個示例中。 最底部是創世（GENESIS）塊，箭頭是從一個區塊指向它的父輩塊（parent）。 如果一個區塊不是任何其他的區塊的父輩，它（們）就被稱為當前區塊圖的tips。 比如上圖中的tips就是M，J和L。Genesis、父輩塊(parent)、tips都是很重要的概念，我們接下來會反覆提到的。
在包容性的前提下，怎麼保證安全性呢？比如惡意挖礦怎麼辦呢？這裡我們就要講到Phantom 和 Greedy Phantom。
Phantom 是什麼？
Phantom 是染色/排序的協議，由Yonatan Sompolinsky 和 Aviv Zohar 發明。它的實現是如下三個主要步驟：
1： 識別出一組連接良好(well-connected)的區塊。 這被稱為藍色集合(set)。 其他的區塊，比如僅引用較舊的區塊，或者自己私藏了一段時間的區塊，在很大的概率情況下，會被排除在藍色集合之外。
2：對區塊圖進行拓撲排序，優先藍色集合的區塊，滯後不在藍色集合的區塊。
3：在排序核對交易的時候，會使用區塊圖的排序，合法的交易將會被採用而惡意的交易將會被拋棄。
讓我們看看使用Phantom或Greedy Phantom時這個圖形的顏色可能是什麼樣子。
上圖顯示的是用 Phantom染色以後的結果（Greedy Phantom是類似的），我們是從區塊M的角度來看如何染色的。在區塊圖的中間部分，有一個連接充分(well-connected)的區塊集合；同時在區塊圖的邊界處的一些區塊(紅色的)，它們的連接不是那麼充分。
我們使用一個系統內部常量(k)來做這個決定的，k是如何選定的我們會在以後的技術分享中解釋。這樣就意味著，同樣級別的紅色集合的區塊會排在藍色集合區塊的後面，注意，不是所以的紅色的區塊都排在所以藍色的區塊後面。沒有顏色的區塊(J 和 L）不屬於M的“過去集合”，它們會被排序在M的後面。
排序結果（從M的角度看）就是：
GENESIS, C, D, E, H, B, I, K, F, M, J, L
在染色和排序的過程中，Phantom 需要：
1：通過分析一個區塊的過去(past)和將來(future)來決定是不是充分連接(well-connected)。
2：遍歷區塊圖，為每一個區塊染色。
3：排序。
下面我們來看一看什麼是Greedy Phantom，作者是Aviv Yaish:
1: 和Phantom的概念基本相同，Greedy Phantom的目標是更簡單有效。
2: 染色部分是從最藍色父輩(bluest parent)繼承。
3: 染色和排序是遞增模式。
染色部分是從最藍色的父輩(bluest parent)繼承來的，最藍色的父輩又稱為染色父輩(colouring parent)。染色父輩的集合會從當前的區塊一直延續到創世塊(genesis)，這又叫做當前區塊的染色鏈(colouring chain)。
和Phantom 不同的部分就是，Greedy Phantom的染色是繼承的，在一個最藍色父輩之前的區塊的排序是不變的，相反的，在Phantom算法中，由於每一個區塊都需要考慮過去(past)和將來(future)，所以每一個區塊的顏色在將來都還有可能改變，完全取決於該區塊在未來的連接程度。
下面我們看一下在區塊被加到區塊圖的過程中，Greedy Phantom的染色過程。
動圖
在這個動畫中，除了藍色、紅色、和透明的區塊，還有綠色和虛線邊界的區塊。
綠色的：代表染色的tip
虛線的：當前區塊的染色鏈。（最藍色的父輩集合）
藍色的：藍色區塊的集合，是指從最新的區塊的角度來看（連接充分的，well-connected)
紅色的：在藍色區塊集合以外的區塊，從最新的區塊的角度來看（連接不是很充分）
可以觀察到的是，從最新的區塊的角度來看，有一些區塊的顏色會改變（在紅藍之間）。還可以觀察到的是，當角度不同當時候，染色鏈也不同。
在DAG最開始當時候，當B、C、D、E被添加當時候，染色鏈並沒有變成這些新的區塊。這是因為一個打破平局的內部規則，當兩個或兩個以上的區塊藍色程度一樣(equally blue)，哈希值低的區塊勝出。在這個例子中，B是字母中最前（低）的，所以B勝出。
總結一下Phantom和Greedy Phantom之間的計算差異（影響到工程實踐上）：
Phantom在染色時，會用到一個區塊的過去（past) 和未來 (future)，隨著區塊圖的增長，一個區塊的未來會無限增長。
Greedy Phantom只會在染色時考慮一個區塊的過去(past)，因為區塊圖不斷的增長，使得Greedy Phantom成為染色/排序在工程實現上更好選擇。
如果非要使用Phantom，可以通過設置節點過去和未來遍歷的下限和上限來實現類似的效果
但限制節點的過去和未來可能會影響染色效果，所以不太理想。
我們的代碼庫中包含了兩者的實現，目的是未來比較它們的差異，也為其他的開發人員提供更多的借鑑之處。
接下來我具體闡述我們如何對代碼進行修改，以達到擴展區塊鏈為區塊圖的目的。
項目開始以前，我們考察了不少已經開源的區塊鏈項目，最終決定以btcd為基礎，在上層做迭代。新的項目名稱叫 soterd。Github的鏈接是: https://github.com/soteria-dag/soterd
工程實現區塊圖（BlockDAG）包括瞭如下內容：
修剪已有的代碼，去掉只能服務於區塊鏈場景下的代碼，還包括不少會使得區塊圖（BlockDAG）開發複雜化同時又沒有太多幫助的代碼。
實現核心模塊，代表區塊圖（舊的代碼代表的是區塊鏈），提供和區塊鏈模塊相同或者類似的服務功能，比如：
找尋tips的功能；
根據已有的區塊，找尋父輩區塊；
檢索指定範圍的區塊圖。
更新了區塊的數據結構 （這可是所有區塊鏈項目中最重要的數據結構哦 ） 。
增加了一個區域可以存儲更多的父輩信息，因為在區塊圖裡面，每一個區塊可以有多個父輩（比特幣只能又一個）。
更新了協議層的編碼和解析的方法 (encoding/decoding)
更新及添加了測試(test)
更新了挖礦程序，還有其他有可能遍歷區塊鏈/區塊圖的地方:
增加了新的P2P 和 RPC 調用
getdagtips rpc call
renderdag rpc call
addrcache p2p call
更新了網絡同步部分的代碼
增加了系統集成測試，
生成區塊圖（原來是區塊鏈），確認每個區塊可以有多於一個父輩區塊。
確認區塊圖可以在不同的全節點同步。
確認可以用挖礦出來的SOTO做交易。
（其實囉裡八嗦這一大堆，不寫程序的群友只要記住，改公鏈代碼不是容易的事情，對程序員好一些。 :P……程序員朋友，details去看我們的github)
以上的改動是通過幾個不同的階段進行的，主要原因是一次改動量太大，風險太高。我們還開發量很多工具，來幫助理解+分析區塊圖和故障排除。工具會在後面的內容分享。
我知道大家看了這麼久的文字直播，很辛苦，心中的一個大問題就是，"A picture is worth a thousand words"。 小編，你的圖呢？？？
圖馬上就來。
好我們繼續……
遇到的挑戰：
在項目的開發過程中，需要更新很多的區塊鏈的代碼來支持區塊圖，大體上有三類不同的挑戰：
區塊鏈的假設。
已有的代碼中，由於系統設計的不同，很多地方缺省假設了是區塊鏈。
點對點 (p2p) 同步。
協議層的編碼和解析。
區塊鏈的假設:
部分代碼需要重構， 例如，在區塊鏈中，區塊的高度(height)是當前區塊距離創世區塊(genesis)中間有多少個區塊。在區塊圖中，一個區塊可以有多個父輩區塊，其中一些有可能比 其他人更直接地聯繫到Genesis。 所以在區塊圖中，區塊的高度現在是父輩區塊中的最大高度 + 1。
在上圖中，K塊的高度，如果通過B的路徑，就是2；如果通過C、D、E就是3。 所以我們認為它的高度是3。
孤塊 (Orphan block)的處理:
Z-shaped dag
一個孤塊是這樣的，當一個全節點收到了一個合理的區塊，但是又找不到該區塊的過去(past)，所以無法連接到現有的區塊圖上，這個區塊就被稱為孤塊。
在區塊鏈中，孤塊是從上往下處理的，從孤塊開始，然後是孤塊的父輩。在區塊圖中，這種遍歷方式就有問題了，尤其是區塊圖中有Z形狀(Z-saped dag)，一些區塊會被忽略掉。我們在這個算法上做了調整，利用深度優先的查找結果排序，從而包括了所有的區塊。
（我知道這段話看起很燒腦，你就想，孤兒多可憐呢，當然要區別對待了）
在孤塊處理中的重複問題 (knots)
對於區塊之間具有高連接性的區塊圖部分，孤塊處理將花費更長時間，因為每一條路徑
連接都會被被重新遍歷。 我們為此建立了緩存，記錄已經處理完成的孤塊及其過去(past)。
（也就是說，對孤兒太多的特殊待遇，也會對系統造成影響）
工具：
下面我們介紹一些開發工具，我們在soterd的代碼中加入了染色功能，目的是：
1: 幫助檢查區塊圖的實現或者同步問題，能直觀的看到區塊圖，比只能看到日誌文件中一組哈希值要有用的多。
2: 為上層應用（比如瀏覽器）提供接口。
dagviz:
Dagviz : https://github.com/soteria-dag/soterd/tree/master/cmd/dagvizDagviz 是一個命令行工具，
它會開啟幾個soterd的全節點（是的，是全節點），讓它們挖礦並且交換區塊，並且對結果進行一步一步的記錄，你可以回放（通過瀏覽器）。每一個區塊是按照它們的礦工區分顏色，這樣很直觀的可以看出每一個礦工對網絡對貢獻。 Dagviz 可以用於展示soterd和區塊圖，而且可以用來衡量算法的改變對於挖礦公平程度的影響。
min :
(記得哦，dagviz會讓幾個全節點在你的電腦上跑，所以對CPU的要求不低的）
dagparam 相關鏈接 dagparam https://github.com/soteria-dag/soterd/tree/master/cmd/dagparam Dagparam 是一個用來探索不同的點對點網絡參數的工具。比如targetTimespan和targetTimePerBlock， 以及這些參數如何影響區塊圖的構成和傳播。
Dagparam 是一個用來探索不同的點對點網絡參數的工具。比如targetTimespan和targetTimePerBlock， 以及這些參數如何影響區塊圖的構成和傳播。
比如當區塊的生成速度超過 62.5blocks/second，就是每16毫秒一個區塊的時候，同步的代碼就會有不穩定的表現。
soterdash https://github.com/soteria-dag/soterdash Soterdash 是一個web UI, 用來瀏覽區塊圖和soterd網絡中的全節點。它可以顯示全部或者部分區塊圖，點擊每個區塊會提供更細節的信息，比如Header, MerkleRoot等等。我們的開發過程中，Soterdash給予了很多幫助，尤其是在問題排查的時候。
Soterdash 是一個web UI, 用來瀏覽區塊圖和soterd網絡中的全節點。它可以顯示全部或者部分區塊圖，點擊每個區塊會提供更細節的信息，比如Header, MerkleRoot等等。我們的開發過程中，Soterdash給予了很多幫助，尤其是在問題排查的時候。
最後一個工具了啊，最後的一定是最好的。
go repo sync
我們絕大部分的代碼庫都是用go寫的。Go不允許relative import paths，這使得在不同的fork/copy的代碼庫之間共享代碼變成一個非常複雜的過程。我們的開發過程涉及到多個版本及不同方向的代碼共享，所以我們自己開發了這個工具來幫助在不同的代碼庫之間作同步。它把改變的部分自動轉移到目標代碼庫，同時做必要的改動，比如原來引用舊的代碼庫的地方，會被替換成新的，其具體步驟如下：
-處理當前項目及其所依賴的前序項目。
-把當前項目及目標項目複製到臨時區域。
-用git archive同步當前及目標項目。
-用git rm刪除目標項目中不需要的文件。
-把引用文件和鏈接替換。
-更新go的模塊名稱。
-把需要的新的文件加入目標項目。
-提交到本地
-提交到目標git tree.
-這個工具現在是在私密的程序庫(private repo)，但是我們可以按照需求提供開源。這個項目可以對廣大的go 程序員都有幫助。
（重複一下，不光是區塊鏈的程序員，所有go的程序員都有幫助的哦，當然，區塊鏈程序員還有很多不用go的）
感謝大家參與我們今天的分享，技術就是在不斷的討論過程中成長的。今天的分享就到此，下面是問答環節，請提問。
以下是 Q&A 精華節選：
seabook: @min@soteria 今天分享很有深度，你們的經濟模型是什麼？
min : 哦，那是我們下一次分享的話題：
SSDE (SELF SUSTAINABLE DECENTRALIZED ECONOMY)...You read my mind.
seabook: 請簡單提示一下。
min : https://www.ssde.io/ 現在是英文的，分享的內容會是中文的。我們還專門錄製過兩期podcast，談論about UBI.
seabook: https://medium.com/bitcoin-is-alien-technology/https-medium-com-bitcoin-is-alien-technology-bitcoin-is-alien-technology-part-1-7c5c82faf552
@min@soteria i enjoy reading your article.
朱江²⁰¹⁹: seabook，你提到的經濟模型是指的宏觀模型還是微觀模型 宏觀上如@min@soteria 提到的我們的SSDE proposal 微觀上是關於soteria dag本身的生態的 比如獎勵機制 incentive design等等 這個我們會在後邊的技術分享中涉及。
seabook: incentive design
朱江²⁰¹⁹: seabook， SSDE和soteria 不是UBI 也不是共產主義，仍然崇尚奮鬥精神，按勞分配。只不過是對現有中心化的經濟系統做了一些去中心化的增強：公平、包容、安全、隱私和可擴容。 incentive design，你也是博弈論的愛好者吧？ 請留意我們後邊的分享。
seabook: 會關注的。
Claire: 非常感謝大家的關注，感謝所有轉播的平臺，歡迎大家稍後繼續深入探討Blockdag 的技術，這次主題此結束。在進行了兩個非常硬核的主題分享之後，我們會繼續跟大家分享其他跟我們生活息息相關的話題，包括經濟，金融，隱私保護，大數據分析，區塊鏈項目的商業模式等等大家非常關心的內容，敬請繼續關注後續的主題分享。。。 再次感謝主講嘉賓吳岷先生的認真準備和細緻分享！
閱讀更多 Odaily星球日報 的文章
