[영지식증명] ZK-CNN 파헤치기 3
Introduction
안녕하세요, 지난시간까지 저희는 2D convolution을 새롭게 제안하는 sumcheck protocol을 통해 증명할 수 있는 방법에 대하여 알아보았습니다. 이번 시간에는, 2D convolution에서 그치지 않고, 실제 CNN 에 대한 증명으로 확장하기 위해 필요한 몇가지 테크닉들에 대하여 알아보도록 하겠습니다.
1. Generalized addition and multiplication gates.
기존의 GKR에서 제안되는 arithmetic gate의 경우는 두 가지 input wire를 받게 됩니다. 하지만 CNN의 경우 구조에 따라 이보다 더 많은 input을 받아야 하는 경우가 생기게 됩니다. 따라서 GKR 식을 좀 변형하여 multiple input을 받을 수 있도록 수정해주게 됩니다.
$X \tilde{add}_i(z, x) = \begin{cases} 1 & \text{if }V_{i+1}(x) \text{ is added to } V_i(z) \\ 1 & \text{otherwise} \end{cases}$
$X \tilde{mult}_i(z, x, y) = \begin{cases} 1 & \text{if }V_{i+1}(x) \cdot V_{i+1}(y) \text{ is added to } V_i(z) \\ 1 & \text{otherwise} \end{cases}$
그렇게 된다면, layer $i$ 에서의 multilinear extension 또한 다음과 같이 표현하여 사용하면 됩니다.
$\tilde{V}_i(z) = \sum_{x \in \{0, 1\}^{s_{i+1}}} X\tilde{add}_i(z, x) \cdot \tilde{V}_{i+1}(x) + \sum_{x, y \in \{0, 1\}^{s_{i+1}}} X\tilde{mult}_i(z, x, y) \cdot \tilde{V}_{i+1}(x) \cdot \tilde{V}_{i+1}(y)$
2. Taking inputs from arbitrary layers
또한 CNN의 구조상 바로 직전의 layer 뿐만 아니라, 그 전의 layer 들에서도 input이 넘어오는 경우가 있습니다. 이에 따라 additional 한 node들을 더해주고, 이에 대한 관계식을 추가로 더해주게 되는데요, ZK-CNN은 사전 연구에서의 방법을 채택했고, 본 글에서 더 깊게 다루지는 않도록 하겠습니다. 나름 직관적이기 때문에 궁금하신 분들은 논문을 찾아보셔도 좋을 것 같습니다. :)
3. Converting real numbers
많은 neural network 들의 weight은 소숫점 (floating point) 로 이루어져 있습니다. 이에 반하여 대부분의 zero-knowledge protocol들은 finite field를 가정합니다. 그렇기 때문에 주어진 소숫점을 어떻게 finite field에 맵핑하는지는, ZKML에서 중요한 포인트입니다. 가장 쉬운 방법은, 단순히 주어진 floating point를 scaling (10의 거듭제곱을 곱함) 하는 방법이 되겠고, $a$를 주어진 실수라고 했을 때, $a = L(q - Z)$, ($L$은 parameter 로 scaling factor, $q$는 quantized 된 finite field 위의 원소, $Z$는 zero-point라고 불리우는 finite field 위의 원소) 의 관계식을 통해 실수를 finite field위의 $Q$-bit integer로 변환하기도 합니다.
CNN 구조의 각 레이어에 있는 각각의 커널은 자신의 $Z$값을 갖게 됩니다. 이제 이렇게 된다면, 두 실수 $a_1 = L(q_1 - Z_1), a_2 = L(q_2 - Z_2)$간의 덧셈은, $a_1 + a_2 = L(q_1 + q_2 - Z_1 - Z_2)$로 나타낼 수 있습니다. 또한 비슷하게 두 곱셈은, $L_3(q_3 - Z_3) = L_1(q_1 - Z_1) \cdot L_2(q_2 - Z_2)$, 식을 정리하면 $q_3 = Z_3 + \frac{L_1L_2}{L_3}(q_1 - Z_1) \cdot (q_2 - Z_2)$로 나타낼 수 있습니다. 이렇게 되는 경우 $\frac{L_1L_2}{L_3}$를 제외하고 나머지 값들은 정수값으로 표현되게 됩니다.
여기서 이 값 또한 $2^{-E} \cdot \tilde{e}$로 normalize 해주게 되는데요, 즉 $q_3 = Z_e + 2^{-E} \cdot \tilde{e} \cdot (q_1 - Z_1) \cdot (q_2 - Z_2)$로 나타낼 수 있습니다. 이렇게 되면 모든 연산을 정수간의 연산과 비트 연산자로 표현할 수 있습니다.
4. ReLU and Maxpool computation
ReLU는 다양한 neural network에서 사용되는 activation function 중 하나로, $ReLU(x) = max(x, 0)$연산을 수행합니다. ZK-CNN에서는 ReLU과정을 증명하기 위해 아래와 같은 과정을 거치게 됩니다.
1. ReLU 연산이 이루어지는 수 ($x$)를 binary로 변환합니다. 또한 이 숫자가 binary 임을 증명합니다. ($b_i(b_i - 1) = 0$) 해당 수는 $Q-1$ bit으로 표현되고, $b_Q$는 음수인 경우 $0$, 양수인경우 $1$의 값을 갖습니다.
2. 해당 binary 가 실제로 $x$와 동일한 값을 가짐을 증명합니다.
3. 마지막으로, ReLU 연산의 특징에 따라, $ReLU(x) = b_Q \cdot \sum_{i=0}^{Q' - 1} b_{i+Q-Q'}2^i$ 연산을 증명합니다. 해당 식은 음수인경우 $0$, 양수인경우 $x$의 값으로 evaluate 됨을 확인할 수 있습니다.
또한 Max pooling 연산의 경우, 계산의 결과가 아래 두 조건을 만족함을 보임으로 증명하게 됩니다. (Max pool 연산에 대하여 본 글에서 자세히 다루지는 않겠습니다.)
1. max 값 $x_{max}$에 대하여, $x_{max} - x_j \geq 0 \text{ for all j } \in [k]$
2. 만약 $x_i$가 전부 음수가 아니라면, 어떠한 $j \in [k]$가 존재하여 $x_{max} - x_j = 0$. 전부 음수라면 $x_{max} = 0$.
두번째 연산의 경우 다음 식으로도 나타낼 수 있습니다. $x_{max} \cdot \prod^{k-1}_{j=0} (x_{max} - x_j) = 0$.
Conclusion
지금까지 다뤄본 2D convolution, ReLU, Max pooling, 그리고 general 한 addition & multiplication gate들을 전부 합치면, 기본적인 CNN에 대한 증명을 만들어낼 수 있게 됩니다. 또한 ZK-CNN protocol을 통한 증명생성은, 기존에 제안되었던 다른 방식들보다 훨씬 더 효율적이라고 합니다.
이번글을 통해 ZK-CNN에 대한 글을 마무리하려고 합니다. 기본적으로 깔고가는 내용이 많은 논문인 만큼 아주 쉽게 읽지는 못했던 것 같습니다. 혹시 질문 있으시면 글로 남겨주세요. 읽어주셔서 감사합니다.