關鍵概念

VRF: 可驗證隨機函數。簡單來說是：vrf,Proof = VRF(sk,seed)，sk為私鑰，seed為隨機種子；通過Verify(proof,pk,seed)驗證vrf的合法性。
cryptographic sorition: 根據用戶本輪的VRF值，自身的權重以及公開的區塊鏈信息，計算出某用戶本輪被選舉的sub-users個數，并提供相應的證明
committee member: 見證人委員會，即使用cryptographic sortition選舉出的用戶集合。
FINAL共識：全網用戶對某一非空塊達成了共識。FINAL區塊及之前區塊所包含的交易均被確認。
TENTATIVE共識：其他用戶可能對不同的區塊達成了共識。TENTATIVE區塊的交易需要在對之后的FINAL區塊達成共識后得到確認。

基本假設

算法假設

誠實用戶運行bug-free的軟件。
節點可以自由地隨時加入網絡，而且不需要申請。網絡中的每一個節點通過一個公鑰的地址（這個地址同時也是錢包地址）進行表示，對于新加入的節點地址，只有和網絡中其余節點發生轉賬關系之后，才可以參與到網絡中的區塊共識
攻擊者是動態變化的，誠實節點隨時可能變為攻擊者
誠實節點所持Token的總數占比大于2/3，以避免區塊分叉與交易雙花。
強同步(strong synchrony)假設：大多數誠實用戶（例如95%）發送的信息都能在一定的已知的時間范圍內，被大多數誠實的用戶接收。
弱同步(weak synchrony)假設：網絡在一定的長時間內是異步的（例如完全被惡意方控制）。在異步階段之后，網絡一定會有一段合理時長的強同步階段，在這一階段，Algorand可以確保算法安全。在此情況下，算法仍然安全但性能會受較大影響。
強同步時鐘：為了在弱同步情況下執行恢復協議，所有節點需要同步本地時鐘，即本地時鐘應當足夠接近，使得所有節點執行恢復協議的步調基本一致。

網絡假設

網絡消息傳播時間上限：固定時間內完成對固定比例的用戶的網絡傳播。
比如，比特幣：1KB消息，在1秒鐘內完成全網95%的傳播，而1MB消息需要1.5分鐘完成全網95%的傳播。

總體概括

Algorand 采用可驗證隨機函數、POS （賬戶余額權重）以及新的拜占庭協議議定書（Byzantine Agreement Protocol，BA*）整合方式的共識機制來實現提高TPS的同時，沒有犧牲去中心化和隱私性，并且擁有良好的擴展性。

可驗證的隨機函數：

Micali是可驗證的隨機函數（verifiable random functions：VRF）的發明人之一，VRF是一種隨機數產生方式，每一個用戶，都能夠通過計算他們的私鑰和區塊鏈上公共信息的函數（VRF），獨立地判斷他是否當選委員會的成員。這一過程是非互動的，所以可以有效保證信息的隱私性和防止參與者被攻擊的可能性。
由于使用節點私鑰作為Input，VRF的結果無法被預測。其他節點只有通過網絡接收到隨機結果后才能對其合法性進行驗證，即攻擊者在得知選舉結果時，選舉人已經做出行動了。
VRF的輸出值除了隨機值外，還包含一個proof，提供了隨機值驗證的零知識證明，即不必知道某人私鑰即可證明該隨機值是由某人產生的。
Algorand 利用 VRF 來選擇區塊生產者和驗證者，保證所有共識參與者都是隨機地、公平地被選出的。可驗證隨機函數（VRF，Verifiable Random Function）是由 Micali 教授等提出的一種偽隨機函數，和普通的隨機函數一樣，對于不同輸入，其輸出也具有隨機性（嚴格來說是“偽隨機”）。其獨特之處在于調用者可以提供一個證明，表明這個隨機輸出確實由該調用者產生。
VRF 可以有多種實現方式，Micali 等人在其原始論文中提供了一種較復雜的實現方式。Algorand 利用哈希函數和數字簽名的特性，提供了一種較為簡單的 VRF 實現。具體實現方式是調用者 i 將輸入 m 通過數字簽名和哈希函數映射為固定長度的輸出 H[SIGi(m)],即 m -> H[SIGi(m)]。
對于任何輸入 m，不同的調用者 i 生成的數字簽名 SIGi(m) 都是唯一的；而對于不同輸入，哈希函數 H 的輸出具有隨機性，因此上述映射符合 VRF 的”隨機性“要求。同時，由于 i 的數字簽名 SIGi(m) 可通過其公鑰對其身份進行驗證，因此其也符合 VRF ”可驗證“ 的特性，SIGi(m) 就是 VRF 中提到的”證明“。

具體內容詳解

隨機選出每一輪的區塊生產者（Leader）

每一輪共識開始時，每個節點都可以通過以下 VRF 獨立地驗證自己是否是潛在的 leader：
.H[SIG(r, 1, Q(r-1))] <= 1 / SIZE(PK(r-k))
其中，H 是哈希運算；SIG 是簽名運算；r 是目前的輪次；Q(r-1) 為與 r-1 輪的種子；SIZE(PK(r-k)) 是在 r-k 輪所有符合要求的公鑰的數量（k 為回溯系數）；公式開始的 . 表示將哈希結果轉化為小數位，從而保證結果為[0,1)的某個值。
節點通過自己的私鑰計算上面簽名的哈希值是否符合要求，從而知道自己是否屬于候選的 leader，在此過程中無需和其他節點交換信息。由于哈希函數輸出的隨機性，可以認為符合要求的候選節點都是隨機選出的。候選節點隨后可以生成新區塊，并向全網提供簽名證實自己的身份。如果有多個候選 leader，最終上述哈希值最小的 leader 將在后續的共識中成為本輪最終的 leader。Leader 產生的區塊 Br 包含了本輪的所有交易和上述的證明信息，由驗證組成員進行共識驗證。

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

