bitcoin と ビザンチン将軍問題

計算機 考え事 ノート マンガ

bitcoin はビザンチン将軍問題を解決したとしばしば言われます。これが厳密には誤りだそうです。私もそんなに詳しくないのだけれども、確かにそうかなと思います。

ビザンチン将軍問題というのは――離れた場所にいる複数の将軍間で作戦の合意をとりたい；ただし将軍の中に裏切り者がいたり、伝令が失踪したり遅れたりする可能性がある――という問題です。

bitcoin がこれを解決したと言われるのは、悪意のある参加者が過半数以下の場合は帳簿が改竄できないようになっていて、参加者が帳簿を共有しているので、bitcoin では帳簿の内容について合意がとれているように見えるからでしょう。

しかし、上でいう「合意」というのは「分散システムにおける合意」（以下 consensus とする）とは全く別物です。例えば、bitcoin には最も長いブロックチェーンを参加者がみんな知っている、つまり consensus がとれている、という保証はどこにもないはずです。*1だから、bitcoin はビザンチン将軍問題をちゃんと解決したわけではない。

でも、bitcoin は現実に動いているので、何かの問題は解決している。それは一体何なのだろうというのが私の疑問です。bitcoin は別にビザンチン将軍問題を解決したわけではない――と批判するのは簡単なんですが、それよりも問題の方をもう一度定式し直した方がいいのではと思うわけです。ビザンチン将軍問題は、おそらくもう解決できないし、現実に即してないので、もはや悩むだけ無駄かと。この辺をちゃんと考えた人いるのかな？

bitcoin が、別にビザンチン将軍問題を解決したわけでもないのに、悪意のある参加者がいる状況で実用的には正しい帳簿を共有できているのはなんでだろうと考えると、おそらく bitcoin は PoW によって CPU ネックになっていて、相対的にネットワークがすごく速くなっているからだと予想する。bitcoin のブロックチェーンにひとつのブロックが追加されるのに10分を要するのは、確かに遅い。しかし、インターネットみたいな不安定な通信網の上で、どんなマシンもネットワークに参加していいという条件下で、世界中に情報が伝播することがだいたい確信できるであろう時間を考えると、そこまで変な値ではないように思う。つまり、10分ぐらい待てば、consensus を保証しなくても、ほとんどのノードには情報が伝わったことを期待してもよかろうということだ。10秒では短すぎる。この辺のさじ加減も bitcoin というのはようできてる。あぶない橋を渡っている気はするが……。

詳しくないけど、ビザンチン将軍問題を解決しようとしたときに最も難しいのは、通信だろう。遅延や欠損なんて無視できるレベルで小さい、完全な通信があれば、ビザンチン将軍問題は解決できそうだ。*2『ドリフターズ』という漫画で、織田信長が無線通信装置（のようなもの）を見た時に、遠隔地にある部隊をリアルタイムで連携できるとその可能性を見出していた。これがおそらく答えで、現実に将軍がいて合意をとりたいという、実地のビザンチン将軍問題が仮にあったら、それは無線通信があれば概ね解決できるように思う。

だから、bitcoin というのはビザンチン将軍問題を解いたわけではなくて、それを解決せずに済むような条件を絶妙なバランスで作っているから上手いこと動いているのではないかというのが、今のところの仮説です。

*1:実装までは把握していないのでこれは推測です。ゴシッププロトコルか緊急連絡網方式か、何かしらの方法で最新のブロックが追加されたことを広報しているだけで、それが確実に全体に伝わっているかは保証していないはず。10分ごとにそれをするのは不可能だと思う。

*2:いくらかの制限は要りそう。そういう条件下での解法は誰かがもう証明しているにちがいない。詳しくないので知らん。

bitcoin: Proof of Work の肝

計算機 考え事 ノート

bitcoin の仕組みは「ようできてる」と感嘆します。ポイントはデータベースの更新を承認する「Proof of Work」(PoW) という仕組みです。

さて、bitcoin が PoW で上手く回っているのは、PoW の特徴によるものに思います。PoW がなかったどうなるのかというのを仮定してみて、PoW の意義について考えてみる。同期とかの用語は厳密な意味は分からずに使っています。

PoW とは、bitcoin クラスタに投げられたトランザクションをいくつかまとめて承認して、トランザクションログに追記することです。トランザクションログは、トランザクションの塊（ブロック）がチェーン上につながっているので、ブロックチェーンと呼ばれます。ブロックチェーンに追記できるブロックは特定の条件を満たす必要があり、その条件を満たすブロックを見つける作業は CPU コストがかかります。PoW の CPU コストのために、bitcoin は非常に遅いです。１つのブロックをチェーンに追加するのに10分かかります。

