0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

SymPLONK: ハミルトン流と保存写像を用いた新世代ゼロ知識証明プロトコル

Last updated at Posted at 2025-03-07

1. はじめに

従来の PLONK プロトコルでは、有限体上の多項式補間や高速フーリエ変換 (FFT) に依存する部分が、計算負荷や実装の複雑さの原因となっていました。ここで、ゼロ知識証明は、たとえばブロックチェーンやプライバシー保護のための認証システムにおいて、証明者が秘密情報を漏らさずにその正当性を示すことを可能にする重要な技術です。これにより、個人情報や機密情報を公開せずに信頼性を担保できる点で、現代のセキュリティ要求に非常に適しています。

PLONKは、比較的シンプルな構造と普遍性(あらゆる計算に対して一度の設定で対応可能)から、ゼロ知識証明プロトコルとして高い評価を受けています。しかし、その効率性や実装の容易さという点では、有限体上の補間やFFTに依存するため、計算負荷の増大や数値的不安定性という課題が付きまといます。

そこで、SymPLONKが登場します。

SymPLONKは、有限体の数論的構造を Teichmüllerリフトによって複素数体へ解析的に埋め込み、ケーラー多様体上の保存写像およびハミルトン流という幾何学的枠組みを導入することで、補間および評価変換の事前計算を効率的かつ安定に行える新たなゼロ知識証明プロトコルです。

イメージとしては、従来の有限体演算に伴う低水準の複雑性や数値的不安定性(例えば、フィールド演算)を、幾何学的な抽象化(例えば、シンプレクティック計算法やハミルトン流など)によって隠蔽することで、従来の専用の算術回路に依存せず、より高水準なプログラミング環境(GPUやCPU)上で直接実装することが可能になるという考え方です。

このアプローチにより、従来の代数的手法の限界、すなわち計算コストや実装の複雑さ、数値の不安定性を大幅に低減し、より実用的かつ堅牢な証明生成が可能となります。

注意: 本文は研究段階の成果であり、まだ査読されていない予備的な内容です。実際の応用や実装に際しては、追加の検証と改善が必要であることにご留意ください。

2. 基本定義と構成要素

2.1 ケーラー多様体の構造

  • 多様体 $M$ とその幾何学的構造
    $M$ は複素数体 $\mathbb{C}$ 上の滑らかな多様体で、次の3要素から構成されます:
    • シンプレクティック形式 $\Omega$
      $\Omega$ は閉形式($d\Omega = 0$)であり、局所座標では例えば
      $\Omega = \sum_i dx_i \wedge dy_i$
      と表現され、面積や体積の保存に寄与します.
    • リーマン計量 $g$
      $g$ は正定値計量であり、各点における内積を定義します.
    • 複素構造 $J$
      線形写像 $J: TM \to TM$ が $J^2 = -\mathrm{Id}$ を満たし、
      $g(X,Y) = \Omega(X, JY)$ の関係が成立します.

2.2 解析的リフト(Teichmüllerリフト)

  • 有限体からの埋め込み
    有限体 $\mathbb{F}_q$ の各要素は、Witt ベクトル環 $W(\mathbb{F}_q)$ を介して、
    特徴 0 の体(例:$\mathbb{C}$)へ一意にリフトされます.

    特に、有限体内の原始 $n$ 番目の単根 $\omega$ は、リフト後も
    $\iota(\tilde{\omega})^n = 1$ の性質を保持し、有限体上の補間ドメインを解析的に扱う基盤となります.

2.3 補間ドメイン

  • 定義と保証
    有限体側で
    $D = \{1,\, \omega,\, \omega^2,\, \dots,\, \omega^{n-1}\}$
    と定義される集合を、Teichmüllerリフトにより
    $D = \{1,\, \iota(\tilde{\omega}),\, \iota(\tilde{\omega})^2,\, \dots,\, \iota(\tilde{\omega})^{n-1}\} \subset M$
    とみなします. Schwartz–Zippel 補題により、
    次数 $< n$ の多項式補間の一意性と非退化性が保証されます.

2.4 保存写像とハミルトン流

  • ケーラー等長写像
    $\phi: M \to M$ が $\phi^*\Omega = \Omega,\quad \phi^*g = g,\quad \phi \circ J = J \circ \phi$ を満たすとき、
    これをケーラー等長写像と呼び、$\Omega$ と $g$ という幾何学的構造の保存を保証します.

  • ハミルトン関数とハミルトン流
    滑らかな関数 $H: M \to \mathbb{R}$ に対し、ハミルトンベクトル場 $X_H$ を
    $\iota_{X_H}\Omega = dH$
    により定義し、初期値問題
    $\frac{d}{dt}\phi_t(x) = X_H(\phi_t(x)),\quad \phi_0(x)=x$
    の解 $\{\phi_t\}_{t\in\mathbb{R}}$ をハミルトン流と呼び、
    Picard–Lindelöf の定理によりその一意性が保証されます.

2.5 PLONKプロトコルにおける評価ドメイン

多項式補間に使用される評価ドメインは、単一根(primitive roots)で構成されます。具体的には、体の原始 $\omega$は、体の $n$ 番目の単根として定義され、以下の条件を満たします。

$$
\omega^n = 1 \quad \text{かつ} \quad \omega^k \neq 1 \quad \text{(ただし } 0 < k < n \text{)}.
$$

この評価ドメイン

$$
D = \{1,\, \omega,\, \omega^2,\, \dots,\, \omega^{n-1}\}
$$

は、多項式補間の一意性と非退化性を保証するための重要な役割を果たし、PLONKプロトコルにおける多項式評価やコミットメントの構築に利用されます。

2.6 補題と補助定理

本プロトコルの理論的基盤を支えるいくつかの補題と補助定理を以下に示します。これらの結果は、保存写像とハミルトン流の存在および一意性、並びに補間問題の非退化性を厳密に保証するための重要な役割を果たします。

