RAC:Algorand 系列一：VRF 密碼學抽簽原理及其在 Algorand 中的應用_ALGO

YOUChainResearch

YOUChain研究團隊，成員畢業于國內外頂級名校，有長期的工業界經驗。我們持續跟蹤的區塊鏈學界和業界的前沿發展，致力于深入區塊鏈本質，推動學術和技術發展。團隊誠邀加密、算法、區塊鏈、工程人才加入！

本文來自

1VRF介紹

隨著Algorand項目的發起，原來越多的人對其所應用到的密碼學抽簽技術產生了興趣并探索相關的應用。目前，隨著Algorand項目的主網上線，該技術也開始了接受大規模的正式實踐檢驗，我們拭目以待。

目前雖然國內已經有大量文章對VRF技術進行了一些介紹，但是目前看都不夠全面深入。因此我們「YOUChainResarch」打算重新梳理，希望能盡可能全面地介紹該技術，作為我們「Algorand技術解析系列」系列文章的開篇，與大家分享及交流探討。

1.1簡介

VRF全稱為VerifiableRandomFunctions，翻譯為“可驗證隨機函數”，由SilvioMicali，MichaelRabiny，SalilVadhan于1999年提出，是一種基于公私鑰的密碼學哈希函數。。只有擁有VRF私鑰才能計算哈希，但任何擁有對應公鑰的人都可以驗證該哈希的正確性。

VRF的一個關鍵應用就是，提供對存儲在基于散列的數據結構中的數據的隱私保護，防止離線枚舉。在這種應用中，證明人持有VRF私鑰，并使用VRF哈希在輸入數據上構造基于散列的數據結構。由于VRF的性質，只有證明人才能回答關于數據結構中是否存儲了某些數據的查詢。任何知道VRF公鑰的人都可以驗證證明人正確地回答了查詢。但是，不能對數據結構中存儲的數據進行脫機推斷(即不查詢驗證器的推斷)。

簡單來說，可驗證隨機函數可以基于私鑰對一個輸入，產生一個唯一的固定長度的輸出，以及一個對應的證明。其他人在知道了公鑰、輸出、證明之后就一定能驗證這三者的正確性，并且也只有在知道了這三者之后才能驗證其正確性。

上面提及的這個過程以及相關的數據，是符合若干安全特性的，接下來會具體描述。

在VRF論文發出來后，到目前已有不同的團隊做出了不同的實現。而IETF目前正在為VRF的實現制定標準，目前還處于草案階段，并于2019-2-8已發布第四版草案。鏈接見文后參考部分。

1.2基本算法表述

從一個概要邏輯來說，VRF總共涉及到幾個相關函數，聯合起來完成一個證明和驗證的閉環。

首先簡單定義一下標識符：

SK：VRF的私鑰PK：VRF的公鑰alpha:VRF的輸入，將對其進行哈希beta:VRF哈希輸出pi:VRF證明Prover:持有VRF公私鑰的人就可以稱為證明人Verifier:只持有VRF公鑰的人，可以稱為驗證人VRF的基本算法，是很簡單清晰的，如下：

前提是有一個秘鑰對生成算法，來生成VRF需要用到的公私鑰對；證明人計算輸入的哈希：beta=VRF_hash(SK,alpha);>注意，VRF_hash算法是確定性的，對于相同的私鑰及相同的輸入，必定生成一個相同的輸出。證明人還需要用私鑰及輸入計算一個證明：pi=VRF_prove(SK,alpha)驗證人通過對應的公鑰可以驗證結果的正確性：VRF_verify(PK,alpha,pi)實際實現中，上面2和3可以放在一起，得到如beta,pi=VRF(SK,alpha)這樣的函數。

1.3所需滿足的安全特性

基于上一節的內容，還不能理解VRF的本質。如果不考慮相關的安全特性，那上面的實現是沒有意義的。那么，VRF需要滿足哪些安全特性呢？

藝術和娛樂數字藏品市場LimeWire將通過Algorand發行NFT:3月14日，藝術和娛樂數字藏品市場LimeWire宣布將通過Algorand發行NFT并成為藝術家和粉絲創造、購買和交易數字收藏品的一站式市場。LimeWire表示將與支付平臺Wyre合作，使得用戶可以直接通過信用卡、銀行轉賬等方式直接通過法幣購買NFT。此外，LimeWire還將在今年晚些時候推出代幣，代幣持有者擁有訪問獨家社區、進行投票和獲得獎勵的權利。

