1 VRF介紹

隨著Algorand項(xiàng)目的發(fā)起，原來越多的人對(duì)其所應(yīng)用到的密碼學(xué)抽簽技術(shù)產(chǎn)生了興趣并探索相關(guān)的應(yīng)用。目前赤兴，隨著Algorand項(xiàng)目的主網(wǎng)上線空郊，該技術(shù)也開始了接受大規(guī)模的正式實(shí)踐檢驗(yàn)，我們拭目以待顾稀。

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

1.1 簡(jiǎn)介

VRF全稱為 Verifiable Random Functions，翻譯為“可驗(yàn)證隨機(jī)函數(shù)”饵蒂，由Silvio Micali声诸，Michael Rabiny，Salil Vadhan于1999年提出退盯，是一種基于公私鑰的密碼學(xué)哈希函數(shù)彼乌。（關(guān)注過Algorand的人一眼就可以看出來泻肯，第一作者正是Algorand創(chuàng)始人Silvio Micali）。只有擁有VRF私鑰才能計(jì)算哈希慰照，但任何擁有對(duì)應(yīng)公鑰的人都可以驗(yàn)證該哈希的正確性软免。

VRF的一個(gè)關(guān)鍵應(yīng)用就是，提供對(duì)存儲(chǔ)在基于散列的數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)的隱私保護(hù)焚挠，防止離線枚舉（例如字典攻擊）膏萧。在這種應(yīng)用中，證明人持有VRF私鑰蝌衔，并使用VRF哈希在輸入數(shù)據(jù)上構(gòu)造基于散列的數(shù)據(jù)結(jié)構(gòu)榛泛。由于VRF的性質(zhì)，只有證明人才能回答關(guān)于數(shù)據(jù)結(jié)構(gòu)中是否存儲(chǔ)了某些數(shù)據(jù)的查詢噩斟。任何知道VRF公鑰的人都可以驗(yàn)證證明人正確地回答了查詢曹锨。但是，不能對(duì)數(shù)據(jù)結(jié)構(gòu)中存儲(chǔ)的數(shù)據(jù)進(jìn)行脫機(jī)推斷(即不查詢驗(yàn)證器的推斷)剃允。

簡(jiǎn)單來說沛简，可驗(yàn)證隨機(jī)函數(shù)可以基于私鑰 對(duì)一個(gè)輸入，產(chǎn)生一個(gè)唯一的固定長(zhǎng)度的輸出斥废，以及一個(gè)對(duì)應(yīng)的證明椒楣。其他人在知道了公鑰、輸出牡肉、證明 之后就一定能驗(yàn)證這三者的正確性捧灰，并且也只有在知道了這三者之后才能驗(yàn)證其正確性。

上面提及的這個(gè)過程以及相關(guān)的數(shù)據(jù)统锤，是符合若干安全特性的毛俏，接下來會(huì)具體描述。

在VRF論文發(fā)出來后饲窿，到目前已有不同的團(tuán)隊(duì)（個(gè)人煌寇、組織、機(jī)構(gòu)）做出了不同的實(shí)現(xiàn)逾雄。而IETF（Internet Engineering Task Force）目前正在為VRF的實(shí)現(xiàn)制定標(biāo)準(zhǔn)阀溶，目前還處于草案階段，并于 2019-2-8已發(fā)布第四版草案嘲驾。鏈接見文后參考部分淌哟。

1.2 基本算法表述

從一個(gè)概要邏輯來說，VRF總共涉及到幾個(gè)相關(guān)函數(shù)辽故，聯(lián)合起來完成一個(gè)證明和驗(yàn)證的閉環(huán)徒仓。

首先簡(jiǎn)單定義一下標(biāo)識(shí)符：

SK：VRF的私鑰

PK：VRF的公鑰

alpha: VRF的輸入，將對(duì)其進(jìn)行哈希

beta: VRF哈希輸出

pi: VRF證明

Prover: 持有VRF公私鑰的人就可以稱為證明人

Verifier: 只持有VRF公鑰的人誊垢，可以稱為驗(yàn)證人

VRF的基本算法掉弛，是很簡(jiǎn)單清晰的症见，如下：

前提是有一個(gè)秘鑰對(duì)生成算法，來生成VRF需要用到的公私鑰對(duì)殃饿；

證明人計(jì)算輸入的哈希：beta = VRF_hash(SK,alpha); > 注意谋作，VRF_hash算法是確定性的，對(duì)于相同的私鑰及相同的輸入乎芳，必定生成一個(gè)相同的輸出遵蚜。

證明人還需要用私鑰及輸入計(jì)算一個(gè)證明： pi = VRF_prove(SK, alpha)

驗(yàn)證人通過對(duì)應(yīng)的公鑰可以驗(yàn)證結(jié)果的正確性：VRF_verify(PK, alpha, pi)

實(shí)際實(shí)現(xiàn)中，上面2和3可以放在一起奈惑，得到如 beta,pi = VRF(SK,alpha) 這樣的函數(shù)吭净。

1.3 所需滿足的安全特性

基于上一節(jié)的內(nèi)容，還不能理解VRF的本質(zhì)肴甸。如果不考慮相關(guān)的安全特性寂殉，那上面的實(shí)現(xiàn)是沒有意義的。那么原在，VRF需要滿足哪些安全特性呢友扰？

