Zero (Knowledge)에서 Bulletproofs까지 — Part 1

Published in

CURG

9 min readJun 21, 2019

본 시리즈는 영지식 증명과, 영지식 증명의 블록체인 적용과 관련해 논리적 비약 없이 설명하고자 쓰여졌다. 특성상 매우 많은 수식이 등장한다. 또한 벡터와 행렬에 대한 기초 지식이 있는 독자를 대상으로 한다. 대수 구조, 타원 곡선 등에 대한 기초 지식이 있다면 이해에 큰 도움이 될 것이다.

본 시리즈는 Adam Gibson의 “From Zero (Knowledge) to Bulletproofs”이 서술하는 흐름을 기반으로 Jens Groth의 “Linear Algebra with Sub-linear Zero-Knowledge Arguments”, Bootle 外의 “Efficient Zero- Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting”, 그리고 Bünz 外의 “Bulletproofs”를 참조해 작성됐다.

Part 1에서는 앞으로의 포스팅을 이해하기 위한 선행 지식을 함양하고자 대수 구조와 타원 곡선에 대한 기초 지식을 설명한다. 시리즈 전반에 걸쳐 중-고등학교 수준의 벡터 및 행렬에 대한 기초 지식을 요구하지만, 이들의 설명은 생략한다.

대수 구조

일련의 연산(들)이 주어진 집합을 대수 구조(algebraic structure)라 한다. 자주 언급되는 대수 구조인 군(group), 환(ring), 체(field)에 대해 간단히 설명한다.

군

군은 가장 기초적인 대수 구조이다. 원소의 집합과 하나의 이항연산을 가진다. 원소 집합을 ‘𝐺’, 연산을 ‘●’이라 할 때, 군은 <𝐺, ●>으로 표기한다. 군은 다음의 네 가지 공리를 만족한다.

이항연산 ‘●’에 닫혀있다.
이항연산 ‘●’에 대해 결합법칙이 성립한다.
이항연산 ‘●’에 대해 항등원이 존재한다.
이항연산 ‘●’에 대해 역원이 존재한다.

만일 위 네 공리와 더불어 교환법칙까지 성립한다면 이를 아벨군(abelian group) 혹은 가환군(commutative group)이라 한다.

환

환은 두 개의 이항연산을 가지는 대수 구조이다. 환의 원소 집합을 ‘𝑹’, 연산을 ‘●’ 및 ‘☐’라 할 때, 환은 <𝑹, ●, ☐>로 표기한다. 환은 다음과 같은 공리를 만족한다.

이항연산 ‘●’에 대해

이항연산 ‘●’에 닫혀있다.
이항연산 ‘●’에 대해 결합법칙이 성립한다.
이항연산 ‘●’에 대해 교환법칙이 성립한다.
이항연산 ‘●’에 대해 항등원(0)이 존재한다.
이항연산 ‘●’에 대해 역원이 존재한다.

즉, <𝑹, ●>은 아벨군이다. 항등원(0)에서의 0은 일반적으로 우리가 생각하는 숫자 0과 아무런 상관이 없다고는 할 수 없지만, 엄밀하게는 구분할 수 있으며, 단순히 ‘●’에 대한 항등원을 의미하는 기호라 생각하자.

이어 이항연산 ‘☐’에 대해

이항연산 ‘☐’에 닫혀있다.
이항연산 ‘☐’에 대해 결합법칙이 성립한다.

이러한 대수 구조 <𝑹, ☐>를 반군(semigroup)이라고 한다. 즉, 환 <𝑹, ●, ☐>에서 <𝑹, ●>는 아벨군이고 <𝑹, ☐>는 반군이다.

나아가 다음을 만족한다.

이항연산 ‘●’에 대한 이항연산 ‘☐’의 분배법칙이 성립한다.

위 공리들을 만족하면 환이지만, 이를 유사환(rng 혹은 pseudoring)으로 구분하고 이항연산 ‘☐’에 대해 항등원이 존재하는 경우에만 환이라고 칭하기도 한다. 유사환은 단위화 과정을 통해 환으로 표준화할 수 있다는 것만 알아두자.

만일 위 공리와 더불어 ‘☐’에 대한 교환법칙까지 성립한다면 이를 가환환(commutative ring)이라 한다.

체

체는 쉽게 말해 덧셈, 뺄셈(덧셈의 역연산), 곱셈, 나눗셈(곱셈의 역연산)의 사칙연산을 소화할 수 있는 대수 구조이다. 체의 원소 집합을 ‘𝑭’, 연산을 ‘●’ 및 ‘☐’라 할 때, 체는 <𝑭, ●, ☐>로 표기한다. 체는 다음과 같은 공리를 만족한다.

