Mastering Bitcoin — CH4 Keys, Addresses, Wallets

Outline

本篇是 Mastering Bitcoin 這本書的第四章心得,如果沒看過前幾章心得的話可以先去看看,如果你沒有這本書的話可以去這邊,書跟心得都不會講的太深入,我的目標是希望不懂寫程式的都能看得懂 (順便幫自己做筆記),希望這目標不會太困難。

第二章我們提過整個區塊鏈的架構,現在這章會著重在使用者端的錢包以及裡面的公鑰、私鑰、地址三樣東西,探討他們之間的關係與推導過程,本章會有五段,每一段可能也會有小節,然後這篇的心得比較長。

另外,這章最常出現的三個名詞,都改用英文表達而不用中文,分別是公鑰 (public key)、私鑰 (private key) 和地址 (address)。

  1. public key、private key 之間是什麼關係?內容會提到三小節,分別是 private key、橢圓曲線加密和 public key。
  2. 比特幣的 address 是怎麼產生的?我們有了 public key 該怎麼得到 address?
  3. keys 的格式,為什麼 public key 和 private key 有分壓 (compressed) 和未壓縮 (uncompressed) 的格式,什麼又是 WIF private key?
  4. 錢包 (wallet) 就是 keys 的集合,但他還能有怎麼樣的分類?
  5. 還有哪些比較進階的 address 跟錢包?

Keys

第二章提過在比特幣網路裡面,區塊鏈 (blockchain) 裡面是記錄著成千上萬的交易 (transaction),每筆交易都會記錄著比特幣在哪一個 address,如果需要花費比特幣就需要提供簽名 (signature) 來代表授權,而 address 和簽名都是由 key 產生出來的,其中 key 又分為 private key 和 public key 兩種,private key 不會儲存在區塊鏈上,而是由使用者的錢包來保管,如剛剛所說的 private key 可以產生簽名,有了簽名就可以花費 address 裡面的比特幣,所以保管好錢包裡面的 private key 就變得相當的重要。

錢包是一個保管使用者 key 的地方,一個錢包當然也可以有很多組 key,private key 簡單來說就是一個數字,一個隨機的數字,而 private key 會透過橢圓曲線相乘 (elliptic curve multiplication) 得到 public key,public key 再透過 hash 函式可以得到 address,如下圖。

橢圓曲線相乘和 hash 函式都是所謂的單向函式,也就是說他們從一個方向算很容易,但是從等式的另一邊算回來就會非常的困難,有點像我們前幾章提到的 PoW 數學比賽。

而 private key 和 public key 還有個相當重要的數學關係,private key 可以對某個訊息 (例如交易) 產生簽名,而 public key 就可以對簽名進行驗證了,所以我們在第二章提過,創建交易之後還需要簽名來代表是我本人對這筆交易授權,因此我就需要提供用我的 private key 產生的簽名,同時附上我的 public key 一同在交易裡面,不需要洩漏 private key。當這筆交易散佈到網路上時,任何一個節點都可以拿簽名和 public key 進行驗證,知道這筆交易是不是合法的,礦工 (miner) 如果驗證是合法的交易,則可以納入到他現在正在組建的新區塊 (block) 裡面,詳細的簽名細節及驗證過程第五章會提到,或可以參考我之前的心得。

Private Key

private key 其實就是從 1 到 2²⁵⁶ 次方選一個隨機數字,然後他一定要保管好不能太容易被猜到,在程式裡面一個很常用的實作就是先產生一個亂數,或是一個沒有意義的字串,送進去 SHA-256 演算法出來就會是個長度為 256 bit 的數字了。

嚴格說起來,private key 需要符合一個條件,他必須要介在 1 到 1.158*10⁷⁷-1,這數字略比 2²⁵⁶ 小一些,會有這個奇怪的數字是因為比特幣選用的橢圓曲線的限制,超過的機率也很低。

Elliptic Curve Cryptography

在進入到 public key 之前,必須要先解釋一下橢圓曲線是什麼。比特幣使用的橢圓曲線叫做 secp256k1,他的公式如下

或是比較好懂的樣子

其中 p 是 2²⁵⁶-2³²-2⁹-2⁸-2⁷-2⁶-2⁴-1,是一個很大的質數,上面這個等式等於是要找到座標 (x, y) 中可以滿足 y² 除 p 的餘數等於 (x³+7) 除 p 的餘數,這些點所構成的曲線。例如以下範例座標 (x, y) 就是這曲線中的一點