總結(jié)起來，主要包括3種安全特性：唯一庶柿、防碰撞村怪、偽隨機(jī)。另外澳泵，對(duì)于IETF的實(shí)現(xiàn)標(biāo)準(zhǔn)实愚，即使在秘鑰對(duì)生成不夠可信的情況下，也可以保持“不可預(yù)測(cè)性”兔辅。

1.3.1 完全唯一 和 可信唯一

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

完全唯一（full uniqueness）指在可計(jì)算范圍內(nèi)對(duì)手不可能找到一個(gè)公鑰pk维苔，一個(gè)輸入alpha，以及兩個(gè)證明 pi1 和 pi2 使得 VRF_verify(pk,alpha,pi1) 輸出 (VALID,beta1)懂昂，VRF_verify(pk,alpha,pi2) 輸出 (VALID,beta2)介时，而 beta1不等于beta2。

一個(gè)相對(duì)弱一點(diǎn)的安全特性叫可信唯一（trusted uniqueness）凌彬，對(duì)很多應(yīng)用來說這就夠了沸柔。可信唯一只在VRF公私鑰是以一種值得信任的方式生成的情況下铲敛，才滿足唯一性褐澎，其他就和完全唯一一樣。換句話說伐蒋，如果秘鑰對(duì)生成方式有問題或者使用了不好的隨機(jī)數(shù)工三，則唯一性可能無法保證迁酸。

直白來說，就是（1）對(duì)于特定的一對(duì)公私鑰（sk,pk）俭正，任意一個(gè)alpha都有并且只有一對(duì) (beta,pi)奸鬓，不存在說對(duì)于某個(gè)或某些輸出無法生成證明的情況；（2）對(duì)于任意特定的 alpha掸读，系統(tǒng)中的任何一對(duì)公私鑰（sk,pk）串远，都能生成唯一的與其他人不相同的 (beta,pi)，不存在說對(duì)于某些輸入有些私鑰能構(gòu)造有效證明但有些私鑰卻不能構(gòu)造有效證明的情況儿惫。

其中可信唯一相對(duì)弱一點(diǎn)是在于抑淫，對(duì)于只滿足這個(gè)特性的系統(tǒng)來說，可以特意構(gòu)造某個(gè)公鑰 PK（它可能沒有對(duì)應(yīng)的有效的私鑰）姥闪，對(duì)于某個(gè)輸入alpha始苇，可以構(gòu)造兩個(gè)或多個(gè)不同的證明pi，用該P(yáng)K都能驗(yàn)證通過筐喳。

嚴(yán)格來說催式，世界上沒有絕對(duì)的事，上面的表述都是基于密碼學(xué)安全的意義之上的避归，就是說只要概率足夠小荣月，我們就認(rèn)為它不會(huì)發(fā)生，比如概率小于

2

?

256

2

?256

? 梳毙。

由上面表述可以看到哺窄，一個(gè)好的秘鑰對(duì)生成算法，對(duì)VRF實(shí)現(xiàn)的唯一特性的保障是很重要的账锹，這在我們選擇某種VRF實(shí)現(xiàn)的時(shí)候萌业，應(yīng)該要加以考量。

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

完全防碰撞是指奸柬，對(duì)手要找到具有相同輸出的兩個(gè)不同的輸入alpha1和alpha2生年，在計(jì)算上是不可能的，即使他知道私鑰也是如此廓奕。

相對(duì)弱一點(diǎn)的安全特性是 可信防碰撞抱婉，這指的是防碰撞特性需要基于一種可信的生成公私鑰的方式。

1.3.3 完全偽隨機(jī) 和 選擇性偽隨機(jī)

偽隨機(jī)性確保對(duì)手在知道輸出beta但是不知道證據(jù)pi的情況下桌粉，beta是隨機(jī)的蒸绩，不可能將其跟一個(gè)隨機(jī)值進(jìn)行辨別。

更精確地說铃肯，假設(shè)公私鑰(pk,sk)是以一種可信方式生成的患亿。偽隨機(jī)性確保了即使輸入是由對(duì)手仔細(xì)選擇的，對(duì)于計(jì)算能力有限的對(duì)手缘薛，只要他不知道私鑰窍育，那么輸出beta對(duì)他而言也是隨機(jī)不可分辨的卡睦。甚至在對(duì)手有意選擇多個(gè)輸入并觀察對(duì)應(yīng)輸出及證明的情況下，也是如此漱抓。

簡(jiǎn)單舉個(gè)例子就是表锻，分別對(duì)一組有規(guī)律的輸入 [alpha1,alpha2,...,alphan] 計(jì)算其對(duì)應(yīng)的輸出[(beta1,pi1),(beta2,pi2),...,(betan,pin)]，你去觀察研究這些輸出乞娄，不可能找出某種確定的規(guī)律瞬逊。

舉個(gè)例子，偽隨機(jī)特性可以保證仪或，你想要生成一個(gè)小于某個(gè)值的哈希（比如按16進(jìn)制輸出后前面有10個(gè)0确镊，0x0000000000...），然后希望能快速推斷出一個(gè)輸入x使其滿足你的要求范删，這是做不到的蕾域。除了按窮舉法計(jì)算VRF哈希之外，別無捷徑到旦。

