base58checkフォーマット出力の先頭文字が決まる理由

ビットコインで使われているbase58checkフォーマット出力の先頭の文字が何になるかって教科書にはよく書かれていますが、
どうやって算出しているのか気になったので、確かめてみました。
取りうる最小値と最大値を与えれば出力値の範囲が分かるという理屈です。
ここでは最小値を0x0、最大値をすべて0xffとしています。

なおbase58checkとbase58は別の概念なので混同しないようにしましょう。

mainnetの公開鍵の場合、先頭が0x00で、base58によって必ず1がパディングされるので、
証明終わりです。

問題はtestnetの公開鍵です。以下で最小値、最大値を網羅しています。
公開鍵の場合、payloadがripemd160のハッシュ結果の20バイトです。

>>> import base58
>>> base58.b58encode(b'\x6f' + bytes([0x00]*20) + bytes([0x00]*4))
>>> base58.b58encode(b'\x6f' + bytes([0xff]*20) + bytes([0xff]*4))

結果

>>> base58.b58encode(b'\x6f' + bytes([0x00]*20) + bytes([0x00]*4))
b'mfWxJ45yp2SFn7UciZyNpvDKrzbhuzkU7H'
>>> base58.b58encode(b'\x6f' + bytes([0xff]*20) + bytes([0xff]*4))
b'n4rZHAPGXCu8bYchjzJhK3V7VVredELJRc'

確かに値の最小値と最大値がこれなので、先頭はmまたはnだと言えますね。

base58check フォーマットとビットコインアドレス

bitcoinでは色々なところでbase58checkフォーマットが使われています。
base58checkフォーマットを行う関数をb58checkとして実装してみたのが以下です。
ここでは、公開鍵から、メインネットのビットコインアドレスを計算しています。
ビットコインアドレスは、versionに0x00、
ペイロードには、公開鍵をバイト列にしたものにsha256とripemd160を施したものになります。

#!/usr/bin/env python

import base58
import hashlib

# version: 1 bytes
# payload: bytes
def b58check(version, payload):
    d = version + payload
    h1digest = hashlib.sha256(d).digest()
    h2digest = hashlib.sha256(h1digest).digest()
    e = d + h2digest[0:4]
    return base58.b58encode(e)

ba = bytes.fromhex("037c3e90284927ea5a46cb7f4d8c91a5d6defd3827144b28ad2451b524becb9806")
d = hashlib.sha256(ba).digest()
m = hashlib.new('ripemd160')
m.update(d)
ba = m.digest()

r1 = b58check(bytes.fromhex("00"), ba)
print(r1)

b'1MQoLvLZ1DcC7BmKGkbkZWgKH2roYQjZLb'

一つ前の記事で bx コマンドで生成したものと一致していることが分かります。

macOS に bitcoin explorer をインストールする

$ brew install bx

秘密鍵を生成しファイルに出力(32バイトhex)

$ bx seed | bx ec-new > private_key
$ cat private_key
4a1bdbb5164f0b096ab56ec74399222e44d13b2a93d5ad7fe8a341bbfa197c46

秘密鍵から公開鍵を計算しファイルに出力(33バイトhex)
先頭が0x03なので、奇数の圧縮公開鍵であることが分かります。

$ cat private_key | bx ec-to-public > public_key
$ cat public_key
037c3e90284927ea5a46cb7f4d8c91a5d6defd3827144b28ad2451b524becb9806

公開鍵からビットコインアドレス形式に変換して出力する

$ cat public_key | bx ec-to-address
1MQoLvLZ1DcC7BmKGkbkZWgKH2roYQjZLb

ripemd160をpythonで試す

ripemd160は160ビット(=20バイト)の値を返すハッシュ関数です。
pythonでは以下で計算できます。

#!/usr/bin/env python

import hashlib
h = hashlib.new('ripemd160')
h.update(b"abc")
r1 = h.hexdigest()

print(r1)
print("len "+str(len(r1)))

8eb208f7e05d987a9b044a8e98c6b087f15a0bfc
len 40

bitcoinではsha256とripemd160の２つのハッシュ関数が使われます。 sha256は有名なので分かりますが、なぜripemd160というマイナーなハッシュ関数が使われているのでしょうか？

明確な理由は不明ですが、256より少し小さいが、十分な強度で、かつsha256と組み合わせることで攻撃に対して少しでも強度を上げるためのようです。

https://en.wikipedia.org/wiki/RIPEMD

自作したい場合はこの辺りを参考にすればいいようです。

https://homes.esat.kuleuven.be/~bosselae/ripemd/rmd160.txt

またopensslコマンドにも実装されているのでそれで取ることも可能です。

$ openssl list-message-digest-commands
md4
md5
mdc2
rmd160
sha
sha1
$ echo -n "abc" |openssl rmd160
(stdin)= 8eb208f7e05d987a9b044a8e98c6b087f15a0bfc

base58をpythonで試す

base58は大まかに言ってbase64を改良したものです。
base64は64個の文字とパディングに=(イコール)を使うものです。WEBプログラマなら説明は不要でしょう。

base58はbase64から小文字のl(エル),大文字のI(アイ),大文字のO(オー),0(数字のゼロ),+(プラス),/(スラッシュ)の6つの文字を取り除き,
さらに=(イコール)でパディングするのもやめたものです。

base58エンコードはバイト列をBigEndianの整数にしてから、58進数として、58個の文字でBigEndianで表現したものですが、
桁が少ない場合は先頭を0パディングします。
ただし、16進の場合とはパディングする桁数が違いますので、ご注意ください。

ここでは、pythonのbase58ライブラリを使って計算した場合と、
直に計算したもの２種類で値が一致しているか試しています。

$ pip install base58

#!/usr/bin/env python

# use library
import base58
r1 = base58.b58encode(b'\x00\x01\x02')
print(r1)

# not use library
alphabet = b'123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
def b58encode(v):
    # パディング桁数を算出する
    nPad = len(v)
    v = v.lstrip(b'\0')
    nPad -= len(v)
    # バイト配列をBigEndianの数値と見なす
    p = 1
    s = 0
    # 右端から可算していく
    for c in reversed(v):
        s += p * c
        p = p << 8

    #   0 * 256 * 256 + 1 * 256 + 2
    # = 258
    print(s)

    output_ba = b''
    while s:
        # s に商, idx に余りが入る
        s, idx = divmod(s, 58)
        output_ba = alphabet[idx:idx+1] + output_ba

    # 先頭の0x0 の nPad バイト分ある場合は0(base58では1)を nPad バイト分パディングする
    return alphabet[0:1] * nPad + output_ba

r2 = b58encode(b'\x00\x01\x02')
print(r2)

b'15T'
258
b'15T'

参考
Base58Check encoding - Bitcoin Wiki