niconegoto Blog

niconegoto's journal

PoWやPoSに頼らないSkycoinのコンセンサスアルゴリズムとはどのようなものなのか #skycoin #bitcoin

はじめに

僕が最初にskycoinに触れたのは今年の4月の事でした。公式のリリースに51%攻撃などの問題を解決していると書いてあったことや、golnagでcoreが書いてあったので個人的にソースを読むモチベーションがあったため非常に興味を持ちました。 Satoshi Nakamotoのwhite paperを読んだ2年前には新しい発想で面白いなとは思いつつも全く可能性を感じていなかったのですが、最近では大手各社がマイニング事業に参入するなどすごい盛り上がりを見せています。 僕自身は bitcoinを5万で買って15万で売ってしまったという悔しい現実から目を逸らすため 各コインの値段の上がり下がりなどには全く興味がないのですがアルゴリズムには興味があり、ちょくちょく情報を集めているので今回このような記事を書くことにしました。

僕はこの分野において素人なので理解や解釈が間違っている点がある可能性がありますが、そのあたりは優しく指摘していただけると幸いです。

skycoinとは

f:id:niconegoto:20171216121141p:plain

Satoshi envisioned Bitcoin as a decentralized digital currency. Blockchain networks were intended to democratize finance, eliminating corporate control and spreading power among users. However, Bitcoin and related currencies have become centralized due to their reliance on Proof of Work (PoW) and Proof of Stake (PoS) algorithms, as well as their use of mining to create coins. This centralization defeats the original purpose of digital currencies.

skycoinの開発経緯に関してはWhy We Built Skycoinを見ていただければよく分かります。 上記に引用したように、PoWやPoSによって集中化が起こってしまっていて本来の意味での分散型ではなくなってしまっていることに対して問題意識を感じており、Bitcoinの問題点を修正してSatochi Nakamotoの当初の目標を達成するべくOSSで開発が行われています。

Joseph Youngも

主要な利害関係者がネットワークの技術的側面と経済的側面の両方を徹底的に制御し、権限を持つシステムは、重大な独占問題を引き起こします。

と述べており、PoWは51%攻撃に対する脆弱性を持っており、それを解決するためのPoSは権限の独占を引き起こす という構造に対する批判を行っています。

PoWやPoSについては様々な解説記事があると思うのでここでは説明を省きます。

実際にどのようなコンセンサスアルゴリズムなのか

Skycoinに関するwhite paperは公式サイトから見る事ができます。 いくつもwhite paperがあるのですがその中でも今回はA Distributed Consensus Algorithm for Cryptocurrency Networksを読んでいきます。

まず最初に、Coinにおいてのコンセンサスの対象はブロックチェーンに追加する候補ブロックのデータのハッシュコードで、コンセンサスの主題は最も正しいハッシュコードが何であるかを合意しようとする分散ノードです。この主題をを中央集権的にではなく分散型で合意形成することがいわゆる分散型のシステムとなるためには必須です。

そしてこのwhite paperは

  • ノード間のコンセンサスがすばやく達成できる
  • 最小のネットワークトラフィックを必要とするように、コンセンサスを試みる際の各ノードに対する最適なルールを見つける
  • 組織化された悪意のあるネットワークによる大規模な協調攻撃に耐えることができる

というアルゴリズムを説明することを目標として作られました。

Mesh Network

そこで今回重要になるのがMesh Networkです。メッシュネットワーク - Wikipedia

今回のように

Sparse network

Sparse networkとは、ネットワークサイエンスにおいて同じネットワーク内のリンクの最大可能数よりも少ないリンク数を有するネットワークを指します。(まあ難しいので簡単に言うなれば不完全なネットワークのことです。)

Mesh Networkの基本の動きは以下の通りです。

  • 各ネットワークノード(「ノード」)は、上流ノードまたは下流ノードに直接接続される
  • 各ノードは特定のデータを発信(publisher)・受信(subscriber)どちらの役割も担うことができる
  • あらたにそのネットワークに加入するノードは、直接接続されている上流ノード(publisher)からデータを受信する

そして具体的なデータの送受信は以下のように行われます。(まあ当たり前ではありますが)

f:id:niconegoto:20171215222411p:plain

  • subscriberにデータのhash値を渡す
  • subscriberは、既にデータが届いていた場合、「もう持ってます」という情報をpublisherに返す
  • subscriberは、まだそのデータを持っていなかった場合は「それください」という情報をpublisherに返す
  • publisherはデータをくださいと言われたらそれをsubscriberに渡す