擁有完全偽隨機(jī)特性旨巷，則允許對(duì)手在任意時(shí)刻選擇輸入。直白但可能不夠準(zhǔn)確地說添忘，就是不管你什么時(shí)候給一個(gè)什么樣的輸入給我采呐，你都無法知道我對(duì)該輸入產(chǎn)生的輸出哈希是大于還是小于某個(gè)值。

選擇性偽隨機(jī)是一個(gè)弱一點(diǎn)的安全特性搁骑，對(duì)于很多應(yīng)用來說這也是足夠的斧吐。這時(shí)，對(duì)手選擇目標(biāo)輸入需要獨(dú)立于VRF公鑰仲器，并且要在他觀察到他選擇的alpha'所對(duì)應(yīng)的beta'和pi'之前煤率。直白但可能不夠準(zhǔn)確地說，就是你知道了我的公鑰以及我曾經(jīng)的一些(alpha,beta,pi)信息娄周，然后你特意構(gòu)造一個(gè)新的輸入涕侈，這時(shí)你可能可以知道我對(duì)該輸入的VRF輸出將會(huì)大于或小于某個(gè)值，而不用等我真正告訴你結(jié)果煤辨。

需要記住，VRF的輸出beta對(duì)證明人（或任何知道了私鑰的人）來說木张，是不隨機(jī)的众辨。他們只要將beta和VRF_hash(sk, alpha)的結(jié)果進(jìn)行比較，就可以輕易地將beta和一個(gè)隨機(jī)值區(qū)分出來舷礼。

同時(shí)鹃彻，對(duì)于任何知道了對(duì)應(yīng)pi的人，beta看起來也是不隨機(jī)的妻献。只要檢查VRF_verify(PK, alpha, pi)是否返回 (VALID, beta)蛛株，就可以將beta跟一個(gè)隨機(jī)值區(qū)別開团赁。

還有，如果VRF秘鑰對(duì)不是用可信方式生成的（例如谨履，如果VRF秘鑰對(duì)使用不好的隨機(jī)數(shù)生成的）欢摄，那么beta也可能看上去不是隨機(jī)的。

1.3.4 一個(gè) “類隨機(jī)預(yù)言機(jī)”的不可預(yù)測(cè)特性

上面提到的偽隨機(jī)性笋粟，在秘鑰是由對(duì)手特意生成的情況下怀挠，是不滿足的。例如害捕，如果對(duì)手輸出的秘鑰是確定地生成的（或硬編碼的并且是公開的）绿淋，那么任何人都很容易獲得VRF的輸出。

然而尝盼，在一些VRF應(yīng)用中吞滞，存在一種不同類型的不可預(yù)測(cè)性。這種特性類似于由一種（普通的盾沫，不基于秘鑰對(duì)的）密碼學(xué)哈希函數(shù)所提供的不可預(yù)測(cè)性：如果輸入具有足夠的熵（如：不可能被預(yù)測(cè)到）裁赠，那么正確的輸出也是均勻不可辨別的。

雖然關(guān)于此特性在密碼學(xué)文獻(xiàn)中既沒有正式的定義疮跑，也沒有證明组贺，但在IETF中呈現(xiàn)的VRF實(shí)現(xiàn)方案中，只要公鑰是以一種可信任的方式生成的祖娘，那么就可以相信滿足了這個(gè)特性失尖。額外地，如果公鑰滿足一些特定驗(yàn)證過程渐苏，那么即使公鑰不是可信方式生成的掀潮，ECVRF也滿足此特性。

1.4 幾種實(shí)現(xiàn)方式概述及選擇考量

VRF都是基于非對(duì)稱加密技術(shù)來構(gòu)建的琼富，當(dāng)前主流的非對(duì)稱加密技術(shù)仪吧，有RSA和橢圓曲線密碼學(xué)這兩種。這兩種技術(shù)都可以用于構(gòu)建VRF實(shí)現(xiàn)鞠眉。

具體實(shí)現(xiàn)就不做詳細(xì)介紹了薯鼠，感興趣的還是以參考IETF的標(biāo)準(zhǔn)為主。

一般而言械蹋，一個(gè)基于RSA的VRF實(shí)現(xiàn)出皇，能滿足可信唯一、可信防碰撞和完全偽隨機(jī)特性哗戈。不過郊艘，RSA方案的一個(gè)問題是，要起到足夠的安全性，則RSA的秘鑰長(zhǎng)度需要比較長(zhǎng)纱注，這在很多應(yīng)用場(chǎng)景下都不是很理想畏浆。

而目前，在非對(duì)稱加密領(lǐng)域狞贱，橢圓曲線加密是越來越被重視刻获、越來越成為主流的非對(duì)稱加密技術(shù)。因此斥滤，對(duì)于VRF的實(shí)現(xiàn)也應(yīng)該盡量選用基于橢圓曲線的實(shí)現(xiàn)方案将鸵，這種方案可簡(jiǎn)稱為 ECVRF。

