PBFT와 자손들 Tendermint, NCCU BFT, SEIVE, IBFT, MinBFT, RBFT, Mir-BFT, aBFT

 

 

PBFT (Practical Byzantine Fault Tolerance)

BFT는 분산된 노드들간에 동일한 상태를 유지하기 위한 방식으로, 악의적인 노드가 있는 것을 전제로 합니다. 여기서 악의적인 노드의 최대수는 N = 3f+1입니다.

N : 전체노드 개수 
f   : 악의적인 노드 개수 

따라서 4개의 노드에서는 1개는 악의적인 노드라도 생관없다는 의미입니다. 7개노드에서는 최대 2개.아래 이미지에서는 4개의 노드에서 최대1개의 비잔틴(악의적노드)가 있다고 치고 합의 단계에 대해 설명해보면 

Request 단계

클라이언트는 상태변경을 위한 요청 (REQUEST, o, t, c)s_c 을 대표 노드에 보냅니다. 참고로 이 대표노드(Primary) 또한 비잔틴이 될 수 있으며 그땐 새로운 대표노드를 선출 하게 됩니다.

Pre-Prepare 단계

대표노드는 다른 모든 노드들에게 ((PRE-PREPARE, v, n, d)s_p, m)이라는 메세지를 전파합니다.
이 상태에서는 최신상태를 일단 가지고 있게 됩니다만 이게 옳은 것인지는 판단 할 수 없습니다.
그리고 n은 순서를 나타내는데 오더링에 대한 합의를 한다고 볼 수 있습니다.  

Prepare 단계

 자신이 받은 최신 상태정보를 기반으로 (PREPARE, v, n, d, i)s_i라는 메세지를 클러스터 내의 모든 노드들에게  전파합니다. 여기서 다른 노드들의 PREPARE 메세지 2f를 받으면, Prepared가 되서 넘어갑니다. 이 단계에서는 오더링을 확신하게 되고 커밋 준비를 할 수 있게 됩니다. 근데 여기서 다시 봐야하는 부분이 2f인데요, 자기 빼고 3개중에 2개의 연락만 받으면 ㅇㅋ 라는 겁니다. 즉 나머지 1개가 비잔틴이건 아니건 상관없는거죠. 비잔틴은 아니지만 그 놈은 좀 헤롱헤롱 대서 처리가 좀 늦는다. 이 놈이 Primary가 된다면? 또한 PBFT를 접한 사람들이 가장 궁금하게 생각하는게 나오는데 , 바로 이 지점에서 클라이언트에게 리턴하면 왜 안되냐는 거죠. 어느 정도 합의를 이끌어 냈잖습니까? 이런 부분들에 대해서는 각자도생하는것으로 합시다. 하나씩 그려보면 안되는 경우를 도출해 낼 수 있을 겁니다. (합의에 3단계가 필요한 이유) 

Commit 단계

위에서 PREPARE 메세지 2f를 받으면,  (Commit, v, n, D(m), i)s_i라는 메세지를 전파할 수 있게 됩니다. 그리고 다른 노드들로 부터 Commit메세지를 받아서 자기포함 2f+1개(논문12p)를 받으면 커밋합니다. 

Reply 단계

                 

Commit 검증에 성공한 노드들은 클라이언트에게 응답을 보내주고 f+1개(논문8p) 이상의 똑같은 응답

을 받으면 클라이언트는 보낸 메세지가 성공적으로 분산노드들의 상태를 변경을 했다는 것을 인지합니다. 이런 합의 로직 이외에도 대표노드를 바꾸기 위한 view change,  메세지 prunning을 위한 checkpoint (watermark) 등에 관련된 내용이 있습니다.

간략히 아래와 같은 도식으로 이해 하실 수 있습니다. (PBFT 논문과는 다르게 Client는 모든 노드에게 메세지를 전달합니다. 이는 Primary가 헛수고 하는 것을 막기 위함으로 자신이 받았는데도 불구하고 Primary 로 부터 Pre-Prepare 메세지가 안날라오는 경우를 대비하기 위함입니다) 

아래부터는 블록체인 계에서 사용하는 PBFT 계열의 합의에 대한 간략한 소개 입니다.

Tendermint

