簡単まとめ

Bitcoin-NG論文を見てみる10

更新日:

本稿について

様々なブロックチェーンにインスピレーションを与えているプロトコルBitcoin-NG(Bitcoin Next Generation)の論文を見ていきます。本稿では「6. Metrics」の前半を見ます。

原文はこちらになります。

スポンサードサーチ

今回のまとめ

  • ブロックチェーンを評価する指標の一つがコンセンサスディレイである。
    • コンセンサスディレイは、ある時点からどれだけ遡れば一定割合のノードの合意がとれるのか?を表す指標である。
    • 時点tにおいて、ε-ポイントコンセンサスディレイがΔであるとは、「全ノードのうちのεの割合が、t-Δまでのステート遷移に合意していること」である。
    • より厳密には時間的に各ノードの示すステート遷移は変化することから、形式的には(ε, δ)-コンセンサスディレイを考える。(ε, δ)-コンセンサスディレイがΔであるとは、「始めからある時点までのδ%が経過するまでにεの割合のノードがt-Δまでのステート遷移に合意していること」である。

※以下、今回まとめた範囲の論文和訳になりますので詳細をご覧になりたい方は読み進めてください。

6. 指標

さて、ブロックチェーンを評価できる指標について説明しよう。これらの指標はナカモトコンセンサスのユニークな特性を評価するために設計されたものだ。

コンセンサスディレイ(Consensus Delay)

直観的に、「コンセンサスディレイ(consensus delay)」はシステムが合意に達するのに要する時間である。具体的な実行と時間に関して、ノードがステートについて合意したポイントを見つけるのにどれだけの時間を遡って見なければならないのかを定義することから始める。

アルゴリズムの具体的な実行においてある時点tと比率0<ε<1を考えると、ε-ポイントコンセンサスディレイは、時点tでノードのうちの少なくともε・|N|が最大でt - Δまで同一のステートマシン遷移プレフィックスを報告するという条件を満たすような最小の時差Δである。Bitcoinプロトコルの例を図4に示す。

コンセンサスディレイは、システムがごく僅かな時間の間に平均的に達成する最良のポイントコンセンサスディレイである。より形式的に表現すれば、(ε, δ)-コンセンサスディレイのシステムは、δパーセンタイルのεポイントコンセンサスディレイである。例えば、90%の時間で50%のノードが10秒前(ただしそれ10秒未満ではない)のステートマシンのステートに合意するのであれば、(50%, 90%)-コンセンサスディレイは10秒である。

筆者注:図4の「間隔Δ1とΔ2はそれぞれ時点t1とt2における50%-コンセンサスディレイである」についての補足

  • まず定義的に、時点tにおける50%-コンセンサスディレイとは「全ノードのうちの50%がある時点tから時間Δだけ過去の時点までは同じステート遷移をしてきたことに合意している、そのような条件を満たすΔ」だけではない点を抑えておきたい。より正しくは「全ノードのうちの"少なくとも"50%がある時点tから時間Δだけ過去の時点までは同じステート遷移をしてきたことに合意している、そのような条件を満たす」のである。よって、t-Δ時点を見たときに例えば66%のノードが合意していれば、50%-コンセンサスディレイと言って差し支えない。もちろん100%でも同様。ただし、逆にt-Δ時点を見たときに33%のノードしか合意していないならば、そのΔは50%-コンセンサスディレイではない(もっと大きなΔを取らないと50%-コンセンサスディレイにならない)。これでもまだ少し分かりにくいと思うので、次のようにイメージしてみるとよいかもしれない。
  • Δ1とt1の関係を感覚的に掴む(以下、t1時点におけるa, b, cのイメージ)
    • b「いまのプレフィックス1(ブロック1までのチェーン)です。先ごろ私がブロック1のあとにブロック2を作って公開しましたからね」
    • a, c「えっ」
    • b「えっ」
    • a「プレフィックス0(ブロック1の前のブロックをブロック0としています)でしょ。私の知る最新のブロックは1よ」
    • c「そうだよ。ブロック2なんてまだ確認できていないし」
    • b「...。私はあなた方がいう最新のブロック1のあとにブロック2を作ったのは確かです。ということは、現在から遡ってプレフィックス0、すなわちaさんがブロック0を生成した時点(t11)まではみな合意しているということでよろしいですね?」
    • a, c「そうなるね」
    • b「なるほど。では、3人全員の総意であればΔ1を50%-コンセンサスディレイとすることに問題はありませんね」
  • Δ2とt2の関係を感覚的に掴む(以下、t2時点におけるa, b, cのイメージ)
    • b「いまのプレフィックス2(ブロック2までのチェーン)です。先ごろ私がブロック2のあとにブロック3を作って公開しましたからね」
    • a, c「えっ」
    • b「えっ」
    • a「プレフィックス1でしょ。t1のときにbが言っていたブロック2は確認できたわ。でもそれ以降のブロックは確認できていないもの」
    • c「えっ。プレフィックス0の間違いじゃないの。ブロック2も3も知らないよ。最新のブロックは1」
    • b「過去にプレフィックス0があったことは私もaも認めるところですが...。現状の合意についてはそれぞれで齟齬があるようですね。aさん、あなたはいまプレフィックス1だと言っていましたね。ということは、現在から遡ってプレフィックス1、すなわち私がブロック2を生成した時点(t22)まではaさんと私で合意しているということでよろしいですね?」
    • a「そうなるわ」
    • c「僕は認められないけど...」
    • b「50%-ポイントコンセンサスディレイの観点で言えば、3人のうち我々2人(aとb)が合意している(=66.66...%>50%)ので、Δ2をとることに問題はないということになりますね」
    • c「ぐぬぬ」
    • a「はやくブロックが伝搬されてくるといいわね」

Bitcoin-NG論文を見てみる9 ←← 前)|(次 →→ Bitcoin-NG論文を見てみる11

免責

邦訳には誤りがある場合がございます。予めご承知おき下さい。

確実な情報を知るためには冒頭に示した原文をご参照くださいますようお願いいたします。

-簡単まとめ
-, , ,

Copyright© 暗号通貨界隈のメモ書きなど。 , 2019 All Rights Reserved Powered by STINGER.

%d人のブロガーが「いいね」をつけました。