밑바닥부터 시작하는 비트코인 - 1장 유한체

본 게시글에서는 저서 '밑바닥부터 시작하는 비트코인'의 Python으로 작성된 예제 코드를 Go로 컨버팅 하여 작성하였습니다.

🐱‍👤 전체 코드

GitHub - piatoss3612/bitcoin-from-scratch

---

❓ 유한체를 이해해야 하는 이유

비트코인의 핵심인 전자서명과 서명 검증 알고리즘을 이해하기 위해 필요한 타원곡선 암호를 파악하기 위해

---

📕 유한체의 정의

1. a와 b가 집합에 속해 있으면, a+b와 a*b도 집합 안에 있다 (덧셈과 곱셈에 닫혀있는 집합)
2. 집합에 0으로 표기하는 원소가 존재하고 집합 내 다른 원소 a와 + 연산 결과는 a다. 즉 a + 0 = a (덧셈의 항등원 존재)
3. 집합에 1로 표기하는 원소가 존재하고 집합 내 다른 원소 a와 * 연산 결과는 a다. 즉 a * 1 = a (곱셈의 항등원 존재)
4. 집합의 원소 a와 + 연산 결과가 0이 되게 하는 원소 b가 역시 집합에 속해 있고 이러한 b를 -a로 표기한다 (덧셈에 대한 역원 존재)
5. 0이 아닌 집합의 원소 a에 대해 a * b = 1이 되게 하는 원소 b가 역시 집합에 속해 있고 이러한 b를 a^-1로 표기한다 (곱셈에 대한 역원 존재)

유한체의 집합 크기를 표현하는 어떤 값 p를 집합의 위수(order)라고 합니다.

---

📗 유한집합 정의하기

 집합의 위수가 p이면 집합의 원소는 0, 1, 2, ... p-1로 쓸 수 있으며 다음과 같이 표기합니다.

F_p = { 0, 1, 2, ... p-1 }

 유한체의 위수(p)는 항상 가장 큰 숫자 원소(p-1)보다 하나가 더 많습니다. 또한 유한체는 반드시 소수(prime)이거나 소수의 거듭제곱을 위수로 가져야 합니다.

 

Go로 유한체 코딩하기

// 유한체의 원소를 나타내는 구조체
type FieldElement struct {
	num   int
	prime int
}

// 유한체의 원소를 생성하는 함수
func New(num, prime int) (*FieldElement, error) {
	if num >= prime || num < 0 {
		return nil, fmt.Errorf("num %d not in field range 0 to %d", num, prime-1)
	}

	return &FieldElement{num, prime}, nil
}

// 유한체의 원소를 문자열로 표현하는 함수 (Stringer 인터페이스 구현)
func (f FieldElement) String() string {
	return fmt.Sprintf("FieldElement_%d(%d)", f.prime, f.num)
}

// 유한체의 원소가 같은 유한체에 속하고 같은 값을 가지는지 확인하는 함수
func (f FieldElement) Equals(other FieldElement) bool {
	return f.num == other.num && f.prime == other.prime
}

Python 예제와의 차이점

1. 구조체를 사용했습니다.
2. 생성자 함수를 추가했습니다.
3. 연산자 오버로딩이 불가능한 대신 구조체의 메서드로 기능을 구현했습니다.

---

🎲 나머지 연산

 유한체의 정의에 따르면 유한체는 덧셈, 곱셈, 뺄셈(덧셈의 역원), 나눗셈(곱셈의 역원)에 대해 집합이 닫혀 있어야 하는데, 어떻게 한정된 범위의 값을 사용해서 유한체를 구현할 수 있을까요?

 

정답은 나머지 연산(Modulo Arithmatic)을 사용하는 것입니다.

 

 아무리 큰 수라도 나머지 연산을 적용하면 비교적 작은 범위의 수로 변환됩니다. 예를 들어, 12로 나머지 연산을 실행하는 경우에는 아무리 큰 수라도 0에서 11 사이의 수가 될 것입니다. 마치 아무리 시간이 흐르더라도 시곗바늘은 0부터 11까지의 수를 가리키는 것을 계속 반복하는 것과 같죠.

---

➕➖ 유한체 덧셈과 뺄셈