ECVRF在具體實(shí)現(xiàn)時(shí)佑颇，可以有很多細(xì)分方案顶掉，包括選用不同的橢圓曲線、選用不同的將消息映射到曲線上的點(diǎn)的算法（需要注意挑胸，橢圓曲線密碼學(xué)是基于有限域的痒筒，密碼學(xué)中所說的橢圓曲線上的點(diǎn)是離散的、不連續(xù)的）茬贵、選用不同的隨機(jī)數(shù)生成算法等等簿透。

一般而言，ECVRF能滿足可信唯一解藻、可信防碰撞和完全偽隨機(jī)特性老充，并且，如果在接收到一個(gè)VRF公鑰時(shí)螟左，做一些額外驗(yàn)證以驗(yàn)證公鑰的有效性啡浊，那么ECVRF就能滿足完全唯一和完全防碰撞特性。

1.4.1 額外討論：關(guān)于橢圓曲線的選擇

橢圓曲線是由如下形式方程式所定義的曲線：

y

2

=

a

x

3

+

b

x

2

+

c

x

+

d

y

2

=ax

3

+bx

2

+cx+d

其中胶背，可用于密碼學(xué)用途的橢圓曲線有很多巷嚣，曾幾何時(shí)锈死，最主流的曲線及相關(guān)算法都是由NIST（美國國家標(biāo)準(zhǔn)與技術(shù)研究院）選定和推薦的盟广，稱為NIST-P系列，比如廣泛使用的 P-256 曲線烘苹。這種情況持續(xù)到了2013年红且，那一年坝茎，一個(gè)叫“愛德華·斯諾登”（Edward Snowden）的牛人曝光了NSA的棱鏡計(jì)劃，其中曝光了NIST標(biāo)準(zhǔn)中一個(gè)基于橢圓雙曲線的隨機(jī)數(shù)生成器暇番，叫 Dual_EC_DRBG景东，包含后門，這可以使掌握該后門的NSA只根據(jù)生成器過去所產(chǎn)生的隨機(jī)數(shù)樣本奔誓，就可以預(yù)測(cè)后續(xù)的隨機(jī)數(shù)輸出，這樣的隨機(jī)數(shù)，對(duì)我們來說是偽隨機(jī)的厨喂，對(duì)NSA來說是可預(yù)測(cè)的和措。這個(gè)事件引起了人們對(duì)NIST的信任危機(jī)，雖然這個(gè)Dual_EC_DRBG跟NIST-P的加密算法沒有直接聯(lián)系蜕煌，人們可以使用其他的偽隨機(jī)數(shù)生成算法派阱，但是人們發(fā)現(xiàn)NIST-P曲線中都存在一些來歷不明的沒有任何說明的隨機(jī)數(shù)種子，比如下面的常數(shù)（參見：Nothing-up-my-sleeve_number）：

P-224: bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5

P-256: c49d3608 86e70493 6a6678e1 139d26b7 819f7e90

P-384: a335926a a319a27a 1d00896a 6773a482 7acdac73

這時(shí)斜纪，一個(gè)新的曲線就閃亮登場(chǎng)了：Curve25519贫母。Curve25519/Ed25519/X25519 是著名密碼學(xué)家 Daniel J.Bernstein 在 2006 年獨(dú)立設(shè)計(jì)的橢圓曲線加密/簽名/密鑰交換算法，和現(xiàn)有的任何橢圓曲線算法都完全獨(dú)立盒刚。這些算法在開始的時(shí)候乏人問津腺劣，但在2013年之后一下子變得炙手可熱，成為絕對(duì)的主流已是大勢(shì)所趨了因块。

這一方面是因?yàn)檫@套算法完全開放設(shè)計(jì)橘原，沒有任何秘密，沒有任何可疑的參數(shù)涡上；同時(shí)趾断，這套算法確實(shí)足夠優(yōu)秀，足夠安全吩愧。此外芋酌，還有點(diǎn)題外話，這位Bernstein之前還曾因?yàn)閷⒆约涸O(shè)計(jì)的加密算法Snuffle發(fā)布到網(wǎng)上而遭到美國政府起訴雁佳，他抗?fàn)幜?年脐帝，最后還是美國政府撤銷了指控（跟全球大環(huán)境變化也有關(guān)系），但之后他還反訴政府甘穿，直到2003年底法院駁回他的訴訟腮恩，要他在政府制造了“具體威脅”之后再來。

關(guān)于算法的安全性温兼，Bernstein進(jìn)行了全面的考察秸滴，結(jié)果見下面截圖，具體參見這里： safecurves

safecurves

目前Curve25519/Ed25519已得到廣泛應(yīng)用募判，人們正在全面拋棄NIST荡含，擁抱Curve25519，應(yīng)用情況可參見：https://ianix.com/pub/curve25519-deployment.html 和 https://ianix.com/pub/ed25519-deployment.html 届垫。

1.5 VRF與數(shù)字簽名算法方案的區(qū)別

對(duì)于剛接觸VRF的人來說释液，可能很容易產(chǎn)生一個(gè)疑問：非對(duì)稱數(shù)字簽名算法，跟VRF有什么區(qū)別装处？或者說误债，非對(duì)稱數(shù)字簽名算法起不到VRF的作用嗎浸船？

