暗号通貨(Bitcoin, Monacoin)のプロトコルを理解する: 公開鍵と秘密鍵

## 概要
近年、Bitcoin, Litecoinに代表される暗号通貨が（良くも悪くも）大きな話題を呼んでいます。暗号通貨は現在混沌を極め、これまで数百もの派生通貨(Altcurrencies)が乱立している状況ですが、ここ日本でも最近「Monacoin」と呼ばれる日本発の派生通貨が誕生し、2chの片隅で密かに盛り上がりを見せています。この著者はその中で、「[Monapay](https://monapay.com/)」と呼ばれる、いわゆる暗号通貨版gumroadのウェブサービスを運営している者です。

以前、ふとした気まぐれで私は次のような形のゲームを提案し、2chに貼り付けました。

> 宣伝+暇つぶしがてらに賞金付きのゲームをやりたいと思います。内容は「俺のmonacoinを盗んでみろ」
> 
> M9WJPA8npJQEwcxXwvzKHwWz5msQfEKzf5
> いま、こちらのアドレスに10MONAを入金しました。実際に入金されたかどうかはAbeで確認できます。
> そして、Base64で符号化された生の秘密鍵はこちらになります。
> 0fHys0+Iy89GnEUfA0ZCJ652Tf8409Yor4ekLdazlXE=
> 昔テレビでビットコインのギフトカードを写したら、ソッコーで盗まれちゃった事件がありました。これと同じことが起こっています。
> 秘密鍵をインターネット上に晒したことで、このアドレスに入金されている10MONAは誰でも手に入れることができるようになりました。
> 
> ゲームは超簡単。最も早くこの秘密鍵を利用して、このアドレスから10MONAを盗み出してください。
> あなたは果たしてハッカーになれるのか？？テレビの司会者がされたようなことを、あなたもやってみてください！
> (テレビだと速攻で盗まれてますが、今回は盗まれなかった場合1日経過する毎に10MONA追加していく予定です)

10MONAとは、暗号通貨であるMonacoin通貨のことを指しています。この「窃盗問題」を提案した理由としては、実際にこの問題を解ける方は現在どれくらいいるのか気になったという単純な理由です。予想としては大体1日以上かかるのではないかと思ってたのですが、実際の結果は貼り付けてから2時間後に初めて解く方が現れ、[最終的には合計3名の方が奪取に成功しました](http://abe.monash.pw/address/M9WJPA8npJQEwcxXwvzKHwWz5msQfEKzf5)。10MONAは現在の日本円に換算して大体5, 60円くらいと安かったのですが、それでもこの問題に挑戦し、解いてくれる方がいたのは嬉しかったです(協力していただいた方、ありがとうございます)。

この問題を解くためには秘密鍵からWallet Import Formatと呼ばれるフォーマットに変換しそれをMonacoinクライアントに読ませる必要があるのですが、そのためには暗号通貨に対する知識だけでなく、[Monacoinのソースコード](https://github.com/monacoinproject/monacoin)を読む必要があります。今回の記事はこの問題に対する解説を載せると同時に、BitcoinならびにMonacoinプロトコルについての知識を深めることが目的です。現在暗号通貨に関する技術的な日本語の記事は皆無と言っていいほどなので、ある程度役に立つかと思います。

なお、この記事ではついでに解説用のPythonコードも併せて載せてあります。また、最後に練習問題として別の窃盗ゲームを載せています。賞金は少ないですが、手持ちのお金が殆どないので勘弁して下さい。

なお、寄付はいつでも受け付けております :)
MKrJpLy8Dg8mATKdH5zWCYiUVYQGvVW5Sx

## 電子署名
ご存知のとおり、Bitcoin、Monacoinを含む多くの暗号通貨は、すべての取引履歴（[トランザクション](https://en.bitcoin.it/wiki/Transactions)）が記入されている「[ブロックチェーン](https://en.bitcoin.it/wiki/Block_chain)」で構成される分散型データベースから成り立ちます。ユーザはこの巨大なデータベースに対し、実施したい取引の内容を書き込むことで実際の取引を行います。すなわち、暗号通貨における送金とは、「自分(Aとする)の口座のある金額をBに送る」という内容のトランザクションを、ブロックチェーンへ書き込むことに相当します。

ここで発生する問題は「Aの口座からの送金を指示した人物が、本当にA自身なのか」を証明する必要があることです。このことを証明するために、Monacoinは公開鍵暗号のアルゴリズムを利用して、トランザクションの書き込みを指示したユーザが本当に口座の持ち主であるのかを検証します。もう少し詳しく見て行きましょう:

![relationship.png](https://qiita-image-store.s3.amazonaws.com/0/37557/61a28874-a35f-d915-72d6-36209e43f680.png "relationship.png")


公開鍵暗号は、 *秘密鍵* と *公開鍵* の2つの鍵のペアで構成されています。Monacoinの場合、秘密鍵は256bit、公開鍵は512bitの数列です。秘密鍵は、トランザクションの書き込みを指示した人物がAであることを証明するために使われます。現実世界における印鑑かサインのようなものを考えてください。トランザクションを秘密鍵を使って署名することで、トランザクションの書き込みを指示した人物がAであることを証明できます。秘密鍵をネット上に漏らした場合は誰もがAを詐称してAの口座からの送金を指示できるため、この情報は決して外部に漏らしてはいけません。

秘密鍵は一般に16進数で表現されますが、このままだと64文字もあるので持ち運ぶには少し冗長です。本当にこれがMonacoinの秘密鍵を表した文字列であるのかを示すようなチェックサムも欲しいでしょう。そのため、Monacoinでは秘密鍵をより簡潔に表現した *[Wallet Import Format(WIF)](https://en.bitcoin.it/wiki/Wallet_import_format)* と呼ばれるフォーマットも提供しています。Monacoinにおける「秘密鍵」という単語は、生の秘密鍵ではなく一般にWIFを指します。生の秘密鍵とWIFは同じ情報を表しているため、WIFから生の秘密鍵を得ることもできますし、その逆も可能です。

次に公開鍵の説明に移ります。公開鍵はブロックチェーン内に記入された公開情報であり、秘密鍵による署名の検証に利用されます。Monacoinネットワークに接続しているすべてのユーザはこの公開鍵と電子署名を照らし合わせることで、トランザクションの書き込み主がAであるかどうかを検証します。秘密鍵から公開鍵を生成することはできますが、その逆はできないことに注意してください。

公開鍵のサイズは512bitもあるので、ブログや掲示板などにそのまま貼り付けるのは少し巨大すぎます。この問題に対処するため、Monacoinではより短い公開鍵の表現形式が提供されています。これが一般に知られる「Monacoinウォレットのアドレス」です。公開鍵からウォレットアドレスを生成することは簡単にできますが、ウォレットアドレスから公開鍵を生成することはできないことに注意してください。

## 変換方法
それでは、具体的な秘密鍵と公開鍵の生成方法について説明します。Monacoinのアドレスを生成するには、大きく3つのステップを取ります: (1)秘密鍵を生成する (2)秘密鍵から公開鍵を生成する (3)公開鍵からアドレスを生成する。また、上図で言及されている (A)秘密鍵からWIFを生成する (B)WIFから秘密鍵を生成する 操作も重要ですので、その方法についても説明します。

### (1) 秘密鍵を生成する
秘密鍵であるための決まりは特に何もなく、256bitであればなんでも構いません。一般には`/dev/random/`などの乱数生成器から取得した真の乱数を使います。なお、メルセンヌ・ツイスタなどの暗号論的に安全でない擬似乱数の使用は避けることがセキュリティ上望ましいとされています。

```python
def make_private_key():
    return os.urandom(32)  # 32 = 256/8
```

実行結果は次のようになります:

```bash
>>> private_key = make_private_key()
>>> print(private_key.encode("hex_codec"))
3954e0c9a3ce58a8dca793e214232e569ff0cb9da79689ca56d0af614227d540
```

### (2) 秘密鍵から公開鍵を生成する
Monacoinでは、電子署名のアルゴリズムに *[楕円曲線DSA](http://ja.wikipedia.org/wiki/楕円曲線DSA)* と呼ばれるアルゴリズムを採用しています(パラメータは`Secp256k1`)。詳細な仕組みを理解することは難しいですが、利用するだけならOpenSSLなどの標準的なライブラリを叩くだけで済みますのでそれを使うのが一番でしょう。

今回は[`ecdsa`](https://pypi.python.org/pypi/ecdsa)と呼ばれるPythonライブラリを使用します。`pip`を利用してインストールするのが楽かと思います。

```bash
$ pip install ecdsa
```

秘密鍵から公開鍵を生成するPythonコードは次のようになります:

```python
def private_to_public_key(private_key):
    signing_key = ecdsa.SigningKey.from_string(
        private_key, curve=ecdsa.SECP256k1)
    verifying_key = signing_key.verifying_key
    return verifying_key.to_string()
```

実行結果は次のようになります:

```bash
>>> public_key = private_to_public_key(private_key)
>>> print(public_key.encode("hex_codec"))
47f272a8dad703f809489dfc9ea3606e206ba6a16ecbde314186a03b68326284eaecd034af5300bb6991ac5897c8163ed67894205bc1b7dd5dac8080dba2fe69
```

### (3) 公開鍵からアドレスを生成する
このプロセスはこれまでと比較して少し複雑ですが、難しいことはしていないので一つづつ分解していきましょう。まず初めに、与えられた公開鍵の先頭に`\x04`を付与します（理由は不明です）。この接頭辞はMonacoin独自の値ではなく、Bitcoin, Litecoin共通の値であることに注意してください。

```python
pk_with_prefix = "\x04" + public_key
```

次に、この公開鍵に2つの一方向性関数`sha256`, `ripemd160`を適用して、160bitのハッシュへ変換します。

```python
ripemd160 = hashlib.new('ripemd160')
ripemd160.update(hashlib.sha256(pk_with_prefix).digest())
hash160 = ripemd160.digest()
```

次に、このハッシュの先頭に`\x32`を付与します。これによって、Monacoinのウォレットアドレスは`M`から始まるようになるので、ウォレットアドレスの種類を識別することが簡単になります。

```python
vhash160 = "\x32" + hash160  # monacoin addresses start with M
```

接頭辞の値は暗号通貨によってそれぞれ異なります。例えば、Bitcoinは`\x00`, Litecoinは`\x30`の値を取ります。なお、他の派生通貨の接頭辞を知りたい場合は、`src/base58.h`の`PUBKEY_ADDRESS`を参照してください。例えばMonacoinの場合、[`src/base58.h`](https://github.com/monacoinproject/monacoin/blob/master/src/base58.h)のソースコードは次のようになっています:

```cpp:src/base58.h
class CBitcoinAddress : public CBase58Data
{
public:
    enum
    {
        PUBKEY_ADDRESS = 50, // Monacoin addresses start with M or N
        SCRIPT_ADDRESS = 5,
        PUBKEY_ADDRESS_TEST = 111,
        SCRIPT_ADDRESS_TEST = 196,
    };
...
```

ソースコードでは`start with M or N`となっていますが[List of address prefixes](https://en.bitcoin.it/wiki/List_of_address_prefixes)ですと`\x32`は常に`M`を指すので、おそらくソースコードに間違いがあるものと思われます。

次に、この`\x32`を付与した(8+160)bitのハッシュの後ろに、アドレスを検証するために使うチェックサムを付与します。多くの暗号通貨は、ハッシュ関数`sha256`を2回適用した数列の先頭から32bitを切り出した値をチェックサムとして扱います。

```python
def _make_checksum_for_address(data):
    code = hashlib.sha256(hashlib.sha256(data).digest()).digest()
    return code[:4]
```

最後に、(8+160)bitのハッシュにチェックサムを付与した値を、[Base58](https://en.bitcoin.it/wiki/Base58Check_encoding)(0, Oなどの紛らわしい文字を除いた、58種類の文字でデータを表現する符号化形式)で符号化します。

```python
checksum = _make_checksum_for_address(vhash160)
raw_address = vhash160 + checksum
return base58_encode(raw_address)
```

長くなりましたが、最終的なPythonコードは次のようになります:

```python
def _make_checksum_for_address(data):
    code = hashlib.sha256(hashlib.sha256(data).digest()).digest()
    return code[:4]

def public_key_to_address(public_key):
    pk_with_prefix = "\x04" + public_key
    ripemd160 = hashlib.new('ripemd160')
    ripemd160.update(hashlib.sha256(pk_with_prefix).digest())
    hash160 = ripemd160.digest()
    vhash160 = "\x32" + hash160  # monacoin addresses start with M
    checksum = _make_checksum_for_address(vhash160)
    raw_address = vhash160 + checksum
    return base58_encode(raw_address)
```

実行結果は次のようになります:

```bash
>>> public_key_to_address(public_key)
MB3D45ngvaWRcACUmAFUf6fzcdXR8bVM6k
```

### (A) 秘密鍵からWIFを生成する
次に、秘密鍵からWIFを生成する方法について説明します。WIFの生成は次の手順で行います。まずはじめに、Monacoinは秘密鍵の先頭に接頭辞`\xb2`を付与します。接頭辞の値は暗号通貨によってそれぞれ異なります。例えば、Bitcoinは`\x80`, Litecoinは`\xb0`の値を取ります。

接頭辞の具体的な値は[`src/base58.h`](https://github.com/monacoinproject/monacoin/blob/master/src/base58.h)の`PUBKEY_ADDRESS`に依存します。具体的には、`PUBKEY_ADDRESS`に`128`を足した値が、接頭辞`PRIVKEY_ADDRESS`の値になります:

```cpp:src/base58.h
class CBitcoinSecret : public CBase58Data
{
public:
    enum
    {
        PRIVKEY_ADDRESS = CBitcoinAddress::PUBKEY_ADDRESS + 128,
        PRIVKEY_ADDRESS_TEST = CBitcoinAddress::PUBKEY_ADDRESS_TEST + 128,
    };
...
```

次に、この接頭辞を付与した秘密鍵の値の後ろに、秘密鍵を検証するためのチェックサムを付与します。多くの暗号通貨は、ハッシュ関数`sha256`を2回適用した数列の先頭から32bitを切り出した値をチェックサムとして扱います。

```python
def _make_checksum_for_wif(code):
    return hashlib.sha256(
        hashlib.sha256(code).digest()).digest()[:4]
```

最後に、チェックサムを付与した値を、Base58で符号化します。最終的なPythonコードは次のようになります:

```python
def _make_checksum_for_wif(code):
    return hashlib.sha256(
        hashlib.sha256(code).digest()).digest()[:4]


def private_key_to_wif(private_key):
    assert(len(private_key) == 32)
    checksum = _make_checksum_for_wif("\xb2" + private_key)
    return base58_encode("\xb2" + private_key + checksum)
```

実行結果は次のようになります:

```bash
>>> private_key_to_wif(private_key)
6ySkrpLpwm6gKsWo2aS6EL1SZxidZNdJkKqsKRNjXzv9WSrpHjR
```

### (B) WIFから秘密鍵を生成する
同様に、WIFから秘密鍵の生成に関しては前述した手順の逆を行うだけです。この手順をもう一度説明するのは冗長なので、下のPythonコードを見れば十分でしょう:

```python
def wif_to_private_key(wif):
    code = base58_decode(wif)
    prefix, private_key, checksum = code[0], code[1:33], code[33:]
    checksum_from_hex = _make_checksum_for_wif(prefix + private_key)
    assert(checksum == checksum_from_hex)
    return private_key
```

## 練習問題
これまでの解説で、秘密鍵からWIFフォーマットへの変換が出来るようになりました。後はこのWIFフォーマットを利用して、秘密鍵をMonacoinクライアントに取り込むだけです。具体的な取り込み方については[Bitcoin wiki](https://en.bitcoin.it/wiki/How_to_import_private_keys_v7%2B)の方法を参照してください。なお、wallet.datのバックアップは必ず取っておいてください。

最後に、これまでのおさらいとして簡単な練習問題を載せておきます。一番初めに解けた方は賞金を盗める特典付きです:)

> Monacoinのウオレットアドレス
> MPKWCip9CLawFKwwMBDTTp2ZWJcrkDf7rX
> の秘密鍵がコンピュータウィルスによって流出し、
> 9a833fd68f30459bd6f7b718818668c5c6d20b5a2b491558cea08be63937f847
> であることが分かった。この秘密鍵を利用して、上のアドレスに保管されている全額を奪取せよ。