FISCO BCOS交易簽名算法基于ECDSA原理進(jìn)行設(shè)計(jì)，ECDSA也是比特幣和以太坊采用的交易簽名算法。

本文介紹ECDSA及橢圓曲線加密（ECC）相關(guān)知識(shí)、ECDSA的Recover機(jī)制和實(shí)現(xiàn)方式、FISCO BCOS交易簽名和驗(yàn)簽的底層原理。內(nèi)容偏硬（shu）核（xue），歡迎對(duì)密碼學(xué)原理、區(qū)塊鏈底層原理感興趣的開發(fā)者一起交流。

故事開始

故事要從以太坊中一個(gè)神奇的魔數(shù)開始說起。

以太坊黃皮書中，關(guān)于交易簽名的闡述講到兩個(gè)特殊的數(shù)「27，28」，實(shí)際上是從「0，1」通過加了一個(gè)27演變得到「27，28」，所以本質(zhì)上是一個(gè)特殊的數(shù)27。

這個(gè)特殊的數(shù)字27代表了什么含義呢？

一次偵探之旅開始了…

這像是一個(gè)bug

搜索發(fā)現(xiàn)此前已有許多關(guān)于該問題的討論，其中，Stack Exchange的一篇帖子指出這是一個(gè)設(shè)計(jì)bug。以太坊源碼github上，也有一個(gè)相關(guān)issue，該issue被打上了「type:bug」的標(biāo)簽。

Stack Exchange帖子中有一個(gè)鏈接給出了修復(fù)該Bug的代碼，請(qǐng)看下面截圖（紅框）。在注釋說明和代碼可見，fromRpcSig函數(shù)對(duì)27這個(gè)魔數(shù)進(jìn)行了特殊處理。從RPC過來的簽名中，v值如果小于27（可能是0-3），則直接加上27作為新v值，fromRpcSig函數(shù)通過這個(gè)方式兼容ECDSA原始v值（也就是recoveryID）和以太坊v值。

這真是以太坊設(shè)計(jì)的一個(gè)bug嗎？

回到剛才那個(gè)fromRpcSig的源代碼文件，詳細(xì)看其各接口實(shí)現(xiàn)，我們發(fā)現(xiàn)有這樣一行代碼「v: chainId ? recovery + (chainId * 2 + 35) : recovery + 27」，這行為v賦值的代碼透露了三個(gè)信息，分別是魔數(shù)27、魔數(shù)35和ChainID。

于是，疑問更多了，魔數(shù)35是什么？ChainID又是什么？

這不像是一個(gè)Bug

帶著這些疑問，再一次查閱相關(guān)設(shè)計(jì)材料，我們看到，以太坊EIP155中描述了有關(guān)ChainID的設(shè)計(jì)?；谝蕴辉创a構(gòu)建的網(wǎng)絡(luò)，實(shí)際運(yùn)行的鏈有很多，為了防止一條鏈的交易被提交上鏈到另一條鏈，造成重放攻擊，引入了ChainID的設(shè)計(jì)，在塊高2,675,000的位置進(jìn)行分叉實(shí)現(xiàn)。

明白了ChainID的作用，另一個(gè)疑問又產(chǎn)生了——以太坊中，有NetworkID來區(qū)分不同網(wǎng)絡(luò)，為什么還需要ChainID？

這要從NetworkID和ChainID的作用范圍來解釋。NetworkID主要在網(wǎng)絡(luò)層面進(jìn)行鏈的隔離，節(jié)點(diǎn)在建立相互連接的時(shí)候需要交換NetworkID，擁有一致的NetworkID才能完成握手連接。ChainID是交易層面，防止不同網(wǎng)絡(luò)的交易被交叉重復(fù)攻擊。

以太坊（ETH）和經(jīng)典以太坊（ETC）的主網(wǎng)NetworkID都是1，需要通過 ChainID機(jī)制才能防止交易在ETH和ETC網(wǎng)絡(luò)之間交叉重放，ETH主網(wǎng)的ChainID是1，ETC主網(wǎng)的ChainID是61。

說到這里其實(shí)還是沒有搞清楚為什么是27，為什么是35？我們?cè)贓IP github的Issue#155中看到Jan和Buterin的交流記錄，看來27是來自比特幣的產(chǎn)物。

順藤摸瓜，打開electrum的github，我們?cè)趀lectrum/electrum/ecc.py中找到如下代碼

從代碼中可見，electrum在簽名時(shí)，為原本只有0-3之間的recid（recoveryID）

加上了27，還有一個(gè)壓縮標(biāo)記，如果有壓縮則再加上4，recid的值范圍在27-34。

至此可知，27和35大概來源于此，以太坊繼承比特幣的設(shè)計(jì)，在比特幣源碼bitcoin/src/key.cpp的CKey::SignCompact函數(shù)中也確定了該實(shí)現(xiàn)方式，但是比特幣為什么如此設(shè)計(jì)，仍未可知。

ECDSA才是“bug”

