ビットコイン技術入門 1/3（トランザクション編）

## はじめに
この記事では，ビットコインの基本的な仕組みを学んで，その技術に入門してみたいと思います．基本的な仕組みといってもひとつの記事で説明するには量が多すぎるので，内容を分割し，以下のように 3つの記事として書く予定です．

1. トランザクション編（この記事）
1. [データ構造・マイニング編](https://qiita.com/flare/items/54579a31204bb785c9dd)
1. ネットワーク編

「入門」の目安として，ビットコインの送金の仕組みが理解できることを目標にします．一連の記事を通して考える具体的な設定として，以下の状況を想定します．

- アリスがボブに 1BTC を送金する．

また，最初からすべてを正確に説明しようとすると，たくさんの新しい概念をいっぺんに突きつけることになり，入門者を殴り倒してしまいかねないので，簡単のため適宜ウソの説明をします．具体的には，台帳がテーブル構造で管理されていたり，中央集権的な管理者がいたりする場面があります．これらのウソは，新しい概念を導入するに従って徐々に訂正し，一連の記事の最後にはウソのない正確な仕組みをお目にかけられるよう努めます．

今回の記事では，ビットコインで利用されている基礎的な暗号技術と，トランザクション（送金取引）の仕組みを紹介します．

## 基礎技術の準備
（以下の「公開鍵暗号」「電子署名」の説明に関して指摘をいただいています．詳しくはコメント欄をご覧ください）
### 公開鍵暗号
メッセージを読解不能な文字列や図，数列等に変換し，特定の知識を持つ者にしかそのメッセージを理解できないようにする方法を **暗号（cypher）**と言います．一般に，誰にでも読解可能な元のメッセージのことを **平文（plaintext）**と言い，これを暗号に変換することを **暗号化（encryption）**，暗号化によって得られるものを **暗号文（cyphertext）**と言います．逆に，暗号文から平文を復元することを **復号（decryption）**と言います．

暗号化や復号に必要な知識を **鍵（key）**と言います．たとえば，$\mathtt{christmas}$ という平文があり，これを暗号化して得られた暗号文が $\mathtt{fkulvwpdv}$ であるとします．このとき，暗号化に用いた鍵は「各文字をアルファベット順で 3文字分後ろにずらす」です．復号のための鍵はその逆で「各文字をアルファベット順で 3文字前にずらす」です．このように，暗号化と復号に同一の（厳密には対称関係にある）鍵を用いる暗号方式を **共通鍵暗号（common key cryptosystem）**と言います．
共通鍵暗号が抱える重要な課題として，暗号文の受信者に事前に安全に鍵を配布しておかねばならないという問題があります．そうしないと，受信者は暗号文を復号することができないからです．どんなに堅牢で解析困難な鍵を設計しても，この配送の段階で第三者に鍵を知られてしまっては意味がありません．

**公開鍵暗号（public key cryptosystem）**は，このような問題を解決した暗号方式です．この暗号方式では，事前に通信相手に接触し，お互いだけで秘密の鍵をこっそり共有しておくという必要がありません．
公開鍵暗号方式では，**公開鍵（public key）**と **秘密鍵（private key/secret key）**という 2つの（非対称な）鍵を用います．名前の通り，公開鍵は公開し，秘密鍵は秘密にしておきます．公開鍵と秘密鍵は互いに対になっていながら，公開鍵から秘密鍵を推測することは困難であるという特殊な性質を持ち，公開鍵は暗号化に，秘密鍵は復号にそれぞれ使用します．
いま，アリスがボブに公開鍵暗号を使って秘密のメッセージ $M$ を送りたいとします．このとき，アリスは公開されているボブの公開鍵 $p_B$ を用いて平文 $M$ を暗号化し，暗号文 $C$ を得ます．この暗号文 $C$ は，ボブの公開鍵 $p_B$ で復号することはできません．$C$ を受信したボブは，自分の秘密鍵 $s_B$ を用いて $C$ を復号し，元の平文 $M$ を得ます．数学的に書くなら，対応する公開鍵 $p$ と秘密鍵 $s$ は以下の性質をすべてみたします（${\rm encrypt}$ と ${\rm decrypt}$ はそれぞれ暗号化と復号を行う関数）．

- ${\rm encrypt}(M, p)=C$，
- ${\rm decrypt}(C, p)≠M$，
- ${\rm decrypt}(C, s)=M$，
- $p$，${\rm encrypt}$，${\rm decrypt}$，$M$，$C$ から $s$ を特定することが困難である．

公開鍵暗号の仕組みを説明するにあたって，わかりやすいたとえとして南京錠があります．ボブの公開鍵 $p_B$ は，解錠された状態の南京錠です．これは誰でも施錠できますが，解錠するには，南京錠の鍵を持っていなければなりません．この「南京錠の鍵」が，ボブの秘密鍵 $s_B$ です．秘密のメッセージ $M$ をボブに送りたいアリスは，ボブが配布している南京錠をひとつ貰ってきて，$M$ を入れた箱に施錠します．この時点で，$M$ は秘匿され，施錠済みの箱 $C$ になります．$C$ を受け取ったボブは，彼だけが持つ鍵で南京錠を解錠し，箱の中のメッセージ $M$ を取り出します．

### 電子署名
ボブがある電子的なメッセージを受け取り，メッセージの文末には「アリスより」と書かれていたとします．しかし，文末に「アリスより」とタイプすることはアリスでない第三者でも簡単に行えるので，これだけでは本当にアリスからのメッセージなのか，ボブにはわかりません．
**電子署名（digital signature）**は，ある者がメッセージの作成者であるかを，それ以外の者が確認するための仕組みです．これは，上述の公開鍵暗号を応用することで実現できます．具体的には，暗号化と復号に使う鍵の公開・秘密を逆にします．すなわち，アリスは署名したいメッセージ $M$ を自分の秘密鍵 $s_A$ で暗号化し，暗号文 $D$ を作ります．この暗号文 $D$ はアリスの公開鍵 $p_A$ によってのみ復号でき，逆にアリスの公開鍵 $p_A$ で復号できるような暗号文は，アリスの秘密鍵 $s_A$ のみが生成可能です．そこで，メッセージを受け取ったボブはアリスの公開鍵 $p_A$ で $D$ の復号を試み，$D$ を正しく復号できれば，そのメッセージは本当にアリスが書いたものだと確認できます．
以降，秘密鍵による暗号化を **署名（sign）**，それによって作られた暗号文の復号を **署名の確認（verification）**と言います．電子署名に使われる公開鍵 $p$ と秘密鍵 $s$ は，以下の性質をすべてみたします（${\rm sign}$ と ${\rm verify}$ はそれぞれ署名と署名の確認を行う関数）．

- ${\rm sign}(M, s) = D$，
- ${\rm verify}(D, p) = M$，
- $p$，${\rm sign}$，${\rm verify}$，$M$，$D$ から $s$ を特定することが困難である．

ビットコインでは，電子署名として ECDSA を利用しています．

## ビットコインの取引の仕組み
### トランザクション
ビットコインのやり取りでは，硬貨や紙幣などの物体が物理的に移動することはありません．やり取りはあくまでデータの変更であり，より正確に言えば，「アリスがボブに 1BTC を送金する」ことは，「アリスが自分の持つ 1BTC を使用する権利を消費し，ボブに 1BTC を使用する権利を付与する」ことです．この使用権の移譲（使用権を消費し，使用権を付与する）を **トランザクション（transaction）**または **取引** と言います．
いま，アリスが 1BTC の使用権を消費し，ボブに 1BTC の使用権を付与したいとします（一連の記事を通して考える設定です）．これは以下のようにして実現されます．

|ビットコインの送金（ver.1）|
|:---|
|${\texttt 1.}$ アリスが「アリスからボブに 1BTC を送金」というトランザクションを提示する．<br>${\texttt 2.}$ ビットコインの管理者が提示されたトランザクションを承認する．|

「ビットコインの管理者」と書きましたが，ビットコインは分散システム（非中央集権システム）で管理されるため，誰か特定の人物や団体が管理しているわけではありません（ビットコインの分散システムに関しては「ネットワーク編」で紹介します）．この管理者とは，言うなればビットコインを利用するコミュニティ全体です．
コミュニティはアリスの提示するトランザクションを承認するため，そのトランザクションが正しいものか確認します．これは，次の 2つの事柄を確認することでなされます．

- アリス以外の誰か（たとえばボブ）がなりすまして提示していないか．
- アリスが 1BTC の使用権を持っていないのに，それを消費しようとしていないか．

ビットコインでは，前者の確認のために電子署名を，後者の確認のために台帳（取引記録）を利用します．

### 電子署名と識別情報
ビットコインでは，使用権を消費する者（ビットコインを送る側）によってトランザクション内容が署名されます．アリスがボブに送金するなら，そのトランザクションはアリスによって署名されているので，人々はアリスの公開鍵で署名の確認を行うことで，アリス以外の誰かがなりすましていないことを確認できます．

ところで，アリスやボブの持つ公開鍵は，ビットコインにおける彼らのアカウント（口座）の ID と見なすことができます．実際，ビットコインではユーザーの識別情報として「アリス」や「ボブ」といった名前ではなく，彼らの持つ公開鍵を利用しており，トランザクション内容は「公開鍵 $p_A$ から公開鍵 $p_B$ に $x$ BTC を送金」のように書かれます[^1]．署名も「アリスによる署名」ではなく「公開鍵 $p_A$ による署名」になるため，「アリス」というユーザーを探し出してその公開鍵を特定する必要はなく，署名者として提示された公開鍵 $p_A$ を使ってその場で署名の確認を行えます．

### 台帳
ビットコインの **台帳（ledger）**とは，これまでに承認されたビットコインのトランザクションが必要十分に記録されたものです．言い換えれば，あるトランザクションが承認されるとは，そのトランザクションがビットコインの台帳に追記されることを意味します．ビットコインの管理者とはすなわち台帳の管理者であり，ビットコインが分散システムで管理されているというのは，この台帳が分散システムで管理されていることを意味します．分散管理に関しては「ネットワーク編」で説明するとして，ここではまず簡単のため，台帳がひとつしかなく，権限のある 1人の管理者によって管理されているかのように話します．

台帳という代物を簡単に図示してみると，下の表のようになります（これは単に概念を可視化しただけであり，実際のビットコインがテーブル構造で台帳を管理しているわけではありません）．各行がひとつのトランザクションを表し，トランザクションは承認された順に時系列で並んでいます．この台帳を使って，いま 1BTC を送金しようとしているアリスが，本当に 1BTC 分の使用権を保持しているか確認することを考えます．

|ID|Contents|Public key|
|---:|:---:|:---:|
|0|$p_0$ による署名済みのトランザクション内容|公開鍵 $p_0$|
|1|$p_1$ による署名済みのトランザクション内容|公開鍵 $p_1$|
|2|$p_2$ による署名済みのトランザクション内容|公開鍵 $p_2$|
|$\cdots$|$\cdots$|$\cdots$|
|$n$|$p_m$ による署名済みのトランザクション内容|公開鍵 $p_m$|

図 1：簡単な台帳の様子．

おそらく最初に思いつくのは，口座ベースの方法です．すなわち，その時点でアリスが使用権を保持するビットコインの総額（つまり残高）を計算して，それが消費しようとしている 1BTC 以上あるのかを確認するものです．
しかしながら，ビットコインではこの方法は使われません．この方法では，アリスのものを含むあらゆる口座の残高を管理しておくデータ構造が必要ですが，その保持や更新のためのコストが大きすぎるからです．もちろん，そうしたデータ構造を構築せず，都度台帳を調べてアリスの口座残高を計算することも可能です．しかし，それではアリスがトランザクションを提示するたびに，台帳をひっくり返して過去にアリスの口座に影響を与えたすべてのトランザクションを調べることになり，大変非効率です．

代わりに，ビットコインでは取引ベースの方法が使われます．これは以下の 2つの事柄を確認するものです．

- いまアリスが消費しようとしている 1BTC（の使用権）がどこから来たのか．
- その 1BTC（の使用権）がまだ消費されていないか．

アリスが本当に 1BTC を所有している（あるいはしていた）なら，誰かが以前の取引でアリスに 1BTC を送金しているはずで，そのことを示すトランザクションが台帳に記録されているはずです．同時に，アリスが受け取ったその 1BTC を誰かに送金したトランザクションが台帳に記録されていないければ，アリスは現在，たしかに 1BTC を所有していると言えます．
この取引ベースでの確認を容易にするため，以下で説明するように，各トランザクション内容は入力と出力から成る形式で記述されます．

### トランザクションの入力と出力
各トランザクションにおける，送金先と送金額の情報を **出力（output）**と言います．いまアリスが提示しているトランザクション「アリスからボブに 1BTC を送金」なら，「ボブに 1BTC」がその出力です．
ビットコインでは，送金者はトランザクションを提示するとき，過去のあるトランザクションの出力の情報をそれに含めます．これをトランザクションの **入力（input）**と言います．入力に指定するのは，自分がいま消費する分の使用権を自分に付与した出力です．
たとえば，以前の取引記録としてキャロルからアリスへ 1BTC を送金したトランザクション $T_C$ があり，その中の該当する出力の ID が $X$ なら（入力や出力は複数持つことができます．後述），いまボブに 1BTC を送金したいアリスは，トランザクションの入力として $T_C[X]$ を提示します．台帳の管理者はトランザクション $T_C$ を台帳で調べ，その中の ID が $X$ の出力を見て，実際にキャロルがアリスに 1BTC を送金したことを確認します．さらに，台帳にある $T_C$ よりあとのトランザクションを走査して，アリスがその 1BTC を誰かに送金したトランザクション（これは $T_C[X]$ を入力として提示しているはずです）が存在しないことを確認します[^2]．

電子署名，および台帳を用いた取引の追跡により，アリスが提示したトランザクションが無事承認されると，そのトランザクションは台帳の末尾に追記され，台帳が以下のように更新されます（$p_A$ はアリスの公開鍵）．

|ID|Contents|Public key|
|---:|:---:|:---:|
|0|$p_0$ による署名済みのトランザクション内容|公開鍵 $p_0$|
|1|$p_1$ による署名済みのトランザクション内容|公開鍵 $p_1$|
|2|$p_2$ による署名済みのトランザクション内容|公開鍵 $p_2$|
|$\cdots$|$\cdots$|$\cdots$|
|$n$|$p_m$ による署名済みのトランザクション内容|公開鍵 $p_m$|
|$n+1$|$p_A$ による署名済みのトランザクション内容|公開鍵 $p_A$|

図 2：簡単な台帳の様子（更新後）．

また，公開鍵 $p_A$ で署名の確認を行うと，いま ID $n+1$ のトランザクション内容には以下の情報が記述されています（$p_B$ はボブの公開鍵）．

- 入力：$T_C[X]$，
- 出力：$p_B$ に 1BTC．

ここまでに得た知識を使って，ビットコインの送金プロセスを少し詳しく書き直すと，次のようになります．

|ビットコインの送金（ver.2）|
|:---|
|${\texttt 1.}$ アリスがボブに 1BTC を送金するトランザクションを用意する．<br>${\texttt 2.}$ アリスがトランザクションに署名し，自分の公開鍵と併せて提示する．<br>${\texttt 3.}$ ビットコインの管理者がトランザクションを検証する．<br>${\texttt 4.}$ ビットコインの管理者がトランザクションを台帳に追記する．|

### コインの統合と分割
たとえば，アリスが異なる 2つの取引でビットコインを受け取ったとします．片方で 1BTC，もう一方で 2BTC 受け取ったとすると，いまアリスの持つ総額は 3BTC です．
上でほのめかしたように，トランザクションは複数の入力を持つことができます．アリスは 3BTC を同時に使いたいと思ったら，提示するトランザクションに 2つの入力（1BTC を受け取ったものと 2BTC を受け取ったもの）を指定することで，コインを統合することができます．

一方で，トランザクションは出力も複数持つことができます．これにより，コインを分割することができます．すなわち，「入力に 3BTC を指定し，そのうち 1BTC をボブに，2BTC をキャロルに送金」ということが可能です．送金先のひとつに自分を指定すれば，おつりを受け取ることもできます．

当然，各トランザクションにおける入力の総額と出力の総額は同じである必要があります．管理者はトランザクションを承認する際，このことも確認します．

### コインベーストランザクション
ビットコインには，入力に何も指定しない特殊なトランザクションがあります．これを **コインベーストランザクション（coinbase transaction）**と言います．これは新しいコインを作るためのトランザクションです．出力先を自分に指定したコインベーストランザクションを提示し，承認されることで，無から新しいコインを生み出し，自分の物にすることができます．
しかし，当然，誰もが好きなだけコインベーストランザクションを発行できるわけではありません（提示しても承認されません）．条件をみたす必要があり，かつ一度に生産できる額も決まっています．詳しくは，次回「データ構造・マイニング編」で説明したいと思います．

ビットコインにおいて，新しいコインを作るための手段はコインベーストランザクションを発行することしかありません．ゆえに，あらゆる（コインベーストランザクションでない）トランザクションは，その入力をたどっていくことで，何らかのコインベーストランザクションに行き着きます．

## おわりに
今回はビットコイン取引の基本的な仕組みを紹介しました．この記事の要点は以下の通りです．

- トランザクションは，ビットコインの使用権の移譲（すなわち送金取引）であり，入力と出力から成る．
- 台帳は，これまでに承認されたトランザクションが必要十分に記録されたものである．
- トランザクションは，署名の確認と台帳の取引ベースな追跡によって検証される．
- ビットコインの送金は（現時点での知識では）以下のように行われる．

|ビットコインの送金（ver.2）|
|:---|
|${\texttt 1.}$ アリスがボブに 1BTC を送金するトランザクションを用意する．<br>${\texttt 2.}$ アリスがトランザクションに署名し，自分の公開鍵と併せて提示する．<br>${\texttt 3.}$ ビットコインの管理者がトランザクションを検証する．<br>${\texttt 4.}$ ビットコインの管理者がトランザクションを台帳に追記する．|

「はじめに」でウソをつくと宣言しましたが，この記事で用いた機構は簡略化されており，実際のビットコインの構造とは異なる部分があります．
まず，ビットコインは台帳を上のようなテーブル構造で管理するわけではありません．実際には，ビットコインは Merkle tree をブロックチェーンに組み込んだデータ構造を使って台帳を実現しています．これについては，次回「データ構造・マイニング編」で紹介したいと思います．
さらに，台帳は分散システムで管理されています．すなわち，権限のある特定の個人や団体が管理しているわけではなく，ビットコインの利用者すべてが台帳を管理しています（より正確には，管理する権限を持っています）．このために，トランザクションの承認と台帳への追記はもう少し複雑になります．これについては，次々回「ネットワーク編」で紹介したいと思います．

誤字や内容の間違いがありましたらご指摘ください．
お疲れさまでした．

次回：[ビットコイン技術入門 2/3（データ構造・マイニング編）](https://qiita.com/flare/items/54579a31204bb785c9dd)

[^1]: 公開鍵は大きいので，実際には公開鍵のハッシュ値が用いられます．これはアドレスと呼ばれ，ビットコインの送付先としてよく目にするQRコードやテキストは，このアドレスを表したものです（テキストはアドレスを base-58 記法で表現したもの）．
[^2]: 台帳を先頭から調べるわけではないので，口座ベースの方法において残高管理のためのデータ構造を用意しない場合よりも，確認処理は効率良く行えます．一方で，この走査処理を回避してさらに効率を良くするために，未使用のトランザクション（の出力）を管理するデータ構造を用いることが多いです．しかしこのデータ構造にしても，口座ベースの方法で利用するあらゆる口座を管理するデータ構造よりは，はるかに少ないコストで運用することができます．