[밑바닥 부터 시작하는 비트코인] -1.Intro
진짜 비트코인의 밑바닥 : 수학, 그리고 타원곡선
Programming Bitcoin : 밑바닥부터 시작하는 비트코인
출처 : Programming Bitcoin by Jimmy Song(O'Reilly). Copyright 2019 Jummy Song, 978-1-492-03149-9
안녕하세요, 스크립토 4기 배준호입니다. 이번시간을 시작으로,"밑바닥부터 시작하는 비트코인" 책을 혼자 공부하고 나름대로 이해해본 내용을 시리즈로 연재해 보려고 합니다. 문과 출신으로 블록체인에 대해 아무것도 모르던 사람이 비트코인의 밑바닥부터 공부해 나가는 자습시리즈 정도로 봐주시면 될 것 같습니다. 저자께서 언급하신 바와 같이 항상 본문 시작하기 전에 출처를 남깁니다. (다른 밑바닥 시리즈를 보신 분들은 아시겠지만, 밑바닥 부터 시작한다고 해서 책의 내용이 기초부터 시작한다는 뜻은 아닙니다. 코어를 다룬다는 느낌으로 받아들이시면 됩니다. 구현 방식으로 파이썬을 다루기 때문에, 파이썬에 대한 이해가 선행 되어야 합니다.)
늦게올려서 죄송합니다ㅎ;
Intro
블록체인을 공부하면 가장 먼저 접하게 되는 것이 비트코인입니다. 블록체인에 대해서 자세히 공부를 하려면, 블록체인이 적용된 가장 초기의 가상화폐인 비트코인에 대해서 우선적으로 알아보아야 합니다. 하지만 비트코인에 대해서 공부를 해보고, 백서를 읽어보더라도, 저 같이 암호학이나 수학, 컴퓨터공학적 지식이 얕은 사람한테는 제대로 이해가 되지 않는 것이 사실입니다.
그렇다면, 비트코인의 가장 밑바닥부터 직접 구현을 해보면서 공부를 해보는 것은 어떨까요? 구현을 직접 하려면, 그 원리를 어떻게든 이해해야 합니다. 말씀드린 바와 같이 저는 문과 출신에서 컴퓨터 공학을 복수전공 하면서, 수학적,암호학적 지식이 얕기 때문에 내가 이해한 부분에 오류가 있을 수도 있고, 구현에 잘못된 부분이 있을 수도 있습니다. “누군가”의 공부의 흔적 정도로 생각해 주시고, 잘못된 부분은 계속해서 수정해 나가겠습니다.
Chapter 0. 개발환경
1. 책은 기본적으로 파이썬을 기반 언어로 사용하고 있고, 개발 환경으로 Jupyter notebook을 선택했습니다. 하지만 저는 제가 가장 익숙한 Visual Studio Code를 사용하였습니다. (공부를 진행하다가 저도 Jupyter notebook으로 환경을 바꿀 수도 있습니다. 처음에 가상환경을 설정하다가, 주피터 노트북에서 가상환경을 설정해본 적이 없어서 그냥 익숙한 VsCode로 환경을 바꿨습니다.)
2. 글을 작성하는 현재 기준 파이썬 최신 버전은 3.8입니다.
3. 책에서 가상환경 설정을 소개하고 있는데, 가상환경이란 마치 가상머신처럼, 내가 활용할 라이브러리나 패키지를 딱 그 환경에서만 설치하는 공간 정도라고 생각하면 됩니다. 여러가지 간섭이나 안정성을 고려했을 때 프로젝트를 시작하면 가상공간을 새로 설정하는 것이 좋습니다. 다만, 책에서 소개하는 가상환경 설치가 이상하게 안되었기 때문에, 저는 vscode에서 git bash 터미널로 “python -m venv (name)” 명령어로 가상환경을 생성했고, “source name/Scripts/activate” 로 가상환경을 실행했습니다.
Chapter 1. 유한체
본격적으로 내용을 다뤄보겠습니다. 이 책에서 기본적으로 1~4장까지는 수학적인 도구들에 대해서 설명합니다. 1장에서는 유한체를, 2장에서는 타원곡선에 대해서 알아보고, 3장에서는 비트코인 트랜잭션 작동방법의 핵심인 ‘전자 서명과 검증’에 필요한 타원곡선 암호를 다룹니다. 수학적인 내용이고, 이를 파이썬으로 구현하는 방식인데, 앞의 내용들을 반드시 알아야만 나중에 나오는 개념을 이해할 수 있기 때문에 반드시 차근차근 짚고 넘어가야 합니다.
1. 유한체의 정의
유한체에 대해서 생각해 보기 전에, 우리가 흔히 알고 있는 '정수'에 대해서 생각해 볼까요. 정수는 마이너스 무한대부터 플러스 무한대까지의 범위를 가지고 있으며, 양의 정수, 0, 음의 정수로 구성되어 있습니다. 정수끼끼리의 덧셈을 생각해 볼까요. 정수끼리 더하면 그 값은 정수입니다. 정수끼리 빼더라도 그 값은 정수 입니다. 이러한 속성을 '닫혀있다' 라고 합니다.
유한체란 수의 “집합”입니다. 다만, 아래의 5가지 특성을 만족하는 '+,-' 연산을 가진 집합이며, 그 원소수가 유한합니다.
a. 만약 a와 b가 집합에 속해있으면, a+b, a*b도 집합에 속해있다. (닫혀있다.)
b. +연산에 대한 항등원이 존재한다. 즉, ‘0’이 있다. a+0=a
c. *연산에 대한 항등원이 존재한다. 즉, a*1=a를 만족하는 “1”이 있다.
d. +연산에 대한 역원이 존재한다. 즉, a와 + 연산 결과가 0이 되는 b 역시 집합에 속해 있고 이는 -a이다.
e. *연산에 대한 역원이 존재한다. 즉. A와 *연산 결과 1이 되는 b 역시 집합에 속해 있고, 이는 A^-1이다.
또한, 유한 개수의 숫자를 원소로 하는 경우에는, 그 집합의 크기를 표현하는 어떤 값 p를 정할 수 있다. 이 p는 ‘위수(order)’라고 합니다. 즉,
의 형태를 띄게 됩니다. 이 F 유한체에는 위에서 말한 5가지의 성질이 적용되어야 하기 때문에, 유한체 내에서의 +,-연산은 우리가 일반적으로 알고 있는 +,-연산과는 다릅니다. 이에 대한 정의는 차후에 살펴보겠습니다. 유한체를 처음 접해본 사람으로써, 유한체는 일종의 새로운 체계와 같습니다. 그래서 익숙하지가 않으면 그 연산이 꽤나 헷갈리기 때문에 주의해야 합니다.
유한체는 “반드시 소수이거나” “소수의 거듭제곱”의 위수를 가져야 하는데, 우리는 “반드시 소수”인 위수를 갖는 유한체를 다룹니다. 그 이유는 곧 있으면 나옵니다.
파이썬으로 구현된 '유한체의 원소' 즉 FieldElement Class코드 분석
1) __init__ 생성자는 num(원소)과 소수인 prime(위수)을 받습니다. 즉, prime을 위수로 하는 유한체 원소 하나를 생성합니다.
2) if문을 통해서 만약 num이 위수인 prime의 범위를 지키는지 확인을 합니다. 즉 num은 prime-1 까지의 범위에 있어야합니다. 그렇지 않을 경우 ValueError를 발생시킵니다.
3) 조건에 맞는다면, num과 prime을 멤버로 갖는 객체를 생성합니다.
4) __repr__ 메서드는 이 객체를 표현하는 방식을 정의하는 메서드입니다.
5) __eq__ 메서드는 이 클래스 간의 “==”연산을 재정의 하는 것입니다. other parameter는 다른 유한체 원소를 의미합니다. 나중에 다루겠지만 유한체에서 “무한대” 는 None으로 정의하며, 만약 비교대상이 None, 즉 무한대면 “거짓”을 리턴합니다. 만약 그렇지 않다면, 두 유한체의 원소의 값(num)과 prime(위수)를 비교합니다. 동일한 원리로 __ne__ (!=를 의미) 역시 정의할 수 있습니다.
2. 나머지 연산(Remainder)
위에서 말한 유한체의 닫힌 특성을 구현하기 위해서, 나머지 연산(%)을 활용합니다. 나머지 연산을 활용하면, 특정 값을 특정 범위 내로 변환시킬 수 있기 떄문입니다. 따라서, 유한체의 덧셈은 새로 정의됩니다.
+연산을 새롭게 정의즉, 만약 위수가 19인 유한체라면, 이 유한체의 원소인 11과 17의 덧셈 결과는 11+17=28, 그리고 28%19를 하여 9가 되는 것입니다. 이 원리는 앞으로 전개되는 모든 내용의 기본입니다. 역원 역시 같은 원리로,-a=-a%p 로 정의가 되며, 음수의 %연산은 음수가 양수가 될 때 까지 계속해서 그 위수를 더해주면 됩니다.뺄셈도 동일하게 a (-f) b=(a-b)%p 로 정의됩니다.
__add__는 "+"연산을 새롭게 정의 / __sub__는"-"연산을 새롭게 정의3. 유한체 곱셈과 거듭제곱
곱셈 역시 덧셈과 유사하게 생각하면 됩니다. 정수집합에서 곱셈은 여러 번 더하기 인데, 유한체에서도 마찬가지입니다. 덧셈과 마찬가지로, %연산을 해주면 됩니다.
이 곱셈에서 특이한 점이 있습니다. 다로 다음과 같은 경우입니다.
위수가 19인 유한체 F가 있다고 생각. 그리고 K가 각각 1,3,7,13,18인 경우에 다음은?
{K*0,K*1,K*2,……….K*18} 단, *은 유한체의 *연산
윗줄부터 1,3,7,13,18을 곱했을 때의 놀라운 결과!다음과 같은 결과가 나옵니다. 즉, 모두가 같은 집합인 것입니다!! 이는 위수가 ‘소수’일 때는, 그 유한체에 0이 아닌 임의의 원소를 전체에 곱하면 같은 집합이 온다는 의미입니다. 이러한 성질을 위해서 우리는 위수가 소수인 유한체를 사용합니다.
거듭제곱의 경우에는, 마찬가지로 거듭제곱한 값을 위수로 나누는 방식으로 메서드를 구현하면 됩니다. 하지만 이 방식은 차후에 필요한 음수 지수를 표현하기가 힘듭니다. 여기에 페르마의 소정리를 활용해야 하기 때문에, 거듭제곱 메서드는 조금 뒤에 다루겠습니다.
4. 유한체의 나눗셈
유한체에서는 나눗셈을 다루기가 가장 힘듭니다. 가장 좋은 방법은, 일반 대수에서 나눗셈이 곱연산의 역연산이라는 것입니다. 즉, 위수가 19이고, 유한체 간의 곱셈을 '*',나눗셈을 '/'라 했을 때, 3 * 7 = 21%19 = 2 로부터 2/7 = 3 이라는 점을 알 수 있습니다. 하지만 이러한 방식은 3*7 = 2 를 모르는 상황에서 2/7를 계산할 수 없습니다. 여기에서 페르마의 소정리가 활용됩니다.
여기서 거듭제곱, %연산은 유한체 연산이 아니라 원래 의미의 연산입니다.페르마의 소정리에 따르면, 소수인 p와 0보다 큰 n에 대해서 n^(p-1)%p=1 입니다. 즉, 유한체를 (위수-1)의 거듭제곱 연산을 하면 1이 나온다는 것입니다. (유한체의 거듭제곱 연산에는 %p가 포함된다는 것을 잊으면 안됩니다.) 페르마의 소정리는 많은 자료가 있기 때문에 따로 다루지는 않겠습니다.
결국, 나눗셈은 곱셈의 역연산이기 때문에 다음이 성립합니다.
여기서 b^-1 을 계산하는데 페르마의 소정리가 사용됩니다. 페르마의 소정리에 따라서 b^(p-1) = 1 입니다. (p-1 거듭제곱 연산 역시 유한체의 거듭제곱 연산으로 일반 거듭제곱연산에 %(p)가 숨어있는 것을 기억해야합니다.) 따라서,
이 성립됩니다. 이로써, 역원의 거듭제곱 연산을 통해서 나눗셈을 구현할 수 있게 되었습니다. 가령, 위수가 19인 유한체에서, 2 / 7 = 2 * 7^19-2 = 2*7^17 의 계산으로 바뀌게 됩니다. 이러한 경우에, 지수가 매우 커지게 되는 경우에는 그 연산에 시간이 오래걸립니다. 따라서, 파이썬에서 제공하는 빠른 거듭제곱 연산인 pow() 함수를 활용할 수 있습니다. pow()함수는 (밑,지수,나머지연산) 인자를 두어 빠르게 연산하는 것이 가능합니다. 따라서 다음과 같은 코드가 가능합니다
코드 분석
1) __pow__ 메서드는 **연산을 재정의 하는 것입니다. exponent를 받는데, 이 exponent가 만약에 음수라면 양수로 바꿔주는 과정이 필요합니다.
2) 양수로 바꿔주는 과정은 다음과 같습니다. 페르마의 소정리에 따라서 a^(p-1)=1. 만약, a^(-3) 을 계산하고 싶다면, a^(-3)* a^(p-1) 을 계속 하면서 지수를 양수로 바꿔줄 수 있습니다. 즉, 지수 exponent를 받아서 만약 이 값이 음수이면 p-1을 계속 더해서 양수로 바꿔줄 수 있습니다.
3) 위의 연산을 반복문으로 할 수도 있지만, 더 간단하게 %연산을 활용하면 양수로 값을 바꿔줄 수 있습니다. (음수의 %연산은 그 수가 양수가 될때까지 더해주는 연산.)
4) __truediv__ 메서드는 실수 나눗셈을 정의하는 메서드입니다. 위수를 비교하고, pow 함수를 실행합니다. pow(other.num, other.prime-2, other.prime) 이라는 의미는 other.num 을 p-2제곱하여 %연산을 한후, 한번 더 %연산을 한 것이다. b^-1= b^(p-2)를 그대로 구현하여 적용한 코드입니다.
여기까지가 chapter 1. 유한체의 내용입니다. 사실 뒷부분의 내용도 정리해놓긴 했는데 한 포스트의 길이가 너무 길어질 것 같네요ㅎㅎ 다음으로 넘기겠습니다. 쓰다 보니까 너무 내용이 장황해진 것 같기도 하네요. 다음부터는 조금 더 컴팩트하게 써보겠습니다. 제가 만약 잘못 이해한 부분, 잘못 작성한 코드가 있다면 너그러이 생각해 주시고 계속해서 수정하겠습니다.
그럼이만!!