驗證組成員的選擇與上述過程類似，在每一輪和每一階段（step），所有節點都可以獨立驗證自己是否屬于驗證組成員：
.H[SIG(r, s, Q(r-1))] <= n / SIZE(PK(r-k))
其中 s 為本輪所處的不同階段，Algorand 在每一輪的各個階段都有不同的驗證組，從而進一步保證安全性；n 為預期的驗證組成員數量，可以人為設定；其他參數含義與候選 leader 一樣，每一階段的驗證組成員均隨機選出，驗證節點在證實自己身份后，可以開始參與共識驗證過程，揭露自己的簽名即可證明其身份。

引入權益證明（Proof-of-Stake，PoS）機制

上述的隨機選擇過程沒有考慮 Token 持有者的權重，惡意節點可能通過大量生成有效私鑰從而有極大概率成為區塊的生產者和驗證者。Algorand 在其公布的實現建議中引入了名為 Honest Majority of Money （HMM）的條件假設，其基本思想來源于 PoS 共識機制，即在上述隨機選擇過程中引入代幣持有量（Stake）作為權重，持有量多的節點被選中的概率較高，而代幣持有者往往更傾向于保護網絡的安全性。
具體可以表示為如下公式：.H[SIG(r, 1, Q(r-1))] <= (a(i,r) / M) * (1 / SIZE(PK(r-k)))
其中，a(i,r) / M 為節點所持有的幣的數量占代幣總數 M 的權重。其余過程與前面描述一直。

純粹股權證明PurePoS

正如上面所述，一小部分資金的所有者不可能損害整個系統，而且大多數資金的所有者作惡，使自己的資產貶值將是十分愚蠢的。
例如，在PoW或BPoS中，少數用戶就可以阻止其他用戶進行交易。在Algorand，只有大部分資金的所有者才能阻止其他用戶進行交易。但如果他們這樣做，聲譽將受到極大的損害，資金將不再被普遍接受，其購買力將大大降低。對于大多數資金的所有者來說，這并不是一個好的結果。

PPos如何出塊

在Algorand一個新的區塊分為兩個階段：?

在第一階段，隨機選擇一個Token，其所有者就是下一個塊提議者。
在第二階段，從當前系統中的所有通證中選擇1000個Token。
這1000個Token的所有者被選為第2階段委員會的一部分，該委員會批準第一個用戶提出的區塊。
因此，委員會的一些成員可以被選擇兩次或更多次，通常是k次，在這種情況下，該成員將在委員會中擁有k票以批準下一個區塊。

第二階段是十分必要的

在任何社會中，區塊鏈也不例外，總有一小部分壞人被發現;比如1％。也許2％。如果一個人不幸生活在一個非常危險的社會中，那么10％的人可能是壞人，也許甚至20％！但只要大多數成員遵守規定的規則，就會存在一個穩定和諧的社會。
假設Algorand中10％的代幣屬于不誠實的人。然后在階段1中，十分之一選擇提議塊的用戶可能是壞演員。因此，他可以告訴一些用戶該塊是X，而告訴其他用戶該塊是Y等等，從而產生關于區塊的意見分歧。
階段2消除了這個問題。實際上，如果你選擇隨機的1000個代幣，當最多10％的代幣是不誠實的手牌時，大多數所選硬幣屬于不良參與者的概率，即委員會大多數投票是糟糕的演員的概率是如此之低，以至于可以忽略不計。

誰來進行隨機選擇委員會

Algorand采取的方式：委員會成員選擇自己。你可能會想“什么？這是一個糟糕的主意！因為如果我是一個壞人，我會選擇自己成為這個委員會的成員。接下來。那之后......“但不是那么快。
要想屬于委員會，你的一枚代幣必須獨立贏得這個機會，像加密地公平的彩票，你可以在你自己的計算機隱私中獨立運行?-?也就是說，不與任何其他人交談。而且由于彩票是加密公平的，你不能改變被選中的機會。（即使是擁有巨大算力資源的民族國家，也無法增加被選中的概率。）
為了在假設10,000,000,000個通證中選擇1,000個隨機通證，每個代幣以概率1,000 /10,000,000,000被選擇?-?即，概率為1千萬分之一。

我可以獲得多少票

（如果用戶有n個通證，額外的算法技術基本上運行一個整張彩票，而不是n個單獨的彩票！）一旦用戶運行她的抽獎，就會出現兩種情況之一。

要么所有代幣都沒有贏得彩票，在這種情況下，用戶對該區塊表達何種意見都將被忽略。
或者其中一些k> 1的代幣贏得了彩票，在這種情況下，用戶獲得了一張中獎彩票，即一個簡短的證明，即每個人都可以很容易地證明此用戶在委員會中有k票。在后一種情況下，通過網絡傳播：證明用戶有k票的中獎票 ?以及該用戶對該票的意見。

例子

這里具體舉例說明一下：假設網絡里總共有100萬個幣，要從中選1000個做委員. 那么每個幣被選中的概率是千分之一。?我如果有100個幣，等于我參選了100次，每次千分之一。你如果有10000次，就等于參選了10000次。這些次選擇都是獨立的，所以有可能你有多次被選中，我也有多次被選中，只是我的概率比你低。
但是每次都是千分之一的概率，那么你有100個token被選中的概率是千分之一的100次方乘以一個二項式的系數，概率極低。

偽代碼

入參解釋

·sk: 用戶私鑰
·seed: 選舉所用的種子信息
·role: 當前所選舉的身份信息
·τ: 期望選舉的子用戶sub-users數量
·w: 用戶的權重
·W: 全網總權重

介紹

