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

# Proof of Work

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

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

## Where problem begins?

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

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

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

### Let's begin our network

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

<div align="center"><img src="https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpLRkq17WBfxvOkARX%2Fimage.png?alt=media&#x26;token=685df65c-db13-41c5-bdce-ccb0da9280c3" alt="1. &#x27;A&#x27; add block and broadcasting"></div>

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

![2. 'B' do the same thing](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpOS0TGTkbDBLUC7e6%2Fimage.png?alt=media\&token=76004f02-20a6-419d-ac99-e61794baaadb)

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

![3. Both 'A' and 'C' add block and broadcast it](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpPb2PYPFIJMi6X5zG%2Fimage.png?alt=media\&token=017d3955-821b-4c87-aa7c-13eafd040b0d)

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

### Here's the challenge

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

## #1 Very Simple Algorithm

### Rule

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

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

![1. 'B' adds another block to randomly picked branch](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpSxmDMgPMfH2xgQiY%2Fimage.png?alt=media\&token=c5cfde8a-89a3-47db-8f5d-b835e9e37165)

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

### 문제점

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

![2. Totally messed up](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpXus1drJJvFEe9hgp%2Fimage.png?alt=media\&token=2909e6f8-7793-45ad-9621-645af689af73)

## #2 Random Backoff Algorithm

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

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

### Rule

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

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

![1. Add frist block and start timer](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpbdOtlLFk0bnVHi9M%2Fimage.png?alt=media\&token=42cf5709-5259-4ae1-85b3-fc8e90ba9b1e)

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

![2. 'C' got opportunity to add block](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXplTi_suW0ifaKkFCp%2Fimage.png?alt=media\&token=bebe59df-ecc3-4252-a20c-fb9c30751ea3)

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

![3. Timer reset](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpl_dYBAbuMJfhZd2V%2Fimage.png?alt=media\&token=c5cd3ac2-7a15-4773-9611-923591775a2b)

### Achieve

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

### 문제점

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

## #3 Cheat Resistant Timer

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

### Rule

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

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

![1. problem](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXplrk0aUEB_w-BIWN8%2Fimage.png?alt=media\&token=ce2aa99f-766d-45e0-bddf-61a967320028)

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

![2. 'A' wins prize](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpmj1-YfOcTf318cB3%2Fimage.png?alt=media\&token=369e6ae2-32a0-4522-947e-3692e26cdc0a)

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

![3. Verification](https://3215684330-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MXVpYCI3pMrks1sJ24r%2F-MXp9fwfVHa3PIGgKP4L%2F-MXpmfiwKvYGgQryJg6f%2Fimage.png?alt=media\&token=c1063103-2cc3-4c04-8e07-d05214c6ab9b)

### Achieve

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

### 문제점

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

## #4 Proof-of-Work

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

### Rule

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

### Math problem

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

PoW는 다음 문제를 출제한다.&#x20;

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

### Achieve

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

## PoW의 단점&#x20;

PoW는 합의를 도출하는 목적을 달성했음은 분명하지만, 다른 측면에서 살펴보면 단점도 있다.&#x20;

### 비효율성

어려운 문제를 풀기 위해서 사용되는 어마어마한 자원이 소요된다. 블록을 생성하는 것에 많은 에너지가 소요된다.

### 느린 처리속도&#x20;

거래가 발생하고 해당 거래가 네트워크에 적히려면 새로운 블록이 만들어져야 한다. 블록은 약 10분의 한 개씩 생성되는데 이는 즉각 거래가 완료되는 기존 방식과 비교하면 매우 느리다.&#x20;





참고: \
[http://www.distributedsystemscourse.com/](http://www.distributedsystemscourse.com/)



Last update: 04/09/0201
