権威と OSS

権威とはなんなのだろう？――というのは長いこと悩んでいる疑問である。私が権威が大好きな権威主義者ということなのだろうな。

また、OSS というのも社会学的に興味深い営みであり、これを観察することも趣味である。

さて、どうも最近 OSS が権威主義的になっている気がする。

OSS は一種の規格であるので、OSS に関して発言力を持つことはソフトウェアベンダーにとっては重要である。OSS の開発に関して発言力を持つことができれば、自社の製品と OSS との親和性を高めることができるので、自社の製品が売れる。そのため、有名どころの OSS では、いろんな企業が主導権をとろうと活発に開発に参加している。

既に存在している OSS の開発に参加するというだけが、OSS で主導権を取る手段もない。既存のものは先行者利益が大きい。先にいた人が強い発言力を持っているので、後から入ってきた人が発言力を持つというのは結構大変だ。OSS で最も偉い人は始めた人で、次に偉い人は最も手を動かした人である。これは OSS に限らずどこの業界であってもそうであろう。しからば、自分が完全にコントロールできるような OSS が欲しいのであれば、自分で OSS プロジェクトを初めてしまうというのは簡単な手段である。

ただ、企業が始めた OSS の開発に参加する人がいるかというと、いないだろう。どうして一企業の利益に、関係ない人が貢献するのだろうか。標準規格にすることを狙って、企業が始めた OSS プロジェクトで、参加者が集まって上手くいっている例は知らない。ただソースコードが公開されているだけで、実際には一企業の人が内々で作っているような OSS だけれどもオープンではない OSS は多い。

標準化したいならば、中立性が必要だ。中立であれば、一企業だけに利する恐れが少ないので、参加者が集まる可能性が高まる。もちろん、ソフトウェアとしての価値が高いことが前提である。

思うに中立性とは権威と同じである。中立とは他より偉いという特権だ。そのため OSS プロジェクトを権威の元におこうというのは自然な考えだ。OSS 界隈で権威ある団体といえば、Apache Software Foundation と Linux Foundation が挙げられよう。一企業主導であれば標準化が難しいからと、Apache Software Foundation にプロジェクトが寄贈されたりだとか、Linux Foundation 配下で開発が行われたりだとかがされる。

ASF や Linux Foundation の元で OSS の開発が行われたら、それが中立化というと実際のところそんなことはないと思うが、一企業に利するようなことは建前上できない。

おそらく、今後 ASF や Linux Foundation の元で OSS を作ろうという風潮がますます活発になって、これらの財団のブランド力が強くなっていくだろう。権威というのは偉いから偉いのであって、一旦権威がついたものはもっと偉くなる方に向かうものだ。OSS で標準化を狙うなら、ASF や Linux Foundation の中で発言力を持てるように頑張るのがオススメだ。*1

しかし、そういう風潮が強まると、OSS が政治的が強いパワーゲームになることもおそれている。みんなで協力して自由なソフトウェアを作ろうみたいな、牧歌的なものではなくなってしまうかもしれない。

*1:とはいっても ASF や Linux Foundation の中がどうなっているのかはようわからないのだが……

ブロックチェーンについての考察

タイトルが雑だが、最近ブロックチェーンについてぼんやり考えていて、その覚書。

元の bitcoin の Proof of Work (PoW) は以下の式を満たすブロックをブロックチェーンにつなげることができる。

hash(prev, tx, nonce) < 1 / difficulty * hash_max                (eq.1)

hash       : ハッシュ値（正数とする）を返す関数
hash_max   : hash が返す最大値
prev       : 前のブロックのハッシュ値
tx         : ブロックに含めたいトランザクション
nonce      : 意味のないテキトーな値
difficulty : 困難さを表す値, (0, ∞)

PoW では上の式を満たす nonce を総当り的に探すということをする。bitcoin は diffuculty を大きくとって、めったにちょうどよい nonce が見つからないようにしている。

しかし、それでは遅いので、下のようにすることが考えられる。

hash(prev, tx, nonce) < credit / difficulty * hash_max           (eq.2)

credit という指標を導入し、信用度が高い人は PoW の難易度をおまけするようにする。credit が高い人が攻撃者の可能性が低ければ、PoW の条件が緩くても、対攻撃性は下がらない。

このような実装をとっている bitcoin 類似の仮想通貨はきっとあるだろう。調べてみると Peercoin というのがこんな感じっぽい。*1Proof of Stake 方式をとっている仮想通貨は、通貨の保持量が高い人の credit を上げるということをしているようだ。

さて、面白いと思うのは、bitcoin は decentralized なシステムであると言われるが、(eq.2) は centralized なシステムも表すことができることだ。単一のノードのみ credit ≒ ∞ で、他のノードが credit ≒ 0 のシステムであれば、centralized なシステムとなる。ひとつのノードが PoW に相当する計算なしに、データベースを更新していくような、一般的な Server-Client 型システムである。*2

(eq.1) のように credit が全ノードで同じシステムは完全に decentralized である。一部のノードの credit が非常に高くで、他のノードの credit が非常に低いシステムは centralized といえる。ということは、いろんな credit のノードがあるようなシステムは、semi-centralized なシステムということになろう。Server-Client と P2P の間のようなシステムである。コンピュータシステムではない実在するシステムにはこういう形態のシステムは多いように思う。

現実のシステムと比較すると、通貨の保持量によって信用度を高めるというやり方もかなり現実を模しているように思うが、他にも良い credit の与え方はありそうだ。通貨の保持量以外の良い credit の与え方のアイデアはあるのだが、それを書くには余白が足りない。

*1:実装はおそらくもっと複雑で、多分コンセプトはこんな感じかなという推測です。詳しい人がいらっしゃったら、教えていただけると非常に嬉しい。こういうことを質問・議論できる場所(メーリスなり掲示板なりSNSなり）はないのだろうか？

*2:複数のノードが credit ≒ ∞ の場合というのも考えられる。この場合には、ちゃんとノード間で「合意」を取るようにしないとそれぞれのノードが持つデータベースがバラバラになるので上手く行かない。credit を少しずつ下げていって、どれぐらいから「合意」がなくても上手く回るようになるのかというのも興味深い問題である。あるいは、厳密に「合意」を取る場合とブロックチェーンのように「合意」を取らない場合をシームレスにつなげる方法はないかなどは、誰も解決していない問題であろう。

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 でスタックトレースを表示する方法。 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 風のものを作った

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の記録２：ベータ版

前回:

• 構造化されたテストスクリプト群の実行ツール - 超ウィザード級ハッカーのたのしみ
• TT-Runner: テストスクリプトのディレクトリ構造フレームワーク - 超ウィザード級ハッカーのたのしみ
• TT-Runner の記録 1 - 超ウィザード級ハッカーのたのしみ

---

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 と名前を変えた。