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安培和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可以实现更高效的Rollup解决方案和隐私保护智能合约。对于可验证机器学习，如[32]等工作中所探索的，GPU加速的ZKP可以在不泄露专有模型参数的情况下，实现模型推理的实际验证。

未来的研究方向包括探索混合精度算术以更好地利用GPU张量核心，开发专门的软硬件协同设计方法，以及创建能够根据特定硬件能力和应用需求自动调整ZKP参数的自适应优化框架。

深度分析

ZKProphet研究代表了在理解现代GPU架构上零知识证明性能特征方面的重大进展。虽然先前的研究，如Ben-Sasson等人（2014）关于zk-SNARKs的基础性工作奠定了理论基础，以及后续如libsnark和bellman等实现提供了实用框架，但在整个计算流水线的系统性性能分析方面一直存在显著空白。

将NTT识别为新的主要瓶颈（占延迟的90%）标志着优化优先级的重大转变。这一发现与其他计算密集型领域的观察结果一致，即初始优化针对最明显的瓶颈，但在初步改进后，次要约束条件会变得主导。在区块链系统的密码学实现中也观察到了类似模式，在优化椭圆曲线操作后，内存访问模式成为限制因素。

仅使用32位整数流水线既带来挑战也带来机遇。与大量利用张量核心和FP32/FP16算术的机器学习工作负载不同，ZKPs在当前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位