[zk-SNARKs 기초] 1. Homomorphic Hiding

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

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

1. Homomorphic Hidings

zk-SNARKs의 모든 요소들을 완전히 이해하는 것은 꽤 오래 걸릴 수 있기 때문에, Zcash 블로그에서는 여러 요소들 중 가장 중요한 한 가지로 “Homomorphic Hiding(이하 HH)”를 고르며 먼저 설명하고 있습니다.

함수 E(x)가 HH 함수라고 할 때 아래 조건들을 만족합니다.

* 대부분의 x에 대해, E(x) 값이 주어졌을 때 x를 알아내기 어렵습니다.
* 입력값이 달라지면 출력값도 달라집니다. 따 라서, x ≠ y일 때, E(x) ≠ E(y) 입니다.
* E(x)와 E(y)를 안다면, x와 y를 연산한 HH를 만들 수 있습니다. 예를 들어, E(x)와 E(y)로부터 E(x + y)를 계산할 수 있습니다.

아래는 HH 함수가 위 특징들을 만족할 때 왜 영지식 증명에서 유용한지를 보여주는 예제입니다.

Alice는 자신이 x + y = 7을 만족하는 x, y값을 알고있다는 사실을 Bob에게 증명하고 싶어합니다. 이 때, Bob은 x, y가 어떤 값인지 알 수 없어야 합니다.
1. Alice는 E(x)와 E(y)를 Bob에게 알립니다.
2. Bob은 전달 받은 E(x), E(y)로부터 E(x + y)를 계산합니다(이것은 위에서 살펴본 HH의 특징때문에 가능합니다).
3. Bob은 E(7)을 계산하고, E(x + y)와 E(7)이 일치하는지 확인합니다. 이 값이 같을 때 Alice의 증명을 받아들입니다.

이 과정에서 Bob은 x와 y가 정확히 어떤 값인지는 알아내지 못하지만, x + y = 7을 만족하는 x와 y가 E에 사용됨으로써 Alice의 증명을 받아들일 수 있습니다. 물론 이 예제는 엄밀히 따지자면 Bob이 아무 값이나 E에 대입해서 x값을 구해볼 수 있는 등 영지식 증명이라고 할 수는 없습니다.

이제 아래에서는 위와 같은 은닉이 어떻게 이루어지는지 살펴봅니다. 이 때, 일반적인 정수의 덧셈 연산을 통해서는 할 수 없기 때문에 유한군내에서 덧셈 연산을 정의해 사용합니다.

유한군
유한개의 원소를 갖는 군입니다. 여기서는 mod 연산을 사용해 최대값을 두어 원소의 갯수를 유한개로 제한합니다.
군은 일련의 연산에 대한 항등원과 역원이 존재하는 등의 조건을 만족하는 집합입니다.

임의의 정수 n이 있을 때, A mod n은 A를 n으로 나누고 남은 나머지를 의미합니다. 예를 들어, 9 mod 7은 2이고, 13 mod 12는 1입니다. mod n의 결과는 항상 0 이상이고 n - 1 이하이기 때문에, 우리는 이러한 mod n 연산을 {0,…,n - 1} 집합 내에서 덧셈 연산을 정의하기 위해 사용할 수 있습니다. 일반적인 덧셈 연산을 한 뒤 mod n을 취하면 그 결과값은 항상 {0,…,n - 1} 내에 포함됩니다. 이런 유형의 덧셈을 사용하고 있다는 것을 명확히 하기 위해 오른쪽에 (mod n)을 쓰기도 합니다. 예를 들어, 2 + 3 = 1(mod 4) 와 같이 표현할 수 있습니다. 이러한 덧셈 연산을 정의한 집합 {0,…,n - 1}을 ℤ_n이라고 하겠습니다.

