합의 알고리즘 종류 및 구성 - PoW

 

해당 포스팅은 "합의 알고리즘 종류 및 구성"에 대해 설명합니다.

 

* 오른쪽 목차를 통해 조금 더 가시적인 요약내용을 확인하실 수 있습니다.

* 내용에 대한 참고 자료 & 관련 자료는 맨 끝 하단에 첨부합니다. 같이 확인해보시고 좋은 내용을 공유하면 좋을 것 같아요 :)

 

# 첨부자료에 없는 그림 및 표의 경우 자체적으로 설명을 위해 제작한 것입니다 #

 

---

1. 장애 모델에 따른 합의 알고리즘

• P2P 네트워크에서는 발생 가능한 장애 모델로 다음과 같은 3가지가 존재한다.(크게 분류한 것 뿐 다양함)

1-1. 합의 알고리즘 비교표

	PoW	PoS	PBFT/Sieve	Paxos/Raft
CPU 연산 비용	높음	중간정도. PoW보다 낮지만 나름대로의 해시 계산을 수행	낮음	낮음
통신 비용	참가 서버 전체가 아닌, 로컬 통신만으로 문제가 없음. 로컬 통신은 비용이 낮음	참가 서버 전체가 아닌, 로컬 통신만으로 문제가 없음. 로컬 통신은 비용이 낮음	각 서버간 통신을 수행하기 때문에 비용은 높음	리더를 중심으로 통신하기 때문에 PBFT보다 통신 비용은 낮음. PoW, PoS와 비교하면 전체적으로 비용은 같지만 리더 1대의 통신 비용이 높아짐
참가 서버의 조건	어떤 서버도 참가 가능	어떤 서버도 참가 가능	신뢰된 서버만 참가	신뢰된 서버만 참가
비밀번호 인증	참가시 준비한 공개 암호화 키를 사용	참가시 준비한 공개 암호화 키를 사용	사전에 서로 신뢰한공개 암호화 키를 사용	특별히 없음
대응하는 장애 모델	Byzantine Fault	Byzantine Fault	Byzantine Fault	Fail-Stop Fail-Recover
다수결 대용	CPU 계산량	보유한 자산 크기	다수결	다수결(투표 형식, 랜덤 등)
권한의 분산	전기세가 낮은 지역에 집중될 가능성이 있음(ex 중국)	일반적으로 화폐 보유는 집중될 가능성이 높음	참가 서버 모두가 평등	리더에게 강한 권한이 있으나, 교체할 수 있음
결함 허용치	1대라도 남아있으면 문제 없음	1대라도 남아있으면 문제 없음	1/3 미만까지 보증(정확히 1/3인 경우 대응 불가)	1/2 미만은 문제 없음(정확히 1/2인 경우 대응 불가) PBFT보다 적은 대수로 가능

PoW, PoS, PBFT, Sieve 등의 알고리즘은 Byzantine fault 장애 모델에 대응하기 위해 고안된 알고리즘이며,
Paxos, Raft 알고리즘은 Fail-Stop, Fail-Recover 등 장애 모델에 대응하기 위해 고안된 알고리즘이다.

 

 

1-2. 합의 알고리즘 PoW(Proof of Work)

신뢰가 가지 않는 불특정 다수가 참가하는 Private한 Block Chain에 경우 PoW 알고리즘이 적합하다.
하지만 신뢰가 보장되는 참가자들 사이(컨소시엄을 만들어 운용하는 Business model)에서는 오히려 처리 속도 및 파이널리티(불변성)의 확실성 보장이 중요하기 때문에 PoW를 사용하지 않는다.

 

 

       -  PoW 알고리즘 개요

Pow(작업증명방식)을 채택하고 있는 블록체인 동작과정

Block chain 동작 개요 에서 설명했던 PoW 방식을 살펴보면서 PoW 알고리즘 동작 방식을 살펴보자. 위에 PoW을 채택하는 블록체인 동작과정을 생성 블록과 함께 조금 더 자세히 살펴보면 아래와 같다.

 

PoW 처리 절차 및 블록 생성과정

 

PoW의 처리 절차를 살펴보면 다음과 같다.

1. Wallet이 트랜잭션을 발행하고 참가자 전원에게 브로드캐스트(1번 트랜잭션 A->B)함
2. Mining Node인 Peer_1 사용자가 해시를 계산한다. 이때 블록이 블록체인에 추가됨
3. Wallet이 트랜잭션을 발행하고 참가자 전원에게 브로드캐스트(2번 트랜잭션 X->Y)함
4. Mining Node Peer_2, Peer_3이 동시에 해시를 계산하여 블록을 생성 하였고, 이때 분기(Fork)가 발생
5. Wallet이 트랜잭션을 발행하고 참가자 전원에게 브로드캐스트(3번 트랜잭션 B->W)함
6. Mining Node Peer_4가 발견하여 Peer_3이 생성한 블록 뒤에 추가함(이전 해시 값이 Peer_3의 블록 이란 의미)
   이때, Peer_4가 생성한 블록이 체인에 이어지므로 더 긴 블록체인(아래)이 올바른 것으로 됨

 

