[PaperNotes]2017.Algorand: Scaling byzantine agreements for cryptocurrencies

本文首發于Feng Yu的空間

Algorand: Scaling byzantine agreements for cryptocurrencies

文章連結：https://doi.org/10.1145/3132747.3132757

作者：Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, Nickolai Zeldovich

發表：SOSP '17: Proceedings of the 26th Symposium on Operating Systems Principles

截止目前（2021.03.08）被引次數：738

Zotero連結: 從我的文庫打開

标簽1	标簽2	标簽3	标簽4
PoS	VRFs	Consensus

[toc]

CS1951L-Algorand

Lack of finality（終結性） is a major issue with PoW!

PoW的主要問題是缺乏終結性。尤其是在跨鍊（cross-chain）或者鍊下（off-chain）應用中。

Byzantine Fault-Tolerance 問題

• 無法擴充到大量選民（voters）的情景中
• 擴充Scalability：Elect a Committee （隻需要委員會選擇committee selection不是腐敗的） ==>>通過委員會方法進行擴充并不是一個新方法
• 對于女巫攻擊而言是脆弱的（vulnerable）
  • Anti-Sybil：PoS（Proof-of-Stake）

Algorand

Customized BFT protocol，Randomly select committee，Weighted by stake，Reselect on each round

• With high probability, all agree on sequence of transactions 極有可能所有人都同意交易順序
• Safety: if one honest use accepts A, all eventually do 安全性：如果一個誠實的使用接受A，則所有最終都接受
• Liveness: under network assumptions 活動性：在網絡假設下

Algorand Adversary

• 我可以參加并持有金錢， 但是我承受不起 h <1/3
• 我可以破壞目标使用者， 但是我不能破壞 > 2/3的使用者

富有的投票更多

