[해석서]Bitcoin: A Peer-to-Peer Electronic Cash System - 4. 작업 증명

앞에서, 어떤 이가 모든 블록에 대한 생성권리를 가지고 있다면, 타임스탬프의 순서를 맘대로 바꿀 수 있다 했습니다.

그래서, 이 블록생성에 대한 권리를 공평하게 분배해야하는 얘기까지 했습니다.

이제 어떻게, 블록생성에 관여하는 노드들이 공평하게 그 권리를 가지게 하는 지에 대한 내용입니다. 먼저 논문내용부터 보겠습니다.

 

4. 작업 증명

피어 투 피어 기반으로 분산된 타임스탬프 서버를 구축하기 위해서는, 신문이나 유즈넷 포스트가 아닌 아담백(Adam Back)의 해시캐시[6]와 유사한 작업 증명(PoW, Proof of Work) 시스템이 필요하다. 작업증명은 sha256같은 해시함수를 사용해서, 연속된 0(zero) 값으로 이루어지는 비트열로 시작되는 해시값을 찾는 과정이 포함된다. 이러한 과정에 걸리는 평균작업량은 요구되는 0 비트 수에 따라 지수적으로 증가하며, 반면에 이에 대한 검증은 한 번의 해시 계산으로 가능하다.

타임스탬프 네트워크의 작업증명은, 블록 해시 결과가 요구되는 연속된 0비트 수를 만족할 때까지, 블록에 포함되는 논스(nonce)값을 증가시키는 과정을 통해 구현된다. 일단 CPU 연산에 의해 작업증명을 만족하는 값을 찾은 경우, 해당 블록은 고정된다. 만약 해당 블록을 수정하려면 다시 작업증명을 만족하는 노력이 수반되어야 하고, 블록들이 체인처럼 연결되어 있기에, 수정한 블록의 다음 블록들에 대해서 동일하게 작업 증명을 해야 한다.

 

 

 

작업증명은 블록을 생성할 권리가 특정인에게 혹은 소수에게 집중되지 않게 하기위한 방법입니다. 어떻게 하면 될까요? 

만약 각 노드들을 통제하는 중앙기관이 있다면 쉽습니다. 그 중안기관이 각 노드들에게 공평한 순서로 블록을 생성할 수 있는 권한을 주면됩니다. 하지만 이 논문에서 제시하고 있는 노드들에는 중앙이란 개념이 없습니다. 해서, 이 논문에서 제시하는 방법은, 각 노드들이 가지고 있는 하드웨어성능에 관계없이 각 노드들이 '운'을 가지고 권한을 획득하게 합니다. 물론 완벽하게 하드웨어 의존성이 사라지는 것도 아니고, 완벽하게 '운'에만 의존하게 되는 것은 아니지만, 최소한 각 노드들의 동작시키는 CPU 갯수가 같다면, 비슷한 확률로 권한을 획득하게 합니다.

 

어떻게해서 각 노드들이 비슷한 확률로 권한을 획득하게 했을까요?

방법은, 각 노드들이 어떤 답을 찾으면 권한을 획득하게 되는데, 그 답을 찾을 수 있는 확률을 각 노드가 비슷하도록 만든 겁니다.

이러한 것이 가능하도록 실제 논문에서 제시한 방법은, 블록에 대한 해시값을 구할 때, 난수를 입력값에 더 가미해서(이 난수를 nonce라고 합니다), 해시값의 앞부분 비트가 연속된 0이 나올 때까지, 각 노드가 난수 입력값을 바꿔가면서 계산하고, k개 이상(예를 들어 60개 이상)의 연속된 0이 나오는 해시값을 가장 먼저 찾은 노드에게 그 블록에 대한 생성권을 주는 겁니다. 쉽게 얘기해서, 각 노드에게 선착순 문제를 풀게하는 겁니다.

 

해시(hash)에서 연속한 0이 나오게 한다는 것의 의미

이 글의 앞 부분에서 설명한 해시함수는, 어떤 입력값을 일정한 자릿 수의 값으로 변환하는 함수라 했습니다. 해시함수의 특성은 1)입력값의 한 비트라도 변화하면 그 해시값은 거의 전체 비트에 대해 변화가 일어나고, 2)해시의 출력값은 그 분포가 균등하고, 3)입력값이 동일하면 동일한 출력값을 내는 성질이 있습니다.

 

