[밑바닥부터 시작하는 비트코인] 4. 직렬화

alg0r1thm·2022년 5월 2일

블록체인

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

목록 보기

4/4

4.1 직렬화 (Serialization)

직렬화 $^{serialization}$ 는 객체를 바이트 스트림으로 바꾸는 것을 말한다.
즉, 객체에 저장된 데이터를 스트림에 작성하기 위하여 연속적인 데이터 값으로 변환하는 것을 의미한다.
이 과정의 목적은 객체의 상태를 그대로 저장하고 필요할 때 재생성하여 사용함에 있다.
앞서 유한체부터 시작해 타원곡선 암호까지 작성한 다양한 클래스가 있을 것 이다.
이 해당 클래스의 객체들을 네트워크를 통하여 다른쪽으로 전송하거나 저장장치에 저장하기 위함에 있다.

4.2 SEC

바로 이전에 작성한 공개키 클래스인 S256Point 클래스부터 직렬화해보자.
우선 ECC 방식에서 공개키는 $(x,y)$ 좌표 형식임을 기억하자.
이미 ECDSA 공개키를 직렬화 하는 표준안이 존재한다.
이를 SEC $^{Standards\ for\ Efficient\ Cryptography}$ 형식 이라고 한다.
이 방식은 아주 작은 오버헤드만 요구하며, 공개키에 관련해서는 두가지 SEC 형식이 존재한다.
- 오버헤드 $^{overhead}$ 란 어떠한 처리를 하기 위해 들어가는 간접적인 처리 시간, 메모리 등을 말한다.

4.2.1 엔디안

들어가기에 앞서 엔디안 $^{Endian}$ 에 대해 알아보자.
엔디안이란 메모리와 같은 1차원 공간에 여러 개의 연속된 대상을 배열하는 방법이다.
엔디안은 보통 큰 단위가 앞에 나오는 빅 엔디안 $^{Big\ Endian}$ 방식과 작은 단위가 앞에 나오는 리틀 엔디안 $^{Little\ Endian}$ 방식, 두 경우에 속하지 않거나 둘을 모두 지원하는 미들 엔디안 $^{Middle\ Endian}$ 으로 나뉜다.

빅 엔디안 방식은 SPARC, ARM, Motorola 계열의 CPU가 사용하는 아키텍쳐 방식에서 사용한다.
리틀 엔디안 방식은 x86의 인텔 계열의 CPU 에서 사용한다.
예시를 들어 설명하면 아래와 같다.

Big Endian
{ 0000 0000, 0000 0000, 0010 0000, 0000 1000 } == { 0x00, 0x00, 0x20, 0x10 }
== { 0, 0, 32 16 }
Little Endian
{ 0000 1000, 0010 0000, 0000 0000, 0000 0000 } == { 0x10, 0x20, 0x00, 0x00 }
== { 16, 32, 0 0 }

4.2.2 비압축 SEC 형식

우선 주어진 점 $P=(x,y)$ 에 대한 비압축 SEC 형식 표현 방법이다.
- $**0$ x $04$ 의 $1$ 바이트 접두부로 시작**한다.
- 그 다음 $**x$ 좌표를 $32$ 바이트 빅엔디안 정수로 표현**한다.
- 그 다음 $**y$ 좌표를 $32$ 바이트 빅엔디안 정수로 표현**한다.
아래 그림을 통해 비압축 SEC 형식을 볼 수 있다.

비압축 SEC 형식 직렬화는 간단하지만 $256$ 비트 숫자를 $32$ 바이트로 변환하는 부분에 주목하자.

class S256Point(Point):
...
		def sec(self):
				'''returns the binary version of the SEC format'''
		return b'\x04' + self.x.num/to_bytes(32, 'big') \
					+ self.y.num.to_bytes(32, 'big')

Python 3 에서는 정수형 숫자를 bytes형으로 바꾸는 to_bytes 메소드를 사용한다.
첫 번째 매개변수는 변환 결과를 보관할 bytes형 상수의 길이이다.
두 번째 매개변수는 빅엔디안인 경우 big, 리틀엔디안인 경우 little의 문자열을 가진다.

4.2.3 압축 SEC 형식

$x$ 좌표값을 갖는 타원곡선 위 점은 2개이다.
앞서 설명한 것 처럼 타원곡선 방정식의 $y^2$ 항에 의한 결과이다.

