Byzantine Fault Tolerance (BFT)
비잔틴 장애 허용은 두 장군 문제를 일반화한 문제인 비잔틴 장군 문제로부터 파생된 장애 허용 연구 분야의 한 갈래입니다. 이 분야의 연구의 목적은 비잔틴 장애라고 불리는 시스템에 생길 수 있는 임의의 장애를 견딜 수 있는 시스템을 만드는 것입니다.
비잔틴 장애는 단지 시스템이 멈추거나 에러 메시지를 보내는 것과 같은 장애뿐만 아니라, 잘못된 값을 다른 시스템에 전달하는 등 좀 더 원인을 파악하기 어려운 장애들까지 포함합니다. 예를 들어서 결과를 반환하는데 실패했다든지, 부정확한 결과를 반환한다든지, 의도적으로 잘못된 결과의 반환 또는 시스템의 다른 파트들에 상이한 값을 반환하는것이 있겠습니다.
만약 비잔틴 장애 허용 시스템이 제대로 구현되었다면 미리 정해진 정도를 넘지 않는 부분에서는 이러한 비잔틴 장애가 있더라도 합의된 값을 전달할 수 있을 것 입니다. 비잔틴 장군 문제에서 합의를 이루기 위해서 다음과 같은 조건이 있습니다.
한 지휘관이 명령을 자신을 제외한 모든 부하들에게 전달하면, 모든 충실한 부하들은 같은 명령에 복종해야 합니다. 그리고 만약 지휘관이 충실하다면, 모든 충실한 부하들은 지휘관 이 보낸 명령에 복종해야 합니다. 그리고 만약 지휘관이 반역자라도 합의는 반드시 이루어져야 하는데, 결과적으로 모든 부하들이 과반수의 표를 얻는 것입니다.
즉, 합의에 도달하기 위한 알고리즘 은 부하가 관찰하는 결정의 대다수 가치를 기반으로 하는 것 입니다. 그래서 비잔틴 장군 문제에서 참 여자의 3분의 2가 정직한 한, 알고리즘 이 합의에 도달할 수 있습니다. 만약 반역자들이 3분의 1 이상 되면 합의에 이르지 못하고, 적들이 이기게 됩니다.
이를 전체 시스템에 3f+1만큼의 노드가 있다면, 그 시스템은 f개의 비잔틴 장애를 일으키는 노드를 허용할 수 있다는 것을 의미합니다. 추가적으로, 이전 설명과 관련하여 비트코인처럼 탈중앙화된 암호화 폐를 만들었다는 것은 곧 이 비잔틴장군 문제를 해결했다는 의미가 됩니다.
비트코인 네트워크에 참여한 노드들 중에서 일부는 위/변조된 화폐 를 이용하여 지불을 시도하거나, 이중 지불을 시도하려는 등의 잘못된 정보를 네트워크에 전파할 수 있습니다. 그럼에도 불구하고 정직한 노드가 비트코인 프로토콜을 충실히 따른다면 전체 네트워크에서 합의된 결론을 도출할 수 있다는 의미가 되는 것입니다. f개의 비잔틴 장애 노드가 있을 때 전체 노드의 수는 3f+1이 있어야 한다고 했습니다.
그렇다면 총 3개의 프로세서가 있을 때는 어떻게 될까요? 결론부터 말씀드리면 3대의 프로세서 사이에서 BFT 합의를 도출하는 알고리즘은 없습니다. Leslie Lamport는 Byzantine Fault Tolerance 논문에서 이를 증명했고 간단한 시나리오를 언급하며 왜 3대의 프로세서가 있을 때 BFT 합의가 불가능한 지 보여주었습니다.
그 시나리오이며 1명의 장군 과 2명의 부하가 있을 때 그중 1 명의 배신자가 있는 경우 입니다. 그림의 경우에는 부하 L2 (Lieutenant 2)가 배신자인 경우입니다. 지휘관이 공격하라는 명령을 L1 과 L2에게 내렸을 때, L2가 L1에게 거짓으로 지휘관이 퇴각하라는 명령을 내렸다고 전달한 경우를 생각해봅시다.
L1의 입장에서 보면, 공격할지 퇴각할지 결정할 수 없기 때문에, 배신자 를 제외한 나머지 두 정직한 장군들은 똑같은 결론을 내릴 수 없게 됩니다. 오른쪽 그림은 지휘관이 배신자인 경우입니다. 마찬가지로 l1이 공격할지 퇴각할지 결정할 수 없기 때문에, 배신자를 제외한 나머지 두 정직한 장군들은 동일한 결론을 못 내릴 수 있습니다.
그렇다면 노드가 4개 있을 때, 즉 3개의 정직한 노드와 1개의 비잔틴 장애 노드인 경우에 합의가 가능한지 알아보겠습니다. 그림은 L3이 배신자인 경우에, L2의 입장에서 바라본 예시입니다. 지휘관이 명령 v를 모든 부하(L1, L2, L3)에게 전달합니다. L1는 정직하기 때문에 v를 그대로L2에게 전달합니다.
하지만 L3은 배신자이기 때문에 v 대신 x를 L2에게 전달했습니다. L2 입장에서 올바른 결정을 할 수 있을까요? L2는 지휘관으로부터 v, L1으로부터 v, L2로부터 x를 전달받았기 때문에 그중 제일 많은 v 명령을 따르면 됩니다. 그러면 정직한 노드인 지휘관 L1, L2는 모두 동일한 결정을 내리게 됩니다.
그림은 지휘관이 배신자인 경우입니다. 지휘관이 각 부하들에게 다른 명령 x, y, z,를 보냅니다. L1은 전달 받은 x를 L2, L3에게 보내고 L2는 전달받은 y를 L1과 L3에게 보냅니다. L3도 마찬가지로 전달받은 z를 L1과 L2에게 보냅니다.
각 부하는 어떤 결정을 내리게 될까요? 받은 명령이 x y z로 동일하므로 합의에 도달할 수 있습니다. 비록 x y z가 모두 다르더라도 모든 3명의 부하들에게 다수결의 값x y z는 동일하기 때문입니다. 예를 들어서 기본 행동이 퇴각이라고 가정한다면 배신자인 지휘관을 제외한 3명의 부하는 퇴각이라는 동일한 행동을 할 것입니다.
Practical Byzantine Fault Tolerance (PBFT)
Practical Byzantine Fault Tolerance (PBFT)는 블록체인 기술이 대두되기 전인 1999년에 castro miguel라는 연구자가 발표한 논문이며 이론적으로 증명 된 BFT를 실제 시스템에서 사용할 수 있도록 구현한 분산 합의 알고리즘입니다.
이 알고리즘은 비잔틴 장애를 일으키는 노드가 있는 상황에서 State Machine Replication을 목표로 합니다. 구체적으로 N=3f+1대의 노드가 있는 클러스터에서 최대 f 대의 노드가 동시에 byzantine fault를 일으킬 때에도 정직한 노드들은 같은 상태로 전이하는 것을 목표로 합니다.
또한 PBFT는 Tendermint를 비롯한 다른 많은 BFT계열의 블록체인 합의 알고리즘에 기반이 되는 알고리즘이며 컨소시움/프라이빗형 블록체인 프로젝트인 Hyperleder Fabric에서 합의 알고리즘으로 채용한 것으로도 알려져 있습니다.
PBFT는 전체 n개의 replica 중에서 최대 (n-1)/3개가 동시에 장애가 발생했을 때까지 safety와 liveness 모두를 제공합니다. Safety를 제공한다는 것은 복제된 서비스(노드)들이 원자성을 만족시킨다는 것이고, Liveness를 제공한다는 것은 client들이 결국에는 그들에 요청에 대한 응답을 받는다는 것을 의미합니다.
PBFT 논문에서는 한 클러스터 안의 노드들끼리 서로 네트워크로 연결되어 있는 비동기 분산 시스템을 가정합니다. 이때 네트워크가 비동기이기 때문에 이로 인해서 일어날 수 있는 현상으로 메시지를 보냈는데 전달에 실패한 경우, 메시지를 보냈는데 전달이 늦어지는 경우 동일한 메시지를 두 번 보내는 경우 메시지가 도착하는 순서가 뒤죽박죽인 경우 등이 있습니다.
또한 PBFT는 Byzantine Failure 모델을 가정하고 있습니다. 따라서 한 클러스터 안에 노드가 최소한 n=3f+1대가 있는 상황에서 동시에 최대 f 대의 서버가 fail 할수 있는 상황을 가정합니다. 그리고 독립적인 실패를 가정하고 있습니다. 어떤 노드가 fail 하면서 다른 노드도 연달아 fail 할 수 있는 가능성을 완전히 차단한다는 의미입니다.
이제 PBFT가 어떻게 작동하는지 대략 적으로 설명하겠습니다. 먼저 클라이언트가 primary에게 서비스 작업을 호출하기 위한 요청을 보냅니다. 그리고 primary는 나머지 backup들에게 클라이언트의 요청을 전파하고 합의 과정을 거칩니다. 그다음, 각 replica(primary+backups)들은 합의 과정에서 요청이 반영되는 것이 확실해지면, 이를 실행하고 클라이언트에게 응답을 해줍니다.
마지막으로 클라이언트가 f+1개 이상의 똑같은 응답을 다른 replica 들로부터 받기를 기다립니다. 이를 받았다면 요청이 제대로 반영 되었다는 것을 클라이언트는 확신할 수 있습니다. 추가적으로 이러한 프로세스를 위해서 각 replica에 deterministic해야 하고, 동일한 상태에서 시작해야 한다는 두 가지 요구사항이 부과됩니다.
우선 처음에 request 단계에서는 클라이언트가 primary에게 요청을 보냅니다. 클라이언트는 primary에게 요청을 보낼 때 요청할 operation과 자신의 타임 스탬프와 클라이언트를 식별할 수 있는 ID를 함께 서명하여 오른쪽에 보이는 메시지를 primary에게 보내는 것입니다.
그 이후 primary는 이 메시지를 입증 하고, 이를 위한 sequence number를 제안할 수 있습니다. Pre-prepare 단계에서는 primary가 유효한 request를 클라이언트로부터 받으면, 그 request에 sequence number라는 숫자 n을 할당합니다. 여기서 sequence number는 몇 번째 request 인지를 나타내는 번호입니다.
예를 들어서 sequence number가 15인 request는 15번째로 도착한 request를 나타내는 것입니다. 번호를 할당한 이후에 primary는 오른쪽 에 보이는 pre-prepare 메시지를 모든 backup들에게 보냅니다. 해당 pre-prepare 메시지의 의미는 이렇습니다.
"메시지 m이 클라이언트로부터 primary p에게 도착했고, View number v, Sequence number n으로 해당 메시지 m을 인정하겠다. 또한 m이 조작되지 않았다는 것은 m의 hash digest인 d로 확인할 수 있다. 마지막으로 이 메시지가 조작된 것이 아님을 primary p의 서명 sp로 보장하겠다." 라는 것입니다.
그래서 Pre-prepare 메시지는 backup 들이 메시지 m을 입증하고 sequence number를 받도록 허용해줍니다. Prepare 단계에서 pre-prepare 메시지를 받은 backup들은 우선 수신한 메시지가 유효한지 검증합니다. 여기서 유효한 pre-prepare 메시지는 서명 Sp가 유효하며, 현재 backup의 view v에 있는 메시지이고 처음 받는 view v, sequence number n인 메시지입니다.
검증 후에 모든 backup들은 그가 받은 sequence number의 수신을 알리기 위해서 오른쪽에 보이는 포맷대로 prepare 메시지를 모든 다른 backup들에게 multicast로 보냅니다. Commit 단계에서, 2f개의 동일한 prepare 메시지를 수집하여 prepared(m, v, n, i) 의 상태가 참이 되면, 해당 노드(replica)는 오른쪽에 보이는 포맷의 commit 메시지를 보냅니다.
그 이후 다른 노드들이 보내는 commit 메시지의 서명을 검증하며, 클러스터에 있는 모든 노드(2f+1)로부터 메시지 m을 view v sequence number n으로 commit 하겠다는 메시지가 쌓이면, committed-local(m, v, n, i) 상태가 됩니다. 마지막으로 reply 단계에서, 노드 (replica) i가 committed-local (m, v, n, i) 상태를 참으로 만족하면, 모든 정직한 노드가 성공적으로 메시지를 반영하겠다는 것을 보장하며 메시지 m을 실행하게 됩니다.
그리고 각 노드들은 클라이언트 에게 오른쪽과 같은 형식의 Reply 메시지를 보냅니다. 그 이후 클라이언트가 f+1개 이상의 똑같은 응답을 받으면 클라이언트는 자신이 요청한 메시지가 시스템에 제대로 반영이 되었다는 것을 확신할 수 있게 됩니다.
Tendermint
Tendermint는 Cosmos라는 블록체인 플랫폼에서 사용하는 합의 알고리즘으로 pbft 알고리즘을 개량한 합의 알고리즘입니다. Tendermint는 기존에 분산시스템에서 합의를 위해서 사용되었던 PBFT같은 알고리즘을 블록체인에 적용시킨 의미 있는 사례입니다.
이것은 DPoS (Delegated Proof-of-Stake)와 PBFT 개념을 혼합해서 퍼블릭 및 프라이빗 블록체인에서 사용할 수 있도록 한 합의 알고리즘입니다. 그래서 BFT에서처럼 safety와 liveness가 보장됩니다. 또한 BFT에서 n=3f+1일때 f만큼의 비잔틴 장애 노드를 허용한다고 말씀드렸었는데, 이것에 맞추어 검증 노드(검증인) 배치 수를 정했습니다.
총 100개의 validator(검증 노드)가 구성 되며, 33개의 장애 노드까지 허용할 수 있습니다. 하지만 10년 동안 매년 13% 비율로 증가하여 최종적으로는 총 300개의 검증 노드를 구성합니다. 추가적으로 cosmos white paper를 기준으로 1000TPS의 처리 속도를 능가합니다.
다음 그림은 Tendermint의 전체 합의 과정을 나타냅니다. Tendermint에서는 현재 라운드에서 다음 블록을 위해서 라운드 로빈 방식으로 검증인 중에 한 명을 블록 생성자(block publisher)로 선정합니다. 따라서 검증인(Validator)의 지분(Stake) 이 더 높을수록, 블록 생성자로 선정 될 기회가 많다는 것입니다.
또한 Non-validator들이 각각 검증인 (Validator)들에게 지분을 위임하여 총합의 과정에 관여하게 되는 검증인들을 선정합니다. 전체 합의 프로세스는 PBFT와 거의 유사합니다. Tendermint의 각 라운드는 Propose, Prevote, Precommit 이렇게 3가지 단계로 나눠집니다.
여기서 Propose는 PBFT의 Pre-prepare, prevote는 Prepare, precommit은 PBFT의 commit 으로 매칭시키면 이해가 쉽습니다. Propose 단계에서 블록 생성자로 지명 된 검증인이 새 블록을 만들어서 전파시킵니다. 그러면 다른 검증인들이 이를 listen하고 있다가 Prevote 단계에서 해당 블록을 받아들인 것인지 아닌지 투표를 하기 위해서 서명된 Prevote 메시지를 브로드캐스팅합니다.
Precommit 단계에서 2/3 이상의 prov ote 메시지를 받았으면 precommit 메시지를 브로드캐스팅합니다. 이 단계 마지막에 Precommit에 동의한 검증인이 2/3 이상인 경우에 블록을 Commit합니다. 만약 여기서 2/3 이상의 Precommit 메시지를 얻지 못한 경우에는 블록을 생성하지 않고 다음 라운드로 진행합니다.
추가적으로, Tendermint는 투표를 할 때 Locking 메커니즘을 통해 투표 에 참여한 지분을 네트워크에 동결시키는 메커니즘을 통해 이중 투표 문제를 막았습니다. 또한 이중 투표 시도와 같은 블록체인을 공격하려는 악의적인 행위를 하면 지분을 빼앗는 방법으로 기존의 블록체인이 네트워크 공격 노드 에 아무런 처벌을 하지 않던 Nothing of Stake 문제를 해결하였습니다.
다음은 여러 가지 합의 알고리즘 의 비교 분석을 위해서 정리한 테이블입니다.
Pow, Pos, Dpos, Poa, PBFT, Tendermint 합의 알고리즘에 대해서 블록체인 타입, 트랜잭션의 변경불가능함, 트랜잭션 처리율, 암호화폐의 필요성 합의에 참여하기 위해서 비용이 발생하는지 여부, 합의 절차에 참여하는 노드의 수 신뢰 모델 등의 특징들을 기준으로 비교해보았습니다.
참조
http://www.kmooc.kr/courses/course-v1:POSTECHk+CSED490U1+2021_T1/about
블록체인 입문
블록체인과 암호화폐 기술을 깊이 배우기에 앞서, 비 전공자들도 이해를 할 수 있는 수준으로 블록체인과 암화화폐에 대한 high-level 설명 및 응용 예시를 제공하고 실제 상황에 적용할 수 있다.
www.kmooc.kr
'SW > 블록체인' 카테고리의 다른 글
| 블록체인 : 하이퍼레저 프로젝트 중 가장 잘 알려진 하이퍼레저 패브릭의 특징 (0) | 2022.02.16 |
|---|---|
| 블록체인 : 엔터프라즈용 블록체인인 하이퍼레저 프로젝트 이해 : 목적에 따라 적절한 프로젝트를 선택하여 활용 방법 (0) | 2022.02.15 |
| 블록체인 : 분산 합의의 필요성 : 블록체인에서 합의 알고리즘이 필요한 이유 : PoW, PoS, DPoS의 차이를 이해 (0) | 2022.02.13 |
| 블록체인 : EOS 프로그램을 구성하고 있는 구성 요소들과 네트워크 구조 : EOS 네트워크 설치 및 운영 (0) | 2022.02.12 |
| 블록체인 : EOS가 DPoS를 합의 알고리즘으로 채택함으로써 발생할 수 있는 여러 이슈들과 EOS 네트워크에서 일어날 수 있는 공격 (0) | 2022.02.11 |