schnorr簽名算法相比ECDSA具有哪些優(yōu)勢

當(dāng)我們研究比特幣 ECDSA 橢圓曲線簽名算法時，就會發(fā)現(xiàn)多重簽名交易驗證過程非常繁瑣，有沒有設(shè)想過把一筆交易中的所有簽名和公鑰通通合并成單個簽名和公鑰，無法追溯并且簡單快速？

20世紀(jì)80年代，德國密碼學(xué)家 Claus-Peter Schnorr 給出了答案。以他命名的 Schnorr 簽名算法可以構(gòu)建更高效和隱私性更強的區(qū)塊鏈系統(tǒng)，一直備受區(qū)塊鏈開發(fā)者們的關(guān)注。 2018年7月，比特幣開發(fā)者 Pieter Wuille 撰寫了 bip-schnorr［2］ 提出了將 bitcoin 的簽名算法更改為 schnorr 方案。Schnorr 與 ECDSA 雖然同為使用 secp236k1［3］ 曲線的橢圓曲線加密算法，但相比 Schnorr 來說，ECDSA 有一些不足之處：

1. 證明安全性：在隨機預(yù)言模型中很容易證明 Schnorr 簽名的安全性，而 ECDSA 不存在這樣的證明。

2. 不可延展性：ECDSA 簽名具有可塑性，不知曉私鑰的第三方可以將給定公鑰和消息的現(xiàn)有有效簽名更改為對同一私鑰和消息的另一個有效簽名，這一問題直到 SegWit 激活后才得以修復(fù)。BIP62［4］ 和 BIP66［5］ 中討論了此問題。而如果使用 Schnorr 簽名則可以避免類似的情況出現(xiàn)［6］。

3. 線性：Schnorr 簽名是線性的，這一點非常重要。使用 Schnorr 簽名的各方可以生成對其各自密鑰的簽名聚合。以這一特性作為基礎(chǔ)，可以構(gòu)建更高效和隱私性更強的區(qū)塊鏈系統(tǒng)。

schnorr 簽名算法相比 ECDSA 來講，對于上述的優(yōu)點，除了尚未標(biāo)準(zhǔn)化之外幾乎沒有缺點。而且由于兩種算法都基于同一個橢圓曲線，整個關(guān)于簽名的升級成本也是很低的。

什么是 Schnorr 簽名？

在密碼學(xué)中，Schnorr 簽名是由 Schnorr 簽名算法產(chǎn)生的數(shù)字簽名。它是一種數(shù)字簽名方案，以其簡單高效著稱，其安全性基于某些離散對數(shù)問題的難處理性。［7］ Schnorr 的原理描述如下：

下面用小寫字母表示數(shù)字，比如：a = 42。同時我們將使用一些橢圓曲線（elliptic curve）上的點。這些點是一些滿足橢圓曲線方程的大數(shù)對。我們將用大寫字母來表示這些點，比如：A = （4， 68）。橢圓曲線上的點可進行一些代數(shù)運算。其上兩個點可以相加可以得到近似隨機的第三個點，表示為：C = A + B。某個點可以與自身相加多次：D = C + C + C。當(dāng)我們講一個點與自身相加多次時，我們稱其為“乘以一個數(shù)”：D = 3 * C。顯而易見的，如果將一個點 A 與自身相加很多次（或者說將其乘以一個很大的數(shù)）然后得到一個點 B ，如果我們只是知道原始點 A 和結(jié)果點 B ，計算出與 A 相乘的這個大數(shù)是相當(dāng)困難的。這里的“困難”意思是，如果要計算出這個“大數(shù)”，我們不能簡單的用 B 除以 A ，只能不斷的猜測一個值 x ，計算是否 x * A等于 B 。所以如果這個 x 的值非常大，甚至大于宇宙中所有原子數(shù)目的和，猜測這個 x 的值將花費一個難以接受的時間。同時如果某人持有正確的 x ，計算 x * A 是非常迅速的。這種非對稱性將作為我們討論的前提。

Alice 持有私鑰 x ，然后選擇一個隨機數(shù) r ，以及橢圓曲線上的原點 G ，計算出R ：= r * G，公鑰X ：= x * G，使用哈希函數(shù)獲取一個隨機的用于驗證的數(shù)字e ：= Hash（R， X， message），然后計算 s ：= e * x + r。

Alice 給 Bob 發(fā)送點 R， X， message ，和點數(shù)值 s ，Bob 驗證 s * G 等于 R + e * X 。事實上，不僅是 Bob，這個世界上的任何人都可以獨自對這一證明進行驗證。一旦s * G = R + e * X通過了驗證，既可以證明 Alice 持有私鑰 x，并生成了一個合法的簽名：（s， e）。

