BFT 기반 합의 알고리즘

저번 포스팅에서는 공개 블록체인(Public Blockchain)에서 주로 활용하는 합의 알고리즘인 작업증명 알고리즘(Proof-of-Work)과 지분증명 알고리즘(Proof-of-Stake)에 대해 알아보았습니다. 이러한 알고리즘들은 확률적 합의 알고리즘으로써 특수한 데이터(PoW : Nonce , PoS : 지분 및 화폐의 나이)를 통해 블록의 유효성과 우선순위를 정하고 별도의 통신 없이 모든 노드가 합의를 하는 알고리즘이었습니다.

블록체인 기술 연재 시리즈

블록체인 기술 개요
스마트 컨트랙트(Smart Contract) 개요 -1
스마트 컨트랙트(Smart Contract) 개요 -2
loopchain SCORE(Smart Contract On Reliable Environment
합의 알고리즘 개요
작업증명(PoW, Proof-of-work)과 지분증명(PoS, Proof-of-stake)

이번 포스팅에서는 기존 확률적 합의 알고리즘의 문제점을 개선하고자 기존 분산시스템에서 상태 기계 복제(State Machine Replication)를 위해 활용한 BFT (Byzantine Fault Tolerance) 합의 알고리즘 방식을 활용한 블록체인 합의 알고리즘을 소개하도록 하겠습니다.

기존 합의 알고리즘의 문제

이전 포스팅에서 설명한 작업증명 알고리즘과 지분증명 알고리즘이 적용된 블록체인이 작동하기 위해서는 내부 가상 화폐 등의 보상 시스템이 꼭 필요합니다. 블록체인의 노드들이 작업증명 알고리즘에서 사용하는 에너지 낭비 방식의 채굴을 수행하는 이유는 블록체인 네트워크에서 주는 가상 화폐 보상을 얻기 위해서 입니다. 지분 증명 또한 마찬가지고 내부 화폐 및 보상이 없으면 블록을 생성할 이유도 없고 지분 증명 메커니즘 자체를 사용할 수 없게 됩니다.  때문에 가상 화폐 외의 다른 많은 서비스를 수행하는 사설 블록체인의 경우 이러한 내부화폐가 필요한 합의 알고리즘을 사용할 수 없습니다.

기존 알고리즘은 가상화폐가 필요하다는 문제 외에도 부분 분기가 일어날 수 있다는 문제가 있습니다.  간단하게 작업증명 알고리즘을 예로 들면 A와 B블록이 거의 동시에 생성될 경우 각 노드는 자신의 선택에 따라 A와 B블록 중 하나를 선택합니다. 이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 됩니다. 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에서는 적용이 어려운 문제점이 있습니다.

PBFT(Practical Byzantine Fault Tolerance) 

PBFT는 분산시스템이 약속된 행동을 하지 않는 비잔틴 노드가 존재할 수 있는 비동기 시스템일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘입니다(비잔틴 노드, 합의 알고리즘등의 용어가 이해 안가면 이전 포스팅에서 알아 보실 수 있습니다).  PBFT는 기존의 BFT 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있게 하였습니다.

PBFT 알고리즘 동작 방식(출처)

위의 그림은 PBFT 알고리즘이 동작하는 방식을 나타낸 것입니다. 이러한 기존 분산 시스템에서 사용하던 합의 알고리즘은 Primary 혹은 Leader라 불리는 특별한 노드가 존재합니다. 이 노드는 클라이언트의 요청 순서를 정렬하고, 요청에 대한 결과를 기입하요 다른 노드들에게 뿌려주는 역할을 합니다.

합의는 다음과 같이 수행합니다. 1) 리더가 클라이언트들의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에 전파합니다. 2) 리더의 메시지를 받은 노드들은 다른 노드들에서 받은 메시지를 다시 한번 나머지 노드들에게 전파합니다. 3) 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메시지(정족수 이상의)가 무엇인지 다른 노드들에게 전파합니다. 1) 2) 3)의 과정이 끝나면 모든 노드들은 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 됩니다.

PBFT는 두번의 브로드캐스트 과정을 이용해 비잔틴 리더나 비잔틴 검증 노드가 네트워크 분기를 위해 이상한, 혹은 임의의 메시지를 보내도 네트워크의 모든 노드는 같은 메시지를 가질 수 있게 하였습니다. 이러한 PBFT 알고리즘은 IBM Fabric 0.6v이나 1.0v의 Orderer서비스, R3 Corda의 Notary와 같은 프라이빗 블록체인에서 사용하고 있습니다.

Tendermint (DPoS + PBFT) 

Tendermint는 Cosmos에서 사용하는 합의 알고리즘으로 PBFT 알고리즘을 공개 및 비공개 블록체인에 맞도록 개량한 합의 알고리즘 입니다. Tendermint는 전통적인 합의 알고리즘이 블록체인에 적용된 의미있는 사례이며 DPoS(Delegated Proof-of-Stake) 개념과 PBFT 개념을 섞어 공개 및 비공개 블록체인에서 사용할 수 있도록 한 합의 알고리즘입니다.

Tendermint
Tendermint 합의 과정(출처 : https://tendermint.com/intro/consensus-overview)

Tendermint의 전체 합의 프로세스는 PBFT와 거의 유사합니다. Tendermint 프로세스에서의 Propose는 PBFT의 Pre-Prepare, Prevote는 Prepare, Precommit은 PBFT의 Commit으로 매칭시키면 이해가 쉽습니다.

Tendermint는 앞에서 언급하였듯이 PBFT에 DPoS개념을 추가하여 블록체인에 적합한 합의 알고리즘을 개발하였습니다. 차이점을 간단히 요약하면 기존의 PBFT는 하나의 노드가 하나의 투표를 하는 방식으로 투표를 받아 가장 많은 투표를 받은 블록을 승인하지만 Tendermint는 지분(Stake)을 기반으로 투표를 합니다. 투표하는 노드의 수 보다는 지분이 중요하죠.

Tendermint는 투표를 할때 Locking 메커니즘을 통해 투표에 참여한 지분을 네트워크에 동결시키고 이를 해제하는 메커니즘을 통해 이중 투표 문제를 막고 지분으로 네트워크를 유지하게 합니다.  또한 이중 투표 시도와 같은 블록체인을 공격하려는 악의적인 행위를 하면 지분을 빼앗는 방법으로 기존의 블록체인이 네트워크 공격 노드에 아무런 처벌을 하지 않던 문제(Nothing of Stake) 문제를 해결하였습니다.

이번 포스팅에서는 전통적인 BFT 알고리즘인 PBFT와 블록체인 합의 알고리즘인 Tendermint에 대해 알아보았습니다. 이러한 합의 메커니즘은 공개 블록체인 뿐 아니라 사설 블록체인에서 활발하게 연구되고 있는 알고리즘들 입니다. 다음 포스팅에서는 loopchain에서 사용하는 합의 알고리즘인 LFT에 대해 간략하게 소개하고 백서를 공개하도록 하겠습니다.

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중