基于門限ECDSA的定期可更新的比特幣密鑰管理方案

韓妍妍 徐鵬格 李兆斌 魏占禎

1(西安電子科技大學通信工程學院 陜西 西安 710071)

2(北京電子科技學院通信工程系 北京 100070)

0 引 言

比特幣[1]是中本聰于2008年提出的一種點對點的電子現金系統。與傳統的銀行交易不同，任何規模的比特幣交易都依賴于ECDSA。用戶獨立創建和存儲一個公私鑰對，其中公鑰通過單向哈希函數可以導出一個比特幣地址，而對應的私鑰僅由用戶自身可見并用于簽名交易。該過程完全獨立于比特幣網絡，且無須訪問區塊鏈或互聯網。礦工利用公鑰對交易的數字簽名進行驗證，如果驗證通過則將該筆交易記錄在區塊鏈中，否則拋棄該交易。由此可見，比特幣的安全性等同于授權交易的私鑰的安全性。一旦私鑰泄露，比特幣將會被盜。即使已知貨幣被盜，也無法扭轉違規交易。

最早的用戶只能生成和存儲有限個私鑰，這種管理方式顯然無法滿足比特幣用戶的需求。2012年，Wuille[2]提出一種分層確定性密鑰管理方案，即可由一個種子以樹狀結構衍生任意多個密鑰，這從根本上解決了私鑰不易再生和難備份的問題，該方案被記為第32項比特幣改進協議(BIP-32)。2013年，Palatinus等[3]提出可用一組容易記憶的單詞來生成密鑰種子，這樣更加易于用戶從本地導入和導出比特幣密鑰。與用二進制或十六進制表示的種子相比，助記詞與人類的交互會更優越。該提議被記為第39項比特幣改進協議(BIP-39)。2014年，Bamert等[4]設計了一種低功耗的藍牙硬件錢包，用于實現對比特幣密鑰的物理保護。然而傳統對密鑰進行單一位置存儲的方法可能會導致黑客匿名地、不可逆轉地盜取用戶的所有資金。

對比特幣進行聯合控制可有效解決這一問題，攻擊者若想完成欺詐性交易必須破壞超過閾值的設備。多重簽名是指比特幣地址需要與n個指定公私鑰對相關聯，花費上面的比特幣至少需要t個簽名。但由于多重簽名會暴露團體的訪問策略，導致用戶的匿名性變弱，這并不是最好的比特幣聯合控制方案。2016年，Gennaro等[5]提出利用門限簽名方案替代多重簽名更加安全合理，并在Mackenzie等[6]提出的雙方ECDSA方案的基礎上提出了一種最優門限ECDSA方案。在n個成員中，任意t個或更多個成員可聯合對某個消息進行簽名。然而，以上方案需要完成分布式Paillier密鑰生成，這是非常昂貴和不切實際的。Zhou等[7]提出一種分布式比特幣賬戶管理(DBAM)框架，利用基于屬性的加密算法實現企業和公司對比特幣賬戶的細粒度管理，但該方案并未真正實現去中心化，仍然需要一個主賬戶完成私鑰份額分發及交易簽名。2018年，Lindell等[8]通過利用支持加性同態的指數型ElGamal替換Paillier加密算法來解決文獻[5]方案中的問題。但是，Lindell等[8]所設計的指數型ElGamal并不是有效的加密方案，其解密過程需要解決離散對數難題，因此只有當簽名消息相對較小時，該方案才能順利執行。同年，Gennaro等[9]通過引入一種份額轉換協議來改進其原始方案[5]，該協議允許雙方將秘密的乘法份額轉換為同一秘密的加法份額。該方案中的每個玩家最終只需要在本地生成自己的Paillier密鑰即可。此外，雙方ECDSA[6,10-11]更符合個體用戶增強比特幣密鑰的安全需求，Mann等[12]將電腦桌面錢包與智能手機錢包結合的方法則是雙方ECDSA的應用實例。

1 基礎知識

1.1 橢圓曲線數字簽名

橢圓曲線數字簽名算法[13-14](ECDSA)由階為p，生成元為G的循環群參數化，其中G為某條橢圓曲線上的點。ECDSA具體定義如下：