此前消息，點對點文件共享平臺LimeWire宣布將于5月以NFT市場的形式重啟。（PRNewswire）[2022/3/14 13:56:05]

總結起來，主要包括3種安全特性：唯一、防碰撞、偽隨機。另外，對于IETF的實現標準，即使在秘鑰對生成不夠可信的情況下，也可以保持“不可預測性”。

1.3.1完全唯一和可信唯一

唯一是指對于任意固定的VRF公鑰以及任意的輸入alpha，都存在唯一的可被證明有效的輸出beta。

完全唯一指在可計算范圍內對手不可能找到一個公鑰pk，一個輸入alpha，以及兩個證明pi1和pi2使得VRF_verify(pk,alpha,pi1)輸出(VALID,beta1)，VRF_verify(pk,alpha,pi2)輸出(VALID,beta2)，而beta1不等于beta2。

一個相對弱一點的安全特性叫可信唯一，對很多應用來說這就夠了。可信唯一只在VRF公私鑰是以一種值得信任的方式生成的情況下，才滿足唯一性，其他就和完全唯一一樣。換句話說，如果秘鑰對生成方式有問題或者使用了不好的隨機數，則唯一性可能無法保證。

直白來說，就是對于特定的一對公私鑰，任意一個alpha都有并且只有一對(beta,pi)，不存在說對于某個或某些輸出無法生成證明的情況；對于任意特定的alpha，系統中的任何一對公私鑰，都能生成唯一的與其他人不相同的(beta,pi)，不存在說對于某些輸入有些私鑰能構造有效證明但有些私鑰卻不能構造有效證明的情況。其中可信唯一相對弱一點是在于，對于只滿足這個特性的系統來說，可以特意構造某個公鑰PK，對于某個輸入alpha，可以構造兩個或多個不同的證明pi，用該PK都能驗證通過。

嚴格來說，世界上沒有絕對的事，上面的表述都是基于密碼學安全的意義之上的，就是說只要概率足夠小，我們就認為它不會發生，比如概率小于2^{-256}2?256。

由上面表述可以看到，一個好的秘鑰對生成算法，對VRF實現的唯一特性的保障是很重要的，這在我們選擇某種VRF實現的時候，應該要加以考量。

1.3.2完全防碰撞和可信防碰撞

完全防碰撞是指，對手要找到具有相同輸出的兩個不同的輸入alpha1和alpha2，在計算上是不可能的，即使他知道私鑰也是如此。

相對弱一點的安全特性是可信防碰撞，這指的是防碰撞特性需要基于一種可信的生成公私鑰的方式。

1.3.3完全偽隨機和選擇性偽隨機

偽隨機性確保對手在知道輸出beta但是不知道證據pi的情況下，beta是隨機的，不可能將其跟一個隨機值進行辨別。

更精確地說，假設公私鑰(pk,sk)是以一種可信方式生成的。偽隨機性確保了即使輸入是由對手仔細選擇的，對于計算能力有限的對手，只要他不知道私鑰，那么輸出beta對他而言也是隨機不可分辨的。甚至在對手有意選擇多個輸入并觀察對應輸出及證明的情況下，也是如此。簡單舉個例子就是，分別對一組有規律的輸入計算其對應的輸出，你去觀察研究這些輸出，不可能找出某種確定的規律。

舉個例子，偽隨機特性可以保證，你想要生成一個小于某個值的哈希，然后希望能快速推斷出一個輸入x使其滿足你的要求，這是做不到的。除了按窮舉法計算VRF哈希之外，別無捷徑。

Coinbase交易所教育平臺上線Algorand學習課程:11月17日早間，Coinbase官方發推宣布，旗下教育平臺Coinbase Earn已上線Algorand學習課程，用戶可通過學習課程賺取ALGO。[2020/11/17 21:02:10]

擁有完全偽隨機特性，則允許對手在任意時刻選擇輸入。直白但可能不夠準確地說，就是不管你什么時候給一個什么樣的輸入給我，你都無法知道我對該輸入產生的輸出哈希是大于還是小于某個值。