덧셈

 유한체에서 임의의 수 2개를 꺼내서 더하고 그 수를 위수로 나눈 나머지를 구합니다.

a + b = (a + b) % p

덧셈의 역원

 유한체에서 꺼낸 임의의 수 a와 더한 뒤 그 수를 위수로 나눴을 때 나머지가 0이 되는 수 -a를 구합니다.

-a = (-a) % p

뺄셈

 유한체에서 임의의 수 2개를 꺼내서 빼고 그 수를 위수로 나눈 나머지를 구합니다.

a - b = (a - b) % p

Go로 유한체 덧셈과 뺄셈 코딩하기

// 유한체의 원소를 더하는 함수 (더한 결과는 같은 유한체에 속함)
func (f FieldElement) Add(other FieldElement) (*FieldElement, error) {
	if f.prime != other.prime {
		return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
	}

	num := (f.num + other.num) % f.prime
	return New(num, f.prime)
}

// 유한체의 원소를 빼는 함수 (뺀 결과는 같은 유한체에 속함)
func (f FieldElement) Sub(other FieldElement) (*FieldElement, error) {
	if f.prime != other.prime {
		return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
	}

	num := (f.num - other.num) % f.prime
	// 음수일 경우 prime을 더해줌
	if num < 0 {
		num += f.prime
	}
	return New(num, f.prime)
}

Python 예제와의 차이점

1. 연산자 오버로딩이 불가능한 대신 구조체의 메서드로 기능을 구현했습니다.
2. 나머지 연산의 결과가 양수로 변환되지 않으므로 원소의 값이 음수인 경우, 위수를 더해줬습니다.

---

✖ 유한체의 곱셈과 거듭제곱

곱셈

 곱셈은 '여러 번 더하기'와 마찬가지 이므로 유한체와 임의의 수의 곱셈의 결과는 유한체에 속합니다.

a * b = (a * b) % p

거듭제곱

 유한체의 임의의 수를 꺼내서 거듭제곱하고 그 수를 위수로 나눈 나머지를 구합니다.

a^b = a^b % p

왜 위수가 소수인 유한체가 유용한가?

 일반적으로 위수가 소수인 유한체에 0이 아닌 임의의 원소 k로 전체 집합을 곱하면 그 결과는 다시 원래 집합이 됩니다. F₅ = { 0, 1, 2, 3, 4 }에 4를 곱한 결과는 { 0, 4, 3, 2, 1 }로 순서만 바뀌었을 뿐 원래 집합과 동일한 것을 확인할 수 있습니다.

 

 그러나 위수가 합성수인 경우에는 위수의 약수로 전체 집합을 곱하게 되면 곱하는 수에 따라 집합이 달라집니다. 예를 들어, F₄ = { 0, 1, 2, 3 }이 있고 4의 약수인 2를 전체 집합에 곱하면 그 결과는 { 0, 2 }가 됩니다. 집합의 원소 개수가 적어지는 것을 확인할 수 있습니다.

Go로 유한체 곱셈 코딩하기

// 유한체의 원소를 곱하는 함수 (곱한 결과는 같은 유한체에 속함)
func (f FieldElement) Mul(other FieldElement) (*FieldElement, error) {
	if f.prime != other.prime {
		return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
	}

	num := (f.num * other.num) % f.prime
	return New(num, f.prime)
}

Go로 유한체 거듭제곱 코딩하기

// 유한체의 원소를 거듭제곱하는 함수 (거듭제곱한 결과는 같은 유한체에 속함)
func (f FieldElement) Pow(exp int) (*FieldElement, error) {
	num := pow(f.num, exp, f.prime) % f.prime
	return New(num, f.prime)
}

// 거듭제곱을 구하는 함수 (분할정복을 이용)
func pow(num, exp, mod int) int {
	if exp == 0 {
		return 1
	}

	if exp == 1 {
		return num
	}

	if exp%2 == 0 {
		temp := pow(num, exp/2, mod)
		return (temp * temp) % mod
	}

	temp := pow(num, (exp-1)/2, mod)
	return (temp * temp * num) % mod
}

Python 예제와의 차이점

1. 분할정복을 이용하여 중간중간 나머지 연산을 적용할 수 있도록 별도의 pow 함수를 정의했습니다.