為了防止女巫攻擊，Algorand使用二項分布作為概率分布函數，原因是B(k1+k2;w1+w2,p) = B(k1;w1,p) + B(k2;w2,p)，即從概率上來說，無法通過拆分token來提高被選中子用戶的數量。
某用戶的子用戶數量j數量大于0，即表示該用戶被選為committee member（見證人委員會）

選舉驗證：

選舉證明算法如下，用于判斷某用戶的VRF值是否合法，且在當前輪次與步驟下是否被選舉為committee member。該函數在CommitteeVote中被使用到

如何選取種子

在Algorand中，seed作為區塊的一個字段，第r輪的seed由第r-1輪區塊的seed所決定
計算公式如下:<seed(r),π> = VRF(sk,seed(r?1)||r).
為了限制攻擊者操縱選舉的能力，選舉算法中所用的seed會每隔R輪刷新一次，即seed(r) = seed(r-1-(r mod R))。

選擇早先于seed的私鑰

上述機制對用戶的私鑰sk選擇提出了新的要求：由于seed在固定R輪中不變，這使得惡意用戶可以通過嘗試不同私鑰來控制VRF值。Algorand要求用戶的私鑰是在區塊r-1-(r mod R)之前生成的，論文中提出的方案是使用距離區塊r-1-(r mod R)早b個時間單位的最近區塊所使用的密鑰對。

新的拜占庭協議議定書BA*：

BA* 是一種高度可擴展性極強，遠超目前拜占庭協議書的鏈上共識，在這個過程中，每個節點連續性提出出塊建議，并且直到權重最高的快被選出為止。
由下圖可知，BA* 協議也可以理解為兩步驟：第一步，同步確定擁有最大優先級的區塊，即驗證者對區塊運行分級共識協議，選出驗證者共識最多的候選區塊。第二步，確定該區塊是否擁有穩定共識的能力，即驗證者對上一階段選出的候選區塊，進行二元拜占庭協議驗證，要么接受他，要么接受空的區塊。

BA*共識又被細化為兩個重要的子算法：

Reduction

在Block Proposal階段，不同的誠實節點因為網絡延遲等因素，會收集到不同優先級的區塊，其所觀察到的最高優先級區塊可能不同。因此，它們傳入BA算法的區塊也會不同。因此在做拜占庭共識之前，先執行Reduction*，在全網對哪個區塊的優先級最高這一問題進行投票并達成共識，將N個潛在的區塊收斂為至多1個非空區塊。

具體步驟

檢查自己是否為committee member，若是則對自己提案的區塊投票。
等待λblock + λstep的超時時間，收集網絡用戶的投票。
一旦某區塊的投票數超過了T*τ的閾值，則認為全網大部分誠實節點在該區塊達成共識，再對該區塊投票；若在執行上一步等待λblock + λstep時間的時候超時，則對空塊投票。
等待λstep的超時時間，收集網絡用戶投票，并返回最終得到的區塊。

Q&A

Q：為什么要進行兩次投票？

A：第一次投票（步驟2）用于對大多數節點所看到的最高優先級區塊達成共識，類似于prepare階段；第二次投票（步驟3、4）用于對第一次投票的共識結果進行共識，表示大多數節點已經對某新區塊達成共識，類似于commit階段。

Q：CommitteeVote函數中為何要傳入不同的step？（REDUCTION_ONE與REDUCTION_TWO）

A：每個用戶的vrf值，round和step均為選舉算法的隨機種子，影響著用戶是否能被選舉為committee member。這里對Reduction的兩次投票引入了一定的隨機性，使得兩次投票的用戶不同。若兩次投票用戶均為同一批，惡意方可以在兩次投票之間的時間間隙，對第一次投票的用戶進行攻擊（因為第一次投票后已經暴露了投票人是誰），從而危及算法安全性。

BinaryBA*

BinaryBA* 算法對Reduction過程收斂的區塊進行多次投票，在網絡狀況良好的情況下在第一步即可達成FINAL共識。
1，step=1時，用戶對Reduction得到的區塊hash進行投票，并收集票數。若超時，則保持原區塊hash，進入步驟2；若不超時且投票結果為非空塊，則再對該hash投票3次，并投出FINAL步驟的票（意為當前用戶已達成FINAL共識），返回該區塊hash。
2，繼續對上一步驟中得到的區塊hash投票并收集票數。若超時，則將hash置為空塊hash，并進行步驟3；若得到空塊，則連續投票3次并返回空塊hash。
3，繼續對上一步驟中得到的區塊hash投票并收集票數。若超時，則執行“拋硬幣”算法，有50%的概率將hash置為原先的區塊hash或空塊hash。若否，則將hash置為投票結果。最后重復步驟1。

Q&A

Q: 在每輪算法的前兩步中達成共識，為何在return之前要連續投票3次？

A: 在公網環境下，若有很多誠實節點在某一步達成共識并返回，而其余誠實節點由于網絡延遲，在給定時間內沒有收集到足夠的票數，從而超時進入下一輪。此時在接下來的step中很可能沒有足夠的committee member進行投票，使得這些節點始終無法對區塊達成共識。Algorand對這一問題的解決方案是：在某用戶達成共識并結束算法之前，預先對該區塊hash進行后三步的投票。在還未達成共識的用戶看來，這些已達成共識的節點仍然參與了后三步（后一輪）的投票。

Q: 為何設計CommonCoin拋硬幣算法？

A: 避免在網絡分區的情況下，攻擊者有機會給不同的用戶發送對不同hash的投票（或故意不投），使它們對不同區塊達成共識。同時CommonCoin加速了BBA的收斂過程。根據CommonCoin的算法特性，誠實用戶的比例最壞為2/3，經過CommonCoin得到block_hash和empty_hash概率均為為1/2，因此每經過一次CommonCoin，全網達成共識的概率為(2/3)*(1/2) = 1/3。則全網用戶在第i輪達成共識的概率為((2/3)^(i-1))*(1/3)。達成共識的期望總輪數為i*((2/3)^(n-1)*(1/3))的無窮級數，即極限為3。因此，通過拋硬幣，在最壞情況下，全網達成共識的期望輪數為3，期望步驟數為2+3*3=11

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

