[Blockchain] 합의 알고리즘

yooni·2022년 3월 3일

DPoS PoS blockchain pow 비잔틴장애허용 합의알고리즘

Blockchain

목록 보기

8/36

👥 합의 알고리즘 (Consensus Algorithm)

다수의 참여자들이 통일된 의사결정을 하기 위해 사용하는 알고리즘
(합의 모델, 합의 방식, 합의 매커니즘, 합의 프로토콜)

블록체인 시스템에는 의사결정을 내릴 권위있는 중앙화 서버가 존재하지 않고, 전 세계에 흩어진 수많은 노드에 데이터가 보관된다. 각 노드들은 블록에 기록하는 데이터가 위변조되지 않은 원본이라는 것을 상호간 합의하는 과정이 필요하다. 누군가 악의적으로 데이터를 조작하여 전파하려고 해도 다수의 노드들이 상호검증을 거쳐 올바른 블록 생성을 할 수 있게 하는 프로세스가 합의(Consensus)이다.

1. 작업 증명 (PoW, Proof of Work)

비트코인의 창시자 사토시 나카모토가 제안한 합의 알고리즘. 컴퓨터의 연산력을 바탕으로 합의에 도달하고 그 연산력이 빠를수록 블록에 기록할 수 있는 권한이 더 많이 부여된다. 비트코인, 라이트코인, 비트코인 캐시 등 현재 시장가치가 높은 주류 코인들이 채택하고 있다. 강력한 보안성을 제공하며, 시빌 공격(Sybil Attack)을 막을 수 있다고 증명된 유일한 알고리즘이다. 블록체인의 취약점인 51% 공격을 쉽게 방여할 수 있다. 또한 서비스 남용을 쉽게 방지할 수 있다.

채굴(Mining)에 사용되는 컴퓨팅 파워로 경쟁을 하며, 체인이 갈라지는 포킹(Forking)이 발생되더라도 가장 긴 블록체인이 남을 때까지 경쟁하여 이긴 브랜치가 채택된다. 채굴 과정에서 어마어마한 전력이 소비되며, 지속적인 해시 파워를 유지해야 한다. 이러한 문제로 일부 국가에서는 채굴 작업에 대한 단속을 실시하기도 한다. 또한 채굴에 성공한 하나의 노드를 제외한 나머지 노드들의 에너지 자원은 그대로 낭비된다는 단점이 있다. 특정 마이닝 세력의 해시 독점으로 인한 생태계 교란 우려가 있다.

👻 고스트 프로토콜 (Ghost Protocol)
메인 체인을 선택하는 데 있어 가장 긴 체인을 선택하는 알고리즘. 비트코인을 위해 나온 알고리즘이다. 비트코인은 블록 생성 시간이 약 10분으로 매우 느려 stale 블록이 생성 확률이 매우 낮다. 따라서 stale 블록이 발생하면 가장 긴 블록을 메인 블록체인에 연결하고 나머지 stale 블록은 버린다. 이더리움의 경우 블록 생성 시간이 약 12초로 훨씬 빠르지만 그만큼 stale 블록이 생성될 확률이 높아 안정성이 떨어진다. 이를 보완하기 위해 이더리움은 수정된 Ghost Protocol을 적용한다.

작업 증명 방식은 채굴시 모든 것을 처음부터 계산하다 보니 블록체인의 속도가 느리다. 또한 이 방식은 노드의 51%가 정당하다고 인정해야 블록이 생성되는데, 거대 자본의 담합으로 연산 능력의 51%를 장악하여 채굴권이 집중되는 문제가 발생할 수 있다. 이는 탈중앙으로부터 멀어지는 것이며 이로 인해 거대 단합 조직이 엉뚱한 블록을 생성하고 조작할 수도 있다.

❗️ "채굴 노드가 하는 일은, 목표값 이하의 블록해시를 생성하는 논스를 찾아 새로운 블록을 생성하는 것이다."

작업 증명에서 연산을 한다는 것은, 반복적인 과정을 통해 무작위로 일정한 조건보다 낮은 값(Nonce)을 찾아내는 것이다. 수없이 많은 연산을 반복해서 미리 정해진 목표값 이하의 해시값이 나오도록 해야 하는데, 이 때 랜덤한 해시값을 생성할 수 있도록 매번 사용하는 임시값이 논스이다. 논스를 찾는 것은 수학적인 유추로는 불가능하다. 논스에 값을 하나씩 대입해가며 찾아야 한다. 논스 값이 달라짐에 따라 해시 연산 결과로 생성되는 블록 해시값도 다양하게 나올 수 있다. 논스값을 찾아내기 위해 비트코인에서는 SHA-256 방식을 이용한다.

N: 논스(Nonce), P_hash: 이전 블록의 해시, Tx: 블록의 트랜잭션, Target: 네트워크 목표 난이도 일 때,

H(N || P_hash || Tx || Tx || ...Tx) < Target 를 만족하는 N을 찾아야 한다.

2. 지분 증명 (PoS, Proof of Stake)