在非對(duì)稱加密領(lǐng)域，存在數(shù)字簽名算法寝蹈，對(duì)于一對(duì)秘鑰 （pk,sk）來說李命，可以計(jì)算消息 m 的簽名 s = SIG(sk,m)，然后知道公鑰的人可以驗(yàn)證 s 是否確實(shí)是簽名者用私鑰對(duì)m的簽名：Verify(pk,m,s)箫老。另外封字，通過密碼學(xué)哈希算法，也能得到消息m的哈希值耍鬓。

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

私鑰擁有者可以聲明自己的簽名結(jié)果s，其他人通過公開信息（pk,m,s）可以驗(yàn)證該聲明牲蜀；

s是不可預(yù)測(cè)的笆制，這具有密碼學(xué)上的安全性；可以再通過對(duì)s進(jìn)行密碼學(xué)哈希各薇，得到一個(gè)不可預(yù)測(cè)的哈希值项贺。

那么為什么還需要VRF呢，直接用數(shù)字簽名的方案不行嗎峭判？ 關(guān)于此問題开缎，主要原因是，VRF相比于數(shù)字簽名方案林螃，具有前面所描述的更多安全特性奕删。對(duì)于數(shù)字簽名方案，有以下主要缺陷：

簽名結(jié)果s不是唯一的疗认！對(duì)于很多數(shù)字簽名方案完残，同一個(gè)私鑰對(duì)同一個(gè)消息，可以給出不同的簽名横漏。比如對(duì)于EdDSA谨设，如果 s = SIG(sk,m)，那么

s

+

?

s+? 也會(huì)是一個(gè)有效的簽名缎浇，其中

?

? 是對(duì)應(yīng)橢圓曲線基點(diǎn)（即生成元）的階扎拣。

s是不可預(yù)測(cè)的，但是s不一定是偽隨機(jī)的素跺。也就是說二蓝，s在取值范圍內(nèi)的分布可能不是均勻的。

對(duì)于上面第1點(diǎn)指厌，當(dāng)然存在一些特定的數(shù)字簽名實(shí)現(xiàn)刊愚，比如將[GMR88]中的數(shù)字簽名方案中的隨機(jī)數(shù)，使用[GMR89]中的GGM偽隨機(jī)預(yù)言機(jī)代替之后踩验，數(shù)字簽名可以是唯一的鸥诽。但是人們沒辦法確認(rèn)簽名者是否采用了這么一種方案商玫，因此也就是說唯一性是無法保證的。

無法保證唯一性的數(shù)字簽名方案衙传，可以認(rèn)為是一種“可驗(yàn)證不可預(yù)測(cè)函數(shù)”决帖，但不是“可驗(yàn)證(偽)隨機(jī)函數(shù)”。

2 Algorand VRF密碼學(xué)抽簽算法及應(yīng)用

2.1 抽簽算法原理剖析

2.1.1 抽簽原理

基于VRF的密碼學(xué)抽簽算法用于根據(jù)每個(gè)用戶的權(quán)重蓖捶，隨機(jī)選出用戶的一個(gè)子集。整個(gè)抽簽過程中扁远，需要保證：

不存在上帝角色操縱整個(gè)抽簽俊鱼；

每個(gè)參與者獨(dú)立做自己的抽簽，在主動(dòng)公布自己的抽簽結(jié)果之前畅买，其他任何人都不可能知道該抽簽結(jié)果并闲；

參與者公布自己的抽簽結(jié)果后，系統(tǒng)中的其他參與者都可以驗(yàn)證該結(jié)果谷羞，參與者不需要泄漏自己的私鑰帝火；

在一輪抽簽開始之前，任何參與者都不能預(yù)先計(jì)算自己的抽簽結(jié)果湃缎；

抽簽對(duì)所有參與者都是公平公正的犀填；

防女巫攻擊。

具體做法就是嗓违，假設(shè)參與者

i

i 的權(quán)重是

w

i

w

i

?

九巡，所有參與者的權(quán)重總和

W

=

∑

i

w

i

W=∑

i

?

w

i

?

，對(duì)于具體的抽簽?zāi)康孽寮荆覀冊(cè)O(shè)置一個(gè)期望值

t

t冕广，表示在所有的權(quán)重當(dāng)中，希望抽出

t

t份權(quán)重偿洁。這樣撒汉，我們基于“伯努利試驗(yàn)”的抽簽方式，按

p

=

t

W

p=

W

t

?

? 的概率涕滋，讓每個(gè)參與者

i

i 依據(jù)自己的權(quán)重

w

i

w

i

?

做

w

i

w

i

?

次抽簽睬辐，這樣所有參與者就總共做了

W

W次抽簽，抽簽結(jié)果將是符合二項(xiàng)分布的何吝。

接下來溉委，需要做的就是構(gòu)造這個(gè)“伯努利試驗(yàn)”，這就用到了VRF爱榕。首先瓣喊，要求每個(gè)參與者都擁有一對(duì)公私鑰，

(

p

k

i

,

s

k

i

)

(pk

i

?

,sk

i

?

)黔酥，然后藻三，為了滿足前面提到的要求洪橘，還需要定義一個(gè)種子seed，以及標(biāo)識(shí)抽簽階段的一些數(shù)據(jù)棵帽，比如round熄求。其中，需要盡可能讓參與者在開始某一輪抽簽的時(shí)候逗概，才知道所用到的seed弟晚，這個(gè)根據(jù)具體的應(yīng)用場(chǎng)景來定。