Algorand 引入的 BBA* 是一個改進的二元拜占庭協議（所謂二元，即只能達成 0 或 1 兩種共識）。BBA* 可以在誠實節點超過 ? 的情況下，快速達成共識。其具體過程是一個 3 步循環，循環中每一步都有 ? 的概率達成共識。
節點之間需要進行 P2P 通信，假設被選中的驗證節點中有 t 個惡意節點，驗證組總的節點數為 n >= 3t + 1，即惡意節點不超過 ? 。協議過程如下：

所有驗證節點i都有一個初始值 bi（bi = 0 或 1），協議開始時，每個驗證節點都會向其他驗證節點發送各自的初始值，

協議第一步（Step 1）是歸 0 過程：

如果某驗證節點 i 收到 0 的總數超過總驗證節點數的 ? ，輸出共識結果為 0，共識結束，不再執行后面所有步驟
如果某驗證節點 i 收到 1 的總數超過總驗證節點數的 ?，則該驗證節點把自己的 bi 設為 1
如果收到的 0 或 1 都沒超過 ?，則驗證節點把自己的 bi 設為 0
第一步結束節點再次向其他節點發送各自的 bi

第二步（Step 2）為歸 1 過程：

如果某驗證節點 i 收到 1 的總數超過總驗證節點數的 ? ，輸出共識結果為 1，共識結束，不再執行后面所有步驟
如果某驗證節點 i 收到 0 的總數超過總驗證節點數的 ?，則該驗證節點把自己的 bi 設為 0
如果收到的 0 或 1 都沒超過 ?，則驗證節點把自己的 bi 設為 1
第二步結束節點再次向其他節點發送各自的 bi

第三步（Step 3）為重新設定初始值的過程：

如果某驗證節點 i 收到 0 的總數超過總驗證節點數的 ?，設定 bi = 0
如果某驗證節點 i 收到 1 的總數超過總驗證節點數的 ?，設定 bi = 1
如果收到的 0 或 1 都沒超過 ?，則每個驗證節點會對某個和本輪本階段相關的信息進行簽名，并對簽名求哈希。bi 被設置為這些哈希值中最小哈希的最低有效位（仍然是 0 或 1）
之后返回第一步，直到達成共識
在 Algorand 中， BBA* 的結果是對是否接受某個區塊達成共識，共識結果只有接受（0）或拒絕（1）兩種情況。

分級共識協議 GC

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

Algorand 采用的 GC 分為兩步（上圖來自 Algorand 白皮書，為了和文中其他部分對應，將兩個步驟命名為 Step 2 和 3），協議開始時，每個驗證節點i各自都有一個初始值 vi（在 Algorand 中即候選的新區塊的哈希）\
第一步（Step 2），所有驗證節點將各自的 vi 發給其他所有驗證節點；
第二步（Step 3），對于某個x值，當且僅當節點收到其他驗證節點發來該 x 值的總次數（多次收到同一節點發送的x值，只算一次）超過總驗證節點數的 ? 時，這個節點會對其它節點發送值 x：

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

當收到 x 的總次數超過總驗證節點數的 ? 時，設定 vi = x， gi = 2；
當收到 x 的總次數超過總驗證節點數的 ? 時，設定 vi = x， gi = 1；
否則，設定 vi = 空， gi = 0；
簡單來說，分級共識的作用是從多個可能的候選新區塊中選擇被大多數認可的一個作為最終候選的區塊，再通過上面的 BBA* 最終達成共識。

BA* = GC + BBA*

改進的拜占庭協議 BA*? 結合了上述 GC 和 BBA*，先通過 GC 把任意值問題（從多個區塊中選擇一個候選）轉化為二元問題（接收或拒絕新區塊？），再利用 BBA* 達成快速二元拜占庭共識，從而可以快速對任意值達成共識，其共識過程如下：

?BA* 的第一步，和第二步，所有驗證節點 i 執行分級共識 GC，各自得到一個關于新區塊的數值對 (vi, gi)，其中 vi 為驗證節點 i 認為的候選區塊哈希（有可能為空），gi = 0 或 1 或 2 。
第三步，所有驗證節點根據各自的 (vi, gi) 設定 BBA* 的初始值，如果 gi = 2，則設定初始值為 0，如果 gi = 0 或 1，則設定初始值為 1 。之后進行BBA* 共識過程：
若共識結果為 0，則最終輸出結果為 vi（非空新區塊）
若共識結果為 1，則最終輸出結果為空（即新區塊為空）
無論哪種情況，BA* 都可以在驗證節點中達成共識，從而確定新區塊及其包含的交易（有可能為空區塊）。

?Algorand 區塊鏈分叉的可能性

Algorand 實際采用的是經典拜占庭共識的升級版 BA*，它和以比特幣為代表的中本聰共識的最大區別在于分叉的可能性。后者由于完全去中心化，節點之間無法完全通信，因此可能僅在部分節點間達成共識，容易發生分叉。
Algorand 可以通過設定最大可接受的錯誤概率 F 調整分叉的概率。在 Algorand 提供的兩種實現中，其分叉概率分別為 10^-12 和 10^-18，在現實中分叉僅存在理論上的可能，但是這個概率賊低，假設 Algorand 每秒生成一個區塊，10^-18 的概率意味著從宇宙大爆炸至今的時間內，只有可能發生一次分叉，可見其概率極低。
即使真的發生分叉，Algorand 仍可以從分叉中恢復：