이어 이항연산 ‘●’에 대해

이항연산 ‘●’에 닫혀있다.
이항연산 ‘●’에 대해 결합법칙이 성립한다.
이항연산 ‘●’에 대해 교환법칙이 성립한다.
이항연산 ‘●’에 대해 항등원(0)이 존재한다.
이항연산 ‘●’에 대해 역원이 존재한다.

즉, <𝑭, ●>은 아벨군이다.

이어 이항연산 ‘☐’에 대해

이항연산 ‘☐’에 닫혀있다.
이항연산 ‘☐’에 대해 결합법칙이 성립한다.
이항연산 ‘☐’에 대해 교환법칙이 성립한다.
이항연산 ‘☐’에 대해 항등원(1)이 존재한다.
이항연산 ‘☐’에 대해 역원이 존재한다. (단, 0이 아닌 모든 원소에서)

즉, 0이 아닌 모든 원소들의 집합 𝑭*에서 <𝑭*, ☐>는 아벨군이다. 또한 모든 0이 아닌 원소가 ‘☐’에 대해 역원을 가지는 환 <𝑹, ●, ☐>을 나눗셈환(division ring)이라 한다. 따라서 체는 가환환인 나눗셈환이다.

나아가 다음을 만족한다.

이항연산 ‘●’에 대한 이항연산 ‘☐’의 분배법칙이 성립한다.

유한체(finite field) 또는 갈루아체(Galois field)라 불리는 대수 구조는 유한개의 원소를 가지는 체이다. 19세기 프랑스의 수학자 갈루아는 체가 유한하기 위해 원소의 개수가 소수의 거듭제곱 꼴이어야 함을 증명했다. 따라서 유한체는 GF(p^n)으로 표기하며, 여기서 p는 소수, n은 1 이상의 임의의 정수이다.

타원 곡선

타원 곡선에 대한 깊은 이해는 지금으로서는 필요 없다. 다음과 같은 특징이 있다는 정도만 숙지하도록 하자.

임의의 체에 대해 일반화된 타원 곡선 방정식은 다음과 같다.

반면 실수체 상에서의 타원 곡선은 다음과 같이 정의된다. 이때 타원 곡선이 비특이(non-singular)하다는 조건이 붙는다. 비특이란 기하학적으로 첨점(cusp), 자체교차점(self-intersection), 고립점(isolated point) 등이 없다는 의미이다. 비특이하다는 조건은 판별식 ∆=−16(4a³+27b²)이 0이 아님과 동치이다.

몇 가지 타원 곡선의 그래프는 다음과 같다.

타원 곡선상의 덧셈 연산

실수체 상에서의 타원 곡선에서, 그래프 상의 임의의 두 점(P와 Q) 사이의 덧셈 연산을 수행할 수 있다. 두 점을 지나는 직선을 그으면 다른 한 점(R’)에서 타원 곡선과 교차하는데, 이 점을 x축으로 대칭시킨 지점 역시 타원 곡선 상의 점(R)이며, 최종적으로 덧셈 연산의 결과(P+Q=R)이다. 즉, 타원 곡선에서 점과 점 사이의 덧셈 연산의 결과 역시 점이다.

만일 동일한 점과 점 사이의 덧셈, 즉 P+P의 경우에는 P를 지나는 타원 곡선의 접선을 그리는 것으로 구할 수 있다.

만일 두 점 P와 Q가 x축에 대해 대칭 관계, 즉 P=−Q에 있다면 두 점을 잇는 직선은 타원 곡선과 교차하지 않는다. 이 경우 연산의 결과를 무한원점(point at infinity) 또는 영점(zero point)라 칭하고 O로 표기한다(P+(−P)=O).

덧셈을 확장하면 자연스럽게 스칼라배(scalar multiplication)를 정의할 수 있다. 타원 곡선 상의 점 P와 상수 k에 대해 kP는 P를 k번 더하는 것으로 구할 수 있다. 즉 2P=P+P, 3P=P+P+P 등과 같다.

타원 곡선 이산 로그 문제

GF(p) 상에서의 타원 곡선에 대해 곡선상의 임의의 점 P의 위수(order)는 tP=O를 만족하는 가장 작은 정수 t로 정의된다.

본 타원 곡선과 곡선상의 점 K, 위수가 t인 곡선상의 점 G가 주어졌을 때, K=kG를 만족하는 정수 k∈[0, t-1]를 구하는 것을 타원 곡선 이산 로그 문제(ECDLP, Elliptic Curve Discrete Logarithm Problem)라 한다. 타원 곡선 이산 로그 문제를 이용한 암호 시스템은 유의미한 시간 내에 k를 구하기가 어렵다는 점에 착안한다.