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

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

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

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

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

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

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

什么是 Schnorr 簽名？

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

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

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

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

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

這個(gè)定制過(guò)程可以簡(jiǎn)單的通過(guò)將 R ， X 和簽名信息進(jìn)行哈希來(lái)做到：

e ：= Hash（R， X， Message）

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

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

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

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

什么是聚合簽名？

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

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

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

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

對(duì)于 ECDSA 簽名算法，驗(yàn)證 n 個(gè)簽名，需要進(jìn)行 n 次取模和 2 * n 次點(diǎn)乘運(yùn)算。而對(duì)于 Schnorr 簽名，我們可以將驗(yàn)證方程相加：

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）

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

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

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

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

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

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

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

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

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

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

5. 允許每個(gè)簽名者簽署相同的消息

6. 允許每個(gè)簽名者簽署自己的消息

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

聚合簽名的使用

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

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

通過(guò)聚合簽名進(jìn)行一筆原子交換的簡(jiǎn)潔過(guò)程如下［10］：

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

2. Alice 所用的私鑰會(huì)是一次性的，因?yàn)樗枰獙⑦@個(gè)私鑰發(fā)送給 Bob

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

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

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

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

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

引入 Schnorr 和聚合簽名的影響

優(yōu)勢(shì)：

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

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

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

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

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

劣勢(shì)：

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