補題 1 (Cartan の魔法の公式)

任意の滑らかなベクトル場 $X$ に対して、シンプレクティック形式 $\Omega$ の Lie 微分は
$$
\mathcal{L}_X \Omega = d(\iota_X \Omega) + \iota_X(d\Omega)
$$
と表されます。特に、$\Omega$ が閉形式($d\Omega = 0$)の場合、
$$
\mathcal{L}_X \Omega = d(\iota_X \Omega)
$$
となり、保存写像の性質を解析する上で不可欠な結果です。

補題 2 (Poincaré 補題)

単連結な開集合 $U \subset \mathbb{C}^m$ において、任意の閉形式 $\alpha$ は正確である、すなわち
$$
\alpha = d\beta
$$
となる滑らかな微分形式 $\beta$ が存在します。
これにより、特に閉形式 $\iota_X \Omega$ が正確であり、ハミルトン関数 $H$ の存在が保証されます。

補題 3 (Schwartz–Zippel 補題)

補間ドメイン
$$
D = \{1,\, \omega,\, \omega^2,\, \dots,\, \omega^{n-1}\}
$$
に対して、次数が $n$ 未満の非零多項式 $f \in \mathbb{C}[x]$ は、
$$
\Pr_{x \in D}[f(x)=0] \le \frac{\deg f}{n} < 1
$$
を満たします。これにより、補間問題における一意性と非退化性が理論的に保証されます。

補助定理 (Teichmüller lift)

有限体 $\mathbb{F}_q$ に対して、Witt ベクトル環 $W(\mathbb{F}_q)$ は特徴 0 の完備離散評価環となり、
各 $a \in \mathbb{F}_q$ に対して一意な Teichmüller代表元 $\tilde{a}$ が存在して
$$
\tilde{a}^q = \tilde{a}
$$
を満たします。特に、有限体の原始単根 $\omega$ はリフト後も
$$
\iota(\tilde{\omega})^n = 1
$$
の性質を保持し、有限体側の補間問題が複素数体内で解析的に扱える基盤となります。

補助定理 (Killing 場の一意性)

ケーラー多様体 $M$ 上で、リーマン計量 $g$ とシンプレクティック形式 $\Omega$ を
同時に保存する Killing 場は、初期条件が定まれば一意に存在します。

これにより、保存写像の無限小生成元 $X$ の一意性が保証され、
後述のハミルトン流の一意性の証明の重要な一部となります.

3. Teichmüller–Kähler Hamiltonian Flow Theorem(仮)

定理
以下の仮定の下で、$M$ 上に保存写像と対応するハミルトン流が一意に存在し、
その性質が PLONK の補間および評価変換に応用可能であることを示します.

仮定

  1. $M$ はケーラー多様体であり、$(\Omega, g, J)$ の構造を満たす.
  2. $M$ は単連結であり、これにより閉形式は正確(Poincaré 補題)となる.
  3. 補間ドメイン
    $D = \{1,\, \iota(\tilde{\omega}),\, \iota(\tilde{\omega})^2,\, \dots,\, \iota(\tilde{\omega})^{n-1}\} \subset M$
    が、Teichmüllerリフトにより構成される.
  4. リー群 $G$ の作用 $G \times M \to M$ により、$g$ と $\Omega$ が保存される.
  5. 有限体側の補間問題は、Teichmüllerリフトにより $\mathbb{C}$ 上で解析的に扱える.

主張

(a) $M$ 上に、$\Omega$ と $g$ を保存する一意なケーラー等長写像 $\phi$ が存在し、
その無限小生成元 $X$ は Killing 場として、
$$\mathcal{L}_X \Omega = 0,\quad \mathcal{L}_X g = 0$$
を満たします.

(b) Cartan の公式により $$d(\iota_X\Omega)=0$$ となるため、単連結性から Poincaré 補題を適用し、
あるハミルトン関数 $H: M \to \mathbb{R}$ が存在し
$$dH = \iota_X\Omega$$
となります.

(c) ハミルトン関数 $H$ により定義されるハミルトンベクトル場 $X_H$
(ここでは $X_H = X$ と同一視可能)を用いると、初期値問題は
$$\frac{d}{dt}\phi_t(x) = X_H(\phi_t(x)),\quad \phi_0(x)=x$$

Picard–Lindelöf の定理により、局所一意な解 $\{\phi_t\}_{t\in\mathbb{R}}$ を与え、
解析条件により全体解へ拡張され、なおかつ流は $\Omega$ と $g$ の保存性を自動的に維持します.

(d) 補間ドメイン $D$ 上では、有限体の乗法構造が保たれ、
Schwartz–Zippel 補題により多項式補間の非退化性が保証されるため、
事前計算されたハミルトン流 $\{\phi_t|_D\}$ は
PLONK の補間および評価変換の前処理として利用可能です.

4. ハミルトン流の一意性の必要十分条件とその検証

命題
ケーラー多様体 $M$(単連結かつ $(\Omega, g, J)$ を有する)上で、
$\Omega$ と $g$ を保存するケーラー等長写像 $\phi$ の無限小生成元 $X$(Killing 場)が存在するとき、
以下の条件は同値です.

  1. $X$ に対して
    $$\mathcal{L}_X \Omega = 0 \quad \text{かつ} \quad \mathcal{L}_X g = 0$$
    が成立し、単連結性から Poincaré 補題により $\iota_X\Omega$ が正確となり、
    ある $H: M \to \mathbb{R}$ が存在して $$dH = \iota_X\Omega$$
    となる.

  2. $H$ の存在により $$dH = \iota_X\Omega$$ が成立していれば、
    対応するハミルトンベクトル場 $X_H$(ここでは $X_H = X$ と同一視可能)が一意に定まり、初期値問題
    $$\frac{d}{dt}\phi_t(x) = X_H(\phi_t(x)),\quad \phi_0(x)=x$$
    は Picard–Lindelöf の定理により一意に解かれ、流は自動的に $\Omega$ と $g$ を保存します.

