BLS簽名演算法

• 2022 年 10 月 10 日
• 筆記
• 密碼學複習

前言

  [失蹤人口回歸 (*/ω＼*)] 真的好久好久沒有更新了，因為自己也還在找方向，但還是把新學的知識記錄在部落格里。今天要介紹的是BLS簽名演算法。

一、BLS簽名演算法簡介

  BLS簽名演算法[1]是由斯坦福大學的 Dan Boneh、Ben Lynn 和 Hovav Shacham一同提出的。

  一般將 ECDSA簽名演算法、Schnorr簽名演算法和BLS進行對比。

  ECDSA簽名演算法局限性：

  無法進行簽名聚合和密鑰聚合。換句話說，當我們驗證多重簽名交易的時候，我們只能逐個對簽名進行驗證，顯然這會耗費大量的區塊空間和交易費。因此並不適用於多重簽名場景。

  Schnorr簽名演算法：

  可以將一筆交易中的所有簽名和公鑰合併成單個簽名和公鑰，其過程是不可見的（即無法判斷該簽名或公鑰是否通過合併得到的）。這樣就可以實現只需要一次就可以對合併後的簽名做驗證，加快了區塊驗證的速度。

  但其仍然存在著局限性：

• 多重簽名需要多次（簽名者之間的）通訊，這對冷錢包來說過於麻煩；
• 聚合簽名演算法依賴隨機數生成器，而不像 ECDSA 那樣可以使用指定的隨機點（R）；
•  m-n 多重簽名機制比較取巧，需要構建公鑰的默克爾樹。當 m 和 n 較大時，樹所佔空間會相當大；
• 無法把一個區塊中的所有簽名聚合成一個簽名。

  與這兩個簽名演算法作比較，BLS有如下優點：

  （1）不需要隨機數生成器，可以將區塊中的所有簽名聚合成一個；

  （2）容易實現 m-n 多重簽名，也可以避免簽名者之間的多餘通訊；

  （3）簽名的長度更短（簽名為橢圓曲線上的一個點而非兩個），是 Schnorr 或 ECDSA 的 2 分之一。

二、基礎知識

  在對BLS演算法進行闡述之前，首先了解一下曲線哈希和曲線配對。

2.1 曲線哈希

  Hashing to the curve 一般可以翻譯為曲線哈希或者是哈希成曲線上的點。沒了解之前聽到曲線哈希可能會不知道是啥，但聽到哈希成曲線上的點就大概知道意思了。

  在一般的哈希計算中，常常是對於不定長的輸入最終輸出一個定長的數值。但曲線哈希就不一樣，其輸出結果會對應到橢圓曲線上的一個點。

  具體做法如下：

  哈希函數保持不變，將得到的哈希值作為點的 x 值尋找橢圓曲線上的對應點。

  通常來說（比如比特幣所用的曲線），橢圓曲線有 2²⁵⁶ 個點，而 SHA-256 哈希演算法的值是 256 位。不過，一個有效的 x 坐標，會對應一正一負兩個 y 坐標（因為（x, y）和（x, -y）都是曲線y²=x³+ax+b上的點）。換句話說，新的哈希演算法大約有 50% 的概率在曲線上找到 2 個對應點，另 50% 的概率則一個點也找不到。因此，在應用過程中會出現需要嘗試多次才能找到對應點的情況。

  · 有兩個對應點怎麼解決呢？

  選擇y坐標較小的作為結果即可。

  · 那出現找不到對應點的情況怎麼辦呢？

  可以在消息體後面附加一個數。當找不到對應點的時候，將該數加一再重新計算直到找到對應的點。

  下面給出一個例子。

  以在模為 23 的有限域上定義的橢圓曲線 y²=x³+7為例。只有一半的 x 坐標在曲線上能找到對應點。

  ① 計算 hash(m||0)，沒有對應的點。

  ② 計算 hash(m||1)，沒有對應的點。

  ③ 計算 hash(m||2)，發現對應的點。對應的點有兩個，選擇y坐標較小的作為結果。

2.2 曲線配對

  在曲線哈希中，我們將輸入（一個值）映射到一個橢圓曲線上的點。顯然，我們還需要能將點映射為數的函數。下面介紹一種特殊的函數，這種函數能夠把一條（或 2 條不同的）曲線上的兩個點 P 和 Q映射為一個數：

