在 Crypto Wednesday No.26 上,Nervos 共識研究員萬涔涔爲我們分享了 CKB 的共識算法:NC-Max,並清晰的解析了其設計原理,以下爲分享整理稿。
NC-Max 是 Nervos 底層公鏈 CKB 的共識算法。如果只用一句話介紹 NC-Max,那我會引用 NC-Max 的發明者張韌博士的說法:「將交易的確認和交易的同步解耦」
NC —— 蹣跚的巨人
要理解 NC-Max,我們先從 NC 開始,NC 是 Nakamoto Consensus,也就是中本聰共識的簡稱,它是第一個在開放網絡中運行的共識算法,礦工可以隨時加入和退出。
在 NC 中,礦工們解決哈希難題,提出區塊,若出現分叉則採用最長鏈原則確定主鏈,最重要的是,NC 引入了激勵機制給共識的安全持續運行提供了源源不斷的燃料。這個共識算法相比傳統的 BFT 算法會更容易理解,並且作爲比特幣的共識算法扛過了十年的安全考驗,我們基本上可以認爲它是安全的。
時至今日,NC 的代表——比特幣,依然佔據着加密貨幣總市值的 60%+,是當之無愧的巨人。然而,7 筆 / 秒的速度,是這個巨人蹣跚的腳步。
那麼 7 筆 / 秒的吞吐量是怎麼得到的?這裏有一個公式,將比特幣的參數帶入計算就能得到這個結果。
吞吐量 = 區塊大小 /(交易大小出塊間隔)
如果想要提高比特幣的吞吐量,最直接的方法就是:
1、提高區塊大小;
2、降低出塊間隔。
以太坊採取了第二種方式,將出塊間隔降低到 12s。相比出塊間隔數十倍地減少,以太坊的吞吐量僅提升了一倍——只有 15 筆 / 秒左右的吞吐量。這顯然不盡人意。
這是因爲,隨着出塊間隔的縮短,以太坊的區塊鏈上出現了頻繁的分叉,那些無法進入主鏈的區塊就成了孤塊。當孤塊率較高時,這些孤塊會浪費大量的算力和帶寬,並會帶來安全上的問題:如果礦工按最長鏈原則來確認主鏈,當出現大量孤塊的時候惡意節點只需要消耗遠低於一半的算力就能雙花。
爲了緩解這個安全問題,以太坊採用了 Ghost 協議,但是其吞吐量還是受到孤塊的制約。那麼,讓我們先來看看孤塊是如何產生的。
孤塊從何而來
這張圖是比特幣的區塊廣播過程,A 節點挖出高度爲 H 的區塊,並廣播緻密區塊,緻密區塊裏面只包含交易哈希而非完整的交易,A 在出塊之後就能開始挖高度爲 H+1 的區塊。礦工 B 收到緻密區塊的時候,首先根據交易哈希查看本地交易池中是否有這些交易,對於本地沒有的新交易,B 會向 A 詢問,A 會返回這些新交易的完整內容。當 B 對所有新交易驗證之後才能開始挖高度爲 H+1 的區塊 。那這中間就有一個 Gap。
在上面的描述中顯然大家能夠看到,B 開始挖高度爲 H+1 的區塊的時間和 A 開始挖的時間有一個時差,我們定義爲區塊傳播時延。因爲,在高度爲 H 的區塊廣播的過程中 B 是不會停止手上的工作的,因爲 B 是不相信 A 的區塊是有效區塊的,萬一被 A 耍了呢?那麼在這個時間裏,如果 B 挖出另一個高度爲 H 的區塊,那就有兩個高度爲 H 的區塊,其中一定會有一個成爲孤塊。
我們再回到以太坊的孤塊問題上,由於相比比特幣,以太坊出塊間隔很低,因此其挖礦難度也遠低於比特幣。在區塊廣播時延相同的情況下,以太坊礦工挖出區塊的概率遠高於比特幣,因此其孤塊率會很高。而實際上以太坊的網絡設計導致其區塊傳播時延比比特幣更長。
實際上,我們可以得到這樣一個關係:
*孤塊率和(區塊傳播時延 / 出塊間隔)成正比。**
所以,在出塊間隔固定的情況下,降低區塊傳播時延就能降低孤塊率。
NC-Max 之道
交易兩步確認
在前面的分析裏,區塊傳播時延包括兩部分,區塊的廣播 +新交易的廣播。這是串行的過程,那麼如果我們能夠把這兩個過程並行,就能有效地縮短區塊傳播時延,進而降低孤塊率。
怎樣讓區塊傳播與新交易的傳播並行呢,NC-Max 設計了一個交易兩步確認的機制。簡單來說,就是在緻密區塊中既包含新交易的哈希值,我們叫 propose 交易,以通知其他礦工同步新交易。又包含老交易的哈希值,我們叫 confirm 交易,這些老交易是前幾個塊中已經通知過的新交易,應該完成同步了,只要礦工完成了這些老交易的同步,就可以立即開始挖下一個區塊。
具體來說,高度爲 h 的區塊所包含的老交易,必須是在高度爲 h-n 到 h-m 之間的區塊包含過的新交易。因此老交易有至少 m 個區塊間隔的時間來完成同步。
在正常情況下,NC-Max 的區塊傳播過程是這樣的。礦工 A 挖出區塊後,立即廣播緻密交易,礦工 B
收到緻密交易後,確認老交易都已經同步過了,可以立即開始挖下一個區塊。新交易的同步過程與新高度的挖礦並行進行。通過這樣的設計,區塊傳播時延相比改進之前縮短了許多,因而在同樣的出塊間隔下,孤塊率也能得到顯著的改善。因此,張韌博士說,NC-Max 將交易的確認與交易同步解耦,這句話道出了交易兩次確認的精髓。
根據孤塊率調整難度
讓我們再回到孤塊率的公式。我想問大家一個問題:孤塊率是越小越好嗎?
區塊傳播時延是有上限的,追求越小的孤塊率,意味着要設置越大的出塊間隔,也就會得到越低的吞吐量。過於追求極致小的孤塊率,會得到一個極致不可用的區塊鏈。我們需要的是一個能夠平衡安全和吞吐量的孤塊率。
假設我們找到了這樣一個安全閾值,那麼我們設置多大的出塊間隔合適?區塊傳播時延是動態變化的,受帶寬、網絡擁堵情況的影響,如果將出塊間隔設置得過於保守,比如像比特幣的 10 分鐘,則吞吐量也會非常保守。如果設置得過於激進,則一旦網絡出現較大波動,就會導致孤塊率遠超安全閾值,影響系統安全。
況且,網絡帶寬隨着技術的進步還將逐漸改善,這也意味着區塊傳播時延從長期來講會逐漸下降。固定的出塊間隔無法適應動態的網絡變化。
既然孤塊率纔是我們要穩定的目標,於是 NC-Max 改變了難度調整的策略,以孤塊率作爲難度調整的依據。爲了能夠計算孤塊率,我們在區塊結構中增加了叔塊區,一個區塊中可以包含若干叔塊。同時,我們還將區塊鏈按固定時長劃分成許多難度調整週期,每個難度調整週期的孤塊率等於叔塊總數除以總區塊數。當孤塊率大於我們預設的安全閾值時,難度上升,區塊間隔上升,從而使得孤塊率回落到安全閾值。反之亦然。
根據孤塊率調整難度,結合交易兩次確認,使得 NC-Max 的吞吐量能夠達到安全閾值下網絡所能承載的最大吞吐量。這就是 NC-Max 之道。