読者です 読者をやめる 読者になる 読者になる

備忘録 blog

Docker/Machine Learning/Linux

Paxos, Raftなど分散合意プロトコルを概観する(2)

前回の記事

sharply.hatenablog.com

本稿ではRaft, Bitcoinの Proof of Work, Proof of Stakeそれぞれのアルゴリズムについて説明する。

分散合意プロトコル

Raft

難解であったPaxosより簡単であることを標榜しているアルゴリズムで、そこまで多くないノード数で、密結合なネットワークにおける分散合意が想定されており、Paxosではあまり触れられなかったリーダー選出手法についてはこちらの説明のほうが腑に落ちやすいと思う。実際にetcdなどで実装されており、ログレプリケーションなどで用いられる。

ここでは明確にプロセスは状態機械として扱われる。各リソース上のそれぞれのプロセスは本質的に平等であり、プロセスはLeader, Follower, Candidateの3stateのどれかを持つ。Leaderは交代する場合があり、それをtermとよばれる世代番号で管理する。1termにLeaderは1人であり、選出フェーズと稼働フェーズによって構成される。

  • Leader: Clientからのログエントリの受領、Followerへのログエントリのブロードキャストを行う。
  • Candidate: 他のプロセスへ候補者になったことをブロードキャストし、過半数から承認を得た場合次のtermのLeaderとなる。
  • Follower: 手持ちのノードへデータを追加し、Leaderからのブロードキャストに応答する。

Leaderはハートビートと呼ばれる、一定時間毎に生存していることを報告するRPCを流す。これをAppendEntriesRPCと呼ぶ。RPCには以下の2種類がある。

  • AppendEntriesRPC: LeaderがFollowerに追加するログエントリを送る。これは内容がなくとも一定時間毎に送られる。
  • RequestVoteRPC: Leaderが不在の時、Candidateが自分に投票するように依頼する。レスポンスが投票である。

リーダー選出

Leaderが不在となった場合に、新たなLeader選出に入る。 Leader不在の状況は、AppendEntriesRPCの未受信によって判明する。それぞれのFollowerはランダマイズされた待ち時間があり、その待ち時間を過ぎてもLeaderからのRPCがなかった場合にCandidateに変化し、termの値が1つ増加する。CandidateはRequestVoteRPCと呼ばれるRPCをブロードキャストし、Candidateが自分に投票するように依頼する。過半数の投票があったことを以って、そのCandidateが新たなLeaderとなる。

もし仮に同時に複数のFollowerが時間切れとなって、複数のCandidateによるRequestVoteRPCが同時にブロードキャストされるような事態を想定してみよう。その場合、どのCandidateも過半数の支持を得られないことから、再びFollowerとなり、他のFollowerが次の時間切れとなってCandidateとなることを待つ。通常、待ち時間はランダマイズされるので、そのうちこのコンフリクトは解決するだろう。

ログレプリケーション、スナップショット

このあたりは調査不足なのだが、以下のスライドがわかりやすい。

www.slideshare.net

Proof of Work

さて、Bitcoinで用いられるコンセンサスアルゴリズムについて考えてみよう。その前に、Bitcoinの仕組みについて予めさらっておきたい。

bitcoinのブロックにはその前のブロックへのポインタ、トランザクションと呼ばれる取引の一覧、そしてnonceと呼ばれる特定の数字が入っている。このブロックが次々につながった単一の鎖をブロックチェーンと呼び、これを1ブロックずつ延長していくことがマイニングという操作で、nonceと呼ばれる特定の数値をうまく調整することで、ブロックに含まれる情報から計算される一方向ハッシュの値が、定められた値(この値はdifficultyにより定められる)より小さくなるようにする(左端から十分長く000000が続く値になるようにする)作業のことである。

SHA-256やScryptといったこれらのハッシュ関数は、入力の値を少し変えると出力の値は大きく変わる上に、それは予測できない性質を持っている。したがってブルートフォースな全探索に頼るしかなく、CPUやGPU, ASICとよばれる専用の外付けハードを用いてひたすら高速計算する必要がある。こうして新しいブロックを得るということは、それだけ計算=workをしたという証明になっているためproof of workと呼ばれるのではないかと思う。