選擇性偽隨機是一個弱一點的安全特性，對于很多應用來說這也是足夠的。這時，對手選擇目標輸入需要獨立于VRF公鑰，并且要在他觀察到他選擇的alpha'所對應的beta'和pi'之前。直白但可能不夠準確地說，就是你知道了我的公鑰以及我曾經的一些(alpha,beta,pi)信息，然后你特意構造一個新的輸入，這時你可能可以知道我對該輸入的VRF輸出將會大于或小于某個值，而不用等我真正告訴你結果。

需要記住，VRF的輸出beta對證明人來說，是不隨機的。他們只要將beta和VRF_hash(sk,alpha)的結果進行比較，就可以輕易地將beta和一個隨機值區分出來。

同時，對于任何知道了對應pi的人，beta看起來也是不隨機的。只要檢查VRF_verify(PK,alpha,pi)是否返回(VALID,beta)，就可以將beta跟一個隨機值區別開。

還有，如果VRF秘鑰對不是用可信方式生成的，那么beta也可能看上去不是隨機的。

1.3.4一個“類隨機預言機”的不可預測特性

上面提到的偽隨機性，在秘鑰是由對手特意生成的情況下，是不滿足的。例如，如果對手輸出的秘鑰是確定地生成的，那么任何人都很容易獲得VRF的輸出。

然而，在一些VRF應用中，存在一種不同類型的不可預測性。這種特性類似于由一種密碼學哈希函數所提供的不可預測性：如果輸入具有足夠的熵，那么正確的輸出也是均勻不可辨別的。

雖然關于此特性在密碼學文獻中既沒有正式的定義，也沒有證明，但在IETF中呈現的VRF實現方案中，只要公鑰是以一種可信任的方式生成的，那么就可以相信滿足了這個特性。額外地，如果公鑰滿足一些特定驗證過程，那么即使公鑰不是可信方式生成的，ECVRF也滿足此特性。

1.4幾種實現方式概述及選擇考量

VRF都是基于非對稱加密技術來構建的，當前主流的非對稱加密技術，有RSA和橢圓曲線密碼學這兩種。這兩種技術都可以用于構建VRF實現。

具體實現就不做詳細介紹了，感興趣的還是以參考IETF的標準為主。

一般而言，一個基于RSA的VRF實現，能滿足可信唯一、可信防碰撞和完全偽隨機特性。不過，RSA方案的一個問題是，要起到足夠的安全性，則RSA的秘鑰長度需要比較長，這在很多應用場景下都不是很理想。

而目前，在非對稱加密領域，橢圓曲線加密是越來越被重視、越來越成為主流的非對稱加密技術。因此，對于VRF的實現也應該盡量選用基于橢圓曲線的實現方案，這種方案可簡稱為ECVRF。

ECVRF在具體實現時，可以有很多細分方案，包括選用不同的橢圓曲線、選用不同的將消息映射到曲線上的點的算法、選用不同的隨機數生成算法等等。

一般而言，ECVRF能滿足可信唯一、可信防碰撞和完全偽隨機特性，并且，如果在接收到一個VRF公鑰時，做一些額外驗證以驗證公鑰的有效性，那么ECVRF就能滿足完全唯一和完全防碰撞特性。

1.4.1額外討論：關于橢圓曲線的選擇

橢圓曲線是由如下形式方程式所定義的曲線：y^2=ax^3bx^2cxdy2=ax3bx2cxd

Algorand基金會與Chainalysis達成合作，加強反洗錢合規解決方案:6月11日，Algorand基金會宣布與區塊鏈分析公司Chainalysis達成合作。Algorand基金會將集成Chainalysis的KYT（了解你的交易）功能來進行交易監控和合規流程，并使用Chainalysis Reactor調查工具來加強對Algorand代幣ALGO的詳盡調查。[2020/6/12]

其中，可用于密碼學用途的橢圓曲線有很多，曾幾何時，最主流的曲線及相關算法都是由NIST選定和推薦的，稱為NIST-P系列，比如廣泛使用的P-256曲線。這種情況持續到了2013年，那一年，一個叫“愛德華·斯諾登”的牛人曝光了NSA的棱鏡計劃，其中曝光了NIST標準中一個基于橢圓雙曲線的隨機數生成器，叫Dual_EC_DRBG，包含后門，這可以使掌握該后門的NSA只根據生成器過去所產生的隨機數樣本，就可以預測后續的隨機數輸出，這樣的隨機數，對我們來說是偽隨機的，對NSA來說是可預測的。這個事件引起了人們對NIST的信任危機，雖然這個Dual_EC_DRBG跟NIST-P的加密算法沒有直接聯系，人們可以使用其他的偽隨機數生成算法，但是人們發現NIST-P曲線中都存在一些來歷不明的沒有任何說明的隨機數種子，比如下面的常數：