故事到這里，我們對(duì)以太坊代碼中那個(gè)魔數(shù)27的前世今生有大概了解，但這僅僅是故事的開端，由此引發(fā)我們進(jìn)一步思考一個(gè)問題：recoveryID是什么？

為了解釋清楚這個(gè)問題，我們需要從ECDSA算法著手，從數(shù)學(xué)角度理解其背后的原理。ECDSA是FISCO BCOS采用的交易簽名算法，由此我們會(huì)發(fā)現(xiàn)，ECDSA算法有一種Recover機(jī)制，它才是真正“bug”級(jí)別的功能。

ECDSA（Elliptic Curve Digital Signature Algorithm）是基于橢圓曲線的數(shù)字簽名算法。數(shù)字簽名算法是采用公私鑰體系實(shí)現(xiàn)類似寫在紙上的普通簽名，用于鑒別數(shù)字信息的方法，常見的數(shù)字簽名算法包括DSA、RSA和ECDSA等。

橢圓曲線密碼（ECC）是基于橢圓曲線數(shù)學(xué)的公鑰加密算法，建立在橢圓曲線離散對(duì)數(shù)困難問題之上，常用的協(xié)議有ECDH、ECDSA和ECIES等。

橢圓曲線的參數(shù)可以有多種配置方式，也就存在多種不同的曲線，例如secp256k1、secp256r1、Curve25519等，不同曲線的安全性存在一些區(qū)別，在SafeCurves中有相關(guān)對(duì)比描述。

ECDSA算法主要包括以下四個(gè)關(guān)鍵功能：

產(chǎn)生密鑰GenKey

· 選擇一條橢圓曲線E_P(a,b)，選擇基點(diǎn)G，G的階數(shù)為n

· 選擇隨機(jī)數(shù)d ∈n為私鑰，計(jì)算公鑰Q = d?G

簽名算法Sign

· 對(duì)消息m使用消息摘要算法，得到z=hash(m)

· 生成隨機(jī)數(shù)k∈n，計(jì)算點(diǎn)(x, y)=k?G

· 取r=x mod n，若r=0則重新選擇隨機(jī)數(shù)k

· 計(jì)算s = k^?1(z+rd) mod n，若s=0則重新選擇隨機(jī)數(shù)k

· 上述(r,s)即為ECDSA簽名

驗(yàn)證算法Verify

使用公鑰Q和消息m，對(duì)簽名(r,s)進(jìn)行驗(yàn)證。

· 驗(yàn)證r,s∈n

· 計(jì)算z = hash(m)

· 計(jì)算u_1 =zs^?1 mod n和u_2 = rs^?1 mod n

· 計(jì)算(x, y) = u1?G+u2?Q mod n

· 判斷r == x，若相等則簽名驗(yàn)證成功

恢復(fù)算法Recover

已知消息m和簽名(r,s)，恢復(fù)計(jì)算出公鑰Q。

· 驗(yàn)證r, s∈n

· 計(jì)算R=(x, y)，其中x=r,r+n,r+2n...，代入橢圓曲線方程計(jì)算獲得R

· 計(jì)算z = hash(m)

· 計(jì)算u_1 = ?zr^?1 mod n和u_2 = sr^?1 mod n

· 計(jì)算公鑰Q= (x’, y’)=u_1?G+u_2?R

為了回答recoveryID的問題，我們重點(diǎn)關(guān)注「恢復(fù)算法Recover」。

在計(jì)算R的步驟可以看到，存在多個(gè)x的取值可能性，導(dǎo)致存在多個(gè)R的可能性，因此計(jì)算得到的Q也存在多個(gè)可能的結(jié)果，需要通過和已知的公鑰對(duì)比，確定哪一個(gè)Q是正確的。如果遍歷x的所有可能都未找到正確的Q，說明該消息和簽名是不對(duì)應(yīng)的，或者是一個(gè)未知的公鑰。

為了確定正確的Q，需要遍歷x的所有可能取值，跑多輪Recover算法，這個(gè)時(shí)間開銷是比較大的。為了提高Recover的時(shí)間效率，采用空間換時(shí)間的思路，在簽名中增加一個(gè)v值，用于快速確定x，避免遍歷查找試探，這個(gè)v值就是recoveryID。

在區(qū)塊鏈系統(tǒng)中，客戶端對(duì)每筆交易進(jìn)行簽名，節(jié)點(diǎn)對(duì)交易簽名進(jìn)行驗(yàn)證。

如果采用「驗(yàn)證算法Verify」，那節(jié)點(diǎn)必須首先知道簽發(fā)該交易所對(duì)應(yīng)的公鑰，因此需要在每筆交易中攜帶公鑰，這需要消耗很大帶寬和存儲(chǔ)。

如果采用「恢復(fù)算法Recover」，并且在生成的簽名中攜帶recoveryID，就可以快速恢復(fù)出簽發(fā)該交易對(duì)應(yīng)的公鑰，根據(jù)公鑰計(jì)算出用戶地址，然后在用戶地址空間執(zhí)行相應(yīng)操作。