這時(shí)逾苫，就可以基于VRF構(gòu)建我們的“伯努利試驗(yàn)”了卿城。

設(shè) x 是由seed、round等組成的抽簽參數(shù)铅搓，則參與者先計(jì)算 x 的VRF哈希及證明：

h

a

s

h

,

p

i

=

V

R

F

s

k

i

(

x

)

hash,pi=VRF

sk

i

?

?

(x) 瑟押。這時(shí)得到的哈希的長(zhǎng)度是固定的，比如32字節(jié)星掰，由VRF的安全特性多望，我們知道hash是在區(qū)間

[

0

,

2

256

]

[0,2

256

]內(nèi)均勻分布的，將該哈希值變?yōu)橐粋€(gè)小數(shù)氢烘，即

d

=

h

a

s

h

2

256

d=

2

256

hash

?

怀偷，這時(shí)

d

d 就在區(qū)間

[

0

,

1

]

[0,1] 之間均勻分布。

另外威始，已知以概率 p 做 n 次伯努利試驗(yàn)枢纠，實(shí)際成功次數(shù)為 k 次的概率，計(jì)算公式如下：

(

n

k

)

p

k

(

1

?

p

)

n

?

k

(

k

n

?

)p

k

(1?p)

n?k

將 k=0...j 所對(duì)應(yīng)的概率加起來黎棠，假設(shè)用 Sum(j) 表示晋渺，我們找到一個(gè)j值，使其滿足式子

S

u

m

(

j

)

≤

d

<

S

u

m

(

j

+

1

)

Sum(j)≤d<Sum(j+1) 脓斩，這時(shí)木西，

j

j 就是參與者的抽簽結(jié)果了。

j

=

0

j=0時(shí)表示沒抽中随静，

j

>

0

j>0時(shí)表示抽中了

j

j份權(quán)重八千。

由于用戶的權(quán)重越大，即w越大燎猛，其抽簽次數(shù)就越多恋捆，從而基于相同的概率p，得到

j

>

0

j>0 的概率也就會(huì)越大重绷，因此沸停，用戶被選中的概率是跟他們的權(quán)重是成比例的。另外昭卓，當(dāng)

j

>

0

j>0愤钾，我們可以想象成用戶有

j

j 個(gè)子用戶被抽中了瘟滨，如果是投票，就可以投

j

j票能颁。這樣一來杂瘸，w個(gè)權(quán)重為1的用戶，有j個(gè)被抽中的概率伙菊，跟1個(gè)權(quán)重為w的用戶败玉，有j個(gè)子用戶被抽中的概率，是一樣的占业。也就是說绒怨，這種抽簽是防女巫攻擊的。

最后谦疾，對(duì)于驗(yàn)證者來說，他可以基于VRF驗(yàn)證機(jī)制犬金，驗(yàn)證抽簽參與者的哈希及證明念恍，驗(yàn)證通過之后，執(zhí)行相同的抽簽計(jì)算晚顷，看結(jié)果

j

′

j

′

? 跟

j

j 是否一致峰伙。

2.1.2 抽簽算法

對(duì)應(yīng)前面的描述，抽簽算法如下：

VrfSortition

(

s

k

,

s

e

e

d

,

r

o

u

n

d

,

r

o

l

e

,

t

,

w

,

W

)

:

?

h

a

s

h

,

π

?

←

V

R

F

s

k

(

s

e

e

d

∥

r

o

l

e

∥

r

o

u

n

d

)

p

←

t

W

j

←

0

w

h

i

l

e

h

a

s

h

2

h

a

s

h

l

e

n

?

[

∑

k

=

0

j

B

(

k

;

w

,

p

)

,

∑

k

=

0

j

+

1

B

(

k

;

w

,

p

)

)

d

o

?

j

+

+

r

e

t

u

r

n

?

h

a

s

h

,

π

,

j

?

?

?

VrfSortition(sk,seed,round,role,t,w,W):

?hash,π?←VRF

sk

?

(seed∥role∥round)

p←

W

t

?

j←0

while

2

hashlen

hash

?

∈

/

?

[

k=0

∑

j

?

B(k;w,p),

k=0

∑

j+1

?

B(k;w,p)) do

? j++

return ?hash,π,j?

?

其中该默，

s

k

sk為用戶私鑰瞳氓，

r

o

l

e

role 參數(shù)和

r

o

u

n

d

round 參數(shù)用于區(qū)分共識(shí)過程中的角色與階段，一個(gè)閾值 t 用于確定本次抽簽所期望選中的用戶數(shù)栓袖。

h

a

s

h

,

π

hash,π 分別為VRF哈希值及證明匣摘。

3.2 抽簽驗(yàn)證算法

驗(yàn)證過程算法描述如下：

VrfVerifySortition

(

p

k

,

s

e

e

d

,

r

o

u

n

d

,

r

o

l

e

,

π

,

t

,

w

,

W

)

:

i

f

?

V

e

r

i

f

y

V

R

F

p

k

(

h

a

s

h

,

π

,

s

e

e

d

∥

r

o

l

e

∥

r

o

u

n

d

)

t

h

e

n

r

e

t

u

r

n

0

;

p

←

t

W

j

←

0