e ( P , Q ) → n

  此函數還要有一個重要的特性。即對於未知數 x 和兩個點 P 、 Q ，無論哪個點乘以 x，結果相同，即：

e ( xP , Q ) = e ( P , xQ )

  該函數還有如下性質：

e ( aP , bQ ) = e ( P , abQ ) = e ( abP , Q ) = e ( bP , aQ ) = e ( P , Q ) ^ab

  這裡就不對該函數的原理進行詳細介紹，裡面涉及到許多數學原理。但不出意外的話，我後面會更新一篇關於配對（pairings）的理論，感興趣的話可以關注一下。

  現在就只需要知道這種函數是存在的，並且它們有上面介紹的性質。除此之外，它並不會暴露x的任何資訊。

  值得注意的是，配對函數中不能使用任何橢圓曲線（特別是比特幣的 secp256k1 橢圓曲線）。我們必須使用非常特殊的曲線（通常出自易於配對的曲線簇），才能保證函數的效率和安全。

三、BLS簽名方案

  現在終於能進入正題啦！

  下面用 pk 表示私鑰， P 表示公鑰， m 表示待簽名的消息。其中 P = pk×G.

3.1 簽名

  ① 對消息m 進行曲線哈希得到H(m).

  ② 使用私鑰進行簽名。將剛剛得到的結果乘以私鑰。

S = pk × H(m)

3.2 驗證簽名

  在驗證簽名的時候，使用公鑰 P 進行驗證。驗證過程如下：

e ( P , H(m) ) = e ( G , S ) 

3.3 原理

  下面證明 e ( P , H(m) ) = e ( G , S ) 該等式成立。

  已知：P = pk×G ，e ( xP , Q ) = e ( P , xQ ) .

e ( P , H(m) ) = e (  pk ×  G, H(m) ) =  e (  G , pk × H(m) ) = e (  G ,  S )

  下圖能夠很直觀的表示。BLS 簽名驗證，我們只需驗證 公鑰和消息的哈希值（曲線上兩個點）與曲線生成點和簽名（曲線上另兩個點）是否映射到同一個數（若是則說明這是一個有效的 BLS 簽名）。

四、簽名聚合

  前面提到BLS簽名演算法可以實現簽名聚合，下面就來介紹這個非常棒的特性。

  現在假設在區塊鏈的場景下，有一個區塊有1000筆交易，每筆交易都由 簽名S_i、公鑰P_i 和 消息m_i 組成。現在我們只關心區塊中所有的簽名（而不是每一個）是否正確。為獲得聚合簽名，只需要將區塊中的所有簽名加起來：

S=S₁+S₂+…+S₁₀₀₀

  為了驗證該區塊是否正確，要保證下面這個等式成立。

 e ( G , S ) =  e ( P₁ , H(m₁) ) × e ( P₂ , H(m₂) ) × … × e ( P₁₀₀₀ , H(m₁₀₀₀) ) 

  如果簽名是有效的，那麼該等式是成立的。證明如下：（這裡我直接放word里的截圖）

  這裡我們仍需用到所有的公鑰，並計算 1001 次配對函數，好處是，區塊中的簽名只佔 33 位元組了。簽名聚合可以由礦工在挖礦時完成，節省大量的區塊空間。

4.1 n-n多重簽名

  使用多重簽名的地址時，我們會對同一筆交易用不同的密鑰進行簽名。這種情況下，可以和 Schnorr 演算法一樣使用聚合密鑰，把所有密鑰和簽名聚合成單個公鑰和簽名。

  下面我們以 3-3 多重簽名方案為例（同理可推導任意數量的多重簽名方案）。一種簡單的聚合方法，是把所有的簽名和密鑰加起來即可。即：

  和 Schnorr 一樣，我們也需要杜絕偽造密鑰攻擊。一種方法是要求每個簽名參與者證明它擁有公鑰對應的私鑰（用私鑰給公鑰簽名）。另一種方法是加入非線性係數，使得攻擊無法實施。要做到這一點，聚合不再是簡單的將多個密鑰和簽名相加，而是將它們分別乘以某個係數後再相加：

