Chapter 1. 유한체
아래 글에서는 “밑바닥부터 시작하는 비트코인(Programming Bitcoin) -한빛미디어(2019)”의 Chapter 1. 유한체에 대한 내용을 다룬다. 본 챕터에서는 비트코인프로그래밍에서 유한체가 왜 중요한지 살펴보고 유한체에 관한 간단한 정의와 특징, 연산원리에 대해 살펴본다.
Writer. 임혜수
Reviewed by…
Contents
1. 들어가며
2. 왜 유한체(finite field)에 대한 이해가 중요한가.?
1) 디지털 서명 알고리즘의 중요성
2) 디지털 서명 알고리즘을 이루는 가장 중요한 두 요소
3) 트랜잭션 작동 핵심 알고리즘을 이해하기 위한 체계적인 학습을 위해서
3. 유한체는 무엇인가.?
1) 정의와 특징
2) 사칙연산
4. 마무리
1. 들어가며
이 글은 비트코인을 연구하고 학습하며 더 나아가 프로그래밍까지 진행하는 모임인 ‘비트코인 프로그래밍 스터디’에 필자가 5개월간 참여하고 활동하면서 얻은 지식과 교훈을 중심으로 이루어져 있다. 스터디는 비트코인 코어 개발자이자 교육자로 활동중인 지미송(Jimmy Song)이 저술한 책 ‘밑바닥부터 시작하는 비트코인 프로그래밍’ 을 중심으로 진행되었다. 필자는 유한체(finite field)와 타원곡선(elliptic curve)을 왜 학습해야 하는지에 대한 명확한 이유와 두 수학적 요소의 이해를 돕기 위한 목적에서 글을 기획해서 작성하게 되었고 나머지 11가지 주제( 타원곡선암호, 직렬화, 트랜잭션, 스크립트, 크랜잭션 검증과 생성, p2sh 스크립트, 블록, 네트워킹, 단순지급검증, 블룸필터, 세그윗 )는 함께한 스터디원 7명이 담당하여 글을 작성하게 되었다
5개월간 비트코인에의 핵심축을 이루고 있는 암호학적 내용을 이해하기 위해 페르마의 정리, 정수론, 현대대수학과 같은 수학적인 내용에서부터 화폐에 대한 경제학적인 논의와 더불어 BSV,BCH 와 같은 비트코인 생태계에 관한 전반적인 내용과 공개형 블록체인의 한계와 폐쇄형 블록체인의 필요성에 대한 갑론을박 등이 있었다. 이러한 내용을 바탕으로 글의 독자가 될 수 있는 블록체인에 대한 기술적인 지식을 넓혀가고자 하는 블록체인 업계 관계자, 일반인 뿐만 아니라 블록체인 개발에 입문하고자 사람들이이 비트코인 코어 기술을 살펴보면서 더 많은 것을 함께 통찰하고 지식을 공유해 보고자 한다.
2. 왜 유한체(finite field)에 대한 이해가 중요한가.?
1) 디지털 서명 알고리즘의 중요성
지미송은 비트코인을 이해하는 핵심은 디지털서명기술이라고 강조한다. 왜냐하면 2013년도부터 비트코인에 관하여 무엇인가를 만들어보려는 시도를 계속해서 진행하면서 이에 필요한 선행학습을 통해 얻게된 내용들이 결과적으로 디지털서명기술을 설명하는 모든 아이디어들에 대해 접근해왔던 것들에 대한 것이라고 말하고 있기 때문이다. 그 무엇에 대한 것은 비트코인의 심장이라고 할 수 있는 유한체(finite field) 연산을 하는 타원곡선 기반(secp256k1)의 디지털 서명 알고리즘(ECDSA) 을 대체하는 슈노르 디지털 서명(Schnorr Digital Signature)기술 때문 이었을 것이다. 현재 많은 비트코인 개발자들의 지지를 얻으면서 비트코인의 성능을 개선하기 위해 슈노르 디지털 서명(Schnorr Digital Signature)로 심장을 교체하는 일정이 예정되어 있다.
2) 디지털 서명 알고리즘을 이루는 가장 중요한 두 요소
비트코인의 심장인 전자서명 암호화 알고리즘인 ECDSA에서 Schnorr Digital Signature 으로 대체가 되더라도 이 두 암호화 암고리즘은 유한체(finite field)연산을 하는 특정한 타원곡선(elliptic curve)에서 정의된 secp256k1 타원곡선을 사용하기 때문이다. 이러한 알고리즘을 타원곡선 암호(ECC)라고 한다. 결국 ECC 를 기반으로하는 ECDSA 가 교체가 되더라도 두 가지 요소로 이루어져 있는 ECC 잘 이해하고 있다면 비트코인 핵심 기술의 이해도를 높일 수 있고, 추후에 소프트포크 이슈가 나오게 되더라도 이 두 가지 요소를 중심으로 구성된 기술 이라는 것을 명확하게 알 수 있다. 그래서 지미송은 유한체(finite field)와 타원곡선(elliptic curve) 두 수학적 이론이 근본적으로 가장 중요하다고 이야기하는 것이다.
3) 트랜잭션 작동 핵심 알고리즘을 이해하기 위한 체계적인 학습을 위해서
비트코인이 동작하는데 있어서 트랜젝션은 쪼갤 수 없는 가장 작은 가치이동의 단위이다. 나카모토 사토시의 백서에서 밝히고 있는 트랜젝션에 대한 발명의 동기를 더블스팬딩을 방지하기 위한 차원에서의 데이터 구조인 ‘a chain of digital signature’ 라는 말을 통해서 서명과 검증에 대한 설명만 집중적으로 다루고 있다. 이러한 트랜잭션 구조와 작동 핵심 알고리즘의 이해는 전자서명과 이를 검증하는 과정의 디지털 서명기술로 이루어진다. 그렇기 때문에 유한체(finite field)와 타원곡선(elliptic curve)에 대한 이해를 높힘으로서 트랜잭션의 작동 알고리즘을 보다 수월하게 학습하게 되고, 너 나아가 블록의 구조와 생성 원리를 학습하게 됨으로서 비트코인이 동작하는 핵심 원리를 이해하게 될 것이다.
4. 유한체는 무엇인가.?
정의와 특징
“ 유한체(finite field)는 수와 사칙연산의 개념을 추상적으로 전개하는 현대대수적 개념으로 덧셈, 뺄셈, 곱셈, 나눗셈과 같은 연산을 해결할 수 있는 유한개의 원소 집합 “
현대대수학에 접근 유한체는 대수적 접근을 통해 수의 개념을 파악하는 것은 익숙하지 않다. 하지만 유한체라는 것은 우리가 친숙하게 알고 있는 1,2,3,… 과 같은 자연수의 집합을 ℕ 으로 나타내는 원리를 활용하여 집합의 크기를 표현하는 값인 p를 위수(order)라고 정의하여 Fp = {0, 1, 2, … , p-1} 과 같은 표기법을 사용하는 또다른 하나의 수의 체계라고 생각하면 하면 쉽게 다가갈 수 있을 것이다. 그리고 나머지연산(Modulo Arithmetic)으로 사칙연산에 대해 닫혀있다는 특징과 소수(prime number)를 위수(order)로 하는 유한체의 특징 2가지를 간단히 살펴보면서 라는 하나의 수의 성질을 가진 것이 왜 비트코인과 블록체인이 해킹이 어려운 암호기술이 된다는 것인지를 친근하게 다가가는 계기가 될 것이다. 그리고 나눗셈 연산을 중심으로 조금 더 자세히 살펴보면서 우리가 일반적으로 알고 있는 사칙연산과 어떻게 다른지 확연히 알 수 있고 이것이 왜 암호학에 쓰이는 핵심 기술의 기반이 되는지를 조금은 알 수 있을 것이다.
사칙연산
체(field)에는 덧셈(+), 곱셈( · )의 연산에 대해 닫혀 있는 이항 연산자를 가지고 있으며 각각 연산에 대해 결합법칙과 교환법칙을 만족한다. 그리고 두 연산에 대해 각각 항등원과 역원이 존재하여 곱셈은 덧셈에 대해 분배법칙을 만족하여 다음과 같은 식은 만족한다.
A · (B + C) = A · B +A · C
나머지연산(Modulo Arithmetic)으로 사칙연산에 대해 닫혀있는 유한체를 만들 수 있게 되는데 이를 활용하여 소수(prime number)를 위수(order) p 로 하는 유한체(finite field) F에서 p 가 19 인 유한체 F19 를 예시 로 하여 다음과 같이 덧셈, 뺄셈, 곱셈의 예시를 보자.
덧셈 : (7 + 8)%19 = 15
뺼셈 : (11–9)%19 = 2
곱셈 : ⁷³ = 343% = 1
나머지연산(Modulo Arithmetic)은 마지막 숫자에서 다시 처음으로 돌아가는 ‘시계’처럼 생각하면 쉬운데 위수가 19인 경우에는 시계에 시침이 1로 시작해서 19로 끝나는 시계라고 생각해볼 수 있다. 이해가 가지 않는다면 도서의 1장중 나머지연산(Modulo Arithmetic)를 살펴보자.
나눗셈 : 2/7 = 2 · 7^(19–2)= 465261027974414%19 = 3
위와 같은 나눗셈 연산은 정수론의 내용을 다루고 있는 페르마의 소정리를 이해해야 한다. 나눗셈이 곱셈의 역연산이라는 점과 위수가 소수인 특징을 통해 다음과 같은 예시와 같은 연산이 가능해지게 되는데 자세한 내용은 1장의 유한체 나눗셈을 살펴보자.
정리하면 유한체는 추상대수학의 개념으로, 사칙연산이 자유롭고 산술의 잘 알려진 규칙들을 만족하는 대수 구조이다. 유리수 전체, 실수 전체 등도 체의 일종이라고 볼 수 있다. 이 체 중에서도 원소의 개수가 유한한 체를 유한체라고 하며, 다른 말로 갈루아 체라고도 한다. 이 유한체는 다음과 같은 특징이 있다.
- 유한체의 원소의 개수는 항상 소수의 거듭제곱이다.
- 유한체에서 0을 뺀 나머지 원소들은 순환군을 이룬다.
- 유한체는 위수(order)가 소수(prime number)이고 반드시 소수(prime number)이거나 소수의 거듭제곱(a power of prime)을 위수로 가져야 한다.
마무리
정리하자면 소수(prime number)를 위수(order) p 로 하는 유한체(finite field) Fp의 중요성을 이해하는것이 가장 중요하다. 위에서 잠시 언급하고 넘어갔지만 왜 소수(prime number)를 위수(order) p 로 하는 유한체(finite field) Fp를 다루는 지에 대한 내용의 중요성은 곧 현존하는 기술로 해킹을 불가능하게 하는 중요한 원리가 된다. 그리고 유한체(finite field)에서 정의된 타원곡선(elliptic curve)을 기반으로 특정한 방식으로 정의된 정규식(secp256k1)에 관한 구현체가 비트코인에 적용되어 전자서명 기술 기반의 핵심적인 체계인 타원곡선 기반의 디지털 서명 알고리즘(ECDSA)이라는 것을 이해하게 된다면 비트코인 가장 중요한 기술의 핵심원리를 파악하게 되는것이다. 이러한 내용들을 좀더 심도깊게 이해하기 위해서는 바로 다음에 소개하는 타원곡선에 내용을 좀 더 살펴보고나서 진수복님의 글을 통해 전자서명을 생성하는데 필요한 도구인 유한순환군(finite cycle grups)과 이산로그 문제(Discrete Logarithm)에 관한 글을 읽고 읽어가면서 ‘밑바닥부터 시작하는 비트코인 프로그래밍’에서 파이썬으로 구현된 구현체를 직접 코딩해보면 완벽한 이해를 도울 것이다.