w

h

i

l

e

h

a

s

h

2

h

a

s

h

l

e

n

?

[

∑

k

=

0

j

B

(

k

;

w

,

p

)

,

∑

k

=

0

j

+

1

B

(

k

;

w

,

p

)

)

d

o

?

j

+

+

r

e

t

u

r

n

j

?

?

VrfVerifySortition(pk,seed,round,role,π,t,w,W):

if?VerifyVRF

pk

?

(hash,π,seed∥role∥round) then return 0;

p←

W

t

?

j←0

while

2

hashlen

hash

?

∈

/

?

[

k=0

∑

j

?

B(k;w,p),

k=0

∑

j+1

?

B(k;w,p)) do

? j++

return j

?

驗(yàn)證過程先驗(yàn)證

π

π 是否合法有效，然后依據(jù)與抽簽類似的過程獲得用戶被選中的子用戶數(shù)(0表示根本沒被抽中)裹刮，從而與用戶隨消息廣播出來的j值做比較以驗(yàn)證其正確性音榜。

2.2 抽簽結(jié)果的概率分布

根據(jù)前面的描述，我們知道整個(gè)VRF密碼學(xué)抽簽算法捧弃，是概率性的赠叼，概率符合二項(xiàng)分布。也就是說违霞，給定期望值 t 嘴办，實(shí)際結(jié)果 k 是不固定的。在這種情況下买鸽，密碼學(xué)抽簽怎么應(yīng)用與具體的場(chǎng)景涧郊，那就得具體情況具體分析了。

在這里癞谒，我們先看一下如何計(jì)算抽簽結(jié)果的概率分布底燎。 如果總權(quán)重 W 是比較小的刃榨，從而概率 p 是比較大的，那這時(shí)直接用二項(xiàng)分布公式進(jìn)行計(jì)算就可以了双仍。

但如果 W 很大枢希，那就要考慮別的方式了。 首先朱沃，再列一下二項(xiàng)分布概率公式（為了和Algorand保持一致苞轿，下面用 U 代替 W）：

(

U

K

)

p

K

(

1

?

p

)

U

?

K

(

K

U

?

)p

K

(1?p)

U?K

將其展開得如下式子：

U

!

K

!

(

U

?

K

)

!

(

t

U

)

K

(

1

?

t

U

)

U

?

K

=

U

…

(

U

?

K

+

1

)

U

K

t

K

K

!

(

1

?

t

U

)

U

?

K

K!(U?K)!

U!

?

(

U

t

?

)

K

(1?

U

t

?

)

U?K

=

U

K

U…(U?K+1)

?

?

K!

t

K

?

(1?

U

t

?

)

U?K

由于K是個(gè)比較小的值，當(dāng)U很大時(shí)逗物，下面的等式是可以接受的搬卒；或者換個(gè)方式說，當(dāng)U大到我們可以接受如下式子的時(shí)候翎卓，U就足夠大了：

U

…

(

U

?

K

+

1

)

U

K

=

1

U

K

U…(U?K+1)

?

=1

另外契邀，U足夠大時(shí)，我們肯定還能接受如下等式失暴。其中分子轉(zhuǎn)換成常數(shù)e的指數(shù)坯门，這是根據(jù)指數(shù)函數(shù)的定義來的。

(

1

?

t

U

)

U

?

K

=

(

1

?

t

U

)

U

(

1

?

t

U

)

K

=

e

?

t

1

=

e

?

t

(1?

U

t

?

)

U?K

=

(1?

U

t

?

)

K

(1?

U

t

?

)

U

?

=

1

e

?t

?

=e

?t

綜合起來就得到當(dāng)U很大逗扒，且期望為t時(shí)古戴，實(shí)際抽簽結(jié)果為K的概率為：

t

K

K

!

e

?

t

(1)

K!

t

K

?

e

?t

(1)

2.3 在區(qū)塊鏈中的應(yīng)用及要解決的問題

Algorand項(xiàng)目開創(chuàng)了密碼學(xué)抽簽算法在區(qū)塊鏈中的應(yīng)用，主要用在兩種場(chǎng)景下：（1）通過抽簽獲得區(qū)塊提議者矩肩；（2）通過抽簽獲得區(qū)塊驗(yàn)證委員會(huì)现恼。

對(duì)于第一種場(chǎng)景，期望值 t 應(yīng)該是比較小的黍檩，主要需要考慮的是叉袍，實(shí)際抽簽結(jié)果 k 應(yīng)該以很高的概率大于0，同時(shí)k又不應(yīng)該很大建炫。Algorand給出了一個(gè)值 t = 26畦韭，這時(shí)k在1到70之間的概率為：

∑

k

=

1

70

2

6

k

k

!

e

?

26

>

1

?

1

0

?

11

k=1

∑

70

?

?

k!

26

k

?

e

?26

>1?10

?11

對(duì)于第二種場(chǎng)景，就比較復(fù)雜了肛跌。除了單純抽簽概率上的考慮艺配，還要考慮網(wǎng)絡(luò)中惡意用戶或者說拜占庭節(jié)點(diǎn)的影響，以及投票通過的閾值衍慎。

