本文へ移動
Financial Context Wiki

暗号学的アキュムレータ

RSA方式とハッシュベース方式、メンバーシップ証人と非メンバーシップ証人、動的更新、ブロックチェーンでの用途、運用上のリスクを扱う、検証に重点を置いた暗号学的アキュムレータのガイドです。

更新日

教育目的に限られ、投資助言または暗号実装に関する助言ではありません。アキュムレータ証明が認証するのは、ある1つのコミットメントに対する主張であり、基礎データ、コンセンサス状態、データ可用性そのものではありません。

直接的な回答

暗号学的アキュムレータは、集合を短い値にコミットし、ある要素がコミット済み集合に含まれることを簡潔な証人によって検証できるようにします。方式によっては非メンバーシップも証明できます。検証者が必要とするのはアキュムレータ値、要素、証人、および方式の公開パラメータであり、集合内のほかのすべての要素ではありません。

集合が変化した後に再構築が必要ならアキュムレータは静的、追加や削除に伴ってアキュムレータと証人を効率よく更新できるなら動的、メンバーシップ証明と非メンバーシップ証明の両方に対応するならユニバーサルです。これらは別々の能力を表す名称であり、動的な方式が自動的にユニバーサルになるわけではありません。

ブロックチェーンでは、トランザクション、未使用アウトプット、アカウント、バリデータ、失効記録などにコミットできます。コミットメントを小さくすれば一部参加者が保持する状態を減らせますが、システムはなお基礎データと最新の証人を配布し、更新を認証し、チェーン再編成を処理し、誰が集合を変更できるかを定義しなければなりません。

仕組み

  1. 集合を厳密に指定します。 要素の正規エンコーディング、重複の扱い、該当する場合の順序規則、ドメイン分離、およびコミットメントの正確なバージョンを定義します。あるエンコーディングや状態ルートに対する証明は、別のものについて何も保証しません。

  2. 方式のセットアップを実行します。 ハッシュベースのアキュムレータは公開ハッシュパラメータだけを使う場合があります。RSAアキュムレータは未知位数群を使用し、通常はRSAモジュラス N から構成されます。その因数分解を権限のない者が悪用できないことが安全性の要件です。ほかの方式では、異なる信頼前提のもとでペアリング、類群、格子、または追加の公開パラメータを利用する場合があります。

  3. 要素を代数構造へ写像します。 単純化したRSA構成では、各要素 x_i を相異なる素数代表 p_i に決定論的に写像します。底を g とすると、アキュムレータは次のとおりです。

    A = g^(p_1 * p_2 * ... * p_n) mod N

  4. メンバーシップ証人を作成します。 p_i で表される要素について、その因子を指数から除きます。

    w_i = g^(product of p_j for all j != i) mod N

  5. 正確なアキュムレータに対して検証します。 検証者は入力が正規形式であることを確認し、次を評価します。

    w_i^(p_i) mod N = A

    この方式の安全性仮定のもとでは、蓄積された集合の外にある要素についてこの等式を成立させるのは実行不可能であるべきです。ただし、この等式は要素自体が真実であることや認可済みであることを示しません。

  6. 更新と非メンバーシップは別々に処理します。 動的方式は、追加や削除によって A がどう変わり、影響を受ける証人をどう更新するかを定義します。ユニバーサル方式は、別個の非メンバーシップ証人と検証アルゴリズムを追加します。実装は、古い証人や異なる状態に結び付いた更新を拒否しなければなりません。

  7. ハッシュベース構造は実際のコストで比較します。 広義には、マークルツリーもハッシュベースのアキュムレータです。ルートは短い一方、メンバーシップ証明には経路上の兄弟ハッシュが含まれるため、葉の数に対して対数的に大きくなります。RSA型方式は個々の証人を一定サイズにできますが、証明生成、証人の維持、セットアップ、計算には異なるコストがあります。

