[zk-SNARKs 기초] 4. How to make Blind Evaluation of Polynomials Verifiable
by Seongjin Kim, Core/Security Manager at ReturnValues (seongjin.kim@returnvalues.com)
[zk-SNARKs 기초] 시리즈
1. Homomorphic Hiding
2. Blind Evaluation of Polynomials
3. The Knowledge of Coefficient Test and Assumption
4. How to make Blind Evaluation of Polynomials Verifiable
이 글은 Zcash 블로그의 내용을 바탕으로 작성했으며, 번역 목적이 아닌 해설을 위해 작성되었기 때문에 내용의 추가와 요약이 있습니다. 원문은 아래 Zcash 블로그를 참고해주시기 바랍니다.
https://z.cash/blog/snark-explain4
미디엄의 수식 표현 한계로 인해 문장 속에 포함되는 수식을 아래와 같이 표현했습니다.
4. How to make Blind Evaluation of Polynomials Verifiable
이 포스팅에서는 이전 포스팅들에서 다루었던 내용을 바탕으로 검증 가능한 다항식의 blind evaluation 프로토콜을 살펴보겠습니다. 그리고 다음 포스팅에서는 이런 프로토콜이 SNARKs를 구성하는데 어떻게 사용되는지 본격적으로 살펴볼 것입니다.
“Blind Evaluation of Polynomials” 포스팅에서 살펴보았던 것처럼, Alice는 d차 다항식 P를 가지고있고, Bob은 F_p에서 임의로 선택한 원소 s를 가지고 있다고 생각해봅시다. 이 때, 우리는 Bob이 E(P(s))를 받을 수 있도록 프로토콜을 구성하면서 다음과 같은 두 가지 성질을 갖길 바랍니다.
1. Blindness : Alice는 Bob에게 받은 정보로부터 s에 대해 알아낼 수 없습니다. (또한 Bob은 Alice에게 받은 정보로부터 P에 대해 알아낼 수 없습니다.)
2. Verifiability : Alice가 올바른 E(P(s))를 전달하지 않았지만 Bob이 Alice의 증명을 받아들일 가능성은무시해도 될만큼 충분히 작습니다. 즉, 부정직한 증명자의 증명은 정직한 검증자가 받아들이지 않습니다.
이것을 우리는 검증 가능한 다항식의 blind evaluation이라고 합니다. 이 프로토콜의 첫 번째 성질(Blindness)은 “Blind Evaluation of Polynomials” 포스팅에서 살펴보았지만, 두 번째 성질(Verifiability)에 대해서는 살펴보지 않았습니다. Verifiability를 얻기 위해서 우리는 “The Knowledge of Coefficient Test and Assumption” 포스팅에서 살펴보았던 Knowledge of Coefficient Assumption(KCA)의 확장된 버전이 필요합니다.
Alice가 s를 알지 못하는 상태에서 다항식 P를 사용하도록 하는 점에서 위 두가지 성질은 유용하게 사용됩니다. 다시 말하면, Alice가 challenge point s에 대해 알지 못하는 상태에서 다항식의 답변을 하도록 약속합니다. 이 부분에 대해서 지금부터 구체적으로 살펴보겠습니다.
An Extended KCA
전 포스팅에서 KCA에 대해 다음과 같이 간단히 살펴보았습니다. Bob이 (a, b = α⋅a)인 α-pair를 Alice에게 전달하고, Alice는 그것을 사용해 α-pair (a’, b’)를 만듭니다. 이 때 Alice는 새로운 α-pair를 만들 때 새로운 계수 c를 선택했고, c를 사용해 a’를 계산했습니다(a’ = c⋅a). 따라서 c는 곧 a와 a’의 비율이라고 볼 수 있습니다.
이제, Bob이 Alice에게 하나의 α-pair가 아니라 여러 α-pair들(a_1, b_1), …, (a_d, b_d)을 같은 α를 사용해 만들어 전달한다고 가정해봅시다. 그리고 Alice는 이 α-pair들을 받으면, 이것들과 다른 α-pair인 (a’, b’)를 만들어야 합니다. 여기서 Alice가 α에 대해 알지 못한 상태에서 α-pair를 만들어야 한다는 점이 중요합니다.
전 포스팅에서 보았듯이, Alice가 α를 모르는 상태에서 α-pair를 만드는 방법은, F_p_*에서 선택한 임의의 c와 Bob이 전달해준 (a_i, b_i) 중 하나를 곱해 (c⋅a_i, c⋅b_i)인 α-pair를 만드는 것입니다. 그렇다면, Alice는 α-pair를 여러개 받았으니 이제 α-pair를 만들 때 더 많은 방법으로 만들 수 있을까요? 여러개의 α-pair들 중 몇 개를 동시에 사용해 새로운 α-pair를 만들 수 있지 않을까요?
그렇습니다. 예를 들면, Alice는 두 개의 c_1, c_2 값을 선택해 다음과 같이 α-pair 생성에 사용할 수 있습니다.
여기서 a’는 0이 아니며, 다음과 같이 (b’ = α⋅a’)라는 α-pair의 조건을 검증할 수 있습니다.
이것은 다음과 같이 더 일반화할 수 있습니다. Alice는 주어진 d개 쌍의 어떠한 선형 결합을 취할 수 있습니다. 즉, Alice는 F_p의 원소 c_1, …, c_d를 선택하고, (a’, b’)를 다음과 같이 생성할 수 있습니다.
이것은 곧, Alice가 위와 같은 방법으로 α-pair를 만들었을 때, Alice는 a’와 a_1, …, a_d 사이의 일차 관계식을 알게 된다는 것을 의미합니다. 즉, Alice는 아래 식을 만족하는 c_1, …, c_d를 알고 있습니다.
확장된 KCA는 이 방법이 Alice가 α-pair를 만들 수 있는 유일한 방법이라고 말합니다. 즉, Alice가 α-pair 생성에 성공한다면 a’와 a_1, …, a_d 사이의 일차 관계식을 알게 된다는 것입니다. 이것의 일반화를 위해 생성원 g를 갖고 크기가 p인 군 G가 있다고 생각해봅시다. 이러한 G에서 The d-power Knowledge of Coefficient Assumption(d-KCA)은 다음과 같습니다.
d-KCA : Bob이 F_p^*에서 임의로 α를 선택하고 F_p에서 임의로 s를 선택한 뒤, α-pair들인 (g, α⋅g), (s⋅g, αs⋅g), …, (s^d⋅g, αs^d⋅g) 들을 Alice에게 보냅니다. 그 후 Alice가 또다른 α-pair인 (a’, b’)를 만들 때, Alice는 아래 조건을 만족하는 c_0, …, c_d를 알게 됩니다.
d-KCA에서는 Bob이 α-pair들을 제멋대로 만드는 것이 아니라 위와 같은 다항식 구조를 사용해 만드는 특징이 있습니다. 이 점은 아래 프로토콜에서 유용하게 사용됩니다.
The Verifiable Blind Evaluation Protocol
E(x) = x⋅g 함수를 Homomorphic Hiding(HH)에 사용한다고 가정해봅시다. 이 때 g는 위에서 언급한 것과 같은 G의 생성원입니다. 간소화를 위해 이와 같은 E 함수를 사용한 프로토콜을 아래에서 설명합니다. 식이 점점 복잡해지기 때문에 아래 설명에서 필요한 부분들을 먼저 정리해보겠습니다.
E : 함수 E는 HH로써, 입력값 x를 은닉하기 위해 사용합니다. E(x) 값으로부터 x값을 알아낼 수 없습니다.
P : X에 대한 d차 다항식 P는 위와 같습니다. P는 크게 c와 X 두 가지 요소로 구성되는데, X는 Bob이 E(x)를 사용해 전달한 값이 될 것이고, c는 α-pair를 만들기 위해 Alice가 임의로 선택한 c_0, …, c_d가 될 것입니다. 우리는 이와 같은 방식을 “Blind Evaluation of Polynomials” 포스팅에서 살펴보았습니다. P 다항식의 구성에 필요한 c_0, …, c_d에 대해서 Bob은 알 수 없습니다.
α-pair : (a, b) 쌍에서 b가 b = α⋅a를 만족할 때 우리는 이 쌍을 α-pair라고 부릅니다. α는 Bob이 임의로 선택한 값이고, 이 값은 은닉을 통해 Alice에게 전달되기 때문에 Alice는 α값을 알지 못합니다.
아래는 프로토콜을 단계별로 그림을 첨부해 나타낸 것입니다. 좌측이 Alice이고 우측이 Bob이며, 서로 전달하는 값들은 중앙에 표시하였습니다.
1. Alice는 임의의 c_0, …, c_d를 선택합니다. 이 값들은 다항식 P(X)를 구성하는데 사용하며, Bob이 알 수 없습니다. Bob은 임의의 α와 s를 선택합니다. 이 값들은 Alice가 알 수 없습니다. g는 서로 공유하는 값입니다.
2. Bob이 Alice에게 g, s⋅g, …, s^d⋅g를 전달합니다. 이것은 곧 (1, s, …, s^d)를 은닉한 것입니다. 동시에 Bob은 α⋅g, αs⋅g, …, αs^d⋅g 또한 Alice에게 전달합니다. 이것은 곧 (α, αs, …, αs^d)를 은닉한 것입니다.
3. Alice는 a = E(P(s))와 b = αE(P(s))를 계산합니다. 이것은 전 과정에서 Bob이 전달해준 정보를 사용해 아래와 같이 할 수 있습니다. 아래와 같이 계산한 a, b를 Bob에게 전달합니다.
4. Bob은 b = α⋅a를 계산해 올바른 α-pair인지 확인합니다.
위와 같은 프로토콜을 정리하면, E(P(s))는 g, s⋅g, …, s^d⋅g의 선형 결합이며, αE(P(S))는 αg, αs⋅g, …, αs^d⋅g의 선형 결합이라고 할 수 있습니다. 두 번째 글에서 보았던 것처럼 Alice는 다항식 P를 사용해 Bob의 메세지를 위와 같이 계산할 수 있습니다.
또한, d-KCA에 의해, Alice가 b = α⋅a인 (a, b)를 보낸다면, Alice가 아래 조건을 만족하는 c_0, …, c_d를 알고 있다고 거의 확신할 수 있습니다.
즉, Alice가 P를 모르는 경우에는 위 프로토콜의 4단계에 의해 Bob이 Alice의 증명을 받아들이지 않습니다.
지금까지의 포스팅에서 살펴본 것들은, ZCash 블로그에서 아래와 같이 나타낸 단계에서 Computation에 해당합니다.
다음 포스팅부터는 지금까지 학습했던 계산 방법이 zk-SNARKs를 구성하기 위해 어떻게 사용되는지 살펴볼 것입니다.