아래는 블록을 조금 더 자세히 살펴 보았을 때 구조로, 실제 이전 블록에 대한 Hash 값이 존재함.

 

 

       -  작업 증명 과정

작업 증명 PoW, 해시 계산 과정 및 논스

 

모든 블록들은 고유한 해시 값을 가진다. 해시 값을 구하기 위해서는 앞에 연결할 블록의 해시 값 이외에도 다른 정보들을 입력 값으로 가져와야 하는데, 그 중 하나가 ‘Nonce’라는 값이다.

Nonce는 다른 정보와 다르게 주어지는 값이 아닌 직접 구해야 하는 값이다. Nonce 값을 구해야만 최종적으로 해당 블록의 해시 값을 구할 수 있다. Nonce 값을 구하기 위해서는 특정 수학적 연산을 수행(‘작업증명’ 혹은 ‘채굴’을 의미)해야 하는데 복잡한 연산은 아니지만 반복적인 작업을 필요로 하는 단순 연산으로 높은 컴퓨팅 파워를 가질수록 유리하게 된다.

비트코인의 경우 평균 10분이 소요되도록 설계되어 있는데 기술 발전 등의 문제에 대응하기 위해 해시 난이도를 주기적으로 조절하고 있다.

 

 

       -  PoW 방식의 주요 노드

PoW 방식에서 주요 노드인 Mining(채굴)와, Full(풀)노드의 역할을 살펴보면 조금 더 동작 개요에 대해 이해하기 쉽다.

작업 증명이란? 주소를 참고한다.

 

 

 

       -  Fork와 고아 블록

PoW 처리 절차 및 블록 생성과정

위 그림을 다시 살펴보면 오른쪽 그림에서 Peer_2, Peer_3이 동시에 해시 값을 맞추어 블록이 생성되었다. 이때 한쪽이 블록체인으로 선택되지 않는다면 기존에 정보(거래내역, 트랜잭션)는 사라지는 것일까?

 

정상적인 거래 내역은 다행히 유지된다. 

즉 거래 내역이 취소되거나 유실되지 않고 블록체인에 포함되지 않은 거래로 취급되어 다른 블록에 포함되는 것이다.

 

실제로 블록체인은 실시간 동기가 불가능하기 때문에, 아래와 같이 서로 다른 국가에서 다음과 같은 현상이 발생한다면 이어지는 블록이 적은 쪽은 고아 블록이 되는 것이다.

 

 

       -  GHOST 계열 알고리즘

GHOST 알고리즘은 메인 체인을 선택하는 데 있어 가장 긴 체인을 선택하는 것이 아니라 가장 무거운 체인을 채택한다.
단순히 얼마나 많은 자식 블록들이 이어져 있는지 뿐만 아니라 얼마나 많은 엉클 블록(고아 블록)들을 가지고 있는지를 모두 고려하여 결정되는 메커니즘인 셈이다. 이러한 메커니즘은 채굴(mining) 후에 버려지는 블록의 개수를 줄여주는 효과를 가진다. 다만 지나친 집중 현상을 막기 위해 유효 엉클 블록 개수는 최대 7개로 한정한다.

 

조금 더 자세한 내용 참고 : [케블리] #44. 합의 알고리즘 마스터하기 - 1편 (PoW, PoS) — Steemit

 

 

       -  PoW방식의 문제점

• 파이널리티 불확실성(결제 완전성)
  더 긴 체인이 올바른 것으로 판단되어, 기존 블록이 채택되지 않을 시 이전 거래 내역이 변경되거나 사라질 수 있음(51% 공격)
• 용량의 한계 및 전력 낭비
  전체 거래 트랜잭션을 보유 하기 때문에 양이 방대함(모든 내용 확보). 뿐만 아니라 채굴에 따른 에너지 과잉 소비(전기 이용) 및 비용등

 

       -  PoW와 유사한 PoET 알고리즘

• PoW 알고리즘과 유사하지만 여기에 Security를 보장하는 알고리즘이 존재함. 이를 PoET(Proof of Elapsed Time)알고리즘 이라고 함.
• PoET(경과 시간 증명)알고리즘은 작업 증명이 TEE(신뢰할 수 있는 실행 환경)에서 무작위로 생성된 대기 시간으로 대체되는 합의 알고리즘이다.
• 안정성, 무작위성을 보증하며 리더를 랜덤으로 뽑는다. 보안 CPU명령을 통해 리더를 선출하는 방식이다.

 

------------------------------

3. 참고 자료

blockchain 이론

[케블리] #44. 합의 알고리즘 마스터하기 - 1편 (PoW, PoS) — Steemit

작업 증명이란? | Ledger

Block chain 동작 개요

PoW & PoS

작업증명, 지분증명 & 순수 지분증명: 분산화 컨센서스의 혁명

PoW와 PoS의 문제점

분산 시스템의 내결함성을 높이는 뗏목 합의 알고리즘(Raft Consensus Algorithm)과 정족수(Quorum) 개념 알아보기

What is etcd?