區(qū)塊鏈?zhǔn)且环N去中心化、不可篡改、可追溯的分布式數(shù)據(jù)庫(kù)系統(tǒng)，可確保數(shù)據(jù)安全，并防止未經(jīng)授權(quán)的訪問。區(qū)塊鏈技術(shù)允許用戶在分布式賬本中添加、查看和驗(yàn)證交易，并使用共識(shí)機(jī)制來(lái)確保所有交易準(zhǔn)確無(wú)誤。

在區(qū)塊鏈中，共識(shí)機(jī)制用于保證網(wǎng)絡(luò)上的所有節(jié)點(diǎn)都同意網(wǎng)絡(luò)的當(dāng)前狀態(tài)和交易的真實(shí)性，這對(duì)于維護(hù)區(qū)塊鏈的安全性和完整性至關(guān)重要，圖1展示了區(qū)塊鏈共識(shí)過程的基礎(chǔ)模型。不同的區(qū)塊鏈平臺(tái)使用不同的算法，例如POW、POS或POB等，以在網(wǎng)絡(luò)上的節(jié)點(diǎn)之間達(dá)成共識(shí)。一個(gè)好的共識(shí)算法可以保持區(qū)塊鏈網(wǎng)絡(luò)的活躍，為整個(gè)網(wǎng)絡(luò)提供源源不斷的有效算力，而設(shè)計(jì)不佳的算法則可能導(dǎo)致整個(gè)網(wǎng)絡(luò)在受到攻擊時(shí)很容易癱瘓。共識(shí)算法可以分為：非拜占庭容錯(cuò)算法與拜占庭容錯(cuò)算法，基于DAG和混合算法，在本次報(bào)告中主要介紹拜占庭容錯(cuò)算法。

圖1 區(qū)塊鏈共識(shí)過程的基礎(chǔ)模型

拜占庭容錯(cuò)算法（Byzantine Fault Tolerance，BFT）是一類分布式系統(tǒng)中用于處理節(jié)點(diǎn)故障和惡意行為的算法。該算法的目標(biāo)是確保在存在節(jié)點(diǎn)錯(cuò)誤或惡意行為的情況下，系統(tǒng)仍能夠達(dá)成一致的共識(shí)。BFT的概念起源于拜占庭將軍問題，其機(jī)制的目的是通過一種集體決策過程來(lái)防范系統(tǒng)故障，該過程考慮了正確節(jié)點(diǎn)和故障節(jié)點(diǎn)的輸入，旨在最小化故障節(jié)點(diǎn)的影響。本報(bào)告主要介紹了pBFT、POW、POS、POB、POC、POA、DPOS共識(shí)算法。

1、Practical Byzantine fault?tolerant (pBFT)

實(shí)用拜占庭容錯(cuò)算法 (pBFT) 是 Barbara Liskov 和 Miguel Castro 在 1999年提出的一種共識(shí)算法[1]，解決了原始拜占庭容錯(cuò)算法效率不高的問題，將算法復(fù)雜度由指數(shù)級(jí)降低到多項(xiàng)式級(jí)，使得拜占庭容錯(cuò)算法在實(shí)際系統(tǒng)應(yīng)用中變得可行。  

pBFT可以在保證活性和安全性的前提下提供（n-1)/3的容錯(cuò)性, 其中 n 為節(jié)點(diǎn)總數(shù)，即只要惡意節(jié)點(diǎn)的最大數(shù)量小于或等于系統(tǒng)中所有節(jié)點(diǎn)的三分之一，pBFT 系統(tǒng)就可以正常運(yùn)行。在啟用 pBFT 的系統(tǒng)中，節(jié)點(diǎn)按順序排序，其中一個(gè)節(jié)點(diǎn)為主節(jié)點(diǎn)，其他節(jié)點(diǎn)為輔節(jié)點(diǎn)。主節(jié)點(diǎn)在每次視圖期間都會(huì)發(fā)生更改，并且如果經(jīng)過了預(yù)定義的時(shí)間而沒有主節(jié)點(diǎn)向輔節(jié)點(diǎn)廣播請(qǐng)求，則可以通過視圖更改協(xié)議替換主節(jié)點(diǎn)。

pBFT共識(shí)分為五個(gè)階段，如圖2所示，其中C為發(fā)送請(qǐng)求端，0123為服務(wù)端，3為宕機(jī)的服務(wù)端，具體步驟如下：

請(qǐng)求階段(request): 請(qǐng)求端C發(fā)送請(qǐng)求到主節(jié)點(diǎn)，這里主節(jié)點(diǎn)是0；