最終，如果要將簽名從這一證明中創(chuàng)造出來，Alice 需要定制一個哈希函數(shù)來對她簽名的消息的進行哈希計算。這樣的話需要確定針對一個消息所計算出的簽名，不能被復(fù)用給另外一個消息。

這個定制過程可以簡單的通過將 R ， X 和簽名信息進行哈希來做到：

e ：= Hash（R， X， Message）

一個良好的哈希函數(shù)，會在哪怕僅有一個字符有更改的情況下，也會返回完全不同的哈希值，使得計算出 s 的值是不可能的任務(wù)

Schnorr 簽名協(xié)議的簡潔描述如下：

Setup：

x ：= random number （aka private key）

G ：= common point

X ：= x * G （aka public key）

Sign：

r ：= random number （aka nonce）

R ：= r * G （aka commitment）

e ：= Hash（R， X， message）（aka challenge）

s ：= r + e * x （aka response）

return （R， X， s， message） （（s， e） aka signature）

Verify：

receive （R， X， s， message）

e ：= Hash（R， X， message）

S1 ：= R + e * X

S2 ：= s * G

return OK if S1 qeuals S2

基于此，開發(fā)者在未來可以添加更復(fù)雜的概念，比如聚合簽名。聚合簽名優(yōu)勢就在于將一筆交易中所有涉及的輸入只需要一個合并簽名就可以完成，大大減少了數(shù)據(jù)處理量，使網(wǎng)絡(luò)速度更快，更加高效。

什么是聚合簽名？

聚合簽名是使用 Schnorr 簽名的各方生成的對各自密鑰的簽名聚合，它可以把一筆多簽交易的各個參與方的公鑰和簽名合并為一個公鑰與簽名，整個合并過程是不可見的，無法從合并后的公鑰與簽名推導(dǎo)出合并前的信息，并且在驗證時僅需一次驗證即可。目前 ，Mimblewimble 已利用 Schnorr 簽名算法實現(xiàn)簽名聚合。

在使用 ECDSA 進行多簽的情況下，如果共有 N 個私鑰進行了簽名，則驗證時需要對 N 個簽名各自進行驗證。由于 Schnorr 簽名算法的線形特性，在同樣的情況下，N 個私鑰的簽名可以「聚合」成為一個簽名，原理如下：

由于橢圓曲線上的點可以滿足乘法結(jié)合律，因此對于橢圓曲線上的兩個點 X，Y 和相應(yīng)的標(biāo)量（私鑰）x，y 以及原點 G，則：

X + Y = x * G + y * G = （x + y） * G

對于 ECDSA 簽名算法，驗證 n 個簽名，需要進行 n 次取模和 2 * n 次點乘運算。而對于 Schnorr 簽名，我們可以將驗證方程相加：

S1 = sum（s）（i） = s1 * G + s2 * G + 。.. + sn * G = （s1 + s2 + 。.. + sn） * G

S2 = sum（R + e*X）（i） = （R1 + e1 * X1） + （R2 + e2 * X2） + 。.. + （Rn + en * Xn） = sum（R1， R2， 。..， Rn） + （e1 * X1 + e2 * X2 + 。.. + en * Xn）

此時對 Schnorr 簽名算法生成的多簽進行驗證時，只需要進行 2n 次加法運算和 n + 1 次點乘運算即可。由于加法運算所占用的資源是極低的，兩種多簽驗證方式的資源消耗可以近似的比較為：ECDSA 為一次取模加兩次點乘，Schnorr 為一次點乘的資源消耗。顯而易見的結(jié)論是，使用 Schnorr 簽名算法所消耗的資源更少。

對于上述多重簽名的情況，使用 Schnorr 簽名算法進行聚合簽名，可以提供如下額外的好處：

· 性能方面：可以大大減少驗證簽名的成本。Schonrr 簽名算法的優(yōu)勢是顯而易見的，對于一筆多簽交易，原本需要進行多次的驗證，而聚合簽名僅需驗證一次，從而提升節(jié)點對于交易的驗證速度

· 交易體積：由于將多個簽名聚合為一個簽名，可以大大減少多重簽名的大小，并且可以顯著降低對于網(wǎng)絡(luò)傳輸消耗的帶寬，以及對于節(jié)點存儲空間的占用

· 隱私：使用 Schnorr 聚合簽名可以提高鏈上數(shù)據(jù)的隱私性。對于驗證者來講，聚合簽名看起來和普通的 Schnorr 簽名并無區(qū)別，無法分辨這一筆交易是普通的交易還是一筆多簽交易，而參與交易的用戶的公鑰和簽名都不會暴露出來

