Byzantine Fault Tolerance 시스템에서 N = 3f + 1인 이유

분산환경 시스템에서는 다른 노드가 보낸 메시지가 정상적이라고 보장할 수 없다. 이때 잘못된 노드가 모두에게 틀린 메시지를 보낸다면 문제가 쉽게 풀린다. 틀린 메시지를 보내는 노드를 차단하면 된다.

하지만 일부 노드에게는 잘못된 메시지를 보내고, 일부 노드에게는 제대로 된 메시지를 보내는 경우는 문제 상황을 찾기 힘들다. 분산 시스템에서 각 노드는 다른 노드의 상태를 모르기 때문이다. 이런 식으로 일부 노드에게만 틀린 메시지를 보내는 노드를 가정하는 모델을 byzantine failure model이라고 부른다.

Byzantine failure model은 네트워크에서 가장 풀기 어려운 모델임과 동시에 실제 네트워크에서 반드시 해결해야 하는 문제다. 특히 다른 노드를 신뢰할 수 없는 p2p에서는 반드시 Byzantine failure model을 가정하고 예외 상황을 처리해야 한다.

그렇다고 인증된 노드만으로 구성된 분산 시스템이라고 byzantine failure model을 가정하지 않아도 된다는 것은 아니다. 노드 자체는 신뢰할 수 있는 사람이 관리하더라도 해킹당했을 수도 있고, 버그로 잘못된 메시지를 보낼 수도 있고, 하드웨어에 문제가 발생할 수도 있다.

Byzantine failure model에서도 정상적으로 돌아가는 시스템을 byzantine fault tolerance (a.k.a. BFT)라고 말한다. 당연히 BFT라고 해도 무한히 많은 faulty 노드에 대해서 동작하지는 않는다. 그래서 보통 어떤 시스템이 BFT라고 말할 때 전체 노드 중 몇 개의 노드에 문제가 있을 때까지 동작하는지를 같이 말한다. 예를 들어 N = 5f라고 말하면, 전체 노드 중 1/5가 byzantine failure일 때 정상 동작하는 시스템이고 N = 3f + 1이라고 말하면, 전체 노드 중 1/3이 byzantine failure일 때까지는 문제없이 돌아가는 시스템을 말한다.

같은 BFT라고 한다면, 감당할 수 있는 faulty 노드의 비율이 더 큰 시스템이 더 안전한 시스템인 것은 당연하다. 하지만 N = 3f + 1. 즉, 1/3 이상의 byzantine failure를 가정하는 시스템은 없다. 이는 1/3이 이론상으로 가질 수 있는 최대치이기 때문이다.

어떤 노드가 byzantine failure일 때 발생할 수 있는 문제 상황은 크게 두 가지다. 첫 번째 문제 상황은 메시지를 보내지 않는 것이다. 즉, 분산 시스템이 N개의 노드 중 byzantine failure f개가 정상적으로 동작하기 위해서는 N - f개의 메시지만으로 합의가 이루어져야 한다. 이것을 다른 말로 quorum을 위해서 N - f개의 노드가 필요하다고 말한다.

두 번째 문제 상황은 byzantine failure인 노드가 악의적으로 다른 메시지를 보내는 것이다. 극단적으로는 quorum을 이룬 N - f개의 노드 중에서 f개가 byzantine failure가 보낸 메시지인 경우를 생각해볼 수 있다. 이 경우도 정상 동작해야 하므로 (N - f) - f 개의 메시지가 byzantine failure인 노드가 보낸 f개의 메시지보다 많아야 한다.

위의 두 경우를 대비하기 위해서 (N - f) - f > f. 즉, N > 3f이므로 f개의 byzantine failure인 노드가 있을 때 최소 3f개보다 많은 노드가 있어야 byzantine fault tolerance한 시스템이고, 이때 가장 작은 N은 3f + 1이다. 따라서 3f + 1개의 노드로 구성된 시스템에서 견딜 수 있는 faulty 노드의 최대 수는 f다.