Algorand 遵守中本聰共識中的最長鏈法則
如果有多條最長鏈，則選擇包含非空區塊的最長鏈
如果仍相同，則可以具體根據區塊哈希值進行排序選擇

Algorand 如何保證安全性

種子Q(r)

Algorand 中的隨機性主要靠 VRF 保證，每輪隨機的選出 leader 及驗證組。一個比較直接的想法是把上一區塊 B(r-1) 作為隨機函數的輸入。但這種方法將給惡意節點帶來一定的優勢：因為區塊和其包含的交易高度相關，惡意節點可以通過調整區塊中包含的交易集，獲得多個輸出，并選擇對其最有利的交易集產生新區塊，從而提高自己在下一輪中成為 leader 或驗證組的概率。
為解決這一問題，Algorand 引入了一個隨機的、不斷更新的種子參數 Q(r)，Q(r) 與交易集本身相互獨立，因此惡意節點無法通過調整交易集而獲利。當區塊非空時，Q(r) = H(SIG(Q(r-1),r) （其中，SIG 為本輪 leader 的簽名）; 當區塊為空時，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 輪的所有公鑰（約 180 MB 數據）。雖然這增加了節點加入時的門檻，但可以從根本上杜絕上述分叉攻擊：因為一旦簽名完成，公鑰即被銷毀，即使被惡意節點劫持，也無法再次簽名產生分叉。

Algorand 的可擴展性

對于目前大多數去中心化區塊鏈，如比特幣，以太坊以及 Qtum 等，可擴展性的主要瓶頸在于所有鏈上計算都要進行全網驗證，而達成全網共識往往需要一定的時間。Algorand 采用 PoS+VRF 機制進行隨機選擇區塊生產者和驗證者，無論網絡中有多少節點，每一輪都只需要在少數節點上進行驗證，大大提高了共識速度，提高可擴展性。同時，Algorand 還采用了改進的拜占庭共識 BA*，該協議可以減少共識節點之間的通信量，從而進一步提高共識速度。
此前 Algorand 發布了其性能測試數據，結果表明，在 1000 臺 EC2 服務器（AWS 虛擬云服務器）、500,000 用戶場景下，Algorand 網絡確認時間穩定為 1 分鐘，吞吐量約為比特幣網絡的 125 倍。（比特幣約為 7 TPS）且吞吐量不會隨著節點數的變多而明顯下降。

賬戶余額權重：

Algorand算法中的節點都有權重（weight），該權重和賬戶的余額成正比。

上圖中的t是選中的賬戶余額閥值，w=賬戶余額/賬戶余額閥值，也就是說w是賬戶中可以分割成多少個賬戶余額閥值。利用多項式分布B(k;w,p)，計算出hash對應的比例在哪個區間內，則最后選中的次數就是多少，也就是最后的j的數值。

加密抽簽算法：

在百萬級別使用用戶的量級下，如何依然能維持快速有效的的拜占庭共識，其主要手段是避免所有用戶參與驗證，那么減少驗證者同樣可能帶來安全性的不足，如何平衡兩者使得在大量節點中提取可靠維持共識效率的驗證人是關鍵。加密抽簽算法就是用來解決這個隨機選擇問題的，他提供了一種私密隨機并可驗證的驗證人篩選方法。
抽簽其實是一種隨機方式，在整個網絡中，節點之間如何不存在事先商議的情況下自動產生隨機驗證人是需要用心構思的技巧。
Algorand的解決方式中，主要有兩點：1、用戶私鑰參與運算的隨機特征值產生算法函數，該函數產生與上一區塊相關，私鑰的保密性，使得參與隨機運算后的結果存在不可預測性；2、將運算后的特征值映射到（0,1）數值區間內，對比特征值數值最小的作為提塊人，按照特定規則從特征值中選取出驗證群體，并且在此時驗證人的選取是在其不可知的情況下被選擇的，只有當區塊組裝完成后，驗證人會同時將自己生成的驗證憑證（用來證明自己是在秘密抽簽中被合法選中的驗證人）一并廣播出去，在這之后其他用戶可驗證當前驗證人是否合法。
Algorand采用了VRF函數，并結合賬戶的余額比例，隨機確定區塊生成以及投票人角色。根據論文中的模擬數據，比特幣的POW共識換成Algorand共識后，TPS增長125倍。和DPOS+BFT相比，Algorand的安全性更強，只要超過2/3的賬戶余額是誠實節點，Algorand即安全。不過Algorand共識只是進行了小范圍的測試，還沒有經過大規模的市場驗證。

算法細節解析

算法輔助函數

CommonCoin

CommonCoin算法用于模擬1/2概率，俗稱”拋硬幣“，但該”拋硬幣“算法有以下兩個特點：
1. 結果只有2個，且每個結果的概率為50%。
2. 使用相同參數作為種子，獲得的結果相同。
在Algorand中，CommonCoin使用全網的投票信息作為種子，對于強同步的大多數誠實節點來說，得到相同結果的概率為h（h即為誠實節點所占比例，h > 2/3）。故每經過一次CommonCoin可以h的概率讓大多數誠實節點達成共識。

CountVotes

CountVotes算法用于在給定時間內統計票數，并選出超過票數閾值的合法區塊。每個投票消息的票數實際為該用戶在當前上下文中所選舉的子用戶數量。

ProcessMsg

ProcessMsg用于接收投票信息，驗證并統計票數。

?AIgorand的區塊鏈的種類的分類

ALGORAND 非許可區塊鏈

Algorand 提供真正去中心化、可擴展和安全的非許可區塊鏈。它具備真正去中心化的特點：每個代幣都可以參與共識協議，與任何其他代幣具有相同的權力。它具有可伸縮性，因為它只需使用少量的運算，即可支持數十億用戶在幾秒之內生成一個區塊。而且它很安全，因為它不可能被少數礦工或受托人或者一小部分代幣的所有者破壞。事實上，只要?Algorand 區塊鏈的大多數代幣掌握在可靠的人手中，它就能保證正常工作。
Algorand 協議依賴于全新的技術，例如其獨特的密碼抽簽和超高效的拜占庭協議。

除了完全的去中心化、可擴展性和安全性之外，Algorand 非許可區塊鏈還具有以下顯著特性：

無分叉和即時交易確認。Algorand 區塊鏈不會分叉。每個新區塊都是單獨商定的，并且保證永遠留在 Algorand 鏈上。因此，用戶可以立即信賴新區塊中包含的交易，而不必等待區塊在鏈中具有足夠的深度。
在?Layer 1?處理標準資產和智能合約。區塊鏈在不同的層面上處理不同的交易。第 1 層是最直接和最安全的一層。傳統意義上來說，第 1 層只處理普通支付和共識協議本身，新資產的發行、智能合約和其他的所有事務都在第 2 層處理。但眾所周知，第 2 層的協議速度慢、成本高并且容易出錯。相比之下，Algorand 在第 1 層還會處理標準資產和大量智能合約的發行，包括資產代幣化、原子交易和抵押借貸，并且能夠在必要時隔離和收回有爭議的交易。事實上，Algorand 在第 1 層就滿足了智能合約的大多數當前用例，并且具有與普通支付手段相同的安全性和效率。

ALGORAND許可鏈版本

許可型區塊鏈的主要優點是能夠保護交易不受外界干擾。
在 Algorand 的非許可鏈版本中，每個原生代幣（除了作為本地貨幣 (Algo) 的計量單位之外）都可以參與共識協議，并具有與其他代幣相同的權力。但是，在 Algorand 的許可鏈版本中，企業 E 只能將給定的 10M 代幣池用于共識協議，并以任何方式將其劃分到自己選擇的驗證節點集合 V 中。例如，E 可以選擇 V 僅包含 5 個驗證節點，并為每個驗證節點分配 2M 共識代幣。這樣做的結果是，E 為五個驗證節點中的每一個提供了生成新區塊的相同能力。另舉一例，E 可以選擇 55 個驗證節點，為前 5 個驗證節點每個分配 1M 代幣，并為另外 50 個驗證節點每個分配 100K 代幣。這樣的話，E 為前 5 個驗證節點分配的區塊生成能力就是其他 50 個驗證節點的 10 倍。
Algorand 的許可型版本具有極細的顆粒度級別，可以為不同的驗證節點分配不同的權重。

通過Algorand 許可區塊鏈，而不是從頭開始構建自己的許可鏈或采用另一個許可鏈，E 獲得了以下主要優勢：

a) 按需分配的加權去中心化。選擇任意數量（任意權重）的驗證節點是至關重要的。實際上，E 可能想做出這種選擇來提高自己區塊鏈的安全性，或者擴大它所服務的社區。最初為少量金融機構服務的區塊鏈可以從少量的驗證節點開始。但是，如果以后它想要為中小型銀行和信用合作社服務，而所有這些機構都希望參與區塊生成，該怎么辦？適用于少數參與者的共識算法可能無法有效地適用于成百上千的參與者。而中途改變策略可能相當具有挑戰性！通過允許共識協議擴展到數十億個驗證節點，E 能夠保證在任何時候毫無問題地擴大驗證節點集。縮小規模容易，擴大規模就難了。
b)?交易最終性和第?1?層智能合約。無論是私有還是公有區塊鏈，許可型還是非許可型區塊鏈，對于任何區塊鏈來說，交易最終性都是一個至關重要的屬性。在第 1 層處理大多數智能合約需求的能力也是如此。通過在 Algorand 中增加權限控制特性，E 從而獲得一個許可型區塊鏈，該區塊鏈會自動繼承這些至關重要并且很難擁有的屬性。
c)?可升級性和持續創新。無論何時將升級改進和創新添加到核心的無許可型 Algorand 主鏈，使用許可型版本的 Algorand 協議均會自動為 E 提供未來的升級改進和創新。