P-224:bd71344799d5c7fcdc45b59fa3b9ab8f6a948bc5

P-256:c49d360886e704936a6678e1139d26b7819f7e90

P-384:a335926aa319a27a1d00896a6773a4827acdac73

這時，一個新的曲線就閃亮登場了：Curve25519。Curve25519/Ed25519/X25519是著名密碼學家DanielJ.Bernstein在2006年獨立設計的橢圓曲線加密/簽名/密鑰交換算法，和現有的任何橢圓曲線算法都完全獨立。這些算法在開始的時候乏人問津，但在2013年之后一下子變得炙手可熱，成為絕對的主流已是大勢所趨了。

這一方面是因為這套算法完全開放設計，沒有任何秘密，沒有任何可疑的參數；同時，這套算法確實足夠優秀，足夠安全。此外，還有點題外話，這位Bernstein之前還曾因為將自己設計的加密算法Snuffle發布到網上而遭到美國政府起訴，他抗爭了6年，最后還是美國政府撤銷了指控，但之后他還反訴政府，直到2003年底法院駁回他的訴訟，要他在政府制造了“具體威脅”之后再來。

關于算法的安全性，Bernstein進行了全面的考察，結果見下面截圖，具體參見這里：

safecurves

目前Curve25519/Ed25519已得到廣泛應用，人們正在全面拋棄NIST，擁抱Curve25519，應用情況可參見：https://ianix.com/pub/curve25519-deployment.html和https://ianix.com/pub/ed25519-deployment.html。

1.5VRF與數字簽名算法方案的區別

對于剛接觸VRF的人來說，可能很容易產生一個疑問：非對稱數字簽名算法，跟VRF有什么區別？或者說，非對稱數字簽名算法起不到VRF的作用嗎？

在非對稱加密領域，存在數字簽名算法，對于一對秘鑰來說，可以計算消息m的簽名s=SIG(sk,m)，然后知道公鑰的人可以驗證s是否確實是簽名者用私鑰對m的簽名：Verify(pk,m,s)。另外，通過密碼學哈希算法，也能得到消息m的哈希值。

因此，這就跟VRF比較像了：

私鑰擁有者可以聲明自己的簽名結果s，其他人通過公開信息可以驗證該聲明；

動態 | 加密量化交易平臺提供商AlgoTrader AG完成380萬美元A輪融資:瑞士自動算法交易平臺提供商AlgoTrader AG周三宣布結束首輪融資，最終募資370萬瑞士法郎（約合380萬美元）。此輪融資由一家未具名的一級銀行領投，BlockChain Valley Ventures和NeueCapital參投，后者也是該公司種子輪的投資者。（Finance Magnates）[2020/1/9]

s是不可預測的，這具有密碼學上的安全性；可以再通過對s進行密碼學哈希，得到一個不可預測的哈希值。

那么為什么還需要VRF呢，直接用數字簽名的方案不行嗎？關于此問題，主要原因是，VRF相比于數字簽名方案，具有前面所描述的更多安全特性。對于數字簽名方案，有以下主要缺陷：

簽名結果s不是唯一的！對于很多數字簽名方案，同一個私鑰對同一個消息，可以給出不同的簽名。比如對于EdDSA，如果s=SIG(sk,m)，那么s\ells?也會是一個有效的簽名，其中\ell?是對應橢圓曲線基點的階。

s是不可預測的，但是s不一定是偽隨機的。也就是說，s在取值范圍內的分布可能不是均勻的。

對于上面第1點，當然存在一些特定的數字簽名實現，比如將中的數字簽名方案中的隨機數，使用中的GGM偽隨機預言機代替之后，數字簽名可以是唯一的。但是人們沒辦法確認簽名者是否采用了這么一種方案，因此也就是說唯一性是無法保證的。

無法保證唯一性的數字簽名方案，可以認為是一種“可驗證不可預測函數”，但不是“可驗證(偽)隨機函數”。

2AlgorandVRF密碼學抽簽算法及應用

2.1抽簽算法原理剖析

2.1.1抽簽原理

基于VRF的密碼學抽簽算法用于根據每個用戶的權重，隨機選出用戶的一個子集。整個抽簽過程中，需要保證：

