비잔티움 장애 허용

위키백과, 우리 모두의 백과사전.
둘러보기로 가기 검색하러 가기

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

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

비잔티움 장군 문제[편집]

비잔티움 장군 문제는 레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 처음 언급됐다.[1] 이 논문에서 저자들은 적군의 도시를 공격하려는 비잔티움 제국군의 여러 부대가 지리적으로 떨어진 상태에서 각 부대의 지휘관들이 (중간에 잡힐지도 모르는) 전령을 통해 교신하면서 공격 계획을 함께 세우는 상황을 가정하고 있다. 이 부대의 지휘관 중 일부에는 배신자가 섞여있을 수 있고, 배신자는 규칙을 충실히 따르는 충직한 지휘관들과 달리 규칙에 얽매이지 않고 마음대로 행동할 수 있다. 이 때 배신자의 존재에도 불구하고 충직한 지휘관들이 동일한 공격 계획을 세우기 위해서는 충직한 지휘관들의 수가 얼마나 있어야 하며, 이 지휘관들이 어떤 규칙을 따라 교신해야 하는지에 대한 문제가 비잔티움 장군 문제다.

이름의 기원[편집]

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

초기 솔루션[편집]

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명이 배반자인 경우 오직 이고 커뮤니케이션이 동시에 이루어져야만(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 암호화폐 시스템인 비트코인이다. 비트코인 네트워크는 병렬적으로 작동하여 작업 증명(채굴이라고도 불림) 형태의 해시캐시 체인을 형성한다. 작업 증명 체인은 비잔티움 실패를 해결하고 일관적인 시스템을 구성할 수 있게 한다.

참고 문헌[편집]

  1. L. Lamport, R. Shostak, M. Pease, The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems, v. 4 n. 3, pp. 382-401, July 1982.
  2. The Writings of Leslie Lamport