사실상 아래 나오는 모든 알고리즘들의 부모격으로써 PoW 말고 PBFT를 이용하여 블록체인을 구성하기 위해서 처음 등장한 개념으로, 무허가형의 지분증명(PoS)기반의 보안 메커니즘에서 수백개의 노드로 활장 할 수 있는 BFT 기반의 프로토콜로써, 

소규모로 구성된 노드들말고 WAN용 광역네트워크에서도 PBFT를 활용할 수 있게 연구하였습니다. 

텐더민트에 관련된 글을 보면 항상 나오는 그림으로써, 위의 PBFT 글을 읽었다면 간단히 이해 할 수 있는 내용입니다. 녹색박스를 보면 Propose -> Pre-Prepare, Prevote Block -> Prepare , Precommit Block -> Commit 와 매칭됨을 알 수 있습니다. 그리고 

아래를 보면 PBFT에 대한 껄쩍지근했던 궁금증을 쉽게 해소 할 수 있습니다.

텐더민트 합의에 3단계가 필요한 이유
텐더민트 합의에 락이 필요한 이유

* Tendermint 에서 대표node 들을 어떻게 선출하는지에 관해서는 조사 안함.  

NCCU BFT

 대만의 Chengchi University 블록체인 그룹에서 텐더민트에서 영감을 받아 만든 프로젝트로써, 이더리움의 합의를 BFT를 통해서 하는 허가형 향으로 변경하기 위한 프로젝트입니다. 메세지로써 블록이 노드들에게 전달되며, 커밋 페이즈에서 블록(트랜잭션)은 실행되고 Insert 되게 됩니다. 

Hyperledger Fabric - SIEVE

PBFT에 체인코드 실행과정과 블록커밋 과정이 제일 앞단과 마지막 커밋 구간에 포함된 것입니다.  
이 얘기는 1.0 이후의 E-O-V 모델을 떠올릴만 한데. 즉 Endorsing 과정이 앞에 선두에 있으며, 그 과정이 끝나면 PBFT를 시작하고 마지막에 커밋한다는 것입니다. 이것은 Full Go언어 기반의 체인코드가 비결정적으로 실행 할 수 있다는 이야기인데, 앞에서 거를 수 있기 때문입니다. 

 

Hyperledger Fabric - Simple BFT 

하이퍼레저가 1.0에서 PBFT를 버리고, 카프카 기반으로 오더링 시스템으로 변한 후에도 패브릭 측은 BFT에 대한 추가 모듈을 개발하는것에 대한 끈은 놓지 않고 있습니다. 일례로 2.0에서 나올 예정인 RAFT도 결국 BFT를 위한 기반이라고 말하고 있는 정도니... (굳이 외부시스템(카프카,주키퍼)를 사용 할 필요없이) 위의 링크의 Simple BFT는 그러한 패브릭이 BFT을 이러한식으로 만들겠다라는 짧은 설계 방향에 대해서 서술해 놓고 있는데 PBFT의 단순화 버전입니다. 개인적으로는 

카프카 대체제로는 RAFT로 충분하고 BFT계열은 간단하든 복잡하는 오버스펙이라 시작할맘도 없을 거 같습니다.참고로 JP모건 애들이 만드는 콘소시엄체인은 RAFT랑 IstabulBFT 라는것을 쓰는데 패브릭도 BFT계열을 오더링만 하는데 사용 할 바엔 E-O-V 프로세스를 폐기하는게 낫다고 봅니다. 아마 거기 아키텍트도 똑같은 생각하고 있을듯..ㅎㅎ 

(추가작성예정)

 

Hyperledger Fabric - MinBFT

 대체제로 PBFT와 똑같은데, Pre-Prepare 과정이 생략됬다고 생각하면 된다. 따라서 페이즈가 2로 줄었고 2f + 1이면 합의를 이룰수 있다. 이는 Secure Hardware (Intel Software Guard Extensions (SGX)) 를 통한 Primary Node의 안전성을 보장함으로 얻어진다. 근데 SGX 해킹된다던데.... 업데이트가 되었는지는 잘..

 

Istanbul BFT (IBFT)