• 有k枚硬币的使用者，每一枚硬币被分為k個子使用者， 被獨立選擇， 沒有人必須知道……， 多少次Alice被選擇

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-wuPZAMSK-1615380557346)(C:%5CUsers%5Cfzhiy%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20210308200717284.png)]

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-W4aq4dMM-1615380557350)(https://img.fzhiy.net/img/20210309184035.png)]

Conclusions

• 委員會的途徑達成共識
• Proof-of-Stake
• Sortition
• VRFs
• Choosing seeds
• Choosing secret keys

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-DH0YmKkK-1615380557352)(https://img.fzhiy.net/img/20210309184120.png)]

0.Abstract

Algorand：一種新的加密貨币，在擴充到許多使用者時可以确認時延為一分鐘（幾乎不分叉）的交易。 即使有一些惡意使用者并且網絡被臨時分區也能確定使用者不會對已确認的交易有不同的view。

使用一種新的Byzantine Agreement（BA）protocol； 使用基于VRFs的新機制來将共識擴充到許多使用者

在Algorand的BA協定中，除了使用者的私鑰外，使用者不儲存他們的任何私有狀态，這使得使用者發送完消息後立即更換參與者==>>緩解了參與者身份暴露後的針對性攻擊

1.Introduction

目前的協定遭遇到交易中時延和信任的權衡。 Bitcoin達成交易實作高度信任需要花費 1小時，另外要求低延遲時間的應用不能肯定交易得到确認并且必須相信payer不會雙花。 雙花攻擊=>使用區塊鍊記賬， 但是達成共識困難（任何人能夠參與，敵手可以創造任意數量的假币【女巫攻擊】使得需要一小部分誠實使用者的傳統共識協定不可行了） ==>> Bitcoin及其他加密貨币使用 PoW， 但是PoW允許分叉攻擊的可能性 。

減緩分叉需要兩個犧牲：

• 将鍊增長一個區塊的時間必須相當高(例如，比特币10分鐘)，
• 應用程式必須等待幾個塊，以確定它們的事務保持在權威鍊上(比特币[7]推薦6個區塊)

==>>其結果是，用比特币确認一筆交易大約需要一個小時。

Byzantine agreement（BA，應用于大規模使用者中，低延遲時間且沒有分叉的可能性）協定是Algorand的核心。BA的關鍵性技術是VRFs（以私密和非互動的方式随機選擇使用者）。 【38，16】是本文的前期技術報告

Three Challenges(Algorand)

• 女巫攻擊
• BA必須擴充到數百萬使用者，遠高于目前最先進的拜占庭協定的操作規模
• 必須能抵抗拒絕服務攻擊（denial-of-service attacks），并且即使在敵手斷開一些使用者的連接配接也要繼續操作【30，52】

Techniques

• Weighted users
  • 為抵抗女巫攻擊，Algorand給每個使用者一個權重。BA旨在保證使用者的一緻意見，隻要有權重的部分(大于2/3的常數)使用者是誠實的。在Algorand，我們根據使用者賬戶裡的錢來衡量使用者。 ==>>隻要誠實使用者擁有超過2/3，則Algorand能夠避免分叉和雙花攻擊。
• Consensus by committee
  • BA通過選擇一個委員會執行協定的每一步（從所有使用者中随機選擇的一小部分代表）實作擴充性。BA基于使用者的權重在使用者中随機選擇委員會成員==>> 允許Algorand確定委員會成員中有相當一部分是誠實的。 但是，對委員會的依賴增加了對標明的委員會成員進行有針對性攻擊的可能性
• Cryptographic sortition（加密抽簽）
  • 為了解決利用委員會達成共識産生的針對性攻擊問題，BA以一種私人的、非互動式的方式選拔委員會成員。 系統中的使用者通過計算自身私鑰的VRF以及來自區塊鍊的公共資訊來 獨立決定他們是否能夠被選擇為委員。 若函數顯示使用者被選擇了，會傳回一個向其他使用者證明委員會成員身份的短字元串（包含在他的網絡資訊中）。由于委員選擇是非互動式的，是以直到該使用者開始參與BA，對手都不知道目标使用者。
• Participant replacement
  • 一旦某個委員會成員在BA中發送了一條資訊，敵手就可能盯上該委員會成員。==>> BA要求委員成員隻發送（發言）一次來減緩這種攻擊。 是以，一旦委員會成員發送了他的資訊(向對手暴露他的身份)，對于BA委員會成員就變得無關緊要了。
  • BA通過避免任何私有狀态**(使用者的私鑰除外)來實作此屬性，這使得所有使用者都能夠平等地參與**，并且通過為Byzantine agreement協定的每一步選舉新的委員會成員來實作。

2.Related Work

• Proof-of-Work
• Proof-of-Stake
  • Algorand使用貨币價值作為權重， 許多權益證明的加密貨币 兩者之間有重要的不同：Algorand中隻要攻擊者控制的貨币價值少于1/3，就能夠保證分叉的可能性是可忽略的（不存在的）；在其他許多權益證明加密貨币中，惡意leader創造新塊導緻網絡分叉，leader将會失去他的錢
  • PoS避免了PoW的計算開銷 ==>> 允許減少交易确認時間。 PoS在實踐中實作【Outdoors【31】第一個實作】是具有挑戰的。一些權益證明加密貨币要求主密鑰來周期性對正确賬本簽名來避免 信任危機；而Algorand在即使leader證明是惡意的情況下也能避免分叉解決這個問題
• Trees and DAGs instead of chains

3.Goals AND Assumptions

• Safety: if one honest use accepts A, all eventually do 安全性：如果一個誠實的使用者使用接受A，則所有最終都接受
• Liveness: under network assumptions 活動性：在網絡假設下
• Assumption
  • Algorand Adversary：我可以參加并持有金錢， 但是我承受不起 h <1/3我可以破壞目标使用者， 但是我不能破壞 > 2/3的使用者
  • Strong synchrony：Algorand用于實作Liveness，在一個已知的有限時間内大部分誠實使用者（eg.95%）能發送消息被大部分其他誠實使用者（eg.95%）接收；敵手最多隻能能夠控制網絡的小部分誠實使用者
  • Weak synchrony：Algorand用于實作Safety。在每個時長b的周期中，必須要有一個時長為s<b的strong synchrony時間

    in every period of length b (think of b as a day or aweek), there must be a strongly synchronous period of length s < b (an s of a few hours suffices).

4.Overview

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-eyYoLdjH-1615380557354)(https://img.fzhiy.net/img/20210309105856.png)]

Algorand要求每個使用者擁有一個公鑰，類似Bitcoin在區塊鍊中添加區塊。使用者使用gossip protocol通信來送出新交易。Algorand使用BA就未确定（排隊中）的區塊達成共識。BA**按步驟（step）**執行，在相同的gossip protocol上通信，并産生一個新的一緻同意的塊。

BA能達成兩類共識：

• final consensus；達成最終共識說明在一個區塊上達成共識，進一步地交易得到确認
• tentative consensus。達成暫時性共識說明可能在不同的區塊（隻要沒有達成final consensus）上達成了共識
  • 兩類情況
  • 1）若網絡是強同步的，敵手 隻有小機率可能性 使BA在一個區塊上達成tentative consensus。BA既不能在不同區塊上達成共識，也不能簡單确認網絡是強同步的。Algorand最終（in a few rounds）以壓倒性（絕對）機率在後續區塊上達成共識，是以确認這些更早一些的交易。
  • 2）若網絡是弱同步的（例如，它完全由對手控制，并有一個上限，即對手可以控制多久）。此時BA能在不同區塊上達成tentative consensus，形成多個分叉。這反過來又會阻止BA再次達成共識，因為使用者被分成不同的組，而這些組對之前的塊有disagree。 為了恢複liveness，Algorand周期性的invoke BA決定哪個分叉進一步增長。 一旦網絡重新回到強同步，這将允許Algorand選擇其中一個分叉，然後在該分叉的後續區塊上達成final consensus。

當且僅當後續塊達成最終共識時，使用者才會确認一個暫時塊的交易。

Algorand的Gossip Protocol 實作類似Bitcoin

Block proposal（section 6）

Agreement using BA（section 7）

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-h9JImRRn-1615380557357)(https://img.fzhiy.net/img/20210309110934.png)]

每個使用者都用他們收到的最高優先級區塊初始化BA。

上圖中，每一步從sortition開始，所有使用者檢查他們自己是否被選為委員會成員。是委員會成員就廣播一條包含他們的選擇證明的消息（上圖中部區域的藍紅綠三個箭頭）。在經過BA的多次這樣重複執行的步驟後，委員會的足夠使用者達成共識。

(Steps are not synchronized across users; each user checks for selection as soon as he observes the previous step had ended.) 使用者之間步驟不是同步的

委員會成員會在每一步結束後可以替換，每個使用者隻要觀察到每一步結束後則檢查選擇。

正如前面所讨論的，BA的一個重要特征是委員會成員除了私有密鑰之外不儲存私有狀态，是以（委員會成員）可以在每一步之後被替換，以減少針對他們的有針對性的攻擊

Efficiency

當網絡是強同步的，BA保證所有誠實的使用者從相同的初始區塊開始（例如，the highest priority block proposer was hon

est）

5.Cryptographic Sortition

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-10n8fMZj-1615380557358)(https://img.fzhiy.net/img/20210309113029.png)]

使用VRFs實作Sortition。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-8BUhRDsl-1615380557359)(https://img.fzhiy.net/img/image-20210308200638367.png)]

Selection procedure

Sortition Interface（源自CS1951L）

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-LGIAjHcd-1615380557360)(https://img.fzhiy.net/img/image-20210308201100807.png)]

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-HLrjx1Ky-1615380557361)(https://img.fzhiy.net/img/image-20210308201145681.png)]

Sortition Algorithm

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-pucuR1uF-1615380557363)(https://img.fzhiy.net/img/image-20210308201318761.png)]

其中W表示 Algorand中貨币單元總數，t表示使用者預計被選擇的次數，p是被選擇成為委員的機率。j是被選中的次數。

僞随機數（PRN，pseudo-random number）hash 決定了 被選擇的sub-users數量。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-IV4lqIXf-1615380557364)(https://img.fzhiy.net/img/20210309173647.png)]

PS：上面兩張PPT後面沒被選中應該是 (1-p)^(w-k) 這樣，大概教授筆誤了吧？ 看下圖原論文

w(使用者權重)個子使用者中正好有k個子使用者被選中的機率遵循二項分布，子使用者的選擇遵循二項分布。

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-L0wwuIov-1615380557365)(https://img.fzhiy.net/img/20210309171759.png)]

由于上圖的性質，則将[0,1) 區間劃分稱如下連續的區間（consecutive intervals）[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-FVgTpIi7-1615380557366)(https://img.fzhiy.net/img/20210309172127.png)]

選擇的子使用者的數量是可以使用proof π(來自VRF輸出)公開驗證的。

Two important properties

• Users selected at random based on weights
• Adversary（that does not know sk_i） can’t guess how many times a user was chosen 或者 更準确地說，對手的猜測不可能比基于權重随機猜測更好

Verifying Sortition

Choosing the seed

• PRG requires a seed …
• Chosen at random
• Publicly known
• Algorand: new one every round
• Cannot be controlled by Adversary

每一輪，釋出一個新的seed，Round r determined with VRFs of r-1（在Algorand中基于第r-1輪的seed使用VRFs來決定第r輪的seed）

Each committee member computes …

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-tbsAPiDq-1615380557368)(https://img.fzhiy.net/img/20210309174608.png)]

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-LQlD3s92-1615380557369)(https://img.fzhiy.net/img/20210309174646.png)]

Round Seeds

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-rVmEZsH4-1615380557370)(https://img.fzhiy.net/img/20210309174818.png)]

seed0 由Algorand最初的參與者（在他們的公鑰公開後）使用distributed random number generation[14]随機選擇

Limiting the Adversary

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-Mur42RSy-1615380557371)(https://img.fzhiy.net/img/20210309174901.png)]

Choosing sk_u well in advance of the seed

如果網絡不是強同步的，attacker對鍊有完全的控制，是以可以drop block proposal，并強迫使用者同意空區塊，這樣就可以計算未來的選擇種子 ==>> 為緩和這種攻擊，Algorand依賴于weak synchrony assuption。

強同步時期的時長s内應該允許足夠多的區塊被創造以保證絕對的（壓倒性的）機率至少有一個區塊是誠實的。這可以確定，隻要s足夠大，選擇私鑰sk_u的敵手u就無法預測r回合的種子

this look-back period b 展現了如下權衡：

較大的 b 降低了attacker能夠打破弱同步假設的風險，但是 增加了使用者将他們的貨币轉移給其他人的機會 是以如果系統的安全性破壞，也不會有什麼損失（俗稱 “無利害關系”問題）。 一個可能避免這種權衡的方法是：将使用者目前餘額的最小值和look-back block中的使用者餘額作為使用者的權重。【本文作者指出，但并未在Algorand中使用】

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-6iiLVEDN-1615380557371)(https://img.fzhiy.net/img/20210309181129.png)]

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-T1F0thK7-1615380557372)(https://img.fzhiy.net/img/20210309181207.png)]

上圖WHP表示 with overwhelming probability

6.Block Proposal

• Minimizing unnecessary block transmissions
  • 為了降低通信成本，用sorting hash對block proposal進行優先級排序：對于使用者i的每個被選擇的sub-user 1,…,j，區塊proposal的優先級通過對連接配接子使用者索引的VRF(可驗證的随機)hash輸出進行哈希得到。
• Waiting for block proposals
• Malicious proposers

Evaluation

[外鍊圖檔轉存失敗,源站可能有防盜鍊機制,建議将圖檔儲存下來直接上傳(img-GtrweNIN-1615380557373)(https://img.fzhiy.net/img/image-20210309184209123.png)]

參考文獻

• Gilad Y, Hemo R, Micali S, et al. Algorand: Scaling byzantine agreements for cryptocurrencies[C]//Proceedings of the 26th Symposium on Operating Systems Principles. 2017: 51-68.
• Micali S, Rabin M, Vadhan S. Verifiable random functions[C]//40th annual symposium on foundations of computer science (cat. No. 99CB37039). IEEE, 1999: 120-130.
• CS1951L-Algorand
• Algorand Releases First Open-Source Code: Verifiable Random Function