p가 소수일 때, {1,…,p - 1} 집합 안에서 이루어지는 곱셈 연산을 정의하기 위해 mod p 연산을 사용할 수 있습니다. {1,…,p - 1} 집합 내의 원소들끼리 곱한 값에 mod p를 취하면 그 결과도 항상 {1,…,p - 1} 내에 존재합니다. 예를 들어, 2 * 4 = 1(mod 7) 입니다. 곱셈 연산의 집합에 0이 포함되지 않는 이유와 mod 연산에 소수를 사용하는 이유는 모두 집합을 군으로 만들기 위함입니다. 군 내의 곱셈 연산에는 항등원과 역원이 존재해야 하는데, 0이 집합에 포함되면 군의 조건을 만족하지 못합니다.

위와 같이 곱셈 연산을 정의한 집합을 ℤ_p^*라고 합니다. ℤ_p^*는 아래와 같은 성질을 지니고 있습니다.
1. ℤ_p^*는 순환군입니다. 따라서 생성원(generator)이라고 부르는 어떤 g가 ℤ_p^*의 원소일 때, ℤ_p^*의 모든 원소들은 g^a로 표현할 수 있습니다. 이 때, a는 {0,…,p - 2}의 원소이며 g⁰=1 입니다. 이런 특징들을 설명하기 위해 예제를 보겠습니다. p = 13, g = 7인 ℤ_p^*가 있을 때, a의 변화에 따라 g^a는 아래와 같이 변합니다. ℤ_p^*에서의 연산은 mod p를 포함하기 때문에, 아래 표의 g^a는 g의 a제곱에 mod p를 취한 것입니다.

위를 살펴보면 a의 최대값이 p - 2가 된 이유를 찾을 수 있습니다. mod 13에 대한 7⁰과 7¹²는 1로 같고 그 뒤로 a값이 변할 때마다 g^a 값은 같은 값이 반복되기 때문에, 이 예시의 ℤ_p^*는 7⁰부터 7¹¹를 원소로 갖는 순환군이라고 볼 수 있습니다. 따라서 이 순환군의 a는 0부터 11(p - 2)까지로 나타낼 수 있습니다.

2. ℤ_p^* 안에서의 이산 대수 문제는 해결이 충분히 어렵다고 여겨집니다. 즉, p가 충분히 큰 값이고 ℤ_p^*의 원소 g와 h 값이 주어졌을 때, g^a = h(mod p)를 만족하는 a값을 0,…,p - 2 내에서 찾기 어렵습니다.

이산 대수 문제
a^x=b에서 a와 b가 주어졌을 때 x를 찾는 문제이며, 지수적 복잡도를 가지고 있기 때문에 해결이 어렵다고 알려져 있습니다.

3. 지수법칙에 따라, a, b가 0,…,p - 2 중에 있을 때 아래 식을 만족합니다.

일반적인 정수의 지수법칙에서는 (g^a)*(g^b)=g^(a+b)가 옳다는 것이 당연한데, 이 식에서 mod (p - 1)이 사용된 이유는 위에서 보았던 것처럼, 지수로 쓰이는 a의 범위가 0부터 p - 2까지이기 때문입니다. 예를 들어, 13¹⁴ = 13^(14 mod 12) = 13² 입니다. 즉, g^a mod p에서 a가 p - 1 이상일 경우 g^a = g^(a mod (p - 1)) mod p이기 때문에 위 식에서 mod (p - 1)이 사용되었습니다. 정리하면, 거듭제곱의 곱으로 인한 지수의 덧셈이 성립합니다.

이런 특징들을 사용해 덧셈을 지원하는 HH를 구성할 수 있습니다. 즉, E(x)와 E(y)로부터 E(x+y)를 계산할 수 있습니다. E의 입력값 x를 ℤ_(p-1)로 가정하면(x가 지수로 사용되기 때문에 ℤ_p가 아닌 ℤ_(p - 1)입니다), 그 범위는 {0,…,p - 2}가 됩니다. 그런 모든 x에 대한 HH 함수를 E(x) = g^x라고 하면 위에서 보았던 특징들을 다음과 같이 정리할 수 있습니다.
1. 입력값 x가 달라지면 결과값은 ℤ_(p - 1)의 다른 원소가 됩니다.
2. E(x)=g^x에서 E(x), g값이 주어졌을 때 x값을 찾기는 어렵습니다.
3. E(x)와 E(y)가 주어졌을 때 다음과 같이 E(x+y)를 계산할 수 있습니다.