這篇文章我們著重介紹一下phantom這種賬本協議。與上一篇的spectre不同，phantom可以對整個賬本做一個線性排序，滿足了智慧合約網路對賬本的時序性的要求。（具體內容參考《從區塊鏈到dag（三）--dag共識之spectre協議》）
下面將逐一對這兩點進行說明。這裡重申一下賬本共識有效的大前提：網路中大多數節點都是誠實的。我們不考慮集中超過51%算力的這種惡意攻擊，因為無論用什麼賬本共識這樣的攻擊都會奏效。 1 phantom的投票原則
從《從區塊鏈到dag（三）--dag共識之spectre協議》 裡的描述可以看出：“雙花”攻擊時，攻擊區塊在釋出以前幾乎不會與誠實節點產生的區塊相關聯，因為在這個階段誠實區塊不知道這些攻擊區塊的存在，所以自然不會引用它們。在censorship攻擊中，攻擊節點產生的區塊也有類似的傾向：不與誠實節點所產生的包含“衝突交易”的區塊相關聯。綜和來看這些惡意攻擊都有一個顯著特點：惡意節點產生的區塊與誠實節點產生的區塊之間的連通度比較低，反之誠實節點產生的區塊之間的連通度會比較高。phantom的投票原則正是基於這個原理，透過判斷不同區塊間的連通度進行投票。為了描述清楚這個投票過程，我們先介紹幾個有關的概念，見圖片1。圖片1 一個典型的dag圖例
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
past(h)={genesis, c, d, e}--在h建立之前直接或間接指向h的過去區塊。future(h)={j,k,m}--在h建立之後直接或間接指向h的未來區塊。anticone(h)={b, f, i, l}--除開past(h)，future(h)之外的區塊，這些區塊與h並沒有直接或間接的指向關係。如何對這些區塊的排序是dag共識的主要難點。tips(g)={j, l, m}--樹葉區塊，或者末端區塊；這些區塊會成為新區塊的塊頭引用。接下來再引入一個在《從區塊鏈到dag（二）--dag的基本結構》裡提到過的概念：分叉係數k，直觀上看這是一個描述網路允許分叉的個數。嚴格來說k被定義為傳播係數（propagation parameter)，用來描述網路延遲（propagation delay）這個現象。在《從區塊鏈到dag（一）--區塊鏈的賬本結構和共識機制》中我們講到過，在實際過程中網路延遲的現象無法避免，二這種延遲會導致分叉。如果要避免分叉，就要保證在網路延遲的時間段δt內不產生新的區塊，即k=0。k值的定義非常重要，如果k值太大會使分叉過多，降低網路的安全性；如果太小又會限制網路效能，使tps較低，比如區塊鏈就是一種k=0的網路。在dag中，為了平衡效能和安全一般把k定為3。連通度的高低是透過k值來判定的，區塊的連通度要滿足最大k-cluster的子集要求，如圖片2。圖片2 k-cluster子集要滿足的條件
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
如何判斷一個區塊是誠實節點產生的呢？先找到這個區塊的anticone的集合，這個集合和dag的k-cluster的子集s的交集數目如果小於等於k，則這個區塊是誠實節點產生的，會被加入到子集s，反之則是攻擊節點產生的區塊不會加入集合。當迭代整個過程把全部區塊濾過一遍以後，所有被判斷為誠實的區塊都會加入這個子集s，這時候的s被稱為最大的k-cluster子集，寫做msck，集合裡的所有區塊會被計入賬本。圖片3 一個最大子集為3-cluster的dag圖例，k=3
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
如圖3所示，誠實節點產生的區塊標記為藍色，攻擊節點產生的區塊標記為紅色。所有滿足圖片2要求的集合都屬於3-cluster的最大子集，也就是所有的藍色區塊都屬於msc3。我們來驗證一下是否這樣的區塊劃分能符合上述要求。anticone(g)={b, f, i, e, h, k};anticone(g)與藍色區塊的交集是b, f, i一共3個，滿足小於等於k值的要求（該dag的k值為3），故g是誠實節點產生的區塊，可以被計入賬本。所有的藍色區塊都滿足這一要求。anticone(e)={b, c, d, f, g, i};anticone(e)與藍色區塊的交集是b, c, d, f, g, i一共有6個，大於這裡的k值3，所以e被認為是攻擊節點產生的區塊，不會被計入賬本。所有的紅色區塊也都符合這一原則。依照這個規律依次濾過所有區塊就可以判斷和排除攻擊區塊。這背後的原理很簡單：區塊x的anticone(x)是指與x無關的區塊的集合，若anticone(x)與誠實節點產生的區塊交集越多則代表x與誠實區塊的連通度越低，這裡透過給連通度加上一個極限值k作為判斷標準。若anticone(x)與誠實區塊交集數高於k值，代表x區塊與誠實區塊的連通度低，x會被判斷為攻擊區塊；反之則代表x與誠實區塊的連通度高，x被認為是誠實區塊。 2 線性排序
在找到msck子集以後，下一步就是對集合裡的進行線性排序，排序的原則和拓撲排序一樣，如圖片4。圖片4 拓撲排序
來源：拓撲排序--百度百科,
https://baike.baidu.com/item/%e6%8b%93%e6%89%91%e6%8e%92%e5%ba%8f/5223807
拓撲排序是指把dag上的頂點排列成一個線性序列，由集合上的一個偏序得到該集合的一個全序的過程。排序的原則：優先選取沒有箭頭輸入的頂點為起點，每排完一個序列就把這個頂點從圖中移除，再從移除後的圖中選取沒有輸入的頂點作為下一個序列，如此循壞直到最後一個頂點被輸出。需要注意，拓撲排序的順序並不是唯一的，可能存在多種選擇方案，比如圖片4也可以在(c)步驟選擇輸出f, 最終順序為acfbde。根據這個原則，圖片3中的dag最終的輸出結果之一是：a->d->c->g->b->f->i->e->j->h->k。這個結果可以是任意的拓撲排序，但是藍色區塊會優先排列，紅色區塊由於連通度低會自然的排在藍色區塊後面。 3 phantom協議的應用舉例
從上文可知，phantom協議的第一步判斷誠實區塊是最關鍵最複雜的一步。怎麼高效的確定msck將直接影響全網的效能，這裡引入貪心演算法ghostdag來解決這個問題。先根據每個區塊的連通度（區塊past()集合裡的元素個數）來打分，選出總分最大的區塊組成主鏈，這些區塊會組成最初的子集s，剩下的區塊將依照主鏈的順序依次投票選出。原理是入選主鏈區塊都有著較高的連通度，可以優先加入s集合。這樣整個網路會按照連通度從高到低的趨勢去投票，用最快的方式找到最大的k-cluster子集msck。下面我們透過一個例子來完成覆盤一下phantom協議的運作過程：圖片5 phantom協議在一個k=3的dag圖中的應用示例（第一步）
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
圖中藍色小圓圈中的數字代表每個區塊x的連通度打分，分數和每個區塊past(x)裡的區塊數目相等。根據貪心演算法的規則，我需要選出一條總分最高的路徑，先選出分值最高的區塊m, 然後依次向前濾過m的所有過去區塊past(m)，如果遇到兩個區塊分值相等則隨機選擇一條路徑，最後選出的主鏈路徑如圖片5中藍色區塊所示：gensis->d->h>k->m，最初的s={genesis, d, h, k, m}。接下來驗證：d區塊past(d)只有創世區塊，anticone(genesis)是個空集，與s的交集個數為0≤3，所以創世區塊滿足3-cluster的子集要求，用藍色邊框標註。圖片6 phantom協議在一個k=3的dag圖中的應用示例（第二步）
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
第二步來到區塊h，past(h)除了創世區塊以外還有c, d, e, 分別找到這三個區塊的anticone集合並判斷它們與s之間的交集個數是否小於等於k值，這裡k值為3。anticone(c)={b, d, e, i, l}; 與s的交集是{d}，交集個數為1≤3。anticone(d)={b, c, f, e, i, l}; 與s的交集個數為0≤3。anticone(e)={b, c, d, f}; 與s的交集交集是{d}，交集個數為1≤3。因此這三個區塊都加入到3-cluster的子集中，這一步結束時子集更新為s={genesis, d, h, k, m, c, e}，在圖片6中用藍色邊框標註。圖片7 phantom協議在一個k=3的dag圖中的應用示例（第三步）
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
第三步訪問區塊k，past(k)中需要判斷h, i, b是否要加入子集s。anticone(h)={b, f, i, l}; 與s的交集個數為0≤3。anticone(i)={b, c, d, h, f, j};與s的交集為{c, d, h}，交集個數為3≤3。所以在這一步結束時h和i也要加入s，在圖片7中用藍色邊框標註。anticone(b)={c, d, e, h, i, l}；與s的交集為{c, d, e, h}，交集個數為4>3。所以b不滿足3-cluster的子集條件，不會被加入到子集中，b被判定為惡意節點產生的區塊。第三步結束時，子集更新為s={genesis, d, h, k, m, c, e, i}。圖片8 phantom協議在一個k=3的dag圖中的應用示例（第四步）
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
第四步訪問區塊m，past(m)中需要判斷f, k是否要加入子集s。anticone(k)={f, j, l}; 與s的交集個數為0≤3。anticone(f)={d, h, k, e, i, l}；與s的交集為{d, h, k, e, i}，交集個數為5>3。所以區塊k被加入到子集，而f不被加入。這裡更新子集s={genesis, d, h, k, m, c, e, i}。 圖片9 phantom協議在一個k=3的dag圖中的應用示例（第五步）
來源：yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
最後一步，訪問到一個還沒正式產生的虛擬區塊v，v引用的區塊是tips(g)，這意味著past(v)是整個現有所有區塊，在圖片9中用虛線表示。繼續判斷j, m, l是否加入子集。anticone(m)={j, l}; 與s的交集個數為0≤3。anticone(l)={b, c, f, j, m, h, k}；與s的交集為{c, m, h, k}，交集個數為4>3, l不屬於3-cluster的子集。anticone(j)={m, k, i, l}; 與s的交集為{m, k, i}，交集個數為3≤3；按理說j應該加入子集，但是這會導致anticone(i)最終與最大子集msc3的交集變為{c, d, h, j}，交集個數4>3，i不能被加入到子集集合中。這會得到一個與前面步驟相矛盾的結果，所以這裡不能把j加入子集。最終這個dag圖的最大3-cluster的子集msc3={genesis, d, h, k, m, c, e, i}。（注意：圖片9中的l不屬於msc3所以不應該被標註為藍色邊框，這裡為圖示錯誤）先對msc3中的藍色區塊做拓撲排序 genesis->d->e->c->i->h->k->m。再對不在msc3中的黑色邊框區塊排序然後新增到藍色區塊的排列之後，最終排序為 genesis->d->e->c->i->h->k->m->b->f->l->j。交易在每個區塊內部會自動按照它們的出現順序排序，至此整個網路的線性排序就完成了。 4 總結
當k=0時，phantom的規則就表現為比特幣的最長鏈共識，和spectre協議一樣，phantom協議是最長鏈共識的拓展。與spectre的不同之處在於phantom這種可以嚴格排序的賬本共識也適用於有智慧合約要求的網路。目前還沒有哪個dag專案採用這兩種協議中的任意一種，也許是在程式碼層面的實現還有一些難度，但是這兩個協議的安全性已經在數學理論上得到了驗證，我們期待未來會有更進一步的發展。下一篇我們簡單介紹一些已經落地的dag專案。
參考資料：
[1] ghost, dag, spectre, phantom和conflux技術原理，https://www.jianshu.com/p/8734e06d558f
[2] yonatan sompolinsky, shai wyborski, and aviv zohar，phantom and ghostdag a scalable generalization of nakamoto consensus
[3] 共識演算法解讀:泛化的中本聰共識phantom
，https://www.tuoluocaijing.cn/article/detail-10009964.html
[4] dag的妙用（三）——比特幣協議的擴充套件,
https://mp.weixin.qq.com/s/keqdvqmjlqlyxqcywfe8sq
[4] 拓撲排序--百度百科,
https://baike.baidu.com/item/%e6%8b%93%e6%89%91%e6%8e%92%e5%ba%8f/5223807
歷史文章
希望大家可以關注微信公眾號更加方便交流。公眾號的文章也會率先更新~