예를 들어 8비트의 출력을 내는 해시함수가 있다할 때, 출력값의 범위는 0000 0000 ~ 1111 1111 이고, 정수로 나타내면 0 ~ 255까지입니다.

그럼 만약, 어떤 값에 대한 출력값을 봤을 때, 제일 첫번째 비트가 0일 확률은 어떻게 될까요? 

답은 1/2입니다. 첫번째 비트가 0이기에 나머지 7비트로 만들 수 있는 경우의 수는 128. 따라서 전체 경우 수 255으로 나누면 128/256=1/2. 

(또는 이렇게 생각할 수도 있습니다. 해시값은 확률적으로 균등하기에, 제일 첫비트가 0 혹은 1일 확률이 균등. 따라서 50%)

확률이 1/2이라는 것은, 10번 던지면 5번정도는 첫비트가 0이 나온다는 것. 다르게 표현하면 2번 정도 던지면 한번은 0이 나오는 것.

 

이제, 첫번 째 비트와 두번째 비트 모두 0일 확률은? (즉, 연속된 2개비트가 0일 확률). 위에서 계산한 것과 같은 방법으로 생각해보면, 앞 2비트를 뺀 나머지 6비트로 만들 수 있는 경우의 수를 전체경우수로 나누는 것이기에, 2⁶/2⁸=1/2²=1/4.

연속 3비트는 2⁵/2⁸=1/2³=1/8

...

연속 k비트는 1/2^k

 

이제 비트코인에서 사용될 수 있는 실제크기를 고려해서 예를 들어보겠습니다.

비트코인에서 사용하는 해시함수는 sha256으로 256비트의 결과값을 토해냅니다. 그럼, 연속된 69개의 비트가 0일 확률은? 

답은 1/2⁶⁹. 이 얘기는 어떤 입력값이 (A + nonce)이고 nonce를 바꿔가면서 계산할 때, 2⁶⁹회 정도 돌리면 69개 연속된 0을 가진 해시값을 찾을 수 있다는 얘기. (nonce는 '논스'라고 읽으면되고, 임의로 입력하는 값을 의미. 이 값을 바꿔가면서 특정 해시값이 나오게끔 조정하는 것 )

그렇다면 2⁶⁹회 정도 해시값을 계산하려면 어느정도의 시간이 걸리는 걸까요? 

하나의 CPU가 해시값 1개를 계산해내는데 1 나노초(10^-9초) 걸린다고 하면, 한 개의 CPU로 18,718년 걸립니다.

만약 10억개(=10⁹) CPU가 사용된다면 대략 10분 정도인 590초만에 계산될 수 있습니다.

 

그렇다면, 이렇게 생각해 볼수 있습니다. "10억개의 노드가 한 개씩의 CPU를 가지고 해당 블록에 대해 '논스'를 바꿔가면서 해시값을 계산하면, 평균적으로 10분정도 안에, 어떤 노드에서 연속된 69개 비트가 0인 해시값을 찾아낼 수 있다."

한 노드가 CPU를 수십개 사용하더라도 약간의 확률적인 이득은 있겠으나 그 자신이 항상 권한을 획득할 수는 없습니다. 왜냐면 10억개 CPU와 확률경쟁을 해야하니깐요. 따라서, 전체 노드를 구성하는 CPU의 대부분을 개인이 독점하지 않는 한, 어느 한 개인이 블록생성 권한을 항상 획득할 수 없게 됩니다. 즉, 이 글의 처음에서 목적했던 바와 같이, 중앙기관이 없음에도 불구하고, 각 노드에 비교적 골고루 블록체인의 생성권한을 배분하는 목적을 달성할 수 있는 것입니다.

 

2018년 3.25일 기준으로 비트코인망에서 요구하는 연속된 0 비트수는 약73개이고, 이를 10분동안 평균적으로 246억 Giga(=2.46 x 10¹⁹) 번의 해시값이 계산되어 목표하는 값을 찾아내고 있습니다. 이렇게 찾아내는 작업을 채굴(마이닝, mining)이라 하는데, 전용 장비를 써서 계산되고 있고, 전용 장비중 하나인 Antminer S9이란 기종은 초당 14테라개의 해시값을 찾아낸다 합니다. 