不存在上帝角色操縱整個抽簽；每個參與者獨立做自己的抽簽，在主動公布自己的抽簽結果之前，其他任何人都不可能知道該抽簽結果；參與者公布自己的抽簽結果后，系統中的其他參與者都可以驗證該結果，參與者不需要泄漏自己的私鑰；在一輪抽簽開始之前，任何參與者都不能預先計算自己的抽簽結果；抽簽對所有參與者都是公平公正的；防女巫攻擊。具體做法就是，假設參與者ii的權重是w_iwi?，所有參與者的權重總和W=\sum_i{w_i}W=∑i?wi?，對于具體的抽簽目的，我們設置一個期望值tt，表示在所有的權重當中，希望抽出tt份權重。這樣，我們基于“伯努利試驗”的抽簽方式，按p=\frac{t}{W}p=Wt?的概率，讓每個參與者ii依據自己的權重w_iwi?做w_iwi?次抽簽，這樣所有參與者就總共做了WW次抽簽，抽簽結果將是符合二項分布的。

接下來，需要做的就是構造這個“伯努利試驗”，這就用到了VRF。首先，要求每個參與者都擁有一對公私鑰，(pk_i,sk_i)(pki?,ski?)，然后，為了滿足前面提到的要求，還需要定義一個種子seed，以及標識抽簽階段的一些數據，比如round。其中，需要盡可能讓參與者在開始某一輪抽簽的時候，才知道所用到的seed，這個根據具體的應用場景來定。

這時，就可以基于VRF構建我們的“伯努利試驗”了。設x是由seed、round等組成的抽簽參數，則參與者先計算x的VRF哈希及證明：hash,pi=VRF_{sk_i}(x)hash,pi=VRFski??(x)。這時得到的哈希的長度是固定的，比如32字節，由VRF的安全特性，我們知道hash是在區間內均勻分布的，將該哈希值變為一個小數，即d=\frac{hash}{2^{256}}d=2256hash?，這時dd就在區間之間均勻分布。

動態 | 區塊鏈公司Bleumi將幫助企業利用Algorand，并開始接受Algos支付:Algorand Official官方宣布， 區塊鏈產品和服務公司Bleumi將成為Algorand和生態系統中的一員，幫助企業利用Algorand，并開始接受Algos的支付。[2019/9/4]

另外，已知以概率p做n次伯努利試驗，實際成功次數為k次的概率，計算公式如下：\binom{n}{k}p^k(1-p)^{n-k}(kn?)pk(1?p)n?k

將k=0...j所對應的概率加起來，假設用Sum(j)表示，我們找到一個j值，使其滿足式子Sum(j)\led\ltSum(j1)Sum(j)≤d0j>0時表示抽中了jj份權重。

由于用戶的權重越大，即w越大，其抽簽次數就越多，從而基于相同的概率p，得到j>0j>0的概率也就會越大，因此，用戶被選中的概率是跟他們的權重是成比例的。另外，當j>0j>0，我們可以想象成用戶有jj個子用戶被抽中了，如果是投票，就可以投jj票。這樣一來，w個權重為1的用戶，有j個被抽中的概率，跟1個權重為w的用戶，有j個子用戶被抽中的概率，是一樣的。也就是說，這種抽簽是防女巫攻擊的。

最后，對于驗證者來說，他可以基于VRF驗證機制，驗證抽簽參與者的哈希及證明，驗證通過之后，執行相同的抽簽計算，看結果j'j′跟jj是否一致。

2.1.2抽簽算法

對應前面的描述，抽簽算法如下：\begin{aligned}&\text{VrfSortition}(sk,seed,round,role,t,w,W):\\&\quad\langlehash,\pi\rangle\getsVRF_{sk}(seed\|role\|round)\\&\quadp\gets\frac{t}{W}\\&\quadj\gets0\\&\quadwhile\frac{hash}{2^{hashlen}}otin\bigg[\sum_{k=0}^{j}B(k;w,p),\sum_{k=0}^{j1}B(k;w,p)\bigg)\do\\&\quad\\big\lfloor\j\\&\quadreturn\\langlehash,\pi,j\rangle\\\end{aligned}?VrfSortition(sk,seed,round,role,t,w,W):?hash,π?←VRFsk?(seed∥role∥round)p←Wt?j←0while2hashlenhash?∈/?[k=0∑j?B(k;w,p),k=0∑j1?B(k;w,p))do?jreturn?hash,π,j??其中，sksk為用戶私鑰，rolerole參數和roundround參數用于區分共識過程中的角色與階段，一個閾值t用于確定本次抽簽所期望選中的用戶數。hash,\pihash,π分別為VRF哈希值及證明。

