AND:深度解析Algorand共識協議_Philosoraptor

*免責聲明：該文僅代表研究人員個人觀點，不代表Qtum量子鏈基金會立場概述

1.1引言

Algorand稱其突破了”公鏈不可能三角“，項目創始人是圖靈獎得主、MITCSAIL實驗室的SilvioMicali教授。Algorand提出的共識協議是項目的一大亮點，本文主要分析Algorand共識協議的工作原理，并分析其優缺點。

1.2Algorand設計的初衷

Algorand想解決的核心問題是：去中心化網絡中低延時和高置信度之間的矛盾。

其中，延時指從發起交易到確認交易所需要的時間；置信度指的是發出的交易不會再被更改的概率。

在比特幣網絡中，為了提高交易的置信度，用戶必須等待6個區塊確認的確認延時；而如果選擇低延時，比如少于6個確認，甚至是0確認，則必然導致低置信度，增加“雙花”攻擊的可能。雙花問題是絕大多數加密數字貨幣的核心問題。比特幣中采用PoW共識來解決，但鏈本身仍然有分叉的可能，并且需要較長的共識達成過程和確認時間。

同時Algorand還想解決比特幣中PoW挖礦耗費巨大資源、交易確認時間長、易分叉、網絡呈中心化趨勢，可擴展性差等問題。

1.3Algorand是什么？

根據官方描述，Algorand是一個采用permissionless的純PoS共識的公鏈項目，結合改進的拜占庭共識協議，可實現快速的交易確認，幾乎不會分叉，并且用戶數可無限擴展，不會影響交易確認速度。同時兼顧“可擴展、安全性、去中心化”這個“公鏈不可能三角”。

可擴展性：Algorand通過可驗證隨機函數隨機選擇區塊的生產者和驗證者，一旦得知被選中，生產者或驗證者只需廣播一個簡短的消息即可證明自己的身份。每產生一個新區塊在網絡中需要交換的消息不會隨著用戶數的增大而改變，，因此即使用戶規模增大，系統仍可保持較高的TPS。Algorand的TPS是比特幣的125倍。

安全性：由于采用了上述的VRF隨機選取生產者和驗證者，并且選取的過程完全由節點獨立完成，因此Algorand網絡中的攻擊者無法預先得知下一個區塊生產者和驗證者，從而也就無法完成攻擊。具體來說，生產者和驗證者的身份只有在他們確定自己被選中并廣播對應的證明信息時才會被披露，這時攻擊者即使立刻采取各種攻擊手段，也無法阻止關于新區塊的正確消息在網絡中的傳播。

去中心化：Algorand中每一輪的區塊生產者和驗證者都是隨機選取的，并且加入網絡沒有任何門檻，因此是完全去中心化的。

下面詳細介紹Algorand的共識協議。

Algorand協議詳述

幾乎所有公鏈項目的區塊產生和共識的過程都可以抽象為兩個步驟：

SEC提出凍結交易所資產后，Binance.US市場深度開始下降:金色財經報道，區塊鏈分析平臺Kaiko數據顯示，在SEC提出緊急動議凍結交易所資產后，Binance.US市場深度開始下降。[2023/6/8 21:22:22]

選擇出區塊生產者，生成新區塊

其他節點對新區塊達成共識

以上步驟周而復始，最終形成一條“不可篡改”的區塊鏈。

整個共識過程雖然簡單，但在實際實現中，必須解決幾個關鍵問題：

如何選擇區塊生產者，且保證公平和不可被預測？

如何對新區塊達成共識？

如何避免分叉？

如何提高安全性？

如何擴展到更大規模的用戶？

比特幣采用哈希函數的隨機性來確保公平，采用工作量證明達成共識，同時能夠在一定程度上抵抗算力攻擊。然而比特幣仍然面臨上述消耗計算資源、確認時間長、易分叉以及擴展性差等問題。以Qtum為代表的采用純權益證明共識機制的項目，同樣采用了哈希函數，并且不需要消耗大量的計算資源，然而仍然面臨易分叉、安全性及擴展性的問題。