4.1 直接構成による確認

  • リー群 $G$ の作用(例:「$x \mapsto \omega x$」の巡回作用)から、無限小生成元 $X$ が一意に定まり、
    $$\mathcal{L}_X g = 0 \quad \text{および} \quad \mathcal{L}_X \Omega = 0$$
    を満たします.
  • Cartan の公式により $$d(\iota_X\Omega)=0$$ となり、単連結性を利用して Poincaré 補題を適用することで、
    $$\exists\, H \quad \text{かつ} \quad dH = \iota_X\Omega$$
    が得られます.
  • この $H$ に対応する $X_H$ を用いて、初期値問題の一意性が Picard–Lindelöf により保証されることを確認します.

4.2 背理法による確認

  • 必要条件側
    もし $X$ が $\Omega$ と $g$ を保存しているにもかかわらず、
    $H$ が存在しなければ、$\iota_X\Omega$ は閉であるにもかかわらず正確でなく、
    単連結性に反します.
  • 十分条件側
    $H$ の存在により $$dH = \iota_X\Omega$$ が成立しているにもかかわらず、
    異なるハミルトン流が存在すれば、初期値問題の一意性に反し、
    Picard–Lindelöf の定理に矛盾します.

5. 具体例:標準的なケーラー構造と回転写像

ここでは、$M=\mathbb{C}$ 上の標準的なケーラー構造と回転写像の具体例を示し、
理論の直感的理解と実際の保存写像の挙動を確認します.

5.1 標準的なケーラー構造

  • 多様体と座標
    $M = \mathbb{C}$ を $z = x + iy$ と表記し、実数座標 $x, y$ を用います.
  • シンプレクティック形式
    $$\Omega = dx \wedge dy.$$
  • リーマン計量
    ユークリッド計量
    $$g = dx^2 + dy^2.$$
  • 複素構造
    複素構造 $J$ は
    $$J(x,y) = (-y, x),$$
    と定義され、$J^2 = -\mathrm{Id}$ および $$g(X,Y) = \Omega(X,JY)$$ が成立します.

5.2 回転写像の適用

  • 定義
    $\phi_t: \mathbb{C} \to \mathbb{C}$ を
    $$\phi_t(z) = e^{it}z$$
    と定義します. これは、$z$ を角度 $t$ だけ回転させる写像であり、自然な保存写像の例です.
  • 保存性の確認
    • ユークリッド計量は回転に対して不変で、$$g(\phi_t(z)) = g(z)$$ が成立します.
    • 回転写像は面積保存性から $$\phi_t^*\Omega = \Omega$$ を満たします.
    • $\phi_t$ は複素構造 $J$ と可換 $$\phi_t \circ J = J \circ \phi_t$$
  • 無限小生成元とハミルトン関数
    微分して
    $$X(z) = \left.\frac{d}{dt}\right|_{t=0}\phi_t(z) = iz$$
    と得られ、Cartan の公式により $$\iota_X\Omega = dH$$ が導かれます. 具体的には,
    $$H(z) = \frac{1}{2}|z|^2$$
    として、回転写像がハミルトン流としての性質(保存性・一意性)を明示します.

5.3 逆ハミルトン流とその性質

逆ハミルトン流の定義

ハミルトン流 ${\phi_t}$ がハミルトン関数 $H:M \to \mathbb{R}$ を用いて
$$
\frac{d}{dt}\phi_t(x) = X_H(\phi_t(x)),\quad \phi_0(x)=x
$$
という初期値問題で定義されている場合、その「逆流」はパラメータ $t$ の符号を
反転したものとして自然に定義されます。すなわち、

$$
\phi_{-t}(x)
$$

を考えます。ここで$\phi_{-t}$は、もとの流 $\phi_t$ に対して、
時刻を逆向きに流したものを意味します。

逆ハミルトン流の存在と一意性の数学的保証

逆ハミルトン流 $\phi_{-t}$ は、元のハミルトン流 $\phi_t$ の生成元であるハミルトンベクトル場 $X_H$ に対して、ベクトル場 $-X_H$ を用いて定義されます:

$$
\frac{d}{dt}\phi_{-t}(x) = -X_H(\phi_{-t}(x)),\quad \phi_0(x)=x.
$$

ここで重要なのは、この新たな微分方程式の一意な解が存在することです。実際、Picard–Lindelöfの定理から局所解の一意性が保証され、さらに、ケーラー多様体の完全性や解析性により、この解は全体に一意に延長可能です。

幾何学的保存性の維持

逆ハミルトン流もまた、元のハミルトン流と同様に、
以下の幾何学的不変量を厳密に維持します。

  • シンプレクティック形式の保存:
    $$
    \phi_{-t}^*\Omega = \Omega
    $$

  • リーマン計量の保存:
    $$
    \phi_{-t}^* g = g
    $$

  • 複素構造との整合性:
    $$
    \phi_{-t} \circ J = J \circ \phi_{-t}
    $$

これらの性質は、元の流 $\phi_t$ が持つ性質から直ちに導かれます。
特に、幾何学的構造の完全な保存性は、逆変換が数値的に安定であることを保証します。

逆ハミルトン流のプロトコルにおける役割

SymPLONKプロトコルの検証フェーズでは、Alice(証明者)が送信した変換後のデータ(コミットメント)に対し、Bob(検証者)が「逆変換」を施す必要があります。この逆変換を行うために用いるのが、事前に計算された逆ハミルトン流 $\phi_{-t}$ です。

具体的には:

  • Aliceは秘密情報を隠すために
    元のハミルトン流 $\phi_t$ を用いて多項式評価値を変換(隠蔽)します。
  • Bobは送信された評価値に対して、
    逆ハミルトン流 $\phi_{-t}$ を適用し、元の評価値との整合性を検証します。

