들어가며
본 편에서는 [블록체인 영지식 증명 시리즈]의 마지막 주제인 zk-SNARKs의 수학 이야기로 Zcash팀이 연재한 Explaining SNARKs 를 다루고자 합니다. Explaining SNARKs를 이해하기 위해서는 영지식 증명, 타원곡선, 대수학 등의 개념이 필요합니다. 이를 위해서 블록체인 영지식 증명 시리즈를 연재하며 필요한 개념에 대해서 미리 다루었습니다. 따라서 본격적으로 이야기에 들어가기에 앞서, 위에 나열 된 이전 포스팅을 읽고 오시는 걸 추천드립니다.
첫 번째 이야기에서는 part 1, 2, 3의 내용을 다룹니다.
- part 1: Homomorphic Hidings
- part 2: Blind Evaluation of Polynomials
- part 3: The Knowledge of Coefficient Test and Assumption
Zcash팀이 연재한 Explaining SNARKs에서 설명한 수학적 논리를 이해하고 싶었으나, 수학을 전공하지 않아 어려우셨던 분들에게 조금이나마 도움이 되었으면 좋겠습니다. 비 수학 전공자도 이해할 수 있도록 구체적이고 상세하게 설명했으나 이해가 되지 않는 부분은 medium을 통해 언제든 질문 주시기 바랍니다. 그럼 시작해봅시다.
본 글은 Zcash의 Explaining SNARKs 시리즈를 바탕으로 작성되었습니다. 또한 시리즈의 한글 번역을 참고하기위해 onther의 슬라이드만 참고해서 작성했습니다.
[블록체인 영지식 증명 시리즈]
영지식 증명의 개요
- 영지식 증명 이해하기
- 영지식 증명의 개요
- ZKP Under the Hood - 비대화형 영지식 증명 이해하기
- 대화형 증명 시스템 (Interactive Proof System)
- 대화형 영지식 증명 시스템 (Interactive Zero-Knowledge Proof System)
- 비대화형 영지식 증명 시스템(Non-Interactive Zero-Knowledge Proof System)
영지식 증명 구현을 위한 타원곡선 이해하기
- 타원곡선의 수학 이야기(1)
- 타원곡선이 왜 생겼나요?
- 왜 타원곡선이라 부르나요?
- 타원곡선의 특징은 무엇인가요? - 타원곡선의 수학 이야기(2)
- 타원곡선이 암호학에서 사용되는 이유는 무엇인가요?
- 타원곡선의 수학적 정의는 무엇인가요?
블록체인에서 가장 많이 사용하는 zk-SNARKs 이해하기
- zk-SNARKs의 수학 이야기(1)
- Homomorphic Hidings
- Blind Evaluation of Polynomials
- The Knowledge of Coefficient Test and Assumption - zk-SNARKs의 수학 이야기(2)
- How to make Blind Evaluation of Polynomials Verifiable
- From Computations to Polynomials
- The Pinocchio Protocol - zk-SNARKs의 수학 이야기(3)
- Pairing of Elliptic Curves
영지식 증명을 활용한 블록체인 확장 솔루션
Explaining SNARKs Part 1: Homomorphic Hiding (HH)
어떤 것이 Homomorphic Hiding(HH)인가요?
우리는 다음 세가지 성질을 만족하는 함수 E(x)를 HH라 하며, 이를 x의 hiding이라 부릅니다.
- 대부분의 x에 대해 E(x)만 가지고 x를 알아내는 것은 거의 불가능하다.
- 함수의 입력값이 다르면 출력값이 다르다.
- E(x)와 E(y)를 안다면, x와 y의 연산을 입력값으로 갖는 HH를 만들 수 있다.
첫 번째 성질부터 살펴봅시다. 1번의 E(x)는 어떤 x에 대한 함수의 값입니다. 우리는 근본적으로 x값을 숨기고 싶어 함수 E(x) 즉, HH를 사용합니다. 다시 말해 E(x)의 값으로 x의 값을 유추할 수 없도록 하고 싶다는 것입니다.
예를 들어, E(x) = 3x+7이라고 가정을 합시다. 만약 E(x)가 10이라면, 우리는 x의 값이 1이라는 것을 빠르게 알 수 있습니다. 1번 성질은 이렇게 우리가 간단한 연산으로 E(x)값(10)을 알고 있는 상태에서 x의 값(1)을 찾을 수 없어야 한다는 것입니다. 그렇다면 여기서 HH의 연산이 우리가 지금까지 배웠던 사칙연산이 아닌 좀 더 복잡한 연산이라는 것을 알 수 있습니다.
1번의 성질에서 ‘대부분의 x에 대해’라는 말이 나옵니다. 사실 Zcash에서 정의하는 HH는 잘 알려진 Computationally hiding commitment의 약화된 버전입니다. Computationally hiding commitment은 1번 성질에서 모든 x의 값을 숨겨야 하는 성질을 가지고 있습니다. 하지만, HH는 약화된 버전이므로 ‘대부분의 x를 숨기는' 것을 성질로 갖습니다.
두 번째 성질은 E(x)의 입력값(즉, x)이 다르면 출력값(즉, E(x))값이 서로 다르다는 것을 의미합니다. 이는 수학에서 일대일 대응이라고 합니다. 즉, 함수값에 대해 x값이 바뀌면 E(x)값이 바뀐다는 것을 의미합니다. 이는 하나의 x가 고유한 E(x)값을 갖도록 하는 성질입니다.
세 번째 성질은 우리가 E(x)와 E(y)의 값을 알고 있다고 할 때, HH의 첫 번째 성질에 의해 x와 y값을 모르지만, E(x+y)의 값을 구할 수 있어야 한다는 것을 의미합니다. 즉, HH는 x, y, x+y값을 모르는 상태에서 E(x)와 E(y) 값으로 E(x+y)를 구할 수 있어야 한다는 것을 의미합니다. 이에 대한 구체적인 예시는 좀 더 후에 살펴봅니다.
HH가 왜 영지식 증명에서 유용한가요?
이제 HH를 왜 영지식 증명에서 사용하는지 알아봅시다.
Prover는 x+y=7을 만족하는 x와 y값을 알고 있고, 이 값을 Verifier에게 공개하지 않고 자신이 x와 y값을 알고있다는 것을 증명하고자 합니다. 여기서 Prover의 secrect은 x와 y값입니다. Verifier가 검증해야 하는 statment는 Prover가 x+y=7을 만족하는 x와 y를 알고 있다는 것입니다. 만약 Prover가 알고 있다는 것을 증명하면 “statement is true”입니다.
Prover는 자신의 x와 y를 공개하지 않고 Verifier에게 x와 y를 알고 있다는 것을 증명하기 위해 HH(hiding)을 사용합니다. 방법은 다음과 같습니다.
- Prover는 x와 y의 hiding 값인 E(x)와 E(y)를 Verifier에게 보냅니다.
- Verifier는 Prover에게 받은 E(x)와 E(y)를 가지고 E(x+y)를 계산합니다(이는 HH의 세 번째 성질에 의거합니다).
- Verifier는 계산한 E(x+y)값이 E(7)의 값과 동일한지 확인합니다.
이 과정을 통해 Verifier는 Prover에게 받은 E(x)와 E(y)로부터 계산한 x+y의 hiding 값인 E(x+y)가 x+y의 고유한 hiding값임을 납득할 수 있습니다(이는 HH 두 번째 성질에 의거합니다). 다시말해, x+y=7에 대한 hiding 값은 하나이고, 만약 Prover가 준 E(x)와 E(y)으로 동일한 값을 도출했다면, Verifier는 Prover의 x와 y값을 몰라도 Prover가 x+y=7을 만족하는 x와 y값을 알고 있다는 것을 받아들일 수 있습니다.
여기서 Verifier가 x+y=7을 알고 있나요?
Verifier는 x와 y값은 모르지만 x+y값이 7이라는 것을 ‘알 수도’ 있습니다. 하지만, 위의 예시에서는 x+y=7이라는 것을 verifier가 알 경우 zkp가 너무 빨리 풀립니다. 실제 zk-SNARKs의 구현을 살펴보니, 위와 같은 과정을 x+y=7을 모른채로 해결합니다. 실제 zk-SNARKs 구현에서 Verifier는 7의 hiding 값인 E(x)을 계산하는 것이 아니라, Prover가 제공하는 연산값을 통해 E(7)과 같은 값을 갖는 연산을 ‘유도’하여 E(x+y)’을 계산하고 이를 2번에서 계산한 E(x+y)값과 비교합니다. 이에 대한 구체적인 이야기는 2편에서 다룹니다.
HH는 어떻게 구성하나요?
- E(x)에서 x를 도출할 수 없는 어려운 연산을 가진 그룹을 만들어 봅시다
우리는 이제 HH인 E(x)를 구성할 것입니다. 앞서 살펴봤듯이 일반적인 정수와 더하기 연산으로는 HH를 구성할 수 없습니다(예: 10 = x+7 => x=3). 즉, 일반적인 정수와 더하기 연산으로 HH를 구성하면 E(x)에서 x을 찾기 쉽기때문에, 첫 번째 성질인 ‘E(x)에서 x를 알 수 없음’이 깨지기 쉽습니다.
우리는 이와 비슷한 내용을 제 3편: 타원곡선의 근본적인 수학 이야기(2) 중 ‘어려운 문제가 무엇인가요?’에서 다루었습니다. 간략히 설명하면 Discrete Logarithm Problem을 어렵게 만드는 그룹이 타원곡선이며, 타원곡선의 정의와 덧셈규칙에 대해 공부했습니다. 결과적으로 SNARKs에서도 이를 위해 타원곡선을 사용합니다.
우리는 HH의 첫번째 성질을 깨기 어려운 HH를 구성하기 위해 finite group을 먼저 알아야 합니다. finite group은 ‘유한 군'이라 부릅니다. 여기서 ‘finite’는 group의 원소의 개수가 유한하다(무한하지 않다)는 것을 의미합니다. Group은 다음 네 가지 성질을 만족하는 ‘이항 연산(binary operation)’이 정의된 원소들의 ‘집합'입니다. 즉, finite group은 다음 네 가지 성질을 만족하는 이항 연산이 정의된 원소들의 유한 집합입니다. 성질은 다음과 같습니다.
첫 번째 성질은 ‘(닫힘)closure’ 성질입니다. 이는 x와 y가 유한 집합 G의 원소라고 할 때, x와 y가 그룹에서 집합 G에 대해 정의된 이항 연산을 취한 값이(x*y) G의 원소여야 한다는 것을 의미합니다.
두 번째 성질은 ‘(결합)Associativity’ 성질입니다. 이는 x, y, z가 모두 집합 G의 원소라고 할 때, 어떤 원소에 대해 우선으로 그룹의 이항 연산을 취하더라도 값이 같아야 한다는 것을 의미합니다. 즉, x*(y*z) = (x*y)*z이 성립한다는 것입니다.
세 번째 성질은 ‘(항등원)Identity’ 성질입니다. 이는 x가 집합 G의 원소일 때, 집합 G에는 x에 그룹의 이항 연산을 취해도 항상 x값이 나오게 하는 원소 I가 존재한다는 것입니다. 여기서 I는 항등원으로 G의 원소이고, I를 포함한 G의 모든 원소(여기서 임의로 x라고 함)에 연산을 취하면, 항상 I와 연산된 원소의 값이 나온다는 것입니다. 즉, x*I = I = I*x 입니다.
네 번째 성질은 ‘(역원)inverse’ 성질입니다. 이 성질은 x가 집합 G의 원소일 때, 집합 G에는 x에 대한 역원인 x^-1가 존재한다는 것입니다. 이는 G의 모든 원소에 해당합니다. x의 역원은 x와 함께 연산되면 항상 항등원(I)가 나옵니다. 즉, x^-1*x=I=x*x^-1가 G의 모든 원소에 대해 성립합니다.
우리가 finite group의 정의를 알아본 이유는, HH의 조건을 만족하는 연산이 포함된 group을 만들기 위해서 입니다. 이제 우리는 E(x)에서 x의 값을 도출하기 어렵게 하는 연산을 가진 group을 만들것입니다.
HH의 성질을 만족하는 연산을 가진 group을 만들어봅시다.
먼저 유한 집합 G에 덧셈 연산을 통해 finite group을 만들어 볼 것입니다. 여기서 정의 하는 덧셈 연산이 조금 특별하니 유의하며 보시길 바랍니다.
어떤 A와 n을 정수하고 합시다. 정수 A에 대한 mod n은 A를 n으로 나눈 나머지 값을 의미합니다. 예를 들어 9 mod 7의 결과 값은 7을 9로 나눈 나머지 값인 2입니다. 이 mod n연산은 그룹 G={0, … , n-1}에 대한 덧셈 연산을 정의하는데 사용할 수 있습니다. 여기서 덧셈연산은 정수끼리 일반적인 덧셈 연산을 한 뒤 다시 mod n을 취하는 것입니다. 이렇게 하면 결과 값이 집합 G={0, … , n-1}에 속해 finite group의 첫 번째 성질인 closure을 만족합니다. 또한 다른 조건도 만족함을 보일 수 있습니다(이는 독자의 몫으로 남겨두겠습니다).
예를 들어 보겠습니다. n을 4라고 하면 그룹 G는 {0,1,2,3}입니다. G의 원소 정수 2와 3을 위의 그룹에서 덧셈연산을 하면 2+3 = 5 mod 4 = 1입니다. 여기서 1은 그룹 G의 원소임을 알 수 있습니다. 우리는 덧셈연산에 mod 4를 취해주었다는 의미로 2+3 = 1 (mod 4)라고 씁니다.
위 집합 G={0,…,n-1}과 이에 대한 특수한 덧셈 연산(mod n)을 가진 그룹을 Zn이라 합니다.
두 번째 그룹은 Zn과 비슷하지만, 곱셈연산을 정의한다는 차이가 있습니다. 우리는 mod p를 집합 G={1,… p-1}의 곱셈연산을 정의하는데 사용합니다. 여기서 p는 소수(prime number)로 우리가 잘 알고있는 1, 3, 5, 7… 입니다. 예를 들어, p가 5라고 할 때, 그룹 G는 {1,2,3,4}입니다. G의 원소 2와 3을 곱셈 연산을 한다고하면, 2*3 = 6 mod 5= 1 (mod 5)입니다. 1은 G의 원소이므로 clousre 입니다. 또한 다른 조건도 만족함을 보일 수 있습니다(이는 독자의 몫으로 남겨두겠습니다).
만약 p가 소수라는 특수한 수가 아니라면 clousre 성질을 만족할 수 없습니다. p가 4라면, 집합 G는 {1,2,3}입니다. G의 원소인 2에 대한 곱셈연산을 하면, 2*2 = 4 mod 4 = 0 (mod 4)이고, 0은 G의 원소가 아니므로 closure 성질을 만족하지 않습니다.
여기서 정의된 특정한 집합 {1,… p-1}와 mod p의 곱셈 연산을 그룹 Zp*라고 합니다(p는 소수). 이렇게 정의된 Zp*는 세 가지의 유용한 성질을 갖습니다.
먼저 Zp*는 Cyclic group입니다. Cyclic group은 그룹의 원소에 genorator라는 특정한 원소 g가 있습니다. 이 g는 특정 횟수를 연산하면(여기서 연산은 그룹에서 정의된 연산입니다), 그룹의 모든 원소와 같은 값을 만들 수 있습니다.
이를 이해하기 위해 일반적인 정수와 덧셈 연산을 가진 그룹을 예로 들어보겠습니다. 이 그룹에서는 1이 generator g에 해당합니다. 1+1+…+1+…로 G의 모든 원소를 만들 수 있기 때문입니다.
따라서 Zp*이 cyclic group이라는 것은 위 처럼 정의된 연산을 통해 그룹 내의 모든 원소를 만들 수 있는 원소 g가 존재한다는 것입니다. Zp*의 연산 횟수 a는 집합 {0, … p-2}의 원소입니다(이 집합은 그룹 Zp*의 집합이 아님을 유의하시길 바랍니다, 이 집합은 앞에서 정의한 mod p의 덧셈 연산을 가지는 그룹Zp-1 의 집합입니다).
두 번째 특징은 이산 로그 문제(DLP: Discrete Logarithm Problem)가 어렵다는 성질을 갖습니다. DLP에 대한 자세한 설명은 타원곡선 (2)를 참고하시면 됩니다. 간략하게 DLP가 어렵다는 것은 x와 y가 Zp*의 원소라고 하고, x를 a번 연산하면 y가 된다고 할 때, 연산 횟수 즉 a를 찾는게 어려우면 DLP가 어렵다고 합니다. 이는 p가 충분히 큰 소수 일 때, Zp*의 원소 h가 주어졌을 때, g^a = h (mod p)를 만족하는 a를 찾는것이 불가능에 가까운 것을 의미합니다. 여기서 a는 집합 {0, … p-2}의 원소(이 집합은 그룹 Zp*의 집합이 아님을 유의하시길 바랍니다)이고, g⁰ = 1이라 정의합니다.
세 번째 특징은 그룹 Zp*의 원소가 mod p에 대한 곱 연산을 할 때, 지수 연산은 덧셈으로 이루어진다는 것입니다. 이를 이해하기 위해 간단한 예시를 살펴봅시다. 연산 횟수인 a와 b가 집합 {0, … p-2}의 원소라고 하고, g를 그룹 Zp*의 원소라고 할 때, g^a 와 g^b의 연산(그룹 Zp*에서 정의한 연산)은 g^(a+b (mod p-1))로 유도 되므로, 합의 mod p-1의 덧셈 연산으로 구할 수 있습니다.
위 세 가지 특징은 그룹 Zp*에서 정의한 함수 E(x)가 HH의 세 가지 성질을 만족하게 해줍니다.
그룹 Zp*에서 HH의 성질을 만족하는 함수 E(x)를 만들어 봅시다
우리는 위 그룹 Zp*에서 HH을 구성할 것입니다. 이 그룹에서 구성된 HH는 “support addition”으로 덧셈을 지원하는 HH라고 말합니다. 여기서 support addition은 E(x)와 E(y)로 E(x+y)를 계산할 수 있음을 의미합니다.
E의 입력값인 x와 y를 {0, … p-2}의 원소(그룹 Zp-1의 집합)라고하고, E(x) = g^x라고(g는 그룹 Zp*의 genorator로 즉, g를 그룹에서 정의된 연산을 사용하여 x번 연산하는 것입니다)정의합니다. 우리는 이 E(x)가 HH임을 보일 수 있습니다.
HH의 첫 번째 성질은 E(x)에서 x를 알아내는 것이 거의 불가능하다는 것입니다. 그룹 Zp*은 이산 로그 문제가 어렵다는 성질을 갖기 때문에, 이 그룹에서 정의된 연산 E(x) = g^x에서 E(x) 값과 g값을 알고 있더라도 x값을 찾는 것은 거의 불가능합니다. 이에 HH의 첫 번째 성질을 만족합니다.
HH의 두 번째 성질은 E(x)의 입력값이 다르면 출력값이 다르다는 것입니다. 그룹 Zp*은 cyclic group이기 때문에, 동일한 입력값 x에 대해서는 같은 연산값 E(x)가 나오지만, 다른 입력값 x에 대해서는 다른 연산값 E(x)가 나옵니다. 따라서 그룹 Zp*에서 정의한 E(x)는 HH의 두 번째 성질을 만족합니다.
HH의 세 번째 성질은 E(x)와 E(y)가 주어졌을 때, x와 y값을 몰라도 E(x+y)를 계산할 수 있어야 하는 것입니다. E(x)는 = g^x이고, E(y) = g^y이므로 E(x+y)는 그룹 Zp*의 세 번째 특징을 통해 다음과 같이 계산할 수 있습니다.
따라서 우리는 그룹 Zp*에서 “support addition” HH인 E(x) = g^x를 만들었습니다.
Explaining SNARKs Part 2: Blind Evaluation of Polynomials
우리는 다항식의 “blind evaluation”을 다룰 것입니다. 이 개념은 SNARKs 구성에 핵심이 되는 도구 입니다. 이를 다루기 위해 먼저 field라는 것을 알아보겠습니다.
Field가 무엇인가요?
Field는 group의 성질을 모두 만족하는 뎃셈과 곱셈 연산들을 갖는 집합을 말하며, ‘체'라 부릅니다. 앞서 우리는 집합 G에서 정의된 연산이 group이 되기 위해 4가지 조건을 만족해야 한다는 것을 살펴보았습니다. 그룹의 경우 덧셈 연산과 곱셈 연산을 따로따로 정의해서 Zn과 Zp*으로 나누어 정의했습니다. Field는 이 두가지의 연산이 4가지의 조건을 동시에 만족하는 집합 F를 말합니다.
여기서 정의하는 체는 Fp로 원소의 개수를 p(소수)개 갖습니다. 즉 Fp의 원소는 {0, … ,p-1}입니다. 이 체에서는 덧셈과 곱셈 연산 두개 모두를 정의할 수 있는데 앞서 그룹에서 살펴본 방법대로 기본 연산에 mod p를 취해줍니다.
Evaluation of Polynomials이 무엇인가요?
이제 우리는 체 Fp에서 d차 다항식 P를 나타낼 것입니다. 이를 하는 이유는 zk-SNARKs에서 Prover가 증명해야 할 것이 다항식의 형태를 띄기 때문입니다. 다항식 P(X)는 a_0+a_1 X¹+a_2 X²+…a_d X^d 입니다. 여기서 a는 체 Fp의 원소입니다.
우리는 이제 ‘Blind Evaluation of Polynomials’에서 ‘Evaluation of Polynomials’을 살펴볼 것입니다. evaluation P는 체 Fp의 원소인 s를 다항식 P(X)에 대입한 P(s)를 말합니다. 만약 제가 다항식이 알고 있다면, 즉 다항식이 어떤 꼴로 되어 있는지 알고 있다면 P(s)를 구하는 것은 쉽습니다. 우리가 알고있는 s에 단순히 계수 a를 곱해서 더하기만 하면 됩니다. 선형대수에서 이를 linear combination이라 합니다. 여기서는 단순히 다항식 P를 알고 있는 사람은 s를 알면 evaluation P인 P(s)를 구하기 쉽다!라는 것을 알면 됩니다.
이러한 성질로 그룹 Zp*에서 정의한 우리의 HH: E(x)는 ‘supports linear combinations’이 됩니다. 우리는 앞서 HH가 E(x)와 E(y)로 E(x+y)를 계산할 수 있어 “supports addition”이라 했습니다. “supports linear combination”은 a, b, E(x), E(y)를 알고 있을 때, x와 y를 몰라도 E(ax+by)를 쉽게 계산할 수 있다는 것을 말합니다. 여기서 x와 y는 그룹 Zp*의 원소이고, a와 b는 체 Fp의 원소입니다.
Blind Evaluation of Polynomials이 무엇인가요?
Blind evaluation of a polynomial의 단어를 하나씩 살펴보면, a polynomial는 다항식 P이고, evaluation of a polynomial은 P(s)입니다. Blind는 감추는 것인데, 여기서는 무엇을, 어떻게 감추는 지 살펴볼 것입니다.
그럼 먼저 evaluation of a polynomial 를 감춰야 하는 상황을 먼저 보겠습니다. Prover는 Fp의 d차 다항식 P를 알고 있고, Verifier는 Fp의 임의의 숫자 s를 알고 있습니다. Verifier는 P(s)의 hiding 값인 E(P(s))를 알고 싶습니다(여기서 E(s)는 우리가 그룹 Zp*에서 정의한 연산입니다). Verifier가 E(P(s))를 알 수 있는 방법을 간단하게 생각해 보면 두 가지가 있습니다.
- Prover가 verifier에게 다항식 P을 알려주고, verifier는 P에 s를 대입하여 E(P(s))를 스스로 계산하면 됩니다.
- Verifier가 prover에게 s를 알려주고, prover가 (E(P(s))를 계산해 verifier에게 알려줍니다.
하지만 이 두 방법은 우리가 궁극적으로 이루고자 하는 blind가 아닙니다. blind evaluation problem의 조건은 다음과 같습니다.
- verifier는 다항식 P를 모른채로, E(P(s))를 계산할 수 있어야 합니다.
이는 우리가 이 전 포스팅인 “zk-SNARKs에 대해 알아보자”에서 살펴본 간결성과 관련한 것입니다. zk-SNARKs는 verifier의 증명의 간결성을 위해 점 8개만 알려주고 verifying이 가능하도록 하였습니다. 만약 verifier가 다항식 P를 알게 된다면, P(s)를 다항식 P를 통해 직접 연산해야 한다는 것을 의미하므로 zk-SNARKs 시스템의 간결성에 도움이 되지 않습니다. - Prover는 s를 알면 안됩니다.
우리가 Blind evaluation of a polynomial에서 궁극적으로 감추고 싶은 것은 verifier의 임의의 숫자 s입니다. 즉 s를 감추는 것이 blind의 조건입니다.
HH를 사용하여 s를 Blind 해봅시다!
이제 우리는 HH를 사용해서 s값을 감추고 Verifier가 E(P(s))을 알 수 있도록 할 것입니다.
먼저 Verifier는 Prover에게 s의 hiding 값인 E(s)를 보냅니다. 그런데 E(s) 하나만 보내는 것이 아니라, 우리가 위에서 만들었던 d차 다항식의 모든 s항에 대한 hidings을 만들어 보냅니다. 즉, E(s⁰), E(s¹), … ,E(s^d)을 모두 보냅니다. 이는 HH의 첫 번째 성질로 s값을 숨기는 역할을 하여 Prover가 s값을 유추하지 못하도록 합니다.
그 다음 Prover는 위 hidings값을 이용해 E(P(s))을 계산하여 Verifier에게 보냅니다. P(s)는 s와 d개의 계수(a0, a1, …, ad)로 구성된 d차 다항식입니다. 이 P(s)를 E(x)에 대입하면 E(P(s))입니다. 한편, 우리가 Zp*에서 정의한 HH는 “supports linear combination이기 때문에 아래등식을 만족합니다.
따라서, Prover는 s를 모른 채 E(P(s))를 계산할 수 있고, 이 값을 Verifier에게 보내더라도 HH의 첫 번째 성질로 Verifier는 P(s)를 알 수 없습니다. 다시말해, 우리는 HH를 통해 blind evaluation of a ploynomial을 성공했습니다!
blind evaluation이 zk-SNARKs에서 실제로 어떻게 유용하게 쓰이는 지는 part 4에서 알아보겠습니다. 그 전에 필요한 개념을 part 3에서 다루겠습니다.
Explaining SNARKs Part 3: The knowledge of Coefficient Test and Assumption
우리는 part 2에서 Prover가 Verifier가 가진 point s를 모른채로 자신이 가진 d차 다항식 P의 HH: E(P(s))를 bindly evaluation 할 수 있다는 것을 보였습니다. 이를 blind라고 부르는 이유는 Prover가 전체 프로세스에서 s에 대한 어떤 정보도 얻을 수 없기 때문입니다.
이 프로세스에서 부족한 점은 Prover가 E(P(s))를 계산할 수 있다는 것이 Prover가 Verifier에게 엉뚱한 값이 아니라 자신이 가진 다항식 P에 s를 대입해서 나온 ‘실제 계산값'을 보낸다는 것을 보장하지 않는다는 것입니다. 이에 따라 Prover가 올바르게 프로토콜을 강제하는 로직(logic)이 필요합니다. 이 로직의 구체적인 방법은 part 4에서 설명하고, 이를 위해 필요한 기본 도구인 knowledge of Cofficient Test를 먼저 알아보도록 합시다.
Knowledge of Coefficient Test(KC test)가 무엇인가요?
사실 KC test가 없던 개념이 아닙니다. 일반적인 연구문헌에서는 “Knowledge of exponent assumption”이라는 개념으로 이미 있던 개념입니다. 이를 exponent assumption이라 부르는 이유는 주로 곱셈 연산이 정의된 그룹에서 사용되기 때문입니다. zk-SNARKs에서는 이를 다르게 바꿉니다.
본격적으로 KC test를 정의하기 전에 필요한 표기부터 살펴봅시다. 우리는 이 전까지 원소의 개수 p개를 갖는 mod p 곱센 연산에 대한 그룹 Zp*에서 HH를 정의했으며, 그룹 Zp*은 DLP문제를 어렵게 만들며, cyclic group이기 때문에 generator g가 존재한다고 했습니다.
우리는 이제부터 직관적인 설명을 위해 곱셈 연산이 아닌 ‘덧셈 연산’으로 표기합니다. 즉, 우리는 이제까지 E( α) 연산을 체 Fp의 원소 α에 대해 g^ α (mod p)로 표기했습니다. 하지만 우리는 ‘마치 덧셈 연산처럼' α*g (mod p)라고 표기할 것입니다. 주의할 점은 표기는 덧셈 연산 처럼 했지만, 실제 연산은 곱셈 연산이라는 것입니다!
우리가 굳이 편의를 위해 연산 표기를 바꾼 이유는 α-pair라는 이름때문입니다. 우리는 KC Test에 사용하는 b= α*a를 만족하는 원소쌍 (a,b)를 α-pair라고 합니다. b=a^α 보다는 b= α*a가 좀 더 α-pair라는 이름을 붙이기 직관적입니다.
자 이제 KC Test를 해봅시다.
- Verifier가 체 Fp*의 원소 α를 선택하고, 그룹 Zp*의 원소 a를 선택합니다. 그 후, b= α*a (mod p)를 계산합니다. 여기서 b 또한 Zp*의 원소입니다.
- Verifier가 Prover에게 “Challenge 쌍"인 α-pair (a, b)를 전송합니다.
- Prover가 (a, b)와 다른 새로운 α-pair (a’, b’)를 그룹 Zp*에서 찾아 Verifier에게 전송합니다.
- Verifier는 Prover에게 받은 (a’ , b’)가 α-pair인 경우에만 이 응답을 받아들입니다.
Verifier는 (a’, b’)가 α-pair인지 계산하는 방법은 간단합니다. Verifier는 α값을 알기 때문에 α*a’가 b’이면, (a’, b’)는 α-pair임을 확인할 수 있습니다. 그런데 여기서 의문이 생깁니다. Prover는 α값을 모르는데 어떻게 새로운 α-pair을 만들 수 있을까요?
Prover의 새로운 α-pair 만들기!
실제 방법을 알아보기 전에 Prover가 α를 알고 있다고 가정해 봅시다. Prover는 α를 알고 있으면, 그룹 Zp*에서 임의의 원소 a’를 선택하여, α*a’를 계산해 b’를 쉽게 구할 수 있습니다. 그런데 이 test에서는 Prover가 α에 대해 아는 것이 오직 α*a (즉, b의 값)뿐이고, a와 b는 DLP를 어렵게 만드는 그룹 Zp*의 원소이기 때문에 b의 값으로 α를 계산할 수 없습니다.
자, 이제 Prover가 α값을 모른 채 새로운 α-pair (a’, b’)를 구하는 방법을 알아봅시다. 먼저 Prover는 체 Fp*에 속한 원소 γ를 선택한 후 (a’, b’) = (γ∙a,γ∙b)를 계산하여 Verifier에게 보냅니다. 여기서 (γ∙a,γ∙b)로 계산된 (a’, b’)는 α-pair의 조건을 만족합니다.
여기서 γα는 둘 다 상수이고 그룹 Zp*에서 정의된 연산이 아닌 일반적인 곱셈 연산입니다.
그런데 Prover가 이를 만족하는 γ를 찾으려면 a와 a’의 비율을 알고 있어야 합니다. 즉, Prover가 a’ = γ∙a를 만족하는 γ를 알고 있다는 것입니다. 우리는 이를 통해 하나의 가정을 만들 수 있으며 그것이 이 파트의 주제인 ‘The Knowledge of Coefficient Assumption(KCA)’입니다.
The Knowledge of Coefficient Assumption(KCA) 정의
KCA의 정의는 다음과 같습니다. 만약 prover가 verifier의 a와 α에 대해 non-negligible한 확률로 verifier의 challenge pair인 α-pair (a, b)에 대해 올바른 응답(α-pair 조건을 만족하는) (a’, b’)를 리턴한다면, prover는 a’ = γ∙a를 만족하는 계수 γ를 알고있다고 가정합니다.
자, 여기서 prover가 계수 γ을 알고 있다는 것을 어떻게 수학적으로 정의할 수 있을까요?
이를 위해 zk-SNARKs는 prover의 추출자라는 새로운 참여자가 있다고 가정합니다. 이 추출자는 prover의 내부 상태에 접근할 수 있습니다. 이 추출자는 KCA에 따라 prover가 성공적으로 α-pair (a’, b’)을 응답할 때마다, prover의 추출자는 a’ = γ∙a를 만족하는 γ를 출력할 수 있습니다. 만약 prover가 성공적으로 α-pair (a’, b’)을 응답했지만, 추출자가 적절한 γ를 추출하지 못할 확률은 negligible 합니다.
마치며
본 편은 [블록체인 영지식 증명 시리즈]의 마지막 주제로 영지식 증명을 활용한 블록체인, zk-SNARKs의 구현 원리에 대해 다루었으며 Zcash팀이 연재한 Explaining SNARKs의 내용을 알기 쉽게 설명해보았습니다.
Explaining SNARKs의 part 1, 2, 3를 다루었으며 HH와 Blind evaluation of polynomial와 이 두가지를 zk-SNARKs에 구현하기 위해 필요한 도구인 KCA를 다루었습니다. 다음 포스팅에서는 Explaining SNARKs의 part 4, 5, 6에 대해 다루며, HH와 Blind evaluation of polynomial 실제 zk-SNARKs에서 구현하는 내용을 알아봅니다.
본 편을 통해 Zcash 팀의 Explaining SNARKs의 zk-SNARKs 구현을 위한 수학적 논리를 이해하는데 도움이 되었기를 바라며, 피드백과 질문은 언제든지 환영합니다.
email: tjfh3217@gmail.com
[블록체인 영지식 증명 시리즈]
영지식 증명의 개요
- 영지식 증명 이해하기
- 영지식 증명의 개요
- ZKP Under the Hood - 비대화형 영지식 증명 이해하기
- 대화형 증명 시스템 (Interactive Proof System)
- 대화형 영지식 증명 시스템 (Interactive Zero-Knowledge Proof System)
- 비대화형 영지식 증명 시스템(Non-Interactive Zero-Knowledge Proof System)
영지식 증명 구현을 위한 타원곡선 이해하기
- 타원곡선의 수학 이야기(1)
- 타원곡선이 왜 생겼나요?
- 왜 타원곡선이라 부르나요?
- 타원곡선의 특징은 무엇인가요? - 타원곡선의 수학 이야기(2)
- 타원곡선이 암호학에서 사용되는 이유는 무엇인가요?
- 타원곡선의 수학적 정의는 무엇인가요?
블록체인에서 가장 많이 사용하는 zk-SNARKs 이해하기
- zk-SNARKs의 수학 이야기(1)
- Homomorphic Hidings
- Blind Evaluation of Polynomials
- The Knowledge of Coefficient Test and Assumption - zk-SNARKs의 수학 이야기(2)
- How to make Blind Evaluation of Polynomials Verifiable
- From Computations to Polynomials
- The Pinocchio Protocol - zk-SNARKs의 수학 이야기(3)
- Pairing of Elliptic Curves