Gen(1κ)：隨機選擇一個私鑰sk∈Zq，計算公鑰Q=sk·G。輸出公私鑰對(Q,sk)。

Sig(sk∈Zq，m∈{0,1}*)：隨機選取一個隨機數k∈Zq，計算(rx,ry)=R=k·G。然后計算s=k-1·(H(m)+sk·rx)，輸出數字簽名σ=(s,rxmodq)。

1.2 陷門承諾方案

承諾方案[15-17]允許發送者先對消息做出承諾而后再對驗證者打開。陷門承諾方案一般由密鑰生成(KG)、承諾(Com)、打開(Open)、驗證(Ver)四個算法組成，具體如下：

KG：密鑰生成算法。輸入相關安全參數，該算法輸出一對公私鑰對(pk，tk)，其中：pk是與方案相關的公鑰；tk又稱為陷門。

Com：承諾算法。輸入公鑰pk和消息M后，輸出[C(M),D(M)]=Com(pk,M,r)，其中r為硬幣投擲。C(M)用于做事先承諾，D(M)是用于稍后揭密消息M。

Open：打開承諾算法。輸入C(M)、D(M)、公鑰pk后，輸出消息M或者⊥。

Ver：驗證算法。輸入公鑰pk、消息M、R，以及一個新消息M′≠M、T。如果T=tk，那么輸出D′使得Ver(pk,C(M),D′)=M′。

1.3 Shamir門限方案

1) Shamir門限方案[18]：給定秘密值s∈Zq，成員個數n及閾值t(t≤n)。分發者D在Zq上選擇一個t-1階的多項式：

f(x)=a0+a1x+…+at-1xt-1modq

(1)

計算每個子秘密值xi=f(i)并秘密分發給成員，則任意t個成員即可利用拉格朗日插值公式恢復秘密值。

2) 拓展方案1(Feldman等[19]可驗證秘密共享)：分發者D首先廣播相關值ga0,ga1,…,gat-1，然后再向成員分發秘密值。每位成員可利用式(2)驗證子秘密的正確性：

gαi=(ga0)(ga1)i…(gat-1)it-1

(2)

當全部的子秘密均正確后分發階段成功完成。

3) 拓展方案2(Baron等[20]主動秘密共享方案)：分發者隨機生成一個t-1階多項式：

(3)

然后分別向成員分發秘密值f′(i)，成員利用式(4)計算新的子秘密，并銷毀之前的子秘密：

(4)

2 方案設計

激勵模型定義如下：假設某慈善機構準備組織一場比特幣全球募捐活動，并希望使用某個比特幣地址來宣傳此次活動。因為比特幣可實現跨幣種、跨國界的轉賬，所以該機構可以直接收到世界各地的募捐，也可以將資金快速分配給更多需要幫助的地區或個體。

由區塊鏈的特性決定，機構的比特幣交易記錄是完全公開透明的，捐贈者和公眾可以實時查看捐贈收入、資金的去向，以及資金撥放情況，任何人都不能從中牟利。機構要求n個部門共同管理該地址，至少t個部門同意才能完成某筆資金撥出。

2.1 安全定義

本文方案的計算模型由n個成員組成，即{P1,P2，…,Pn}。成員間通過安全的點對點通道以及廣播通道進行通信。假設S∈{1,2,…,n}是任意的成員集合，|S|=t。

敵手：假設敵手A是惡意且靜態的。惡意是指敵手可以腐敗其中k個成員，指示他們執行任意操作。并且本方案允許腐敗成員的人數k達到n-1個(k=n沒有意義)。靜態是指敵手A必須在協議執行前選擇腐敗成員，敵手被要求在每輪的最后發言。

本文需要基于現有的比特幣系統實現以下安全目標和要求：(1) 完全去中心化。整個方案完全不需要借助第三方，而是由成員交互完成密鑰生成、分發、更新及數字簽名等一系列協議。(2) 比特幣地址的不可偽造性。在密鑰生成協議中，敵手A無法偽造目標地址來欺詐誠實的成員。(3) 數字簽名的不可偽造性。在選擇消息攻擊下數字簽名具有不可偽造性。(4) 抵御合謀攻擊。任意t個成員可以共同生成簽名，而少于t個成員則無法生成簽名。

