目錄
- Base 編碼的歷史
- 為什么需要 Base58
- Base58 的特點(diǎn)
- Base58 的擴(kuò)展 Base58Check
摘要
Base Encoding 是一組二進(jìn)制轉(zhuǎn)文本的編碼模式（Encoding Scheme）璃弄，常見的有 Base64篙耗、Base58、Base32、Base16乎完。可是我們總會(huì)疑惑為什么需要二進(jìn)制轉(zhuǎn)文本這種編碼模式呢软免？既然所有的編碼最終都會(huì)變成 0 和 1贰军，那么分成 ASCII 和 Base64 編碼是不是就沒有必要呢植兰？這篇文章會(huì)解答這些問題份帐。
Base 編碼的歷史
1970~1980 年代，DEC（和其他公司）生產(chǎn)的“微型計(jì)算機(jī)”使用的字符編碼為 ASCII钉跷。 每個(gè)字節(jié)使用 7 位弥鹦，給出 128 個(gè)可用值。 這足以滿足大寫和小寫拉丁字母，數(shù)字彬坏，標(biāo)點(diǎn)朦促，一些常見的數(shù)學(xué)符號(hào)，貨幣符號(hào)和控制字符的需要栓始。此后 ASCII 變得非常流行务冕，并在很長(zhǎng)一段時(shí)間內(nèi)占主導(dǎo)地位。ASCII 規(guī)定了范圍在 [0,127] 之間的字符編碼幻赚，其中 [0, 31] 以及 127 (del) 這 33 個(gè)屬于不可打印的控制字符（可以使用 man ascii 查證）禀忆。互聯(lián)網(wǎng)的殺手級(jí)應(yīng)用——電子郵件系統(tǒng)當(dāng)初是為了傳輸 7 位 ASCII 文本而設(shè)計(jì)的落恼，于是在傳輸信息時(shí)箩退，有些郵件網(wǎng)關(guān)會(huì)把 [0,31] 這些控制字符給清除，而有些會(huì)替換 10 (newline 或 \n）和 13 (carrige 或 \r) 字符佳谦，有些更加粗暴地將二進(jìn)制的最高位清空戴涝，還有的程序在收到 [128, 255 ] 之間的國際字符會(huì)發(fā)生錯(cuò)誤。
如何在不同郵件網(wǎng)關(guān)之間安全地傳輸控制字符钻蔑、國際字符和二進(jìn)制文件呢啥刻？作為 MIME（RFC 2045 和 RFC 3548）多媒體電子郵件標(biāo)準(zhǔn)的一部分的 Base64 編碼就被開發(fā)出來了。
Base64 編碼的解題思路很簡(jiǎn)單咪笑。既然直接傳輸控制字符可帽、國際字符和二進(jìn)制文件容易造成原始信息在傳遞過程中的錯(cuò)誤，那么就把原始信息都轉(zhuǎn)成 ASCII 的可打印字符窗怒，這樣就能讓舊系統(tǒng)安分點(diǎn)映跟，不再胡亂改變其內(nèi)容。
Base64 是怎么做的呢扬虚？它的核心算法是將每 3 個(gè)字節(jié)（3 * 8 = 24 比特）依次轉(zhuǎn)換成 4 個(gè)可打印字符（4 * log 64 = 24 比特）申窘。具體操作如下：
將 3 字節(jié)的數(shù)據(jù)，先后放入一個(gè) 24 位的緩沖區(qū)中孔轴，先來的字節(jié)占高位。數(shù)據(jù)不足 3 字節(jié)的話碎捺，緩沖器中剩下的比特用 0 補(bǔ)足路鹰。
每次取出 6 比特，按照其值選擇 ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/ 中的字符作為編碼后的輸出收厨，直到全部輸入數(shù)據(jù)轉(zhuǎn)換完成晋柱。
若原數(shù)據(jù)長(zhǎng)度不是 3 的倍數(shù)時(shí)且剩下 1 個(gè)輸入數(shù)據(jù)，則在編碼結(jié)果后加 2 個(gè) =诵叁；若剩下 2 個(gè)輸入數(shù)據(jù)雁竞，則在編碼結(jié)果后加1個(gè) =。用來代表補(bǔ)足的字節(jié)數(shù)。
我們以換行字符（ASCII 碼 10）為例碑诉，原始的二進(jìn)制表示如下
10 的二進(jìn)制表示是 0000 1010彪腔，放到 24 位的緩沖區(qū)補(bǔ)零為 00001010 00000000 00000000
每次取 6 比特，則如右邊劃分所示：000010 100000 000000 000000进栽。因?yàn)楹髢刹糠譃檠a(bǔ)零德挣，適用于規(guī)則 3。前兩部分的十進(jìn)制依次是 2, 32快毛，所以通過索引表選擇的值是 C, g
后兩部分是補(bǔ)零格嗅，所以替換成=。
故結(jié)果為 Cg==
為什么需要 Base58唠帝？
首先屯掖，Base58 和 Base64 一樣都是一組二進(jìn)制轉(zhuǎn)文本（binary-to-text）的編碼模式。Base58 的主要職責(zé)是將大整數(shù)表現(xiàn)成文本襟衰，它是由中本聰在 Bitcoin 中首先引入進(jìn)來的贴铜。為什么要這樣使用呢？有如下幾個(gè)原因：
https://en.bitcoin.it/wiki/Base58Check_encoding#Background
// Why base-58 instead of standard base-64 encoding?
// - Don't want 0OIl characters that look the same in some fonts and
// could be used to create visually identical looking account numbers.
// - A string with non-alphanumeric characters is not as easily accepted as an account number.
// - E-mail usually won't line-break if there's no punctuation to break at.
// - Doubleclicking selects the whole number as one word if it's all alphanumeric.
- 去掉了 Base64 中的長(zhǎng)相相近的字符右蒲，這樣直觀上就能分辨賬戶數(shù)字阀湿，如：0（零）和O（大寫 o），I（大寫 i）和 l（小寫l）瑰妄，以及 + 和 / （non-alphanumeric 非字母和數(shù)字組成的）陷嘴，共 6 個(gè)字符。這也是 Base58 名稱的由來间坐，因?yàn)?64 - 6 = 58
- 非字母和數(shù)字的字符就不太容易混入賬戶地址里
- 在郵件里沒有標(biāo)點(diǎn)就不會(huì)斷行（意在排除截?cái)嗟目赡苄裕?/li>
- 雙擊就能全部選中所有字符和數(shù)字的串
順帶一提灾挨，Base56 相較于 Base58，少了 1（一）和 o（小寫 o）這兩個(gè)字符竹宋，而 Base32 則只包含 A-Z 和 2-7 這 32 個(gè)字母和數(shù)字劳澄。
Base58 的特點(diǎn)
維基百科上說，Base58 不太適合編碼二進(jìn)制數(shù)據(jù)蜈七，而適合編碼大整數(shù)秒拔？在探討 Base58 的實(shí)現(xiàn)原理之前，我們先看看比較常見的幾種 Base 編碼飒硅。
Base16
有人可能會(huì)說 Base16 我沒有用過砂缩，怎么能說常見呢？乍看這個(gè)名字還挺唬人的三娩，但其實(shí)它就是 Hexidecimal 十六進(jìn)制編碼庵芭。對(duì)于 10101010，會(huì)被編碼成 0xAA雀监。拆解來看双吆，1010 是十進(jìn)制的 10，也就等于十六進(jìn)制中的 A。原因是十六進(jìn)制只能表示 0-9 以及 A-F 這16個(gè)數(shù)好乐，16 換成二進(jìn)制的范圍就是 0000 - 1111匾竿。
Base32
那么 Base 32 這種編碼呢？同理曹宴，它可以表達(dá)的二進(jìn)制范圍是 00000 - 11111 也即 2 的 5 次方搂橙，即 32 個(gè)數(shù)。但問題是二進(jìn)制都是 8 位起笛坦，8 是沒法整除 5 的区转。既然 8 除以 5 除不盡，那我們就找 8 和 5 的最小公倍數(shù)版扩，即 40废离。換句話說，5 bytes = 8 chars礁芦。也就是說蜻韭，我們需要將每 5 個(gè)字節(jié)轉(zhuǎn)化成 8 個(gè)Base32 中的字節(jié)。
由此柿扣，我們可以總結(jié)出一些規(guī)律肖方。Base16 這種編碼方式，8 和 4 的最小公倍數(shù)是 8未状，所以 1 bytes = 2 chars俯画，每次都能將一個(gè)字節(jié)轉(zhuǎn)化成 2 個(gè)字符，都能剛好對(duì)齊司草。而 Base32 這種編碼方式艰垂，因?yàn)?8 和 5 的最小公倍數(shù)是 40，所以 5 bytes = 4 chars埋虹，存在對(duì)齊不了情況猜憎，那么非 5 字節(jié)倍數(shù)的字節(jié)序列就需要額外補(bǔ)齊，同理搔课， Base58 和 Base64 也需要如此胰柑。
Base58
繼續(xù)深入之前，我們先回憶一下中學(xué)學(xué)習(xí)的短除法求解二進(jìn)制爬泥。以 10 為例旦事，計(jì)算如下：
短除法的實(shí)質(zhì)是連除進(jìn)制，降低位權(quán)急灭，依次得到各位上的數(shù)值。我們不妨以十進(jìn)制的 111 舉例谷遂。
雖然上面的計(jì)算純屬畫蛇添足葬馋，不過它對(duì)于理解二進(jìn)制的短除法還是很有幫助的。我們第一次用 111/10，得到的余數(shù)為1畴嘶，便是個(gè)位上的數(shù)蛋逾；再次用 11/10，得到的余數(shù)為1窗悯，便是十位上的數(shù)区匣；最后用 1/10 得到的余數(shù)為 1，就是百位上的數(shù)蒋院。類比可得亏钩，上例中計(jì)算 10 這個(gè)數(shù)字的二進(jìn)制時(shí)，第一次用 10/2欺旧，得到的余數(shù) 0 便是最低位上的數(shù)姑丑，得到的商為 5，則是 10 這個(gè)數(shù)的二進(jìn)制 1010 的高三位（101）辞友，依次類推即可得到不同數(shù)位上的二進(jìn)制數(shù)了栅哀。所以這樣就不難理解短除法有效性的來源。
我們?cè)賮砜纯?Base58 這種編碼方式称龙，它有 58 個(gè)字符留拾，所以可以表示的二進(jìn)制范圍是 000000 - 111001。因此鲫尊，Base58 編碼算法需要除法運(yùn)算實(shí)現(xiàn)痴柔，如果被編碼的數(shù)據(jù)較長(zhǎng)，則要用特殊的類來處理大數(shù)马昨，在 Bitcoin 使用了 OpenSSL 中的 BIGNUM竞帽。
偽代碼 - Base58 利用短除法編碼的過程
code_string = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";
x = convert_bytes_to_big_integer(hash_result);
output_string = "";
while(x > 0)
{
(x, remainder) = divide(x, 58);
output_string.append(code_string[remainder]);
}
repeat(number_of_leading_zero_bytes_in_hash)
{
output_string.append(code_string[0]);
}
output_string.reverse();
小結(jié)
Base64 用于編碼郵件內(nèi)容、網(wǎng)頁圖片鸿捧，意在減少傳輸過程中可能出現(xiàn)的錯(cuò)誤屹篓；Base58 是比特幣地址使用的編碼方法，旨在提高地址的辨識(shí)度匙奴；Base32 用在一些對(duì)大小寫不敏感的文件系統(tǒng)中堆巧。每種 Base-x 的編碼都有適合它們的應(yīng)用場(chǎng)景，自然為了需要我們也可以發(fā)明自己的 Base 編碼泼菌。
補(bǔ)充
Base58Check
就是將雙重 hash RIPEMD 之后的公鑰地址的頭4個(gè)字節(jié)作為校驗(yàn)值放到末尾谍肤，然后進(jìn)行 Base58，不過需要關(guān)注前導(dǎo)零哗伯。
參考資料