在創(chuàng)建一個基于 Schnorr 聚合簽名的多簽方案時，為保證多簽的簽名看起來像單密鑰簽名，并且使傳統(tǒng)的驗證方法有效并且保證整個過程只需要線性次簽名聚合，該方案需要滿足如下的特性：

1. 在普通的公鑰模型中被證明是安全的

2. 滿足 Schnorr 方程，從而可以將得到的簽名寫成公鑰組合的函數(shù)

3. 允許簽名者需要合作的交互式聚合簽名（IAS）

4. 允許非交互式聚合簽名（NAS），其中聚合可以由任何人完成

5. 允許每個簽名者簽署相同的消息

6. 允許每個簽名者簽署自己的消息

基于 Schnorr 的聚合簽名方案目前有多種實現(xiàn)，最終 Blockstream 給出的方案是 MuSig，各個實現(xiàn)方式的區(qū)別以及 MuSig 的具體原理可以參照引用［8］［9］。

聚合簽名的使用

7月10日，Qtum量子鏈基金會宣布實現(xiàn)QTUM-BEAM原子交換（Atomic Swap），原子交換（Atomic Swap）允許兩個獨立鏈上進行原子性的跨鏈交易。（鏈接：Qtum量子鏈實現(xiàn)QTUM-BEAM原子交換，支持隱私跨鏈交易|附實驗步驟詳解）

而通過聚合簽名，可以安全又簡單的實現(xiàn)原子交換。聚合簽名本質(zhì)是一個簽名的偏移量，一旦與真實的簽名進行組合，即可計算出簽名所用的私鑰。聚合簽名的可信度可以進行驗證，同時又無需暴露任何信息。聚合簽名可以保證原子交換的原子性，又可以保證交易雙方的安全。

通過聚合簽名進行一筆原子交換的簡潔過程如下［10］：

1. Alice 和 Bob 將加密貨幣分別存入兩個各自簽名的地址之中

2. Alice 所用的私鑰會是一次性的，因為她需要將這個私鑰發(fā)送給 Bob

3. Alice 向 Bob 提供一個聚合簽名，這個簽名需要經(jīng)過 Bob 的確認(rèn)

4. 當(dāng) Alice 廣播她的簽名來證明她持有的加密貨幣時，Bob 可以獲得足夠的信息計算出 Alice 的私鑰并獲得她持有的加密貨幣

5. Bob 簽署一筆交易發(fā)送加密貨幣給 Alice

6. Alice 使用另一半私鑰對接收加密貨幣的交易進行簽名并將其廣播

7. Bob 獲知全部的私鑰并收到 Alice 持有的加密貨幣，同時 Alice 也將獲得 Bob 的貨幣

引入 Schnorr 和聚合簽名的影響

優(yōu)勢：

· 節(jié)省數(shù)據(jù)：簽名聚合可在區(qū)塊鏈上提供數(shù)據(jù)壓縮

· 隱私：除交易結(jié)算外，關(guān)于無腳本智能合約的任何東西都不會記錄在區(qū)塊鏈上（簽名聚合過程發(fā)生在鏈下）

· 多重性：可在單個交易結(jié)算中在雙方之間轉(zhuǎn)移多種資產(chǎn)（跨鏈原子交換）

· 隱式可伸縮性：區(qū)塊鏈的可伸縮性是通過將多個交易壓縮到單個結(jié)算事務(wù)中實現(xiàn)的。只有滿足所有先決條件后，交易才會被廣播

· 結(jié)合聚合簽名的 Scriptless script 相比標(biāo)準(zhǔn)智能合約具有更好的擴展性。因其合約執(zhí)行是發(fā)生在鏈下的，通過將此執(zhí)行結(jié)果推送給關(guān)心它的人，公共計算資源可以減輕存儲合約數(shù)據(jù)和執(zhí)行條件的負(fù)擔(dān)。非公開的合約也可以提供更好的隱私性。合約的詳情只有參與者可以知曉，對于其他人來說，該筆交易與普通的交易并沒有什么區(qū)別

劣勢：

Maxwell 等人的工作指出［11］，滿足密鑰聚合的 Schnorr 多重簽名的簡單實現(xiàn)并不是安全的。在普通的公鑰模型中，如使用 BN Schnorr 的簽名方案，需要通過放棄密鑰聚合的屬性來獲得安全性。他們提出了一個新的基于 Schnorr 的多簽?zāi)Ｐ?，叫?MuSig，以在普通的公鑰模型中可使用密鑰聚合，并具備應(yīng)有的安全性。其與標(biāo)準(zhǔn)的 Schnorr 簽名具有相同的密鑰和簽名大小。對于單個「聚合」公鑰可以通過與標(biāo)準(zhǔn) Schnorr 簽名相同的方式進行驗證（通過簽名者各自的公鑰進行計算得出證明）。