逆に、nonce値が正しいかを計算するのは容易である。検証者は示されたnonceの値でhash値を計算し、difficultyの条件に合っているかを確かめればよいからである。このようにマイニングはハッシュ関数の計算困難性に依拠していて、bitcoinにおけるdifficultyは10分に1回新しいブロックが発見されるような難易度となるように調整されている。 取引が発生した場合、そのトランザクションはUTXOとよばれる場所に一時的にプールされ、次のブロックの採掘が始まったときにそこから手数料に応じて抽出されブロックに組み込まれてハッシュ値の計算が始まり、そしてブロックチェーンに組み込まれる。マイニングでは、マイナーはブロックの発見報酬とそのブロックの取引手数料の和を得ることができるのだ。

では仮に、異なる2箇所で同時にブロックA,Bが発見されたらどうなるだろうか。ブロックの発見と同時にそのブロックはブロードキャストされるが、疎結合なネットワークのためあるノードはA,あるノードはBを最新のブロックとして受け取ってしまうだろう。そして既にAを受領しているところでは、同じブロック番号であるBを受領することはできないし、その逆もまた真である。そのため、一時的にチェーンが分裂することがある。半分のマイニングノードではAの次にくるべきブロックを探し、残りの半分はBの次にくるべきブロックを探すようになってしまうからだ。

この場合どうするかというと、その次のつながるブロックA'あるいはB'のうち、A'が先に発見されたとしよう。するともともと先頭がAだったチェーンは次にA'が続くのはよいとして、先頭がBだったチェーンではそのチェーンは放棄され、A, A'の鎖が採用される。このとき比較するのは累積difficultyであり、今回であればA'がブロードキャストされた際に比較され、より累積difficultyの多いA'のほうを選択する。こうして、鎖は元通り1本になった。

difficultyが10分毎に発見されるように調節されていることで、次のブロックの発見には十分な時間差がついていると期待されるのだ。

51%攻撃

しかし、累積difficultyが高いチェーンをプライマリ・チェーンとして選択していくことには罠がある。それはあくまで相対的な規準であるため、51%以上の計算速度を持つノードが(実際にはそれより少ないノード数でも、確率的には引き起こすことが可能である)、プライマリ・チェーンから分岐させたセカンダリ・チェーンを延長させて元の鎖よりPoWの大きい鎖ができてしまった場合、元の鎖は破棄されてしまうのだ。 従って、ソフトウェアにハードコードされているGenesis Block以外のブロックが改変される可能性は0%ではない*1。厳密な意味では分散合意できていない!

現在は6世代まで遡って改変されることはないという前提のもと、それより6ブロック以上発見されているブロックにおけるトランザクションは成立したと見做される。またマイニングへのインセンティブのため、ブロックの発見報酬は100ブロック後が発見されるまでお預けとなる。これらの工夫によりコンスタントに良心的な計算力がマイニングに投下されているという状態が続く限り、そうそう簡単にトランザクションの取り消し、ブロックの改変が起こることはないが、起きた際のビットコインに対する信用の低下は免れない。

そして実際にマイニングは個人で行えるレベルではないため、複数人でマイニングを分担し、発見した分け前を分配するマイニングプールとよばれる集団による集権化が進んでおり、その中にはシェアの2割以上を占めるプールも出現していることから、それがウィークポイントとなるという指摘もされている。

Proof of Stake

さてAltcoinとよばれるBitcoinのオルタネイティブな実装のなかでは、Proof of Workとは異なるメカニズムでの合意を提供しているものがある。その一例がProof of Stakeであり、Stakeの名の通りブロックチェーンはそれを承認するコインの量によって定まるという仕組みである。これはProof of Workにおけるマイニングの電力消費、上記の51%攻撃への対処法として提案されたもので、Peercoin, Etheriumなどで実装されている。

考え方としては、コインを長期間持っている人はコインを鋳造することができるというような認識でよいだろう。コインを有する人がブロックを承認することができ、その承認の多いチェーンが選択されるという理解をしている。この場合、コインを多く持っている人はブロックチェーンのわかれたブランチに対して全承認をしてしまうことも考えられる(Nothing at stake)が、実際にそのようなことをするとブランチが乱立してコインの価値が下がってしまう。またPoS上で51%攻撃をしたとして、51%する主体はすでにコインの51%を取得しているため、そのような攻撃はそのコインの経済的価値を下げることになり、実質的には損である。

