분산 네트워크 합의 그리고 BFT(비잔틴 장애 허용)

분산 네트워크에서 가장 오래된 이슈이며 풀어야할 문제가 "비잔틴 장군의 딜레마" 입니다 

 

이 문제는 전시 상황에서 4명의 장군으로 구성된 각 4개의 부대가 동시에 한개의 적진을 같은 시간에 공격해야하는

상황입니다 

이때 각 부대는 물리적으로 떨어져있기 떄문에 소통이 필요합니다 

만약 한 명이 잘못된 정보를 퍼트린다면 동시에 공격할수 없어 공격에 실패하는 상황을 해결하기 위한 문제입니다 

 

정리하자면 분산 네트워크 환경에서 악의적인 노드가 존재할 때 이를 어떻게 극복하고 합의에 도달할수있냐가 

"비잔틴 장군의 딜레마" 입니다

 

어떻게 합의를 해야하지?

 

 BFT(Byzantine Fault Tolerance)는 분산 네트워크 안에서 악의적인 노드가 네트워크에 존재하는 경우에도 선의의 노드들이 안전하게 네트워크를 사용할 수 있는 합의 방법은 무엇인지 연구하는 분야 입니다 

 

BGP(Byzantine Generals' Problem)는 두장군 또는 셋 이상이 네트워크에 참여할 떄 서로 합의를 도출하기 위한 방법인데 

램포트가 제안한 OM알고리즘 과 OM 알고리즘에서 서명을 붙임으로 누가 보낸 메시지인지 인지하는 방법을 통해서 

3N+1 이상의 노드가 존재할때 M명의 악의적인 노드가 있더라도 합의가 될 수 있음을 알수 있다 그리고 램포트 증명에서는 3N+1 보다 작은 노드의 상황에서 합의가 되지 않는다는 방식을 증명했다

 

그리고 Safety와 Liveness 모두를 만족시킬수 있다는 결론 또한 나오게 된다 이는 BFT에서 이야기하는 3N+1의 노드가 있을때 N개의 악의적인 노드가 있더라도 합의가 가능하다는 결론과 동일하다 

 

블록체인에서 BFT는 어떻게 해결하였는가? 

블록체인 중 가장 처음 제시된 비트코인의 합의 알고리즘 중 작업증명방식(POW)은 타임 스태픔와 서명을 통해 BFT문제를 해결하였다

 

동작 방식은 아래와 같다 

 

1. 장군은 메시지를 보내기 위해 10분의 시간을가진다

(nonce를 찾기 위한 컴퓨팅 작업)

 

2. 메시지는 모든 장군의 메시지와 메시지를 보내기 위해 10분을 들였다는 증거를 포함한다, 이 규칙이 추가 됨에 따라 중간의 비잔틴 장군(악의적인)이 존재하더라도 다른 장군들은 이 장군이 거짓임을 밝혀 낼수 있다. 혹은 초기에 메시지를 받은 장군이 존재하더라도 앞선 시나리오 처럼 정직한 장군들이 성을 함락할수있다.

 

POW는 작업증명 방식에 따라 언제나 어려운 문제에 대한 답(Nonce)을 마이너(채굴자)가 찾으면 블록이 생성되어 체인을 이어나가게 된다

이렇게 만들어진 가장 긴 체인은 유효(Valid)한 체인이고, 정격 체인(Canonical Chain)이라 부른다

이 방식은 FLP Impossibility를 우회하는 바아법 중 Liveness over Saftey의 방법이며 비트코인은 Liveness를 먼저 확보하고 6Confirm(약 60분)을 통해 완결성(Finality)을 가져 Safety를 보안 하였다

 

BFT 합의 알고리즘은 동기식 네트워크에서만 합의할 수 있었던 문제가 있는데 이문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰수 있게한 방식이 PBFT다 

 

PBFT 동작 방식

위 그림은 PBFT의 합의 알고리즘을 설명한 그림이다 

 

PBFT는 비동기 네트워크에서 배신자 노드F개가 있을때, 총 노드 개수 3F+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘입니다 

네트워크에서 모든 노드는 거래와 같은 합의 대상의 상태를 변화할 것인지 Prepared Certificate와 Commit Cretificate라는 두번의 절차를 거쳐 결정하게 됩니다 

PBFT는 블록체인에서 Tendermint는 PBFT에 DPos 합의 할고리즘을 결합하고 이더리움은 Casper 에 Pow방식 채굴에 Pos + PBFT 형태의 블록 검증 시스템을 제안하고 있고 진행중입니다 이외에도 PBFT는 Hyperledger Fabric, R3, Ripple, EOS에 이르기 까지 Public과 Private을 가리지 않고 다양한 블록체인에서 사용되고 있다

 

PBFT의 장점 

1. 트랜잭션 완결성과 빠른 거래 확정: PBFT는 다음 블록 합의가 이루어진다면 제안된 블록의 합의 내용이 확정되어

한번 확인(1 Confirmation)으로 거래가 완료되므로 거래 확정 상대적으로 시간이 짧습니다.

 

2. 저 에너지 비용, PBFT는 작업증명방식 POW가 아니고 지분증명방식 Pos를 기본으로 하여 에너지 사용량이 비교적기 떄문에 거래 비용이 적다. 예를 들어 현재 POW 방식의 이더리움은 POS를 사용하는 테라에 비해 높은 가스비를 유지한다

 

PBFT의 단점

1. 결국 합의 그룹의 각 노드들은 모든 다른 노드들과 두 번씩 메시지를 주고받아야 하므로 전체 노드 N의 제곱 수준의 커뮤니케이션 교환이 필요하기떄문에 100개 노드로 합의를 이루려면 

위 공식에 따라 16,434번의 통신이 필요합니다

즉 합의 그룹 크기가 커질수록 합의속도가 느려지는 문제가 있습니다

PBFT 합의

 

Tendermint를 좀더 자세히 

 

텐터민트 알고리즘 state machine

Tendermint는 Cosmos에서 사용하는 합의 알고리즘으로 PBFT 알고리즘을 공개 및 비공개 블록체인에 맞게 개량한 합의 알고리즘입니다 Tendermint는 DPos 개념과 PBFT 개념을 섞어서 공개와 비공개 블록체인에서 사용할 수 있도록한 합의 알고리즘 입니다 

먼저 Tendermint의 전체 합의 프로세스는 PBFT와 거의 유사합니다 Tendermint 프로세스에서의 Propose는 PBFT의 Pre-prepare, Prevote는 Prepare, Precommit은 PBFT의 Commit으로 이해하면 된다

PBFT와 차이점은 기존의 PBFT는 하나의 노드가 하나의 투표를 하는 방식으로 투표를 받아 가장 많은 투표를 받은 블록을 승인하지만, Tendermint는 지분(stake)을 기반으로 투표하게 됩니다 노드의 수보다는 지분이 중요!

 

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

 

요약하자면 Tendermint는 블록을 노드들에게 전파하는 방식을 단순화하고 노드의 수를 늘릴수있게했으며, 블록제안자를 수시로 교체할 수 있게 하여 안정성을 높였습니다 그리고 비잔틴 노드를 쉽게 발견하여 처벌할수 있습니다 

 

번외로 DBFT는 여러노드가 아닌 대표자를 선출하여 합의를 보기 떄문에 특정 노드에 권력이 집중되거나 집단화 현상이발생할수있다