比特幣背後的數學

數學與人工智能丨華研數據

比特幣系統會讓新人迷惑不解的原因之一是其背後的技術重塑了“所有者”這一概念。

>>>>

傳統意義上,“擁有”某物——諸如房產或金錢——意味著該物要么是個人保管,要么是委託一個可信實體(如銀行)來保管。

比特幣系統的情況則不然。比特幣本身既不集中存儲也不本地存儲,因此沒有任何一個實體是其保管人。

比特幣是以記錄的形式存儲於一個被稱為“區塊鏈”的帳薄之中,該帳薄的副本在互聯計算機所組成的志願者網絡中共享。

“擁有”比特幣僅僅意味著擁有移交控制權給他人的能力——通過在區塊鏈中創建一條轉帳記錄來實現。但這種能力是如何保證的呢?通過一個ECDSA私鑰、公鑰密鑰對。這又是什麼意思?怎麼保障比特幣系統安全的呢?

讓我們掀開蓋子看一看下面到底是什麼。

ECDSA是橢圓曲線數字簽名算法(Elliptic Curve Digital Signature Algorithm) 的縮寫。它是利用一條橢圓曲線和一個有限域來“簽名”數據的流程,通過這種方法,在第三方能驗證簽名的真實性同時,還能讓簽名者繼續保留創建簽名的專屬能力。比特幣系統中,被“簽名”的數據指的是轉移所有權時的交易。 ECDSA將簽名流程和驗證流程分離。每個流程都是由幾步算術運算所組成的算法。簽名算法使用私鑰,驗證算法使用公鑰。稍後我們將演示一個示例。

不過首先,先鋪墊一個關於橢圓曲線和有限域的速成教程。

橢圓曲線

橢圓曲線在代數上的表示是下面這個方程:

y2 = x3 + ax + b

其中,a = 0, b = 7 (比特幣系統所使用的版本),它的圖形如下:

橢圓曲線有一些很有用的特徵。例如,一條非垂直的直線與橢圓曲線相交於兩點,若這兩點均不是切點,則曲線上必有第三點與那條直線相交。另一個特徵是,過曲線上任意一點的非垂直切線與該曲線必有且僅有另一個交點。

利用這些特徵,我們可以定義兩種運算:“異點相加”和“同點加倍”。 (譯者註:用弦切法規則來定義加法運算)

“異點相加”, P + Q = R, 定義為:R為R’基於x軸的反射點(對稱點)。其中,R’為包含P和Q的直線與曲線的第三個交點。用圖解的方式最容易理解:

同樣,“同點加倍”,P + P = R, 定義為:作一條過P點的切線,先求出該切線與曲線的另一交點R’,再計算R’基於x軸的反射點R。

將這兩種運算結合起來可以用於標量乘法,R = a P, 定義為將P點與其自身相加a次。例如:

R = 7P

R = P + (P + (P + (P + (P + (P + P)))))

標量乘法的運算過程可以通過“異點相加”與“同點加倍”運算相結合來簡化。例如:

R = 7P

R = P + 6P

R = P + 2 (3P)

R = P + 2 (P + 2P)

這裡,7P被分解為兩步“同點加倍”和兩步“異點相加”。

有限域

ECDSA中的有限域可以理解為一個預定義的正數區間,使得每種運算的結果必包含於這個區間中(譯者註:對上面定義的加法運算封閉)。區間外的任何數要通過“迴繞”來使其落於該區間內。

達到這一目標的最簡單的方法是求餘數,即用模運算(mod)來實現。例如,9/7 的結果是商1餘2:

9 mod 7 = 2

這裡,我們的有限域是模數7,所有在這個有限域上的模運算,都會得到一個落在0到6區間內的結果。

綜合運用

ECDSA使用的橢圓曲線基於一個有限域,使曲線外觀發生了極大變化,而不是改變曲線所基於的方程或特殊屬性。用與上圖相同的方程式,在模數為67的有限域中繪製後中看起來成了這個樣:

現在變成了一個點的集合,所有的x值和y值都是0至66間的整數。注意這個“曲線”仍保持著水平方向的對稱。