結局これはコインを有している人が選択権を握るということは、そのコインの価値を高める方向の選択(チェーンを1本に絞るような安定性を向上させる方向への選択)をするだろうという経済的インセンティブに依拠しているため、悪意を喪失させる*2という点では確かに効力を発揮するかもしれないが、かえってビザンチン故障に対しては弱い。

故障モデルをもとにしたプロトコルの概観

それでは最後に、今までのプロトコルをまとめたい。以下の分類法は「分散プログラミングモデルおよびデザインパターンの考察」に依っている。

マシンは死なない前提

マシンは死なないとする。この状況下で最も簡単な合意プロトコルは2 Phase Commitであり、このプロトコルではマシンが死んでしまうとブロックしてしまうので、死なないことが前提となっている。

Fail-Stop障害

マシンは死んだら死にっぱなしになっている障害のことをFail-Stop障害と呼ぶ。この状況下での合意プロトコルは3 Phase Commitであり、マシンの死に対してノンブロッキングである。

Fail-Recover障害

マシンが死んでいるか単に通信が遅延していうのか分からないような障害のことをFail-Recover障害と呼んでいる。

この状況に対して、初めて回復力を持つプロトコルとして提案されたのがPaxosであったが、元論文である"The Part-Time Parliament"は古代ギリシャの議会をモチーフにした難解なものであった。後に"Paxos made simple"と題されたそれより読みやすい論文や、Googleの開発者らによって実装上における手法を記した"Paxos made live"という論文が出回り理解は容易になったが、実装するにあたっては触れられていない部分も多く難しいことに変わりない。それに対して分かりやすく構成することを試みたRaftアルゴリズムというものが提案されており、そちらは明瞭な記述によって多くの実装が生み出されており、Paxosに比べて理解はやさしい。

論文間のつながりを敢えて図示するならば、以下である。

f:id:sharply:20160611191544p:plain

だが読むならば、以下の順に読むとわかりやすいだろう。

f:id:sharply:20160611191645p:plain

ビザンチン障害

ビザンチン将軍問題とは以下の問題である。

相互に通信しあう何らかのオブジェクト群において、通信および個々のオブジェクトが故障または故意によって偽の情報を伝達する可能性がある場合に、全体として正しい合意を形成できるかを問う問題である。 (Wikipediaによる)

このことから、偽のデータを流しうるノードが存在する状況をビザンチン故障と呼ぶ。数学的には3分の2以上は信頼できるノードである場合は、Lamport(1982)によると全プロセスに対して自分の情報をブロードキャストし、次に受け取った情報をベクトル化し再びブロードキャストすることで、過半数が同じ値のものを正しいと認識すれば、ビザンチン故障したノードがあっても正しい合意に至ることが可能となる。実際にPaxosの亜種として、3分の2以上のプロセスが正常の際にビザンチン障害に耐えうるプロトコルは提案されている。

しかし、さきのメカニズムでは巨大な疎結合ネットワークでは全対全通信が必要となるため、現実的な解決策ではない。これに対して解法を与えたとするのがBitcoinのProof of Workの主張であり、よく考えると厳密には合意に至っていないのだが確率的な制約条件によってほぼ覆ることのない状況にすることは可能であり、その制約条件は現時点では満たされている。

前回の記事

sharply.hatenablog.com

Reference

分散合意

http://www-higashi.ist.osaka-u.ac.jp/~nakata/mobile-cp/chap-07j.pdf

kumagi.hatenablog.com

postd.cc

Paxos

Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)

Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)

Consensus Protocols: Paxos : Paper Trail

www.slideshare.net

Raft

Raft(分散合意アルゴリズム)について · GitHub

Raft Consensus Algorithm

Bitcoin

github.com

d.hatena.ne.jp

qiita.com

アルトコイン | Bitcoin日本語情報サイト

*1:ただしその可能性は限りなく低い

*2:仮にこのネットワークをProof of Stakeの枠組みで攻撃しようとするならば、攻撃者はそれだけコインを保有する必要があるが、それだけコインを保有するならば攻撃によって失われるコインの価値もまた多くなるはずであり、従って損得で考えるならば攻撃者は攻撃する意味を失うはずである。