Coursera: 仮想通貨とビットコイン Week1

o3c9

7 minute read

Coursera の Bitcoin and Cryptocurrency Technologies を受講しはじめた。一攫千金を狙う亡者たちが騒いでいるのをよそ目に、ビットコインやブロックチェーンに使用されている技術をきちんと学びたいと思う人に強くおすすめできる内容だ。

講座はプリンストン大学の講師陣によるもので、教科書はこちら。

日本語訳も出ている。

ちなみに、ドラフト版であれば、探せばインターネットでも公開されている。

第一週から課題があり、Scrooge コインという学習用の Coin を使って、取引を承認する部分を実装することになる。課題は Java で書かれていたが、シンプルな実装なので 5 年越しの Java でも特に苦労はなかった。

以下に、講義メモを残しておく。

概要

1 暗号技術

  • ハッシュ関数
  • デジタル署名
  • アイデンティティとしての Public Key

2 仮想通貨

  • Goofy コイン
  • Scrooge コイン

1 暗号技術

ハッシュ関数

あらゆる長さの文字列を入力として受け付け、決まった長さ(256bit, 512bit)の文字列を返す関数。効率よく計算できることが重要である。

ハッシュ関数のセキュリティ要件

  1. collision-free:

H(x) = H(y)となるような x と y を事実上見つけることができないこと。あらゆるハッシュ関数で、collision-free だと証明されたものはないけれど、理論的に現代のコンピュータすべてを使っても宇宙創成から現在までの時間以上に計算時間がかかると説明されているものはある。

ハッシュは大きなファイルなどのダイジェストとして使われる。

  1. hiding:

H(x)から x を導き出せないこと。このとき、たとえば、x が「裏」「表」しか取らない場合は H(“裏”), H(“表”)を試せばいいだけなので、簡単に推測できてしまう。

そのため、r という非常によく分散されている性質を持つ（＝ high min-entropy）鍵を x に連結する。これを r|xと表記する。

H(r|x)から x を導き出せないことが、hiding 要件となる。

hiding のアプリケーション例

Commitment API

  • あるメッセージを封筒に入れて、封をする
  • 封があるので、他の人はメッセージを読めない
  • 封を解除し、メッセージを見たとき、それが改ざんされていなかったことを確認できる

あるメッセージを封筒に入れて、封をする

(commitment, key) := commit(msg) := (H(key | msg), key)
where key is a random 256bit value and publish `commitment`

commitment が封をされた封筒であり、これは公開してもよい。

封を解いてメッセージを受け取った人は、そのメッセージが改ざんされていなかったことを確認する。

match := verify(commitment, key, msg) := H(key | msg) == commitment

