비잔틴 장애 허용 (Byzantine Fault Tolerance)
쉽게 풀면
고전적인 "비잔틴 장군 문제"를 생각해보면 이해가 쉽습니다. 여러 장군이 각자 다른 위치에서 하나의 도시를 포위하고 있고, 전령을 통해서만 서로 "공격" 또는 "후퇴" 신호를 주고받을 수 있습니다. 그런데 이 장군들 중 일부가 배신자여서, 어떤 장군에게는 "공격"이라 말하고 다른 장군에게는 "후퇴"라고 거짓말을 할 수도 있습니다. 이런 상황에서도 배신자가 아닌 정상적인 장군들끼리는 결국 모두 같은 결정(공격이면 공격, 후퇴면 후퇴)에 도달해야 승리할 수 있습니다. 비잔틴 장애 허용 시스템은 바로 이런 문제를 컴퓨터 네트워크에 적용한 것으로, 일부 노드가 단순히 고장나서 응답하지 않는 것을 넘어 아예 거짓된 메시지를 퍼뜨리더라도, 정상 노드들만큼은 서로 일관된 결론에 도달할 수 있도록 설계된 시스템을 말합니다.
왜 중요한가
여러 대의 컴퓨터가 협력해 하나의 서비스를 제공하는 분산시스템에서는, 일부 노드가 단순히 고장나는 것뿐 아니라 해킹당하거나 조작되어 의도적으로 잘못된 정보를 퍼뜨리는 상황까지 견뎌내야 신뢰할 수 있습니다. 그래서 비잔틴 장애 허용은 분산 합의(consensus), 블록체인, 클라우드 인프라의 신뢰성 연구에서 핵심적으로 다뤄지는 주제입니다. 최근에는 여러 참여자가 데이터를 나눠 갖고 학습하는 연합학습이나 다중 에이전트 시스템처럼, 신뢰할 수 없는 참여자가 섞여 있을 수 있는 새로운 응용 분야로도 그 논의가 확장되고 있습니다.
핵심 정리
- 비잔틴 장애는 고장 난 구성요소가 관찰자마다 서로 다른 신호를 주어, 다른 쪽에서는 그것이 고장인지 알기 어려운 문제입니다. 이름은 ‘비잔틴 장군 문제’라는 비유에서 왔고, 이 비유는 Lamport, Shostak, Pease(1982)의 논문이 소개했습니다.
- 메시지에 서명이 없는 모형에서는, 합의를 이루려면 전체 노드 수가 불성실(결함) 노드 수의 3배보다 커야 한다고 알려져 있습니다. 결함 노드가 f개이면 전체는 최소 3f+1개입니다. 이 결과는 Pease, Shostak, Lamport(1980)의 논문에 실렸습니다.
- 위조할 수 없는 디지털 서명을 쓸 수 있는 경우는 조건이 달라지며, 이 사례도 1980년 논문에서 다뤘습니다.
- 실용적인 알고리즘의 예로 Castro와 Liskov의 PBFT(실용적 비잔틴 장애 허용)가 있으며, 이 알고리즘을 능동 복구와 함께 다룬 논문이 Castro와 Liskov(2002)입니다.
- 결함허용 중 비잔틴 장애는 가장 일반적이고 어려운 부류로 설명됩니다. 결함 노드가 어떤 오류든 만들어 낼 수 있다고 보기 때문입니다.
예시로 보기
서명이 없는 모형에서 f개의 비잔틴 노드를 견디려면 필요한 최소 노드 수(n ≥ 3f+1)를 계산하면 다음과 같습니다.
| 견딜 결함 노드 수 f | 필요한 최소 노드 수 3f+1 | 부족한 경우(3f) |
|---|---|---|
| 1 | 4 | 3 |
| 2 | 7 | 6 |
| 3 | 10 | 9 |
| 4 | 13 | 12 |
예를 들어 4개 노드는 1개의 비잔틴 노드까지, 3개 노드는 1개도 견디지 못한다는 뜻입니다(위 모형의 조건에서). 블록체인의 작업증명처럼 다른 방식의 합의도 있으므로, 이 조건이 모든 합의에 적용되는 것은 아닙니다.
자주 하는 오해
| 오해 | 바로잡기 |
|---|---|
| 비잔틴 장애 허용은 블록체인에서 나온 개념이다. | 1970년대 말 Shostak이 SIFT 프로젝트에서 정식화한 문제로, 1980년과 1982년 논문에서 이론이 정리되었습니다. 블록체인보다 훨씬 오래된 개념입니다. |
| 과반수가 동의하면 합의가 안전하다. | 서명이 없는 모형에서는 결함 노드가 전체의 3분의 1 이상이면 합의를 보장할 수 없습니다. 과반수 정도로는 충분하지 않습니다. |
| 충돌 장애만 견디는 알고리즘이면 충분하다. | 충돌 장애(노드가 멈추는 것)는 가장 단순한 부류이고, 비잔틴 장애는 거짓 메시지까지 포함하는 가장 일반적인 부류입니다. |
논문에서는 이렇게 쓰입니다
실제 논문에서
이 용어를 직접 쓴 국내 논문 문장을 아직 수집하지 못했습니다. 수집되는 대로 출처와 함께 싣겠습니다.
예시 문장
아래는 용어의 쓰임을 보여 주려고 만든 예시로, 실제 논문에서 가져온 문장이 아닙니다.
이 문장은 네트워크에 참여한 노드 중 일부가 고장나거나 악의적으로 행동하더라도, 나머지 다수의 정상 노드들이 서로 다른 결론에 도달하지 않고 하나의 합의된 상태로 수렴한다는 것을 수학적으로 보였다는 뜻입니다. PBFT(Practical Byzantine Fault Tolerance)와 같은 프로토콜이 대표적인 구현 사례이며, 블록체인의 합의 알고리즘 설계에도 널리 응용됩니다.
연합학습(federated learning) 분야에서는 참여 기기 중 일부가 악의적으로 조작된 학습 결과를 서버에 보내 전체 모델 학습을 방해할 수 있습니다. 이 문장은 그런 상황에서도 정상 참여자들의 정보만으로 모델이 올바르게 학습되도록 하는 방어 기법을 다루고 있다는 의미이며, 비잔틴 장애 허용의 개념이 전통적인 분산시스템을 넘어 기계학습 영역으로 확장된 사례입니다.
블록체인 연구에서는 채굴자나 검증자 노드 일부가 부정 행위를 저지르더라도 전체 원장(ledger)의 일관성이 깨지지 않아야 합니다. 이 문장은 새로운 합의 알고리즘이 기존 방식만큼 비잔틴 결함에 안전하면서도 더 효율적임을 실험으로 입증했다는 뜻입니다.
조금 더 깊게 보면
비잔틴 장애 허용을 다루는 논문에서는 흔히 전체 노드 수 n과 허용 가능한 비잔틴 노드 수 f 사이의 관계(예: n이 3f보다 커야 안전성을 보장할 수 있다는 식의 조건)를 제시하며 프로토콜의 이론적 한계를 증명합니다. 또한 PBFT 계열 프로토콜은 여러 라운드에 걸친 메시지 교환(pre-prepare, prepare, commit 등)을 통해 노드 간 합의를 확정하는 방식을 취하며, 이 과정에서 발생하는 통신 복잡도(메시지 교환 횟수)가 성능 평가의 핵심 지표로 쓰입니다. 최근 연구들은 이러한 통신 비용을 줄이기 위한 다양한 변형 프로토콜(예: 리더 기반 방식, 샤딩 기법과의 결합)을 제안하고 있으므로, 논문을 읽을 때는 어떤 조건에서 안전성(safety)과 활성(liveness)을 보장하는지, 그리고 그 대가로 어떤 성능 지표를 희생하는지를 함께 살펴보는 것이 중요합니다.
주의할 점
비잔틴 장애 허용은 노드가 단순히 멈추거나 응답하지 않는 "충돌 장애(crash fault)"보다 훨씬 강한 가정, 즉 노드가 의도적으로 거짓된 메시지를 보낼 수 있다는 가정까지 다룹니다. 그래서 충돌 장애 정도만 다루는 일반적인 결함허용 기법에 비해 훨씬 많은 노드 간 통신과 계산 비용이 필요하다는 점에 유의해야 합니다.
헷갈리기 쉬운 용어
분산 시스템의 장애와 합의 관련 용어입니다.
| 용어 | 한 줄 설명 |
|---|---|
| 결함허용 | 일부 구성요소가 고장 나도 시스템이 동작을 이어 가는 성질 |
| 충돌 장애(fail-stop) | 노드가 멈추고 다른 노드가 그것을 알아챌 수 있는 가장 단순한 장애 |
| 비잔틴 장애 허용 | 노드가 임의의, 심지어 거짓된 메시지를 보내도 합의에 이르는 성질 |
| 합의 알고리즘 | 여러 노드가 하나의 값에 동의하도록 하는 절차. 비잔틴 장애 허용은 그 조건의 하나 |
| CAP 정리 | 일관성·가용성·분할 내성의 동시 충족 한계를 말하는 정리로, 비잔틴 장애와는 다른 축의 문제 |
참고 문헌
- Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3), 382–401.
- Pease, M., Shostak, R., & Lamport, L. (1980). Reaching agreement in the presence of faults. Journal of the ACM, 27(2), 228–234.
- Castro, M., & Liskov, B. (2002). Practical Byzantine fault tolerance and proactive recovery. ACM Transactions on Computer Systems, 20(4), 398–461.
표의 기준값은 위 문헌에 근거한 관례이며, 분야·학술지마다 다른 기준을 쓸 수 있습니다.