異點相加”和“同點加倍”在視覺上稍有不同。圖上繪製的直線在水平和垂直方向上要作迴繞,就像“小行星”遊戲裡那樣,保持著相同的斜率。因此,(2,22)和(6,25)”異點相加”的圖形是這樣的:

第三個交點是(47,39),它的反射點是(47,28)。 (譯者註: 28 = 67 – 39)

回到ECDSA和比特幣

諸如比特幣這樣的協議為橢圓曲線和其有限域選擇了一套參數,協議下所有用戶使用的參數是固定的。這套參數包括所用的方程式、有限域的質數模數、落在曲線上的“基點”(G)的一個點。基點的“序次”(n)不是單獨選定的,它與其他參數構成一個函數,圖形上可以想像成“基點”反復與自身相加,直至切線的斜率無窮大(或成為重直線)為止時所疊加的次數。 (譯者註: “序次”的算術表示是nG = O中的n )

比特幣系統把一些非常大的數設為“基點”、質數模數和“序次”。實際上,所有實際應用中的ECDSA都使用極大的數值。基於這些數值的算法安全性非常高,試圖暴力破解或逆向工程的做法是不切實際的。

比特幣系統中:

橢圓曲線方程:y2 = x3 + 7

質數模數 = 2256 – 232 – 29 – 28 – 27 – 26 – 24 – 1 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

基點 = 04 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

序次 = FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

誰選擇的這些數字,為什麼這樣選?圍繞適合參數的選擇問題,產生了大量的研究,同時還有相當數量的陰謀論也被拋了出來。畢竟,一個巨大的,看起來隨機的數字有可能隱藏了重構私鑰的後門。簡言之,這一特定實現被定名為secp256k1,它是密碼學用途所使用的基於有限域橢圓曲線解決方案體系中的一員。

私鑰和公鑰

先把這些規定放到一邊,現在到了了解私鑰、公鑰以及它們的關係的時候了。簡要概括一下:ECDSA中,私鑰是一個用無法預知的方法選擇出的介於1和“序次”之間的數。公鑰由私鑰演算而得,通過將“基點”和一個等於私鑰的數值做標量乘法計算得出。計算公式為:

公鑰 = 私鑰 × 基點

這表明私鑰的最大可取的數值(這也是比特幣地址的數量)等於“序次”。

在一個連續的域上,我們可以繪製切線並在圖上標出公鑰來,不過,有公式可以在有限域上完成同樣的工作。 p + q “異點相加”求r用分量表示的計算公式如下:

c = (qy – py) / (qx – px)

rx = c2 – px – qxry = c (px – rx) – py

p“同點加倍”求r的公式如下:

c = (3px2 + a) / 2py

rx = c2 – 2pxry = c (px – rx) – py

實際計算中,公鑰的計算被分解為從“基點”開始的一系列“同點加倍”和“異點相加”運算。

下面我們用一個小的數字作示例演示底層的運算過程,以便直觀上了解密鑰是如何構建並如何用於簽名和驗證的。我們使用的參數為:

方程式:y2 = x3 + 7(亦即:a = 0, b = 7)

質數模數:67

基點:(2,22)

序次:79

私鑰:2

首先,求出公鑰。由於我們選擇的是一個最簡單的取值為2的私鑰,所以只需對“基點”進行一次“同點加倍”運算即可。計算過程如下:

c = (3 * 22 + 0) / (2 * 22) mod 67

c = (3 * 4) / (44) mod 67c = 12 / 44 mod 67

這裡,我們不得不先停下來使出些手法:當結果必須始終是整數時,怎麼做有限域下的除法?我們必須使用倒數來做乘法,不過沒有足夠篇幅在這裡解釋(如果對此感興趣,建議參考這里和這裡)。此刻,請您先權且相信我們的計算吧:

44-1 = 32

下面繼續:

c = 12 * 32 mod 67

c = 384 mod 67c = 49

rx = (492 – 2 * 2) mod 67rx = (2401 – 4) mod 67rx = 2397 mod 67rx = 52

ry = (49 * (2 – 52) – 22) mod 67ry = (49 * (-50) – 22) mod 67ry = (-2450 – 22) mod 67ry = -2472 mod 67ry = 7