PoS는 PoW에 비해 더 쉬운 방식으로 전반적으로 PoW의 단점을 보완한다. 더 많은 노드들이 참여할수 있고, 더욱 분산화가 이루어진 합의 방식이다.

작업 증명은 채굴에 필요한 컴퓨터만 있으면 참여할 수 있는 반면, PoS는 지분(코인)을 많이 가지고 있는 노드에게 블록을 생성할 권한을 주는 방식이다. 지분이 많을수록 블록에 기록할 권한도 그에 비례하여 더 많이 부여된다. 주주총회에서 주식 지분율에 비례하여 의사결정 권한을 주는 것과 유사하다. 오랜 기간 코인을 보유해야 한다는 조건 때문에 PoW 방식에 비해 다른 코인으로의 이탈 가능성이 적다.

이 방식에서는 채굴자가 존재하지 않고 검증자(Validator)가 존재한다. 얼마의 지분을 스테이킹(staking)했느냐에 따라 검증자가 선택되며, 더 많은 지분을 보유하고 있을수록 검증자로 선택될 확률이 높다. 검증자는 블록을 생성한 후 자신이 원하는 체인에 블록을 연결하여 그에 대한 보상을 받는다. PoS는 자신이 스테이킹한 코인에 대해 이자를 받는 방식이라고 할 수 있다.

블록 생성자가 직접 암호화폐에 투자하게 하기 때문에 블록 생성자와 지분 생성자의 이해관계를 일치시킬 수 있어 나쁜 의도로 블록을 생성할 동기를 없앨 수 있다. PoW에 비해 인센티브에 대한 동조와 지지가 강하다. 악의적으로 잘못된 블럭을 생성할 경우에는 모든 자산을 0으로 만드는 패널티를 부과한다.

무의미하게 논스를 찾아내기 위한 채굴 경쟁이 없어 해시파워가 많이 필요하지 않아 PoW 방식 보다 에너지 소모가 적어 경제적이며 친환경적이다. 또한 블록 처리 시간이 획기적으로 줄어든다. 코인을 가진 누구나 허가없이 참여할 수 있기 때문에 소수 채굴 풀의 중앙집중화를 해결하여 블록 생산자의 탈중앙화, 분산화**가 더 잘 이루어진다. 블록 생성을 위해 지분을 담보로 잡아야 하므로 Dumping을 방지할 수 있다.

하지만 아직 보안성이 검증되지 않았으며, 지분이 많은 소수의 거대 권력이 독점할 가능성이 있다. PoS의 가장 큰 문제는 'Nothing at stake(전혀 위험하지 않은)' 문제이다.

🤷‍ Nothing at Stake
모든 노드들이 제한없이 여러 블록에 자신의 지분을 증명할 수 있기 때문에 발생하는 문제이다. 자산 증명을 하는데 있어 한계 비용이 전혀 없다는 것이다. 블럭체인에 포크가 발생하여 노드가 투표를 할 때 두 블럭체인에 모두 투표를 할 수 있고 이 때 노드는 손해보는 것이 전혀 없음을 뜻한다. 블록의 정당성 여부와 상관 없이 양쪽 모두에 자신의 지분을 증명해야 어느 것이 참이 되든 보상을 받을 수 있기 때문이다. 이로 인해 포크 문제를 해결하기 어려워진다.
이더리움에서는 이 문제를 해결하기 위해 보증금을 걸게 한다. 검증자가 투표한 블록이 거짓임이 드러나면 보증금을 차감하는 'Something at State' 방식이다.

퀀텀, 스트라트, 엔엑스티, 아더코인 등이 지분 증명을 채택중이며, 이더리움은 작업 증명 방식에서 지분 증명 방식으로 합의 알고리즘을 변경하려고 추진중이다. 현재 개발되고 있는 블록체인은 대체로 지분 증명 방식을 선택하고 있는 추세이다.

3. 위임 지분 증명 (DPoS, Delegated Proof of Stake)

PoS 방식이 변형된 것으로, 네트워크 상의 지분을 가진 모든 노드들이 자신의 지분율에 비례한 투표권을 행사하여 상위 노드(증인, Witness)를 선출하고 트랜잭션 유효성 검사에 대한 권한을 위임한다. 일정 수의 증인들은 모든 권한을 위임받아 블럭 생성을 담당하는 검증자가 된다. 블록 생성을 확정하기 위해서는 2/3 이상의 승인이 필요하다. 국회의원을 뽑아 국회를 구성하는 민주주의 제도와 유사하다. EOS, Steem, Tezos, ARK, RISK에서 채택하고 있다.

