Proof of Work

비트코인의 컨센서스 알고리즘

Proof-of-Work는 비트코인에서 사용되는 컨센서스 알고리즘이다. 즉, 비트코인에 참여하는 참여자들이 중앙의 관리없이 합의점에 이를 수 있도록 하는 프로토콜이다.

설명의 편의성을 위해서 가장 직관적으로 생각할 수 있는 알고리즘에서부터 시작한다. 바로 PoW에 대한 내용을 확인하려면 오른쪽의 옆의 CONTENTS를 이용하자.

Where problem begins?

비트코인에서 합의에 문제가 생기는 시점은 언제인가?

블록체인 네트워크가 시작되었다. 참여자들은 각자 블록을 새로 생성해서 데이터를 적어서 네트워크에 퍼트리는 것으로 네트워크에 참여한다.

이 네트워크에서 규칙은 '가장 긴 체인이 유효한 체인' 이라는 것뿐이다.

Let's begin our network

가장 먼저 A가 블록을 생성하고 네트워크의 참여자에게 퍼트린다. 여기서 주의해야 할 것은 퍼트리는 과정은 시간이 소요되는 과정이라는 것이다. 예시는 참여자가 3명밖에 안되기 때문에 거의 동시에 새로 생성된 블록을 받을 수 있겠지만 실제 네트워크에서 그렇지 않다.

다음 블록은 B가 생성하여 네트워크에 퍼트린다.

B가 추가한 블록을 모두 로컬에 저장한 후에 A와 C가 새로 블록을 추가하고 네트워크에 전파한다.

이와 같이 동시에 블록이 생기면 블록체인의 분기가 생겨 더 이상 블록 체인이 아닌 블록 트리가 된다. 이 상태에서 두 체인의 길이가 같으므로 참여자들은 어떤 체인이 유효한 체인인지 합의점에 다다를 수 없다.

Here's the challenge

합의에 문제가 생기는 지점은 블록이 동시에 생성되어 분기를 만들 때이다. 이렇게 분기가 만들어졌을 때 다시 합의를 이루는 과정을 가장 직관적인 알고리즘부터 살펴보자.

#1 Very Simple Algorithm

Rule

랜덤하게 분기를 선택하여 해당 분기를 이어 나간다.

B가 새로운 블록을 추가하려고한다. B는 두 분기 중 오른쪽 체인을 선택하여 체인을 이어 나간다.

B가 새로 추가한 블럭이 네트워크 참여자에게 퍼진 후에 다시 네트워크 참여자들은 오른쪽 분기가 유효한 체인임을 합의할 수 있게 되었다.

문제점

이 알고리즘을 사용했을 때 문제점도 역시 간단하다. 만약 동시에 블록을 생성하는 일이 계속 발생한다면 어떻게 될까? 분기의 분기의 분기의 분기가 생기게되면서 하나의 합의점으로 도달하는게 점점 어려워질 것이다.

#2 Random Backoff Algorithm

분기가 생기는 이유는 새로운 블록이 네트워크로 퍼져서 합의가 일어나기 전에 새로운 블록이 추가되는 것이다. 이를 방지하기 위해서 랜덤한 타이머를 도입하여 타이머가 끝난 후에 새로운 블록을 추가하도록 한다.

이 방법은 네트워크의 collision 방지를 위해 사용되는 backoff 알고리즘과 유사해서 이름을 차용하였다. https://www.geeksforgeeks.org/back-off-algorithm-csmacd/

Rule

새로운 블록이 추가되면 랜덤한 타이머를 가동시킨다.
타이머가 종료되면 블록을 추가한다.
#1의 규칙을 따른다.

먼저, A가 블록을 추가하고 타이머가 시작된다. 새로운 블록을 받은 B, C도 각각 타이머를 시작한다.

C의 타이머가 가장 먼저 완료되고, C는 블록을 추가하고 네트워크에 퍼트린다.

다시 Timer가 설정되고 이 과정이 반복된다.