>>> p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
>>> x = 55066263022277343669578718895168534326250603453777594175500187360389116729240
>>> y = 32670510020758816978083085130507043184471273380659243275938904335757337482424
>>> (x**3 + 7 - y**2) % p
0

是不是覺得很詭異?沒關係接下來更詭異。

在橢圓曲線裡面也有加法,給定曲線上兩點 P 和 Q,則這兩點的相加就是畫一條線通過這兩點,必會和曲線另一點相交,這點再對 x 軸映射就是答案了,如左圖。

而這條線就是 a 和 b 的割線,可以想像如果圖中的 a 和 b 越來越靠近,則 a + b 就等於在求 2a,所以橢圓曲線任一點的兩倍等於是該點的切線與曲線相交的點,再對 x 軸做映射的點。

如果要求五倍怎麼辦?就先做兩次兩倍 (切線),在跟原本的點相加 (割線) 就好了。

另外,橢圓曲線還有一個特殊的點叫做無窮遠點,他的概念有點像一般數學運算加法的 0。什麼時候會用到?如果 a 和 b 點是再同個垂直線上的兩點,那他們的割線肯定不會和曲線再相交,他們相加就會得到無窮遠點,等等,往 x 軸映射過去的點跟加一個負號意思好像一樣,所以他們相加等於自己減自己,就是 0,同理如果曲線上任一點和無窮遠點相加,就會等於他自己,很像四則運算加法裡的 0 的效果。

Public Key

終於回來 public key 了,我們把 private key 乘上橢圓曲線上一個固定的點叫做生成點 (generator point, G) 之後會得到一個點,這個點就會是我們的 public key 了,公式如下

K = k * G

其中 k 為 private key,是剛剛產生的一個範圍很大的隨機亂數,而 K 就是 public key,他是一個座標,G 在這邊是一個常數,也因為 G 是常數,所以我們每次拿一樣的 private key 去做乘法都會得到一樣的 public key,另外因為這個等式是單向的 (給你圖上一個點,要你求除法或減法往回找,你找看看),所以我們可以給別人看到我們的 public key,例如和簽名一起附在交易裡面讓網路上其他的礦工來驗證交易是不是合法的,但並不用擔心洩漏 private key 給其他人知道。而下圖是 private key 為 8 產生 public key 的過程示意圖。


Bitcoin Address

本篇第一張圖的前半段已經結束了,現在要進入後半段了,比特幣的 address 是由 public key 衍生出來的,一樣也是一對一且單向的數學式產生的,所以 address 可以給任何要送錢給你的人知道,也不用擔心會洩漏 public key,更不會洩漏 private key。簡單來說,public key 經由一次 SHA256 演算法再加上一次 RIPEMD160 演算法,最後再用 Base58Check encoding 就會得到 address 了,如下圖。而 SHA 和 RIPEMD 都是一種 hash 家族,這種單向的 hash 函式在比特幣的世界裡面除了產生 address 會用到以外,工作量證明 PoW 也會用到。

如果不知道什麼是 hash 函式的話可以去查一下資料,簡單來說就是把一個數值送進去一個函式,輸出得到的值,例如我可以把我的手機號碼 0911333779 用函式 f(x) = (2x + 1) mod 10 來 hash 就會變成 1933777559,當然真實情況會更複雜就是了。

上半段就是把 public key 去做一些 hash 而已,但有沒有看到倒數第二格有個 Base58Check,他到底是什麼?先從 Base58 開始。

Base58 encoding

這個編碼 (encoding) 是為了方便人類閱讀用的,如果在二進位的 1001 在十進位表示就是 9,本來要四個字元現在只需要一個字元就表示完了,Base58 概念就是這樣,他是 Base64 的衍生物,Base64 就是把 0–9 和大小寫的英文字母再加上 +- 兩個字元,總共 64 個字元都拿來表示,這樣表示出來的字串一個字元就代表 64 bits 的大小,長度就會變短。而 Base58 就只是把其中六個會讓人混淆的字元拿掉不用,分別是 +- 跟 0 (數字零)、O (大寫字母 O)、l (小寫字母 l)、I (大寫字母 I),所以就剩下 58 個字元而已了。所以剩下可以拿來用字元的就如下。

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

簡單來說,他是把長度縮短,方便閱讀用的。

Base58Check encoding

