はじまりはBitcoinアドレス
Bitcoinのアドレスは公開鍵のハッシュ値(160bit)をBase58(正確にはBase58check)で表したものである。Base58は与えられた値を58進数にして、それぞれの桁を58種の文字で表す。
このためBitcoinのアドレスは、160bitのバイト列であるハッシュ値を大きな数値(最大$2^{160}-1$)として扱い、この大きな数値を繰り返し58で割りながらその余りを求めることで生成できる。
これをプログラムで行おうとする場合、変数に初期値として大きな数を代入する必要があるが、変数に代入可能な値の範囲はせいぜい$2^{64}-1$までである(*1)ため、これを超える値は代入できない。また58進数への変換は、64進数など基数が2の冪数である場合と異なり、単純に元のバイト列を適当なビット数(64進数であれば6bit)ごとに表して行うこともできない。
*1:この認識はC言語のunsigned long long型が64bitである事に依っており、他の言語においては誤りな場合がある。例えばPython3では整数の上限はない(Integers)。 実はこのPython3の整数やJavaのBigIntegerの事はあとから知った。整数を扱う変数に上限がない場合は、58で割りながら余りを求める方法が使えるので、この記事のこのあとの話は不要なのだが、せっかく理解できたので「大きな値が使えない」という体で記述することにした。
58進数への変換の算数的な理解
対象となる大きな値を1つの変数で扱えないのであれば、いくつかの変数に分割して扱うしかない。ここで、そもそもこの値($V$)は160bit(20Byte)のバイト列を数値として扱ったものであることを考えると、元のバイト列を1Byteずつ区切ったそれぞれの値($b_i$; 範囲は0から255=0xFF)によって、以下の式で表すことができる。
$$ V = b_0 \times 256^{19} + b_1 \times 256^{18} + \cdots + b_{17} \times 256^2 + b_{18} \times 256 + b_{19}$$
この式により、$b_0b_1 \cdots b_{17}b_{18}b_{19}$は値$V$を20桁の256進数で表していると言い換えられる。さらに、値$V$を58進数で表すには以下の式における$r_j$(範囲は0から57)が分かればよいといえる。
$$ V = r_0 \times 58^{27} + r_1 \times 58^{26} + \cdots + r_{25} \times 58^2 + r_{26} \times 58 + r_{27} $$
ここまでの事により、大きな値$V$は元のバイト列を1Byteずつに区切った値により、256進数で$b_0b_1 \cdots b_{17}b_{18}b_{19}$と表せ、これを58進数で$r_0r_1 \cdots r_{25}r_{26}r_{27}$と表した時のそれぞれの値が分かれば、256進数から58進数に変換できたと言える。
Base58エンコードの実装
Base58エンコードの実装を探したところ、C言語で実装されたlibbase58を見つけた。実際にエンコードをする関数b58enc()を以下に引用する。
145 bool b58enc(char *b58, size_t *b58sz, const void *data, size_t binsz)
146 {
147 const uint8_t *bin = data;
148 int carry;
...
155 size = (binsz - zcount) * 138 / 100 + 1;
156 uint8_t buf[size];
...
159 for (i = zcount, high = size - 1; i < binsz; ++i, high = j)
160 {
161 for (carry = bin[i], j = size - 1; (j > high) || carry; --j)
162 {
163 carry += 256 * buf[j];
164 buf[j] = carry % 58;
165 carry /= 58;
166 }
167 }
...
185 }
第3引数でエンコードの対象となる値を指定し、関数内で値を配列(bin)として扱っており、若いアドレス(小さい添字の要素)に、256進数で表した時のより大きな位の値を格納している。変換結果は、58進数で表した時のそれぞの桁の値を配列bufに格納する。sizeに58進数で表した時の桁数をあらかじめ計算し、小さい添字の要素に、より大きな位の値を格納する。
159行から167行で256進数から58進数へ変換するための処理をしているが、bin、bufの配列要素のサイズは1Byte(uint8_t)、計算過程で登場する変数carryのサイズは4Byte(int)であり、日常的なサイズの変数のみを使って計算していることが分かる。
具体的な計算例
なぜb58enc()の処理で256進数から58進数への変換が実現できるのかを理解するために、165行の直後でそれぞれの変数の値を表示しながら、具体的な入力で実行した。実行例として、入力となるバイト列に0fffc34b(*2)を与えたきの結果を以下に示す。
*2:Bitcoinアドレスと比べるとだいぶ小さく4Byteに収まってしまうが、処理を理解するための手頃な入力のサイズで例を示す。
$ echo '0fffc34b' | xxd -r -p | ./base58
1: i, j, high: 0, 5, 5 buf: 0 0 0 0 0 15 carry: 0
2: i, j, high: 1, 5, 4 buf: 0 0 0 0 0 35 carry: 70
3: i, j, high: 1, 4, 4 buf: 0 0 0 0 12 35 carry: 1
4: i, j, high: 1, 3, 4 buf: 0 0 0 1 12 35 carry: 0
5: i, j, high: 2, 5, 2 buf: 0 0 0 1 12 49 carry: 157
6: i, j, high: 2, 4, 2 buf: 0 0 0 1 39 49 carry: 55
7: i, j, high: 2, 3, 2 buf: 0 0 0 21 39 49 carry: 5
8: i, j, high: 2, 2, 2 buf: 0 0 5 21 39 49 carry: 0
9: i, j, high: 3, 5, 1 buf: 0 0 5 21 39 33 carry: 217
10: i, j, high: 3, 4, 1 buf: 0 0 5 21 51 33 carry: 175
11: i, j, high: 3, 3, 1 buf: 0 0 5 41 51 33 carry: 95
12: i, j, high: 3, 2, 1 buf: 0 0 41 41 51 33 carry: 23
13: i, j, high: 3, 1, 1 buf: 0 23 41 41 51 33 carry: 0
Qiita
この例の場合、配列binの要素の値はそれぞれ以下のように格納される。
bin[0] = 0x0f (= 15)
bin[1] = 0xff (= 255)
bin[2] = 0xc3 (= 195)
bin[3] = 0x4b (= 75)
入力されたバイト列を数値として扱った時の値$V$(=0x0fffc34b=268419915)は以下のとおり表せる。
$$ V = 15 \times 256^3 + 255 \times 256^2 + 195 \times 256 +75$$
表示結果を見ながら、値$V$を数式上で58進数に変換していく。
まず、一番大きな位の値$b_0$を処理する。この例では15であり、58で割った余りも同じく15であるので、これを58進数で表した時の一番小さな位の値$r_5$とする。表示結果の1行目はこの様子を表している。
次に、$b_1$(=255)を処理する。$b_1$にここまでの結果$r_5$(=15)を256倍した値を足し、58で割った商と余りを算出する。数式で表すと以下のとおり。
\begin{align}
V &= 15 \times 256^3 + 255 \times 256^2 + 195 \times 256 +75\\
&= (15 \times 256) \times 256^2 + 255 \times 256^2 + 195 \times 256 +75\\
&= (15 \times 256 + 255) \times 256^2 + 195 \times 256 +75\\
&= 4095 \times 256^2 + 195 \times 256 +75\\
&= (70 \times 58 + 35) \times 256^2 + 195 \times 256 +75\\
&= \bigl( (1 \times 58 + 12) \times 58 + 35 \bigr) \times 256^2 + 195 \times 256 +75\\
&= \bigl( 1 \times 58^2 + 12 \times 58 + 35 \bigr) \times 256^2 + 195 \times 256 +75\\
\end{align}
ここまでの計算で、$r_3$(=1)、$r_4$(=12)、$r_5$(=35)の途中結果が得られ、表示結果の4行目はこの様子を表している。
さらに、$b_2(=195)$を処理する。$b_2$にここまでの結果$r_5(=35)$を256倍した値を足し、58で割った商と余りを算出する。数式で表すと以下のとおり。
\begin{align}
V &= (1 \times 58^2 + 12 \times 58 + 35) \times 256^2 + 195 \times 256 +75\\
&= \bigl( (1 \times 58^2 + 12 \times 58 + 35) \times 256 +195 \bigr) \times 256 +75\\
&= \bigl( (1 \times 58^2 + 12 \times 58) \times 256 + (35 \times 256 +195) \bigr) \times 256 +75\\
&= \bigl( (1 \times 58^2 + 12 \times 58) \times 256 + 9155 \bigr) \times 256 +75\\
&= \bigl( (1 \times 58^2 + 12 \times 58) \times 256 + (157 \times 58 + 49) \bigr) \times 256 +75\\
\end{align}
ここまでの計算で、$r_5(=49)$に更新され、$r_4$以降の更新のための繰り上がり値$(=157)$が得られる。表示結果の5行目はこの様子を表しており、繰り上がり値はcarryに格納されているのが分かる。続けて$r_4$を更新する。繰り上がり値に、ここまでの結果$(=12)$を256倍した値を足し、58で割った商と余りを算出する。数式で表すと以下のとおり。
\begin{align}
V &= \bigl( (1 \times 58^2 + 12 \times 58) \times 256 + (157 \times 58 + 49) \bigr) \times 256 +75\\
&= \bigl( 1 \times 58^2 \times 256 + 12 \times 58 \times 256 + 157 \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( 1 \times 58^2 \times 256 + (12 \times 58 \times 256 + 157 \times 58) + 49 \bigr) \times 256 +75\\
&= \bigl( 1 \times 58^2 \times 256 + (12 \times 256 + 157) \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( 1 \times 58^2 \times 256 + 3229 \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( 1 \times 58^2 \times 256 + (55 \times 58 + 39) \times 58 + 49 \bigr) \times 256 +75\\
\end{align}
ここまでの計算で、$r_4$は39に更新され、繰り上がり値は55となる。表示結果の6行目はこの様子を表している。さらに続けて、ここまで同様に$r_3$を更新する。
\begin{align}
V &= \bigl( 1 \times 58^2 \times 256 + (55 \times 58 + 39) \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( 1 \times 58^2 \times 256 + 55 \times 58^2 + 39 \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( (256 + 55) \times 58^2 + 39 \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( 311 \times 58^2 + 39 \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( (5 \times 58 + 21) \times 58^2 + 39 \times 58 + 49 \bigr) \times 256 +75\\
&= \bigl( 5 \times 58^3 + 21 \times 58^2 + 39 \times 58 + 49 \bigr) \times 256 +75\\
\end{align}
ここまでの計算で、$r_2$(=5)、$r_3$(=21)、$r_4$(=39)、$r_5$(=49)の途中結果が得られた。表示結果の8行目はこの様子を表している。
最後に、$b_3(=75)$を処理する。これまで同様に、$b_3$にここまでの結果を256倍した値を足し、順に58で割った商と余りを算出する。数式で表すと以下のとおり。
\begin{align}
V &= (5 \times 58^3 + 21 \times 58^2 + 39 \times 58 + 49) \times 256 +75\\
&= (5 \times 58^3 + 21 \times 58^2 + 39 \times 58) \times 256 + (49 \times 256 + 75)\\
&= (5 \times 58^3 + 21 \times 58^2 + 39 \times 58) \times 256 + 12619\\
&= (5 \times 58^3 + 21 \times 58^2 + 39 \times 58) \times 256 + (217 \times 58 + 33)\\
\end{align}
表示結果の9行目は、この時の様子を表している。
\begin{align}
V &= (5 \times 58^3 + 21 \times 58^2 + 39 \times 58) \times 256 + (217 \times 58 + 33)\\
&= (5 \times 58^3 + 21 \times 58^2) \times 256 + 39 \times 58 \times 256 + 217 \times 58 + 33\\
&= (5 \times 58^3 + 21 \times 58^2) \times 256 + (39 \times 256 + 217) \times 58 + 33\\
&= (5 \times 58^3 + 21 \times 58^2) \times 256 + 10201 \times 58 + 33\\
&= (5 \times 58^3 + 21 \times 58^2) \times 256 + (175 \times 58 + 51) \times 58 + 33\\
\end{align}
表示結果の10行目は、この時の様子を表している。
\begin{align}
V &= (5 \times 58^3 + 21 \times 58^2) \times 256 + (175 \times 58 + 51) \times 58 + 33\\
&= (5 \times 58^3 + 21 \times 58^2) \times 256 + 175 \times 58^2 + 51 \times 58 + 33\\
&= 5 \times 58^3 \times 256 + (21 \times 58^2 \times 256 + 175 \times 58^2) + 51 \times 58 + 33\\
&= 5 \times 58^3 \times 256 + (21 \times 256 + 175) \times 58^2 + 51 \times 58 + 33\\
&= 5 \times 58^3 \times 256 + 5551 \times 58^2 + 51 \times 58 + 33\\
&= 5 \times 58^3 \times 256 + (95 \times 58 + 41) \times 58^2 + 51 \times 58 + 33\\
\end{align}
表示結果の11行目は、この時の様子を表している。
\begin{align}
V &= 5 \times 58^3 \times 256 + (95 \times 58 + 41) \times 58^2 + 51 \times 58 + 33\\
&= 5 \times 58^3 \times 256 + 95 \times 58^3 + 41 \times 58^2 + 51 \times 58 + 33\\
&= (5 \times 256 + 95) \times 58^3 + 41 \times 58^2 + 51 \times 58 + 33\\
&= 1375 \times 58^3 + 41 \times 58^2 + 51 \times 58 + 33\\
&= (23 \times 58 + 41) \times 58^3 + 41 \times 58^2 + 51 \times 58 + 33\\
\end{align}
表示結果の12行目は、この時の様子を表している。
\begin{align}
V &= (23 \times 58 + 41) \times 58^3 + 41 \times 58^2 + 51 \times 58 + 33\\
&= 23 \times 58^4 + 41 \times 58^3 + 41 \times 58^2 + 51 \times 58 + 33\\
\end{align}
ここまでの計算で、$r_1$(=23)、$r_2$(=41)、$r_3$(=41)、$r_4$(=51)、$r_5$(=33)の結果が得られ、これで$V$の58進数での表現が得られた。(この例では$r_0$はゼロ)。表示結果の13行目は、この時の様子を表している。
おわりに
バイト列から58進数への変換について、大きな値(を格納する変数)を使わずに実装したプログラムを紹介し、数式を用いてそのプログラムで確かに58進数への変換ができることを示した。
Bitcoinアドレスは、得られた58進数の各位の値を、割り当てた文字で表示する。この割り当てに従うと、今回の計算例は、23(Q)、41(i)、41(i)、51(t)、33(a)、でQiitaとなる。