大きな値を使わずにバイト列(256進数)を58進数に変換する


# はじまりはBitcoinアドレス

Bitcoinのアドレスは公開鍵のハッシュ値(160bit)をBase58(正確にはBase58check)で表したものである。Base58は与えられた値を58進数にして、それぞれの桁を58種の文字で表す。
このためBitcoinのアドレスは、160bitのバイト列であるハッシュ値を大きな数値(最大$2^{160}-1$)として扱い、この大きな数値を繰り返し58で割りながらその余りを求めることで生成できる。

参考：[Bitcoinで使われる技術要素](https://qiita.com/tnakagawa/items/57c03595cb69cb685be1)

これをプログラムで行おうとする場合、変数に初期値として大きな数を代入する必要があるが、変数に代入可能な値の範囲はせいぜい$2^{64}-1$までである(*1)ため、これを超える値は代入できない。また58進数への変換は、64進数など基数が2の冪数である場合と異なり、単純に元のバイト列を適当なビット数(64進数であれば6bit)ごとに表して行うこともできない。

*1:この認識はC言語のunsigned long long型が64bitである事に依っており、他の言語においては誤りな場合がある。例えばPython3では整数の上限はない([Integers](https://docs.python.org/3.1/whatsnew/3.0.html#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](https://github.com/luke-jr/libbase58)を見つけた。実際にエンコードをする関数[`b58enc()`](https://github.com/luke-jr/libbase58/blob/1cb26b5bfff6b52995a2d88a4b7e1041df589d35/base58.c#L145)を以下に引用する。

```c
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に収まってしまうが、処理を理解するための手頃な入力のサイズで例を示す。

```bash
$ 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`の要素の値はそれぞれ以下のように格納される。

```c
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で割った商と余りを算出する。数式で表すと以下のとおり。

```math
\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で割った商と余りを算出する。数式で表すと以下のとおり。

```math
\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で割った商と余りを算出する。数式で表すと以下のとおり。

```math
\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$を更新する。

```math
\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で割った商と余りを算出する。数式で表すと以下のとおり。

```math
\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行目は、この時の様子を表している。

```math
\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行目は、この時の様子を表している。

```math
\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行目は、この時の様子を表している。

```math
\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行目は、この時の様子を表している。

```math
\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となる。

参考：[Base58 symbol chart - Bitcoin wiki](https://en.bitcoin.it/wiki/Base58Check_encoding)