비트코인의 합의 알고리즘 - 작업증명 (Proof of Work)

채굴(Mining)은 새로운 비트코인을 생산하는 과정입니다.

최초에 비트코인의 제네시스 블록이 생성된 시점에는 새로운 블록이 생성될때마다 50개의 비트코인이 보상으로 제공되었습니다. 비트코인 블록은 평균 10분마다 생성이 되기 때문에 10분마다 50개의 비트코인이 생성되었습니다.

또한 통화의 인플레이션을 방지하기 위해 비트코인은 4년마다(정확히는 210,000블록마다) 그 생산량이 절반으로 줄어듭니다. 즉, 4년후에 25개로 줄어들고, 다시 4년이 지나면 12.5개로 줄어듭니다.

하기의 블록정보를 보면 최초의 0번블록의 보상은 50 비트코인, 250000번 블록의 보상은 25 비트코인, 500000번 블록의 보상은 12.5비트코인으로 절반씩 줄어드는것을 볼수 있습니다.

[Block : #0]

[Block : #250,000]

[Block : #500,000]

채굴노드가 블록을 생성하여 메인 체인에 연결하기위해서는 먼저 거래가 포함된 블록을 생성해야 합니다.

블록을 생성하기 위해서 채굴노드는 먼저 검증된 거래가 들어있는 메모리풀(Memory pool) 또는 거래풀(Transaction pool)에서 조건에 맞는 거래들은 선별하여  블록을 구성합니다.

거래가 거래풀에 들어오기 위해서는 사전에 해당 거래가 유효함이 검증되어야 하며, 이 조건에 통과된 검증된 거래만 거래풀에 들어오게 됩니다.

하기 예와같이 채굴노드 1은 거래풀에서 거래 0,4,7,11번을 블록에 포함시켰고, 채굴노드 2번은 거래풀에서 거래 1,4,6,14번을 선택하여 헤더를 구성하였습니다.

채굴노드가 거래풀에서 거래를 선택하는것은 각 거래의 우선순위를 기준으로 하며 우선순위는 다음과 같이 계산되는데, 거래의 나이는 각 거래가 거래풀에 포함된후 지나간 시간을 말합니다. 블록내부의 거래공간중 첫 50KByte의 공간은 우선순위가 높은 거래들에게 할당이 됩니다. 따라서 거래수수료가 높지 않다고 해도 거래풀에 오래 포함되게 되면 자동으로 거래 나이가 증가되기 때문에 결국에는 블록에 포함되게 됩니다.

우선순위 = Sum ( 거래 수수료 * 거래 나이 ) / 거래 크기

위의 예에서처럼 채굴노드 1과 2가 서로 경쟁하여 한쪽이 채굴에 성공한경우, 예를 들어 채굴노드 1이 채굴에 성공한 경우, 해당 블록은 메인체인에 연결이 되고 블록체인상의 모든 노드에게 전송이 됩니다. 아직 채굴이 진행중인 채굴노드 2가 이와같이 새로 생성된 블록을 받게되면 자신의 작업증명을 중지한후, 자신이 작업중인 헤더에서 새로운 블록에 포함된 거래를 제거하고(4번 거래를 제거), 다시 거래풀에서 새로운 거래들을 가져와 새로운 헤더를 구성하고 다시 작업증명을 시작합니다. 채굴노드는 이 과정을 무한반복하게 됩니다.

그럼 채굴노드가 블록생성에 성공했음을 알리는 작업증명(Proof of Work)에 대해서 알아보겠습니다.

작업증명을 알아보기 위해 먼저 각 블록에 포함된 정보를 보도록 하겠습니다.

다음의 #277316번 블록의 정보를 나타내고 있습니다. 

https://blockchain.info/block/0000000000000001b6b9a13b095e96db41c4a928b97ef2d944a9b31b2cc7bdc4

먼저 Hash는 각 블록을 구분하는 SHA256 의 결과값인 256비트의 해쉬값입니다.

SHA256 의 결과값은 256비트의 고정길이 값으로 위와같이 64개의 Hex 값으로 표현됩니다.

어떤입력값에 대해서도 동일한 256비트의 결과값을 생성해냅니다.

SHA256의 결과값을 다음과 같이 예를 들어서 확인해 보겠습니다.

Hello world1 : d8f469ffeb577973530355bb16d593ef42320d8dfbe4720ff6f54467c04a46c5

Hello world2 : e0ecd5da1cf87424e4a4331c97ba94b37a7c0632676f3ce81dc299582596d2f8

Hello world3 : 3fcfca89f6b70c05d87035d1d2cf0d92bc05622d5f9d7304ed566af962c334bd

Hello world4 : 09b044fe014a500edc4358d55e4b59d595b7a2c9d01143ae37c577d1f68378e4

위의 예에서 Hello world1의 SHA256 결과값과 Hello world2의 SHA256 결과값은 완전히 상이한 결과값을 보이고 있습니다. 즉, SHA256 알고리즘은 입력값에서 약간의 변화가 있어도 전체가 다 변하는 특성이 있기때문에 출력값을 가지고 입력값을 유추할수가 없습니다. 위의 예시에서 앞의 고정값인 "Hello world"는 고정되고, 뒤의 숫자만 1에서 4로 변경이 되었는데, Hello world4를 입력으로 했을때 처음으로 첫자리에 0이 나왔습니다. 이것이 작업증명의 힌트가 됩니다.

각 블록의 Hash 값은 블록헤더를 사용하여 생성을 한다고 하였습니다.

이전에 설명했던 블록헤더를 다시한번 살펴보면 다음과 같이 블록헤더는 Previous Hash, Merkle Root, Timestamp, Bits, Version, Nonce 6개로 구성되며, 이중 Nonce를 제외한 5개의 값은 고정된 상수값입니다. 즉, SHA256의 입력이 동일하면 출력값은 동일하게 되기 때문에 Nonce 값이 변하게되 되면 출력값이 변하게 됩니다.

즉, 위의 예에서처럼 고정된 상수인 헤더의 5개값에 숫자 Nonce 값을 변화시켜 SHA256 출력값을 생성하는것입니다. 생성된 값이 특정값보다 작을 경우 작업증명에 성공했다고 판단하고, 각 노드에 생성한 블록을 전파합니다.

이때 기준이 되는 특정값이 블럭의 정보에서 보여지는 Bits 값입니다.

Bits 값이 바로 난이도 목표값을 나타내며 해당 목표값보다 작은 Hash값이 발견되면 작업증명이 완료되는것입니다.

Mastering Bitcoin[비트코인 : 블록체인과 금융의 혁신]에 나온 예를 가지고 설명하겠습니다.

난이도 목표값은 다음의 공식으로 계산됩니다.

target = coefficient * 2**(8 * (exponent - 3))

Bits 값은 419668748을 나타내고 있고, 이것을 Hex로 변경하면 0x1903a30c 이고, 첫 2자리수의 16진수가 지수, 나머지 6자리의 16진수가 계수를 나타냅니다.

(419668748 = 0x1903a30c :   exponent = 0x19, coefficient = 0x03a30c)

target = 0x03a30c * 2**(0x08 * (0x19 - 0x03)) 

  => target = 0x03a30c * 2**(0x08 * 0x16)  

  => target = 0x03a30c * 2**0xB0 

  => target = 238348 * 2**176(2의 176제곱)

 

즉, 계산된 target 값은 다음과 같습니다.

target = 22,829,202,948,393,929,850,749,706,076,701,368,331,072,452,018,388,575,715,328

이것을 Hex로 표현하면 다음과 같습니다.

target = 0x0000000000000003A30C00000000000000000000000000000000000000000000

즉 위의 target 값보다 작은 Hash 값을 찾게 되면 작업증명이 성공하는것입니다.

예를 든 277316번 블록의 블록 Hash 값은 다음과 같습니다. 

Hash = 0x0000000000000001b6b9a13b095e96db41c4a928b97ef2d944a9b31b2cc7bdc4

즉, target으로 계산된 난이도 목표값보다 작기 때문에 작업증명에  성공한것입니다.

이와같이 채굴과정의 작업증명은 타겟 난이도값보다 작은값을 발견하는 과정입니다. 이와같이 특정값보다 작은 Hash 값을 찾는 과정은 공식이 없이 무조건 SHA256 과정을 거쳐서 결과값을 확인하는 방법밖에 없습니다. 즉, Nonce  값을 변화시키며 타겟값보다 작은 Hash 값이 나올때까지 무한정 SHA256 연산을 수행하는것입니다.

비트코인의 블럭은 10분마다 생성이 됩니다. 이와같이 10분마다 블럭이 생성되도록 하기위해 난이도목표값인 Bits 값을 가변적으로 변경하고 있습니다. 이 값은 2주마다(정확히는 2016개 블록마다) 새롭게 계산이 됩니다. 즉, 2016개 블록마다 현재까지 블록이 생성된 시간이 2주보다 작은경우, 난이도 목표값을 높이고, 2주보다 큰 경우 난이도 목표값을 낮춥니다. 이와같이 난이도 목표값을 변화시켜 평균적으로 10분마다 하나의 블록이 생성되도록 조정하고 있습니다.