Byzantine Generals' Problem

Citation: Lamport, Leslie, Robert Shostak, and Marshall Pease. "The Byzantine generals problem." ACM Transactions on Programming Languages and Systems (TOPLAS) 4.3 (1982): 382-401.

Intro

현재 분산 네트워크 시스템에서는 BFT 기반의 합의 알고리즘이 많이 사용되고 있다. BFT (Byzantine Fault Tolerance)는 분산 네트워크 안에서 악의의 노드 (Byzantine)가 네트워크에 존재하는 경우에도 선의의 노드들이 안전하게 네트워크를 사용할 수 있는 합의 방법은 무엇인지 연구하는 분야이다.

본 포스트에서는 1982년 레슬리 램포트 외 2명이 퍼블리싱한 논문 "The Byzantine Generals Problem"을 중심으로 초기의 분산 네트워크 합의 알고리즘 연구 방향과 그 내용을 살펴본다.

Two Generals' Problem

두 장군 문제는 신뢰할 수 없는 네트워크에서의 노드 간 메시지가 올바르게 전송되기 위한 조건을 논의하면서 처음 나온 개념이다.

1957년에 출판된 논문" SOME CONSTRAINTS AND TRADEOFFS IN THE DESIGN OF NETWORK COMMUNICATIONS"에서 처음 논의를 시작했고, 두 장군 문제라는 용어는 1978년에 만들어졌다.

네트워크를 구성하는 노드를 장군으로 가정하고, 두 장군이 공동의 적을 공격하는 시나리오를 생각해보자.

Scenario

두 장군은 적진을 사이에 두고 공격 시각을 합의해야 하는 상황. 어떻게 합의에 성공할 수 있을까?

반드시 두 장군이 동시에 공격해야만 이길 수 있다.
공격 시각을 합의하기 위해 각자의 메신저를 보낸다.
메신저는 메시지 전달을 위해 반드시 적진을 통과해야 한다.

공격 시각을 결정하기 위해서 장군들이 생각한 방법은?

장군 A가 메신저를 통해 장군 B에게 공격 시간을 전달
장군 B가 장군 A의 메시지를 확인 후 회신
장군 A가 장군 B의 회신 메시지를 확인
결정된 공격 시각에 일제히 공격!

장군들의 고민

장군 A가 "11월 1일 오전 8시에 공격"이라는 메시지를 작성해서 장군 B에게 보낸다. 장군 B가 장군 A의 메시지를 받고 "공격 확인"이라는 응답 메시지를 장군 A에게 보낸다. 장군 A가 메시지를 받으면 합의는 성공적으로 이루어진다.

하지만, 장군 A가 보낸 메시지를 가지고 떠난 메신저가 도중에 적군에게 잡힐 수도 있다. 장군 A의 메신저가 적군의 경계를 무사히 뚫고 장군 B에게 메시지를 전달했다고 해도 장군 B의 메신저가 적군에게 잡힐 수도 있다. 이 경우 메시지가 잘 전달되지 못할 확률이 반드시 존재하기 때문에 장군들은 합의에 도달할 수 없다.

Byzantine Generals' Problem