つまり、publisherノードがこのデータの送信について 受信したデータ生成したデータに関して行うことで、ノードは潜在的に各ノードからデータを受信し、潜在的にネットワーク上のすべてのノードにデータを送信することができるということになります。(ここから少し詳しく説明します)

ノードのセキュリティ

ノードは公開鍵(「Pubkey」)によってアドレス指定され、ノードのIPアドレスは、ノードが直接接続されているノードのみが認知できるようになっています。

そして、伝達に関してはどのノードでもメッセージをpublishすることができるため、そのメッセージを受信した下流ノードは暗号検証の後、メッセージが重複していないことをそれぞれの下流ノードにチェックした後、それを転送するという処理(最初の図のやつ)をし、その結果、ネットワーク全体にメッセージが伝達されます。

f:id:niconegoto:20171215222807p:plain

Mesh Networkにおける ノードの物理的接続性(左) ノー​​ドPK0の論理的接続性(右) 図の「PK」は「公開鍵」の略です。

データコンテンツの制御

データが伝達仕組みは分かったところで、今度はどうやってそのデータを制御するのかという話になります。 そこでノードの切断という処理が生まれてきます。

たとえば、

  • ノードYは、ノードXが処理できない速度でトラフィックを転送している。
  • ノードYは、大量の不適切または悪意のあるデータを含むメッセージを転送している。

といった場合にこの切断が行われます。

そして、切断を行ったとしてもXに関連しないYへのルートが存在する場合、ネットワーク内の他のノードは依然としてYからデータを受信することができます。

切断を行った後、さらに、ノードは、Pubkeyによって他のノードをローカルにブラックリストに登録することができます。 ノードXがノードYをブラックリストした後、Yから来るメッセージはXによって無視され、Xの下流ノード達には転送されません。

  • ノードYは、不適切または悪意のあるデータを転送しているが、YはXに直接接続していないため、Yから切断できない

といった場合にこのブラックリストが役立ちます。

Network Consensus Algorithm

これらの前提知識をもとにコンセンサスアルゴリズムの説明に入っていきます。 先ほども触れましたが、コンセンサスアルゴリズムの主な目的は、すべてのネットワークノードでブロックチェーンの状態を同期させることです。

まず、skycoinのチームはノードが

  • 最寄りのノード
  • 少数のローカルノードのノード

とは異なる意見を持つことを避けるようないくつかのコンセンサスアルゴリズムを試したものの、シミュレーションの結果少数の悪意のあるノードによってコンセンサスが容易に操作されることが判明しました。同様に、リーダーノードを選ぶような行動モデルも試したものの、リーダーの選挙にはグループの生存に高い知能が必要になり、グループメンバーの平均知性が低い状況では成り立たないため候補から排除されました。 したがって、グループは生き残るために、グループのために賢明な決定をすることができるメンバーを見つけなければなりません。このような挙動は、シープル後、または 指導されていることに対する好みを持っている種、それは暗号侵害コミュニティと一致するようではない。さらに、指名された社会の利益に反する行動をとるために悪意のあるエンティティによって強制される可能性があるため、リーダーは潜在的に単一障害点になります。そのため、リーダーベースのモデルも考慮に入れることにしました。

結果、ノードの要件は以下の様に定まりました

  • ノードは賢く、各ノードは、受け取った意見の堅牢な統計分析を行うことによって、独自の独立した意見(例えば、最良の次のブロック)を形成することができる
  • ノードは懐疑的であり、各ノードは、データの生成者の検証と不正検出を常に実行する
  • ノードは主権者であり、他のノードの意見が考慮されている間に、特定のグループと意見を一致させず、ある特定の意見を支持する代わりに支払いを求めるような行動をしない
  • ノードはコンテンツ生成者であり、ノードは、生データ(トランザクションのような低レベルの基本イベント)を受信し、新しい意見を導く独立した処理を行うことができる(ブロックハッシュ生成)

ネットワークサイズによるスケーラビリティ

上記でも述べたとおり、ノードはネットワーク内の任意のノードからメッセージを受信する可能性があります。 ノードは多数のデータを元にした方が統計的に有意な結果が得られるためより多くのメッセージを求めようとしますが、ネットワークの規模が大きくなるにつれてコンセンサス関連のメッセージ数も増加しメッセージ待ちの時間が増加していった結果、スケーラビリティの問題に直面します。 そのためブロックを作る際のルールに、 サンプルサイズ数の制限を追加することによってこの問題および他の関連する問題を回避します。(このパラメータは、以下ではZとします)

どの程度のZが適切であるかのテストに関しては、ネットワークがサブバージョン攻撃を受けているときのZの影響を以下の様に調査し、Zはそこまで大きくなくとも100程度であれば許容できるという結果になりました。