3.2抽簽驗證算法

驗證過程算法描述如下：\begin{aligned}&\text{VrfVerifySortition}(pk,seed,round,role,\pi,t,w,W):\\&\quadifegVerifyVRF_{pk}(hash,\pi,seed\|role\|round)\then\return\0;\\&\quadp\gets\frac{t}{W}\\&\quadj\gets0\\&\quadwhile\frac{hash}{2^{hashlen}}otin\bigg[\sum_{k=0}^{j}B(k;w,p),\sum_{k=0}^{j1}B(k;w,p)\bigg)\do\\&\quad\\big\lfloor\j\\&\quadreturn\j\\\end{aligned}?VrfVerifySortition(pk,seed,round,role,π,t,w,W):if?VerifyVRFpk?(hash,π,seed∥role∥round)thenreturn0;p←Wt?j←0while2hashlenhash?∈/?[k=0∑j?B(k;w,p),k=0∑j1?B(k;w,p))do?jreturnj?驗證過程先驗證\piπ是否合法有效，然后依據與抽簽類似的過程獲得用戶被選中的子用戶數(0表示根本沒被抽中)，從而與用戶隨消息廣播出來的j值做比較以驗證其正確性。

2.2抽簽結果的概率分布

根據前面的描述，我們知道整個VRF密碼學抽簽算法，是概率性的，概率符合二項分布。也就是說，給定期望值t，實際結果k是不固定的。在這種情況下，密碼學抽簽怎么應用與具體的場景，那就得具體情況具體分析了。

在這里，我們先看一下如何計算抽簽結果的概率分布。如果總權重W是比較小的，從而概率p是比較大的，那這時直接用二項分布公式進行計算就可以了。

