ZKProphet: GPU에서의 영지식 증명 성능 이해

1. 서론

영지식 증명(ZKPs)은 한 당사자(증명자)가 비밀 자체에 대한 어떤 정보도 공개하지 않고 비밀 입력에 대한 지식을 입증할 수 있는 혁신적인 암호화 프로토콜을 나타냅니다. 이 능력은 개인 정보 보호 암호화폐, 검증 가능한 계산 아웃소싱 및 블록체인 확장 솔루션에서 변혁적인 응용 분야를 가능하게 했습니다. ZKP 채택의 근본적인 과제는 증명 생성에 필요한 상당한 계산 오버헤드로, 복잡한 계산의 경우 최신 CPU에서 몇 분이 소요될 수 있습니다.

GPU는 핵심 계산 커널의 데이터 병렬 특성으로 인해 ZKP의 주요 가속 플랫폼으로 부상했습니다. 그림 1에서 보여주듯이, GPU 가속 ZKP는 CPU 구현 대비 최대 200배의 성능 향상을 보여줍니다. 그러나 이러한 인상적인 성능 향상에도 불구하고, 현대 GPU 아키텍처에서의 성능 병목 현상과 확장성 한계에 대한 체계적인 특성 분석은 문헌에서 현저히 부족했습니다.

2. 배경 및 관련 연구

2.1 영지식 증명 기본 개념

영지식 증명은 증명자가 공개 함수 $f$ 및 입력 $x$에 대해 $f(x,w) = y$를 만족하는 증인 $w$에 대한 지식을 $w$에 대한 어떤 정보도 공개하지 않고 검증자에게 납득시킬 수 있다는 원리에 따라 작동합니다. 본 연구의 기초를 이루는 Groth16 프로토콜은 간결한 증명과 밀리초 미만의 검증 시간을 제공하여 실제 응용 분야에 특히 적합합니다.

2.2 암호화에서의 GPU 가속화

암호화 기본 요소의 GPU 가속화에 대한 이전 연구는 상당한 성능 향상을 입증했습니다. [19,30,31,42]와 같은 연구들은 GPU의 병렬 아키텍처가 암호화 연산, 특히 대규모 수학 계산을 포함하는 연산에 매우 적합하다는 것을 보여주었습니다. 그러나 이러한 노력은 주로 개별 커널에 초점을 맞추었으며 종단 간 시스템 성능보다는 부분적인 최적화에 집중했습니다.

3. 방법론 및 실험 설정

3.1 ZKProphet 프레임워크

ZKProphet은 GPU에서 ZKP 성능을 평가하기 위한 종합 분석 프레임워크를 제공합니다. 이 프레임워크는 ZKP 생성에서 계산 작업량의 95% 이상을 차지하는 다중 스칼라 곱셈(MSM) 및 수론적 변환(NTT)을 포함한 핵심 계산 커널을 체계적으로 평가합니다.

3.2 벤치마크 구성

우리의 실험 설정은 NVIDIA의 Ampere 및 Ada Lovelace 세대의 현대 GPU 아키텍처를 활용합니다. 우리는 증명되는 계산의 복잡성을 나타내는 다양한 제약 조건 수에 걸쳐 성능을 평가합니다. 벤치마크에는 합성 작업 부하와 암호화폐 및 블록체인 도메인의 실제 ZKP 응용 프로그램이 모두 포함됩니다.

4. 성능 분석 결과

4.1 커널 성능 세부 분석

우리의 분석은 성능 병목 현상에서 중요한 변화를 보여줍니다. 이전 연구가 MSM 연산 최적화에 크게 집중한 반면, 우리는 현대적으로 최적화된 MSM 구현에서 NTT 연산이 이제 증명 생성 지연 시간의 최대 90%를 차지한다는 것을 발견했습니다. 이는 NTT 최적화에 대한 새로운 집중이 필요한 중요한 패러다임 전환을 나타냅니다.

그림 1: 제약 조건 수 대비 증명자 성능 향상
실험 결과는 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 et al. (2014)의 zk-SNARK에 대한 기초 연구와 같은 이전 연구가 이론적 기초를确立했고, 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비트