Algorand提出了一種新的共識機制解決上述5個問題。

2.1基礎知識

正式介紹Algorand共識協議之前，本文假設讀者基本了解以下名詞的含義：

哈希函數

公鑰/私鑰

數字簽名

交易

區塊

賬本

共識

拜占庭協議

誠實節點

攻擊節點

P2P通信

如果讀者對上述概念不理解，請先搜索相關關鍵詞進一步了解，再閱讀以下內容。

2.2Algorand的基本過程

Algorand協議可以按照時間順序劃分為不同輪次，每一輪都會達成共識并生成新區塊。其典型的通用過程如下：

每一輪共識開始時，隨機選出潛在的leaders，各自生成新區塊，對新區塊進行簽名和廣播

隨機選出驗證組，對leaders廣播的新區塊進行驗證，達成共識后廣播確認新區塊，進入下一輪

接下來具體討論Algorand共識協議細節，本節主要參考。

2.3保證Algorand的隨機性：可驗證隨機函數

Algorand利用VRF來選擇區塊生產者和驗證者，保證所有共識參與者都是隨機地、公平地被選出的。可驗證隨機函數是由Micali教授等提出的一種偽隨機函數，和普通的隨機函數一樣，對于不同輸入，其輸出也具有隨機性。其獨特之處在于調用者可以提供一個證明，表明這個隨機輸出確實由該調用者產生。

動態 | 蘭州市大數據服務中心將推進區塊鏈等新技術的深度應用:日前，蘭州市大數據服務和應用創新中心舉行啟動儀式。中心主要從加固基礎運行支撐環境、建立健全數據標準規范、拓展數據匯聚采集方式、打造數據運行維護體系、構建一體化數據運營體系等五個方面進行探索創新。下一步中心將圍繞實現“政通、惠民、興業”的目標，全面推進大數據、人工智能、區塊鏈等新技術的深度應用，不斷釋放數據價值、促進政務信息共享共用和業務流程協同再造，助力提升政府的現代化治理能力，助推蘭州市經濟社會實現跨越式發展。（人民網）[2020/1/13]

VRF可以有多種實現方式，Micali等人在其原始論文中提供了一種較復雜的實現方式。Algorand利用哈希函數和數字簽名的特性，提供了一種較為簡單的VRF實現。具體實現方式是調用者i將輸入m通過數字簽名和哈希函數映射為固定長度的輸出H,即m->H。

對于任何輸入m，不同的調用者i生成的數字簽名SIGi(m)都是唯一的；而對于不同輸入，哈希函數H的輸出具有隨機性，因此上述映射符合VRF的”隨機性“要求。同時，由于i的數字簽名SIGi(m)可通過其公鑰對其身份進行驗證，因此其也符合VRF”可驗證“的特性，SIGi(m)就是VRF中提到的”證明“。

這個函數特別適合在所有節點中隨機選擇出共識的參與者，下面具體討論。

2.3.1隨機選出每一輪的區塊生產者

每一輪共識開始時，每個節點都可以通過以下VRF獨立地驗證自己是否是潛在的leader：

.H<=1/SIZE(PK(r-k))

其中，H是哈希運算；SIG是簽名運算；r是目前的輪次；Q(r-1)為與r-1輪的種子；SIZE(PK(r-k))是在r-k輪所有符合要求的公鑰的數量；公式開始的.表示將哈希結果轉化為小數位，從而保證結果為[0,1)的某個值。

節點通過自己的私鑰計算上面簽名的哈希值是否符合要求，從而知道自己是否屬于候選的leader，在此過程中無需和其他節點交換信息。由于哈希函數輸出的隨機性，可以認為符合要求的候選節點都是隨機選出的。候選節點隨后可以生成新區塊，并向全網提供簽名證實自己的身份。如果有多個候選leader，最終上述哈希值最小的leader將在后續的共識中成為本輪最終的leader。Leader產生的區塊Br包含了本輪的所有交易和上述的證明信息，由驗證組成員進行共識驗證。

2.3.2隨機選出每一輪每一階段的驗證組