根據(jù)Algorand的分析转唉，假設(shè)網(wǎng)絡(luò)中誠實(shí)用戶所占的權(quán)重比例為 h，委員會(huì)期望權(quán)重為 t 稳捆，由上面的公式（1）赠法，可以得到最終誠實(shí)權(quán)重為k的概率為：

(

h

t

)

K

K

!

e

?

h

t

(2)

K!

(ht)

K

?

e

?ht

(2)

在一個(gè)存在拜占庭節(jié)點(diǎn)的投票委員會(huì)中，設(shè)投票通過的閾值（比例）為 r（也就是說票數(shù)超過 t * r 就通過），則要保證系統(tǒng)的活性即能完成投票砖织，需要滿足下面的條件1：

條件1：

#

g

o

o

d

>

t

?

r

#good>t?r

>

#

g

o

o

d

#good 表示誠實(shí)票數(shù)

通過上面的概率公式款侵，這個(gè)條件不滿足的概率是可以計(jì)算出來的，不滿足的概率為:

∑

K

=

0

t

?

r

(

h

t

)

K

K

!

e

?

h

t

K=0

∑

t?r

?

?

K!

(ht)

K

?

e

?ht

另外侧纯，考慮拜占庭節(jié)點(diǎn)新锈，要保證系統(tǒng)的安全性，假設(shè) #bad 表示不誠實(shí)的票數(shù)眶熬，那么要保證安全性就要滿足下面的條件：

條件2：

1

2

#

g

o

o

d

+

#

b

a

d

≤

t

?

r

?

2

1

?

#good+#bad≤t?r

對(duì)于條件2妹笆，抽取 #good = K 并且 #bad = L 的概率如下：

(

h

t

)

K

K

!

e

?

h

t

(

(

1

?

h

)

t

)

L

L

!

e

?

(

1

?

h

)

t

K!

(ht)

K

?

e

?ht

?

L!

((1?h)t)

L

?

e

?(1?h)t

條件2不滿足的概率是不大好算的，實(shí)際評(píng)估時(shí)娜氏，我們可以先計(jì)算條件2滿足的概率宝恶，公式為:

∑

K

=

0

2

t

?

r

∑

L

=

0

2

?

t

?

r

?

K

2

(

h

t

)

K

K

!

e

?

h

t

(

(

1

?

h

)

t

)

L

L

!

e

?

(

1

?

h

)

t

K=0

∑

2t?r

?

?

L=0

∑

2

2?t?r?K

?

?

?

K!

(ht)

K

?

e

?ht

?

L!

((1?h)t)

L

?

e

?(1?h)t

用 1.0 減去計(jì)算結(jié)果衣吠，可得到條件2被違背的概率崩泡。 > 當(dāng)然弄息，先計(jì)算概率大的情況時(shí)，計(jì)算精度會(huì)降低绵疲。

上面兩個(gè)條件均不滿足的概率需要極小極小狸涌，才可以認(rèn)為不會(huì)影響系統(tǒng)的活性和安全性。舉個(gè)淺顯的例子就是：假設(shè)定下來 t = 100, r = 0.7, h = 0.8最岗。那么投票閾值就是70，但是由于抽簽結(jié)果的概率性朝捆，那么如果抽簽結(jié)果不足70般渡，那就完不成投票了，如果抽簽結(jié)果大于140芙盘，那在網(wǎng)絡(luò)不好的情況下是不是可能出現(xiàn)分歧（分叉）呢驯用？另外，由于總體誠實(shí)比例只有0.8儒老，那也有可能抽簽結(jié)果中不誠實(shí)數(shù)直接就超過70蝴乔，那也可能搞亂整個(gè)投票，這時(shí)驮樊，確切地說就是條件2的情況薇正。

綜上，理論上來說囚衔，活性和安全性都是無法絕對(duì)保障的挖腰，但是可以考慮一個(gè)很小的概率 F（如

F

=

1

0

?

18

F=10

?18

），當(dāng)兩個(gè)條件被違背的概率均小于F時(shí)练湿，我們可以認(rèn)為這樣的事件基本不會(huì)發(fā)生猴仑。

這個(gè) F 跟 t,r,h都有一定的負(fù)相關(guān)關(guān)系，就是t,r,h中任意兩個(gè)值不變的情況下肥哎，第三個(gè)值越大辽俗，F(xiàn)就越小疾渣。例如，r,h不變時(shí)崖飘，t越大榴捡，F(xiàn)越小。

還有一個(gè)問題坐漏，t也不是越大越好的薄疚。t很大時(shí)，雖然可以使F很小赊琳，但是在一個(gè)分布式網(wǎng)絡(luò)中街夭，t越大則完成投票所需要的通信量也就越大，所以這需要權(quán)衡考慮躏筏。

以上板丽，就是本文分享的所有內(nèi)容了。至于Algorand項(xiàng)目中是如何權(quán)衡相關(guān)問題的趁尼，敬請(qǐng)關(guān)注后續(xù)分享埃碱。

參考

Verifiable Random Functions

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/

[GMR88] Shafi Goldwasser, Silvio Micali, and Ronald L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM Journal on Computing, 17(2):281–308, April 1988.

[GMR89] Shafi Goldwasser, Silvio Micali, and Charles Rack- off. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186– 208, February 1989.

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- Scaling Byzantine Agreements for Cryptocurrencies