預(yù)準(zhǔn)備階段(pre-prepare)：服務(wù)端0收到C的請(qǐng)求后進(jìn)行廣播，擴(kuò)散至服務(wù)端123；

準(zhǔn)備階段(prepare): 服務(wù)端123收到后記錄并再次廣播，1->023，2->013，3因?yàn)殄礄C(jī)無(wú)法廣播；

提交階段(commit): 服務(wù)端0123節(jié)點(diǎn)在Prepare階段，若收到超過一定數(shù)量的相同請(qǐng)求，則進(jìn)入Commit階段，廣播Commit請(qǐng)求；

回復(fù)(reply): 0123節(jié)點(diǎn)在Commit階段，若收到超過一定數(shù)量的相同請(qǐng)求，則對(duì)C進(jìn)行反饋。

圖2 PBFT 算法流程

pBFT首次提出在異步網(wǎng)絡(luò)環(huán)境下使用狀態(tài)機(jī)副本復(fù)制協(xié)議，該算法可以工作在異步環(huán)境中，并且通過優(yōu)化在早期算法的基礎(chǔ)上把響應(yīng)性能提升了一個(gè)數(shù)量級(jí)以上。但該算法僅僅適用于permissioned systems 且通信復(fù)雜度使得系統(tǒng)性能隨著網(wǎng)絡(luò)規(guī)模的增加而下降。

2、Proof of work (PoW)

圖片

圖3 POW算法流程

PoW的優(yōu)點(diǎn)是完全去中心化 ，節(jié)點(diǎn)自由進(jìn)出；只要破壞者算力不超過網(wǎng)絡(luò)總算力的50%，交易狀態(tài)就能達(dá)成一致。PoW 的缺點(diǎn)是挖礦造成大量資源浪費(fèi)；礦池算力高度集中；達(dá)成共識(shí)周期較長(zhǎng)(每秒最多7筆交易)；還存在自私挖礦攻擊的風(fēng)險(xiǎn)。

3、Proof of stake (PoS)

PoS 共識(shí)算法因其節(jié)能特性而被認(rèn)為是 PoW 有前途的替代方案。PoS 由系統(tǒng)中具有最高權(quán)益而非最高算力的節(jié)點(diǎn)獲得記賬權(quán)[3]。相對(duì)于PoW中 Nonce 字段的大搜索空間而言, PoS 將搜索空間限制在一個(gè)計(jì)算量可接受的范圍; 除此外，PoS 中還引入了“幣齡”作為權(quán)益,即：

圖片

競(jìng)爭(zhēng)出塊記賬前，擁有權(quán)益的節(jié)點(diǎn)將自己的權(quán)益放入PoS機(jī)制中，同時(shí)身份變?yōu)轵?yàn)證者，PoS機(jī)制根據(jù)驗(yàn)證者下注的多少，選出一個(gè)記賬者進(jìn)行出塊記賬。選擇算法綜合使用候選者的股權(quán)（持有的加密貨幣數(shù)量）和其他因素（如幣齡和隨機(jī)化），以確保網(wǎng)絡(luò)上所有節(jié)點(diǎn)之間的公平性。其中一個(gè)因素是幣齡，它是候選節(jié)點(diǎn)成為驗(yàn)證者的時(shí)間。節(jié)點(diǎn)擔(dān)任驗(yàn)證者的時(shí)間越長(zhǎng)，被選為記賬者的機(jī)會(huì)就越大。另一個(gè)因素是隨機(jī)塊選擇，其中驗(yàn)證器是根據(jù)最低哈希值和最高權(quán)益的組合來(lái)選擇的。具有這些因素的最佳加權(quán)組合的節(jié)點(diǎn)成為新的記賬者。如果選出的記賬者在一段時(shí)間內(nèi)沒有記賬，PoS機(jī)制重新選擇記賬節(jié)點(diǎn)，當(dāng)出塊完成，開始進(jìn)入下一輪的記賬。

PoS縮短了共識(shí)達(dá)成的時(shí)間，降低了PoW機(jī)制的資源浪費(fèi)。但是破壞者對(duì)網(wǎng)絡(luò)攻擊成本低，存在“無(wú)利害關(guān)系“（Nothing at stake）”攻擊問題，且共識(shí)受少數(shù)富裕賬戶支配，缺乏公正性。

圖4 POS算法流程

4、Proof of burn (PoB)

