[영지식 증명] PLONK 파헤치기 2 - Permutation Check

Introduction

안녕하세요, 오늘은 지난 시간에 이어 PLONK에서의 Copy Constraint를 검증하는 방법에 대하여 알아보도록 하겠습니다. 

이번 글은 How PLONK Works - 2 를 참조하여 작성되었습니다. 

 

이전 시간에 저희는 arithmetic circuit에 존재하는 두 가지 종류의 constraint 중 한 가지인 gate constraint를 영지식 증명을 활용해 검증하는 방법을 알아보았습니다. KZG-PCS를 사용해 prover는 verifier에게 자신이 gate constraint를 만족하는 circuit 내부값들을 가지고 있음을 증명할 수 있었습니다. 이번 시간에는 남은 한 가지 constraint인 copy constraint를 검증하는 방법에 대하여 알아보도록 하겠습니다. 

첫 포스트에서 다루었던 arithmetic circuit의 모습입니다. 여기서 copy constraint들의 예시를 들어보자면, 

• $a_0 = a_2$
• $c_1 = b_2$
• $c_2 = a_3$

등이 있겠습니다. 

Copy Constraint within a single variable

이전의 포스팅에서 우리는 아래와 같이 변수 $a$ 에 대한 값들을 하나의 벡터로 만들어 사용했습니다. 

$\textbf{a} = (a_0, a_1, a_2, a_3)$

처음으로 $a_0 = a_2$ 처럼 같은 변수 내에서의 copy constraint를 검증하는 방법에 대하여 알아보겠습니다.

우선 $\sigma$ 함수를 정의하겠습니다. $\sigma$ 함수의 목적은 하나의 벡터/변수 내에서의 원소의 위치를 변환하는 것입니다. 

예를 들어, $\sigma (0) = 2, \sigma (2) = 0$ 이라면, 이것은 $\textbf{a}$ 벡터의 처음과 두번째 원소의 순서를 바꾸는 것을 의미합니다. 다음으로는 두 가지 함수를 정의하겠습니다. 

 

$f(i) = a_i + i \beta + \gamma$

$g(i) = a_i + \sigma (i) \beta + \gamma$

$\beta$ 와 $\gamma$ 값은 랜덤한 값입니다. 이제, 해당 함수들을 사용해 아래와 같은 계산을 수행하게 됩니다.

$\prod^3_{i=0} \frac{f(i)}{g(i)}$ 이것을 permutation check, 혹은 grand sum 이라고 부르도록 하겠습니다. 

 

Permutation check 식에 대하여 조금 더 살펴보도록 하겠습니다. 우리가 검증해야 하는 copy constraint가 $a_0 = a_2$ 라고 하겠습니다. 각 분자와 분모의 형태는, $a_i$에 대하여 $i$에 조건부로 랜덤한 값을 곱해주게 됩니다. 즉, 만약 $a_0 \neq a_2$ 라면, $f(0)$ 값은 $g(0)$ 값과 달라지게 됩니다. 또한 $f(2) \neq g(2)$가 됩니다. 결론적으로 permutation check의 분자 곱이 분모 곱과 같아질 확률은 매우 낮습니다. 결론적으로 확인하고 싶은 copy constraint에 올바른 permutation을 적용한 후, permutation check 을 계산했을 때, 해당 값이 $1$이어야만 해당 copy constraint를 만족한다고 할 수 있습니다. 

 

Permutation Check with Polynomials

이번 섹션에서는 다항식을 활용해 permutation check 을 하는 방법에 대하여 알아보겠습니다. 이전에 interpolation을 통해 다항식을 생성해낼 때 domain을 양의 정수를 사용했습니다. 하지만 이번에는 계산의 편의성을 위해 root of unity를 사용하게 됩니다. root of unity $\omega$ 는 $\omega ^n = 1$인 성질을 가지고 있으며, $\{ \omega ^0, \omega ^1, \omega ^2, \omega ^3\, \dots, \omega ^n\}$ 값들을 사용해 interpolation을 수행하게 됩니다. 

 

이제 interpolation 값으로 사용할 새로운 벡터 $P$를 정의하도록 하겠습니다. 

$P(\omega ^0) = 0$

$P(\omega ^i) = \prod_{j<i}\frac{f(j)}{g(j)}, i \in \{1 \dots n\}$

정의처럼 벡터 $P$는 아까의 permutation check 식을 쌓아나가는 방식으로 정의됩니다.

또한 이렇게 정의된 $P$는 아래와 같이 재귀적인 방법으로도 나타낼 수 있습니다. 

$P(\omega ^ {i+1}) = P(\omega ^i)\frac{f(i)}{g(i)}$

만약 해당 조건을 만족하는 $P(x)$가 실제로 존재한다면, 우리는 grand sum 의 값이 $1$이라는 것을 알 수 있습니다. 

 

