可驗證随機數VRF的一種實作

本文簡單分析一下ietf-vrf方案的實作原理。

所謂VRF就是指給定一個消息和一個私鑰，可以計算出一個唯一确定的值，這個值唯一确定且不可預測，且可以驗證。

傳統的簽名算法不具有唯一确定的特性，私鑰持有者可以計算出多個合法解。

前置技能樹：需了解橢圓曲線的基本運算法則。

1. 簡單的多項式:

t = ( r − s ∗ k )   m o d   p t = (r - s * k) \bmod p t=(r−s∗k)modp

這個等式就是普通的整數運算，

r

,

t

,

s

,

k

,

n

均為大整數，

p

為常量。

k

為私鑰,

r

為随機數，二者不可洩露。

2. 橢圓曲線上的多項式

把上面的等式和橢圓曲線的基點 G G G相乘，可以得到下面的等式:

T = t ∗ G = ( r − s ∗ k ) ∗ G = r ∗ G − s ∗ k ∗ G = R − s ∗ K \begin{aligned} T &= t*G \\ &= (r - s * k)*G \\ &= r*G - s*k*G \\ &= R-s*K \end{aligned} T​=t∗G=(r−s∗k)∗G=r∗G−s∗k∗G=R−s∗K​

小寫字母為整數，對應的大寫字母為該整數映射到曲線上的點

當選取不同的基點 G x G_x Gx​時, 等式也依然成立:

T x = t ∗ G x = ( r − s ∗ k ) ∗ G x = r ∗ G x − s ∗ k ∗ G x = R x − s ∗ K x \begin{aligned} T_x &= t*G_x \\ &= (r-s*k)*G_x \\ &= r*G_x - s*k*G_x \\ &= R_x - s*K_x \end{aligned} Tx​​=t∗Gx​=(r−s∗k)∗Gx​=r∗Gx​−s∗k∗Gx​=Rx​−s∗Kx​​

3. 多項式的執行個體化

随機選取兩個不同的基點 G 1 G_1 G1​, G 2 G_2 G2​，則:

T 1 = R 1 − s ∗ K 1 T 2 = R 2 − s ∗ K 2 T_1 = R_1 - s*K_1 \\ T_2 = R_2 - s*K_2 T1​=R1​−s∗K1​T2​=R2​−s∗K2​

回到起始的多項式 t = ( r − s ∗ k )   m o d   p t = (r - s * k) \bmod p t=(r−s∗k)modp，

k

為私鑰，

r

為随機數, 則隻需确定

s

，就可以計算出

t

。

定義哈希函數 H 2 H_2 H2​，用于計算

s

:

s = H 2 ( G 1 , G 2 , K 1 , K 2 , R 1 , R 2 ) s=H_2(G_1,G_2,K_1,K_2,R_1,R_2) s=H2​(G1​,G2​,K1​,K2​,R1​,R2​)

現在

t

的值确定了，我們構造出了一組數字，它們滿足上述的多項式，而且系數之間有着苛刻的限制。

公開除了

k

,

r

之外的所有參數，則任何人都可以驗證這組數字的有效性，并且其他的人幾乎無法給出其他的有效解。

公開

t

,

s

, G 1 G_1 G1​, G 2 G_2 G2​, K 1 K_1 K1​, K 2 K_2 K2​即可，其餘參數均可推導出。

4. 應用到VRF

回到基點 G x G_x Gx​的選擇，令:

G 1 = G G 2 = H 1 ( M ) G_1=G \\ G_2=H_1(M) G1​=GG2​=H1​(M)

其中 G G G為約定好的基點，

M

為任意消息， H 1 H_1 H1​為哈希函數，負責将

M

編碼成曲線上的點。

對于任意消息

M

和私鑰

k

，總能計算出一組數字，滿足上述的多項式。

當選擇不同的

r

時，

t

,

s

是不同的，但其餘的值是固定的，比如 K 2 K_2 K2​，而且 K 2 K_2 K2​的值隻由

k

,

M

決定，是以 K 2 K_2 K2​就是

VRF

輸出的"确定的不可預測的可驗證的随機數"。

相關連結:

• google的實作
• Spectrum的實作
• IETF草案