ZKProphet: GPUにおけるゼロ知識証明のパフォーマンス理解

1. はじめに

ゼロ知識証明（ZKPs）は、証明者（Prover）が秘密入力に関する知識を、その秘密自体に関する情報を一切明かすことなく示すことを可能にする革新的な暗号プロトコルです。この能力により、プライベートな暗号通貨、検証可能な計算の外部委託、ブロックチェーンのスケーリングソリューションなど、変革的な応用が実現されています。ZKPの採用における根本的な課題は、証明生成に必要な多大な計算オーバーヘッドであり、複雑な計算の場合、最新のCPUでも数分かかることがあります。

GPUは、中核となる計算カーネルのデータ並列性の高さから、ZKPの主要なアクセラレーションプラットフォームとして台頭しています。図1に示すように、GPUで加速されたZKPは、CPU実装と比較して最大200倍の高速化を実現しています。しかし、これらの印象的な向上にもかかわらず、最新のGPUアーキテクチャにおける性能ボトルネックとスケーラビリティの限界に関する体系的な特性評価は、文献において顕著に欠けていました。

2. 背景と関連研究

2.1 ゼロ知識証明の基礎

ゼロ知識証明は、証明者（Prover）が公開関数$f$と入力$x$に対して$f(x,w) = y$となる証人$w$の知識を、$w$に関する情報を一切明かすことなく検証者（Verifier）に納得させることができるという原理に基づいて動作します。本研究の基礎をなすGroth16プロトコルは、簡潔な証明とサブミリ秒単位の検証時間を提供し、実世界の応用に特に適しています。

2.2 暗号技術におけるGPUアクセラレーション

暗号プリミティブのGPUアクセラレーションに関する以前の研究では、大幅な性能向上が実証されています。[19,30,31,42]などの研究は、GPUの並列アーキテクチャが、特に大規模な数学的計算を含む暗号操作に適していることを示しています。しかし、これらの取り組みは主に個々のカーネルに焦点を当てており、エンドツーエンドのシステム性能には重点を置いていませんでした。

3. 方法論と実験設定

3.1 ZKProphetフレームワーク

ZKProphetは、GPU上のZKP性能を評価するための包括的な分析フレームワークを提供します。このフレームワークは、ZKP生成における計算ワークロードの95%以上を占める、Multi-Scalar Multiplication（MSM）およびNumber-Theoretic Transform（NTT）を含む中核的な計算カーネルを体系的に評価します。

3.2 ベンチマーク設定

我々の実験設定では、NVIDIAのAmpereおよびAda Lovelace世代の最新GPUアーキテクチャを利用しています。証明される計算の複雑さを表す様々な制約数にわたって性能を評価します。ベンチマークには、合成ワークロードと、暗号通貨およびブロックチェーンドメインからの実世界のZKP応用の両方が含まれます。

4. 性能分析結果

4.1 カーネル性能の内訳

我々の分析は、性能ボトルネックにおける重要な変化を明らかにしています。以前の研究はMSM操作の最適化に重点を置いていましたが、現代の最適化されたMSM実装では、NTT操作が証明生成レイテンシの最大90%を占めることがわかりました。これは、NTT最適化に新たに焦点を当てる必要がある重要なパラダイムシフトを表しています。

図1: 証明者速度向上率 vs 制約数
実験結果は、GPU実装がCPUベースラインに対して大幅な高速化を提供し、大規模な制約セットでは最大200倍の改善で、性能が制約数に対してほぼ線形にスケーリングすることを示しています。

4.2 スケーラビリティ分析

ZKP計算はGPUの32ビット整数パイプラインでのみ排他的に実行され、内在的なデータ依存性により命令レベルの並列性が制限されていることが観察されました。これは、浮動小数点能力ではなく、利用可能な整数演算ユニットに基づいて性能スケーリングが根本的に制限されることを意味します。

5. 技術的実装の詳細

5.1 数学的基礎

ZKPの中核となる数学的操作は、大きな素数体上の有限体演算に依存しています。有限体におけるフーリエ変換の特殊な形式であるNTT操作は、次のように表されます：

$$X_k = \sum_{j=0}^{n-1} x_j \cdot \omega^{jk} \mod p$$

ここで、$\omega$は法$p$における原始$n$乗根、$p$は大きな素数です。逆NTTも同様に$\omega^{-1}$を用いて定義されます。

5.2 コード実装

以下の擬似コードは、GPUアーキテクチャ向けの最適化されたNTT実装を示しています：