では、PoW の CPU コストをなくしたら、どうなるのだろうか。*1

まず、同期が非常に難しくなる。複数のノードを同期させつつ、ネットワークの不安定にも耐えて、ノードが増えたり減ったりすることにも耐えるというのは、難しい問題である。長年研究されているけれども、決定的な解決法というのは見つかっていない。bitcoin はひとつの解決法ではあるが、ネットワークネックを CPU ネックに替えることで、ネットワークを相対的に速くしているから、回っているように思う。PoW がなくなってしまうと、おそらくネットワークの不安定に対する耐性が弱くなってしまうだろう。同期がうまいこと取れなくなって、データの整合性や永続性が得られなくなる可能性が高い。一番長いチェーンがどれなのかの合意を取る仕組みも特にないから、ブロードキャストしてちゃんと届くことを期待していると思われるが、ネットワークがネックになったら、それも期待できない。

また、対攻撃性が弱くなる。承認が簡単になってしまうと、承認とその検証が同じ程度のコストになってしまう。PoW のいいところは、誰でも承認作業ができるが、承認にはコストを要して、逆にその検証は非常に容易であることだ。承認の正当性や権威性を「計算」に置き換えてしまっている。計算をなくすと、承認の正当性も権威性も失われてしまうのだ。誰でも承認ができる仕組みをやめて、特権を持った人をつくるとしても、特権を持った人を合意するにはどうするのかとか、特権を持った人の承認の正当性はどうやって保証するのかという問題が生じる。また、特権を持った人がシステムとしてクリティカルな場所になってしまう。*2

そういうわけで分かりきった結論かもしれないが、PoW は非常にコストがかかるが、このコストがなくなると bitcoin はシステムとして成立しなさそうである。bitcoin って本当にようできている。

多分、うまい解決方法はある。おそらく、bitcoin のどこかを捨てることになるのだが、それはどこなのだろう。*3

*1:bitcoin の貨幣価値の出処は PoW に要する CPU コストなので、貨幣として弱くなる可能性もあるが、そこはあまり興味の対象でないので、議論しない。

*2:Proof of Stake という通貨を多くもっている人の権限を上げる仕組みもあるらしいが、仮想通貨としての用途以外の場合には適用しづらい。仮想通貨に興味があるのでなくて、非常に堅牢なデータベースとしての bitcoin に興味がある。

*3:既に多くのアイデアと実装はあるのだろうけれど、調べきれてない。きっと知られていない、うまいやり方は多くある

Bash でスタックトレースを表示

Bash 計算機 ノート

Bash でスタックトレースを表示する方法。 caller という組み込みコマンドで関数の呼び出し元の位置がさかのぼって取れます。これを使って以下のようなスタックトレースを表示する関数が作れます。

function print_stacktrace() {
  index=1
  while frame=($(caller "${index}")); do
    ((index++))
    # at function <function name> (<file name>:<line no>)
    echo "at function ${frame[1]} (${frame[2]}:${frame[0]})" >&2
  done
}

function func_a() {
  print_stacktrace
}

function func_b() {
  func_a
}

function func_c() {
  func_b
}

func_c

実行すると下のようにスタックトレースがプリントされます。

at function func_a (stack.sh:11)
at function func_b (stack.sh:15)
at function func_c (stack.sh:19)
at function main (stack.sh:22)

Bash で Power Assert 風のものを作った

手慰み Bash 計算機

GitHub - fjkz/power-assert-bash: Power Assert for Bash

Bash で Power Assert 風のものを作りました。*1

なぜか Bash には assert がありません。なので、 Bash でテストを書くときは、 set -e として、

[ "$actual" == "$expect" ]

とか書きます。しかし、これだと失敗したときに、情報がないので困ります。set -x としてもいいのですが、これ欲しくない表示も出て、ウザイのです。また結果も見づらい。Bats もテストのどこでエラーとなったかは教えてくれるが、変数の中身とかは教えてくれません。

そこで、 Power Assert 風のものを作ってみました。 Power Assert とは、Spockに含まれる assert の結果を美しく表示してくれる機能です。

. power-assert.bash
A="HELLO WORLD"
[[[ "${A}" == "HELL WORLD" ]]]