DPoS는 합의 참여 노드 수가 한정되어 있어 PoS에 비해 매우 빠른 성능과 확장성을 갖고 있고 비용 및 수수료가 낮다. 하드포크의 위험이 낮으며, 증인들이 투표에 참여할 인센티브가 분명하다. 하지만 DPoS는 완전한 탈중앙화를 이루지 못했다는 비판을 받기도 한다. 증인끼리 손쉽게 담합할 수 있고, 공개된 소수의 증인에 대한 디도스(DDos) 공격 위험도 있다. 또한 대표자를 선출하면 대표자에 대한 정보를 밝혀야 하기 때문에 익명성이 떵러져 외부 공격에 취약할 수 있다. 네트워크가 커질 수록 대표자의 수 역시 늘어나야 하는데 이는 역으로 위임증명이 가진 빠른 속도라는 장점이 줄어들게 한다. 또한 참여를 통한 보상이 소유한 코인을 기준으로 하기 때문에 빈익빈 부익부 현상이 생길 수 있다.

4. 비잔틴 장애 허용 (Byzantine Fault Tolerance)

장애가 있더라도 전체의 1/3을 넘지 않는다면, 시스템이 정상 작동하도록 허용하는 합의 알고리즘. 분산원장 체계에서는 악의적인 노드가 데이터를 조적하려고 하더라도 모두가 지닌 원장이 같은 내용을 유지할 수 있는 방법이 존재해야 하며, 이를 위한 것이 비잔틴 장애 허용 알고리즘이다.

5. 권한 증명 (PoA, Proof of Authroty)

권한 증명(PoA)은 보통 프라이빗 블록체인을 위한 증명 방식이다. 확실한 신원에 기반한 합의 방식을 통해 즉각적인 거래를 제공할 수 있다. 채굴이 필요없어 다른 합의 알고리즘보다 속도가 빠르고 확장성이 높다. 탈중앙화와 익명성을 어느 정도 포기하는 대신 여러 이해관계자의 협업을 효과적으로 지원할 수 있다. 모든 거래와 블록은 채굴자를 대체하는 검증인(Validator)들이 처리한다. 각 PoA 네트워크는 검증인을 정하는 원칙이 있다.

PoA 노드 참가자들은 거래 검증의 보증인 역할을 한다. 신원이 이미 공개된 노드 소유자의 명성을 기반으로 거래 내역 조작을 방지한다. 따라서 PoA 방식에서는 노드의 명성이 결정적인 역할을 하며 검증인들의 명성 그 자체가 가치이자 기본이다.

최근 기업들이 운영하는 블록체인에 많이 투입되고 있으며 월마트, GE Avigation 에서 공급망 추적을 위해 PoA 알고리즘을 사용하고 있다. 카카오 자회사 그라운드X의 클레이튼도 PoA에 기반하고 있다.

Klaytn IBFT(Istanbul Byzantine Fault Tolerance)

PBFT(Practical Byzantine Fault Tolerance)의 변형된 버전의 합의 알고리즘을 사용하며 권한증명(PoA) 방식을 기반으로 한다. 역할에 따라 세 가지의 노드로 구성되어 있다.

컨센서스 노드 (CN)
네트워크에서 블록 생성을 담당한다. Core Cell Network에 의해 합의된다.
프록시 노드 (PN)
네트워크의 인터페이스 역할을 담당한다. 트랜잭션 요청을 CN으로 전송하고 블록을 EN로 전파한다.
엔드포인트 노드 (EN)
RPC API 요청을 처리하고, 서비스 체인과 주고받는 데이터를 처리한다.

6. 합의 알고리즘의 2가지 속성

어떤 합의 알고리즘이 네트워크에서 통용되기 위해서는 아래 두 가지 특성을 가지고 있어야 한다.

Safety (시스템에 나쁜 일이 발생하지 않는다.)
정상적인 참여자는 같은 상태에 동의해야 하고 그 상태는 유효해야 한다. 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안된다. 즉, 문제 없는 노드는 잘못된 합의를 하지 않는다.
Liveness (시스템은 항상 살아있어야 한다.)
모든 참여자는 결국에는 어떤 상태에 동의해야 한다. 문제 없는 노드는 반드시 합의를 한다.

FLP Impossibility (FLP Theorem)

Fail-Stop-Failure가 하나만 있어도 Safety와 Liveness를 둘 다 만족하는 합의 알고리즘은 존재할 수 없다. 비동기 네트워크 내에서는 Safety와 Liveness를 둘 다 만족시킬 수 없다는 것이다. 즉 비동기 네트워크 내에서는 합의 문제를 완벽하게 해결할 수 있는 분산 알고리즘이 존재하지 않는다. 블록체인 구동 네트워크 역시 비동기 네트워크이므로 블록체인 시스템의 완벽한 합의 알고리즘은 존재하지 않는다. 따라서 합의 알고리즘을 선택한다는 것은 Safety와 Liveness 중 무엇을 선택하고 무엇을 포기할지에 대한 문제이다.

Fail-Stop-Failure
전통적 분산 시스템에서는 여러 노드들이 메시지를 주고받으며 상태를 변화시킨다. 이 때 모든 노드가 정상적인 경우만 가정할 수는 없다. 시스템이 감당할 수 있는 에러의 종류를 시스템의 Failure Model이라고 부르며 총 6 계층으로 분류된다. Fail-Stop-Failure에서는 문제가 발생한 노드는 더이상 상태가 변하지 않지만, 문제가 발생하기 이전의 상태를 돌려준다.