BGP (Byzantine Generals' Problem)는 앞서 설명한 두 장군 문제를 일반화한 주제로 셋 이상이 네트워크에 참여할 때 서로 합의를 도출하기 위한 방법을 논의한다. 두 장군 문제와 같이 공동의 적을 상대로 승리하고 싶은 장군들을 예시로 제시하고, 여기에 메시지 위조가 가능하며 서로 담합도 할 수 있는 배신자를 등장시킨다. 레슬리 램포트 외 2명이 퍼블리싱한 논문에서의 논의 주제는 배신자가 존재할 경우에도 합의에 성공하려면 배신자를 포함하여 총 몇 명의 장군이 네트워크에 있어야 할 지를 정하는 것이다.

Base Conditions

적은 어느 정도의 병력이 모여서 한 번에 공격을 해야 이길 수 있는 상대이다. 이를 위해 여러 부대가 적진을 둘러싸고 있으며 각 장군들은 합의를 통해 공격을 해야할지 말아야 할지를 결정해야 한다.
각 부대는 하나의 장군이 이끌고 있으며 메신저가 전달하는 메시지를 통해서만 서로 소통이 가능하다.
메신저는 반드시 적진을 통과해야지만 다른 부대로 갈 수 있다.
장군들 중 한 명의 사령관이 "공격" 이냐 "후퇴" 냐를 결정하여 메시지를 모든 장군에게 전달한다.
메시지를 받은 장군들은 나머지 장군들에게 사령관으로부터 받은 메시지를 전달한다. (장군들은 서로 연결되어 있다.)
일정 시간 이후 각 장군들은 자신이 받은 메시지를 종합하여 "공격" 이냐 "후퇴"냐를 결정하여 명령을 이행한다. (동기화)

Risk Factors: 합의를 방해하는 요소들

메신저가 메시지를 전달하는 도중에 실패할 확률이 있다. (적군에게 포획당하거나 살해당하거나..)
장군들 중에는 배신자가 섞여 있을 수 있다.
1. 배신자는 행동에 아무런 제약이 없다.
2. 사령관도 배신자가 될 수 있다.

Pass Conditions: 어떻게 해야 전쟁에서 승리할 수 있을까?

만약 사령관이 "공격" 명령을 하달했을 때 메시지를 받은 장군들이 모두 "공격" 을 이행해야 전쟁에서 승리할 수 있다. 그렇기 때문에 배신자의 방해가 있더라도 모두 같은 결정을 할 수 있어야 한다. 이에 저자는 추가적으로 아래의 두 가지 조건을 제시한다. (IC, Interactive Consistency)

IC1: 배신자가 아닌 모든 장군들은 같은 명령을 이행한다.
IC2: 만약 사령관이 배신자가 아니라면, 배신자를 제외한 모든 장군들은 사령관의 명령을 이행한다.

BGP가 생길 수 있는 최소 조건은 아래와 같이 합의 대상이 3명일 때이다.

V_i가 i번째 장군이 받은 메시지의 집합이라고 할 때, 일정 시간 이후 배신자가 아닌 장군들은 자신이 받은 메시지 내용으로 "공격"과 "후퇴" 중 하나를 선택하여 이행한다. (과반수 우선 선택 기준)

사령관이 배신자일 경우: 사령관이 보낸 메시지는 진하게 표시
- V_1 = {"공격", "후퇴"} -> 장군 1은 "공격" 으로 결정
- V_2 = {"후퇴", "공격"} -> 장군 2는 "후퇴" 로 결정
장군 2가 배신자일 경우: 사령관이 보낸 메시지는 진하게 표시
- V_1 = {"공격", "후퇴"} -> 장군 1은 "공격" 으로 결정

m의 수를 늘려서 (m = 2, 3, ...)장군의 수가 총 3m일 때를 생각해보면 배신자 집단에 사령관이 포함될 경우 정직한 장군들이 잘못된 결정을 하도록 조작이 가능함을 알 수 있다.

안정적인 합의를 위해서는 장군들은 모두 같은 알고리즘을 통해 메시지를 전달하고, 전달받은 메시지에서 "공격"이나 "후퇴" 중 일치된 하나의 메시지를 도출할 수 있어야 한다. 이를 위해 저자는 두 가지 알고리즘을 제시한다.

Solution 1: Oral Message (OM)

Assumptions

장군들이 보낸 모든 메시지는 올바르게 전달된다.
메시지를 받은 장군들은 누가 보낸 메시지인지 알 수 있다.
더 이상 메시지가 도착하지 않음을 인지할 수 있다.

Algorithm OM(m)

BGP를 해결하기 위해 저자가 제안하는 OM 알고리즘은 아래와 같다.

OM(0)
1. 사령관은 모든 장군들에게 메시지 ("공격" 과 "후퇴" 중 하나)를 보낸다.
2. 모든 장군들은 사령관이 보낸 메시지를 수신하여 "공격" 과 "후퇴" 중 하나를 결정한다.
OM(m), m은 배신자의 수
1. 사령관은 모든 장군들에게 메시지 ("공격" or "후퇴" 중 하나)를 보낸다.
2. 각 i에 대해 사령관에게 장군 i가 받은 메시지를 v_i라고 한다. 만약 장군 i가 아무런 메시지를 받지 못했다면 그 장군은 "후퇴"로 결정한다. 장군 i는 OM(m-1)의 사령관 역할로 v_i를 다른 (n-2)명의 장군들에게 보낸다.
3. 장군들은 메시지를 받고 majority(v_1, v_2, ..., v_(n-1))을 통해 "공격"과 "후톼" 중 하나를 결정한다.

majority()
장군이 받은 메시지에서 "공격"과 "후퇴" 중 많은 쪽을 택한다. 만약 아무런 메시지를 받지 못했다면 "후퇴"한다.
만약 1번에 과반수를 선택할 수 없는 경우, 중앙값을 선택한다. (메시지가 순서 집합의 형태일 때)

앞에서 장군의 수가이 3m 이하일 경우에는 BGP를 해결할 수 없음을 얘기했기 때문에, 여기서는 3m+1일 경우를 가정하여 알고리즘 OM을 설명한다.

OM(1), m = 1일 경우 장군의 수는 사령관 포함 4명

사령관이 배신자일 경우: 사령관이 보낸 메시지는 진하게 표시
- V_1 = {"공격", "후퇴", "공격"} -> 장군 1은 "공격" 으로 결정
- V_2 = {"후퇴", "공격", "공격"} -> 장군 2는 "공격" 으로 결정
- V_3 = {"공격", "후퇴", "공격"} -> 장군 3은 "공격" 으로 결정
장군 2가 배신자일 경우: 사령관이 보낸 메시지는 진하게 표시
- V_1 = {"공격", "공격", "후퇴"} -> 장군 1은 "공격" 으로 결정
- V_3 = {"공격", "공격", "후퇴"} -> 장군 3은 "공격" 으로 결정

두 가지 경우 모두 배신자가 아닌 장군들이 모두 "공격"으로 결정하였으므로 합의에 성공하여 전쟁에 승리할 것이라 예상할 수 있다.

위와 같이 알고리즘 OM은 n ≥ 3m+1일 때 안전하게 사용할 수 있지만 재귀적으로 동작하기 때문에 배신자의 수가 늘어날 수록 메시지의 전달 과정이 지수적으로 (기하급수적으로) 늘어난다. 예를 들어, 배신자가 3명이라면 OM(3) <- OM(2) <- OM(1) <- OM(0) 과정을 거친다. 즉, OM 알고리즘을 (m+1)번 거쳐야 합의에 도달할 수 있다는 의미이다. 이에 따른 복잡도는 아래 표와 같이 나타낼 수 있다.

배신자의 수 (m)

복잡도 (n은 장군의 수)

O(n)

O(n^2)

O(n^3)

O(n^4)

...

Solution 2: Signed Message (SM)

메시지에 각자의 서명을 붙여서 보내면 장군의 수가 적어도 성공적으로 합의할 수 있지 않을까?

Assumptions (Solution 1의 가정에 추가)

배신자가 아닌 장군의 서명은 위조될 수 없으며, 메시지를 수신한 장군은 서명된 메시지의 내용이 변경되었을 경우 인지할 수 있다.
작성된 서명은 누구나 검증 가능하다.

Signed Message

서명한 메시지는 다음과 같이 정의한다. 사령관을 포함한 장군들은 각자의 식별자 (ID)를 가진다.

v:0 -> 사령관이 서명한 메시지 v
- v (value: "공격" or "후퇴" 둘 중 하나의 값을 가짐): 메시지 내용
- 0: 사령관의 ID
v:j:i -> 장군 i와 장군 j의 서명이 담긴 메시지 v
- j: 메시지 v에 서명한 장군 j
- i: 메시지 v:j에 서명한 장군 i

Algorithm SM(m)

사령관은 모든 장군들에게 서명하고 v:0을 보낸다.
각 i에 대해,
1. 장군 i가 처음 사령관의 메시지 v:0를 받았다면,
  1. V_i = {v}
  2. v:0에 자신의 서명을 붙여서 v:0:i를 다른 장군들에게 전달한다.
2. 장군 i가 메시지 v:0:j_1, j_2, … j_k 를 받았는데, V_i에 v가 없다면 (i.e., 계속 “공격” 을 받았는데, 방금 온 메시지는 “퇴각” 이라면)
  - V_i에 v를 추가한다.
  - j_1~j_k를 제외한 다른 장군들에게 메시지 v:0:j_1, j_2, … j_k:i를 전달한다.
더 이상 메시지가 오지 않을 때, choice(V_i)의 값을 실행하여 공격할지 퇴각할 지 결정한다.

앞에서 배신자가 1명일 때 장군이 4명 이상이라면 합의가 가능함을 보였으니 (n ≥ 3m+1) 3명의 장군이 합의하는 경우를 생각해보자. 사령관이 합의를 방해하기 위해 한 명에게는 "공격" 이라고 전달하고, 다른 한 명에게는 "퇴각"이라고 지시한다. 장군들은 아직까지 사령관이 배신자인지 모르기 때문에 다른 장군에게 받은 메시지를 그대로 전달한다. 배신자가 아닌 장군 1과 2가 받은 메시지는 아래와 같다.

V_1 = {"공격" :0, "후퇴": 0:2} -> 장군 1은 "후퇴"로 결정
V_2 = {"후퇴" :0, "공격": 0:1} -> 장군 2는 "후퇴"로 결정

장군 1과 2는 두 번째로 받은 메시지를 통해 사령관이 배신자임을 알고 "공격" 명령을 수행하지 않을 것이다. 배신자가 아닌 두 장군이 "후퇴"라는 합의를 얻었기 때문에 IC1을 만족했다고 할 수 있다. (IC2는 사령관이 배신자가 아닌 경우에만 고려)

choice (V_1) = choice (V_2)

또한 장군 1, 2 중 하나가 배신자라면 두 번째 메시지에 사령관의 서명이 없었을 것이다. (알고리즘 SM에서의 첫 번째 가정에 의해 배신자가 아닌 장군의 서명은 위조할 수 없기 때문에)

만약 앞의 케이스에 배신자 장군 3을 추가해도 SM(m)으로 합의에 성공할 수 있을까? SM(1)과 거의 비슷하나, 장군 1은 장군 2에게 메시지 {"후퇴" :0:2}를 받고 장군 3에게 메시지 {"후퇴": 0:2:1}을 보내는 과정과 장군 2가 장군 1에게 메시지 {"공격": 0:1}을 받고 장군 3에게 메시지 {"공격": 0:1:2}를 보내는 두 과정이 추가된다.

장군 1, 2가 받은 메시지와 최종 결정은 아래와 같다.