內容還是 Base58 encoding,但多了一個小特色。在最後面多加上 4 bytes 的錯誤檢查碼 (checksum),做法是把資料做兩次 SHA256 演算法取前 4 個 bytes。而資料再拿去算錯誤檢查碼之前,最前面要先加上一個 version code,這個東西的用處是為了讓使用者一看就知道這個 address 是屬於哪種型態,例如一般 address 就是 1 開頭,多簽 (後面會提到,第五章會介紹) address 就是 3 開頭,testnet 的 address 就是 m 或 n 開頭。Base58Check 的過程如下圖。


Key Format

現在,我們已經瞭解 private key 是一個隨機產生的亂數,這個亂數的範圍很大,而 private key 透過橢圓曲線的乘法可以產生 public key,是橢圓曲線上的一點,而 public key 透過兩個不同的 hash 函式在經過 Base58Check 編碼轉換成人類比較容易讀的格式,就變成 address 了,一個看起來沒有意義的字串,而這兩個過程均是單向的很難從等式的另一邊推回去。在前進到錢包之前我們先介紹一下 key 可能有的格式有哪些。

Public Key Format

在我們先前的介紹裡面可以知道 public key 其實就是一個座標,為橢圓曲線上的一點 (x, y),所以 public key 最簡單的形式就是 04xy,也就是把座標 x 和 y 的值接起來 (concat),前面再多一個 0x04 來做區分,例如以下座標

x = f02889...dc341a
y = 07cf33...505bdb
public key K = 04f02889......505bdb
public key 的座標 (x, y) 要先轉換成十六進位而不是十進位。

不過這樣有個問題,這種的 public key 長度為 130 (以十六進位來看),因為 public key 會被附帶在交易裡面驗證簽名,這樣的長度太長了會使交易太大,區塊鏈的大小也會跟著變大,而 public key 又是橢圓曲線上的一點,所以只要把 x 座標記起來去找到滿足方程式的 y 就可以得到這點了,如此一來 public key 的表示長度可以大幅減少一半,因此剛剛 0x04 開頭的 public key 形式又稱為未壓縮 (uncompressed) 的,只記錄 x 座標的就稱為壓縮 (compressed) 的。

複習一下橢圓曲線的公式,因為是 y² 代表就算我們知道了 x 座標,仍然有兩種 y 的可能,一正一負,從圖形去想也可以,在橢圓曲線上畫任一條垂直線會與橢圓曲線有兩點相交,因此我們在壓縮的表示方式就分為 0x020x03 開頭,分別代表取正根還是取負根。而順帶一提,compressed public key 現在為比較主流的形式了,因為可以省空間,壓縮過程如下圖。

這樣又衍生出一個新的問題,當我們拿 compressed public key 和 uncompressed public key 分別去產生 address,會是不樣的結果,因為產生 address 的過程畢竟只是 hash 函式,他不懂橢圓曲線的特性,但是這兩種 public key 都是源自於同一個 private key,有些舊版的錢包又不支援 compressed public key,所以這樣就會造成一些混淆,因此 private key 也要有相對應的格式來因應。

Private Key Format

為了區分 public key 是 compressed 還是 uncompressed 的,所以比較新版的錢包會在 private key 後面加上 0x01 做出區別,也叫做 compressed private key,而這種 private key 就要產生對應的 compressed public key,沒有 0x01的 private key 就代表對應到 uncompressed public key。為什麼需要這樣?我理解這是一個軟體向下兼容的手段,就像是你軟體更新之後常常需要保持舊的服務依然可以不受影響。以這邊的例子來看,如果你本來是舊版的 private key 要輸出舊的錢包換到新的錢包,新錢包需要知道區塊鏈上哪些 UTXO 是你的,但是他怎麼知道你原本是用 compressed public key 還是 uncompressed 的去產生 address,兩種都是合法的 address 但只會有一個是我原本在用的,所以這樣的做法他只要看你輸入的 private key 有沒有多出來的 0x01 就知道他應該用哪一種 public key 去產生 address,到區塊鏈上去掃一遍交易了。

這邊十分的混淆,因為其實 private key 根本不能壓縮,而且反而 compressed private key 還比原本的長度還長 (多出 0x01),private key 壓不壓縮沒有實質的意義,他只是在你轉換錢包時的一個旗標,代表著我當前用的 address 到底是用 compressed 還是 uncompressed 的 public key 所產生的。新錢包需要知道你是新版的還是舊版的概念。