異なるメッセージである msg’について、verify(commit(msg), msg')が事実上常に false を満たす必要がある。

  1. puzzle-friendly

k を high min-entropy な分布を持つ集合から選んだとき、任意の hash 値 y を出力するような x を見つけ出すことが困難であること。k と y が判明したとしても、x を解明する方法は、ランダムに試すよりいいものがないということ。

puzzle-friendliness のアプリケーション例: Search puzzle

y = H(id | x) ∈ Y

n-bit のハッシュ値を出力する Hash 関数 H がある。id が high min-entropy な分布を持つ集合から ランダムに与えられたときに、Y の中に含まれるハッシュ値が出力となるような x を、ランダムに試すよりも簡単に見つけることができるだろうか。

この特性を利用しているのが、bitcoin の Proof of work である。 bitcoin の場合、先頭に 0 が n 個続くような hash 値を出力する入力を探索することがマイニングのタスクとなっている。

代表的なハッシュ関数: SHA256

メッセージを 512 ビットのブロックに区切り、はじめのブロックを c という圧縮関数にかけ、その結果(（256bit）と次のブロックをまた c にかける。これを最後のブロックまで続けることで、最終的な hash が生成される。c が collision-free であれば、全体もまた collision-free となる。

ハッシュポインタとデータ構造

LinkedList や Tree などの構造をハッシュポインタを用いて構築する.

tamper-evident である(改ざん不能). あるノードの data を改ざんした場合、そのノードの hash を持つ、次のブロックの previousHash も変えなくてはいけない。次のブロックの previousHash を変更すると、そのブロックの hash も変わるため、結局後続のノードすべてをアップデートする必要がある。これが改ざんに強い理由である。

Merkle Tree Binary-search tree built with Hash ポインタ。 O(log n)でメンバーの検証ができる。

ソート済み Merkle Tree O(log n)で非メンバーであるかの検証ができる。

データ構造がサイクルを持たない限りは、ハッシュポインタを用いることができる。このデータ構造は、ブロックチェーンやビットコインの分散データストアで使われている。

デジタル署名

  • 本人だけが署名でき、誰もが正しい署名か検証できること
  • 署名は特定の書類に紐付けられており、他の書類に移すことはできない
(sk, pk) := generateKeys(size)
sk = secret signing key
pk = public verification key

sig := sign(sk, message)

match := isValid(pk, message, sig)

メッセージが改ざんされていた場合、署名をつかっての検証に失敗するというのがみそ。思考実験として、pk だけをもつ attacker がメッセージを改ざんできるか検証する。 attacker が任意のメッセージの signiature を見ることができるとして、果たして、新しいメッセージとその署名のペアを生成することができるか。この可能性が無視できるほど低いことを、偽造不可能(unforgibility)とよぶ

実践 Tips

  • generateKeys はランダムの要素を含むべき。そのためには、優秀な乱数生成器が必要である
  • 署名できる message のサイズには上限があるが、その場合は message の hash を使えばいい
  • hash ポインタと signature を組み合わせると、ブロックチェーン全体のメッセージに対して署名したことになる
  • Bitcoin では、ECDSA という署名アルゴリズムを用いている。
  • 高度な数学に基づいている
  • 良質な乱数が重要である: 予測可能なランダムネスはセキュリティホールとなる

アイデンティティとしての Public Key

  • pk は、public “name"である。(H(pk)を使う方がよりよい)
  • sk は、自分がその name の持ち主であるという identity を証明するものとなる

Bitcoin では、この pk name のことを address とよんでいる。この方法だとユーザー管理のために centalized な仕組みは不要であり、もし必要であれば、一人の人がいくつもの name を所有することができる。

現実の人間とこの identity は紐付いていないため、匿名性は保たれるが、この identity の行動やイベントを経時的に観測することで、この identitiy がだれなのか、外から推測することは可能になることもある。

2 仮想通貨

GoofyCoin - 最もシンプルな仮想通貨

  • Goofy はコインを生成できる
  • ここでのコインとは、“CreateCoin [uniqueCoinID]“というメッセージと、この文字列の Goofy によるデジタル署名で構成されている
  • 生成されたコインは Goofy のものとなる
  • コインの妥当性は、Goofy の署名とメッセージを検証することで確認できる
  • コインを持っている人は別の人に譲渡できる
  • コインを渡すとは、“Pay [coin] to [pk]“というメッセージをつくり（coin は、元のコインへの hash ポインタであり、pk とは新しい所有者の pk）、Goofy の署名を添えること。
  • メッセージと Goofy の署名がそろったら、新しい所有者はコインが自分のものであると宣言できる。
  • さらにコインを消費するには、また別の"Pay [coin] to [pk]“メッセージをつくり、元の所有者が署名をすればよい。

ただし、Goofy コインには致命的な欠陥がある。それは、、、

ダブルスペンド攻撃

  • 同じコインを複数にわたって使用すること

仮想通貨の設計において、このダブルスペンド対策がもっとも重要になる。GoofyCoin にはこの対策がないため、Alice は自分のコインを何度も使用できてしまう。

ScroogeCoin

  • Scrooge では取引履歴をブロックチェーンに保存し、改ざんできないように Scrooge によって署名されている。
  • 公開されているので、だれもが verify できる

CreateCoins トランザクション

  • 新しいコインを生成する
  • num : シリアルナンバー in Transaction
  • value :
  • recipient
  • coinID = TransactionID(num)
  • Scrooge だけが生成できる

PayCoins トランザクション

  • コインを他の人に譲渡する
  • consumed coin IDs: このトランザクションで消費されたコイン ID
  • 代わりに新しい recipient 名で createCoins する
  • このトランザクションが valid なのは、
  • 使用された coins が valid である
  • まだ消費されていないこと（ダブルスペンドではないこと）
  • total value in == total value out
  • 元のコインの所有者全員による署名がされていること
  • トランザクションが valid であると Scrooge が確認できたら、Scrooge はブロックチェーン台帳に追記する

コインは Immutable である

  • コインは移動させたり分割したりマージしたりできない
  • 毎度コインを新しく作り直すことで譲渡を実現する

次回に向けてこの ScroogeCoin では、Scrooge が中心的な役割を果たしているが、はたして Scrooge なしで、非中央集権的なシステムにすることはできるだろうか。

comments powered by Disqus