但如果W很大，那就要考慮別的方式了。首先，再列一下二項分布概率公式：\binom{U}{K}p^K(1-p)^{U-K}(KU?)pK(1?p)U?K將其展開得如下式子：\frac{U!}{K!(U-K)!}(\frac{t}{U})^K(1-\frac{t}{U})^{U-K}=\frac{U\dots(U-K1。{U^K}\frac{t^K}{K!}(1-\frac{t}{U})^{U-K}K!(U?K)!U!?(Ut?)K(1?Ut?)U?K=UKU…(U?K1)?K!tK?(1?Ut?)U?K

由于K是個比較小的值，當U很大時，下面的等式是可以接受的；或者換個方式說，當U大到我們可以接受如下式子的時候，U就足夠大了：\frac{U\dots(U-K1。{U^K}=1UKU…(U?K1)?=1另外，U足夠大時，我們肯定還能接受如下等式。其中分子轉換成常數e的指數，這是根據指數函數的定義來的。(1-\frac{t}{U})^{U-K}=\frac{(1-\frac{t}{U})^U}{(1-\frac{t}{U})^K}=\frac{e^{-t}}{1}=e^{-t}(1?Ut?)U?K=(1?Ut?)K(1?Ut?)U?=1e?t?=e?t綜合起來就得到當U很大，且期望為t時，實際抽簽結果為K的概率為：\frac{t^K}{K!}e^{-t}\quad\quad\text{(1。K!tK?e?t(1)

2.3在區塊鏈中的應用及要解決的問題

Algorand項目開創了密碼學抽簽算法在區塊鏈中的應用，主要用在兩種場景下：通過抽簽獲得區塊提議者；通過抽簽獲得區塊驗證委員會。

對于第一種場景，期望值t應該是比較小的，主要需要考慮的是，實際抽簽結果k應該以很高的概率大于0，同時k又不應該很大。Algorand給出了一個值t=26，這時k在1到70之間的概率為：\sum_{k=1}^{70}\frac{26^k}{k!}e^{-26}>1-10^{-11}k=1∑70?k!26k?e?26>1?10?11

對于第二種場景，就比較復雜了。除了單純抽簽概率上的考慮，還要考慮網絡中惡意用戶或者說拜占庭節點的影響，以及投票通過的閾值。

根據Algorand的分析，假設網絡中誠實用戶所占的權重比例為h，委員會期望權重為t，由上面的公式，可以得到最終誠實權重為k的概率為：\frac{(ht)^K}{K!}e^{-ht}\quad\quad\text{(2。K!(ht)K?e?ht(2)

在一個存在拜占庭節點的投票委員會中，設投票通過的閾值為r，則要保證系統的活性即能完成投票，需要滿足下面的條件1：

條件1：\#good>t*r#good>t?r>\#good#good表示誠實票數

通過上面的概率公式，這個條件不滿足的概率是可以計算出來的，不滿足的概率為:\sum_{K=0}^{t*r}\frac{(ht)^K}{K!}e^{-ht}K=0∑t?r?K!(ht)K?e?ht

另外，考慮拜占庭節點，要保證系統的安全性，假設#bad表示不誠實的票數，那么要保證安全性就要滿足下面的條件：

條件2：\frac{1}{2}\#good\#bad\let*r\,21?#good#bad≤t?r

對于條件2，抽取#good=K并且#bad=L的概率如下：\frac{(ht)^K}{K!}e^{-ht}\frac{((1-h)t)^L}{L!}e^{-(1-h)t}K!(ht)K?e?htL!((1?h)t)L?e?(1?h)t

條件2不滿足的概率是不大好算的，實際評估時，我們可以先計算條件2滿足的概率，公式為:\sum_{K=0}^{2t*r}\sum_{L=0}^{\frac{2*t*r-K}{2}}\frac{(ht)^K}{K!}e^{-ht}\frac{((1-h)t)^L}{L!}e^{-(1-h)t}K=0∑2t?r?L=0∑22?t?r?K??K!(ht)K?e?htL!((1?h)t)L?e?(1?h)t

用1.0減去計算結果，可得到條件2被違背的概率。>當然，先計算概率大的情況時，計算精度會降低。

上面兩個條件均不滿足的概率需要極小極小，才可以認為不會影響系統的活性和安全性。舉個淺顯的例子就是：假設定下來t=100,r=0.7,h=0.8。那么投票閾值就是70，但是由于抽簽結果的概率性，那么如果抽簽結果不足70，那就完不成投票了，如果抽簽結果大于140，那在網絡不好的情況下是不是可能出現分歧呢？另外，由于總體誠實比例只有0.8，那也有可能抽簽結果中不誠實數直接就超過70，那也可能搞亂整個投票，這時，確切地說就是條件2的情況。

綜上，理論上來說，活性和安全性都是無法絕對保障的，但是可以考慮一個很小的概率F，當兩個條件被違背的概率均小于F時，我們可以認為這樣的事件基本不會發生。

這個F跟t,r,h都有一定的負相關關系，就是t,r,h中任意兩個值不變的情況下，第三個值越大，F就越小。例如，r,h不變時，t越大，F越小。

還有一個問題，t也不是越大越好的。t很大時，雖然可以使F很小，但是在一個分布式網絡中，t越大則完成投票所需要的通信量也就越大，所以這需要權衡考慮。

以上，就是本文分享的所有內容了。至于Algorand項目中是如何權衡相關問題的，敬請關注后續分享。

參考

VerifiableRandomFunctions

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

https://tools.ietf.org/pdf/draft-irtf-cfrg-vrf-04.pdf

https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/

ShafiGoldwasser,SilvioMicali,andRonaldL.Rivest.Adigitalsignatureschemesecureagainstadaptivechosen-messageattacks.SIAMJournalonComputing,17(2):281–308,April1988.

ShafiGoldwasser,SilvioMicali,andCharlesRack-off.Theknowledgecomplexityofinteractiveproofsystems.SIAMJournalonComputing,18(1):186–208,February1989.

curve25519

https://en.wikipedia.org/wiki/Daniel_J._Bernstein

https://en.wikipedia.org/wiki/Bernstein_v._United_States

https://en.wikipedia.org/wiki/Nothing-up-my-sleeve_number

http://cr.yp.to/djb.html

http://cr.yp.to/ecdh.html

https://safecurves.cr.yp.to/

https://ianix.com/pub/curve25519-deployment.html

https://en.wikipedia.org/wiki/Dual_EC_DRBG

Algorand-ScalingByzantineAgreementsforCryptocurrencies

Tags：RACFRAALGOALGBrace ProtocolFRASAlgorandalgo幣2023

以太坊交易