S = a₁ × S₁ + a₂ × S₂ + a₃ × S₃

P = a₁ × P₁ + a₂ × P₂ + a₃ × P₃

  公式中籤名和密鑰的係數，可以通過簽名者以及其它所有人的公鑰計算得出，公式如下：

a_i = hash (P_i, {P₁, P₂, P₃})

 

  舉個例子，可以簡單的將簽名者的公鑰和所有人公鑰拼接在一起算出係數：

 

a_i = hash (P_i || P₁|| P₂ || P₃)

  此時，上面的驗證公式依然成立。雖然多了係數a_i，但計算邏輯未變。

  該方案的好處是，無需在設備間進行多輪通訊，只需知曉其它簽名者的相應資訊即可。它可比 Schnorr 演算法（需要 3 輪通訊）的多重簽名方案簡單多了。這個方案也不依賴隨機性，是一種具有完全確定性的簽名演算法。

4.2 m-n多重簽名

  上面對n-n多重簽名進行了介紹，但實際中其實並不是很常見，更常用的是m-n多重簽名。

  Schnorr 簽名演算法中，我們用公鑰組成的默克爾樹來實現密鑰聚合，這種方式效率不高，但是將將堪用。不幸地是，當 m 和 n 的值變大時，默克爾樹的大小會呈指數增長。

  BLS 使用了另一種方法，不過略複雜。我們需要一個普通哈希函數hash(x)（結果為一個數）和一個曲線哈希函數H(x)。開始多重簽名時，還需要一個初始化過程，這之後，簽名者之間就不再需要通訊了，只需提供交易簽名即可。

  下面舉個例子，我們要創建一個 2-3 多重簽名，3 個簽名存儲在不同的設備上（這個例子可以擴展為任意的 m-n 多重簽名）。

  （1）生成成員密鑰

  用 i = 1,2,3 來表示集合中相應位置的設備，用pk_i表示私鑰，用P_i = pk_i×G表示公鑰。我們用前面說的方法來聚合公鑰：

P = a₁ × P₁ + a₂ × P₂ + a₃ × P₃

  其中，a_i = hash (P_i, {P₁, P₂, P₃}) .

  現在，每個設備都需要對每個i簽名，以證明該i是聚合公鑰中的一員。將簽名聚合後，保存在對應的設備中：

MK_i = (a₁ × pk₁) × H( P , i ) + (a₂ × pk₂) × H( P , i ) + (a₃ × pk₃) × H( P , i ) 

  這個簽名被稱作「成員密鑰」，稍後簽名時我們會用到。每個成員密鑰都是對消息體H( P , i ) 的 n-n 多重簽名，即：

e (G, MK_i) = e (P, H(P , i) )

  證明如下：

  記住這個等式，稍後還會用到。它用來證明某個設備是多重簽名中的合法參與者。

  （2）簽名

  假設現在用pk₁和 pk₃對交易進行簽名，會生成兩個簽名S₁和S₃：

S₁ = pk₁ × H(P,m) + MK₁

S₃ = pk₃ × H(P,m) + MK₃

  將它們加起來，聚合成單一的簽名和公鑰：

(S’, P’) = (S₁+S₃, P₁+P₃)

  用P’和S’, 是為了強調它們只是由部分簽名者參與計算的（公鑰和簽名），而不像 P 那樣是由所有簽名者參與計算的（公鑰）。為了驗證 2-3 多重簽名，需證明如下等式成立：

e(G,S’) = e(P’,H(P,m)) × e(P,H(P,1)+H(P,3))

  上面說過，成員密鑰 MK₁ 和   MK₃ 是對消息 H(P,1) 和  H(P,3)（消息本身由聚合公鑰P簽名）的簽名，所以有：

  證明完畢。比 n-n 多重簽名複雜一些，但仍然可以理解。

五、缺點

  ① 配對函數並不是十分高效

  ② 存在一種針對橢圓曲線加密體系的攻擊-MOV攻擊。該攻擊能夠利用配對函數來危害系統安全。所以對配對函數的使用要十分謹慎。

參考文獻

[1] Boneh D , Lynn B , Shacham H . Short Signatures from the Weil Pairing[J]. Springer, Berlin, Heidelberg, 2001.

[2] 理解 BLS 簽名演算法