勉強会でビットコインの元論文(Nakamoto, 2008)を読んだときのレジュメを公開してみる。
自分も含め誰も詳しく知らない分野のため、レジュメは要約することよりもむしろ議論のディテールが把握できるような構成をこころがけた。
ところどころ用語や言い回しが変だったり、表現が不正確だったりするところがあると思うのでご指摘いただければ。
なお元の論文についてはhttps://bitcoin.org/ から入手可能。
ビットコイン：P2Pを用いた電子通貨システム
Abstract A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending. We propose a solution to the double-spending problem using a peer-to-peer network. The network timestamps transactions by hashing them into an ongoing chain of hash-based proof-of-work, forming a record that cannot be changed without redoing the proof-of-work. The longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power. As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network, they'll generate the longest chain and outpace attackers. The network itself requires minimal structure. Messages are broadcast on a best effort basis, and nodes can leave and rejoin the network at will, accepting the longest proof-of-work chain as proof of what happened while they were gone.
要旨：純粋にPeer-to-Peer方式である電子通貨は金融機関を仲介することなく二者間の直接のオンライン決済を可能にする。この方式には電子署名が重要な役割を果たしているが、二重支払を防ぐために信頼できる第三者のような存在を必要とするのであれば、[仲介者を必要としないという]主要な利点が失われてしまう。[そこで]我々はPeer-to-Peerネットワークを用いて二重支払問題を解決する方式を提案する。ネットワークは取引をハッシュ化し、現在進行形で伸長するハッシュベースのProof of Workのチェーンに記録することで、取引とその時刻を記録する。これはProof of Workを再実行しなければ変更することのできない記録となる。最長のチェーンは一連の取引の証拠として機能するだけでなく、それが[数あるチェーンの中で]最大のCPU パワーの集積によって作られたものであるということを担保する。CPUパワーの過半数が攻撃者のコントロール下にない限り、ネットワークは最長のチェーンを更新し続け、攻撃者[の計算能力]を凌駕し続ける。ネットワーク自体は最小限の構造しか要求しない。[ノード間の]メッセージはベストエフォートベースで広められる。最長のProof of Workのチェーンの記録を採用するため、ノードは随意にネットワークを離脱したり再接続したりできる。
イントロダクション
基礎知識①：ハッシュ関数
ハッシュ関数を用いた認証手順の例自分も含め誰も詳しく知らない分野のため、レジュメは要約することよりもむしろ議論のディテールが把握できるような構成をこころがけた。
ところどころ用語や言い回しが変だったり、表現が不正確だったりするところがあると思うのでご指摘いただければ。
なお元の論文についてはhttps://bitcoin.org/ から入手可能。
Nakamoto, S. (2008): Bitcoin: A Peer-to-Peer Electronic Cash System
ビットコイン：P2Pを用いた電子通貨システム
Abstract A purely peer-to-peer version of electronic cash would allow online payments to be sent directly from one party to another without going through a financial institution. Digital signatures provide part of the solution, but the main benefits are lost if a trusted third party is still required to prevent double-spending. We propose a solution to the double-spending problem using a peer-to-peer network. The network timestamps transactions by hashing them into an ongoing chain of hash-based proof-of-work, forming a record that cannot be changed without redoing the proof-of-work. The longest chain not only serves as proof of the sequence of events witnessed, but proof that it came from the largest pool of CPU power. As long as a majority of CPU power is controlled by nodes that are not cooperating to attack the network, they'll generate the longest chain and outpace attackers. The network itself requires minimal structure. Messages are broadcast on a best effort basis, and nodes can leave and rejoin the network at will, accepting the longest proof-of-work chain as proof of what happened while they were gone.
要旨：純粋にPeer-to-Peer方式である電子通貨は金融機関を仲介することなく二者間の直接のオンライン決済を可能にする。この方式には電子署名が重要な役割を果たしているが、二重支払を防ぐために信頼できる第三者のような存在を必要とするのであれば、[仲介者を必要としないという]主要な利点が失われてしまう。[そこで]我々はPeer-to-Peerネットワークを用いて二重支払問題を解決する方式を提案する。ネットワークは取引をハッシュ化し、現在進行形で伸長するハッシュベースのProof of Workのチェーンに記録することで、取引とその時刻を記録する。これはProof of Workを再実行しなければ変更することのできない記録となる。最長のチェーンは一連の取引の証拠として機能するだけでなく、それが[数あるチェーンの中で]最大のCPU パワーの集積によって作られたものであるということを担保する。CPUパワーの過半数が攻撃者のコントロール下にない限り、ネットワークは最長のチェーンを更新し続け、攻撃者[の計算能力]を凌駕し続ける。ネットワーク自体は最小限の構造しか要求しない。[ノード間の]メッセージはベストエフォートベースで広められる。最長のProof of Workのチェーンの記録を採用するため、ノードは随意にネットワークを離脱したり再接続したりできる。
1. Introduction
イントロダクション
- 旧来のインターネット取引：信頼(trust)ベースのモデル
- 信頼できる第三者(trusted third party)が必要
- 不可逆的な（＝記録を改竄できない）取引には「信頼できる第三者」が必要。ただし：
- 仲介の問題を避けて通れない
- 仲介のための費用が増大
- 最小の取引量があるなどの制限がある
- 暗号学的な証明システムが信頼ベースのシステムに替わって必要
- 計算論的に改竄が困難であることを利用
2. Transaction
（発表者による補足）基礎知識①：ハッシュ関数
- 値を入力すると一定長のデータを出力する関数。
- 同じ値を入れればいつでも同じ値が出てくる
- 一方向性を持つ
- 入力$x$と出力$f(x)$について、$x$から$f(x)$を求めるのは容易であるが、$f(x)$から$x$を復元・推測することはできない
- $x$がわからなければ、$f(x)$を生成できない
- クライアント：idとパスワード$a$を持つ
- システム： 入力された値$a$からハッシュ値$f(a)$を計算
- サーバ：idとハッシュ値$f(a)$の組をデータベースに保管
- 手順：
- 認証時にクライアントはidとパスワード$a$をシステムに入力
- システムは$f(a)$を計算し、idと一緒にサーバに渡す
- サーバは登録されているidとハッシュ値の組を確認、正しければ認証
- 利点 サーバが破られても$a$の値は洩れない（洩れるのは$f(a)$の値のみ）→パスワードそのものを保存していないので安全
- これは印章（判子）と印影の関係に似ている
- クライアント：いつでも印影（ハッシュ）を発行できることで自分が印章（パスワード）の持ち主であるということを証明
- サーバ：登録された印影が正しいかを比較することで、印章の正しさを確認。印章そのものを持っているわけではないので、印影を再発行することはできない。
基礎知識②：公開鍵暗号
- 安全に通信をするための暗号方式
- 鍵をかける鍵と、 鍵を開ける鍵からなる 二つの鍵はセットになっている
- 事前に鍵をかける鍵を公開しておく（公開鍵: Public Key）
- メッセージの送り手は公開鍵を用いてメッセージを暗号化して受け手に送る
- 受け手は自分だけが持っている鍵(秘密鍵: Private Key)でメッセージを復号化する
- 暗号化されたメッセージは公開鍵では復号することができないので、メッセージが洩れても大丈夫
- 認証の場合は手順が逆になる；
- 事前に鍵を開ける鍵を公開しておく（公開鍵）
- 送り手は自分だけが持っている鍵（秘密鍵）でメッセージを暗号化して受け手に送る
- 受け手は公開鍵を用いてメッセージを復号化する
- その公開鍵で復号できるのは送り手の持っている秘密鍵だけなので、送り手の真正性が立証される
取引
- 電子署名のチェーンとして電子的なコインを定義する
- （チェーンの一番新しい位置にいる人物がコインを所有しているとみなす）
- 所有者①から所有者②に所有権が移転した場合について考える
- 前回の取引内容と所有者②の公開鍵でハッシュを生成する
- これを所有者①の秘密鍵で暗号化し、署名とする
- 所有者①の公開鍵を用いて、署名を検証できる
- （所有者①が電子署名することによって所有権が移転したことを担保する）
- 問題点：受取人は、コインが二重払いされていないこと（＝それ以前に使用されていないこと）を検証できない
- 受取人が、コインの前の保有者がそれ以前にコインを使用していないことを検証できる仕組みがいる
- →所有権が移転してからの最初の取引だけ着目すればよい （一度使われたコインの二回目以降の取引はすべて無効とすればよい）
- 旧来の解決手段：造幣局（Mint）の導入
- すべての取引を監視、複数支払があった場合、最初に行われた取引だけを有効なものとして認める
- ただし、中央集権的になってしまう
- 信頼できる第三者が存在しない場合：取引をネットワークに公表(Publicly Announced)する
- 取引の履歴ががただひとつに定まるようなシステムが必要
3. Timestamp Server
- タイムスタンプサーバ
- ハッシュを公開
- ブロック（いくつかの取引の記録）をタイムスタンプとともにハッシュ化して知らせる
- 時点$t+1$のハッシュ： 時点$t$のブロックとTimestampをハッシュ化したもの
- あるデータがある時間に存在したことを証明
- 各タイムスタンプはひとつ前のタイムスタンプをハッシュとして含むので、チェーン構造になっている
4. Proof of Work
クライアント側のコストを上げることによって攻撃を不利にする仕組み cf. HashCash
リクエストの処理に一定（以上）の作業を要求する
- BitcoinにおけるProof of Work：ブロックを追加（登録）するための作業
- 一定以上の数のゼロの連続から始まるハッシュ値を探索する
- ナンス(nonce)と呼ばれる数字を変更し、ブロック全体のハッシュ値が条件を満たすようにする
- いわば$f(data+nonce)$=(条件をみたすハッシュ)となるnonceを求める作業
- 平均的な計算量は指数的に増加（総当たり的な探索）
- チェーンを再生成（改竄）するにはすべての計算を繰り返さないといけない
- （注：Proof of Workを達成したブロックのみが次のブロックとして認められる。追加したブロックがチェーンに受け入れられれば報酬がある）
- （正しいチェーンを決める）多数決の方法
- Proof of Workを使うことで、どれを正しいチェーンとして認めるかという問題が解決する
- 投票の方法
- ×IPベース（IPひとつにつき一票）
- 大量のIPを持っているものが有利
- ○CPUベース（CPUパワーに応じた投票）
- 最長のチェーンを選ぶようにすればよい（改竄するには過半数を超えるCPUパワーが必要になる）
- 最長のチェーンを保持するには最大のProof of Workが必要
- honest nodeが過半数ならば、honest chainがもっともよく伸びる
- 過去のブロックを修正するためには（現在進行形で伸張する最長のチェーンを上回るスピードで）ブロックのProof of Workを繰り返し、続くチェーンをすべて改竄しないといけない
5. Network
ネットワークの仕組み
- 新しい取引はすべてのノードに伝えられる
- それぞれのノードはブロックに新しい取引の情報を保管する
- それぞれのノードは、そのブロック内のProof of Workを見つけようとする
- ノードがProof of Workを見つけると、ブロックをすべてのノードに伝達する
- ノードは、ブロック内の取引が有効であり（そのブロックが）未使用である場合のみブロックを受け入れる
- ノードは受け取ったブロックを用いてチェーンに新しいブロックを作り出し、ブロックを受け入れたということを示す
- ノードは常に最長のチェーンを正しいものとしてみなし、伸ばし続ける
- タイになったら次のProof of Workが見つかるまで両方のブロックを保持して作業し、いずれか長くなった方のブロックに移動する
- 新しい取引はすべてのノードに届かなくても大丈夫
- 多くのノードに届けばいつか届く
- メッセージの欠落にも寛容
- ノードがブロックを受け取り損ねても、次のブロックを受け取ったときにないことに気付ける
6. Incentive
インセンティブ
- ブロックの最初の取引で、ブロックを作成した人に新しいコインが渡される
- 参加者がネットワークを支持するインセンティブになる
- 採掘：貨幣の発行と同じ効果→貨幣を発行する中央当局がいらない
- ブロックに取引を追加するための手数料(transaction fee)を導入することによって、ブロックを採掘するインセンティブを保つことができる。（注：手数料を支払うと、より早く取引が処理される、という仕組みがある）
- コインが採掘され終わると取引費用の方に主要なインセンティブは移るだろう
7. Reclaiming Disk Space
ディスクの再利用
新しいコインがブロックで埋まってくると、以前の取引を破棄してディスクスペースを開放する。取引はマークル木(Merkle Tree)の形で保管されており、ブロックのハッシュはマークル木のルート（根）ハッシュのみが含まれる→ブロックのハッシュを破壊せずに、古いブロックのデータを削減できる。
（発表者による補足）
$ T_{x0},T_{x1},T_{x2},T_{x3} $の４つの取引の記録がハッシュ値($Hash0, Hash1, Hash2, Hash3$)としてそのまま保存されていた場合、全体を検証するためにはすべての値を調べなければならず、非効率。 そこで、それぞれのハッシュをもとにハッシュを作るというハッシュ木（マークル木）を作成する
$Hash01=f(Hash0+Hash1)$
$Hash23=f(Hash2+Hash3)$
$RootHash=f(Hash01+Hash23)$
このRootHashの値が同じかどうかを調べれば、ブロックに含まれる取引の値が同じかどうかを効率的に調べることができる。
※出力が違うならば入力が異なっている $\iff$入力が同じならば出力が同じである（ハッシュ関数の性質）
（補足ここまで）
なおブロックは十分に小さいので、メモリに格納することになっても問題にならない
簡略な支払いの検証
価値の統合と分割
プライバシー
（改竄することの困難性についての計算。割愛）
まとめ
本論文：信頼によらない電子取引システムを提案
従来の電子署名方式→所有権に関しては堅牢、二重支払に関しては脆弱
提案した手法：
（以上）
※出力が違うならば入力が異なっている $\iff$入力が同じならば出力が同じである（ハッシュ関数の性質）
（補足ここまで）
なおブロックは十分に小さいので、メモリに格納することになっても問題にならない
8. Simplified Payment Verification
簡略な支払いの検証
- すべてのチェインのノードを走査せずに支払いを検証することが可能
- 検証方法：ユーザーは最長のチェーンのブロックヘッダを持っていればよい
- 最長のチェーンを検索し、取引に対応するタイムスタンプの入っているマークル枝を見つければよい
- ネットワークがその取引を（正しい記録として）受け入れたということが確認できる
- ネットワークが誠実なノードのコントロール下にあれば真正性を証明できる
- ただし攻撃者が膨大な計算量を保持し続けている場合には脆弱性がある
- 改竄が行われていないか検知する仕組みが必要になる
- 最長のチェーンを検索し、取引に対応するタイムスタンプの入っているマークル枝を見つければよい
9. Combining and Splitting Value
価値の統合と分割
- 複数の入出力があれば、価値を分割・統合することが可能
10. Privacy
プライバシー
- 銀行におけるプライバシーの確保：銀行自体は個人情報を集めるが、他のユーザーに情報のアクセスを制限させることでプライバシーを守る
- Bitcoin：公開鍵（認証鍵）を匿名にすることで、個人と取引の結びつきをわからなくする
- 取引がされていることはわかるが、それが誰と誰の間のものかはわからない
11. Calculation
（改竄することの困難性についての計算。割愛）
12. Conclusion
まとめ
本論文：信頼によらない電子取引システムを提案
従来の電子署名方式→所有権に関しては堅牢、二重支払に関しては脆弱
提案した手法：
- Peer to PeerネットワークとProof of workを用いて取引履歴を記録
- CPUパワーの過半数が誠実なノードにある限り改竄は計算論的に実行困難
- ネットワークはシンプルなのでロバスト 協調不要 個人の特定も不要
- ノードの接続・離脱は随時可能
（以上）