ALGORAND Co-Chain：定義和挑戰

定義

Algorand Co-Chain是特殊的 Algorand 許可鏈版本。因此，它是一個可擴展的許可鏈框架，可按需實現去中心化，具有交易即時確認和第 1 層智能合約等特性。它還滿足一個額外的關鍵特性：
與其他Co-Chain的互操作性。許可型區塊鏈能讓給定范圍內的用戶安全地進行互動。但它可能不允許他們與其他實體和個人進行互動。這是一個很大的限制，因為“外部”的世界比“內部”的世界更大，我們可能想要與更大的世界互動。一組金融機構可能想建立他們自己的許可鏈。但是一些醫療機構可能也想這樣做。由于醫療保健是經濟的重要組成部分，所以金融機構鏈想必希望與醫療機構鏈進行交互和資產交換。如果沒有外部的互操作性，許可鏈的成員就可能被困在自己的鏈中。

Co-Chain是?Algorand?許可鏈，它能保證?Algorand?無許可鏈與其他Co-Chain之間高效和安全的互操作性。

挑戰

第一個挑戰：安全性

許可鏈之間的互操作性很容易聲明，但很難得到保證。考慮一個簡單的例子。用戶a擁有資產?x，他希望與擁有資產?y的另一用戶?b進行交換。
如果?a和?b屬于 Algorand 無許可鏈或同一個 Algorand Co-Chain，此問題可以在 5 秒內解決，并且具有最終性和安全性。實際上，他們可以使用原子交換，這是 Algorand 中作為第 1 層交易可用的主要工具之一。但是，如果?a是Co-Chain?A?的成員，b是另一個Co-Chain?B?的成員，該怎么辦？
不同鏈間的資產交換通常通過哈希鎖定協議來實現的。但是這種方法存在相當大的問題。除了需要多個邏輯復雜的步驟之外，它還容易受到拒絕服務攻擊。這樣的攻擊可以使欺騙一方保留自己的資產，同時獲得另一方的資產。為了避免這種情況，協議可能需要持續很長一段時間，這可能使拒絕服務的成本高于相關資產的價值。

