Re: レイテンシーと局所性

人物: Red

このアイデアを頭ごなしに否定する理由を探せば、見つかるだろう。しかし、なぜ一部の P2P システムは成功し、多くは失敗するのかを理解するためにこの例を使えば、何かしらの洞察が得られるはずだ。

その精神で、質問に直接答えよう。

ギャビン・アンドレセンの投稿(2010年8月6日 14:32 UTC)

どちらのトランザクションが先だったかについて意見が分かれたらどうなるのか?多数決か?誰が多数派を決定するのか、そして 5 つのノードのうち 4 つがネットワークを離れ、別の 5 つのノードに置き換わった場合、結果は変わりうるのか?

その out-point を使う他のトランザクションが 1 つでも見つかれば二重支払いだ。現在の Bitcoin システムと同じルールだ。意見の不一致が起こり得るのは、競合するトランザクションが同時にブロードキャストされ、一方がノード A に先に到着し、競合する方がノード E に先に到着した場合だけだ。2 つの 5 ノードブロードキャストが完了するまでに、双方が二重支払いを発見する。

ではどちらが有効か?どちらでもいい。コインを投げればいい。Bitcoin はこの状況でまさにそうしている。自分のノードがあるトランザクションを含むブロックに取り組んでいて、あなたのノードが競合するトランザクションを含むブロックに取り組んでいる場合、先にブロックを解いた方が勝つ。分散コイン投げアルゴリズムは自明だ。これらすべてはほぼ即座に実行できる。10分間のウィンドウよりはるかに速い。だから 4 ノードが離脱しても多数派は変わらない。合意はすでに達成され、ノードは整合性が取れた状態になっているからだ。

ちなみに、標準的な DHT はノードが離脱した時のデータ保持と、ノードが参加した時のデータ分散にすでに対応している。

ギャビン・アンドレセンの投稿(2010年8月6日 14:32 UTC)

また、大きなトランザクションを作成しようとしていることが分かっている場合、そのトランザクション(まだ送信していない)が自分の支配下にあるノードにハッシュされるよう、ノード ID を事前計算することはできないのか?トランザクションを保存するすべてのノードを支配していれば、「はい、間違いなく、そのトランザクションは有効で二重支払いはありません」と回答するだけで済む……

いいえ、これは要件上の制約だ。同じ理由で不可能だ——2 つの公開鍵が同じ Bitcoin アドレスに一致するものを生成することが不可能なのと同じだ。以前の私の失言を参照してほしい。

ノードは Bitcoin アドレスと全く同じように秘密鍵に基づいてノードアドレスを生成する。これによりノードのなりすましは非現実的になる。out-point ハッシュへのすべての入力は受取人を除いて固定されており、受取人は事前に指定されている。唯一の柔軟性は支払い額だろう。すべての可能な金額を反復して同時に 5 方向のハッシュ衝突を作ろうとするなら、どうぞ好きにしてくれ。

ギャビン・アンドレセンの投稿(2010年8月6日 14:32 UTC)

Bitcoin の背後にある素晴らしい洞察は、分散型タイムスタンプの仕組みだ。全員がトランザクションの順序に合意する。あなたの方式がその問題をどう解決するのか、私には分からない。

実は全く同じ方法で問題を解決する。ただ CPU パワーがはるかに少なくて済む。

Bitcoin の分散タイムスタンプメカニズムの背後にある素晴らしい洞察は、絶対的なタイムスタンプは全く必要ないということだ!必要なのは相対的な順序だけだ。短いウィンドウ内での競合については、気にする必要すらない。単に任意に 1 つを選べばいい。

私の解決策はまさに同じことをする。トランザクション間の相対的な順序を維持する。競合については任意に合意に達する。どちらの方法も、無関係なトランザクションを時間順に正確に並べる必要はない。繰り返すが、あれは素晴らしい洞察だった。