__global__ void ntt_kernel(uint32_t *a, uint32_t *roots, int n) {
    int tid = threadIdx.x + blockIdx.x * blockDim.x;
    int stride = blockDim.x * gridDim.x;
    
    for (int i = tid; i < n/2; i += stride) {
        int j = bit_reverse(i, log2(n));
        if (i < j) {
            swap(a[i], a[j]);
        }
    }
    
    __syncthreads();
    
    for (int len = 2; len <= n; len <<= 1) {
        int half = len >> 1;
        for (int i = tid; i < n; i += stride) {
            if ((i & (len - 1)) < half) {
                uint32_t u = a[i];
                uint32_t v = mul_mod(a[i + half], roots[len + (i & (half - 1))]);
                a[i] = add_mod(u, v);
                a[i + half] = sub_mod(u, v);
            }
        }
        __syncthreads();
    }
}

6. 将来の応用と方向性

GPU上のZKPの最適化は、数多くの応用の可能性を開きます。ブロックチェーン技術において、最適化されたZKPは、より効率的なロールアップソリューションとプライバシー保護スマートコントラクトを可能にします。[32]などの研究で探求されている検証可能な機械学習においては、GPU加速されたZKPが、独自のモデルパラメータを明かすことなく、モデル推論の実用的な検証を可能にする可能性があります。

将来の研究方向性には、GPUテンソルコアをより効果的に利用するための混合精度演算の探求、専用のハードウェア・ソフトウェア協調設計アプローチの開発、特定のハードウェア能力と応用要件に基づいてZKPパラメータを自動調整する適応的最適化フレームワークの作成が含まれます。

独自分析

ZKProphet研究は、最新GPUアーキテクチャにおけるゼロ知識証明の性能特性を理解する上で重要な進歩を表しています。Ben-Sassonら（2014）によるzk-SNARKsに関する基礎研究のような以前の研究が理論的基礎を確立し、libsnarkやbellmanのような後続の実装が実用的なフレームワークを提供しましたが、計算パイプライン全体にわたる体系的な性能分析には顕著なギャップがありました。

新しい主要ボトルネックとしてのNTTの特定（レイテンシの最大90%を占める）は、最適化の優先順位における重要な変化を示しています。この発見は、初期の最適化が最も明白なボトルネックを対象とし、初期の改善後に二次的な制約が支配的になるという、他の計算集約型ドメインでの観察と一致しています。同様のパターンは、楕円曲線操作を最適化した後、メモリアクセスパターンが制限要因となったブロックチェーンシステム向けの暗号実装でも観察されています。

32ビット整数パイプラインの排他的使用は、課題と機会の両方を提示します。テンソルコアとFP32/FP16演算を多用する機械学習ワークロードとは異なり、ZKPは現在のGPUアーキテクチャではこれらの特殊化されたユニットの恩恵を受けることができません。これは、ニューラルネットワーク向けのGoogleのTPUアーキテクチャで採用されたアプローチに類似していますが、暗号操作に特化したハードウェア・ソフトウェア協調設計の可能性を示唆しています。データ依存性による命令レベルの並列性の制限は、より多くの並列性を引き出すことができるアルゴリズムの革新の必要性をさらに強調しています。

[9]で参照されている準同型暗号や検証可能計算フレームワークなどの他の暗号アクセラレーションの取り組みと比較して、ZKProphetが個々のカーネル最適化ではなくエンドツーエンドの性能に焦点を当てていることは、実世界での展開により実用的な洞察を提供します。[32]での検証可能な機械学習応用への言及は、GPU加速されたZKPがAIシステムにおける新しい信頼モデルを可能にする可能性がある、有望なクロスドメイン応用を示唆しています。

本研究で特定された性能スケーラビリティの限界は、本番システムにおけるZKPの実用的な展開に重要な意味を持ちます。より複雑な計算に伴って制約数が増加するにつれて、線形スケーリング関係は、暗号ワークロードに特化したアーキテクチャの革新なしには、現在のGPUアーキテクチャが根本的な限界に直面する可能性があることを示唆しています。

7. 参考文献

Groth, J. (2016). "On the Size of Pairing-Based Non-interactive Arguments." EUROCRYPT 2016.
Ben-Sasson, E., et al. (2014). "Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture." USENIX Security Symposium.
Parno, B., et al. (2013). "Pinocchio: Nearly Practical Verifiable Computation." IEEE Symposium on Security and Privacy.
Setty, S., et al. (2013). "Resolving the conflict between generality and plausibility in verified computation." EuroSys.
Zhang, J., et al. (2020). "vCNN: Verifiable Convolutional Neural Network based on zk-SNARKs." Cryptology ePrint Archive.
Wahby, R.S., et al. (2018). "Full accounting for verifiable outsourcing." CCS.
Kosba, A., et al. (2016). "C∅C∅: A Framework for Building Composable Zero-Knowledge Proofs." USENIX Security.
Xie, T., et al. (2022). "zkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy." CCS.

目次

200倍

90%

32ビット