2.2 方案描述

本文方案由密鑰生成協議、密鑰更新協議和數字簽名協議三個協議組成。具體流程如圖1所示。

圖1 方案設計流程圖

密鑰生成協議用于生成密鑰對和比特幣地址。該協議必須先執行且僅需執行一次，而其他兩個協議可重復執行。密鑰更新協議不必在每次數字簽名協議前執行(圖中用虛箭頭表示)，當一方或多方的私鑰發生泄露后，可通過執行該協議獲取新私鑰，但舊私鑰必須被徹底銷毀。數字簽名協議需要在付款時執行，用于對相關比特幣交易進行簽名。收款時僅需向對方提供比特幣地址。

2) 數字簽名協議。(σ=(r,s))←Sig({ski}i∈S,m):集合S共同執行數字簽名協議。每位成員Pi輸入私鑰ski和待簽名的交易m，協議輸出數字簽名σ=(r,s)。然后向比特幣網絡中廣播交易m和簽名σ，等待礦工驗證。

3 具體方案

當發生惡意成員拒絕廣播消息或者拒絕打開承諾等情況時，本文方案中的協議均會立刻中止，且為了描述簡潔，省略了對承諾方案的驗證說明。

3.1 密鑰生成協議

首先，全體成員利用t-1階多項式：

f(x)=skmas+a1x+…+at-1xt-1modq

(5)

協議1KeyGen

輸出：成員Pi在本地保存(ski,Q,Adr)。

私鑰生成：

(2) 接收并存儲其他成員Pj的值KGCj。接著，成員Pi隨機生成一個Zq上的t-1階多項式：

(6)

(3) 當接收到其他所有成員Pj發送的值αj→i后，成員Pi先利用式(7)對該值進行正確性驗證。

(7)

如果驗證失敗則立即中止協議，否則繼續計算私鑰：

(8)

公鑰生成：

比特幣地址生成：

(7) 否則，成員Pi繼續計算比特幣地址：

Adr=Base58(RIPEMD160(SHA256(Q)))

(9)

成員Pi在本地存儲(ski,Q,Adr)。

3.2 密鑰更新協議

協議2KeyUpdate

(1) 成員Pi隨機生成一個t-1階多項式：

(10)

(11)

如果驗證失敗則立即中止協議，否則繼續計算新私鑰：

(12)

(3) 成員Pi計算：

(13)

(14)

(6) 成員Pi更新私鑰ski(m)，并銷毀舊私鑰ski(m-1)。

3.3 數字簽名協議

協議3Sig

輸入：每位成員Pi輸入私鑰ski，公鑰Q，用戶IDi和待簽名的比特幣交易m。

輸出：σ=(r,s)。

(2) 成員Pi選取一個隨機數ρi∈Zp，然后向協議4-Mult輸入兩個值ki和ρi，集合S共同完成相關計算：

(15)

(3) 成員Pi在本地計算：

γi=m/t+λi·ski·r

(16)

然后向協議4-Mult輸入兩個值ρi和γi，集合S共同完成相關計算：

(17)

(4) 成員Pi在本地完成計算：

s=α-1·βmodp

(18)

得到簽名σ=(r,s)。然后利用式(19)驗證簽名的正確性。

P′=s-1·m·G+s-1·r·Q=(x′,y′)

(19)

如果x′=rmodn，則證明簽名有效，向比特幣網絡廣播交易m和簽名σ，否則中止該協議。

以下協議4參考文獻[8]的6.2節。在執行該協議前，每個成員Pi需生成一個Paillier同態加密算法[21]的公私鑰對(xi,yi)，并廣播其公鑰yi。假設Enc表示pailler加密算法，Dec代表解密算法。Paillier的系數N>p22128。每位成員Pi操作具體如下。

協議4Mult

輸入：每位成員Pi輸入值ai和bi。

輸出：值c。