這里潛藏了一個(gè)區(qū)塊鏈設(shè)計(jì)哲學(xué)，區(qū)塊鏈上的資源（資產(chǎn)、合約）都是歸屬某個(gè)用戶的，如果能夠構(gòu)造出符合該用戶地址的簽名，等同于掌握了該用戶的私鑰，因此節(jié)點(diǎn)無需事先確定用戶公鑰，僅從簽名恢復(fù)出公鑰，進(jìn)而計(jì)算出用戶地址，就可以執(zhí)行這個(gè)用戶地址空間的相應(yīng)操作。

FISCO BCOS基于這個(gè)原理設(shè)計(jì)實(shí)現(xiàn)了交易簽名和驗(yàn)簽。

recoveryID的計(jì)算

關(guān)于JavaSDK性能優(yōu)化的文章（記一次JavaSDK性能從8000提升至30000的過程）中提到一個(gè)關(guān)鍵優(yōu)化點(diǎn)——recoveryID的計(jì)算，這里仔細(xì)展開討論。

ECDSA簽名（r,s），其中r是橢圓曲線上一個(gè)點(diǎn)kG (x, y)對(duì)應(yīng)的x mod n，相當(dāng)于簽名信息中只留下了X軸坐標(biāo)相關(guān)的值，丟棄了Y軸相關(guān)的值。在「恢復(fù)算法Recover」中嘗試找回Y軸對(duì)應(yīng)的值構(gòu)造R，進(jìn)而恢復(fù)出公鑰。

由于r = x mod n，因此r,r+n,r+2n…都可能是合法的原始x值，不同的橢圓曲線存在不同數(shù)量這樣合法的x值，F(xiàn)ISCO BCOS采用的secp256k1曲線存在兩個(gè)可能r, r+n。

每一個(gè)X軸坐標(biāo)對(duì)應(yīng)兩個(gè)可能的Y坐標(biāo)，因此FISCO BCOS中具備四種可能的R，(r, y) (r, -y) (r+n, y’) (r+n, -y’)。但是，對(duì)于一個(gè)r值存在兩個(gè)X軸坐標(biāo)的概率極低，低到幾乎可以忽略，以太坊中就忽略了這兩種小概率事件。

那這個(gè)小概率事件的概率具體有多小呢？這要從secp256k1曲線的參數(shù)說起，通常描述一個(gè)橢圓曲線的點(diǎn)（x,y）的時(shí)候，x和y的值是 mod p 的結(jié)果，p是曲線的參數(shù)，它是一個(gè)大素?cái)?shù)，之前提到的n也是曲線的參數(shù)，等于這條曲線上點(diǎn)的數(shù)量（曲線上點(diǎn)的數(shù)量為n*h，h也是曲線參數(shù)，該曲線h=1），在secp256k1中，n和p的值非常接近，具體可見下圖。

由于r = x mod n，x是mod p的結(jié)果，r是mod n的結(jié)果，x值的范圍是[0, p-1]，r值的范圍是[0, n-1]。如果r+n也是曲線上的點(diǎn)，則r的值必須小于p-n，概率為 (p-n) / p，大約為3.73*10^-39，這個(gè)概率是非常小的。

基于簽名結(jié)果（r, s）和簽名過程中生成的隨機(jī)點(diǎn)（x, y）的y值，recoveryID的計(jì)算方式如下：

1. id = y & 1; //「簽名算法Sign」中kG點(diǎn)的y坐標(biāo)，根據(jù)奇偶性設(shè)置id值，因?yàn)閥是mod p的結(jié)果，其奇偶性與坐標(biāo)軸的正負(fù)性是完全對(duì)應(yīng)的

2. id |= (x != r ? 2 : 0); // 小概率事件，如前文解釋

3. if (s > n / 2) id = id ^ 1; // 簽名計(jì)算得出的s如果大于n/2就會(huì)取n-s作為s值，因此這里做相應(yīng)轉(zhuǎn)換，這兩個(gè)轉(zhuǎn)換是同時(shí)發(fā)生的

JavaSDK性能優(yōu)化的文章就是基于這個(gè)計(jì)算公式，將遍歷探尋recoveryID改為計(jì)算獲得，大幅提升了性能。

后話

從一個(gè)神奇的數(shù)字開始，查閱相關(guān)資料，了解設(shè)計(jì)原理，進(jìn)而闖入ECDSA的世界，在一堆數(shù)學(xué)公式中迷茫、游蕩，問題一個(gè)接著一個(gè)。一開始霧里看花，似懂非懂，靠著處女座的潔癖精神，總算把心中疑問一一化解。

精妙絕倫的密碼協(xié)議，高深莫測(cè)的數(shù)學(xué)理論，做一個(gè)區(qū)塊鏈碼農(nóng)，要學(xué)習(xí)的東西還很多。唯有苦其心志，勞其筋骨，善待每一個(gè)疑點(diǎn)，不放過每一處細(xì)節(jié)。

總會(huì)有一天，那時(shí)——撥開云霧見天日，守得云開見月明。