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能夠實現更高效的匯總解決方案和隱私保護智能合約。對於可驗證機器學習，如[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位元