計算例

  • マークル証明のサイズ。 1,048,576 = 2^20 枚の葉を持つ平衡二分マークルツリーでは、一本の包含経路に 20 個の兄弟ハッシュが必要です。ハッシュが 32 バイトなら、葉データ、位置ビット、シリアライズのオーバーヘッドを除いて 20 * 32 = 640 bytes です。ルートは 32 バイトのままです。
  • 一定サイズでも作業量は一定ではありません。 単純化したRSA構成では、集合が増えても A と1つの w_i はそれぞれ1つの群要素のままです。それでも積の指数、素数代表の生成、バッチ更新、更新済み証人の配布には、多大な計算や補助データが必要になる場合があります。
  • UTXOアキュムレータは、誰が何を保存するかを変えます。 コンパクトな状態を持つノードは未使用アウトプットのアキュムレータを保持し、アウトプットと最新のメンバーシップ証明を受け取った場合にのみ支出を検証できます。ほかの参加者は証明生成に十分な状態を引き続き保持し、更新では使用済みアウトプットを削除して新規作成されたものを追加しなければなりません。
  • 失効にも同じ境界が適用されます。 資格情報の保有者は、識別子が有効メンバーのアキュムレータに残っていることを証明できます。またはユニバーサル方式を使い、失効集合に含まれないことを証明できます。証明が認証するのは発行者がコミットした集合であり、発行者が公正または正確な失効方針を適用したことではありません。

リスク

  • 曖昧または非正規な要素エンコーディングを使い、論理的に同じ項目が異なる値に写像されることを許す。
  • 要素から素数代表への写像を誤る、または方式が要求する衝突制御を行わない。
  • セットアップ担当者や攻撃者が因数分解を知っている可能性のあるRSAモジュラスを信頼する。
  • トランスクリプト、参加者に関する仮定、パラメータの結び付きを検証せず、多者間セットアップセレモニーを安全だとみなす。
  • 認証された移行規則なしに、管理者が公開パラメータやアキュムレータのバージョンを置き換えられるようにする。
  • 古い、未確定の、または攻撃者が選んだアキュムレータ値に対して証人を検証する。
  • 誤ったブロック、フォーク、エポック、または集合バージョンからの追加、削除、証人更新を適用する。
  • メンバーシップ証人が、要素の有効性、所有権、認可、または経済的価値まで証明すると考える。
  • 短いコミットメントがあれば、基礎となる集合が利用可能または復元可能になると考える。
  • 最新の証人を構築するために必要なデータやサービスを失い、有効な状態を利用不能にする。
  • アプリケーションが暗黙に不存在証明へ依存しているのに、非メンバーシップ対応を省く。
  • マークル経路、RSA証人、多項式オープニング、有効性証明を交換可能なものとして混同する。
  • 削除コスト、証人更新トラフィック、証明生成の遅延、またはサービス拒否を狙う入力を無視する。
  • 証明をプロトコル、チェーン、コントラクト、状態ルート、ドメイン、シリアライズバージョンに結び付けない。
  • 独立したテストベクトルがないまま、監査されていない単一実装や独自の算術処理に依存する。
  • 古典的なRSA、ペアリング、離散対数の安全性が、暗号学的に有用な量子コンピュータに対しても保たれると考える。

よくある誤解

  • アキュムレータには集合の圧縮コピーが入っている。 これは拘束力のあるコミットメントであり、可逆的なアーカイブではありません。
  • どのアキュムレータも不存在を証明できる。 非メンバーシップには、その能力を備えるよう設計され、検証された方式が必要です。
  • 一定サイズの証人なら総コストも一定になる。 セットアップ、証明生成、更新、保存、証人配布は、それぞれ別個のコストとして残ります。
  • ステートレスなら誰も状態を保存しない。 要素、更新、証人を作成するには、一部の主体が十分なデータを保持または再構築しなければなりません。
  • 有効な証明があれば、コミットされた項目は真である。 指定された仮定のもとで、その項目を認証済みの1つのコミットメントに結び付けるだけです。
  • マークルツリーとRSAアキュムレータの信頼性・性能特性は同じである。 集合へのコミットメントという目的は共通していますが、前提、証明サイズ、更新手順、障害モードは異なります。

関連トピック

出典

ナビゲーション

Wiki を検索...