驗證組成員的選擇與上述過程類似，在每一輪和每一階段，所有節點都可以獨立驗證自己是否屬于驗證組成員：

.H<=n/SIZE(PK(r-k))

其中s為本輪所處的不同階段，Algorand在每一輪的各個階段都有不同的驗證組，從而進一步保證安全性；n為預期的驗證組成員數量，可以人為設定；其他參數含義不再重復。

聲音 | 深圳市委書記：深圳將加快區塊鏈等技術深度應用，推動技術融合、業務融合、數據融合:據人民網深圳報道，12月1日，深圳建設中國特色社會主義先行示范區“數字政府”高級別研討會舉行。深圳市委書記王偉中致辭表示，深圳將切實發揮建設粵港澳大灣區和支持深圳建設中國特色社會主義先行示范區“雙區”利好疊加優勢，對標最高最好最優，率先探索完善數據管理和安全保護機制，加快大數據、人工智能、5G、區塊鏈等先進技術深度應用，推動技術融合、業務融合、數據融合，實現跨層級、跨地域、跨系統、跨部門、跨業務的協同管理和服務，打開數字世界新空間，增強數字經濟新動能，拓展數字生活新內涵，努力建設具有世界一流水平的新型智慧城市標桿市，用數據為國家治理體系和治理能力現代化賦能，更好滿足人民對美好生活的向往,為建設網絡強國、數字中國、智慧社會作出新的更大貢獻。[2019/12/2]

與候選leader一樣，每一階段的驗證組成員均隨機選出，驗證節點在證實自己身份后，可以開始參與共識驗證過程，揭露自己的簽名即可證明其身份。

2.3.3引入權益證明機制

上述的隨機選擇過程沒有考慮Token持有者的權重，惡意節點可能通過大量生成有效私鑰從而有極大概率成為區塊的生產者和驗證者。Algorand在其公布的實現建議中引入了名為HonestMajorityofMoney的條件假設，其基本思想來源于PoS共識機制，即在上述隨機選擇過程中引入代幣持有量作為權重，持有量多的節點被選中的概率較高，而代幣持有者往往更傾向于保護網絡的安全性。具體可以表示為如下公式：

.H<=(a(i,r)/M)*(1/SIZE(PK(r-k)))

其中，a(i,r)/M為節點所持有的幣的數量占代幣總數M的權重。其余過程與前面描述一直。

2.4Algorand如何對新區塊達成共識：改進的拜占庭協議BA*

Algorand中驗證者對新區塊達成共識的過程，實際上是一種改進的拜占庭協議，Algorand稱其為BA*。

BA*由一種改進的二元拜占庭協議和分級共識協議組合而成。

2.4.1改進的二元拜占庭協議BBA*

Algorand引入的BBA*是一個改進的二元拜占庭協議。BBA*可以在誠實節點超過?的情況下，快速達成共識。其具體過程是一個3步循環，循環中每一步都有?的概率達成共識。

節點之間需要進行P2P通信，假設被選中的驗證節點中有t個惡意節點，驗證組總的節點數為n>=3t1，即惡意節點不超過?。協議過程如下：

上述協議中各符號的具體含義可參考。所有驗證節點i都有一個初始值bi，協議開始時，每個驗證節點都會向其他驗證節點發送各自的初始值，

動態 | 區塊鏈深度融入雄安新區建設發展 區塊鏈在雄安新區已有四大應用:中國雄安官網今日發布文章《動圖解丨看！區塊鏈在雄安“初顯身手”》，目前區塊鏈技術在雄安新趨已有四大應用，分別是：

1、工程項目資金管理，實現工程進度及合同透明管理、資金撥付穿透式管理、多銀行系統直聯等功能；

2、勞務工資實現穿透式發放，實現了建設者工資透明撥付，如果項目參與方未按約定按時發放建設者工資，區塊鏈智能合約會自動觸發代付機制，保障金會自動穿透式撥付至建設者工資卡中，實現建設者無感狀態下的智能支付保障。截至今年10月，區塊鏈資金管理平臺累計已為11萬人次建設者按時發放工資；