6. SymPLONK プロトコルの全体構成と各参加者の役割

本節では、SymPLONKプロトコルの全体的な流れを説明します。暗号学における標準的な役割であるAlice(証明者)、Bob(検証者)、Charlie(攻撃者)の立場を明示的に取り入れ、各フェーズで読者が抱くであろう疑問に答えつつ、プロトコルの安全性がどのように担保されるかを明瞭にします。

6.1 共通パラメータ生成フェーズ(Setup)

目的:
プロトコルの全参加者が共通に使用する数学的パラメータを安全かつ一貫して生成します。

SymPLONK における信頼できるセットアップは、共通参照文字列(CRS)の生成として実現されます。この CRS は、有限体の選定、原始単根の決定、Teichmüllerリフトによる補間ドメインの構成、そしてケーラー多様体上の保存写像およびハミルトン流の事前計算といった要素から構成され、これらのパラメータは透明かつ公に検証可能な方法で生成されるため、プロトコル全体の安全性を担保します。

具体的手順:

  • 有限体 $\mathbb{F}_q$ と原始 $n$ 次単根 $\omega$ を決定します。
  • Teichmüllerリフトを用いて補間ドメイン
    $$
    D = {1,,\iota(\tilde{\omega}),,\dots,,\iota(\tilde{\omega})^{n-1}}\subset M
    $$
    を構成します。
  • ケーラー多様体 $(M,\Omega,g,J)$ の構造を設定し、リー群 $G$ の作用により保存写像 $\phi$ およびハミルトン流 ${\phi_t}$ を事前計算し、公開します。

疑問への解説:

  • 「なぜ事前にパラメータを共有する必要があるのか?」
    → パラメータの共通化は、Aliceが行う証明生成とBobが行う検証の整合性を保証し、信頼性の高いゼロ知識証明を実現するためです。
  • 「Charlieがパラメータを悪用できる可能性はないのか?」
    → 共通パラメータは公開情報ですが、秘密情報を含まず、また保存写像の数学的保証によって不正利用が困難になるよう設計されています。

6.2 証明生成フェーズ(Aliceの役割・Prover)

Aliceの目的:
自身の秘密情報(計算結果や属性)を明かさずに、
その情報を正しく処理したことを証明します。

具体的手順:

  • Step 1:秘密情報の多項式エンコード
    Aliceは秘密情報を多項式$P(x)\in \mathbb{F}_q[x]$に変換します。

  • Step 2:ランダムブラインディング
    秘密情報が漏洩しないよう、ランダム係数$r$とマスキング多項式$M(x)$を選び、
    $$
    \hat{P}(x) = P(x) + r,M(x)
    $$
    として情報を隠蔽します。

  • Step 3:幾何学的変換(ハミルトン流の適用)
    Aliceは補間ドメイン$D$上で評価した$\hat{P}(x)$に対して、事前計算されたハミルトン流${\phi_t|_D}$を適用します。この変換は数学的保存性(シンプレクティック形式やリーマン計量の保存)により安全性が保証されています。

  • Step 4:コミットメントの生成
    変換後の評価値を用いて構造保存型コミットメントを生成し、Bobに送信します。

疑問への解説:

  • 「なぜ多項式を使うのか?」
    → 多項式を使うことで数学的な補間問題として情報を効率的に処理・保護し、非退化性(Schwartz–Zippel 補題)を活用できます。
  • 「ブラインディングは本当に安全なのか?」
    → ランダムブラインディングは秘密情報の復元を数学的に困難にし、Charlieによる逆算攻撃を防ぎます。

6.3 証明検証フェーズ(Bobの役割・Verifier)

Bobの目的:
Aliceの証明が正当であることを、秘密情報に直接アクセスせずに検証します。

具体的手順:

  • Step 1:パラメータ受信
    Aliceからコミットメント、タイムスタンプ、ハミルトン流の変換パラメータなどを受信します。

  • Step 2:逆変換の適用
    Bobは事前に計算された逆ハミルトン流$\phi_{-t}$を適用し、コミットメントに含まれる評価値を逆変換して元の多項式の評価値との整合性を検証します。

  • Step 3:幾何学的不変量の検証
    変換前後で保存されるシンプレクティック形式やリーマン計量に由来する幾何学的不変量(内積や面積)を利用して整合性を代数的・数値的に検証します。

疑問への解説:

  • 「Bobは本当に秘密情報を得られないのか?」
    → Bobはコミットメントと不変量をチェックするのみであり、秘密情報そのものを復元する手段を持ちません。数学的保証によってゼロ知識性が担保されています。

6.4 攻撃者視点での安全性分析(Charlieの役割・Adversary)

Charlieの目的:
コミットメントを改ざんするか、コミットメントから秘密情報を抽出することです。

このプロトコルにおける困難性は、単なる「計算量が大きい」というだけでなく、暗号学的前提に基づく難解な問題を組み合わせたものです。

例えば、以下の点が挙げられます。

  1. ウィットネスの秘密性の保持:
    Alice の秘密情報(ウィットネス)は、通常NP困難な問題や高いエントロピーを持つ情報に基づいてエンコードされます。Charlie がこれを推測または再現するには、実質的に全探索や既知の難解な問題を解く必要があり、現実的な計算資源では破ることができません。

  2. ランダムブラインディングの難解性:
    ブラインディングに使用されるランダム係数やマスキング多項式は十分な乱数性を持っており、これを模倣して同一のブラインディングを再現するには、暗号的に安全な乱数生成の強度(たとえば128ビットや256ビットのセキュリティレベル)が必要です。これにより、Charlie が同じブラインディングを作り出すのは事実上不可能となります。

  3. 保存写像とハミルトン流の正確な再現:
    事前計算されたハミルトン流から、正確に同一の微小な時間区間を選び、同じ変換結果を再現するためには、極めて精密な時間パラメータの管理と逆変換処理が要求されます。この部分は、数学的に一方向性が保証された変換に依存しているため、逆算は暗号学的に困難です。

  4. コミットメントのバインディング性:
    構造保存型コミットメントは、コミットメントからウィットネスを復元できないように設計されており、これを破るには、通常、暗号学的なハードネス(例えば、離散対数問題や楕円曲線離散対数問題など)の計算量に匹敵する困難性が要求されます。

