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ū)塊鏈底層原理感興趣的開(kāi)發(fā)者一起交流躬厌。
故事開(kāi)始
故事要從以太坊中一個(gè)神奇的魔數(shù)開(kāi)始說(shuō)起马昨。
以太坊黃皮書(shū)中，關(guān)于交易簽名的闡述講到兩個(gè)特殊的數(shù)「27扛施，28」鸿捧，實(shí)際上是從「0，1」通過(guò)加了一個(gè)27演變得到「27疙渣，28」笛谦，所以本質(zhì)上是一個(gè)特殊的數(shù)27。
這個(gè)特殊的數(shù)字27代表了什么含義呢昌阿？
一次偵探之旅開(kāi)始了…
這像是一個(gè)bug
搜索發(fā)現(xiàn)此前已有許多關(guān)于該問(wèn)題的討論，其中恳邀，Stack Exchange的一篇帖子指出這是一個(gè)設(shè)計(jì)bug懦冰。以太坊源碼github上，也有一個(gè)相關(guān)issue谣沸，該issue被打上了「type:bug」的標(biāo)簽刷钢。
Stack Exchange帖子中有一個(gè)鏈接給出了修復(fù)該Bug的代碼，請(qǐng)看下面截圖（紅框）乳附。在注釋說(shuō)明和代碼可見(jiàn)内地，fromRpcSig函數(shù)對(duì)27這個(gè)魔數(shù)進(jìn)行了特殊處理伴澄。從RPC過(guò)來(lái)的簽名中，v值如果小于27（可能是0-3）阱缓，則直接加上27作為新v值非凌，fromRpcSig函數(shù)通過(guò)這個(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玖媚。
于是箕肃，疑問(wèn)更多了，魔數(shù)35是什么今魔？ChainID又是什么勺像？
這不像是一個(gè)Bug
帶著這些疑問(wèn)，再一次查閱相關(guān)設(shè)計(jì)材料涡贱，我們看到咏删，以太坊EIP155中描述了有關(guān)ChainID的設(shè)計(jì)∥蚀剩基于以太坊源碼構(gòu)建的網(wǎng)絡(luò)督函，實(shí)際運(yùn)行的鏈有很多，為了防止一條鏈的交易被提交上鏈到另一條鏈激挪，造成重放攻擊辰狡，引入了ChainID的設(shè)計(jì)，在塊高2,675,000的位置進(jìn)行分叉實(shí)現(xiàn)垄分。
明白了ChainID的作用宛篇，另一個(gè)疑問(wèn)又產(chǎn)生了——以太坊中，有NetworkID來(lái)區(qū)分不同網(wǎng)絡(luò)薄湿，為什么還需要ChainID叫倍？
這要從NetworkID和ChainID的作用范圍來(lái)解釋。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，需要通過(guò) ChainID機(jī)制才能防止交易在ETH和ETC網(wǎng)絡(luò)之間交叉重放桥嗤，ETH主網(wǎng)的ChainID是1须妻，ETC主網(wǎng)的ChainID是61仔蝌。
說(shuō)到這里其實(shí)還是沒(méi)有搞清楚為什么是27，為什么是35荒吏？我們?cè)贓IP github的Issue#155中看到Jan和Buterin的交流記錄敛惊，看來(lái)27是來(lái)自比特幣的產(chǎn)物。
順藤摸瓜司倚，打開(kāi)electrum的github豆混，我們?cè)趀lectrum/electrum/ecc.py中找到如下代碼
從代碼中可見(jiàn)，electrum在簽名時(shí)动知，為原本只有0-3之間的recid（recoveryID）
加上了27皿伺，還有一個(gè)壓縮標(biāo)記，如果有壓縮則再加上4盒粮，recid的值范圍在27-34鸵鸥。
至此可知，27和35大概來(lái)源于此丹皱，以太坊繼承比特幣的設(shè)計(jì)妒穴，在比特幣源碼bitcoin/src/key.cpp的CKey::SignCompact函數(shù)中也確定了該實(shí)現(xiàn)方式，但是比特幣為什么如此設(shè)計(jì)摊崭，仍未可知讼油。
ECDSA才是“bug”
故事到這里，我們對(duì)以太坊代碼中那個(gè)魔數(shù)27的前世今生有大概了解呢簸，但這僅僅是故事的開(kāi)端矮台，由此引發(fā)我們進(jìn)一步思考一個(gè)問(wèn)題：recoveryID是什么？
為了解釋清楚這個(gè)問(wèn)題根时，我們需要從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)類(lèi)似寫(xiě)在紙上的普通簽名，用于鑒別數(shù)字信息的方法辆童，常見(jiàn)的數(shù)字簽名算法包括DSA召川、RSA和ECDSA等。
橢圓曲線密碼（ECC）是基于橢圓曲線數(shù)學(xué)的公鑰加密算法胸遇，建立在橢圓曲線離散對(duì)數(shù)困難問(wèn)題之上，常用的協(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的問(wèn)題圈纺，我們重點(diǎn)關(guān)注「恢復(fù)算法Recover」。
在計(jì)算R的步驟可以看到济欢，存在多個(gè)x的取值可能性赠堵，導(dǎo)致存在多個(gè)R的可能性，因此計(jì)算得到的Q也存在多個(gè)可能的結(jié)果法褥，需要通過(guò)和已知的公鑰對(duì)比茫叭，確定哪一個(gè)Q是正確的。如果遍歷x的所有可能都未找到正確的Q半等，說(shuō)明該消息和簽名是不對(duì)應(yīng)的揍愁，或者是一個(gè)未知的公鑰。
為了確定正確的Q杀饵，需要遍歷x的所有可能取值莽囤，跑多輪Recover算法，這個(gè)時(shí)間開(kāi)銷(xiāo)是比較大的切距。為了提高Recover的時(shí)間效率朽缎，采用空間換時(shí)間的思路，在簽名中增加一個(gè)v值，用于快速確定x话肖，避免遍歷查找試探北秽，這個(gè)v值就是recoveryID。
在區(qū)塊鏈系統(tǒng)中最筒，客戶(hù)端對(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ì)算出用戶(hù)地址厨相，然后在用戶(hù)地址空間執(zhí)行相應(yīng)操作。
這里潛藏了一個(gè)區(qū)塊鏈設(shè)計(jì)哲學(xué)鸥鹉，區(qū)塊鏈上的資源（資產(chǎn)蛮穿、合約）都是歸屬某個(gè)用戶(hù)的，如果能夠構(gòu)造出符合該用戶(hù)地址的簽名毁渗，等同于掌握了該用戶(hù)的私鑰践磅，因此節(jié)點(diǎn)無(wú)需事先確定用戶(hù)公鑰，僅從簽名恢復(fù)出公鑰灸异，進(jìn)而計(jì)算出用戶(hù)地址府适，就可以執(zhí)行這個(gè)用戶(hù)地址空間的相應(yīng)操作。
FISCO BCOS基于這個(gè)原理設(shè)計(jì)實(shí)現(xiàn)了交易簽名和驗(yàn)簽肺樟。
recoveryID的計(jì)算
關(guān)于JavaSDK性能優(yōu)化的文章（記一次JavaSDK性能從8000提升至30000的過(guò)程）中提到一個(gè)關(guān)鍵優(yōu)化點(diǎn)——recoveryID的計(jì)算檐春，這里仔細(xì)展開(kāi)討論。
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ù)說(shuō)起颠黎，通常描述一個(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的值非常接近亡鼠，具體可見(jiàn)下圖撕彤。
由于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）和簽名過(guò)程中生成的隨機(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ù)字開(kāi)始悴势，查閱相關(guān)資料，了解設(shè)計(jì)原理措伐，進(jìn)而闖入ECDSA的世界特纤，在一堆數(shù)學(xué)公式中迷茫、游蕩侥加，問(wèn)題一個(gè)接著一個(gè)捧存。一開(kāi)始霧里看花，似懂非懂担败，靠著處女座的潔癖精神昔穴，總算把心中疑問(wèn)一一化解。
精妙絕倫的密碼協(xié)議提前，高深莫測(cè)的數(shù)學(xué)理論吗货，做一個(gè)區(qū)塊鏈碼農(nóng)，要學(xué)習(xí)的東西還很多狈网。唯有苦其心志宙搬，勞其筋骨，善待每一個(gè)疑點(diǎn)拓哺，不放過(guò)每一處細(xì)節(jié)勇垛。
總會(huì)有一天，那時(shí)——撥開(kāi)云霧見(jiàn)天日拓售，守得云開(kāi)見(jiàn)月明窥摄。