(1) 成員Pi利用自己的公鑰yi加密值ai，即計算wi=Encyi(ai)，并生成一個非互動的零知識范圍證明πi={ai

(2) 當接收到來自成員Pj的消息(wj,πj)后，成員Pi先對πj進行驗證。如果驗證失敗則中止該協議，否則隨機選取一個數vi→j∈Zp22128，利用同態加密性質計算：

wi→j=Encyj(di)=Encyj(aj·bi+vi→j)

(20)

并生成一個非互動的范圍證明：

πi→j={aj·bi+vi→j

(21)

然后將消息(wi→j,πi→j)傳回給成員Pj。

(3) 當接收到來自成員Pj的消息(wj→i,πj→i)后，成員Pi先驗證πj→i，如果驗證失敗則中止該協議，否則對wj→i進行解密：

dj→i=Decxi(wj→i)

(22)

當解密得到{dj→i}j∈S/{i}后，計算并廣播:

(23)

正確性分析。c值的計算公式為：

4 安全性分析

4.1 去中心化

實現門限ECDSA最簡單的方法是由可信經銷商將已存在的密鑰分為n份，然后分發給每個成員，而后t個成員即可通過將私鑰份額交由該經銷商完成數字簽名。但該方法仍然存在可信第三方這一單點故障，更安全的方法則是完全實現去中心化，密鑰生成、分發、數字簽名等過程均由全體成員協作完成。下面具體說明本方案如何實現完全去中心化操作。

f(x)=skmas+a1x+…+at-1xt-1=

(24)

a(t-1,i)xt-1modq

生成n個相關秘密份額并完成分發工作。成員將對應的秘密份額進行累加得到私鑰ski。

然后全體成員根據下式完成主公鑰生成工作：

最后，每位成員可在本地利用主公鑰Q生成比特幣地址。整個密鑰生成協議均是由全部成員共同完成的。

同理，在密鑰更新協議中，私鑰的更新算法與生成算法相類似，此處就不再贅述。需強調的是新私鑰生成后，全體成員還需驗證新私鑰對應的主公鑰Q(m)與原有主公鑰Q是否一致，從而確定新私鑰與原有比特幣地址是否相關聯。

在數字簽名協議中，參與交易的集合S無須通過將私鑰交由可信的第三方間接完成數字簽名工作。但集合S需要協助完成如下計算：

s=α-1β=

(∑ki∑ρi)-1·(∑ρi∑(m/n+λi·ski·r))=

(kρ)-1·ρ·(m+skmas·r)=

k-1·(m+skmas·r)

(25)

由式(25)可知，集合S聯合生成的ECDSA的簽名結果與集中式ECDSA相同。并且本文可以保證在協議的執行過程中，成員的私鑰不會泄露。

4.2 比特幣地址的不可偽造性

證明：假設I?[n]為腐敗成員集合。因為所有成員均被腐敗證明是沒有意義的，所以下面僅考慮I?[n](|I|

(1) 集合J中的成員Pj隨機選取一個值si∈Zq，然后計算Qi=si·G，[KGCi,KGDi]=Com(Qi)，并廣播KGCi，然后集合I執行相同操作。

4.3 數字簽名的不可偽造性

定理2協議4-Mult滿足輸入的隱私性和不可區分性。

(2) 敵手A接收到的是成員Pj加密后的輸入值wj=Encyj(aj)，無法獲知成員的輸入值aj。

(3) 當接收到成員Pj返回的密文wj→i后，A解密得到的是{ai·bj+vj→i}，但也無法從中獲知成員Pj的輸入值bj。

但本文強調由于Mult協議無法保證最后結果的正確性，所以在數字簽名協議結束前，成員還需要利用公鑰Q對生成的數字簽名σ=(r,s)進行驗證。當驗證通過后，成員即可向比特幣網絡中廣播交易等待礦工記入區塊鏈中，否則需要重新執行簽名協議進行交易。

基于Mult協議安全及ECDSA的SU-CMA安全性假設，可采用傳統的歸約模擬器方法證明本文的數字簽名協議是SU-CMA安全的。

4.4 抵御合謀攻擊

定理3Shamir門限方案的性質和數字簽名協議的不可偽造性決定本方案至少t個成員才能生成數字簽名，而少于t個則不能。

證明：不失一般性，假設t-1個成員試圖偽造某筆交易的數字簽名。

5 性能分析

表1從四個方面將本方案與多重簽名方案及文獻[7]方案進行了對比。

表1 方案的特性對比

在多重簽名方案中，同一個比特幣地址需關聯若干個固定數量的公鑰，至少生成閾值個相關的簽名才能花費該地址上的比特幣。在門限簽名方案中，一個比特幣地址僅與一個公鑰關聯，團體按需生成或分割相關的比特幣私鑰，最終生成一個簽名即可。雖然門限簽名和多重簽名均為多人參與的簽名方案，但兩者在比特幣密鑰管理中的應用效果有所不同。多重簽名的優點在于僅需標準的ECDSA，每個簽名可獨立完成；而門限簽名在訪問策略結構上更具靈活性，且匿名性相對更強。因此，門限簽名在比特幣密鑰聯合管理的場景下適用范圍更廣。

從匿名性角度而言，將多重簽名作為比特幣交易的簽名方案時，其內部訪問控制策略將完全暴露給外界，這會嚴重損害團體的匿名性。而門限ECDSA的結果與常規ECDSA是完全無法區分的，可以避免多重簽名的這一缺點，滿足許多公司對于內部訪問控制的保密需求。因此，本文方案可保證聯合簽名的匿名性與個體簽名的匿名性一樣強。

從去中心化角度而言，當某個人或團體希望將已有的比特幣私鑰進行分割管理時，則必須借助一個可信第三方。在文獻[7]方案中，主賬戶利用基于屬性的加密算法和Shamir門限方案對現有的私鑰進行共享，從而實現整個公司對某個比特幣地址上資產的細粒度管理。但其方案需要直接恢復私鑰才能完成對交易的簽名，因而只適合管理一次性地址。而本文方案的側重點則是實現完全去中心化，允許各方以分布式方式生成或更新比特幣私鑰，且在簽名過程中充分保證個體成員私鑰的隱私性，而無須重新構建比特幣主私鑰，這更利于團體對某個固定比特幣地址的長久共享。

從密鑰更新角度而言，本文方案增設了密鑰更新協議。全體成員可在每個時間周期內按協議規定更新自己的比特幣私鑰，而共享的主私鑰不變。攻擊者只有在某個周期內盜取閾值個數的比特幣私鑰份額，才能進一步恢復目標主私鑰，盜取對應地址上的比特幣。因此，密鑰更新協議有效增大攻擊者盜取成員私鑰的難度，更適合于團體對某個比特幣地址進行長期的聯合管理。

從計算成本角度而言，多重簽名中的每個成員都是以非交互的方式獨立完成簽名的。當成員并行完成簽名時，簽名的完成時間與單密鑰ECDSA接近相同。本文方案和文獻[7]方案均采用門限ECDSA對比特幣交易進行簽名，所以參與者的人數t是影響簽名效率的重要因素。文獻[7]方案是由主賬戶完成簽名，參數t主要影響主私鑰的恢復時間，而本方案的數字簽名協議全程由t名成員交互完成，參數t影響整個協議的執行。表2就本文方案各個協議的主要開銷進行了統計。

表2 本文方案的計算開銷統計

在密鑰生成和密鑰更新協議中，成員的主要計算開銷來自于橢圓曲線上的點乘運算、指數運算及基于承諾的零知識證明。因為在密鑰生成階段需要完成比特幣地址的生成，所以該協議需要格外完成兩個哈希運算。而數字簽名協議是基于兩次Mult協議運算的，表2先對Mult協議的主要運算開銷進行統計，然后在此基礎上統計簽名協議的開銷。該協議的主要開銷來自于同態加解密算法以及其同態加性和乘性運算。

6 結 語

本文所提出的比特幣密鑰聯合管理方案利用門限ECDSA實現對比特幣的聯合控制，并且成員私鑰可進行定期更新。整個方案滿足中小企業對于比特幣密鑰管理的安全需求，同時也為其他區塊鏈項目中用戶的密鑰管理方案提供了新思路。