증명)

$P(\omega ^n) = \prod_{i=0}^{n-1}\frac{f(i)}{g(i)} = P(1) = P(\omega ^ 0) = 1$

Q.E.D.

 

위의 식을 다시 정리하면 아래식은 $\{ \omega ^0, \omega ^1, \omega ^2, \omega ^3\, \dots, \omega ^n\}$ 의 정의역에서 성립합니다.

$P(\omega ^ {i+1})g(i) = P(\omega ^i)f(i)$

또한 정의역을 $\{ \omega ^0, \omega ^1, \omega ^2, \omega ^3\, \dots, \omega ^n\}$으로 정한다면, 아래와 같이 간단히 표기할 수 있습니다.

$P(x\omega)g(x) = P(x)f(x)$

이 식은 이전의 PCS 에서처럼 식을 아래와 같이 정리할 수 있습니다. 

$P(x\omega)g(x) - P(x)f(x) = Z(x)Q(x)$

where $Z(x) = (x-\omega ^0)(x - \omega ^1) \dots (x - \omega ^n)$

마지막으로, 이전의 KZG-PCS를 사용해 임의의 랜덤한 값 $r$에서 위의 식이 성립됨을 prover가 증명하는 것은, 위의 증명에서처럼 grand sum 이 $1$인것을 증명하는 것이 되어, 해당 permutation 에 대응되는 copy constraint를 증명하는 것이 됩니다. 

 

Copy Constraint across multiple variables

하지만 실제로 copy constraint는 $c_1 = b_2$처럼 다양한 변수에 걸쳐 존재하는 경우들이 있습니다. 이런 경우 단일 변수에서의 copy constraint와 매우 비슷한 방법으로 검증을 진행하게 됩니다. 이 경우 우리는 $\textbf{a}, \textbf{b}, \textbf{c}$ 세가지 벡터를 하나의 큰 벡터로 붙여주게 됩니다. 

 

$V = (a_0, a_1, a_2, a_3, b_0, b_1, b_2, b_3, c_0, c_1, c_2, c_3)$

 

또한 이와 비슷하게 permutation 함수 $\sigma$를 정의해줄 수 있는데요, 위의 arithmetic circuit에 대한 $\sigma$는 다음과같이 정의되게 됩니다. 

 

$i = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11)$

$\sigma(i) = (2, 8, 4, 10, 5, 0, 9, 7, 1, 6, 3, 11)$

 

모든 copy constraint들을 검증하진 않겠지만 실제로 하나씩 대응시키며 수식을 확인하면, 올바른 copy constraint들이 전부 들어간 것을 확인할 수 있습니다. 또한 이 경우 세 가지 변수를 가지고 한번에 grandsum 을 계산하기 위한 수식은 다음과 같습니다.

$f(i) = (a_i + idx(a_i)\beta + \gamma)(b_i + idx(b_i)\beta + \gamma)(c_i + idx(c_i)\beta + \gamma)$

$f(i) = (a_i + \sigma(idx(a_i))\beta + \gamma)(b_i + \sigma(idx(b_i))\beta + \gamma)(c_i + \sigma(idx(c_i))\beta + \gamma)$

 

여기서 $idx$ 함수는 input element 가 $V$벡터내에서 위치하는 index 를 변환해주는 함수입니다.

이 경우도 단일변수 내에서의 copy constraint검증과 동일하게, 실제로 copy constraint들이 만족해야만 항들이 상쇄됨을 확인할 수 있습니다. (조금 와닿지 않는 경우 주어진 예시에 대하여 식을 한번 전개해보는 것을 추천드립니다.)

이제 아까와 동일한 방식으로 다항식 $P$를 정의한 뒤, 동일한 과정을 거쳐 KZG-PCS를 통해 변수 내부 간, 심지어 변수 사이의 copy constraint도 확인할 수 있습니다. 

 

Conclusion

지금까지 세 편의 포스트를 통해 PLONK의 기본적인 작동원리에 대하여 훑어보았습니다.

• 첫 시간에는 검증하고자 하는 문제를 arithmetic circuit으로 변환하고 gate constraint를 다항식으로 변화시키는 방법에 대하여 알아보았습니다.
• 두번째 시간에는 다항식으로 변화된 gate constraint를 prover가 다항식에 대한 아무런 정보를 유출하지 않으며 검증하는 방법에 대하여 알아보았습니다. (KZG-PCS)
• 마지막으로 오늘은 prover 가 copy constraint를 역시 다항식으로 변환하여 PCS를 사용해 아무런 정보를 유출하지 않고 검증하는 방법에 대하여 알아보았습니다. 

여기까지가 PLONK의 기본적인 작동원리입니다.

질문 있으시다면 편하게 댓글로 남겨주세요. 

 

읽어주셔서 감사합니다.