MODULE 1 - BLOCKCHAIN INTUITION
07. BYZANTINE FAULT TOLERANCE (BFT)
여기에서는 비잔틴 내결함성(Byzantine Fault Tolerance, BFT)에 대해 알아볼 것이다. 이는 블록체인뿐만 아니라 모든 형태의 탈중앙화 시스템에서도 아주 중요한 특징이다
비잔틴 내결함성(Byzantine Fault Tolerance, BFT)
문제 이해하기
<그림 1>
이야기는 비잔틴 제국이 공격하여 점령하고자 했던 성이 있었다고 가정하며, 이 성을 둘러싸고 네 명의 장군이 공격하여 한다.
하지만 과반수의 동의가 있어야 행동을 개시하고 전투에서 이길 수 있으며, 공격을 하든 후퇴를 하든 간에 장군들의 대다수가 합의에 도달한다.
즉, 어떤 행동을 할지에 대한 합의를 말한다.
네 명 중 세 명이 공격이라고 하면 공격을 해서 이길 것이고 네 명 중 세 명이 후퇴라고 하면 후퇴해서 안전해질 것이다. 하지만 합의점을 찾지 못해 혼란을 겪게 되면 적에게 당할 것이다.
이것이 바로 전제 조건이다.
장군 중에는 사령관이 한 명 존재한다. 하지만 동시에 배신자도 존재한다.
이들 중 반역자가 누군지는 모른다. 반역자가 있을 수도 있고 없을 수도 있다. 하지만 누가 반역자인지는 모른다.
이 반역자는 실제로 의견이 합의에 이르지 못하도록 훼방을 놓습니다
그렇다면 이제 어떻게 원하는 합의를 도출해 낼 수 있는 알고리즘을 만들어내느냐가 문제이다.
BFT에서의 합의 프로토콜
<그림 2>
면저 추가적인 전제조건은 장군들은 서로 의사소통을 할 수 있으나, 구두로만 전달할 수 있고 서신을 서서 서로 전달할 수 없다.
이것이 서로 간의 의사소통 방식이다.
예를 들어서 사령관이 명령을 내린다고 하자.
하지만 사령관이 배신자일 수 있으니 이 장군들 누구라도 셋 중 누가 반역자인지, 그리고 누구를 믿어야 하는지 알 수 없다.
이와 같은 상황을 해결하기 위해서는 모두가 사전에 동의한 알고리즘을 따라야 한다.
현재로서는 이들이 사용할 알고리즘은 단지 이들이 매일 받는 수 많은 메시지를 보고 그에 대해 내린 결정을 기반으로 할 예정이라고 하자.
그렇다면 다음과 같은 상황이 이루어 질 수 있다.
<그림 3>
사령관은 반역자가 아니고, 사령관이 공격하라는 명령을 내렸다고 했을 때,
공격, 후퇴라는 명령이 중요한 것이 아닌 모두가 같은 행동을 하는지인 합의에 더 초점을 맞춰야 한다.
먼저 반역자는 상관 없다. 다른 장군이 하는 말을 딱히 들을 필요가 없기 때문이다.
이제 이 명령을 따를지는 반역자가 아닌 나머지 둘이 정할 일이다.
사령관이 반역자인지, 반역자가 아닌지는 모르기 때문이다.
<그림 4>
이들은 다른 장군들이 모두에게 하는 말을 들어 보고 다수결로 결정하겠다고 하자.
반역자는 당연하게도 사령관이 후퇴하라고 명령했다고 주장한다.(초록색 화살표는 공격을 빨간색 화살표는 후퇴를 뜻함)
그리고 반역자가 아닌 장군들은 다른 장군들에게 사령관으로부터 공격을 명 받았다고 전합니다
이 경우 다수결에 의해 합의에 도달하여 명령을 내린 대로 공격을 할 것이다.
알고리즘에 의해 이들은 합의에 도달했다. 절반 이상이 공격을 정했으니 성을 함락하고 이길 수 있을 것이다.
사령관이 후퇴를 명령했다고 하더라도 동일한 결과가 나올 것이다. 이의 없이 후퇴하는 합의를 볼 수 있었을 것이다.
<그림 5>
이제 사령관이 반역자인 경우를 한번 살펴보자.
- 모두에게 공격을 명령할 경우
- 모두가 공격해서 성을 함락시키는 합의
- 모두에게 후퇴를 명령할 경우
- 모두들이 후퇴하는 합의
- 두 장군에게는 공격을 명령하고 한 장군에게는 후퇴를 명령할 경우
- 모두가 공격해서 성을 함락시키는 합의
- 두 장군에게는 후퇴을 명령하고 한 장군에게는 공격를 명령할 경우
- 모두들이 후퇴하는 합의
이러한 일련의 문제들이 비잔틴 장군 문제이며, 전달된 정보에 대한 다수결의 알고리즘으로 장군들은 전달된 정보에 기반해 의사결정을 내린다. 이 알고리즘을 비잔틴 내결함성(Byzantine Fault Tolerance)이라고 한다.
또한 비잔틴 내결함성에서는 이 내결함이 얼마인지가 중요하다.
만약 반역자가 두 명이라면 어떨까?
이 경우에는 성공이 절대 불가능하다. 반역자가 두 명인 경우에 이 문제를 풀 수 있는 솔루션은 없다.
따라서 논문에서 이 알고리즘이 작동하려면 30% 이상, 33% 이하의 반역자가 있어야 한다고 한다. 즉, 이들 중 3분의 1 이상이 반역자일 때는 작동할 수 없는 것이다.
만약 10명 중 네 명이 반역자 일 때에는 작동하지 않는다.
그러나 그들 중 셋이 반역자였다면 알고리즘은 작동할 것이다.
이것이 바로 반역자에 대한 시스템의 내결함성 수준인 것이다.
블록체인과 비잔틴 내결함성
비잔틴 내결함성이 블록체인이나 탈중앙화된 더욱 기술적인 시스템에서는 어떻게 적용되는 걸까?
예를 들어서 블록체인이라면 시스템을 공격하려는 사람이 있을 수 있으니 이럴 때를 대비해 이 장군들이 고안해낸 알고리즘과 같이 합의 프로토콜을 만들어야 한다.
이 프로토콜은 반역자처럼 시스템을 공격하려는 사람으로부터 보호해 준다. 그리고 최대한의 내결함성을 구현하려면 최대한 그 내결함성을 높인다는 것이 비잔틴 내결함성의 개념이다.
그리고 이 개념은 앞서 언급했듯이 블록체인뿐만 아니라 다양한 분야에서 사용된다.
예를 들어서 모든 시스템이 서로 활발히 대화하는 비행기, 핵발전소, 로켓 등에 적용된다.
비록 비잔틴 제국의 장군에 대한 간단하고 비현실적인 이야기처럼 보일 수 있지만 아주 거대한 개념이다. 특히, 구성 요소가 많은 탈중앙화된 시스템에서는 더욱 중대한 개념이며 블록체인은 그들 중 하나에 속한다.
비잔틴 내결함성에 대해 더 잘 알고싶다면 아래 참고
Leslie Lamport, Robert Shostak, & Marshall Pease, (1982). The Byzantine Generals Problem
Georgios Konstantopoulos, (2017). Understanding Blockchain Fundamentals, Part 1: Byzantine Fault Tolerance
