PBFT Consensus Algorithm
합의 알고리즘
합의 알고리즘이란, 즉 몇 개의 노드로 이루어진 네트워크가 있을 때, 이들을 합의에 이르게 할 수 있는 알고리즘을 말한다. 이는 블록체인이 세상에 등장하기 전부터도 분산 컴퓨팅 시스템에 대해 연구되었던 주제이지만, 블록체인이라는 개념의 등장과 함께 새로운 국면을 맞이하기 시작한다.
실제로 블록체인 또한 잘 정의된 연산을 실행한 결과가 무엇인지에 대한 의견을 모으는 과정의 반복이다. 의견을 제출하는 모든 컴퓨터(노드)가 충분히 빠른 시간 안에 올바른 결과를 내는 것이 이상적이지만, 현실에서는 그렇지 않기 때문에 합의 프로토콜이 필요하다. 프로토콜을 평가하는 기준은 크게 다음 두 가지가 있을 것이다.
- Liveness: 얼마나 빠르게 합의를 진행할 수 있는지
- Safety: 네트워크 문제, 노드의 잘못된 응답 등에 얼마나 견고한지
일반적으로는 둘 중 하나를 얻기 위해서는 나머지 하나를 포기해야 한다고 생각되었다. 하지만 나카모토 사토시는 이를 창의적으로 해결하며, 심지어 이 방법으로 전 세계의 누구나 동시에 참여할 수 있는 시스템인 비트코인을 만들게 된다. 비트코인의 작업증명 (Proof of Work; PoW) 합의 방식에서는 가장 많은 계산력 (computational power)가 사용된 장부를 신뢰한다는 단순한 규칙으로, “설마 잘못된 주체 하나가 전 세계의 계산력의 과반을 차지할 리 없다”는 전제 하에 합의를 이루게 된다. 이는 발명 당시에는 굉장히 획기적이었으나, 현재에는 과도한 계산력 낭비로 발생하는 문제들로 인해 다른 합의 방식으로 전환하려 하는 추세이다.
그래서 최근의 블록체인들은 채굴자 없이 검증자 (validator)들에 의해 블록이 만들어지는 방식들을 사용한다. 대표적인 방식이 자신이 가진 암호화폐의 지분에 따라 블록을 생성할 권한을 얻게 되는 지분 증명 (Proof of Stake; PoS) 방식이다. Solana, Polygon Avalanche PoS 방식을 사용했고, 최근에는 이더리움도 PoS 방식으로 완전히 전환할 준비를 진행하고 있다.
지분 증명 방식에서 중요한 요소들은, 먼저 어떤 사람이 검증자가 될 수 있는가, 그리고 검증자들이 어떤 방법으로 올바르게 합의에 이르게 할 수 있는가일 것이다. 우리는 지금은 전자는 제쳐두고 후자에 집중해보자. 이를 해결하는 방법들을 합의 프로토콜 또는 합의 알고리즘이라고 한다. 대표적인 합의 알고리즘은 PBFT (Practical Byzantine Fault Tolerence) 알고리즘이다. 대부분의 지분 증명 블록체인은 PBFT를 기반으로 한 알고리즘을 채택하고 있다.
BFT와 PBFT
BFT (Byzantine Fault Tolerance)는 합의 알고리즘 중 하나이다. BFT의 목표는, 네트워크를 이루는 노드들 중 몇 개가 실수로, 혹은 악의적으로 올바르지 않은 응답을 할 때에도 올바르게 합의에 이르게 하는 방법을 총칭한다.
비잔틴 장군 문제
이는 다소 비유적인 비잔틴 장군 문제 에서 시작한다.
A국의 장수들이 어떠한 결정을 위한 의견을 모은다. 모든 장수들이 올바른 의견을 말하면 제일 좋겠지만, 이들 중 틀린 판단을 하는 장군이나, 심지어는 배신자가 있을 수 있다. 다르게 생각하는 장군들의 의견을 모두 바꾸어 만장일치로 의견을 모으기는 현실적으로 불가능하고, 한 명이 독단적으로 의사결정을 하는 것도 위험하다.
여기서 장군들이 모두 서로 다른 위치에 있어서 편지로만 의견을 전달할 수 있다면? 이 때에는 문제가 훨씬 더 복잡해진다. 어떤 한 명을 완전히 신뢰하는 것은 위험하고, 너무 안전하게 진행하려 하면 의사결정을 할 수 없다. PBFT는 다음과 같은 성질을 만족하는 프로토콜을 제공한다.
- 전체 장군이 $3N+1$명 이상이라면, $N$명의 장군들이 잘못된 결정을 하더라도 ($2N+1$명의 장군만 올바른 결정을 한다면) 안전한 의사 결정을 할 수 있다.
이와 같은 성질 때문에, PBFT를 도입한 네트워크들의 검증자 수는 보통 $3N+1$ 꼴이다.
PBFT의 합의 과정
위 문제에서 비유를 걷어내고 컴퓨터 노드들 사이의 통신으로 생각해 보자. 완전히 동일한 노드들 $3N+1$개가 있다. 각 노드들을 $1, 2, \cdots, 3N+1$ 번 노드로 번호 붙이고, 1번 노드를 Primary node, 다른 노드들을 Backup node라고 부르자. ‘어떤 트랜잭션들을 처리해 주세요’, i.e. ‘블록을 생성해 주세요’라는 요청이 들어오면, 각 노드들은 트랜잭션들을 처리한 결과를 계산하고 그 결과 상태에 대한 합의를 이룰 것이다. 이 과정은 아래 단계들로 구성된다.
-
Request : 요청자 (client) 가 Primary node에게 ‘이 블록 생성해 주세요’ 요청을 보낸다. (사실 요청자는 모든 노드에게 요청을 보낸다)
-
Proposal message : Primary node가 1차적으로 요청을 검증하고, backup node들에게 ‘이 블록 생성해 달래요’ 요청을 각 노드들에게 전파한다.
-
Prepare message : 각 노드들이 Proposal message를 검증하고, ‘이 블록 생성해 달라던데 전 괜찮은 거 같아요’ 메시지를 각 노드들에게 전파한다.
-
Commit message : 각 노드들은 $2N+1$명 (본인 포함) 이상에게 prepare message를 받으면 ‘다들 괜찮으신 것 같네요~ 처리하겠습니다!’ 메시지를 각 노드들과 요청자에게 전파한다.
-
각 노드들은 $N+1$명 이상에게 commit message를 받으면 요청이 처리된 것으로 이해한다. 요청자 또한 $N+1$명 이상에게 commit message를 받으면 요청이 처리된 것으로 이해한다.
$2N+1$개 이상의 노드가 올바른 노드라면 비둘기집의 원리에 의해 $N+1$개의 commit message들 중 최소 하나는 올바른 메시지, 즉 다른 $2N+1$개 이상의 노드가 합의한 메시지임이 보장이 된다. 위 과정들 중 하나의 과정이라도 생략되면 단일 노드의 공격에 의해 네트워크가 취약해질 수 있는 가능성이 존재한다.
만약..
노드가 실패할 수도 있다. Primary 노드가 아닌 노드가 검증에 실패할 경우에는, 큰 문제가 되지 않는다. $N$개 이하의 노드가 실패할 때에는 네트워크는 완전히 올바르게 작동한다.
만약 Primary 노드가 실패한다면? PBFT의 제안자들은 이 경우를 해결할 수 있는 View Change Protocol을 제안하였다.
- Backup 노드가 client에게 메세지를 받으면 타이머를 시작한다.
- 타이머가 끝난 뒤, Primary 노드가 Backup 노드에게 Proposal message를 보내지 않았다면, ‘Primary 노드를 바꿉시다!’라는 요청을 (client 없이 스스로) 보낸다. 다음 Primary 노드가 누가 되어야 하는지는 프로토콜에 의해 미리 결정되어 있다.
- ‘새로운 Primary 노드가 될 노드’가 이 메시지를 $2N+1$개 (본인 포함) 받으면, 이 노드는 자신이 Primary 노드인 것처럼 ‘Primary 노드를 바꾸는 Proposal message’를 만든다.
- 이후 PBFT의 합의 과정을 거쳐 Primary 노드가 바뀐다.
이 과정을 거쳐 PBFT의 view가 바뀌고, primary 노드가 죽었음에도 불구하고 새로운 primary 노드로 liveness를 이어갈 수 있게 된다. 기존에 node들이 합의한 정보는 새로운 view에서도 여전히 유효하다.
PBFT를 왜 쓰나요?
장점
PoW로 생성된 블록의 finality는 확률적으로 보장되므로, 트랜잭션이 충분히 높은 확률로 finalize되었다는 확신을 얻기 위해서 몇 개의 블록을 기다려야 한다. 그러나, validator들이 합의한 블록은 finality가 즉시 보장되기 때문에 한 번 확정된 블록은 절대 변경되지 않는다. 이는 블록체인을 이용한 응용 서비스를 만들 때 UX에 있어서 큰 차이를 만들게 된다.
PoW 방식과 비교해서는, 에너지 소비도 획기적으로 절감되었을 뿐 아니라, PoW 방식에서는 확률적으로 결정되는 miner가 모든 보상을 독식했으나 PBFT에서는 모든 노드가 보상을 받을 수 있다는 장점이 있다. 블록 생성을 멈추는 데에는 $3N+1$개의 노드들 가운데 $N$개만 공격해도 충분하지만, 가짜 블록을 생성하거나 트랜잭션을 검열하는 등의 작업은 $2N+1$개를 공격해야 할 수 있다.
단점
모든 노드들이 서로를 알고 있어야 하며, 모든 노드들로 메시지를 전파하는 연산이 여러 번 이루어진다. 총 연산 횟수가 노드의 개수의 제곱에 비례한다. Network load 또한 노드가 많아질수록 커지기 때문에 합의 노드의 개수를 쉽게 늘이기 힘들다.
PBFT를 어디서 쓰나요?
PBFT는 합의에만 국한된 알고리즘이다. 자체로는 어떤 노드들에게 합의할 권한을 줄 것인지, 잘못된 노드들을 처벌하는 제도 등이 정의되어 있지 않기 때문에, 이를 해결할 수 있는 다른 개념들과 함께 버무려 쓰는 경우가 많다.
Tendermint Protocol
Tendermint 프로토콜은 PBFT를 위임 PoS (DPoS)에 버무린 합의 알고리즘이다. 일정량 이상의 암호화폐를 네트워크에 lock해 두어야만 합의에 참여할 수 있고, 빨라도 합의가 종료된 이후에야 암호화폐를 unlock할 수 있게 해서 중복 투표 문제를 해결하였다. 또한, 악의적으로 잘못된 응답을 할 경우, lock한 지분을 빼앗는 처벌 또한 추가했다.
Solana
Solana는 아주 새로운 합의 방식을 들고 나온 현대적인 블록체인들 중 하나이다. Solana의 합의 방식은 메시지를 주고 받는 시간 지연을 줄이고 liveness를 더욱 높이기 위해 PBFT를 개량해 Tower BFT라 이름붙여졌다. Solana는 PoH라고 불리는 “블록체인 안의 자체적인 시계”를 탑재하고 있기 때문에 이를 이용한다.
Solana block의 finality는 ‘시간 제한 아래에서’ 보장된다. 즉, 예를 들면 블록이 “10분간은 finalize되어있다”는 것은, 10분동안은 이 블록이 절대 롤백될 일이 없다는 것이다. 10분이 넘어가면 블록이 롤백될 수도 있다는 것 아닌가? 이 불확실성을, Solana는 이 ‘시간 제한’을 child block들에 대한 검증이 진행될수록 지수적으로 늘어나게 함으로써 해결한다. 아래에 100개의 블록이 더 생성된다면, ‘시간 제한’은 $2^{100}$배 증가해서 사실상 무한대가 되는 방식이다. 만약 어떤 노드가 올바르지 않은 fork를 승인한다면, 투표한 노드들의 지분은 삭제 (slash) 된다. 해당 패널티 아래에서 해당 fork는 충분히 오래 finalize되지 못한다.
노드들의 합의들을 동기적으로 모으지 않고, 각각의 노드가 비동기적으로 처리한 다음 그 결과를 충분히 빠른 시간 안의 언젠가 전달받기만 하면 되는 방식이다. 다른 검증들의 시간 제한을 통신 없이 계산할 수 있기 때문이다. 그렇기 때문에 네트워크 속도 의존성을 크게 줄어들게 한다.