비잔틴 장군 문제와 BFT: 블록체인 합의의 첫 원리
비잔틴 장군 문제를 스토리와 도식으로 풀어 설명하고, BFT의 요건·조건·한계를 간결히 정리했습니다. PoW/PoS가 어떻게 BFT를 만족하는지도 비교합니다.
독자는 이 글을 통해 비잔틴 장애와 BFT의 핵심 구조를 빠르게 이해하고, 분산 원장에서 합의가 왜·어떻게 안전하게 성립되는지 실전 감각으로 파악합니다.
비잔틴 장애, 무엇이 문제인가
분산 시스템은 서로를 완전히 신뢰하지 못하는 노드로 구성됩니다. 일부는 고장 나거나 악의적일 수 있죠. 그럼에도 정직한 노드들이 같은 결정에 도달해야 서비스가 지속됩니다. 이때 나타나는 근본 난제를 비잔틴 장애라 부르고, 이를 극복하는 체계가 *BFT(Byzantine Fault Tolerance)*입니다.
BFT의 목표는 간단합니다. 일부 노드가 거짓을 말해도, 나머지가 올바른 결론에 일관되게 수렴하도록 만드는 것.
장군과 전령: 스토리로 이해하는 핵심
고전적 비유인 비잔틴 장군 문제는 서로 떨어진 장군들이 동시에 공격/후퇴를 합의해야 승리하는 상황을 설정합니다. 전령이 배신하거나 메시지를 변조하면 타이밍이 어긋나 작전이 실패합니다.
이 문제를 체계화한 레슬리 램포트는 다음을 제시했습니다.
- 3n+1 조건: 최대 n명의 배신자가 있어도 합의를 보장하려면 노드는 최소 3n+1개여야 한다.
- 신뢰 가능한 전달 전제: 전송된 메시지는 수신자가 그대로 인지(위변조 검출 가능)할 수 있어야 한다.
- 정직성 보존: 정직한 노드는 동일한 입력에 같은 출력을 내야 한다(일관성).
핵심: “일부가 어지럽혀도, 전체는 수렴한다.” 이것이 비잔틴 환경에서의 합의 조건입니다.
BFT의 두 요건: 합의와 정당성
- 합의(Agreement): 모든 정직한 노드는 동일한 값에 동의해야 합니다.
- 정당성(Validity): 그 값은 유효한 규칙을 충족해야 합니다. 악의적 메시지로 잘못된 결정을 내리면 안 됩니다.
아래 표는 블록체인에서 두 요건이 어떻게 구현되는지 요약합니다.
| 요소 | 의미 | 블록체인에서의 구현 예 |
|---|---|---|
| 합의 | 정직 노드가 같은 결정 | 체인 선택 규칙, 다수 증명 누적 |
| 정당성 | 규칙상 유효한 값 | 유효 블록/트랜잭션 검증 |
메시지의 전파를 바꾸면 결과가 달라진다
단일 경로로만 전달되면 배신자가 시간·내용 왜곡을 유발합니다. 반대로, 각 노드가 모든 노드에게 브로드캐스트하고, 받은 메시지를 서명·다수결로 검증하면 왜곡이 격리됩니다.
예시처럼 A, C, D가 동일한 “3시에 공격”으로 수렴하면, B가 혼선을 유도해도 다수 정직 노드가 올바른 결론을 채택합니다.
팁: 동일 메시지를 여러 경로로 확인하는 중복 경로 + 서명은 비잔틴 환경에서 신뢰를 합성하는 대표적 기법입니다.
PoW와 PoS는 어떻게 BFT를 달성하나
블록체인은 전통적 PBFT 류의 합의와 달리, 확률적 최종성 또는 경제적 보증으로 BFT를 달성합니다.
PoW(작업증명)
- 아이디어: 계산 난이도로 블록을 만들 권리를 희소하게 배분.
- BFT 기여: 공격자가 다수 해시 파워를 갖지 못하는 한, 가장 긴(누적 난이도 최대) 체인이 정직한 기록을 대표.
- 특성: 최종성은 상대적(확률적). 더 많은 확정 블록이 쌓일수록 역전 비용 급증.
PoS(지분증명)
- 아이디어: 스테이킹된 지분이 블록 제안/검증 권한을 부여.
- BFT 기여: 잘못된 행동은 슬래싱으로 경제적 손실을 초래하므로 정직 행동이 내쉬 균형.
- 특성: 프로토콜 설계에 따라 빠른 최종성(예: 체크포인트, 파이널라이저) 제공.
| 합의 방식 | BFT 달성 원리 | 장점 | 주의점 |
|---|---|---|---|
| PoW | 계산 비용(희소 자원) | 검증 단순 | 에너지 비용, 51% 공격 가정 |
| PoS | 경제적 담보(지분) | 빠른 최종성 | 초기 분배·슬래싱 설계 중요 |
주의: 어떤 방식이든 네트워크 파티션, 시빌 공격, 타임스탬프 조작 등 환경 가정을 명시하고, 그 한계에서 안전성을 평가해야 합니다.
언제 3n+1이 필요한가, 그리고 한계
고전적 동기식 BFT(예: PBFT)는 명시적 메시지 합의를 하므로 3n+1 조건이 직접 적용됩니다. 반면, 체인 기반 합의(예: PoW/PoS)는 블록 확정 규칙으로 유사 BFT 보증을 제공하며, 파라미터(확정 깊이, 체인 선택 규칙)로 안전성/활성도 균형을 맞춥니다.
설계자는 합의, 정당성, 활성도(liveness) 사이의 트레이드오프를 평가해야 하며, 네트워크 지연·노드 오프라인을 고려한 실천적 파라미터를 함께 제시해야 합니다. 자세한 큰 그림은 내부 글 **타임스탬프 역사**에서 이어집니다.
