[영지식 증명] Lookup Argument 파헤치기

Introduction

안녕하세요, 오늘은 영지식증명 과정에서 유용하게 사용되는 lookup argument에 대하여 알아보려고 합니다. Lookup argument는 영지식증명을 통해 증명하기 까다로운 연산들을, 이름에서처럼 미리 table 형식으로 지정해두고 (public table), 까다로운 연산들을 증명하는 대신, 해당 연산 결과값을 테이블에서 참조했음을 증명함으로써 까다로운 연산에 시간이 많이 소요되는 것을 방지할 수 있습니다. 

 

예를 들어 영지식증명을 통해 non-linear 함수를 증명하는 것은 까다로운데요, lookup argument를 사용하면 미리 nonlinear한 연산의 증명은 테이블 참조 증명으로 대체함으로 영지식증명의 영역을 넓혀주는 역할을 하는데 굉장히 중요합니다. Lookup argument 의 방법에도 여러가지가 있지만, 오늘은 상대적으로 간단하다고 여겨지는 Halo 2에서 사용되는 lookup argument에 대하여 살펴보도록 하겠습니다. 오늘 글은 halo2 document에 기술된 lookup argument 파트를 참조했습니다. 

Lookup Argument without Zero-Knowledge

우선적으로 영지식 개념을 포함하지 않는 lookup argument에 대하여 살펴보도록 하겠습니다. 우리가 원하는 연산에 대하여, 연산 operand와 연산 결과값을 가지고 $2^k$개의 row를 가지는 table을 가지고 있다고 가정하겠습니다. 

우리에게는 column $\mathbf{A}, \mathbf{S}$ 가 주어집니다. Lookup  연산의 목표는 $\mathbf{A}$의 모든 cell이 $\mathbf{S}$에 있는 어떤 cell에 대응됨 (존재함)을 증명하는 것입니다. 대략적으로 감이 오시겠지만, 우리는 어떤 연산에 대하여 public 한 테이블 $\mathbf{S}$를 만들어두고, 증명과정 중 필요한 $\mathbf{A}$ 연산들에 대하여 미리 지정해둔 테이블에서 가져왔음을 증명하게 되는 것입니다. 또한 한 가지 짚고 넘어갈 부분은, $\mathbf{A}, \mathbf{S}$의 각 entry들이 distinct 할 필요는 없다는 것입니다. 이들은 중복적인 cell들을 가지고 있을 수 있습니다. 

우선 $i$ 에서 $1$의 값을 가지고, 나머지에서 $0$으로 evaluate 되는 lagran basis polynomial $l$ 이 있다고 가정하겠습니다. 또한 $\mathbf{A}, \mathbf{S}$ 에 permutation을 적용한 $\mathbf{A'}, \mathbf{S'}$을 만들었다고 가정하겠습니다. 우선 첫번째로 보여야 하는 것은, 실제로 $\mathbf{A'}, \mathbf{S'}$ 이 $\mathbf{A}, \mathbf{S}$를 permute 하여 만든 행렬임을 증명하는 것입니다. 이 증명은 permutation argument 라는 방법을 통해 증명할 수 있습니다. 해당 방법은 아래 기술된 것과 같습니다:

우선 우리는 아래 특징을 만족하는 $Z$를 만들게 됩니다.

$Z(\omega X) \cdot (\mathbf{A}'(X) + \beta) \cdot (\mathbf{S'}(X) + \gamma) - Z(X) \cdot (A(X) + \beta) \cdot (S(X) + \gamma) = 0$

 

$l_0(X) \cdot (1 - Z(X)) = 0$.

 

해당 식을 가지고 division by zero가 일어나지 않는다는 가정을 가지고 $Z$에 대하여 조금 더 간단하게 기술하면 다음과 같이 적을 수 있습니다:

$Z_{i+1} = Z_i \cdot \frac{(A_i + \beta) \cdot (S_i + \gamma)}{(A_i' + \beta)\cdot(S_i' + \gamma)}$

 

$Z_{2^k} = Z_0 = 1$.

 

여기서 $\beta, \gamma$ 는 랜덤한 값을 가집니다. 해당 식을 의미적으로 접근해보자면, $A$와 $S$의 각 element에 랜덤한 값을 더하고 곱해주고 있기 때문에, 만약 $A', S'$이 $A, S$의 permutation이 아니라면, Z_{2^k} 값은 $1$이 될 확률이 매우 작아지게 됩니다. 반대로 $A', S'$이 실제로 $A, S$의 permutation이라면, 모든 항들이 약분이 되며 Z_{2^k} 값은 $1$이 됩니다. 이렇게 $A', S'$이 실제로 $A, S$의 permutation임을 증명하는 과정은, lookup argument의 과정에 $A, S$를 특정한 순서로 배치하는 과정이 필요하기 때문입니다.

구체적으로 우리는 $A'_i = S'_i$ 이거나, $A'_i = A'_{i-1}$ 이 되도록 $A, S$를 permute 해주게 됩니다. 해당 관계는 다음과 같이 나타낼 수 있습니다. 

