[영지식증명] Sum-Check Protocol 응용: 행렬곱 증명

Introduction

안녕하세요, 지난 시간에는 영지식 증명 방법론 중 하나인 Sum-Check Protocol에 대하여 알아보았습니다. 

이번 시간에는 sum-check protocol의 강력함을 경험하기 위해, 아주 유용한 사용 예제를 하나 가져와 보았습니다. 

지난 시간과 마찬가지로 Justin Thaler 교수님의 렉쳐노트를 참조해 글을 작성했습니다. 

Main Protocol

행렬곱 증명의 목표는, prover가 verifier에게 어떠한 두 행렬 $A, B$의 곱은 $C$라는 claim을 증명하는 것입니다. 

두개의 인풋 행렬 $A, B \in \mathbf{R}^{n \times n}$이 있을 때, 각각의 행렬은 $\{0, 1\}^{logn} \times \{0, 1\}^{logn}$ 에서 finite field $\mathbf{F}$로 가는 mapping으로도 생각할 수 있습니다:

$A(i_1, \dots, i_{logn}, j_1, \dots, j_{logn}) = A_{ij}$

어렵게 들리지만, 풀어 설명하면 꽤 단숨합니다. 행렬 $A$의 $i, j$ 번째 entry의 원소를 생각해 보겠습니다. $i, j < n$이기 때문에, $logn$의 비트를 같은 binary 로 $i, j$를 표현할 수 있습니다. 그리고 앞서 정의된 mapping은 단순히 기존 index $i, j$를 해당 binary 로 변환해준 것입니다.

 

또한 $\tilde{A}, \tilde{B}, \tilde{C}$를 $A, B, C$ 행렬의 multilinear extension으로 표기하겠습니다. 본 글에서 multilinear extension에 대하여 자세히 다루지는 않습니다. 해당 내용은 이 자료를 통해 공부하는걸 추천드립니다. 정말 놀랍게도 이제 거의 다 마무리 되었습니다. 우리가 해야하는 건, $\tilde{C}(x, y) = \sum_{\mathbf{b}\in \{0, 1\}^{logn}}\tilde{A}(\mathbf{x}, \mathbf{b})\cdot\tilde{B}(\mathbf{b}, \mathbf{y})$ 임을 확인하는 것입니다. (행렬곱의 정의에 의해)

 

헌데 자세히 식의 형태를 살펴보면, 저희가 이전 포스트에서 다루었던 sum-check protocol이 적용 가능한 형태입니다. 고로 해당 식을 sum-check protocol을 통해 prover가 verifier에게 증명할 수 있습니다. 

 

Conclusion

오늘 알아본 행렬곱 protocol을 통해 배울 수 있는 점은, 주어진 행렬곱이라는 문제를 적절히 sum-check protocol이 적용가능한 형태로 변형시키는 작업인 것 같습니다. 행렬곱 증명은 sum-check protocol 뿐만 아니라 다른 protocol인 GKR을 통해서도 할 수 있다고 하는데요, 기회가 된다면 다음에 GKR, 그리고 GKR를 사용한 행렬곱에 대하여도 글을 작성해 보도록 하겠습니다.