BLS簽名演演算法

前言

  [失蹤人口迴歸 (*/ω＼*)] 真的好久好久沒有更新了，因為自己也還在找方向，但還是把新學的知識記錄在部落格里。今天要介紹的是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座標較小的作為結果。

  和 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多重簽名