具体的な難易度の数値としては、例えば128ビットや256ビットのセキュリティレベルを持つとすれば、Charlie が成功するためには約 $2^{128}$ あるいは $2^{256}$ 回の計算が必要となります。これは、現代の計算技術では実用的な時間内に達成することは不可能です。

まとめると、各段階で必要な計算は、暗号学的前提に基づく高度な困難性(例えば、 $2^{128}$ 〜 $2^{256}$ 回の操作が必要なレベル)を要求しており、これらが組み合わさることで、Charlie がAliceに成り代わって正しい証明を作成するのは、実質的に不可能とされています。

攻撃可能性

  • Charlieはコミットメントを傍受・改ざんしようと試みることがあります。
  • ランダムブラインディングや変換パラメータから秘密情報を逆算しようとします。

疑問への解説:
「Charlieが攻撃に成功する可能性はゼロか?」

理論上ゼロとは言えませんが、SymPLONKの設計上、多重の数学的保証と検証プロセスの厳格性により、攻撃の成功確率は事実上無視可能に抑えられています。

具体的に、Charlie が Alice に成り代わって同じ証明を用意するためには、秘密情報の完全な復元、正確な多項式エンコード、ランダムブラインディングの模倣、事前計算されたハミルトン流から適切な時間区間の選択、そして構造保存型コミットメントの生成といった、Alice が証明生成の際に実行するすべての作業を、プロトコルの安全性の前提条件(ウィットネスの秘密性、コミットメントのバインディング性、保存写像の不変性など)
を突破する形で正確に行う必要があります。

Alice が証明生成の際に利用しているハミルトン流や変換パラメータは、非常に高精度な数値列(例えば 10⁻¹⁰ 桁程度の精度が要求されるような)を、事前計算した任意の期間(十分に長い時間)において、誤差が蓄積しないような形で行わなければならなりません。


6.5 実装上の注意点と今後の展望

  • 数値安定性:
    実際の実装では浮動小数点演算の誤差や精度管理に注意する必要があります。

  • 計算効率性:
    ハミルトン流の事前計算および逆変換の効率化がプロトコル全体の性能に影響します。

  • 拡張性:
    今後はより複雑なケーラー多様体や保存写像の採用を検討し、プロトコルの適用範囲を広げることが期待されます。

7. 結論

本稿は、SymPLONK プロトコルの意図とモチベーションを明確にし、
以下の点を中心に論じました.

  1. 新たな理論的枠組みの構築
    従来の PLONK の数論的手法に代わり、Teichmüllerリフトとケーラー多様体上の保存写像・ハミルトン流を導入することで、補間および評価変換の効率性と安全性を大幅に向上させる新たなアプローチを提供します.

  2. 理論の定義と証明
    ケーラー多様体、Teichmüllerリフト、補間ドメイン、保存写像、ハミルトン流といった基本概念を統一的に定義し、Teichmüller–Kähler Hamiltonian Flow Theorem とハミルトン流の一意性の必要十分条件を、直接構成および背理法によって確認しました.

  3. 具体例による直感的理解の促進
    $M=\mathbb{C}$ 上の標準的なケーラー構造と回転写像の具体例を通じて、理論がどのように実装されるかを明確に示し、 読者が保存写像やハミルトン流の意義を直感的に理解できるようにしました.

  4. プロトコル全体の流れと参加者の役割の明確化
    Alice(証明者)、Bob(検証者)、Charlie(攻撃者)の各視点から、プロトコルの各フェーズの目的、手順、安全性の担保方法を、読者が「なぜこの手順が必要なのか」「どのように安全性が確保されるのか」を説明しました.

注意:
本稿は、著者が有限体の数論的構造を維持したまま、トポロジカルな観点で誤差累積が抑制された、堅牢で高精度なプロトコルの構築の可能性を探るものです。重ねて慎重な議論と検証が必要な旨、ご留意ください。

8. デモンストレーション

image.png

出力結果
==================================================
SymPLONK Protocol Demonstration (Finite Field with Teichmüller Lift)
==================================================
A geometric approach to zero-knowledge proofs using Kähler manifolds

Setup complete: n=8, p=17
Finite field domain D_f: [1, 2, 4, 8, 16, 15, 13, 9]
Teichmüller-lifted domain D (in ℂ): [ 1.    +0.j      0.7071-0.7071j -0.    -1.j     -0.7071-0.7071j
 -1.    +0.j     -0.7071+0.7071j  0.    +1.j      0.7071+0.7071j]

=== Alice (Prover) ===
Secret data (finite field elements mod 17): [1, 2, 3, 4]
Polynomial encoding (with Teichmüller lift) complete
Random blinding applied with coefficient r = -0.3871+1.7026j
Hamiltonian flow applied with time t = 0.7854
Commitment generated and ready to send to verifier

=== Bob (Verifier) ===
Received commitment from Alice
Flow time parameter: t = 0.7854
Inverse Hamiltonian flow applied
L2 norm of difference: 3.00222453e-16
Verification SUCCESS: Geometric invariants preserved

==================================================
Verification result: SUCCESS
==================================================

Visualizing 3D comparison (Before vs. After Branding)...
フルコード
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
import matplotlib.cm as cm
import math
from typing import List, Tuple, Dict, Optional, Union, Any, TypeVar, Callable
import numpy.typing as npt
from dataclasses import dataclass
from functools import lru_cache