f:id:niconegoto:20171216110422p:plain

正しいハッシュ(縦軸)と悪意のあるノードの割合(横軸)を取得する確率 この図は、意思決定サンプルZのサイズを大きくすることでコンセンサストライアルの堅牢性が増すことを示しています。 ネットワークは、N = 1000、B = 1000、S = 5、およびZ∈{25,100,200,1000}の循環接続したグラフです。

また、ブロック作成ノードBの数を一定に保ちながら、ネットワーク内のノード数Nを増やすという実験も行っている。

f:id:niconegoto:20171216111042p:plain

B = 1000、S = 5、Z = 100、N∈{1000,10000}なランダムに接続したグラフ Nが増加してもコンセンサスの質に影響があまり無いことを示している。

ノードが所与のブロック番号(シーケンスに振られるもの)に対してZ個の意見を取得した場合又はブロッククロックがシーケンス番号を大幅に超えて進んだ場合、ノードは試行を終了してハッシュコードの計算を行います。

コンセンサストライアル中、ノードはブロックのハッシュコードを含む小さなメッセージを通信しますがコンセンサストライアルが終わるまではブロック自体に関する内容を通信しないようにすることで効率化を図っています。そして、勝ったブロックがローカルブロックチェーンに追加されます。

ブロッククロック

このコンセンサスアルゴリズムはカレンダーの日付/時刻を使用しません。代わりに検証されたコンセンサスおよびブロックチェーン関連のメッセージから抽出されたブロック番号がノードの内部時間を計算するために使用されます。これは非公式に「ブロッククロック」と呼ばれています。

コンセンサスアルゴリズムの実装

まず、いくつかのノードをブロック作成者として指定する必要があります。 すべてのノードはブロック作成者になる可能性があり、ブロックメーカノードは

  • 他のノードによって公開されたトランザクションをチェックする
  • ルールに従いチェックされたトランザクションを新たな候補ブロックと結合する
  • ネットワークに、以下の4つの項目を含むメッセージを伝達する
    • 候補ブロックのハッシュコード
    • ハッシュコードの署名(ノードの秘密鍵で行われる)
    • ノードの公開鍵
    • ブロックのシーケンス番号

ということを行います。候補ブロックは要求に応じて別個のメッセージとして伝達されます。

複数のノードによる候補ブロックの作成の目的は、多数の独立し暗号的に署名された意見(opinion)を作成することです。 すべてのブロック作成者が

場合、それらが生成した候補ブロックは同一なものになります。 現実的なネットワーキング環境では、これまでに公開されたすべてのメッセージをもたないノードによって作成されたブロックが存在しますが、メッセージ到着率の点から実際にはブロック作成ノードの大多数が与えられたシーケンス番号に対して同一の候補ブロックを構築することができます。

不正攻撃を受けた場合

攻撃者が、不正な候補ブロックのハッシュコードをブロードキャストする多数の悪意のあるノードを設定した場合どのようになるのでしょうか。

すべてのノードは、伝達されてきた候補ブロックのハッシュコードを基に、正しいハッシュコードが何であるかについて統計的推論を試みるためのデータサンプルを構築します。 ネットワーク接続が不良なノードはすべてのトランザクションを監視することができないため、ブロック作成者として指定されません。それらのノードは依然として候補ブロックのハッシュコードを有するメッセージを受信することができますが、それはトランザクションよりもはるかに低い頻度で行われます。そのため、非ブロック作成ノードは最新のブロックチェーンのローカルコピーを維持することができます。

悪意のあるノードだけに物理的に接続されたノードが存在する場合、悪意のあるノードは受け取ったを破棄してその代わりに悪意のあるデータを送信しますが、publisherに悪意があると思われる場合subscriberはそのPubkeyをブラックリストに登録し、ローカルブロックチェーンの再同期を試みることができるため、悪意のあるノードはネットワークの他の部分から切断され、残りのネットワークが新しいブロックを生成した瞬間にそのブロックチェーンが失効します。

このような仕組みで51%攻撃に対するPoSではない対策を打ち出しています。

まとめ

まだまだ他のwhite paperもあるため読んでいかないと完璧に理解することはできませんが、ざっくりとしたイメージはつかんでいただけたのではないでしょうか。 世の中にある様々な暗号通貨に対して本当にシステム的に優れているのかどうかは実際にwhite paperや実装を読まなければわかりません。 インターネット上に転がっている情報にはソースの不明なものが多いため、自分でこのようなソースを読んでいき、実際にそれがアルゴリズムとして優秀なのか、実現可能なのかを考えて行かないといけないなとひしひしと感じました。