Achieve

랜덤한 타이머를 설정하기 때문에 짧은 시간안에 두 참여자가 새로운 블록을 네트워크에 추가할 확률이 낮다. 우연히 동시에 블록이 추가될 경우도 있지만 낮을 확률로 일어나기 때문에 다음 블록을 통해 유효한 체인을 합의할 수 있다.

문제점

비트코인은 네트워크 활성화를 위해서 블록을 추가한 참여자에게 보상을 제공하는 시스템을 가지고 있다. 누구나 참여할 수 있는 공공 네트워크인 비트코인에서 랜덤한 Timer를 준수하지 않는 악의적인 참여자는 무조건 있을 수밖에 없다. 이 알고리즘을 이용하기 위해서는 참여자간의 신뢰가 있어야하는데 비트코인 네트워크는 그렇지 않다.

#3 Cheat Resistant Timer

#2 방법은 타이머를 준수하지 않는 악의적인 참여자가 문제가 된다. 그렇다면 사기 칠 수 없는 타이머를 도입한다면 위의 문제를 해결할 수 있다. 어려운 문제를 출제하고 문제를 풀어야만 타이머가 완료된다.

Rule

새로운 블록이 추가되면 해당 블록과 연관된 문제가 출제된다.
문제의 답을 찾으면 새로운 블록과 답을 네트워크에 퍼트린다.
블록을 전달받으면 답이 맞는지 확인하고 체인에 블록을 추가한다.

A가 첫 블록을 추가하고 이 블록과 관련된 문제가 출제된다.

A가 문제를 가장 먼저 풀고 네트워크에 블록을 추가한다. 이때, 발견한 답을 포함해서 전파한다.

나머지 참여자들은 A가 보낸 정답을 대입해봄으로써 검증한다. 이후 다시 문제가 출제되면서 블록체인이 형성된다.

Achieve

타이머를 문제 푸는 것으로 대체하여 의도적으로 타이머를 조작할 수 없어졌다.

문제점

위의 알고리즘이 제대로 동작하기 위해서는 출제하는 문제를 잘 설정하여야 한다. 참여자가 많아지면 문제를 푸는 시간이 점점 단축된다는 것도 문제이다.

#4 Proof-of-Work

드디어 비트코인에서 사용하는 컨센서스 알고리즘인 proof-of-work(PoW)를 소개한다. 기본적으로 #3과 같고 암호화 해시 함수를 통해 문제를 출제한다.

Rule

새로운 블록이 추가되면 해당 블록과 연관된 암호학 문제가 출제된다.
문제의 답을 찾으면 새로운 블록과 답을 네트워크에 퍼트린다.
새로운 블록이 너무 빠르게 추가되면 암호학 문제의 난이도를 증가시킨다.
블록을 전달받으면 답이 맞는지 확인하고 체인에 블록을 추가한다.

Math problem

PoW에서 사용하는 수학 문제는 cryptographic hash function(암호화 해시 함수)을 사용한다. 답을 구하기는 무지막지하게 어렵지만 답을 검증하기는 매우 쉬운 특징과 입력값이 조금 변해도 출력되는 해시값은 완전히 달라진다는 특징이 있는 함수이다.

PoW는 다음 문제를 출제한다.

이전 블록의 해시값을 Prev Hash, 사용하는 암호화 해시 함수를 SHA256이라고 할때, SHA256(Prev Hash + Nonce)의 최상위 difficulty개의 비트가 0이되는 Nonce를 구하여라.

Achieve

Cryptography를 사용한 문제를 사용하면 문제를 푸는 방법은 무작위 Nonce를 대입해보는 방식 밖에 없다. 따라서 연산 능력에 비례해서 새로운 블록을 추가할 수 있는 확률을 얻게된다. 또, 위의 difficulty(난이도)를 조절함으로써 더 많은 노드가 네트워크에 참여하더라도 문제를 푸는 시간을 유지할 수 있다.