在 "燒毀證明"（PoB）中，驗(yàn)證者通過 "燒毀 "貨幣或?qū)⑵浒l(fā)送到一個(gè)永遠(yuǎn)無(wú)法取回的地址來(lái)表示自己愿意為了長(zhǎng)期投資而承受短期的損失，以及獲得在某個(gè)隨機(jī)選擇程序系統(tǒng)上進(jìn)行挖礦的終生特權(quán)[4]。這一過程用于確定哪些驗(yàn)證者能夠挖掘系統(tǒng)中的下一個(gè)區(qū)塊。驗(yàn)證者可以使用本地社區(qū)的貨幣或比特幣等替代鏈的貨幣，以增加被選中進(jìn)行區(qū)塊挖掘的機(jī)會(huì)。礦工燒掉的貨幣越多，被系統(tǒng)選中開采下一個(gè)區(qū)塊的機(jī)會(huì)就越大。隨著新區(qū)塊的挖出，被燒毀幣的能量會(huì)略有減少，從而產(chǎn)生一個(gè)通縮過程，即貨幣的總量會(huì)隨著時(shí)間的推移而減少，從而有可能增加其價(jià)值。相比之下，數(shù)量隨時(shí)間增加的加密貨幣往往會(huì)貶值。

PoB更環(huán)保，因?yàn)樗⒉粡?qiáng)調(diào)硬件的功率或數(shù)量，貨幣銷毀會(huì)永久減少被銷毀的加密貨幣的供應(yīng)，從而導(dǎo)致稀缺性和資產(chǎn)價(jià)值增加。雖然在硬件方面，PoB不需要像Pow那樣多的資源，但它會(huì)破壞通過計(jì)算創(chuàng)建的硬幣，這也是一種浪費(fèi)。PoB中，由于銷毀是最終的結(jié)果，沒有任何保證可以收回?zé)龤У呢泿诺娜績(jī)r(jià)值，這增加了用戶的風(fēng)險(xiǎn)。

5、Proof of capacity (PoC)

容量證明（PoC）是一種新的挖礦方法，目前在加密貨幣 Burstcoin 中使用[5]?？臻g容量證明利用的是計(jì)算機(jī)的硬盤空間大小而不是電腦的計(jì)算能力。硬盤的容量越大，可以儲(chǔ)存在硬盤里的方案值就越多，礦工就越有機(jī)會(huì)匹配到其中所需要的哈希值，從而有更多的機(jī)會(huì)獲得獎(jiǎng)勵(lì)。

PoC 通過在計(jì)算機(jī)上提供更多解決方案或“圖”來(lái)增加礦工贏得挖礦競(jìng)爭(zhēng)的機(jī)會(huì)。PoC由兩個(gè)主要部分組成：繪圖和挖礦

• 繪圖：礦工使用 Shabal 哈希函數(shù)創(chuàng)建一系列預(yù)先計(jì)算的哈希值并將其存儲(chǔ)在硬盤上。這個(gè)繪圖過程是一次性的，且根據(jù)硬盤的大小，繪制周期也將不同，一般為幾天甚至數(shù)周。哈希值被分組為“scoops”，每個(gè)scoop由兩個(gè)相鄰的哈希值組成。
• 挖礦：挖礦需要計(jì)算scoop數(shù)，并將其應(yīng)用于存儲(chǔ)在硬盤驅(qū)動(dòng)器上的每個(gè)nonce值，以確定一個(gè) "截止日期 "值。如果在該時(shí)間段內(nèi)沒有其他人創(chuàng)建新區(qū)塊，礦工就會(huì)選擇截止日期最短的 nonce 并使用它來(lái)創(chuàng)建新區(qū)塊。如果礦工在截止日期前創(chuàng)建了區(qū)塊，就會(huì)獲得區(qū)塊獎(jiǎng)勵(lì)。

POC挖礦減少了大量的計(jì)算，同時(shí)避免了AISC化的礦機(jī)出現(xiàn)，大大降低了挖礦的門檻和礦工的成本。

6、Proof of activity (PoA)

活動(dòng)證明（PoA）結(jié)合了PoW工作量證明與PoS權(quán)益證明的特點(diǎn)并進(jìn)行了相應(yīng)擴(kuò)展[6]，PoA共識(shí)具有更為復(fù)雜的記賬節(jié)點(diǎn)選取，同時(shí)有更為公平的獎(jiǎng)勵(lì)機(jī)制。通過考慮礦工的利益，網(wǎng)絡(luò)可以優(yōu)先考慮那些對(duì)網(wǎng)絡(luò)建設(shè)有長(zhǎng)遠(yuǎn)利益的礦工，而不僅僅是那些擁有最強(qiáng)大計(jì)算資源的礦工。其具體步驟如下：