第二個挑戰：明確所有權

但是，這又會產生另一個問題，并且該問題適用于僅涉及x和y及其各自區塊鏈A和B的任何協議。也就是說，由于A?和B是許可型的私有鏈，最多只有它們的成員知道x和y交換了原始資產，因此，b現在由鏈A的成員擁有。如果鏈B?損壞，沒有什么能夠阻止y多次向其他區塊鏈的成員出售b或用其交換其他資產！從本質上講，這相當于資產交換的雙重支付。
如果許可鏈的大多數驗證節點是惡意的，或者其密鑰已泄露，那么該許可鏈就算是腐敗了。在腐敗的鏈中，原始區塊可以被替換為假區塊，這樣就再也無法弄清楚誰擁有哪些資產。（這就是去中心化對安全來說至關重要，以及幾百個驗證節點比幾十個更好的原因！）許可鏈的損壞具有很強的隱匿性，因為它的私密性可以防止外部人員注意到這種腐敗。鏈的損壞是比較罕見的事件，但當它發生時，應該只影響鏈的成員，而不應該影響誠實鏈！沒人能夠保證另一條鏈可以保持誠實。
鏈的互操作性應該保證誠實鏈的成員所獲得的任何資產都有明確的所有權。即便從腐敗的鏈的成員處獲得的資產也是如此。

ALGORAND（簡化版）Co-Chain體系結構

現在，我們來概述一下 Algorand Co-Chain如何互操作。為簡明起見，先忽略隱私特性。

序言

我們用?MAIN來表示 Algorand 的主網，它是無許可并且公開的。相應地，每個Co-Chain監控?MAIN的區塊。對于每個Co-Chain?C，MAIN都需要維護

Co-Chain的驗證節點的最新列表VALIDATORSC，
以及Co-Chain的成員擁有的，可以轉讓給其他鏈的所有資產的最新列表ASSETSC。

過程

最初，當一個Co-Chain形成時，這兩個列表都可能被包含在本質上是Co-Chain?C在“MAIN中的創世區塊”。（這個創世區塊與Co-Chain?C的原始創世區塊不同，它指示哪些是Co-Chain?C的初始公鑰，以及這些密鑰最初擁有哪些資產。）
隨著時間的推移，VALIDATORSC和?ASSETSC都通過Co-Chain?C在?MAIN中發布由Co-Chain?C的最新驗證節點列表（適當多數）簽署的適當交易進行更新。
需要強調的是，MAIN不僅對Co-Chain?C?中發生的交易一無所知，而且也不知道Co-Chain?C的實際公鑰，更不用說使用這些密鑰的實際用戶了！事實上，ASSETSC不會透露有關Co-Chain?C中控制?ASSETS中資產的公鑰的任何信息。

從?Algorand Co-Chain?到主鏈的資產轉移

Algorand Co-Chain?A?的用戶?x可能想要通過公鑰?tx將他擁有的資產?a轉移到?MAIN。用戶?x這樣做可能出于多種原因。例如，x可能想拍賣?a，而“出價的人越多，價格就越高”。因此，與其在?A上拍賣?a，用戶?x可能更愿意在?MAIN上拍賣，這樣不僅有?A的成員報價，還有?MAIN或其他Co-Chain的成員報價。事實上，Co-Chain的任何成員都可以輕松地向?MAIN轉移穩定幣，唯一的目的就是參加拍賣。
與Co-Chain?A?中普通的轉移相同，將?a從?tx轉移到?MAIN的操作由 tx?的數字簽名授權，用符號表示為?SIGx(tx, a, MAIN)。由于?tx擁有?a?，并且轉移得到了適當的授權，SIGx(tx, a, MAIN)會進入經?A的驗證節點適當認證的?A的一個新區塊?X。此時，Co-Chain?A?的所有成員意識到?tx和?A中的任何其他公鑰均不擁有資產?a。因此（除非?A已損壞），tx不能再授權?a在?A內或?A外的轉移。
與?A的所有其他區塊相同，X的結構是為了便于將?SIGx?(tx,a, MAIN)和轉到?MAIN的所有其他資產轉移與所有其他信息隔離開來，這些信息必須僅對?A的成員保持可見。從概念上來說，表示方式如下：

X= (SIGx?(tx, a, MAIN), other transfers to MAIN, H)

其中H是A中所有交易的單向哈希（通常長度為 256 位），必須在A中保持私密。需要注意的是，X的格式非常緊湊。實際上，除了打算傳遞給 Algorand 主鏈的信息外，它只包含 256 個字節。
此格式的區塊X以及它在A中的證書會傳播到MAIN的節點。

由于Co-Chain?A運行與MAIN相同的共識算法，并且MAIN知道 A 的驗證節點，因此MAIN的驗證節點可以解析X的證書，并了解到

tx是A擁有資產a的密鑰
密鑰tx的所有者希望將?a轉移到 Algorand 的主鏈。

相應地，

資產a會從?ASSETSA中移除，并且
密鑰tx會被記錄為MAIN擁有（在MAIN中！）資產a的（可能為新的）密鑰。

注意：步驟 1 中使用的MAIN既是公有的，也是非許可的。具體來說，MAIN為非許可型這一事實能夠保證tx成為MAIN中的密鑰，不會出現任何問題。并且MAIN是公有的這一事實能夠保證所有人意識到資產a現在位于MAIN中。這能夠保證y將（在下一個步驟中）獲得a的明確所有權。事實上，無論Co-Chain?A?是否損壞，x和A中的任何其他成員均無法將a轉移給任何其他Co-Chain的任何成員。