3、白洋淀水體污染治理，白洋淀水專項區塊鏈科研資金管理平臺實現項目可研經費的全流程穿透式管理；

4、政務服務創新實踐，各政府部門建立數據調用互信共認機制；區塊鏈非對稱式加密技術、公私鑰機制，確保公眾及政府部門數據資產安全。[2019/11/17]

協議第一步是歸0過程：

如果某驗證節點i收到0的總數超過總驗證節點數的?，輸出共識結果為0，共識結束，不再執行后面所有步驟

如果某驗證節點i收到1的總數超過總驗證節點數的?，則該驗證節點把自己的bi設為1

如果收到的0或1都沒超過?，則驗證節點把自己的bi設為0

第一步結束節點再次向其他節點發送各自的bi

第二步為歸1過程：

如果某驗證節點i收到1的總數超過總驗證節點數的?，輸出共識結果為1，共識結束，不再執行后面所有步驟

如果某驗證節點i收到0的總數超過總驗證節點數的?，則該驗證節點把自己的bi設為0

如果收到的0或1都沒超過?，則驗證節點把自己的bi設為1

第二步結束節點再次向其他節點發送各自的bi

第三步為重新設定初始值的過程：

如果某驗證節點i收到0的總數超過總驗證節點數的?，設定bi=0

如果某驗證節點i收到1的總數超過總驗證節點數的?，設定bi=1

如果收到的0或1都沒超過?，則每個驗證節點會對某個和本輪本階段相關的信息進行簽名，并對簽名求哈希。bi被設置為這些哈希值中最小哈希的最低有效位

之后返回第一步，直到達成共識

在Algorand中，BBA*的結果是對是否接受某個區塊達成共識，共識結果只有接受或拒絕兩種情況。

2.4.2分級共識協議GC

上述BBA*只適用于二元情況，當需要對任意值達成共識，需要引入分級共識協議，將任意值問題轉化為二元問題：

Algorand采用的GC分為兩步，協議開始時，每個驗證節點i各自都有一個初始值vi：

中國信通院與SAP簽署合作備忘錄：共同推動區塊鏈技術與實體經濟深度融合:中國信息通信研究院與SAP在北京簽署合作備忘錄。中國信通院副院長王志勤與SAP全球高級副總裁、中國研究院院長李瑞成代表雙方在協議上簽字。雙方將集中優勢資源，依托可信區塊鏈計劃，在區塊鏈技術與標準研究、企業區塊鏈應用、行業推廣方面展開深入合作，共同推動區塊鏈技術與實體經濟深度融合。[2018/4/10]

第一步，所有驗證節點將各自的vi發給其他所有驗證節點；

第二步，對于某個x值，當且僅當節點收到其他驗證節點發來該x值的總次數超過總驗證節點數的?時，這個節點會對其它節點發送值x：

經過GC，每個節點都會輸出一個值對(vi,gi)，輸出規則：

當收到x的總次數超過總驗證節點數的?時，設定vi=x，gi=2；

當收到x的總次數超過總驗證節點數的?時，設定vi=x，gi=1；

否則，設定vi=空，gi=0；

簡單來說，分級共識的作用是從多個可能的候選新區塊中選擇被大多數認可的一個作為最終候選的區塊，再通過上面的BBA*最終達成共識。

2.4.3BA*=GCBBA*

改進的拜占庭協議BA*結合了上述GC和BBA*，先通過GC把任意值問題轉化為二元問題，再利用BBA*達成快速二元拜占庭共識，從而可以快速對任意值達成共識，其共識過程如下：

BA*的第一步，和第二步，所有驗證節點i執行2.4.2中分級共識GC，各自得到一個關于新區塊的數值對(vi,gi)，其中vi為驗證節點i認為的候選區塊哈希，gi=0或1或2。

第三步，所有驗證節點根據各自的(vi,gi)設定BBA*的初始值，如果gi=2，則設定初始值為0，如果gi=0或1，則設定初始值為1。之后進行2.4.1中的BBA*共識過程：

若共識結果為0，則最終輸出結果為vi

若共識結果為1，則最終輸出結果為空