. か source コマンドで power-assert.bash を読み込むと、 [[[ コマンド (実体は関数) が使えるようになります。 シェルスクリプトの [ コマンドとほとんど一緒で、条件が否なら 1 のステータスコードを返し、正なら 0 を返します。しかし、[ と異なり、条件が否の場合はエラーメッセージを吐きます。

上記のスクリプトを実行すると、以下のメッセージが表示されます。

assertion error:

[[[ "${A}" == "HELL WORLD" ]]]  ->  false
     |
     "HELLO WORLD"

at function main (sample.sh:3)

まあ、ただこれだけです。 assert_equals みたいな関数を用意するよりは、いいと思っているがどうなのだろう。

*1:○風としているところが、そんなに powerful ではないことを示していますが……。 powerful にしようと思ったら、Bash で Bash のパーサーをつくらんといけない……。まだ綺麗に表示されない条件も多い。

TT-Runnerの記録２：ベータ版

計算機 手慰み Python Bash

前回:

GitHub - fjkz/ttap: ttap: a testing framework with file system hierarchy

結合テスト用のテストスクリプトを実行するためのツールを作っている。

シェルスクリプトベタ書きのテスト群を整理された状態にまとめられるものが欲しいという、当初の目的は達成できたように思う。1000 LOC にも満たない小さなプログラムだが、欲しいものの仕様にたどり着くのに時間を要してしまった。

英語のドキュメントは下手なので伝わらないだろうから、日本語のドキュメントも書いた。

https://github.com/fjkz/tt-runner/tree/master/doc/jp

しばらく寝かせて、バグ修正だとか異常系の作り込みだとかをしたら、1.0版としたい。

追記

ttap と名前を変えた。

ディレクトリ構造のスキーマ

計算機 考え事

私はファイルシステムとかブロックストレージとかには少しだけ詳しいと思うが、現実に興味があるのはもう少し上の階層だ。RDB でいうとどのようにスキーマを設計すべきかという階層の話に興味がある。昔に書いた以下の記事でいうと「シンタックス層」が関心の対象だ。

データにもOSI参照モデルがある - 超ウィザード級ハッカーのたのしみ

なぜかというと、個人的な動機だが、私は情報を集めるのは好きなのだが、整理するのはあまり得意ではない。例えば本やメモであればフラットな場所、つまり一個の本棚やノート、にすべて放り込んで、目視探索か脳内検索をしてしまっている。そういうのは他人には扱えない。そのためには、体系的に情報を整理する必要があるので、どうやったらそれができるのかということに苦心している。

得意な人は苦労せずに整理してしまっているのだが、それが良い出来かというと疑問で、正直なところ勘で整理されたものも他の人には理解できない。頭の良い人が工夫して整理したもので、はじめてまともに整理されている状態と言える思える。

どのようにしたら情報をうまいこと整理できるのかという問題については、人類は長いこと悩んでいる。どのへんに学問性があるのか私には分からないのだけれども、図書館学というものもある。

近年では、情報はデータと言われてバイト列として計算機に収められている場合が多い。計算機上のデータは、紙面の情報と異なって物理的な制約がなくなった。そのためにデータの量が爆発的に増えてしまった。PC に収められるドキュメントの量では整理しないと人間が追いつけない。目視探索や脳内検索の限界を超えてしまっている。

計算機上にデータを保存する手段はいろいろある：RDBやファイルシステムだ。上で引用した昔の記事でいうところの「ウツワ層」に相当するものだ。ウツワ層は多くの人が研究してきて、もうだいたい完成しているように私は思っている。

しかし、その上のシンタックス層――つまりスキーマのこと――に関してはまだ未完成ではないかと思う。

RDB に関しては、何が良い設計で何が悪い設計なのかは概ね共通理解となっている。RDB はスキーマを定義しないと使えないし、それを設計するための専門職がいる。彼らのおかげで、デザインパターンというのか、良い設計をするための知見が蓄積されている。

しかし、ファイルシステムに関しては未だ全くダメだ。

ファイルシステムは RDB より歴史が長いにも関わらず、いや歴史が長いゆえか、ファイルシステム上のディレクトリ構成はたいていグチャグチャだ。UNIX OS のディレクトリ構成に関しては、Filesystem Hierarchy Standard といって概ね統一されている。あるいは、Java のソースコードも Apache Maven で標準のディレクトリ構成というのが定義されて統一されつつある。だが、そういうのがないデータはグチャグチャにならざるを得ない。PC 上のデータが整理されていないのは、実害は少ないが、共有フォルダが整理されていないのは目に見えた害がある。

どうしてこういうことになるかというと、ファイルシステムにはスキーマが定義されないからだ。

Filesystem Hierarchy Standard や Maven 標準ディレクトリ構成は一種のスキーマである。賢い人が設計しているので、なんとなく作ったものより使いやすい。また、規格なのでそれに合わせることで、他のプログラムとの親和性が向上する。

しかし、設計とかせずになんとなくディレクトリを作っちゃうことも可能で、ほとんどの場合はそうなっている。自由であるとも言えるのだが、自由にできたところで、間違った選択肢が増えるだけだ。正しい選択肢は少ないが、間違った選択肢は無数にある。最初にディレクトリを作ったときには、なにかしらの意図があるものだが、その意図も曖昧模糊としているし、時間が経過するとその意図を無視してファイルが配置されたり、新たなディレクトリが作られたりする。結果、整理されていないデータが氾濫することとなる。

ファイルシステムの構成にもスキーマを定義できたらよいと思う。スキーマが定義できれば、いつの間にかディレクトリ構成がグチャグチャになることが防げるだろう。

テストスクリプトのディレクトリ構成を規定するツール「ttap」というのを作っている*1。作ってから気づいたが、これもファイルシステムの構成のスキーマを定義しようとしているのだ。

これを敷衍してもう少し一般的な形でディレクトリ構成を定義できるようにしたい。XML にはスキーマを定義できる XSD というものがある。このようなイメージでディレクトリ構成のスキーマを Well-Defined に規定できる手段が欲しい。ディレクトリ構成には慣例があって、空気読めや――みたいに現状はなっている。今は人の手に頼るかたちになっているが、厳密に定義することができれば、機械によって整理することも可能だ。賢い人がスキーマを定義すれば、いろんな場所で使いまわせるようになるだろう。

以上のようなことを思いついたが、どうやって実現したらいいのか今は答えがない。ちょっと考えてみようと思う。

*1:https://github.com/fjkz/ttap

TT-Runner の記録 1

手慰み 計算機 Python

TT-Runner: テストスクリプトのディレクトリ構造フレームワーク - 超ウィザード級ハッカーのたのしみ

GitHub - fjkz/ttap: A Test Scripts Runner

TT-Runner (Test scripTs Runner あるいは Tree Tests Runner) というのをシコシコと作っています。*1

以下、作業記録。

スクリプトのある場所に cd するようにした。

シェルスクリプトはカレントディレクトリ、つまりどこの場所からスクリプトを実行したのか、にシビアである。スクリプトが存在するディレクトリから実行することを期待するのが多いかと思うので、スクリプトを実行する前にそのディレクトリがあるディレクトリに cd するようにした。

カレントディレクトリを変えないオプション (--no-chdir) も念のために用意した。

--stop-on-failure, --skip-all オプションの追加

一つでも operation が失敗したら、残りはすべて skip するオブション --stop-on-failure と、すべての operation を skip するオプション --skip-all を追加した（--dry-run の方がわかりやすいかもしれない）。主にテストスクリプトのデバッグ用です。実行にある程度時間がかかるようなテストを想定しているので、こういうオプションは欲しい。

各スクリプトの出力をファイルに保存できるようにした

-o オプションで指定されたディレクトリに各スクリプトの結果を保存するようにした。ok/ngだけですべてが分かればいいが、そうはいかないので、ログが残せないと不便だ。result.txt に ok/ng のテスト結果の出力も残す。一応、TAP っぽく出力はしているが、今の出力は本当に TAP として正しいのか。

今後すること

ファイルに結果を保存できるになったら、コンソールへの出力は再考の余地がある。一つ一つのオペレーションが重いことを想定しているので、今のままでは見づらい。何％終わっていて、経過時間はどのくらいかで、失敗があるのかは、コンソールから簡便に確認したい。

JUnit XML も出力できるようにしたい。

テストツールなのにテストがないので、書く必要がある。

ドキュメントは一応書いてみたが、読めないのでまともにしたい。添削してくれる人が欲しい。

可能であれば、TAPを介して、他のテスティングフレームワークと連携できるようにしたいが、それをし始めると大変だろうか。

次回

TT-Runnerの記録２：ベータ版 - 超ウィザード級ハッカーのたのしみ

*1:陽の目は見ないがやる。これが「でも、やるんだよ」ってやつか？