[영지식증명] ZK-CNN 파헤치기 - 1

안녕하세요, 오늘부터는 ZK-CNN 논문에 대하여 살펴보도록 하겠습니다. ZK-CNN은 영지식증명을 통해 기계학습의 결과를 증명하는 Zero-Knowledge Machine Learning (ZKML) 분야의 논문입니다. 해당 논문에서는 영지식증명을 활용해 비전 분야에서 많이 활용되는 Convolutional Neural Network (CNN) 을 증명하는 방법을 제안하고 있습니다. 저에게도 도전적인 논문인데요, 같이 한번 살펴보고 질문이나 잘못이해한 부분 있다면 같이 이야기해보면 좋을 것 같습니다. 

 

Introduction

우선 본격적으로 protocol에 대하여 알아보기 전에, ZK-CNN 이 왜 필요한지, 어떤식으로 작동하는 protocol인지에 대하여 먼저 살펴보도록 하겠습니다. Prover가 이미 학습된 CNN 모델을 가지고 있다고 가정하겠습니다. Prover는 많은 노력을 쏟은 자신의 모델에 대한 정보를 유출하지 않으면서, verifier에게 자신이 실제로 올바른 연산을 수행했다는 사실을 증명하고 싶습니다. ZK-CNN은 여기에 맞는 protocol을 제공함으로 prover는 자신이 올바른 모델을 돌렸음을 증명하고, verifier도 자신이 올바른 결과값을 전달받았다는 사실을 증명받도록 할 수 있습니다. 

 

좀 더 구체적인 증명과정은 다음과 같습니다. 

1. public key generation: prover는 public key 를 생성합니다. 

2. com_w: prover 가 ZK-CNN 프로토콜을 통해 자신의 모델에 대한 commitmen를 생성합니다. 

3. (y, $\pi$): 어떠한 데이터 $X$가 주어졌을 때, ZK-CNN 프로토콜을 통해 CNN을 통한 proof $\pi$와 결과값 $y$를 제공합니다.

4. verify: verifier는 prover가 사전에 제공한 commitment와 추후에 제공한 proof를 통해 prover가 올바른 증명을 만들어냈는지 검증합니다. 검증이 통과한다면 verifier는 prover가 올바른 연산을 통해 결과값을 제공했음을 알 수 있습니다. 

 

Overview

ZK-CNN의 과정은 세 파트로 나눌 수 있습니다.

1) Fast Fourier Transform (FFT) 에대한 새로운 Sumcheck Protocol 제안

2) CNN에서 사용되는 2D convolution의 1D convolution 수식으로 변환

3) 1D convolution을 FFT 로 증명 

 

앞으로의 블로그 글을 통해 이에 대한 과정들을 하나씩 알아볼 예정입니다. 

우선 이번 시간에는, Fast Fourier Transform (FFT) 에 대한 새로운 Sumcheck Protocol에 대하여 알아보겠습니다. 

 

New Sumcheck for Fast Fourier Transform

FFT는 어떠한 주어진 함수를 여러 진동수를 갖는 $sin, cos$ 함수로 변환하는 알고리즘입니다. FFT는 음성인식, 시스템 결함 측정 등 정말 많은 분야에서 사용됩니다. FFT가 어떻게 convolution을 증명하는데 사용되는지는 ZK-CNN의 3번 과정에서 알아보도록 하고, 우선은 FFT를 증명하기 위한 새로운 Sumcheck Protocol에 집중해보도록 하겠습니다. 

 

FFT는 어떠한 polynomial 이 있을 때, 해당 polynomial의 계수에서부터 root of unity 에서 해당 polynomial의 evaluation 값으로 변환할 수 있습니다. 예를 들어, $\mathbf{c} = (c_0, c_1, \dots, c_{N-1})$ 을 해당 polynomial의 계수에 해당하는 벡터, $\mathbf{a} = (a_0, a_1, \dots, a_{M-1})$ 을 해당 polynomial을 각 root of unity $(\omega^0, \omega_1, \dots,  \omega^{M-1})$에서 evlaution 한 결과라고 하겠습니다. 여기서 $\omega$는 M-th root of unity 로서, $\omega^M = 1 \text{ mod p}$인 성질을 갖고 있습니다. 벡터 $\mathbf{c}, \mathbf{a}$는 가장 가까운 2의 거듭제곱승에 맞도록 패딩되게 됩니다. 또한 정의에 의하여, $a_j = \sum^{N-1}_{i=0} c_i \omega^{ji}$로 나타낼 수 있는데요, 이것은 또한 행렬-벡터 연산 식으로 다음과 같이도 나타낼 수 있습니다. $\mathbf{a} = F \cdot \mathbf{c}$. 해당 식에서의 $F$는 다음과 같이 정의되게 됩니다. 

 