無論哪種情況，BA*都可以在驗證節點中達成共識，從而確定新區塊及其包含的交易。

2.5Algorand區塊鏈分叉的可能性

Algorand實際采用的是經典拜占庭共識的升級版BA*，它和以比特幣為代表的中本聰共識的最大區別在于分叉的可能性。后者由于完全去中心化，節點之間無法完全通信，因此可能僅在部分節點間達成共識，容易發生分叉。

Algorand可以通過設定最大可接受的錯誤概率F調整分叉的概率。在Algorand提供的兩種實現中，其分叉概率分別為10^-12和10^-18，在現實中分叉僅存在理論上的可能。為給讀者一個直觀概念，假設Algorand每秒生成一個區塊，10^-18的概率意味著從宇宙大爆炸至今的時間內，只有可能發生一次分叉，可見其概率極低。

即使真的發生分叉，Algorand仍可以從分叉中恢復：

Algorand遵守中本聰共識中的最長鏈法則

如果有多條最長鏈，則選擇包含非空區塊的最長鏈

如果仍相同，則可以具體根據區塊哈希值進行排序選擇

2.6Algorand如何保證安全性

上述的共識算法在理想情況下可以實現去中心化環境下較快速的拜占庭共識，數字簽名和VRF本身的安全性也對系統安全提供了基本的保障。除此之外，Algorand還引入了以下機制，進一步提升安全性：

種子Q(r)

Algorand中的隨機性主要靠VRF保證，每輪隨機的選出leader及驗證組。一個比較直接的想法是把上一區塊B(r-1)作為隨機函數的輸入。但這種方法將給惡意節點帶來一定的優勢：因為區塊和其包含的交易高度相關，惡意節點可以通過調整區塊中包含的交易集，獲得多個輸出，并選擇對其最有利的交易集產生新區塊，從而提高自己在下一輪中成為leader或驗證組的概率。

為解決這一問題，Algorand引入了一個隨機的、不斷更新的種子參數Q(r)，Q(r)與交易集本身相互獨立，因此惡意節點無法通過調整交易集而獲利。