# Type aliases
ComplexArray = npt.NDArray[np.complex128]
RealArray = npt.NDArray[np.float64]
T = TypeVar('T')

@dataclass
class Commitment:
    """Data structure representing the zero-knowledge proof commitment."""
    transformed_evaluations: ComplexArray
    flow_time: float
    secret_original_evaluations: ComplexArray
    r: complex
    mask: ComplexArray

class FiniteFieldUtils:
    """Utility class for finite field operations."""
    
    @staticmethod
    @lru_cache(maxsize=128)
    def divisors(n: int) -> List[int]:
        """Compute all divisors of the integer n."""
        divs = set()
        for i in range(1, int(math.sqrt(n)) + 1):
            if n % i == 0:
                divs.add(i)
                divs.add(n // i)
        return sorted(list(divs))
    
    @staticmethod
    def prime_factors(n: int) -> List[int]:
        """Compute the prime factors of the integer n."""
        i, factors = 2, []
        while i * i <= n:
            if n % i:
                i += 1
            else:
                n //= i
                if i not in factors:
                    factors.append(i)
        if n > 1 and n not in factors:
            factors.append(n)
        return factors
    
    @classmethod
    def find_primitive_nth_root(cls, n: int, p: int) -> Optional[int]:
        """
        Find a primitive nth root of unity ω_f in F_p.
        Requires that n divides (p - 1).
        
        Args:
            n: Order of the root of unity
            p: Prime modulus for the finite field F_p
            
        Returns:
            A primitive nth root of unity in F_p, or None if none exists
        """
        if (p - 1) % n != 0:
            print(f"Warning: n={n} is not a divisor of p-1={p-1}")
            
        # Precompute proper divisors for efficiency
        divisors = cls.divisors(n)
        proper_divisors = [d for d in divisors if d < n]
        
        for candidate in range(2, p):
            if pow(candidate, n, p) != 1:
                continue
            if all(pow(candidate, d, p) != 1 for d in proper_divisors):
                return candidate
        return None
    
    @classmethod
    def find_primitive_root(cls, p: int) -> Optional[int]:
        """
        Find a primitive element (generator) of F_p (of order p-1).
        
        Args:
            p: Prime modulus for the finite field F_p
            
        Returns:
            A primitive element of F_p, or None if none exists
        """
        factors = cls.prime_factors(p - 1)
        coprime_exponents = [(p - 1) // f for f in factors]
        
        for candidate in range(2, p):
            if all(pow(candidate, exp, p) != 1 for exp in coprime_exponents):
                return candidate
        return None
    
    @staticmethod
    def discrete_log(a: int, g: int, p: int) -> int:
        """
        Compute the discrete logarithm: find k such that g^k ≡ a (mod p).
        For small p, brute-force search is used; for larger p, Baby-step Giant-step is applied.
        
        Args:
            a: Target element in F_p
            g: Generator element in F_p
            p: Prime modulus for the finite field F_p
            
        Returns:
            k such that g^k ≡ a (mod p)
            
        Raises:
            ValueError: If no discrete log exists
        """
        if p < 100:  # Brute-force for small p
            for k in range(p - 1):
                if pow(g, k, p) == a:
                    return k
        else:
            m = int(math.sqrt(p - 1)) + 1
            # Baby-step
            baby_steps = {pow(g, j, p): j for j in range(m)}
            g_inv = pow(g, p - 1 - m, p)  # g^(-m) mod p
            value = a
            for i in range(m):
                if value in baby_steps:
                    return (i * m + baby_steps[value]) % (p - 1)
                value = (value * g_inv) % p
        raise ValueError(f"No discrete log exists: a={a}, g={g}, p={p}")

class HamiltonianFlow:
    """Handles Hamiltonian flow operations for complex numbers."""
    
    @staticmethod
    def hamiltonian_function(z: complex) -> float:
        """
        Define Hamiltonian function H(z) = 1/2 |z|^2 (for potential energy, etc.)
        
        Args:
            z: Complex number
            
        Returns:
            Energy value H(z)
        """
        return 0.5 * np.abs(z)**2
    
    @staticmethod
    def apply_flow(points: ComplexArray, t: float, epsilon: float = 1e-8) -> ComplexArray:
        """
        Apply the Hamiltonian flow (rotation) to complex points.
        For circular flow, the analytical solution is: z(t) = z(0) * exp(i*t)
        
        Args:
            points: Array of complex numbers
            t: Flow time parameter
            epsilon: Numerical error tolerance
            
        Returns:
            Transformed array of complex numbers
        """
        if abs(t) < epsilon:
            return points
        return points * np.exp(1j * t)
    
    @classmethod
    def apply_inverse_flow(cls, points: ComplexArray, t: float, epsilon: float = 1e-8) -> ComplexArray:
        """
        Apply the inverse Hamiltonian flow.
        
        Args:
            points: Array of complex numbers
            t: Flow time parameter
            epsilon: Numerical error tolerance
            
        Returns:
            Inverse-transformed array of complex numbers
        """
        return cls.apply_flow(points, -t, epsilon)


class SymPLONK:
    """
    SymPLONK:
    Demonstrates a geometric zero-knowledge proof protocol by mapping a finite field
    interpolation domain to complex numbers via the Teichmüller lift, then applying
    a Hamiltonian flow (rotation) to hide and later verify secret information.
    """
    def __init__(self, n: int = 8, p: int = 17, epsilon: float = 1e-8):
        """
        Initialize the SymPLONK protocol.
        
        Args:
            n: Number of interpolation points
            p: Prime for finite field F_p
            epsilon: Numerical error tolerance
        
        Raises:
            ValueError: If primitive roots cannot be found
        """
        self.n = n                  # Number of interpolation points
        self.p = p                  # Prime for finite field F_p
        self.epsilon = epsilon      # Numerical error tolerance
        
        # Define the interpolation domain in F_p: D_f = { ω_f^0, ω_f^1, ..., ω_f^(n-1) }
        self.omega_f = FiniteFieldUtils.find_primitive_nth_root(n, p)
        if self.omega_f is None:
            raise ValueError(f"Could not find a primitive {n}th root in F_{p}")
        self.D_f = [pow(self.omega_f, i, p) for i in range(n)]
        
        # Find a primitive element g of F_p* (used for computing discrete logs)
        self.g = FiniteFieldUtils.find_primitive_root(p)
        if self.g is None:
            raise ValueError(f"Could not find a primitive root for F_{p}")
        
        # Apply the Teichmüller lift to each element in D_f to obtain complex points
        self.D = np.array([self._teichmuller_lift(a) for a in self.D_f], dtype=np.complex128)
        
        # Initialize the Hamiltonian flow handler
        self.flow = HamiltonianFlow()

        self._log_setup_info()
    
    def _log_setup_info(self) -> None:
        """Log initialization information."""
        print(f"Setup complete: n={self.n}, p={self.p}")
        print(f"Finite field domain D_f: {self.D_f}")
        print(f"Teichmüller-lifted domain D (in ℂ): {np.around(self.D, 4)}")

    def _teichmuller_lift(self, a: int) -> complex:
        """
        Teichmüller lift of an element a in F_p.
          - If a == 0, returns 0.
          - For nonzero a, find k such that a ≡ g^k (mod p), then return exp(2πi * k/(p-1)).
        
        Args:
            a: Element in F_p
        
        Returns:
            Complex number representing the Teichmüller lift of a
            
        Raises:
            ValueError: If the primitive root is not set
        """
        if a == 0:
            return complex(0.0, 0.0)
        if self.g is None:
            raise ValueError("Primitive root is not set")
        k = FiniteFieldUtils.discrete_log(a, self.g, self.p)
        return np.exp(2j * np.pi * k / (self.p - 1))
    
    def polynomial_encode(self, secret: List[int]) -> ComplexArray:
        """
        Encode the secret (a list of elements in F_p) as a polynomial f(x) and evaluate it at the domain points.
        Then, apply the Teichmüller lift to convert each evaluation to a complex number.
        Horner's method is used for efficient polynomial evaluation.
        
        Args:
            secret: List of integers representing the secret data (mod p)
            
        Returns:
            Array of complex numbers representing the encoded secret
        """
        coeffs = [0] * self.n
        for j in range(min(len(secret), self.n)):
            coeffs[j] = secret[j] % self.p
            
        evaluations = []
        for x in self.D_f:
            val = 0
            for coeff in reversed(coeffs):
                val = (val * x + coeff) % self.p
            evaluations.append(self._teichmuller_lift(val))
            
        return np.array(evaluations, dtype=np.complex128)
    
    def blind_evaluations(self, evaluations: ComplexArray, r: Optional[complex] = None) -> Tuple[ComplexArray, complex, ComplexArray]:
        """
        Apply random blinding to the polynomial evaluations (complex numbers).
        A normalized random mask is generated for numerical stability.
        
        Args:
            evaluations: Array of complex numbers to blind
            r: Optional blinding factor (random complex number)
            
        Returns:
            Tuple containing:
            - Blinded evaluations
            - Blinding factor r
            - Blinding mask
        """
        if r is None:
            r = complex(np.random.normal(), np.random.normal())
        mask = np.array([complex(np.random.normal(), np.random.normal()) for _ in range(self.n)], dtype=np.complex128)
        mask = mask / np.linalg.norm(mask)
        return evaluations + r * mask, r, mask
    
    def alice_prove(self, secret: List[int], flow_time: float = np.pi/4) -> Commitment:
        """
        Alice's protocol:
          1. Encode the secret as a polynomial and evaluate it on the domain.
          2. Apply random blinding.
          3. Apply Hamiltonian flow (rotation).
          4. Generate and return the commitment.
        
        Args:
            secret: List of integers representing the secret data (mod p)
            flow_time: Time parameter for the Hamiltonian flow
            
        Returns:
            Commitment object containing the proof data
        """
        print("\n=== Alice (Prover) ===")
        print(f"Secret data (finite field elements mod {self.p}): {secret}")
        
        evaluations = self.polynomial_encode(secret)
        print("Polynomial encoding (with Teichmüller lift) complete")
        
        blinded_evals, r, mask = self.blind_evaluations(evaluations)
        print(f"Random blinding applied with coefficient r = {r:.4f}")
        
        transformed_evals = self.flow.apply_flow(blinded_evals, flow_time, self.epsilon)
        print(f"Hamiltonian flow applied with time t = {flow_time:.4f}")
        
        commitment = Commitment(
            transformed_evaluations=transformed_evals,
            flow_time=flow_time,
            secret_original_evaluations=evaluations,
            r=r,
            mask=mask
        )
        
        print("Commitment generated and ready to send to verifier")
        return commitment
    
    def bob_verify(self, commitment: Union[Commitment, Dict[str, Any]]) -> bool:
        """
        Bob's protocol:
          1. Apply the inverse Hamiltonian flow to the commitment.
          2. Verify that the masked (blinded) evaluations are preserved.
        Verification is performed by computing the L2 norm of the difference.
        
        Args:
            commitment: Commitment object or dictionary containing the proof data
            
        Returns:
            Boolean indicating whether verification succeeded
        """
        print("\n=== Bob (Verifier) ===")
        print("Received commitment from Alice")
        
        if isinstance(commitment, dict):
            comm = Commitment(
                transformed_evaluations=commitment['transformed_evaluations'],
                flow_time=commitment['flow_time'],
                secret_original_evaluations=commitment['secret_original_evaluations'],
                r=commitment['r'],
                mask=commitment['mask']
            )
        else:
            comm = commitment
        
        flow_time = comm.flow_time
        print(f"Flow time parameter: t = {flow_time:.4f}")
        
        recovered_evals = self.flow.apply_inverse_flow(comm.transformed_evaluations, flow_time, self.epsilon)
        print("Inverse Hamiltonian flow applied")
        
        original = comm.secret_original_evaluations
        r = comm.r
        mask = comm.mask
        blinded = original + r * mask
        
        norm_diff = np.linalg.norm(recovered_evals - blinded)
        print(f"L2 norm of difference: {norm_diff:.8e}")
        
        is_verified = norm_diff < self.epsilon
        print(f"Verification {'SUCCESS' if is_verified else 'FAILED'}: " 
              f"Geometric invariants {'preserved' if is_verified else 'not preserved'}")
        return is_verified
    
    def visualize_flow_3d_comparison(self, secret: List[int], flow_time: float = np.pi, num_steps: int = 100) -> None:
        """
        3D visualization comparing the trajectories before and after branding.
        
        Left subplot: Plain domain (Teichmüller-lifted points without blinding)
        Right subplot: Masked evaluations (after applying polynomial encoding and random blinding)
        Both are rotated according to the analytical Hamiltonian flow.
        
        Args:
            secret: List of integers representing the secret data (mod p)
            flow_time: Maximum time parameter for the Hamiltonian flow
            num_steps: Number of time steps for visualization
        """
        times = np.linspace(0, flow_time, num_steps)
        
        # Compute plain trajectories from the precomputed Teichmüller-lifted domain (self.D)
        plain_start = self.D
        plain_trajs = self._compute_trajectories(plain_start, times)
        
        # Compute polynomial encoding and then apply random blinding (without flow)
        plain_evals = self.polynomial_encode(secret)
        blinded_evals, r, mask = self.blind_evaluations(plain_evals)
        blinded_start = blinded_evals
        blinded_trajs = self._compute_trajectories(blinded_start, times)
        
        self._plot_3d_comparison(plain_trajs, blinded_trajs, times, flow_time)
    
    def _compute_trajectories(self, start_points: ComplexArray, times: RealArray) -> List[ComplexArray]:
        """
        Compute trajectories for a set of starting points.
        
        Args:
            start_points: Array of complex numbers representing starting points
            times: Array of time values
            
        Returns:
            List of trajectories (arrays of complex numbers)
        """
        trajectories = []
        for z in start_points:
            traj = z * np.exp(1j * times)
            trajectories.append(traj)
        return trajectories
    
    def _plot_3d_comparison(self, plain_trajs: List[ComplexArray], blinded_trajs: List[ComplexArray], 
                           times: RealArray, flow_time: float) -> None:
        """
        Plot 3D comparison of trajectories.
        
        Args:
            plain_trajs: List of trajectories for plain points
            blinded_trajs: List of trajectories for blinded points
            times: Array of time values
            flow_time: Maximum time parameter
        """
        # Create 3D subplots for comparison
        fig = plt.figure(figsize=(16, 8))
        
        # Left subplot: Before branding
        ax1 = fig.add_subplot(121, projection='3d')
        ax1.set_title("Before Branding")
        ax1.set_xlabel("Re(z)")
        ax1.set_ylabel("Im(z)")
        ax1.set_zlabel("Time t")
        ax1.set_xlim(-1.5, 1.5)
        ax1.set_ylim(-1.5, 1.5)
        ax1.set_zlim(0, flow_time)
        colors = cm.viridis(np.linspace(0, 1, self.n))
        
        self._plot_trajectories(ax1, plain_trajs, times, colors)
        
        # Right subplot: After branding
        ax2 = fig.add_subplot(122, projection='3d')
        ax2.set_title("After Branding")
        ax2.set_xlabel("Re(z)")
        ax2.set_ylabel("Im(z)")
        ax2.set_zlabel("Time t")
        ax2.set_xlim(-1.5, 1.5)
        ax2.set_ylim(-1.5, 1.5)
        ax2.set_zlim(0, flow_time)
        
        self._plot_trajectories(ax2, blinded_trajs, times, colors)
        
        plt.tight_layout()
        plt.show()
    
    def _plot_trajectories(self, ax: plt.Axes, trajectories: List[ComplexArray], 
                          times: RealArray, colors: np.ndarray) -> None:
        """
        Plot trajectories on a given axes.
        
        Args:
            ax: Matplotlib axes to plot on
            trajectories: List of trajectories (arrays of complex numbers)
            times: Array of time values
            colors: Array of colors for each trajectory
        """
        for i, traj in enumerate(trajectories):
            xs = traj.real
            ys = traj.imag
            ax.plot(xs, ys, times, color=colors[i], lw=2)
            ax.scatter(xs[0], ys[0], times[0], color=colors[i], s=50, edgecolor='black')
            ax.scatter(xs[-1], ys[-1], times[-1], color=colors[i], s=50, edgecolor='white')


def run_demo() -> None:
    """Run demonstration of the SymPLONK protocol with 3D comparison visualization."""
    print("="*50)
    print("SymPLONK Protocol Demonstration (Finite Field with Teichmüller Lift)")
    print("="*50)
    print("A geometric approach to zero-knowledge proofs using Kähler manifolds\n")
    
    symplonk = SymPLONK(n=8, p=17, epsilon=1e-15)
    secret = [1, 2, 3, 4]
    
    commitment = symplonk.alice_prove(secret)
    verification_result = symplonk.bob_verify(commitment)
    
    print("\n" + "="*50)
    print(f"Verification result: {'SUCCESS' if verification_result else 'FAILED'}")
    print("="*50)
    
    print("\nVisualizing 3D comparison (Before vs. After Branding)...")
    symplonk.visualize_flow_3d_comparison(secret, flow_time=np.pi, num_steps=100)
    
    print("\nDemonstration complete!")


if __name__ == "__main__":
    run_demo()

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?