$(A'(X) - S'(X)) \cdot (A'(X) - A'(\omega^{-1}X)) = 0$

또한 $A'_0 = S'_0$ 를 만족하도록 순서를 배치하게 되고 이는 또한 다음과 같이 나타낼 수 있습니다.

$l_0(X) \cdot (A'(X) - S'(X)) = 0$.

 

지금 살펴본 것처럼 만약 우리가 영지식증명을 통해 증명하기 까다로운 연산을 다루어야 한다면, 해당 연산들을 table 형식으로 미리 만들어둔 후, 증명 과정에서 해당 연산을 사용하는 부분이 등장하면, 해당 연산 결과 값을 공개하지 않고도 까다로운 연산의 결과값이 미리 지정해둔 table을 통해 올바르게 계산되었음을 증명할 수 있습니다. 

 

Lookup Argument with Zero-Knowledge

미리 공개된 table의 size를 $2^k$ 라고 하겠습니다. 해당 lookup argument 가 '영지식증명' 이기 위해서는, 증명과정에서 증명을 진행하는 연산 중간값들이 드러나서는 안됩니다. 하지만 만약에 $A, S$의 사이즈가 $2^k$ 보다 작다면, $Z$ polynomial의 차수가 $2^k$ 보다 작게 되고, verifier는 많은 query 를 날린 후 의도적으로 $Z$에 대한 정보를 얻을 수 있습니다. ($n$개의 point를 알고 있다면, $n-1$ 보다 작은 차원을 갖는 polynomial을 전부 특정할 수 있습니다.) 따라서 lookup argument가 '영지식증명'이기 위해서, $A, S$의 마지막 t row 들은 랜덤한 값을 갖도록 변화시켜주게 됩니다. 이러한 변환을 통해 우리는 $Z$ polynomial 의 차수를 의도적으로 높일 수 있습니다. 하지만 이러한 랜덤한 값들이 들어가면서 protocol 에 변화를 주어야 합니다. 

 

이제 우리는 $A, S$에서 사용가능한 row의 갯수를 $u = 2^k - t - 1$ 로 정의하겠습니다. 또한 두개의 selector $q_{blind}, q_{last}$를 두게 됩니다. Selector는 일종의 스위치, 혹은 마커 정도로 이해할 수 있습니다. $q_{blind}$는 랜덤한 값들이 들어간 마지막 $t$개의 row 에 $1$이, 나머지 row에는 $0$이 들어가게 됩니다.$q_{last}$의 경우 랜덤한 값이 아닌 실제로 사용하는 row들 중 마지막 entry 에 $1$의 값을, 나머지에 $0$의 값을 갖게 됩니다.

 

또한 $A, S$에 사용하지 않는 값들을 포함한 만큼 polynomial $Z$를 실제 사용하는 row들만 가지고 조건을 표현하게 되면 다음과 같이 나타낼 수 있습니다.

$(1-(q_{last}(X) + q_{blind}(X))) \cdot (Z(\omega X) \cdot (A'(X) + \beta) \cdot (S'(X) + \gamma) - Z(X) \cdot (A(X) + \beta) \cdot (S(X) - (1 - (q_{last}(X) + q_{blind}(X))) \cdot (A'(X) - S'(X)) \cdot (A'(X) - A'(\omega^{-1}X)) = 0$

 

또한 첫번째 row에 대한 조건은 동일합니다.

$l_o(X) \cdot (A'(X) - S'(X)) = 0$

$l_o(X) \cdot (1 - Z(X)) = 0$

마지막 row 에 대한 조건은 이제 조금 달라지는데요, $Z$는 이제 $\omega^{2^k}$ 에 대한 값이 1의 값을 갖는 것에서 이제 $\omega^u$의 값에서 1의 값을 갖게 됩니다. 또한 매우 무시 가능한 확률이지만, $i \in [0, u)$의 범위에서 $A_i + \beta$ 혹은 $S_i + \gamma$가 $0$의 값을 갖는 것을 대비하여 $Z(\omega^u)$ 를 0 혹은 1의 값을 갖도록 수정해줍니다. 해당 조건은 다음과 같이 표현할 수 있습니다. 

$q_{last}(X) \cdot (Z(X)^2 - Z(X)) = 0$.

 

Conclusion

즉, prover의 경우 원하는 연산이 기술된 테이블 ($A$를 바탕으로 public table에서 참조) $S$, 해당 연산중 증명 과정에서 필요한 연산을 모아둔 $A$, 해당 두 column들을 permute 해 만든 $A', S'$, 그리고 permutation argument를 위한 올바른 polynomial Z를 제공함으로, 영지식증명을 통해 필요한 연산이 실제로 public 하게 기술해두었던 table 에서 왔음을 알 수 있습니다. 

 

다음 시간에는 plonk 와 함께 사용되는 plookup 에 대하여 알아보거나, sumcheck 혹은 gkr 프로토콜의 응용에 대하여 살펴보는 시간을 갖도록 하겠습니다. 긴 글 읽어주셔서 감사합니다. 혹시 질문 있다면 남겨주세요 :)