• 每個(gè)礦工先利用自身算力通過工作量證明機(jī)制后得出nonce并生成一個(gè)空區(qū)塊頭，這個(gè)區(qū)塊頭除了沒有交易信息數(shù)據(jù)外其他數(shù)據(jù)與正常區(qū)塊一致。
• 最先生成空區(qū)塊的節(jié)點(diǎn)廣播全網(wǎng)節(jié)點(diǎn)，全網(wǎng)節(jié)點(diǎn)接收到消息后，將此區(qū)塊的hash值與上一區(qū)塊的hash值進(jìn)行拼接，然后加上n個(gè)固定后綴值進(jìn)行再hash，最后得出n個(gè)值作為輸入，進(jìn)入follow-the-satoshi程序，然后可輸出n個(gè)隨機(jī)權(quán)益持有者。擁有大量加密貨幣的礦工被選為簽名者的機(jī)會(huì)更高。
• 前n-1個(gè)隨機(jī)權(quán)益持有者對(duì)空區(qū)塊進(jìn)行簽名，第n個(gè)隨機(jī)權(quán)益持有者即為獲取到記賬權(quán)的節(jié)點(diǎn)，他將在空區(qū)塊的基礎(chǔ)上添加交易數(shù)據(jù)與簽名。
• 第n個(gè)隨機(jī)權(quán)益持有者將打包好的區(qū)塊廣播全網(wǎng)，全網(wǎng)節(jié)點(diǎn)接收到區(qū)塊后進(jìn)行驗(yàn)證，驗(yàn)證成功后上鏈。
• 產(chǎn)生空區(qū)塊的礦工與第n個(gè)隨機(jī)權(quán)益持有者以及前n-1個(gè)已簽名的隨機(jī)權(quán)益持有者共享交易費(fèi)獎(jiǎng)勵(lì)。

PoA 可以有效地平衡區(qū)塊鏈的安全性和效率，但與純 PoW 或 PoS 系統(tǒng)相比，PoA 的實(shí)施可能更復(fù)雜，安全性也可能更低。PoA因部分使用PoW和PoS而被詬病，但也防范了51%攻擊的風(fēng)險(xiǎn)。

7、Delegate proof of stake (DPoS)

圖片

大幅縮少參與驗(yàn)證和記賬節(jié)點(diǎn)的數(shù)量，能達(dá)到秒級(jí)的共識(shí)驗(yàn)證；另外, 區(qū)塊的產(chǎn)生不需要消耗算力, 相對(duì)于 PoS 更加節(jié)省能耗。但不合適完全去中心化的場(chǎng)景。

區(qū)塊鏈技術(shù)的出現(xiàn)代表了數(shù)字貨幣經(jīng)濟(jì)時(shí)代的到來(lái)。但是區(qū)塊鏈的共識(shí)機(jī)制仍然還面臨一些挑戰(zhàn)，區(qū)塊鏈的共識(shí)機(jī)制還有可進(jìn)步之處。只有做到各方面的平衡，通過之后的發(fā)展以及不斷的更迭，才能設(shè)計(jì)出更加適合實(shí)際應(yīng)用場(chǎng)景的共識(shí)機(jī)制。

參考文獻(xiàn)

[1] Miguel Castro, Barbara Liskov, et al. Practical byzantine fault tolerance. In OsDI, volume 99, pages 173–186, 1999.

[2] Shixiong Jin, X Zhang, J Ge, HB Shi, Y Sun, M Li, YM Lin, and ZJ Yao. Overview of blockchain consensus algorithm. Journal of Information Security, 6(2):85–100, 2021.

[3] Chaya Ganesh, Claudio Orlandi, and Daniel Tschudi. Proof-of-stake protocols for privacy-aware blockchains. In Advances in Cryptology–EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany, May 19–23, 2019, Proceedings, Part I 38, pages 690–719. Springer, 2019.

[4] Kostis Karantias, Aggelos Kiayias, and Dionysis Zindros. Proof-of-burn. In Financial Cryptography and Data Security: 24th International Conference, FC 2020, Kota Kinabalu, Malaysia, February 10–14, 2020 Revised Selected Papers 24, pages 523–540. Springer, 2020.

[5] Shubhani Aggarwal and Neeraj Kumar. Cryptographic consensus mechanisms. In Advances in Computers, volume 121, pages 211–226. Elsevier, 2021.

[6] Manpreet Kaur, Mohammad Zubair Khan, Shikha Gupta, Abdulfattah Noorwali, Chinmay Chakraborty, and Subhendu Kumar Pani. Mbcp: Performance analysis of large scale mainstream blockchain consensus protocols. IEEE Access, 9:80931–80944, 2021.

[7] Fan Yang, Wei Zhou, QingQing Wu, Rui Long, Neal N Xiong, and Meiqi Zhou. Delegated proof of stake with downgrade: A secure and efficient blockchain consensus algorithm with downgrade mechanism. IEEE Access, 7:118541–118555, 2019.