Base58Checkがビットコインアドレスの打ち間違いを検知する仕組み

# はじめに
以下の記事でビットコインアドレスを作ったときに、Base58Checkというエンコーディング方式でビットコインアドレスをエンコードしました。

[ビットコインアドレスを自分の手で作って理解する - Qiita](https://qiita.com/quincedaddy/items/2e54f35683facb519446)

この際にBase58Checkにはビットコインアドレスの打ち間違いを検知する機能があると説明しました。この記事ではその検知の仕組みを実際に試しながら解説してみたいと思います。

なおBase58Checkはビットコインアドレスをエンコードするためだけではなく、ビットコインを成すシステムの色々な箇所で使われています。

今回はビットコインアドレスの打ち間違いの検知という例を用いて解説をしますが、これはあくまで一例であるということは念頭に置いて下さい。

# 解説
ではさっそく解説に入ります。上述の記事で以下のようなビットコインアドレスを作りました。

```
1EohnzQdSSSsarBSncpHnfWxCzqSVZ3uPj
```
詳しくは元記事を参照してもらいたいのですが、このビットコインアドレスはあるバイト列をBase58Checkエンコーディングして求めました。以下このバイト列をBと呼びます。

このバイト列Bの最後の4バイトはチェックサムになっています。ちなみにどうやらこのチェックサムの存在を持ってBase58Checkという名前が付いていますが、このチェックサムも検知の機能もエンコーディングとは独立したものなので、私はBase58エンコーディングと呼んだ方が自然だと思います。

このチェックサムはどのように求めたかというと、Bから最後の4バイト（つまりチェックサム）を除いたバイト列に、SHA256と呼ばれるハッシュアルゴリズムを2回実行した結果の最初の4バイトです。

以下、上述の関係を疑似コードで書いてみます。

```
byteArray = { 0x01,...,0xFF }
CheckSum = SHA256(SHA256(byteArray))[0:3]
B = {byteArray + CheckSum}
BitcoinAddress = Base58Encode(B)
```
これはつまり、ビットコインアドレスをBase58デコードしてバイト列に戻し、最後の4バイト（チェックサム）を取り除いた後にSHA256を2回実行し、結果の最初の4バイトとチェックサムを比べることで誤り検知の機能になるということです。

と日本語で説明してもいまいちわかりづらいのでこちらも疑似コードで解説します。

```
B = Base58Decode(BitcoinAddress)
CheckSum = B[Last 4 Bytes]
First4Bytes = SHA256(SHA256(B[Except last 4 bytes]))[0:3]
IsValidAddress = (CheckSum == First4Bytes) ? TRUE : FALSE
```
このようになります。簡単ですね。このようにビットコインアドレスはその中に検知の仕組みを内在しています。

ビットコインアドレスは物理的にはQRコード等で配布されることがほとんどですし、大抵は電子的にやりとりされるので大体はコピペされるでしょう。

しかしながらビットコインアドレスの打ち間違いで送付されてしまったビットコインを取り戻す術は存在しないため、このような検知の仕組みを備えることは非常に重要だったと思います。

以下、C#で上述の検知の仕組みを書いてみました。Base58のデコーディングの関数も書いています。上述の記事にBase58エンコーディングも書いてありますので、併せて参考にして下さい。

```csharp
using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Security.Cryptography;

namespace Base58Check
{
    class Program
    {
        static string Base58CharSet = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

        static byte[] GetBase58DecodedBytes(string base58str)
        {
            BigInteger result = 0;

            // Count # of preceding '1's
            int countOfPrecedingOne = 0;
            for (int i = 0; i < base58str.Length; i++)
            {
                if (base58str[i].Equals('1'))
                    countOfPrecedingOne++;
                else
                    break;
            }

            // Calculate the big integer out of the string
            for (int i = countOfPrecedingOne; i < base58str.Length; i++)
            {
                int reminder = Base58CharSet.IndexOf(base58str[i]);
                if (reminder < 0)
                    throw new Exception("Not a Base58 char -> " + base58str[i]);
                result = result * 58 + reminder;
            }


            List<byte> bList = new List<byte>(result.ToByteArray());
            bList.Reverse(); // To big endian as BigInteger.ToByteArray() is in little endian

            // We want preceding 0x00 in the result as many as preceding '1's in the given string
            int countOfPrecedingZero = 0;
            for (int i = 0; i < bList.Count; i++)
            {
                if (bList[i] == 0)
                    countOfPrecedingZero++;
                else
                    break;
            }

            // First remove all preceding 0x00 bytes which we happen to get due to the little endian return
            // from BigInteger.ToByteArray()
            if (countOfPrecedingZero > 0)
            {
                bList = bList.Skip(countOfPrecedingZero).ToList();
            }

            // Adding 0x00 bytes
            while (countOfPrecedingOne > 0)
            {
                bList.Insert(0, 0x00);
                countOfPrecedingOne--;
            }

            return bList.ToArray();
        }

        static bool ValidateBitcoinAddress(string base58str)
        {
            byte[] b = GetBase58DecodedBytes(base58str);
            byte[] checkSum = b.Skip(b.Length - 4).ToArray();
            byte[] rest = b.Take(b.Length - 4).ToArray();

            var sha256 = new SHA256CryptoServiceProvider();
            var testBytes = sha256.ComputeHash(sha256.ComputeHash(rest)).Take(4).ToArray();

            return testBytes.SequenceEqual(checkSum);
        }

        static void Main(string[] args)
        {
            Console.WriteLine(ValidateBitcoinAddress("1EohnzQdSSSsarBSncpHnfWxCzqSVZ3uPj")); // Correct
            Console.WriteLine(ValidateBitcoinAddress("1EohnxQdSSSsarBSncpHnfWxCzqSVZ3uPj")); // Typo
            Console.WriteLine(ValidateBitcoinAddress("1EohnQdSSSsarBSncpHnfWxCzqSVZ3uPj"));  // Missing letter
            Console.WriteLine(ValidateBitcoinAddress("1EohnQzdSSSsarBSncpHnfWxCzqSVZ3uPj")); // Swapping letters
        }
    }
}
```

以下、出力結果です。打ち間違いのあったビットコインアドレスに対しては誤りが検知されたのが分かります。

```
True
False
False
False
```

# まとめ
ビットコインでは要所要所でBase58というエンコーディングが用いられていますが、その特性から誤り検知の機能が必須であり、4バイトのチェックサムを使ったBase58Checkという誤り検知の仕組みが使われています。その仕組みについて解説しました。

# 参照
- [ビットコインアドレスを自分の手で作って理解する - Qiita](https://qiita.com/quincedaddy/items/2e54f35683facb519446)
- [Base58Check encoding - Bitcoin Wiki](https://en.bitcoin.it/wiki/Base58Check_encoding)