이는 일반 노트북에 비해 대략 만배 이상 차이나는 것인데, 이 정도면 노드간의 CPU 계산격차가 너무 심해서, 블록생성권한의 공평성이 훼손될 수 있습니다. 그렇더라도 이 논문에서 추구하고자 하는 전체 블록의 안정성은 보장될 수 있습니다. 그러한 부분은 이 다음 논문의 뒷 부분에서 설명될 것인데, 간략히 얘기하면, 노드의 전체 CPU 파워의 50% 이상을 한 개인 혹은 단체가 독점하지만 않으면, 블록의 안정성은 보장될 수 있다 합니다. (40%정도 독점을 해도, 절반의 확률로 블록의 안정성을 깰 수 있다고도 합니다.)

 

이제 정리해보면, 이 논문에서 각 블록생성에 대한 권한은, 해당 블록에 대해 임의의 값 '논스'를 바꿔가면서 해시값을 계산했을 때, 운좋게도 요구되는 수준만큼의 연속 zero값으로 이루어진 해시값을 찾은 노드에게 주어집니다. 그 노드는 권한을 획득하고, 그 블록에 대해 계산된 해시값을 기록합니다. 

그 다음 블록에 대해서도 모든 노드가 블록생성권한을 위한 해시계산 경쟁을 하고, 누군가가 권한을 획득해서 그 해시값과 함께 블록을 생성합니다. 블록해시값을 계산할 때는, 앞 장에서 살펴봤듯이 이전 블록의 해시값을 입력값으로해서 계산하기에, 블록간에는 서로 바꿀 수 없는 순서로 체인처럼 연결됩니다. 이 체인처럼 연결된 블록이 제대로 되어 있는 지의 검증은 매우 쉽고 빠르게 이루어집니다. 이전 블록의 해시값과 해당 블록의 내용(블록생성권한을 획득했던 노드가 넣은 논스값 포함)을 입력으로 해서 해시값을 계산해봤을 때, 그 값이 블록생성자가 기록해 놓은 해시값과 비교하면 됩니다. 물론, 그 해시값은 약속된 길이만큼 0으로 채워져 있어야 합니다. 

 

이제 불순한 의도를 가진 누군가가 중간에 위치한 블록의 내용을 수정하고자 한다면, 그는 수정된 블록의 해시값을 새로 계산해야하는데(왜냐면 해시값을 그대로 놔두면, 나중에 누군가의 검증과정에서 들킬것이기에) 혼자서 연속된 73개 정도의 0비트가 되는 해시값을 찾아내는 것은 쉽지 않은 일입니다. 그 불순한 의도를 가진 이가 CPU도 꽤 많이 가지고 있어서 요행히도 자신이 수정한 블록에 대한 해시값을 발견해서 기록했다해도, 그는 그 다음 블록에 대해서도 다시 계산해서 기록하고 배포해야합니다. 왜냐면, 블록1 -> 블록2 -> 블록3 -> 블록4 로 블록체인이 되어 있을 때(이미 블록에 대한 해시값들이 계산되어 기록되어 있을 때), 불순한 이가 블록2의 내용을 바꾼다고 할 때, 블록2에 대한 해시값을 요행히 바꿨다해도, 다시 블록3에 대한 해시값을 재계산해야한다는 겁니다. 블록3의 해시값을 계산할 때 블록2의 해시값이 입력으로 들어가기 때문이죠. 마찬가지로 블록4에 대해서도 해시값을 재계산해야합니다. 이러한 작업을 10분안에 해야합니다. 왜냐면 10분마다 새로운 블록들을 누군가가 열심히 만들기때문인데, 불순한 이가 블록2을 고치고 블록2~블록4에 대한 해시값을 계산하고 있는 와중에 정상적인 노드중 누군가가 정상블록4의 해시를 기준으로 블록5에 대한 해시값을 계산해서 올리기 때문. 즉, 불순한 이는, 혼자서 전체노드와 해시경쟁을 해야하는건데, 이길 수 없는 게임인겁니다.

 

이러한 얘기가 논문에서 이어집니다. 이어지는 논문 본문입니다.