由此可知,我們的公鑰對應的點是(52,7)。上面這些就是一個數值為2的私鑰所需的運算!

比起試圖由公鑰推導出私鑰來,從私鑰到公鑰容易計算。在實際應用中的橢圓曲線加密由於使用大數值作為參數,由公鑰推導私鑰在理論上是可能的,但在計算上行不通的。

因此,從私鑰得到公鑰是設計使然的單向行程。

與私鑰一樣,公鑰通常用一個十六進制數的字符串來表示。但等等,我們是怎麼把平面上的一個由兩個數字所代表的點變成了一個數?在非壓縮格式的公鑰中,代表x坐標和y坐標的兩個256位的數字粘合在一起就生成了一個長字符串。我們還可利用橢圓曲線的對稱性生成一個壓縮格式的公鑰,只保留x值標明該點在位於曲線上的哪一側。由這個部分數據我們就可以把兩個軸的坐標都還原出來。

用私鑰簽名

現在我們有了一個私鑰和公鑰對,簽名些數據吧!

數據可以上任意長度。通常第一步是哈希數據來生成一個與曲線的“序次”位數(256)相同的數字。這里為了使文章簡潔,我們省略了哈希的步驟,只簽名原始數據z。我們用G來代表“基點“,n代表“序次”,d代表私鑰。簽名的方法如下:

1.選擇一個介於1和n-1之間的整數k;

2.用標量乘法計算點(x, y) = k × G;

3. 令r = x mod n。若r = 0則返回步驟1;

4. 令s = (z + r × d) / k mod n。若s = 0則返回步驟1;

5. (r, s)即為簽名。

需要提醒的是,在步驟4中,若計算結果出現分數(在實際計算中總會出現),要用分子去乘以分母的倒數。在步驟1中,進行不同的簽名時,一定要注意使用的k值不能出現重複,並且不能被第三方猜出來。也就是說,k值要么是一個隨機數,要么是使用讓第三方無法竊密的確定性方法來生成。否則,私鑰會從第4步中被提取出來,因為s, z, r, k和n都是已知的。你可以在這裡了解一個過去出現過的此類型的漏洞。

我們選取數字17作為待簽名的數據,按下面的方法來計算。變量如下:

z = 17 (數據)

n = 79 (序次)G = (2, 22) (基點)d = 2 (私鑰)

1.選取一個隨機數:

k = rand(1, n – 1)

k = rand(1, 79 – 1)

k = 3(“這真的是隨機的嗎?我讀書少,不要騙我哦!”“好吧,被你看出來了,不過這個數能讓我們的示例更簡單點!”)

2.將點計算出來。這與前面確定公鑰時方法相同,為了簡明扼要,我們省略了“同點加倍”和“異點相加”的算術計算。

(x, y) = 3G

(x, y) = G + 2G

(x, y) = (2, 22) + (52, 7)

(x, y) = (62, 63)

x = 62

y = 63

3.計算r.

r = x mod n

r = 62 mod 79

r = 62

4. 計算s:

s = (z + r × d) / k mod n

s = (17 + 62 × 2) / 3 mod 79

s = (17 + 124) / 3 mod 79

s = 141 / 3 mod 79

s = 47 mod 79

s = 47

注意上面的計算中3能被除開,結果是個整數。實際計算中,我們需要使用k的倒數(和前面一樣,我們隱藏了一些令人作嘔的計算細節):

s = (z + r * d) / k mod ns = (17 + 62 * 2) / 3 mod 79s = (17 + 124) / 3 mod 79s = 141 / 3 mod 79s = 141 * 3-1 mod 79s = 141 * 53 mod 79s = 7473 mod 79s = 47

5. 我們的簽名就是(r, s) = (62, 47)。

與私鑰和公鑰一樣,簽名通常用一個十六進制的字符串來表示。

用公鑰來驗證簽名

現在,我們有了數據和該數據的簽名。掌握我們的公鑰的第三方機構可以收到該數據和簽名,並能驗證出我們是發送者。讓我們看看具體是怎樣工作的。

用Q來表示公鑰,其他的變量同上,驗證簽名的步驟如下:

1. 驗證r和s在1和n-1之間;

2. 計算 w = s mod n ;

