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

Seongjin Kim
Feb 13, 2019 · 6 min read

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

Image for post
Image for post

이 글은 Zcash 블로그의 내용을 바탕으로 작성했으며, 번역 목적이 아닌 해설을 위해 작성되었기 때문에 내용의 추가와 요약이 있습니다. 원문은 아래 Zcash 블로그를 참고해주시기 바랍니다.
https://z.cash/blog/snark-explain2

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

Image for post
Image for post

2. Blind Evaluation of Polynomials

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


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

다항식과 선형 결합

Image for post
Image for post

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

Image for post
Image for post

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

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

Image for post
Image for post

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

Image for post
Image for post

다항식의 Blind evaluation

* 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))를 풀어서 써보면 다음과 같습니다.

Image for post
Image for post

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

왜 유용한가?

ReturnValues

ReturnValues Blogs

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store