ホワイトペーパー

DFINITYホワイトペーパー日本語訳9

更新日:

本稿について

本稿では、DFINITY White Paper:Consensus Systemのうち第6章「FINALIZATION」の日本語訳を掲載します。

本章は数学的な表記が多く、やや表記に慣れていないと読み解くのが難しくなっています。しかし、単に文中に注を入れていくと冗長になるため、節が終わるごとに数学的表記を噛み砕いて平易な文章(緑字)に直した注記をまとめて入れるようにします。

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

スポンサードサーチ

6 ファイナライゼーション

レプリカはアルゴリズム2に示すファイナライゼーションのプロシージャを使ってコンセンサスポイントを識別する。このプロセスに関しては、公証済みのブロックを観測するだけで十分である。つまり、ブロック提案やブロック提案になされている個々の署名を無視できる。ファイナライゼーションプロトコルは受動的で公証プロトコルとは独立である。ファイナライゼーションプロトコルは公証済みブロックにアクセスできる任意の者(レプリカを除く)が実行できるので、本章ではレプリカではなく「観測者(observers)」について述べる。

6.1 説明

アルゴリズム2は、ラウンドrについての最初の公証を受け取ったあとから時間Tより前に参照されうる全てのラウンドr - 1の公証を観測者が受け取るものとする仮定を立てる。この過程はアルゴリズムの正当性と同等であり、定理9.18において全レプリカに関しても証明される。

アルゴリズム2の一般的なアイデアは次のようなものである。つまり、公証済みブロックを継続的に集めてラウンド数に従ってバケツに入れる。Nrをラウンドrについての公証済みブロック全てのバケツであるとする。

複数のバケツを同時に満たすことができる。例えば、Nr+1が既に1ブロック入っている場合であっても2つ目のブロックがNrに入る可能性がある。だが、ブロックの先任者が分からないままそのブロックを検証することはできない。従って、相互に参照するブロックのペア全てに関して、先任者が最初に処理されると仮定する。結果として、Nr+1が最初の要素を受け取るより前にNrが最初の要素を受け取らなければならない。

最初の仮定によれば、それぞれのラウンドrについて、参照されうるNrにこれ以上の公証済みブロックを受け入れないようにできる瞬間がある。その時点でラウンドrを「ファイナライズ」する。なぜなら、Nrがラウンドr以降も生存できる可能性のある全チェーンのチップスを既に持っていると分かるからである。従って、LCP(最長共通接頭辞)C(Nr)を最終的なものとしてアウトプットできる。

(筆者注)

  • 言うまでもないが、バケツは文字通りのバケツではなく、ブロックを入れておくためのハコのような概念である。
  • FINALIZE(h)のプロシージャは、つまり、ジェネシスブロックではないときに、そのラウンドの公証済みブロックのバケツをチェーンCに入れるということである。

6.2 ファイナライゼーションの特性

BlockTimeの利用とTの利用の間には注目すべき違いがいくつかあることを強調しておきたい。すなわち、BlockTimeはプロトコル仕様の合意であり一部であるのに対して、Tは観測者それぞれが独自に定めるものである。公証プロトコルはBlockTimeのみを必要とするのであって、Tは不要である。ファイナライゼーションプロトコルはTのみを必要とするのであって、BlockTimeは必要ない。

アルゴリズム2についての以下の仮定を「正当性の仮定(correctness assumption)」という。

命題6.1

(6.1)の状態が持続しているとすると、アルゴリズム2におけるチェーンCはappend-only(追記のみ可能)である。

このアサーションはアルゴリズム2で「ファイナライズされ」たチェーンCの呼び出しを正当化する。

証明

ChCh+1をそれぞれアルゴリズム2の実行でFINALIZE(h)、FINALIZE(h + 1)により返されるチェーンとする。Nthは時点tにおける集団Nhを表すものとする。明らかにNthtの増加につれて大きくなる。t0t1をそれぞれFINALIZE(h)、FINALIZE(h + 1)が呼び出された時点とする。(6.1)により、t0以降にNhに追加されたブロックで参照されうるようなブロックは1つも存在しない。換言すれば、Nh+1がいつ考慮されるかに関わらずprv(Nh+1) ⊆ Nt0hがある。従って、

ネットワークのトラバーサルタイムがΔで制限されるとき、T ≥ 2Δならば(6.1)の状態が持続することを後に示す(理論9.18、命題9.25)。明らかにこの結果はBlockTimeについて何らの仮定も置いていない。すなわち、公証者がBlocktimeに不正な値を選んだ場合でさえもこの結果は有効である。

アルゴリズム2には変形バージョンがあり、それはパラメータTを必要としない。今から時間T経過後にFINALIZE(r - 1)を呼び出す代わりに、変形バージョンではすぐにFINALIZE(r - 2)を呼び出す。系9.19に従ってこれもまた(6.1)を保証するが、この場合はBlockTimeの値が公証者に利用されるという仮定が必要である。

(筆者注)

  • 上記の証明について簡単に捕捉する。
    • まずC(B)という表記は、ヘッドがブロックBであるようなチェーンCという意味である。C ≤ C′という表記は、CがC'のプレフィックスであるという意味である。以上は第4章(DFINITYホワイトペーパー日本語訳5)で既に定義されている通りである。
    • アルゴリズム2で、FINALIZE(h)はC(Nh)をCに入れるプロシージャである。上記証明で宣言している通り、FINALIZE(h)を呼び出した時点がt0なのでその時のC(Nh)をC(Nt0h)と記載する。また同様に上記証明で宣言している通りFINALIZE(h)を呼び出すと結果としてChが返ってくる。以上からC= C(Nt0h)は必然的にこうなる。同様にCh+1 = C(Nt1h+1)も必然的にこうなる。
    • C(Nt0h) ≤ C(prv(Nt1h+1))について理解するには、まずprv(Nt1h+1)がNt0hに含まれる何らかのブロックを参照するハッシュであるという点に注目したい。すなわち、そのようなハッシュがあるという事実自体がNhがt0でファイナライズされていることを示している。一方でファイナライズされてしまえばそれ以降Nhにブロックが追加されてもそのブロックをNh+1が参照してくれることはない。当然Nh+1のファイナライズが行われるNt1h+1の時点においても参照してくれない。ゆえに、必然的にC(Nt0h) ≤ C(prv(Nt1h+1))である。
    • C(prv(Nt1h+1)) ≤ C(Nt1h+1)は第4章の4で述べた(4.5)すなわち、C(prv S) ≤ C(S)を適用したものである。Nt1h+1をSに置き換えてみれば全く同じであることが分かる。(4.5)については第4章(DFINITYホワイトペーパー日本語訳5)を参照されたい。

DFINITYホワイトペーパー日本語訳8 ←← 前)|(次 →→ DFINITYホワイトペーパー日本語訳10

免責

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

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

-ホワイトペーパー
-, , , , , , , , ,

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

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