[영지식증명] Sum-Check Protocol

Introduction

안녕하세요, 오늘은 영지식증명의 다양한 분야에서 사용되고 있는 Sum-Check Protocol에 대하여 알아보는 시간을 가지려고 합니다. 

이번 블로그 포스트는 Justin Thaler 교수님의 Sum-check Protocol 강의 자료를 참조하여 만들었습니다. 

 

Sum-Check Protocol

Sum-Check Protocol 에서 증명하고자 하는 바는 다음과 같습니다:

우리가 어떤 finite field $\mathbf{F}$에서 $v$개의 변수를 같는 다항식 $g$를 가지고 있다고 가정하겠습니다. sum-check protocol의 prover는 아래 값을 verifier에게 증명하는 것이 목표입니다. 

$H := \sum_{b_1 \in \{0, 1\}} \sum_{b_2 \in \{0, 1\}} \dots \sum_{b_v \in \{0, 1\}} g(b_1, \dots, b_v)$

 

Prover가 해당 값을 제시했을 때, Verifier가 이를 검증할 수 있는 가장 간단한 방법은 직접 해당 계산을 다시 수행하는 것입니다. 하지만 이 과정은 Verifier에게 굉장히 많은 계산을 요구하게 됩니다. sum-check protocol은 이 검증을 더 간편하게 만들어주는 역할을 합니다. 단순히 위의 식만을 보면 어디에 사용할 수 있을지 잘 감이 오지 않지만, 해당 protocol은 행렬 곱셈을 증명하는 등 다양한 부분에서 유용하게 사용될 수 있습니다. 

 

우선 우리는 verifier 가 임의의 점 $(r_1, \dots, r_v) \in \mathbf{F}^v$ 에서의 $g(r_1, \dots, r_v)$ 값을 계산할 수 있다고 가정하겠습니다. 만약 실제 상황에서 함수 $g$가 private이어야 한다면, 이 과정은 verifier가 $g(r_1, \dots, r_v)$값을 요청하고, prover가 이를 증명하는 과정으로 대체되게 됩니다.

 

sum-check protocol은 총 $v$ round에 걸쳐 진행되게 됩니다. 

First Round

첫번째 round에서, prover는 verifier에게 다항식 $g_1(X_1)$을 전송하고, $g_1(X_1) = \sum_{(x_2, \dots, x_v) \in \{0, 1\}^{v-1}}g(X_1, x_2, \dots, x_v)$ 임을 claim 합니다. 또한 만약 해당 claim 이 맞다면, $H = g_1(0) + g_1(1)$ 을 통해 계산될 수 있습니다.

여기서 $g_1$에 대하여 조금 더 살펴보도록 하겠습니다. 우리는 $deg_i(p)$를 다항식 $p$에서 변수 $i$의 degree 라고 정의하겠습니다. 그렇다면, 다항식 $g$는 다항식의 성질에 의해 $deg_1(g) + 1$개의 field element를 통해 특정될 수 있고, 예를 들어 집합 $\{0, 1, \dots, deg_1(g) \}$ 에서의 evaluation을 통해 $g_1$를 특정화할 수 있습니다.

 

Consecutive Rounds

$j > 1$ 번째 round에서, verifier는 랜덤한 값 $r_{j-1}$을 선택하여 prover에게 전달하게 됩니다. 그 후 prover는 verifier 에게 $g_j(X_j)$를 전달하고, $g_j(X_j) = \sum_{(x_{j+1}, \dots, x_v) \in \{0, 1\}^{v-j}} g(r_1, \dots, r_{j-1}, X_j, x_{j+1}, \dots, x_v)$임을 claim하게 됩니다. 

 

Verifier는 두 가지를 확인하게 되는데요, 우선 첫번째로는 $g_j$의 정의에 의하여, $g_{j-1}(r_{j-1}) = g_j(0) + g_j(1)$의 조건을 만족하는지 확인합니다. 또한 두번째로는 앞서 $g_j$의 차수에 대한 논의를 한것처럼, $g_j$의 차수가 적합한 range에 있는지 (너무 높지 않은지) 확인하게 됩니다. 

 

Final Round

마지막 round에서 prover는 verifier에게 $g_v(X_v)$를 보내고, 이것을 $g(r_1, \dots, r_{v-1}, X_v)$라고 claim 하게 됩니다. 앞선 가정에 의해 verifier는 $g(r_1, \dots, r_v)$값을 계산할 수 있기 때문에, verifier는 $g_v(r_v) = g(r_1, \dots, r_v)$를 만족하는지 확인하게 됩니다. 만약 이전 round들에서 prover가 verifier를 속이기 위해 의도적으로 조작된 $g_i$ 들을 전송해 왔다면, 마지막 round에서 조건을 만족시킬 확률은 매우 미비합니다. 

 

Completeness and Soundness

여기서 증명하지는 않겠지만, sum-check protocol의 completeness 와 soundness는 아래 proposition에 나타나 있습니다. 

Completeness의 경우, prover가 올바른 계산을 진행했다면, verifier는 무조건 해당 증명을 받아들이게 됩니다. 따라서 completeness error는 0이 되며, soundness의 경우 proof by induction을 통해 해당 proposition과 같음을 증명할 수 있습니다. 

 

Conclusion

오늘은 Sum-Check Protocol에 대하여 알아보았습니다. 다음시간에는 해당 protocol의 응용으로, 행렬곱을 sum-check protocol을 통해 증명할 수 있는 방법에 대하여 알아보도록 하겠습니다.