이런 대칭성은 유한체에서도 성립한다.
- 방정식 $y^2=x^3+ax+b$ 를 어떠한 점 $(x,y)$ 가 만족시킬 때, $(x,-y)$ 또한 이 방정식을 만족시키기 때문이다.
- 유한체에서 $-y\ \%\ p=(p-y)\ \%\ p$ 이기 때문에 점 $(x,y)$ 가 타원곡선을 만족시키면 $(x,p-y)$ 또한 만족시킨다.
- 이들은 주어진 $x$ 좌표를 만족하는 방정식의 $2$ 개의 근이다.
- 그래서 $x$ 값을 안다면 $y$ 좌표값은 $y$ 또는 $p-y$ 가 된다.
- $p$ 는 $2$ 보다 큰 소수이기 때문에 홀수값을 가지며, $y$ 가 짝수인 경우 $p-y$ 는 홀수와 짝수의 뺄셈이 된다.
- 반면 $y$ 가 홀수인 경우 $p-y$ 는 짝수가 된다.
- $y$ 와 $p-y$ 중 하나는 짝수이고 하나는 홀수인 셈이다.
이를 활용하여 비압축 SEC 형식의 내용을 줄일 수 있다.
다음은 주어진 점 $P=(x,y)$ 에 대한 압축 SEC 형식의 표현 방법이다.
1. $y$ 값이 짝수면 $0$ x $02$ , 홀수이면 $0$ x $03$ 인 $1$ 바이트 접두부로 시작한다.
2. 그 다음 $x$ 좌표를 $32$ 바이트 빅엔디안 정수로 표현한다.

class S256Point(Point):
...
		def sec(self, compressded=True):
				'''returns the binary version of the SEC format'''
			if compressed:
				if self.y.num % 2 == 0:
						return b'\x02' + self.x.num.to_bytes(32, 'big')
				else:
						return b'\x03' + self.x.num.to_bytes(32, 'big')
			else:
				return b'\x04' + self.x.num.to_bytes(32, 'big') + \
						self.y.num.to_bytes(32, 'big')

압축 SEC 형식의 가장 큰 장점은 $65$ 바이트가 아닌 $33$ 바이트만 차지한다는 점이다.
수많은 트랜잭션에 정보가 포함된다고 할때 엄청난 절약이 될 수 있다.
그럼 유한체의 제곱근 계산을 통해 다음과 같은 수학문제를 풀어보자.

알려진\ v에\ 대하여\ w^2=v를\ 만족하는\ w를\ 구하시오

페르마의 소정리로부터 다음과 같이 전개 가능하다.

w^{p-1}\ \%\ p=1

w^2=w^2 \cdot w^{p-1}=w^{(p+1)}

이 때 $p$ 는 소수이므로 홀수이기에 $p+1$ 은 짝수이고 $2$ 로 나누어 떨어진다.
위의 식 $w^2=w^{(p+1)}$ 의 양변에 제곱근을 취하면 아래와 같다.

w=w^{(p+1/2)}=w^{2(p+1)/4}=(w^2)^{(p+1)/4}\\ \therefore v^{(p+1)/4}

secp256k1 에서 사용하는 $p$ 는 $p\ \%\ 4=3$ 인 성질을 만족하기 때문에 아래와 같이 된다.

(p+1)\ \%\ 4=0

이는 $(p+1)$ 이 $4$ 로 나누어 떨어진다는 의미이므로 $(p+1)/4$ 는 정수가 된다.
정리하면 아래와 같다.
- secp256k1 의 $p$ 값을 가지는 유한체에서 $w^2=v$ 를 만족하는 $w$ 값은 $v^{(p+1)/4}$ 이다.
- 제곱근은 양수와 음수의 2개의 근이 있으므로 나머지 근은 $p-w$ 로 구할 수 있다.
위 공식을 다음과 같이 S256Field 클래스에 일반 메소드로 추가 가능하다.

