Arweave 第 17 版白皮书解読（3）：SPoRes ゲームの論証

この記事は少しハードコアです。多くの数学的な導出と証明プロセスが含まれているので、皆さんは準備をしておいてください。しかし、筆者は数学が基礎学問として、論理的に物事を説明する際に非常に高い精度を持っていると考えています。ですので、@ArweaveEco メカニズムにおける数学の美しさを簡単な言葉で示してみたいと思います。

ホワイトペーパー解読（2）記事では、簡潔アクセス証明（ #SPoA ）ゲームが、参加者がデータセットの特定の位置に実際にデータを保存していることを証明するために使用できることを説明しました。このパターンは、簡潔な複製証明（Succinct Proofs of Replications #SPoRes ）という第二のゲームを作成するためにも使用でき、これにより証明者はデータセットのサイズに関係なく、非常に少ないデータ転送と検証コストで、検証者に一定数のデータのコピーを保存していることを証明できます。

✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨

SPoRes ゲーム

簡潔な複製証明（SPoRes）ゲームは次のように進行します。アリスは、n 部のマーケル化データセットの唯一のコピーを保存していると主張します。ボブはアリスが嘘をついていないか確認したいと思っています。そのために、彼はアリスに難易度パラメータ d とランダムに生成されたシード Seed を与えます。アリスはこの Seed を使用して、毎秒チェックポイントを発生させる VDF ハッシュチェーンを生成します。このチェックポイントは、データセット内の最大 k 個の SPoA チャレンジを解除するために使用できます。彼女がこれらのチャレンジに対応するパッケージデータブロックを持っているとき、アリスは対応する SPoA 証明を構築できます。それからこれらの証明をハッシュ処理し、ボブの難易度パラメータ d と比較します。証明のハッシュ値が d より大きければ、アリスは有効な解決策を見つけたことになり、対応する証明をボブに送信します。ボブは、ランダムシードを送信してからアリスの有効な証明を受け取るまでの時間を記録します。

難易度 d に基づいて、有効な解決策を見つけるための単一の試行の確率 p の表現は次のようになります：

公式注釈：SHA 256 ベースのアルゴリズムは 256 ビットの文字列であるため、最大ハッシュ数は 2\^256（ここで「\^」は累乗を意味します）です。d より大きい有効な解決策を見つけるには、2\^256-d のハッシュ数しかないため、単一の試行が成功する確率を計算できます。

アリスが n 個のコピーを持ち、各コピーが毎秒 k 回試行できる場合、彼女が任意の与えられた 1 秒の間に解決策を見つける確率は次のようになります：

公式注釈：kN はアリスが 1 秒間に行えるハッシュ解決策の試行回数を意味します。この試行回数はアリスが保存している唯一のコピーの数に比例します。具体的な説明は以前の記事「Arweave 2.6 はおそらく中本聡のビジョンにより合致する」の内容を参照してください。1-p は単一の試行が失敗する確率です。p2 の確率値は、kN 回の試行が失敗する確率の差です。

上記の 2 つの公式を代入して導出することで、次のようになります：

公式注釈：p を P2 の公式に代入した結果です。

アリスが証明を提出するのに必要な時間は、幾何学的なランダム変数 X ~ geom(p2) でシミュレートできます。p2 は成功の確率です。このランダム変数 X は d、k、および n に依存します。アリスが嘘をついていないか確認するために、ボブは難易度 d を送信し、アリスが n 個のコピーを持っている前提で、120 秒ごとにボブに証明を提出できるようにします。これは、アリスが 120 秒の間に成功する確率が次のようになることを意味します：

公式注釈：1/120 は 120 秒内に証明を成功裏に提出する確率です。

アリスが要求された時間内に証明を提出できる場合、彼女は正しい数の唯一のコピーを持っている可能性が高いです。しかし、1 回の証明だけではボブがアリスが嘘をついていないと確信するには不十分です。アリスが長期間にわたって平均して 120 秒ごとに証明を提出できる場合、ボブはアリスが期待されるデータ量を保存していると合理的に確信できます。

次に、ボブがアリスの保存している確実性を定量化しようとします。

