비잔티움 장애 허용

비잔티움 장애 허용(영어: Byzantine Fault Tolerance)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티움 장군 문제(영어: Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래다.

이 분야의 연구는 비잔티움 장애(영어: Byzantine faults)라고 불리는 시스템에 생길 수 있는 임의의 장애를 견딜 수 있는 시스템을 만들기 위한 것이 목적이다. 이 비잔티움 장애는 단지 시스템이 멈추거나 에러 메시지를 내보내는 것과 같은 장애 뿐 아니라, 잘못된 값을 다른 시스템에 전달하는 등의 좀 더 그 원인을 파악하기 어려운 장애들까지 포함한다. 제대로 구현된 비잔티움 장애 허용 시스템에서는 미리 정해진 정도를 넘지 않는 부분에서 어떠한 형태의 장애가 있더라도 정확한 값을 전달할 수 있다.

비잔티움 장군 문제

비잔티움 장군 문제는 레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 처음 언급됐다. 이 논문에서 저자들은 적군의 도시를 공격하려는 비잔티움 제국군의 여러 부대가 지리적으로 떨어진 상태에서 각 부대의 장군들이 (중간에 잡힐지도 모르는) 전령을 통해 교신하면서 공격 계획을 함께 세우는 상황을 가정하고 있다.

충직한 장군들은 합의된 규칙을 충실하게 따르며 이 외의 행동은 하지 않는다. 그러나 전체 장군 중 일부는 배신자일 수 있으며, 배신자는 규칙에 얽매이지 않고 마음대로 행동할 수 있다. 이 때 배신자의 존재에도 불구하고 충직한 장군들이 동일한 공격 계획을 세우기 위해서는 충직한 장군들의 수가 얼마나 있어야 하며, 장군들이 어떤 규칙을 따라 교신해야 하는지에 대한 문제가 비잔티움 장군 문제다.

사실 계획이 합리적인지도 판단한다면 더 좋으나, 이는 판단할 수 없으므로 포기하고, 오직 다수의 합의를 이끌어내는 것에만 초점을 맞춘다.

보장해야 하는 것은 아래와 같다.

1. 모든 충직한 장군들은, 같은 정보를 획득해야 한다. (누가 배신자인지 모르기 때문에, x번째 장군이 직접 보낸 메시지를 받았다 하더라도, 바로 사용할 수 없다.)
2. 만약 n번째 장군이 충직하다면, n번째 장군이 보낸 값은 충직한 장군들한테 같게 보내져야 한다.

이름의 기원

레슬리 램포트는 이 문제의 장군들의 국적을 놓고 고민하던 중 당시 동구 공산국가 중 가장 고립된 국가였던 알바니아를 장군들의 국적으로 한다면 주변의 누구도 불쾌해하지 않을 것이라 생각해서 당시 논문의 초안을 "알바니아 장군 문제"라는 제목으로 작성했다. 하지만 이 초안을 읽은 잭 골드버그가 알바니아인이 꼭 알바니아에만 사는 것은 아니라고 지적했고, 이 말에 램포트는 아무도 불쾌해하지 않을 비잔티움 제국으로 장군들의 소속을 바꿨다.

초기 솔루션

1982년 Lamport, Shostak, Pease가 여러 솔루션을 제시했다. 이들은 비잔티움 장군 문제가 충직한 부관(Lieutenant) 모두가 지휘관(Commander)이 내린 명령과 일치하게, 같은 행동을 해야한다는 "Commander and Leutenants" 문제로 좁혀질 수 있다고 말했다.

• 첫 번째 솔루션은 전달된 메시지가 위조될 수도 있다는 시나리오를 가정한다. 하지만 이 때 배반한 장군의 수가 전체 장군 수의 3분의 1 이상과 같거나 넘지 않는 이상 비잔티움 장애 허용으로 간주된다. 3분의 1 혹은 그 이상의 배반자가 있을 경우는 하나의 지휘관과 두 부관 문제(one Commander and two Lieutenants problem) 문제로 간주될 수 있으며, 즉, 지휘관이 배반자인 경우 해결할 수 없다. 한 명의 배반자 지휘관 A와 두 부관 B, C가 있다고 가정하자. A가 B에게 공격하라고, C에게는 후퇴하라고 명령하는 경우 A의 메시지를 전달받은 B, C는 누가 배반자인지 알 수 없다. A가 아니라 부관 B와 C가 배반했을 수도 있기 때문이다. 따라서 n명의 지휘관이 있고 그 중 t명이 배반자인 경우 오직 $n>3t$이고 커뮤니케이션이 동시에 이루어져야만(synchronous; bounded delay) 솔루션이 있다.
• 두 번째 솔루션은 메시지의 서명이 위조될 수 없다는 전제로 한다. 보안이 중요한 시스템(security-critical system)에서 디지털 서명은(대개 현대의 컴퓨터 시스템에서 공개 키 암호화로 구현됨) 임의의 배반자 지휘관이 있는 상황에서 비잔틴 장애 허용을 제공한다. 하지만 안전이 중요한 시스템(safety-critical system)에서 CRCs 등은 대부분의 상황에서 적용될 수 있는 간단한 에러를 찾는 코드를 낮은 비용에 제공하며, 이는 비잔틴 장애와 비잔틴 장애가 아닌 것 모두에 가능하다. 따라서 암호화된 디지털 서명 방식은 별도의 보안 위협이 있지 않은 한 안전이 중요한 시스템에서 좋은 선택은 아니다.
• 또한 Lamport, Shostak, Pease는 앞서 서술한 두 솔루션 외에도 모든 지휘관이 서로 소통할 수 없는 경우 등 다양한 경우에 대해서도 서술했다.

1980년 비잔틴 장애 허용이 도입된 이후로 Draper's FTP, Honeywell's MMFCS. SRI's SIFT 등 여러 시스템 구조가 디자인되었다.

실용적 비잔티움 장애 허용

P2P 분산 원장 기술에서 폐쇄형 합의 기준이 비잔티움 장애 허용을 따른다. 활용분야는 결제시스템, 신원 및 문서 인증, 무역금융, 스마트계약 등이 있다.

활용 사례

활용되고 있는 비잔티움 장애 허용의 예시 중 하나는 P2P 암호화폐 시스템인 비트코인이다. 비트코인 네트워크는 병렬적으로 작동하여 작업 증명(채굴이라고도 불림) 형태의 해시캐시 체인을 형성한다. 작업 증명 체인은 비잔티움 실패를 해결하고 일관적인 시스템을 구성할 수 있게 한다.