class S256Field(FieldElement):
...
		def sqrt(self):
				return self**((P + 1)//4

또한 직렬화 된 SEC 형식의 공개키가 있으면 이로부터 $(x,y)$ 를 반환하는 parse 메서드를 적용 가능하다.

class S256Point:
...
    @classmethod
    def parse(self, sec_bin)
        '''returns a Point object from a SEC binary (not hex)'''
        if sec_bin[0] == 4: #1
            x = int.from_bytes(sec_bin[1:33], 'big')
            y = int.from_bytes(sec_bin[33:65], 'big')
            return S256Point(x=x, y=y)
        is_even = sec_bin[0] == 2 #2
        x = S256Field(int.from_bytes(sec_bin[1:], 'big'))
        #right side of the equation y^2 = x^3 + 7
        alpha = x**3 + S256Field(B)
        #solve for left side
        beta = alpha.sqrt() #3
        if beta.num % 2 == 0: #4
            even_beta = beta
            odd_beta = S256Field(P = beta.num)
        else:
            even_beta = S256Field(P = beta.num)
            odd_beta = beta
        if is_even:
            return S256Point(x, even_beta)
        else:
            return S256Point(x, odd_beta)

주석 표시의 순서대로 코드를 해석하면 아래와 같다.
1. 비압축 SEC 형식은 순서대로 $x, y$ 값을 읽으면 된다.
2. $y$ 값이 짝수인지 홀수인지는 첫 번째 바이트로 알 수 있다.
3. $y$ 값을 얻기 위해 타원곡선 방정식의 오른쪽 변(alpha)의 제곱근을 구한다.
4. $y$ 값이 짝수인지 홀수인지에 따라 그에 따라 적절한 점을 반환한다.

4.3 DER 서명 형식

직렬화가 필요한 또다른 클래스로 Signature가 있다.
SEC 형식과 같이 $r$ 과 $s$ 두 숫자를 직렬화 해야한다.
그러나 Signature는 S256Point 처럼 압축될 수 없는데, $s$ 값을 $r$ 값에서 온전히 유도 할 수 없기 때문이다.
이 때, 서명을 직렬화 하는 표준을 DER $^{Distinguished\ Encoding\ Rules}$ 형식 이라고 한다.

4.3.1 DER 서명 형식의 정의

우선 DER 서명 형식은 아래와 같이 정의된다.
- $0$ x $30$ 바이트로 시작된다.
- 서명의 길이를 붙이며 보통 $0$ x $44$ ( $10$ 진수로 $68$ ) 이나 $0$ x $45$ 가 된다.
- $r$ 값의 시작을 표시하는 표식 바이트로 $0$ x $02$ 를 붙인다.
- 빅엔디안 정수로 $r$ 값을 표현하며 그 결과값의 첫 번째 바이트가 $0$ x $80$ 보다 크거나 같으면 $00$ 을 앞에 붙인다. 이후 바이트 단위의 길이를 다시 앞에 붙이고 최종 결과를 $3$ 번 결과 뒤에 더한다.
- $s$ 값의 시작을 표시하는 표식 바이트로 $0$ x $02$ 를 붙인다.
- 빅엔디안 정수로 $s$ 값을 표현하고 그 결과의 첫 번째 바이트가 $0$ x $80$ 보다 크거나 같으면 $00$ 을 앞에 붙인다. 이후 바이트 단위의 길이를 다시 앞에 붙이고 최종 결과를 $5$ 번 결과 뒤에 더한다.
$4$ 번과 $6$ 번 규칙에서 첫 번째 바이트 $\ge$ $0$ x $80$ 인 경우 $00$ 을 넣는 이유는 DER 형식이 음수값도 수용 가능한 일반 형식이기 때문이다.
또한 부호 있는 이진수에서 첫 번째 비트가 1인 것은 음수를 의미한다.
- 첫 번째 바이트 $\ge$ $0$ x $80$ 인 경우에 해당된다.
ECDSA 서명에서 모든 숫자는 양수이며, $0$ x $00$ 을 앞에 넣어야 첫 번째 비트가 $0$ 이 되어 양수로 인식된다.
아래의 그림과 같이 DER 형식의 예를 볼 수 있다.

$r$ 은 $256$ 비트 정수이기에 최대 $32$ 바이트로 표현된다.
첫 번째 바이트가 $\ge$ $0$ x $00$ 이라면 $33$ 바이트까지 필요하게 된다.
당연히 $r$ 이 작은 값이라면 $32$ 바이트보다 작을 수 있지만 $6$ 번 규칙의 $s$ 에 대해서도 동일하다.
굳이 필요하지 않아 보이는 $6$ 바이트가 포함되어 있어 이런 방식의 $r,s$ 직렬화 방식은 전체적으로 비효율적이다.

4.3.2 파이썬을 통한 구현

이를 파이썬을 통해 구현하면 아래와 같다.

class Signature:
...
    def der(self):
        rbin = self.r.to_bytes(32, byteorder='big')
        rbin = rbin.lstrip(b'\x00')
        
        if rbin[0] & 0x00:
            rbin = b'\x00' + rbin
        result = bytes([2, len(rbin)]) + rbin
        sbin = self.s.to_bytes(32, byteorder='big')
        
        sbin = sbin.lstrip(b'\x00')
        
        if sbin[0] & 0x00:
            sbin = b'\x00' + sbin
        result += bytes([2, len(sbin)]) + sbin
        return bytes([0x30, len(result)]) + result

여기서 result 부분은 정수 리스트를 byte([])를 통하여 bytes 형으로 변환 한 모습을 볼 수 있다.

4.4 비트코인 주소 및 WIF 형식

초기 비트코인은 비압축 SEC 형식 공개키가 할당되고 DER 형식 서명이 적용되었다.
하지만 이런 방식은 다양한 이유로 미사용 트랜잭션 출력 $^{UTXO}$ 의 보안성을 낮추는 방식이다.
그럼 현재는 어떤 방식을 사용하며 비트코인 주소가 무엇이고 어떻게 표현하는지 알아보자.

4.4.1 Base58 부호화

우선 송금을 위해서 어디에 보내야할지 원하는 주소를 알아야한다.
이는 모든 지불 방법에서 필요한 사항으로 비트코인에서만 해당되는 사항은 아니다.
비트코인은 디지털 화폐이기 때문에 주소는 공개키 암호 체계의 공개키가 될 수 있다.
하지만 SEC 형식은 전송하기에는 길이가 길다. ( $65$ 또는 $33$ 바이트)
이런 긴 바이트는 이진 형식으로 작성 시 사람 눈으로 읽기 어렵다는 문제가 있다.
Base $58$ Encoding은 공캐키의 $3$ 가지 고려사항인 가독성, 길이 보안성을 모두 달성하는 부호화 방식이다.

BASE58_ALPHABET = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

def encode_base58(s):
    count = 0
    for c in s:  #1
        if c == 0:
            count += 1
        else:
            break
    num = int.from_bytes(s, 'big')
    prefix = '1' * count
    result = ''
    while num > 0: #2
        num, mod = divmod(num, 58)
        result = BASE58_ALPHABET[mod] + result
    return prefix + result  #3

def encode_base58_checksum(b):
    return encode_base58(b + hash256(b)[:4])

주석을 통해 살펴보면 아래와 같다.
1. 몇 바이트가 $0$ 바이트인지 검증한다.
2. 매 while 루프에서 각 자리에 사용한 Base $58$ 숫자를 결정한다.
3. 맨 앞부분 $0$ 으로 된 부분을 $1$ 로 변경한다.
해당 파이썬 함수는 임의 길이의 bytes 형 값을 받아 Base $58$ 로 부호화된 str 형 값을 반환한다.

4.4.2 비트코인 주소 형식

압축 SEC 형식의 $264$ 비트도 여전히 비트 수가 많으며, 보안에 취약한 면이 있다.
주소의 길이도 줄이고 보안성도 높이기 위하여 ripemd $160$ 해시를 사용 가능하다.
- ripemd160 이란, 임의의 길이의 입력 값을 $160$ 비트로 압축하는 암호화 해시함수이다.
그럴 경우 $33$ 바이트의 SEC 형식을 $20$ 바이트로 줄일 수 있다.
비트코인 주소를 생성하는 방법은 아래와 같다.
1. 메인넷 $^{Mainnet}$ 주소는 $0$ x $00$ 으로 시작하고, 테스트넷 $^{Testnet}$ 주소는 $0$ x $6$ f 로 시작한다.
2. 압축 또는 비압축 SEC 형식 주소를 sha $256$ 해시함수에 넣고, 다시 ripemd $160$ 해시함수에 넣어 출력을 얻는다.
3. $1$ 의 접두 바이트와 $2$ 의 최종 해시 결과를 합친다.
4. $3$ 에서 얻은 결과를 hash $256$ 으로 해시하고 그 결과에서 첫 $4$ 바이트를 취한다.
5. $3$ 의 결과 뒤에 $4$ 의 결과를 붙이고 이를 Base $58$ 로 부호화 한다.
위의 절차를 아래와 같이 한줄 코드로 표현 가능하다.

def encode_base58_checksum(b):
		return encode_base58(b + hash(b)[:4])

또한 hash $160$ 함수는 helper.py 파일에 다음과 같이 정의되어 있다.

def hash160(s):
		'''sha256 followed by ripemd160'''
		return hashlib.new('ripemd160', hashlib.sha256(s).digest()).digest()

sha $256$ 해시는 hashlib.sha256(s).digest로 얻은 뒤 ripemd160 해시함수의 입력으로 넘겨준다.
이후 다음과 같이 S $256$ Point 클래스에 hash $160$ , address 메소드를 추가할 수 있다.

class S256Point:
...
		def hash160(self, compressed=True)
				return hash160(self.esec(compressed))

		def address(self, compressed=True, testnet=False):
					'''Returns the address string'''
					h160 = self.hash160(compressed)
          if testnet:
		          prefix = b'\x6f'
          else:
              prefix = b'\x00'
			    return encode_base58_checksum(prefix + h160)

4.4.3 비밀키의 WIF 형식

일반적으로 비밀키를 직렬화 할 경우는 별로 없는데, 비밀키는 네트워크로 전파하지 않기 때문이다.
비밀키를 전파시키는 것은 매우 위험한 행동이지만 가끔씩 다른 지갑으로 비밀키를 옮기고 싶은 경우가 있다.
이러한 경우에 WIF $^{Wallet\ Import\ Format}$ 형식을 사용할 수 있다.
비밀키를 읽기 쉽도록 직렬화 하는 방법인데, WIF는 주소에서 사용했던 Base $58$ 부호화를 사용한다.
아래는 비밀키를 WIF 형식으로 만드는 방법이다.
1. 메인넷 비밀키는 $0$ x $80$ 으로 시작하고 테스트넷 비밀키는 $0$ xef 로 시작한다.
2. 비밀키는 $32$ 바이트 길이의 빅엔디안으로 표현한다.
3. 만약 대응하는 공개키를 압축 SEC 형식으로 표현했다면 $2$ 번의 결과 뒤에 $0$ x $01$ 을 추가한다.
4. $1$ 번의 접두 바이트와 $2$ 번의 빅 엔디안 형식의 비밀키, $3$ 번의 접미 바이트를 순서대로 연결한다.
5. $4$ 번의 결과를 hash $256$ 으로 해시하고 그 결과에서 첫 $4$ 바이트를 체크섬으로 취한다.
6. $4$ 번 결과의 뒤에 $5$ 번 절차에서 구한 체크섬을 붙이고 Base $58$ 로 부호화 한다.
이를 통해 PrivateKey 클래스에 WIF 메소드를 아래와 같이 수정 가능하다.

class PrivateKey
...
		def wif(self, compressed=True, testnet=False):
        secret_bytes = self.secret.to_bytes(32, 'big')
        if testnet:
            prefix = b'\xef'
        else:
            prefix = b'\x80'
        if compressed:
            suffix = b'\x01'
        else:
            suffix = b''
        return encode_base58_checksum(prefix + secret_bytes + suffix)

비밀키를 $32$ 바이트 빅엔디안으로 바꾸고 테스트넷일 경우 $0$ xef 메인넷일 경우 $0$ x $80$ 으로 시작하며 압축형식인 경우 $0$ x $01$ 이 뒤에 붙게된다.

alg0r1thm

블록체인 한입

이전 포스트

[밑바닥부터 시작하는 비트코인] 4. 직렬화

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

4.1 직렬화 (Serialization)

4.2 SEC

4.2.1 엔디안

4.2.2 비압축 SEC 형식

4.2.3 압축 SEC 형식

4.3 DER 서명 형식

4.3.1 DER 서명 형식의 정의

4.3.2 파이썬을 통한 구현

4.4 비트코인 주소 및 WIF 형식

4.4.1 Base58 부호화

4.4.2 비트코인 주소 형식

4.4.3 비밀키의 WIF 형식

[밑바닥부터 시작하는 비트코인] 3. 타원곡선 암호

0개의 댓글