從主鏈轉回Co-Chain的資產轉移

在?MAIN中出售?a后，tx可能會想將拍賣所得的穩定幣轉移給?A。
更普遍的情況下，如果?tx是?MAIN和?A兩者的公鑰，tx可能會想將它在?MAIN中擁有的資產?b轉移到?A。同樣，這樣的轉移可能是由?tx的數字簽名授權的，用符號表示為?SIGx?(tx,b, A)，它會進入?MAIN的一個新區塊。由于?MAIN為非許可型，A的驗證節點可能會看到?SIGx?(tx,a, A)出現在?MAIN的區塊中，或者它們可以通過?tx本身看到這種出現的適當緊湊證明。無論哪種情況，A的驗證節點都將導致?tx成為?A中資產?b的當前所有者，因為它已經是?A中的一個密鑰。同時，只要?SIGx(tx, a, A)出現在?MAIN的區塊中，tx便不再擁有?MAIN中的?b，并且?ASSETS A將更新為包含資產?b。

Co-Chain互操作性

接下來，我們使用上面提到的相同資產交換示例來說明Co-Chain是如何互操作的。現在，A和?B是不同的 Algorand Co-Chain。具體來說，資產?a在?A中由公鑰?tx控制，其私鑰為?x所知，而資產?b在?B中由公鑰?ty控制，其密鑰為?y所知。

要交換它們的資產，x和y通過以下概念步驟利用MAIN。

在鏈A中，tx“將a轉移到MAIN”，并向MAIN提供轉移證明。在鏈B中，ty“將b轉移到MAIN”，并向MAIN提供轉移證明。
在MAIN中，tx和?ty通過原子互換交換a和b。
在MAIN中，tx將b轉移到A，并且?ty將a轉移到B。鏈A?和B都能看到這兩項轉移

步驟 1 的說明

步驟 1 可以通過tx在MAIN的區塊中發布?SIGx?(tx, a, A)?來實現，如上所述。相應地，在MAIN中，

資產a會從?ASSETA中移除，并且資產b會從?ASSETB中移除。
密鑰tx不再擁有a。

類似地，對于ty來說也是如此。

步驟 2 的說明

從現在開始，在?MAIN中，tx?擁有a，并且ty擁有b，它們可以在幾秒鐘之內以超級安全的方式交換這些資產。實際上，所采取的方式是第 1 層原子交易，這是 Algorand 非許可鏈的主要功能特性之一。

步驟 3 的說明

如前所述，在?MAIN中，tx?將b轉移給 A 中的自己，因為tx仍然是A的批準密鑰。類似地，對于ty來說也是如此。

附加說明

我們可以注意到，整個過程非常快。實際上，以上三個步驟中的每一步都可以在生成新區塊所需的時間內執行。這一時間在 Algorand 的主鏈中不超過 5 秒。但是在 Algorand Co-Chain中生成區塊可能會快很多。實際上，在 Algorand 協議中，可以在確保大多數驗證節點看到區塊所需的時間內生成一個區塊。在網絡速度很快的Co-Chain中，這一時間可以忽略不計。
還注意到，整個過程發生在第 1 層，因此無論是在主鏈中還是在Co-Chain中，都具有更高的安全性。
最后請注意，給定Co-Chain的資產累計價值可能超過 Algorand 主鏈的估值。然而，Algorand 的主鏈并不用于保護任何Co-Chain的資產。在給定的時間點，它僅用于處理給定Co-Chain的少量資產，并且僅持續幾秒鐘。也就是說，它用于處理Co-Chain想與另一個鏈交換的資產。

增強私密性

Algorand Co-Chain之間資產交換的隱私性可以大幅增強。
具體而言，tx和?ty可以是臨時密鑰，僅供?x和?y在本次資產交換中使用。也就是說，在開始上述的三步流程之前，x生成臨時公鑰?tx?并將資產?a從之前持有a的任何公鑰轉移到?tx。完成步驟 3，并且?tx?在?A中擁有資產?b后，x可以將?b從?tx?轉移到他選擇的任何其他公鑰。通過這樣的方式，Algorand 的主鏈永遠不知道?A中的哪個公鑰最初擁有資產?a，以及哪個公鑰最終會擁有?b。

Co-Chain主要有以下幾個特點

完全獨立于公有區塊鏈，保護其交易不被外部人員所看到，可以自行選擇驗證者節點，并自行來運行Algorand共識協議；
通過與Algorand主鏈交互從而和其他Co-Chains以及其他方之間進行交易，并且確保該過程和在Algorand無需許可的公鏈內進行資產交換，擁有相同程度的安全性和便利性；
Co-Chain能夠使用原子交換（Atomic Transfers），智能合約（ASC）等所有Algorand公鏈原生擁有的工具和特性；實際上，Co-Chain能夠自動享受到Algorand公鏈上所有的升級以及性能提升。

Algorand網絡節點分為兩種

Relay Node（中繼節點）和 Non-Relay Node（非中繼節點）。其中中繼節點承擔 Algorand 網絡樞紐的作用，執行重復數據刪除，簽名檢查和其他驗證步驟，最終向其他節點重新傳播有效消息。非中繼節點則又稱為參選節點，通過配置有效賬戶并連接到中繼節點參與網絡選舉。作為一個開放性的網絡，任何人都可以下載安裝跑一個Algorand節點。參選節點可以設置為全節點模式和非全節點模式。在非全節點模式下，節點只需要保留大約1天的區塊數據，能有效降低存儲要求。Algorand 所固有的高速、可擴展性和安全性等特點將被其上發行的 USDT 所繼承。