JP Morgan의 콘소시엄형 블록체인인 GoQuorum (IBFT1.0) 과 ethereum 기반의 Hypereledger besu(GoQuorum의 IBFT1.0을 개선하여 IBFT2.0업그레이드한 버전)에서 채택하여 주목받은 BFT계열 합의로써, 기본적으로 PBFT의 형식을 따라가며 블록을 모아서 전송한다는 개념이 추가되었습니다.  주요 차이점은 Client가 분명하지 않으며, 합의 노드들에는 아무 클라이언트들이 요청을 보낼 수 있으며, 합의노드들은 서로의 존재에 대해 알고 있으며 (Public key 공유) 리더(IBFT에서는 Proposer 노드)는 트랜잭션을 모아 블록을 검증 (논스관련,클라이언트 서명관련, Besu경우 가스관련등등) 하고 만들어서 전파합니다. Prepare단계를 거쳐 Commit 단계에서 블록 커밋을 하며, 비 합의노드에도 블록은 전파됩니다. 각 합의노드들의 인증이 모여서 블록 헤더에 extraData로 들어가게 되며, (인증받은 블록이란걸 검증하기 위함, 따라서 스스로 검증가능하다고 말해 집니다)  Validator는 블록에 서명을 하고 insert 를 하게 되는데 이렇게 되면 블록해쉬가 달라지기 때문에 서명한 부분은 블록해쉬에서 제외 하기도 합니다. 한라운드의 합의가 끝마치게 되면 Validators(Backups)들은 새로운 Proposer를 골라서 새로운 블록을 만들 책임을 지웁니다. 보통 라운드로빈으로 하며 이런 Validators들은 그룹멤버쉽을 통해 새로운 멤버가 추가되거나 삭제 될 수 있으며 각각의 투표는 블록헤더에 기록됩니다.

(Hyperledger besu - IBFT2.0 에서의 트랜잭션 검증도)

RBFT 

간략하게 설명하면 여러개의 BFT 인스턴스들을 생성해서 병렬처리하며, 하나의 인스턴스에서 오더링 하는 구조 입니다. (추가 작성중..) 

Mir-BFT

간략하게 설명하면 트랜잭션의 모음을 몇개의 버켓으로 나누어서 각 버켓을 각 노드들에게 맞기는데 , 각 노드들은 리더가 됩니다. 즉 리더가 여러개이며, 이 버켓들이 병렬적으로 처리되고 마지막에 순서를 갖춰서 커밋되는 구조 입니다. 초기 서명검증을 병렬적으로 할 수 있기 때문에 속도 향상을 꽤 할 수 있습니다.

 

공통

* 모든 방법에는 가쉽네트워크를 통한 블록싱크가 추가되야 한다. (패브릭처럼 합의 네트워크 말고 합의 네트워크의 결과를 받아서 블록체인 공유를 하는 시스템이라면 필요 없고~) 
* 패브릭의 체인코드의 Go코드는 비결정적인데 이를 해소할 방안은 없다. (SIEVE가 가능한데...성능상에 불리하며, VM레이어를 만들어 넣어서 결정적으로 바꿀 수 밖에..)

그 밖에도)

* 사실 EOS도 DPos 합의 아래 계층에서 BFT 변형을 사용한다.
* 스텔라도 BFT 변형을 사용한다. 


부록)

Clique (PoA) 알고리즘 

Hyperledger Besu에서 IBFT 말고 사용 할 수있는 합의 알고리즘. (Go etheurem버전도 있음)  
3라운드인 PBFT계열에 비해서 1라운드이다. 따라서 BFT계열보단 빠르다. (추가 작성 중..) 

aBFT (asynchronous byzantine fault tolerance) 
Hedera Hashgraph에서 사용하는 컨센서스 알고리즘으로 BFT계열 알고리즘 중에서는 가장 속도가 빠를 듯 하며, 그 영향력으로 Hyperledger fabric의 ordering 과 Corda 의 notary 및 기타 엔터프라이즈 블록체인등의 합의 알고리즘으로 포함될 가능성이 크다. 

PS)
개인적 의견으론 Permisioned BlockChain에서는 그냥 RAFT를 사용하는게 좋지 않을까 한다. 
비교적 단순하고, 비잔틴은 없다고 가정하므로 성능이 PBFT계열보단 훨씬 빠르다. 
Hyperledger Fabric도 GoQuorum도 RAFT가 디폴트이다. Besu는 IBFT2.0이지만 RAFT를 지원해야 하지 않을까?