比特币中的Base58 编码

时间:2021-03-01 11:16:11

base58和base64一样是一种二进制转可视字符串的算法,主要用来转换大整数值。区别是,转换出来的字符串,去除了几个看起来会产生歧义的字符,如 0 (零), O (大写字母O), I (大写的字母i) and l (小写的字母L) ,和几个影响双击选择的字符,如/, +。结果字符集正好58个字符(包括9个数字,24个大写字母,25个小写字母)。不同的应用实现中,base58 最后查询的字母表可能不同,所以没有具体的标准。下面是几个应用中的字母表:

比特币地址:

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

Monero 地址

123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

Ripple 地址

rpshnaf39wBUDNEGHJKLM4PQRST7VWXYZ2bcdeCg65jkm8oFqi1tuvAxyz

Flickr 的短URL

123456789abcdefghijkmnopqrstuvwxyzABCDEFGHJKLMNPQRSTUVWXYZ

Base58 编码与解码

Base58 的输入是一个[0,256)的值的流,输出结果是一个[0,58) 的值的流。然后将每个值去查字母表,得出一个可视字符串。转换过程实际上就是一个256进制的值转换为一个58进制的值。

进制转换过程如下(下面伪代码描述256进制转换为58进制过程, base58编码需要将58进制流查表得到对应的字符流):

# 将 input 256进制流转换为 output 58进制流
for carry in input:
for (outputPos, outputNum) in output.reverse():
carry += outputNum * 256
output[outputPos] = carry % 58
carry /= 58
# output 流处理完毕, carry依然有值, 则继续向 output 前部插入
while carry != 0 :
output.insertFront(carry%58)
carry /= 58

在实现的时候,开头的0需要特殊处理下,因为0转换后依然是0, 所以可以将输入流开头的0直接填充到结果前边。

逆转换过程(先将输入字符串转换为58进制的流, 然后将58进制的流转换为256进制的流, 下面伪代码描述58进制转换为256进制过程):

# 将 input 58进制流转换为 output 256进制流
for carry in input:
for (outputPos, outputNum) in output.reverse():
carry += outputNum * 58
output[outputPos] = carry % 256
carry /= 256
# output 流处理完毕, carry依然有值, 则继续向 output 前部插入
while carry != 0 :
output.insertFront(carry%256)
carry /= 256

同样,在实现的时候,开头的0需要特殊处理下,因为0转换后依然是0, 所以可以将输入流开头的0直接填充到结果前边。

Base58Check

比特币之所以加入改进版的 Base58 算法,主要为了解决 Base58 导出的字符串没有校验机制,这样,在传播过程中,如果漏写了几个字符,会检测不出来。所以使用了改进版的算法 Base58Check。

实现是:在encode前,在输入流尾部加入输入内容的hash值(4个字节)。然后再对输入流进行 Base58Encode。

在 decode 时候:先 Base58Decode, 然后拆成两部分(内容和校验值),判断对内容计算的校验值和校验值字段是否一致。

Go 的base58库:
https://github.com/shengdoushi/base58

比特币Base58相关源码地址: https://github.com/bitcoin/bitcoin/blob/master/src/base58.cpp