共識演算法解讀:泛化的中本聰共識PHANTOM

買賣虛擬貨幣
引言比特幣執行了十幾年都非常的安全,但是飽守詬病的問題就是它的吞吐量太低了,這也是由它的安全模型即最長鏈規則決定的。最長鏈規則要求所有的誠實節點能迅速接收到新建立的區塊,因此,必須要等到一個區塊完全傳遞到所有節點才能建立下一個塊,並且保證了建立的"孤塊"(orphan blocks)非常的少。那麼從這個角度上來講,就是吞吐量和安全之間必須進行權衡,而比特幣協議的最長鏈規則限制了這個權衡規則,有沒有更好的思路呢?

答案就是,在並行的同時保障安全。以色列的研究團隊,在2020年的《PHANTOM and GHOSTDAG A Scalable Generalization of Nakamoto Consensus[1]》一文中,提出了在藉助於有向無環圖DAG,使用一個引數k(後面具體介紹k的來歷)來限定網路的安全容忍度的同時,且保障了並行出塊(因為新區塊,會引用所有DAG的葉子節點作為父塊,而不是直接丟棄網路中沒有到主鏈上的快,然後先出塊再排序)。比如下圖,B,C,D,E可以並且出塊,且V是新出的塊,它需要引用J,M,L。

直觀上來看,具體的思路是怎樣的呢?

類比比特幣,定義網路的延遲是D,那麼為了保證沒有分叉,那麼D這個時間段內就不能再產生塊了,也就是每秒出塊速度得很慢,我們可以認為是肯定小於k個塊。具體而言就是網路時延1秒的話,1秒內最多產生1/600個塊(10分鐘出一個塊)。

那麼把這個概念拓展一下就是,在DAG圖中的塊,需要保證在一個出塊的週期內(此處指的是沒有明顯的前後引用關係),最多出k個塊。

PHANTOM協議的思路也就由此而來,它需要保證在同一個出塊階段內,最多出(k+1)個塊。為了保證這點,它先定義了anticone函式:對於一個塊B,查詢它所在的DAG圖中與他沒有直接或間接引用關係(也就是在DAG圖中不能訪問到的)的塊的數目。比如說下圖中區塊G,在整個DAG圖中它不能訪問到B,F,I,H,K所以anticone(B)=B,F,I,H,K。並定義|anticone(B)|為總共塊的數目,也即5.

然後就需要求解一個最大k-cluster子DAG圖的問題,記為MCSk:

簡單來說就是這樣一個問題:

•輸入:DAG
•輸出:一個最大子DAG圖S’,S‘中任一區塊B的anticone在S’的塊的數目不超過k。

舉圖2中最大3-cluster的例子,藍色的塊構成的DAG圖就是最終找到的MCS3。很容易驗證任何一個藍色的塊都滿足|anticone(B)|≤3,比如anticone(G)=B,I,F。而anticone(E)=(B, C, D, F, G, I),有6個塊,不滿足。並且可以看出k=3時,實際上保證了每一個出塊間隔內最多產生3+1個塊(因為不同階段的明顯可以透過引用關係直接確定),也就是說k決定了每個出塊間隔最多出k+1個塊。

但是實際上,這個問題是個NP-hard問題,所以作者採用簡單的貪心法來構建MCSk,也就是先把之前滿足MCSk條件的DAG圖建立好,然後新建立的區塊再去找到滿足它的條件的塊,判斷是否滿足MCSk條件,並加入到MCSk中。

找到MCSk之後,就可以進行確定區塊的全域性序了。

整個DAG區塊的序按照如下方式確定:

1.確定好MCSk,然後把它標記為藍色的,其他的塊標記為紅色的
2.對MCSk按照拓撲排序(也就是DAG圖中從創世區塊開始,根據邊的關係,後面被訪問到的就排後面),這樣就確定了一個主鏈;然後再對藍色塊中,沒有在主鏈上的逐個加入到序列中;最後把紅色的區塊,按照拓撲排序加入進來。

聽起來是不是頭暈了,還是舉個簡單的例子吧,假設k=3,我們來按照下圖構建全域性的序(V為虛擬區塊便於理解):

1.從M開始(因為它包含的過去的區塊最多),再選K(因為F的過去的區塊只有3個),依次選取H,D,genesis,從而構建出主鏈

2.然後再迭代地構建MCSk

1.首先訪問D,過去的只有Genesis,所以新增創世區塊到藍色塊中
2.訪問H,然後判斷C,D,E的|anticone|是否小於等於3,發現都滿足,所以新增C,D,E
3.訪問K,同理新增H,I
4.訪問M,新增K,因為|anticone(F)|=4,所以不能新增F
5.然後新增M

3.排序

1.根據任意的拓撲排序演算法確定藍色集合的序,比如Genesis,D,E,C,I,H,K,M
2.將紅色區塊進行拓撲排序並加在後面,逐個加上B,F,L,J

· 因此總體的序為:Genesis,D,E,C,I,H,K,M,B,F,L,J
· 最後按照交易在區塊內部的出現的順序進行排序,就可以確定交易的序了

感興趣的可以看下,形式化的演算法如下:

實際上,我們發現如果把k設為0,那麼這就是中本聰共識。

拓展性又如何呢?

在此,我們定義協議的拓展性指的是,在不犧牲安全門限(惡意節點控制的最小算力比例)的同時,還能提高區塊的生成速度。

作者證明了PHANTOM可以保證安全門限的下限是1 /2 · (1 − δ),而δ由k來控制,k越大δ越小。

增加區塊產生速度λ:安全門限不會隨著λ增大而增大,但是同時受到節點頻寬的限制,比如頻寬1M的話,一個區塊大小是1M,那麼λ最多可以提升到每秒出一個塊。

提升安全性:提升安全門限,需要提升k,但是會增大確認時間

存活性(確認時間):區塊被篡改的風險,隨著不斷出塊,指數級下降。假設網路延遲7秒,可以安全地設定k=16,在攻擊者算力為α ≤ 0.25,被篡改的概率為ϵ = 0.1% 時,交易確認時間僅為45秒。並且確認時間,對網路延遲增大不敏感。

總結

PHANTOM在DAG資料結構的區塊鏈上,將中本聰共識進行了泛化,它不需要事先設定出塊間隔等限制,因此也接觸了中本聰共識對拓展性-安全性的權衡。採用貪心演算法,也便於實現,並且安全性也被嚴格證明了。

但是具體的實驗資料,目前還是沒有,需要進一步的驗證...

免責聲明:

  1. 本文版權歸原作者所有,僅代表作者本人觀點,不代表鏈報觀點或立場。
  2. 如發現文章、圖片等侵權行爲,侵權責任將由作者本人承擔。
  3. 鏈報僅提供相關項目信息,不構成任何投資建議

推荐阅读

;