3. 計算 u = z × w mod n ;

4. 計算 v = r × w mod n ;

5. 計算點(x, y) = uG + vQ ;

6. 驗證r = x mod n. 若等式不成立則簽名無效。

為什麼這些步驟能有用?我們省略了證明過程,不過你可以從這裡了解更多細節。

依照上面的方法我們看一下驗證過程是如何進行的。變量如下:

z = 17 (數據)

(r, s) = (62, 47) (簽名)

n = 79 (序次)

G = (2, 22) (基點)

Q = (52, 7) (公鑰)

1. 驗證r和s介於1與n-1之間。

檢查、再檢查

r: 1 <= 62 < 79

s: 1 <= 47 < 79

2. 計算w:

w = s mod n

w = 47 mod 79

w = 37

3. 計算u:

u = zw mod n

u = 17 * 37 mod 79

u = 629 mod 79

u = 76

4. 計算v:

v = rw mod n

v = 62 * 37 mod 79

v = 2294 mod 79

v = 3

5. 計算點(x, y):

(x, y) = uG + vQ

我們將uG和vQ分解為“同點加倍”和“異點相加”,分別進行計算。

uG = 76G

uG = 2(38G)

uG = 2( 2(19G) )

uG = 2( 2(G + 18G) )

uG = 2( 2(G + 2(9G) ) )

uG = 2( 2(G + 2(G + 8G) ) )

uG = 2( 2(G + 2(G + 2(4G) ) ) )

uG = 2( 2(G + 2(G + 2( 2(2G) ) ) ) )

稍坐片刻來體會一下吧,通過使用分組技巧,我們將75次連續的加法運算減少為6次“同點加倍”和2次“異點相加”運算。當數字真的變得很大時,這些技巧將會派上用場。

將工作結果算出來:

uG = 2( 2(G + 2(G + 2( 2( 2(2, 22) ) ) ) ) )

uG = 2( 2(G + 2(G + 2( 2(52, 7) ) ) ) )

uG = 2( 2(G + 2(G + 2(25, 17) ) ) )

uG = 2( 2(G + 2( (2, 22) + (21, 42) ) ) )

uG = 2( 2(G + 2(13, 44) ) )

uG = 2( 2( (2, 22) + (66, 26) ) )

uG = 2( 2(38, 26) )

uG = 2(27, 40)

uG = (62, 4)

下面是 vQ:

vQ = 3Q

vQ = Q + 2Q

vQ = Q + 2(52, 7)

vQ = (52, 7) + (25, 17)

vQ = (11, 20)

把兩個加到一起:

(x, y) = uG + vQ

(x, y) = (62, 4) + (11, 20)

(x, y) = (62, 63)

顯然步驟5在整個計算中佔了大部分。最後一步是,

6. 驗證 r = x mod n

r = x mod n

62 = 62 mod 79

62 = 62

我們的簽名有效!

結論

那些看完了所有的公式然後跳轉到底部的讀者,我們剛剛學到了什麼?

我們對存在於公鑰和私鑰間的深層數學關係有了一些直觀認識。我們看到即使在這個最簡單的示例中,簽名和驗證的過程也立刻變得非常複雜,從而我們可以體會到一旦相關參數變成了256位,相應會帶來多麼巨大的複雜度。我們看到了最簡單的數學運算是如何巧妙應用,使其實現了保護信息所需要的單向“陷阱門”功能,此功能定義了比特幣的所有權。我們對系統的強健度有了新的自信,只要我們能細心保護好我們的私鑰。

換句話說,這就是人們常說比特幣是“基於數學”的原因。

如果你面對這些複雜的二進制位仍能堅持看下來,我希望這可以給你一些信心邁向下一步,嘗試自己用數學算一算(這裡有一個模運算計算器能讓有限域的運算更容易些)。我覺得手工進行數據的簽名和驗證能令人更深地理解這一密碼學算法,正是它塑成了比特幣系統的獨一無二的“所有者”形式。

文章內容是由網友自行分享或搜索引擎推薦,如果您認為其內容違規或者侵犯了您的權益,請與我們聯繫,我們核實後會第一時間刪除;新聞取自網絡,觀點不代表本站立場!