$F = \begin{equation} \begin{bmatrix} 1 & 1 & 1 & \dots & 1 \\ 1 & \omega^1 & \omega^2 & \dots & \omega^{N-1} \\ \vdots & \vdots & \vdots & \vdots & \vdots \\ 1 & \omega^{M-1} & \omega^{2(M-1)} & \dots & \omega^{(M-1)(N-1)}\end{bmatrix} \end{equation}$

 

여기서 한가지 중요한 점은, FFT에서 $\omega^M = 1$이기 때문에, $F$ 내부에는 $M$개의 distinct 한 값들만 존재한다는 사실입니다. 이러한 성질 덕분에 $F$와 $\mathbf{a}$는 빠른 시간에 계산될 수 있다고 하는데요, 해당 방법론을 여기서 다루지는 않도록 하겠습니다. 

 

그 다음으로 우리가 진행하고 싶은 것은, 랜덤한 값에서 $\mathbf{a}$의 multilinear extension이 주어졌을 때, 이것을 $c$의 multilinear extension에서의 evaluation 으로 증명할 수 있게끔 수정하는 것입니다. 이를 위해서 우리는 $\mathbf{a}$와 $c$의 multilinear extension 간의 관계를 서술하게 됩니다. 

$\tilde{a}(y) = \sum_{x \in \{0, 1\}^{logN}} \tilde{c}(x) \tilde{F}(y, x)$

즉 $\mathbf{a}$에서의 evaluation은 $c$의 multilinear extension에 대한 sumcheck protocol을 통해 증명해낼 수 있습니다. 여기서 또한, 자세한 증명 과정 (where prover's time complexity is $O(N)$)은 다루지 않도록 하겠습니다.

FFT Sumcheck Protocol 알고리즘

위에 구체적인 Sumcheck Protocol이 기술되어 있습니다. 기본적인 모양새는 전에 살펴보았던 Sumcheck Protocol과 유사합니다. 여기서 prover의 time complexity 가 커지는 부분은, $A_F$를 만드는 과정입니다. Naive 한 과정을 통해 해당 array를 만들면, $O(MN)$의 시간이 걸리게 됩니다. 따라서 이 cost를 줄기이 위한 방법이 제안됩니다. 

여기서 모든 수식 정리를 다루지 않겠지만, 논문에서 수식 정리를 통해 $\tilde{F}(u, x) = \prod^{logM - 1}_{i=0}((1-u_i)+ u_i \cdot \omega^X_{2_{i+1}}$임을 보이게 됩니다. 또한 이렇게 수식이 정리가 되면, 아래 있는 Algorithm2를 통해 $O(M + N)$의 time complexity 에 해당 $A_F$를 만들어내게 됩니다. 

A_F generation algorithm

 

지금까지 소개된 알고리즘을 다시 살펴보면, Sumcheck Protocol 중간에 prover는 $\tilde(F)(\cdot)$을 계산해야 하는 과정이 포함되어 있습니다. ZK-CNN은 이 cost 를 다시 좀 더 줄일 수 있는 방법을 제안합니다. Notation을 조금 abuse 하여 $\tilde{A}_F^{i}$를 Algorithm 2의 첫 for loop에서 i 번째 iteration 까지 계산된 $A_F$ entry 라고 하겠습니다. 이러한 notation에서 verifier가 계산해야하는 $\tilde(F)(\cdot)$ 는 $\tilde{A}_F^{logN - 1}$로 표현될 수 있습니다.

 

그렇다면 앞서 살펴본 것처럼 $\tilde{A}_F^{(i)}(x, b) = \sum_{z \in \{0, 1\}^i} \tilde{\beta}(x, z) \tilde{A}_F^{(i-1)}(z) ((1-u_i)+u_i \cdot \tilde{\omega}_{i+1}(z, b)$ 처럼 나타낼 수 있습니다. 이제 verifier 가 $\tilde{F}(u, v)$를 계산해야 하는 상황에서, prover와 verifier는 대신 각 i에 대하여 Sumcheck Protocol을 통해 prover 가 제공해준 evaluation이 맞는지 화깅ㄴ하는 과정으로 reduce 할 수 있습니다. 이러한 방식을 통해 verifier time 이 $O(log^2 N)$으로 줄일 수 있다고 합니다. 

 

Conclusion

오늘은 ZK-CNN에 대한 overview와 함께 해당 프로토콜의 첫번째 단계로서 FFT에 대한 새로운 Sumcheck Protocol에 대하여 알아보았습니다. 궁금하신 부분 있다면 댓글로 남겨주셔서 같이 이야기해보아도 좋을 것 같습니다. 다음 시간에는 2D convolution을 1D convolution으로 reduce 하는 방법에 대하여 알아보도록 하겠습니다. 긴 글 읽어주셔서 감사합니다 :)