アリスが 20 個のコピーを保存していると主張し、2 週間の間に平均 120 秒の速度で一貫して証明を提出した場合（合計 10,080 個の証明を提出）、この時ボブはアリスが 19 個（またはそれ以下）のコピーしか保存していない場合でも、これらの証明を提出できる確率はどれくらいかを考えます。これは、異なる 1 秒の間に証明を提供する確率に対応します：

公式注釈：ここでの 19k は、アリスが 19 個のコピーを保存しており、各コピーが解決策を見つけるために k 回の試行を持つことを意味します。

過度に単純化すると：

この確率は、ボブが誠実なアリスのために生成した d 値を使用して計算できます。彼女が 19 個以下のコピーを保存している場合、彼女が 1 秒間に証明を提供する確率は、次の一連の導出によって得られます。ここで、p2 はアリスが誠実に 20 個のコピーを保存しているときの 1 秒間に証明を生成する確率を表し、p2* は彼女が嘘をついている（保存 ≤ 19 個のコピー）場合の 1 秒間に証明を提供する確率を表します：

この導出プロセスは複雑に見えますが、基本的な数学的能力を持つ友人であれば誰でも理解できます。導出プロセスは、上記の会社の代入プロセスです。

したがって、p2*=0.00791832081 であり、期待される証明生成時間は 126.2894 秒です。X* を p2* から得られるアリスの証明提出時間とし、すなわち X*~ geom(p2*) です。これは、アリスが嘘をついている場合 ------ つまり、19 個のコピーしか保存していない場合に、証明を提出するのにかかる時間 X* の期待値（平均値）が次のようになることを示します：

公式注釈：E[X*] は、アリスが 19 個のコピーしか保存していない場合に、成功裏に証明を提出する平均時間が 126.2894 秒であることを示します。もし彼女が 20 個のコピーを保存していれば、成功裏に提出する時間は平均して 120 秒です。

中心極限定理を使用して、サンプル平均が 120 未満である確率を推定できます。これは、上記の期待値 E[X*] とは異なります。この確率は次のように表されます：

公式注釈：等式の左側の表現は、2 週間の間にアリスが平均して証明を提出する時間が 120 秒以下である確率を表します。等式の右側は、左側の表現の変形です。

大量のサンプルに対して、この不等式の左側は平均 E[X*] と分散 σX*\^2/n の正規分布に近づきます。ここで、σX* は Xd の標準偏差であり、n（ここでは =10,080）はサンプルサイズです。したがって、上記の公式は次のように変形できます：

この分布を標準正規形式に変換して、同等の確率を得ることができます：

最終的に、標準正規分布表を使用して、アリスがこの 2 週間の期間中に嘘をついている確率を得ることができます：

したがって、この例では、ボブは約 99.99997416% の確実性を持って、アリスがこの 2 週間の間に 19 以上のデータセットのコピーを保存していたと判断できます。アリスが保存しているコピーが 19 未満であれば、期待される証明提出時間は 126.3 秒を超えることに注意してください。また、全体の証明システムは、120 秒ごとに証明を 1 回送信するだけで済みます。これは、アリスとボブの間の平均データ転送率が毎秒 2.389 KB（280 KB/120 秒）であり、ビットコインネットワークの同期オーバーヘッドに相当します。

最後に、これらの確率はデータセットのサイズが任意に増加しても変わらず、サンプリング期間を増やすことでボブがアリスのコピー数に対する確実性の精度が超線形の速度で向上し続けることがわかります（図1）。

図 1：簡潔複製証明（SPoRes）ゲームにおいて、確実性はサンプル持続時間の増加に対して超線形です。2 週間のサンプル収集を経て、19 個未満のコピーを維持する確率は微々たるものです（P\<0.0000002584）。

したがって、SPoRes ゲームは次のパラメータで定義されます：

ここで：

r= ゲームに使用されるデータセットのマーケルルート。

k= 各コピーが毎秒に解除できる最大のチャレンジ数。

d= 各試行時の成功確率を決定する難易度パラメータ。

✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨✨

これらの興味深い数学的導出を通じて、合理的な時間内にマイナーが継続的に証明を提出する限り、データが保存されているかどうかを確実に判断できることを安心して確認できます。これは、Arweave が分散ストレージを目指すコンセンサスメカニズムの核心を形成します。数学の楽しさはまだ始まったばかりで、次の記事ではさらに興味深い推論と証明が続く予定です。