들어가며
본 편에서는 [블록체인 영지식 증명 시리즈]에서 다루는 zk-SNARKs의 영지식 증명 구현 방법을 설명하기 위해, 핵심이되는 타원곡선을 이해할 것입니다. 타원곡선의 이야기는 ‘수학적’으로 다룰 것이며 첫 번째 이야기에서는 타원곡선의 근본적인 아이디어와 특징을 알아봅니다. 블록체인이나 영지식 증명이 아닌 타원곡선에 대해 궁금한 독자에게도 충분히 도움이 되는 수학적 내용으로 구성되어 있습니다
필자는 학부시절 수학을 전공해 대수학 등 과목을 공부 했으며, 본 글은 비 수학 전공자도 이해하기 쉽도록 풀어 설명하지만, 삼각함수 등의 내용을 다루기 때문에 고등학교 이과의 수학적 지식이 있으면 이해가 더욱 쉽습니다. 그럼 이제 같이 시작해 봅시다.
본 글은 카이스트의 Hahn, Sanggeun 교수님의 타원곡선 이론의 발표 내용을 참고하여 작성했습니다. 전체적인 흐름과 내용을 참고 했으며, 설명의 완결성과 독자의 이해성을 위해 구체적인 설명과 내용을 추가했습니다.
[블록체인 영지식 증명 시리즈]
영지식 증명의 개요
- 영지식 증명 이해하기
- 영지식 증명의 개요
- 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
영지식 증명을 활용한 블록체인 확장 솔루션
타원곡선의 근본적인 아이디어를 알아보자
Diophantus 퍼즐
타원곡선의 이야기는 고대 그리스의 수학자인 Diophantus로부터 시작하자. Diophantus가 재미있는 퀴즈를 제시했는데, 이를 먼저 살펴보자.
공으로 쌓아진 입체 피라미드를 평면에 한 겹으로 늘어놓았을 때, 각 층은 정사각형이 된다. 그 때 정사각형 한 면의 크기는 어떻게 구할 수 있을까?
x² 을 피라미드 제일 바닥에 있는 공의 개수라고 하면, 피라미드의 넓이는 우리가 고등학교 수학에서 배운 수열에 의해 식 (1)과 같은 x의 3차 방정식으로 유도할 수 있다. 우리는 이를 평면에 있는 정사각형에 관한 식으로 나타낼 수 있다. 평면에 공을 늘어놓았을 때, 한 변의 길이가 y인 정사각형의 넓이 y²는 x에 관한 3차 방정식(피라미드는 입체)으로 식 (2)와 같이 나타낼 수 있다.
Diophantus 퍼즐은 식 (2)에서 x와 y의 정수해를 찾는 것이다. 식 (2)를 그래프로 나타내면 다음과 같다.
Diophantus’ method
자, 이제 위의 내용을 하나하나 뜯어보자. 우리는 위에서 살펴본 y²의 식의 자명해(trivial solution: 자명한 해는 말 그대로 너무나 당연한 해를 말한다) 두 개를 알고 있다. 바로 (0, 0)과 (1, 1)이다. 이 두점으로 구성된 직선의 방정식은 y=x이다. 우리는 이 직선을 그림 (2)의 그래프에 그려서, y² 방정식(x의 3차 방정식)과 y=x의 새로운 교점을 “무조건” 찾을 수 있다. 직선의 방정식의 점 2개를 3차 방정식에 대입하면, 교차하는 또 다른 점을 쉽게 찾을 수 있다는 것이다. 식 (3)과 (4)에 해당하는 그림 (4)에 x의 3차 방정식과 y=x의 교점을 찾는 과정을 설명해 두었다.
교점 찾는 과정이 해결되었다면, 다음 단계로 넘어가도록 하자. 우리는 곡선의 자명해를 정하고 직선을 만들어 새로운 교점인 (1/2, 1/2)를 찾았다. 그림 (2)를 보면 알 수 있겠지만, 위 곡선은 x축 대칭이다. 따라서 (1/2, -1/2)를 갖는 또 다른 해도 찾을 수 있다.
우리는 새롭게 찾은 점(1/2, -1/2)와 자명해 (1,1)을 통해 또 다시 새로운 직선을 만들고, 그림 (4)와 같은 과정을 반복하여 또 다시 새로운 해를 찾을 것이다. 이를 통해 식 (6)을 유도하여 식 (7)의 새로운 해를 찾을 수 있다. 아래 그림을 통해 이를 관찰 해보자.
우리는 Diophantus 퍼즐을 통해 특정한 식(y²)과 곡선을 하나 유도 했고, 그 곡선의 특징(직선과 곡선의 제 3의 교점 찾기)도 알아보았다. 우리는 그림 (5)의 그래프를 타원곡선(elliptic curve)라 부른다. 이제부터 본격적으로 타원곡선에 대한 이야기를 해보자.
왜 타원곡선이라 부르나요?
본격적으로 타원곡선을 알아보기 전에 재밌는 적분을 알아보자. 식 (8)의 적분에 치환 적분을 사용하면 sin함수의 역함수로 유도할 수 있다. 사실 식 (8)의 적분함수는 쉬운 함수가 아니다. 이에 노르웨이 수학자 Abel이 식 (8)에서 적분식와 y의 상관관계를 연구하면서, y=sinw로 놓으면(즉 y라는 변수를 함수로 정의하면) sin^-1(sinw) = w가 되어 좀 더 식을 쉽게 관찰가능함을 밝혔다.
사실 Abel의 발견이 특별한 이유는 그 당시 Abel이 살펴본 ‘어려운' 적분식을 좀 더 쉽게 해결할 수 있도록 했기 때문이다. 그 적분식은 다음과 같다.
그 당시 Able은 그림 (7)의 F(w)라는 어려운 적분식(특별히 정의 하기도 어려워 F라고 쓴 것)을 살펴보고 있었다. 식 (9)는 곡선의 길이를 구하는 적분을 나타내는데, Abel은 이 식을 그림 (6)과 같은 방법으로 w를 특정한 함수로 정의하여 더욱 쉽게 적분식을 관찰할 수 있었다. 이를 통해 Abel은 타원 적분에 역함수 관계를 취했고, double periodicity를 발견했다.
이제 구체적으로 그림 (6)과 그림 (7)에 있는 내용을 살펴보자. 먼저 식 (8)은 제곱근 안에 “원의 방정식"으로 얻게 되는 2차 방정식(x²+y² = 1)이 포함되어 있다. 우리는 식 (8)의 y라는 변수를 함수로 변환하여 적분을 쉽게 풀 수 있는 방법을 찾았으니, 좀 더 발전시켜 제곱근 안에 3차 방정식을 넣고 변수 변환을 시도할 수 있다. 이에 따라 식(9)의 변수의 변환을 시도했는데, 제곱근 안의 3차 방정식의 경우 어떤 변수변환을 시도해도 적분이 3차 혹은 4차 방정식으로 남아있었다.
식 (9)와 같은 꼴의 적분식을 우리는 “타원 적분”이라 부른다. 식 (8)에 원의 방정식이 들어있다라는 말에서 힌트를 얻었을 수도 있지만(필자는 몰랐다..) 식 (9)은 “타원 둘레의 길이"를 구하기 위해 유도된 것이기 때문이다. 식 (9)의 적분이 어려운 이유 중 하나는 타원의 둘레 길이를 구하는 특별한 공식이 없기 때문이며, 우리는 심지어 이 것을 초월수라 부른다. 공식은 없지만 우리는 아래와 같은 과정을 통해 적분 꼴로 유도할 수 있다.
우리는 타원의 길이를 구하는 위의 과정 중 식 (10)이 식 (9)의 F(w)와 유사한 꼴을 가진다는 것을 확인할 수 있다. 이러한 꼴의 적분을 타원 적분(elliptic integral)이라 하며, 식 (11)의 y²으로 정의한 값을 “타원 곡선”이라 한다.
우리는 이때까지 타원 곡선의 근본적인 이야기를 살펴보았으니, Adel이 발견한 double periodicity를 통해 타원 곡선의 특징을 알아보자.
타원 곡선이 가진 특징이 무엇인가요?
우리는 앞서 y²이 x의 3차식으로 구성된 방정식을 “타원곡선”이라고 부르는 이유를 알아보았고, 이를 통해 타원 적분을 살펴본 후, 이 적분이 주기 2개를 가지고 있다는 특징을 확인했다. 이제 본격적으로 타원 곡선과 타원 함수의 이야기를 해보자
Double Periodicty
Adel과 가우스가 타원 적분을 연구하다 보니, z값에 어떤 w를 더해도 같은 값이 나온다는 것을 발견했다. 즉, z가 주기 w를 갖는다는 것이다. 여기서 z는 복소수인데, 복소수는 주기를 2개 갖는다. 그래서 이를 double periodicty function이라 부른다.
그림 (9)에서 식 (13)의 함수는 우리가 앞서 살펴본 그림 (7)의 식(9)와 같은 꼴의 적분이다. 위 함수는 식 (14)의 미분 방정식을 만족한다. 식 (14)의 G는 상수값이다. 여기서 재미있는 것은 왼쪽항의 미분의 제곱을 y²이라 하고 오른쪽 함수를 x라고 하면, 우리가 맨첨음 살펴본 Diophantus’의 식과 같은 꼴이 나온다는 것이다. 이는 z가 복소수이던 아니던 고려하지 않고 단순히 y²은 x의 3차식이라고 하더라도 모두 대수적(Algbriaic)으로 적분이 가능하다는 것을 의미한다.
Elliptic Functions and Elliptic Curves
이제 w라는 주기가 어떤 것을 의미하는 지 알아보자. 우리는 너무나 어려운 적분이라는 이유로 정의한 F 함수가 w_1, w_2라는 두 개의 주기를 갖는다는 것을 알고 있다. F는 복소수(C)에서 복소수로 가는 함수(F: C → C)이다. F가 주기를 2개 갖는 다는 것은 F가 w_1에서 갖는 값과 w_2에서 갖는 값이 동일하다는 것이다. 즉, 이는 그림 (10)의 평행사변형에서 나타나는 F의 함수값이 전체 필드에서 반복된다는 것이다. 따라서 이를 다시 표현하면 함수 F는 복소수를 L로 나눈 나머지 복소수로 가게 한다(F:C/L → C). 위의 내용이 조금 어려울 수 있다. 아래 예시를 통해 이를 이해해보자.
그림 (11)은 우리가 잘 알고 있는 삼각함수인 sin함수의 그래프이다. sinx은 실수에서 실수로 가는 함수(sin: R → R)이다. 이는 sin의 입력값을 실수로 주고, sin함수의 출력값이 실수로 나온다는 것이다. 위 그래프를 보면 sin은 주기가 2파이인 삼각함수라는 것을 알 수 있으며, sin의 모든 함수는 구간 [0, 2파이]까지의 값의 반복임을 알 수 있다. 따라서 실수 전체를 주기인 2파이로 나누면, [0, 2파이], [2파이, 4파이], … , [100파이, 102파이], … 이고, 이를 2파이로 나눈 나머지로 나타내면 모두 [0, 2파이(0)]을 갖는 다는 것을 알 수 있다. 즉, 주기에 따른 구간이 존재하면, 구간을 주기로 나눈 나머지 값은 모든 구간에서 같으므로, 동일한 함수값을 갖는다는 것을 알 수 있다. 이를 간단하게 표현하면 sin: R/2파이 → R이며, 여기서 2파이는 모듈러(modula)라고 한다. 모듈러는 어떤 값으로 나눈 나머지를 의미한다.
자 이제 다시 F:C/L → C로 돌아가자. sin의 2파이 역할을 하는 것은 격자 L이다. 즉, 빨간 네모가 sin의 구간 [0, 2파이]와 동일한 기능을 한다. 따라서 복소수에서 복소수로 가는 함수 F는 주기가 두 개(w_1, w_2) 존재하므로, 네모 안에 있는 F값을 전부 알면 복소수 평면 전체 함수 값을 알 수 있다(주기에 의해 네모 안의 함수 값이 반복하므로). 이제 저 복소수 평면을 주기로 나눈 나머지인 빨간 네모를 좀 더 살펴보자.
The complex points on an Elliptic Curve
미리 말하자면 이번 파트에서는 더욱 수학적인 이야기가 나온다. 결과부터 살펴보면 타원 곡선 그래프에 대한 이야기, “Point at infinity”에 대한 설명이 나온다. 수학적인 이야기보다 암호학에서 타원 곡선 사용에 관한 이야기가 궁금하다면 이 부분을 건너뛰고 2편을 읽어도 된다.
먼저 식 (17)을 직관적으로 설명하면, 복소수를 격자로 나눈 나머지는 평행사변형 꼴이 되는데, 이는 어떤 특정한 x, y 값에 의해 torus라는 것에 도달한다. 어려우니, 하나하나 다시 정리하자
- 우리는 앞서 타원의 둘레를 구하는 적분인 타원 적분을 통해, y²이 x의 3차식을 갖는 타원 곡선에 대해 계속 살펴보았다.
- 그런데 Adel이랑 가우스가 타원 적분 함수를 살펴보더니, 적분이 두 개의 주기를 갖고 특정한 미분 방정식을 만족한다는 것을 밝혔다. 그런데 이 미분방정식을 자세히 살펴보니 타원 곡선의 꼴이랑 같았다.
- 주기를 갖고, 미분방정식을 만족하는 ℘함수를 살펴보니, 주기로 인해 복소수 필드에서 격자 L로 나눈 나머지가 그래프에서 평행사변형 꼴이고, 모든 복소수에서 이 함수의 값은 평행사변형안에 있는 값의 반복이라는 것을 알았다.
- 자 그런데 식 (17)을 보니 저 평행사변형이 함수 ℘를 x값으로 하고, ℘’가 y값으로 하면 복소수 좌표 E(C)라는 torus에 도달한다고 한다.
여기까지가 위의 내용이다. 이제 E(C)인 torus에 대해 먼저 알아보자.
torus는 삼차원 공간 상에서 원을 포함하는 평면위의 직선을 축으로 만든 회전면(surface of revolution)이다. 사실 복소수 좌표에서는 x와 y의 값에 따라 torus에 도달할 수도 있고, sphere에 도달할 수도 있다. 이에 대한 설명은 그림 (14)를 참고하자. 우리가 관심있는 타원 곡선 꼴인 y²은 x의 3차식 방정식은 torus에 도달한다.
그림 (14)는 y²이 x의 이차방정식이고, x와 y가 모두 복소수이면 sphere에 도달함을 보여주며, y²이 x의 삼차방정식이면 torus에 도달한다는 것을 보여준다.
이러한 그래프 모양이 타원곡선이 복소수 함수에 의해 sphere이 아닌 torus에 도달하는 이유에 대한 추가적 설명이기도하다.
마치며
본 편은 [블록체인 영지식 증명 시리즈]의 두 번째 주제로 SNARKs에서 블록체인 시스템에 영지식을 구현하기 위해 사용하는 타원곡선에 대한 이해를 돕기 위해 작성되었습니다.
본 편에서는 타원곡선이 어떠한 이유로 생겼는지, 왜 이 방정식의 그래프를 타원 곡선이라 부르는지, 타원곡선이 갖는 특징인 주기가 무엇인지 알아보았습니다. 타원곡선의 내용은 타원곡선의 수학 이야기(2)로 이어지며, 여기서는 암호학에서 타원곡선이 사용 되는 이유, 타원곡선의 수학적 정의 등을 알아봅니다.
타원곡선에 대한 궁금증이 해결 되었기를 바라며, 피드백과 질문은 언제든지 환영합니다.
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
