ZKProphet：解構零知識證明喺GPU上嘅效能表現

1. 簡介

零知識證明（ZKPs）係一種革命性嘅密碼協議，容許一方（證明者）喺唔洩露任何秘密輸入資訊嘅情況下，向另一方（驗證者）證明自己知道某個秘密輸入。呢種能力已經為私隱加密貨幣、可驗證計算外判同區塊鏈擴容方案帶嚟突破性應用。ZKP應用嘅主要挑戰在於證明生成所需嘅龐大計算開銷，對於複雜運算，現代CPU可能需要幾分鐘先完成。

由於核心計算核心具有數據並行特性，GPU已成為ZKP嘅主要加速平台。如圖1所示，GPU加速嘅ZKP相比CPU實現可以達到高達200倍嘅加速效果。然而，儘管有呢啲令人印象深刻嘅效能提升，現有文獻仍然缺乏對現代GPU架構上效能樽頸同擴展限制嘅系統性分析。

2. 背景與相關研究

2.1 零知識證明基礎

零知識證明嘅運作原理係，證明者能夠說服驗證者自己知道某個見證$w$，用於公共函數$f$同輸入$x$，使得$f(x,w) = y$，而過程中唔會洩露任何關於$w$嘅資訊。作為本研究基礎嘅Groth16協議，提供簡潔證明同亞毫秒級驗證時間，令佢特別適合實際應用。

2.2 GPU喺密碼學中嘅加速應用

先前關於GPU加速密碼原語嘅研究已經展示咗顯著嘅效能提升。好似[19,30,31,42]等研究顯示，GPU嘅並行架構非常適合密碼運算，特別係涉及大規模數學計算嘅操作。然而，呢啲努力主要集中喺單獨核心運算，而唔係端到端系統效能。

3. 方法論與實驗設置

3.1 ZKProphet框架

ZKProphet提供一個全面分析框架，用於評估ZKP喺GPU上嘅效能表現。該框架系統性評估核心計算核心，包括多標量乘法（MSM）同數論轉換（NTT），兩者合共佔ZKP生成計算工作量超過95%。

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. 未來應用與發展方向

ZKP喺GPU上嘅優化開啟咗眾多應用可能性。喺區塊鏈技術中，優化ZKP可以實現更高效嘅rollup解決方案同私隱保護智能合約。對於可驗證機器學習，正如[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位元