[zk-SNARKs 기초] 2. Blind Evaluation of Polynomials

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

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

2. Blind Evaluation of Polynomials

이번 글에서는 다항식에 대해 살펴보면서 다항식의 blind evaluation에 대해 설명하고, 이것이 어떻게 Homomorphic Hiding(이하 HH)을 사용하면서 구현되는지 설명하겠습니다. 앞으로의 포스팅에서 blind evaluation이 SNARK의 가장 중요한 도구라는 것을 볼 것입니다.

우리는 p 크기만한 체(field)를 𝔽_p라고 정의합니다. 즉, 𝔽_p의 원소들은 {0,…,p - 1}이고, 이전 포스팅에서 보았던 것처럼 mod p를 사용한 덧셈과 곱셈 연산을 지원합니다.

체
사칙연산이 자유롭고, 일반적인 산술 연산의 규칙들을 만족하는 집합입니다.

다항식과 선형 결합

𝔽_p를 떠나서, d차 다항식 P가 다음과 같이 표현될 수 있다는 점을 떠올려봅시다. 이 때, a_0, …, a_d는 𝔽_p의 원소입니다.

이와 같은 다항식에서 X 대신 𝔽_p의 원소 s를 사용하면, 다항식 P는 다음과 같이 계산될 수 있습니다.

P(s) 값은 a_0, …, a_d를 가중치로 둔 1, s, …, s^d의 선형 결합임을 볼 수 있습니다.

이전 포스팅에서 우리는 생성원 g를 사용한 HH 함수 E를 E(x) = g^x라고 정의하고, 이산 대수 문제가 어렵다는 점을 사용한 것을 보았습니다. 또한, HH는 덧셈을 지원하기 때문에 E(x), E(y) 값이 주어졌을 때 E(x + y)를 계산할 수 있다는 점을 보았습니다. 이제 이런 특징들을 사용해서 선형 결합 또한 지원한다는 점을 살펴보겠습니다. 즉, a, b, E(x), E(y)가 주어졌을 때 우리는 E(ax + by)를 계산할 수 있습니다. 이것을 수식으로 풀어보자면 다음과 같습니다.

g^ax가 (g^x)^a로 되는 것 역시 지수 법칙에 의한 것인데, 아래와 같이 유도할 수 있습니다.

다항식의 Blind evaluation

Alice에게 d차 다항식 P가 있고, Bob은 F_p의 원소 s를 임의로 선택해 갖고 있을 때, Bob이 E(P(s))를 알고싶어하는 상황을 가정하겠습니다. E(P(s))는 곧 s를 다항식에 대입한 것의 HH입니다. Alice와 Bob이 서로 모든 정보를 공개한다면, 다음과 같은 두 가지 방법으로 간단히 할 수 있습니다.

* Alice가 Bob에게 다항식 P를 전달하고, Bob은 E(P(s))를 계산합니다.
* Bob이 s를 Alice에게 전달해서, Alice가 E(P(s))를 계산해서 알려주기를 기대합니다.

그러나 우리는 Bob이 다항식 P를 모르게 하는 동시에, Alice 또한 s를 모르게 하는 Blind evaluation 문제를 살펴보겠습니다.

1. Bob이 E(1), E(s),…, E(s^d)를 계산해 Alice에게 전달합니다.
2. Alice는 Bob이 전달해준 정보로부터 E(P(s))를 계산해 Bob에게 전달합니다.

위와 같은 방법으로 Alice와 Bob이 각자 가지고 있는 정보를 알리지 않고 원하는 결과를 얻을 수 있습니다. Alice가 계산해야하는 E(P(s))를 풀어서 써보면 다음과 같습니다.

여기서 Alice는 다항식 P를 알고 있기 때문에 이미 a_0, …, a_d 값을 알고 있습니다. 따라서, Alice가 E(P(s))를 계산하기 위해서 Bob에게 s를 전달 받는 대신, E(1), E(s),…, E(s^d)를 전달 받는 것으로 계산이 가능합니다. 또한 Alice는 Bob에게 전달 받은 정보들로부터 s 값을 알아낼 수 없습니다.

왜 유용한가?

이어지는 포스팅들에서는 blind evaluation이 SNARKs 안에서 어떻게 쓰이는지 상세히 살펴볼 것입니다. 살짝 이야기해보자면, 검증자는 증명자가 올바른 다항식을 알고 있는지 확인하고 싶어합니다. 증명자가 알지 못하는 s값에 대해 다항식을 풀도록 검증자가 유도할 때, 증명자가 잘못된 다항식을 가지고 있다면 검증자가 원하는 올바른 답을 전달하지 못할 것입니다. 이것은 즉, “서로 다른 다항식은 대부분의 점에서 다르다”라는 Schwartz-Zippel Lemma와도 같습니다.