BFT 기술의 발자취와 컬러의 “프리즘” 컨센서스
2019년 5월 6일 박창기 작성
비잔티움 장군 문제의 기원
인공위성과 비행기에서 쓰기 위한 장애 없는 분산 컴퓨터 씨스템을 연구하던 Lamport, Shostak, Pease 3인이 1982년 공저한 논문에서, 중앙 통제장치가 없는 분산 컴퓨터 씨스템은 일부 노드의 장애와 해킹 공격이 있으면 씨스템을 안정적으로 운영하기 어렵다는 원리를 설명하면서, 비잔티움 장군 문제 Byzantine Generals Problem를 처음으로 언급한다. 배신자가 있는 상황에서는 여러 장군들이 받은 명령을 진실이라고 확정하기 어렵다는 비유이다.
이 논문에서 몇가지 해결책을 제안하지만, 실제로 씨스템을 실제로 구현한 것은 2009년 Staoshi Nakamoto의 Bitcoin이 처음이다.
‘Byzantine Fault Tolerance’라는 용어를 ‘비잔티움 장애 허용’이라고 주로 번역되는데, 필자는 ‘Tolerance’를 ‘내성’이라고 번역하려 한다. 비잔티움 장군 중 배신자를 ‘허용한다’가 아니라 “배신자가 있어도 견딘다.”라는 의미를 더 잘 전달된다고 생각하기 때문이다.
PBFT (실용적BFT: Practical Byzantine Fault Tolerance)의 출현
1999년 Castro와 Liskov는 BFT 비잔티움장애내성 기술의 가장 큰 문제였던 느린 속도에 대한 해결책을 제시하면서 PBFT를 제안한다.
BFT 알고리즘은 안전성 보장을 위해 모든 메시지를 저장해야 하므로 데이터 량이 많아 느려지고 비용이 크다. 이를 해결 위해 중간 중간에 검증되고 안전한 체크포인트(stable checkpoint)를 만들어 결과 값만 저장하고 나머지 데이터를 버리는 방식이 실용적인 BFT, 즉 PBFT이다. PBFT는 전체 노드 중 최대 1/3의 악의적인 노드가 있다고 가정하면 안정성이 보장된다고 입증했다.
비트코인의 나카모토 컨센서스 Nakamoto consensus
2008년 발표된 비트코인의 나카모토 합의 알고리즘은 확률적(probabilistic) 합의 메커니즘이다. 네트워크가 대략적으로 10분 간격으로 리더를 선출하며, 리더는 이중 지불(double spend) 방지와 같은 제약사항을 준수하는 다음 블록을 제안한다. 그리고 네트워크에 그 블록을 전파(Broadcast) 하고, 전체 노드 중에서 51% 이상이 그 블록을 허용하면 블록이 연결된다.
나카모토 합의 알고리즘의 핵심은 리더 선출 방식이다. 약 10분 간격으로 네트워크 내의 각 노드들은 작업 증명 Proof of Work을 수행하며, 가장 빠르게 연산을 하여 Nonce 값을 찾은 노드는 리더가 된다. 나카모토 합의는 이중 지불 공격을 방지하기 위해 여섯번의 확인( 6 confirmations)이 필요하여 적어도 1시간 후에야 거래가 확정된다. 나카모토 컨센서스는 많은 시간이 소요되며 에너지를 낭비하는 단점이 있다. 수천개의 컴퓨터가 동원되어 전기를 소모하지만 단 한 개 컴퓨터의 성능을 발휘하기 때문이다.
PBFT Practical Byzantine Fault Tolerance의 장점
PBFT를 간단히 설명하면, 비동기 네트워크에서 비잔티움(배신자) 노드가 f개 있을 때, 전체 노드의 개수가 3f+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘이다.
PBFT 는 나카모토 컨센서스에 비해 빠르고 비용이 작기 때문에 보다 많은 블록체인에서 채택되는 추세이다. PBFT의 장점은,
1. 트랜잭션 완결성과 빠른 거래 확정: PBFT는 다음 블록 합의가 이루어진다면 제안된 블록의 합의 내용이 확정되어 한번 확인(1 confirmation)으로 거래가 완결되므로 거래 확정시간 latency이 짧다.
2. 저에너지로 비용 감소: PBFT는 작업증명방식 PoW 이 아니고 지분증명방식 PoS을 기본으로 하여 에너지 사용량이 적고, 따라서 거래 비용이 작다.
블록체인 합의 알고리즘 중 BFT 방식을 채택한 경우 대부분 PBFT 합의 알고리즘을 기본으로 진보시켰다고 할 수 있다. 대표적인 PBFT인 Tendermint는 PBFT에 DPoS 합의 알고리즘을 결합했으며, 이더리움의 Casper는 PoW 방식에 PoS와 PBFT를 결합한 모형이다. PBFT는 Hyperledger Fabric, R3, Ripple, EOS, Cardano 에 이르기까지 Public과 Private을 블록체인에서 다양한 변형으로 사용되고 있다.
Tendermint 의 장점
2014년 재미한국인 권용재 Jae Kwon는 “Tendermint: Consensus without Mining”이라는 논문을 발표했다. 몇 달 후 그는 실제로 작동되는 프로토콜을 오픈소스로 공개했다. 그동안 이론과 시제품에 머물던 PBFT를 사용 가능한 완성품으로 제작하여 발표한 것이다.
기존의 PBFT와 비교하여 Tendermint의 장점을 들어 보면,
1. Tendemint는 블록을 노드들에게 전파Gossip하는 방식을 단순화하고 노드의 수를 늘릴 수 있게 했다.
2. Tendermint는 블록제안자를 수시로 교체할 수 있게 하여 안정성을 높혔다.
3. Tendermint는 비잔티움 노드를 쉽게 발견하여 처벌 할 수 있도록 했다.
그는 Tendermint 를 확장한 인터체인 블록체인 플랫폼 Cosmos를 설계하고 2017년 4월 ICO를 통해 1700만 달러를 30분만에 모금했다. 당시 가격은 1 Atom 당 0.1 달러 였다.
2019년 3월 메인넷을 출범시키며 주요 거래소에서 Atom이 거래되기 시작했다. 2019년 5월 초 현재 Atom의 가격은 5달러 내외이며 시가총액은 약 9억 달러로 세계 15위권이다.
PBFT의 문제점
PBFT는 합의 그룹 크기가 커짐에 따라 합의 속도가 느려지는 문제가 있다. 100개 이상의 노드를 운영하기는 쉽지 않다. 예를 들면 Cosmos는 100개 노드로 운영하면 거래 확정에 약 6초 걸린다. 합의 그룹의 각 노드는 모든 다른 노드들과 두번씩 메시지를 주고받아야 하므로 전체 노드 N의 제곱 수준의 커뮤니케이션 교환이 필요하다. 즉,
Number of communications = N-1 + (N-1) x (N-1) + 2/3 (N-1) x (N-1)
= N-1 +5/3 (N-1)²
100개 노드로 컨센서스를 이루려면 16,434번의 통신이 필요하다.
49개 노드로 컨센서스를 이루려면 3,888번의 통신이 필요하다.
Color Platform의 Prism Consensus
컬러플랫폼의 Prism 역시 PBFT의 진보된 형태이며 dPoS방식이 적용된 컨센서스 알고리즘이다. 일상생활에 쓰는 암호화폐를 지향하기에 “1초에 거래확정”을 목표로 제작되었다. 필자는 2016년 Jae Kwon을 한국에 초청했고 여러 번 미팅을 통해 PBFT와 Tendermint의 장단점을 파악하고 그 개선 작업을 해 왔다.
프리즘 컨센서스는 컬러플랫폼의 CTO인 Dr. Nikolay Pakulin와 본인이 공동으로 개념을 설계하였으며 코딩은 전적으로 Nikolay가 수행했다. 코드의 상당량은 Tendermint의 오픈소스를 재활용했다.
Prism의 핵심 원리는 L 개의 Cluster에 N개의 노드들을 균등하게 분산 배치하여 거래확정속도 Latency를 획기적으로 낮추는 것이다. 즉,
Number of communications = (L-1) + (N/L-1) + (N/L-1) + 2(L-1)² + (N/L-1)
= L - 4 + 3N/L + 2(L-1)²
(* 밑줄 친 부분은 L개의 Cluster에서 병렬로 일어난다)
100개 노드 10개 클러스터로 컨센서스를 이루려면 198 번의 통신이 필요하다.
49개 노드로 컨센서스를 이루려면 96 번의 통신이 필요하다. 전통적 PBFT에 비해서 통신 횟수가 40분의 1 이하로 적어서 빠른 거래확정이 가능하다.
일반적 PBFT에서 클러스터 PBFT 방식인 Prism으로 만드는 과정에서 여러가지 기술적인 난점이 있었다. 몇가지 보안상 취약점을 해결하기 위해 Random number 처리 기술, 사이드체인 Side Chain 도입 등 여러가지 기술이 개발되었다.
Prism의 소스코드는 2019년 4월말 시제품 형태로 Github에 공개했고, 5월 중에 알파버전을 완성할 계획이며, 점차 여러 기술을 접목하여 Color Platform의 메인넷의 핵심Core로 만들 것이다. (이상)
