[zk-SNARKs 기초] 3. The Knowledge of Coefficient Test and Assumption

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-explain3

미디엄의 수식 표현 한계로 인해 문장 속에 포함되는 수식을 아래와 같이 표현했습니다.

3. The Knowledge of Coefficient Test and Assumption

전 포스팅에서 Bob이 임의로 선택한 s에 대해 Alice가 d차 다항식 P의 정보를 숨기고 E(P(s))를 계산하는 것을 살펴보았습니다. 이 때 Alice는 s값이 무엇인지 알 수 없기 때문에 이런 일련의 과정을 “blind” 계산이라고 합니다.

그런데 이 과정에 대해 언급되지 않은 부분이 있습니다. Alice가 E(P(s))를 계산할 수 있다는 점과 무관하게, Alice가 Bob에게 올바른 E(P(s))를 전달하리라는 보장이 되지 않습니다.

그러므로 Alice가 프로토콜을 정직하게 수행하도록 강제할 수 있는 방법이 필요합니다. 이 방법에 대해서는 다음 포스팅에서 자세히 살펴보고, 이번 포스팅에서는 그러한 방법에 필요한 Knowledge of Coefficient (KC) Test라고 하는 기본적인 것을 설명하는데 집중할 것입니다.

지금까지와 같이 우리는 g를 이산 대수 문제의 해결이 어려운 크기가 p인 군 G의 생성원(generator)으로 쓸 것입니다. 이 포스팅에서는 앞으로 편의를 위해 군의 연산을 곱셈 대신 덧셈을 사용할 것입니다. 즉, F_p의 원소 α에 대해서, α⋅g는 α를 g번 더한 것을 의미합니다.

The KC Test

앞으로 사용할 군 F_p^*는 F_p에서 0을 제외한 것과 같고, 첫 포스팅의 Z_p^*와 같습니다. 또한 F_p^*의 원소 α는 G의 원소 두 개를 (a, b) 쌍으로 하는 α-pair로써 만들어진다고 하겠습니다. 이 때, a, b ≠ 0이며 b = α ⋅a 입니다.

KC Test는 아래와 같이 진행됩니다.

1. Bob이 F_p^*에서 임의로 α를 선택하고, G에서 임의로 a를 선택합니다. 그 후 b = α ⋅a를 통해 b를 계산합니다.
2. Bob은 Alice에게 (a, b) 쌍을 보냅니다. 여기서 (a, b)는 전 과정에서 보았듯이 α-pair입니다.
3. Alice는 Bob이 전달한 것과 다른 α-pair를 만들어 응답해야 합니다. Alice가 생성할 α-pair를 (a’, b’)라고 하겠습니다. 이 때, Alice는 α를 모르는 상태에서 α-pair를 만듭니다. 이 과정은 뒤에서 자세히 살펴보겠습니다.
4. Bob은 Alice가 전달한 (a’, b’)가 α-pair 기준을 만족할 때만 Alice의 응답을 받아들입니다. 이것은 b’ = α ⋅a’를 계산하여 확인할 수 있습니다. Bob은 α를 알고 있기 때문에 확인이 가능합니다.

여기서 Alice가 어떻게 성공적으로 Bob의 challenge를 응답할 방법이 있을지 생각해봅시다. Alice가 Bob이 임의로 선택한 α를 안다고 가정해봅시다. 이 경우에 Alice는 G 안에서 아무 값을 골라 a’로 선택하고 b’ = α ⋅a’를 계산하여 간단하게 α-pair를 만들 수 있습니다. 그리고 Alice는 자신이 만든 새로운 α-pair를 응답하면 됩니다.

그러나, Alice가 가진 α에 대한 유일한 정보는 Bob에게 받은 α ⋅a(= b)인데, G에서는 이산 대수 문제의 해결이 어렵기 때문에 Alice가 α를 알아낼 수 없습니다.

그러면 Alice는 어떻게 α를 알지 못한 상태에서 α-pair를 만들어 challenge에 대해 응답할 수 있을까요? 그 방법은 다음과 같습니다. Alice는 F_p^*의 원소 γ를 임의로 선택하고 γ ⋅a를 계산한 결과를 a’로 사용합니다. 이제 b’를 계산해야 하는데, α-pair 조건을 만족하려면 b’는 α ⋅a’와 같아야 합니다. 이 때, α를 모르는 상황에서 b’를 구하는 방법은 다음과 같습니다. 이 과정에서 Bob이 전달해준 b가 α ⋅a와 같다는 점을 이용합니다.

위와 같이 b’를 계산하면 Alice가 만든 (a’, b’) 쌍은 α-pair 기준을 만족하게 됩니다.

여기서 기억해야 할 특징은, Alice가 이런 방법으로 응답한다면, Alice는 a’ = γ ⋅a를 통해 a’를 만들었기 때문에, a와 a’의 비율을 알고 있고, 이는 곧 a’ = γ ⋅a에서 계수 γ를 알고 있다는 점입니다. 이 계수는 전 포스팅에서 Alice가 다항식 P의 일부인 a_0, …, a_d를 Bob에게 알리지 않고 사용했던 것처럼 다음 포스팅에서 활용될 것입니다.

Knowledge of Coefficient Assumption(KCA)은 다음과 같이 기술하고 있습니다. KCA는 일반적으로 Knowledge of Exponent Assumption(KEA)라고도 불립니다.

KCA : Bob의 (a, b) challenge에 대해 Alice가 올바른 (a’, b’)를 만든다면, Alice는 a’ = γ ⋅a를 통해 γ를 알게 됩니다.

이러한 KC Test와 가정은 다음 포스팅에서 중요한 도구로 쓰일 것입니다.