在解決上述問題之後,private key 除了原本的十六進位的表示方式之外,一樣也可以套用之前提到的 Base58Check encoding,這種格式的 private key 又叫做 WIF (Wallet Import Format),而這個 WIF 也比較常用。而下表格是比特幣用到 Base58Check 的一個整理。

上表格 private key WIF 如果是 5 開頭代表是沒有 compressed 的,而 K 或 L 開頭則代表是 compressed 的。

Wallet

錢包之前提過了,他就是裝有一堆 key 的地方,他並不存比特幣,當使用者需要簽名時會用到裡面的 private key,然而錢包其實還是有幾種分類。

Non-Deterministic Wallets

非常的簡單就是「一堆 keys 的錢包」,又叫做 Random Wallet,例如比特比核心隨機產生 100 組沒有關聯的亂數,你就可以拿來用來當作產生 private key 們的種子 (seed)。這種錢包缺點是很難管理,因為彼此都沒有關聯,然而他的優點當然是安全,但仍然是不建議使用。

Deterministic Wallets

跟上面相反,就是讓 key 之前能有點關聯,有比較好的移植性,但也必須格外注意安全,最有名的就是 BIP32 提出的 HD Wallet (Hierarchical Deterministic Wallet),而我之前也因為實務上有需求,寫過一篇 HD Wallet 的心得,裡面也是按照 Mastering Bitcoin 的書來寫的,但同時搭配一個 python 的套件邊展示。連結在以下這邊就不再佔篇幅了。


Advanced Keys and Addresses

Encrypted Private Keys

大意就是 private key 需要夠安全,但又不能弄丟,所以錢包常常需要有備份,因此就會跟安全性有點衝突,所以作法就是再把 private key 用密碼加密一次,由 BIP38 所提出的,有興趣的話可以參考這裡,這邊就不詳細探討了。

Pay To Script Hash (P2SH) and Multi-Sig Addresses

P2SH 是一種不同於一般的 address,其中最常見的就是多簽 address (multi-sig address) 了,簡單來說他並不是一個 private key 產生的 address,可能同時由不只一人控管,達到規定比例的簽名時,授權就有效力了,詳細的 P2SH 和 multi-sig address 會在下一章提到,或是參考這邊

Vanity Addresses

他跟一般的 address 沒什麼兩樣,一樣要透過我們上面講的過程產生,不同的是這種 address 前幾碼可能含有特定的字元,例如你希望你的 address 是 1Kids 開頭,這樣重複搜索尋找符合的 address 大概需要花費一分鐘,值得注意的是如果希望匹配的字元越多,例如希望是 1KidsCharity 開頭的 address,需要試驗的時間就會越久,以現在這長度大概需要試驗兩百多萬年才能找到你想要的 address,這跟第八章介紹挖礦 (mining) 的原理有異曲同工之妙。

Paper Wallets

顧名思義就是把 private key 印在紙上,通常為了方便性會把 address 也一起印出來,他屬於冷錢包 (cold wallet) 的一種,冷錢包就是把錢包備份在離線的地方,例如隨身碟,或像這邊在紙上,以免電腦突然壞掉錢包也不見了,或防止駭客入侵,但他的缺點就是要保管好那張紙,要防小偷或被拍照。


Conclusion

終於結束了,簡單歸納幾個重點。

  1. private key 要是一個很難被猜到亂數,他是一個數字。
  2. public key 由 private key 經過橢圓曲線乘法而得到的一點,他是一個座標。
  3. address 是由 public key 經過一些 hash 函式產生的,他是一個 1 開頭的字串。
  4. private key 產生 public key 的過程是單向不可逆的,public key 產生 address 的過程也是。
  5. public key 因為需要夾帶在交易裡面,所以有壓縮版本的格式,因為兩種版本會產生不同的 address,所以連帶的 private key 也需要有兩種格式,表明這個使用者是用哪一種 public key 產生的 address。
  6. 錢包有分 deterministic 還是 non-deterministic 兩種,前者沒有規律,後者最有名的為 HD Wallet。

如果有還是不懂的或是講不清楚的地方歡迎來找我討論~如果有講錯的也請見諒並歡迎大力的更正我 Orz


雖然文章都只是一些我的閱讀心得,但如果你覺得我寫的文章有幫助到你踏入比特幣的世界,也歡迎透過比特幣贊助我 :D 1FwXwuNBA25fuJNBQ1L2iXnx23VHQBch3m

Reference

  1. Mastering Bitcoin