---

➗ 나머지 연산

 유한체의 나눗셈은 일반대수의 나눗셈과 마찬가지로 곱셈의 역연산을 적용할 수 있습니다. 예를 들어, F₁₉에서 3 * 7 = 21 % 19 = 2로부터 2 / 7 = 3이라는 등식이 성립합니다. 어떤 유한체 원소를 0이 아닌 다른 원소로 나눈 결과는 역시 유한체에 소속된 원소이므로 닫혀 있는 나눗셈이 가능해 집니다.

 

 그런데 3 * 7 = 2라는 것을 모른 채 2 / 7 = 3이라는 것을 어떻게 알 수 있을까요?

 

페르마의 소정리: n^(p-1) % p = 1

 

 페르마의 소정리에서 p는 소수입니다. 우리는 소수를 위수로 가지는 유한체를 다루고 있으므로 이 정리를 사용할 수 있습니다.

 

 나눗셈은 곱셈의 역연산이므로 아래와 같이 표현할 수 있습니다.

a / b = a * (1 / b) = a * b^-1

 여기서 b^-1을 구하면 나눗셈 문제가 곱셈 문제로 바뀝니다. b^-1은 페르마의 소정리를 활용하여 구할 수 있습니다.

페르마의 소정리에 따르면 b^(p-1) = 1
b^-1 = b^-1 * 1 이므로 페르마의 정리를 적용하면 b^-1 * b^(p-1) = b^(p-2)
따라서 b^-1 = b^(p-2)

Go로 유한체 나눗셈 코딩하기

// 유한체의 원소를 나누는 함수 (나눈 결과는 같은 유한체에 속함)
func (f FieldElement) Div(other FieldElement) (*FieldElement, error) {
	if f.prime != other.prime {
		return nil, fmt.Errorf("cannot add two numbers in different Fields %d, %d", f.prime, other.prime)
	}

	// 페르마의 소정리를 이용하여 나눗셈을 곱셈으로 변환
	num := (f.num * pow(other.num, f.prime-2, f.prime)) % f.prime
	return New(num, f.prime)
}

---

✖ 거듭제곱 메서드 수정

 거듭제곱의 지수가 음수인 경우에도 페르마의 소정리를 활용하여 값을 구할 수 있습니다. p가 소수일 때 a^(p-1)은 항상 1이 되므로 지수가 p-1보다 커지거나 -(p-1)보다 작아지게 되면  지수에 나머지 연산을 적용하여 불필요한 연산을 줄일 수 있습니다. 

// 유한체의 원소를 거듭제곱하는 함수 (거듭제곱한 결과는 같은 유한체에 속함)
func (f FieldElement) Pow(exp int) (*FieldElement, error) {
	exp %= (f.prime - 1)
	// 지수가 음수일 경우 양수로 변환
	if exp < 0 {
		exp += (f.prime - 1)
	}

	num := pow(f.num, exp, f.prime) % f.prime
	return New(num, f.prime)
}

---

💯 테스트 결과

$ go test -v -cover .
=== RUN   Test_FieldElement_New
--- PASS: Test_FieldElement_New (0.00s)
=== RUN   Test_FieldElement_String
--- PASS: Test_FieldElement_String (0.00s)
=== RUN   Test_FieldElement_Equals
--- PASS: Test_FieldElement_Equals (0.00s)
=== RUN   Test_FieldElement_Add
--- PASS: Test_FieldElement_Add (0.00s)
=== RUN   Test_FieldElement_Sub
--- PASS: Test_FieldElement_Sub (0.00s)
=== RUN   Test_FieldElement_Mul
--- PASS: Test_FieldElement_Mul (0.00s)
=== RUN   Test_FieldElement_Pow
--- PASS: Test_FieldElement_Pow (0.00s)
=== RUN   Test_FieldElement_Div
--- PASS: Test_FieldElement_Div (0.00s)
=== RUN   Test_main
--- PASS: Test_main (0.00s)
PASS
coverage: 100.0% of statements
ok      finite-field    0.002s  coverage: 100.0% of statements

---

📖 참고자료

밑바닥부터 시작하는 비트코인

GitHub - jimmysong/programmingbitcoin: Repository for the book

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!