이러한 작업 증명 방법은, 다수결에 의해 결정되는 시스템에서의 대표성 문제도 해결한다. 만약 IP주소 하나당 한 표로 하는 대표성을 부여하는 경우, 다수의 IP를 보유할 수 있는 한 개인에 의해 시스템이 장악될 수 있다. 작업 증명은 CPU 한 개에 한 표이다. 다수결에 의한 결과는, 가장 많은 작업증명 노력이 투여되어야 만들어지는, 가장 긴 체인으로 표현된다. 만약 대다수의 CPU 파워가 정직한 노드들에 의해 사용된다면, 정직한 체인이 다른 경쟁 체인들을 압도하면서 가장 빠르게 성장할 것이다. 공격자가 예전 블록을 수정하기 위해서는, 수정하려는 그 블록과 그 블록 뒤에 있는 모든 블록의 작업증명을 재작업 해야만 하고, 그런 이후에 다시 정직한 노드들의 작업을 추월해야만 가능하다. 블록이 하나씩 더 추가될 때마다, 추격이 늦은 공격자가 따라잡을 확률은 기하급수적으로 낮아진다. 이 부분은 이 논문의 후반부에서 보여줄 것이다

시간이 흐름에 따른 하드웨어 속도 증가와 노드들의 참여도 증가율을 보상하기 위해서, 작업증명의 난이도는 시간당 평균 블록 생성수를 목표로 하는 이동평균값에 의해 결정된다. 블록들이 너무 빨리 생성되면, 난이도는 증가 된다.

 

"과거 블록을 변경하려면 공격자는 그 블록과 그 뒤를 잇는 모든 블록의 작업증명을 재수행해야 하고 그러면서 가장 정직한 노드들의 작업을 따라잡아 앞질러야 한다." 

블록체인에서 '블록'에 대한 '무결성'이 왜 보증되는지를 설명해주는 문구입니다. 그리고 공격자가 블록에 대한 임의의 조작을 하기가 어려운지를 수학적으로 계산해보는 것은 논문 뒷쪽에 나옵니다.

 

작업증명 난이도(difficulty)는, 블록생성을 할 수 있는 권한을 획득하기위해 풀어야하는 문제의 난이도라고 할 수 있습니다. 앞에서 봤듯이 연속된 0값을 많이 요구할 수록, 그러한 조건을 만족하는 해시값을 찾는게 어려워집니다. 

그렇다면 이런 난이도는 어떻게 결정되고 누가 결정할까요? 

 

난이도 수준은 10분마다 1개정도의 블록이 생성되도록 2주마다 결정됩니다. 즉, 2주=20,160분(14일=14 x 24시간 x 60분 =20,160분)이니깐, 10분마다 한개의 블록이 생성된다면, 2,016개의 블록이 생성될 것입니다. 따라서, 2주마다 몇 개의 블록이 생성되었는지를 카운트해서, 만약 2016개보다 많이 생성되었으면 난이도를 높이고(연속 0비트수를 더 많이 요구하고), 2016개보다 적게 생성되었다면 난이도를 낮춥니다.

 

난이도 수준의 결정은 시스템 자체적으로 됩니다. 즉, 2주마다 조정해야할 난이도를 결정하고, 결정된 난이도값은 블록의 헤더에 들어가게됩니다. 즉, 블록을 생성할 때 블록의 헤더부분에 난이도값이 들어가도록 되어 있고, 이 블록에 대한 해시값을 구할 때 그 난이도 조건에 맞게 구하게되는 것입니다.

 

이처럼, 난이도가 자동으로 조정되게 시스템을 설계함으로써, 컴퓨팅파워가 늘어나서 해시계산속도가 빨라지고, 해시값을 찾아내는 작업인 '채굴(mining)'을 하는 노드가 많아져서 평균적인 블록 생성시간이 빨라져도, 10분에 한 개정도의 블록이 생성되도록하는 메카니즘이 유지될 수 있게되는 겁니다. 기발한 아이디어입니다. 원래 목적한 메카니즘이 동작되도록, 주변 동작환경에 따라서 시스템이 스스로 보정해나가는 겁니다.!!!

 

-계속-

 

[전체 목차] 1. 서론   2. 거래(1/2)   2. 거래 (2/2) 3. 타임스탬프 서버  4. 작업 증명  5. 네트워크  6. 인센티브  7. 디스크공간 회수  8. 지불 입증 간소화  9. 금액의 결합과 분할