當區塊非空時，Q(r)=H(SIG(Q(r-1),r)

當區塊為空時，Q(r)=H(Q(r-1),r)

可以看出，Q(r)在每一輪都發生變化，且與交易本身無關。可以證明，當Q(r-1)是隨機的，則Q(r)也是隨機的。因此惡意節點無法通過改變交易集影響下一個種子的生成。其中，Q(1)的定義沒有在相關文獻中找到。

回溯系數k

種子參數降低了惡意節點預測leader的可能性，但擁有多個潛在leader的惡意節點仍可以有比普通節點更高的概率成為下一個區塊的leader，但這個概率會隨著區塊的變多而逐漸變小。因此，Algorand引入了一個回溯系數k，第r輪的候選組只從r-k輪已存在的候選組中選取，惡意節點在r-k輪能夠影響第r輪候選組的概率極低。

一次性公鑰

上一節中提到，Algorand從協議層面的分叉僅在理論上可能發生。在實際中，如果惡意節點可以挾持其他節點，仍可以在驗證組被公開的瞬間，強制這些節點重新簽名新的區塊，從而產生短暫的分叉。Algorand引入了一種一次性公鑰的機制，以杜絕這種可能性。

具體原理是所有節點在加入Algorand網絡時，都生成足夠多的一次性公鑰，并公布。這些公鑰將用作后續所有輪次的簽名驗證，并且每個公鑰只使用一次，一旦被使用后就銷毀。一次性公鑰的生成過程需要一定的時間，在Algorand的典型實現中，每個新節點需要約1小時來生成未來10^6輪的所有公鑰。雖然這增加了節點加入時的門檻，但可以從根本上杜絕上述分叉攻擊：因為一旦簽名完成，公鑰即被銷毀，即使被惡意節點劫持，也無法再次簽名產生分叉。

2.7Algorand的可擴展性

對于目前大多數去中心化區塊鏈，如比特幣，以太坊以及Qtum等，可擴展性的主要瓶頸在于所有鏈上計算都要進行全網驗證，而達成全網共識往往需要一定的時間。Algorand采用PoSVRF機制進行隨機選擇區塊生產者和驗證者，無論網絡中有多少節點，每一輪都只需要在少數節點上進行驗證，大大提高了共識速度，提高可擴展性。同時，Algorand還采用了改進的拜占庭共識BA*，該協議可以減少共識節點之間的通信量，從而進一步提高共識速度。

此前Algorand發布了其性能測試數據，結果表明，在1000臺EC2服務器、500,000用戶場景下，Algorand網絡確認時間穩定為1分鐘，吞吐量約為比特幣網絡的125倍。且吞吐量不會隨著節點數的變多而明顯下降。

Algorand的優缺點

通過上述分析，Algorand基本解決了第2節開頭提出的一系列問題：

通過PoS和可驗證隨機函數實現區塊生產者和驗證者的選擇

通過改進的拜占庭共識BA*對新產生的區塊達成共識

通過一定的參數設計，從數學上將分叉的概率降至極低值

引入種子參數，回溯系數以及一次性公鑰等機制進一步增強安全性

每一輪都只進行局部驗證，并通過減少節點間通信量進一步提升系統的吞吐量，提高可擴展性

Algorand在可擴展性，安全性和去中心化程度三個方面達到了一個很好的均衡，但這不意味著其真的打破了所謂的”不可能三角“。

可擴展性方面：本質上還是通過較少的驗證節點對所有交易進行驗證，當網絡中全節點變多時，只能保證性能不下降太多，不是真正意義上的可擴展。另外，每一輪驗證節點之間的通信依賴于所處的網絡狀態，網絡不穩定將導致共識時間變長，影響TPS。官方稱Algorand在Permissinoed環境下將有更好的性能，原因可能在于Permissionless環境下節點所處環境有太多不確定性，會在一定程度上影響可擴展性。

安全性方面：Algorand本質上采用的還是拜占庭共識，惡意節點不能超過?，而比特幣可以在惡意節點數小于?的情況下保證安全。

去中心化方面：Algorand采用PoS共識和VRF決定區塊生產者和驗證者，擁有較多代幣的節點在PoS過程中被選中的概率較高，且Staking獎勵向大戶集中，有一定的中心化趨勢；而VRF選舉機制的引入讓鏈上計算只由部分節點進行驗證，損失了去中心化系統全網驗證的特性。

此外，Algorand的主網剛剛發布，此前所有結果均是理想環境下的數據，且部分代碼未開源，虛擬機相關設計也暫未提及，其實現的復雜度、穩定性和實際性能還有待時間的檢驗。

總結

Algorand通過創新共識協議設計，同時實現了較高的可擴展性，較好的安全性和一定程度的去中心化，并且所有結論都有較為嚴格的數學證明，是一種較為創新和嚴謹的共識機制，目前較適用于有一定準入門檻的去中心化、高吞吐量加密數字貨幣項目。

參考文獻

https://algorandcom.cdn.prismic.io/algorandcom/a26acb80-b80c-46ff-a1ab-a8121f74f3a3_p51-gilad.pdf

https://www.algorand.com/what-we-do/technology/core-blockchain-innovation

S.Micali,M.RabinandS.Vadhan.VerifiableRandomFunctions.40thFoundationsofComputerScience(FOCS),NewYork,Oct1999.

https://algorandcom.cdn.prismic.io/algorandcom/ece77f38-75b3-44de-bc7f-805f0e53a8d9_theoretical.pdf

https://algorandcom.cdn.prismic.io/algorandcom/218ddd09-8d6f-42f7-9db9-5cfbc0aedbe5_algorand_agreement.pdf

https://www.algorand.com/resources/blog/the-borderless-economy-is-here

https://www.odaily.com/post/5134308

https://www.algorand.com/what-we-do/technology/scalability/

https://www.algorand.com/what-we-do/technology/security/

https://www.algorand.com/what-we-do/technology/permissionless-blockchain/

Tags：ANDRANORAALGLIONISLANDEvident Proof Transaction TokenPhilosoraptorAlgoPainter

BNB