위키원
비잔틴 장애 허용
“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야하며, 또 모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 사토시 나카모토와 비트코인 개발 작업을 협업했던 제임스 A 도날드가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도날드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘두 장군의 문제’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘비잔틴 장군의 문제’로 확장이 된다.
분산원장 체계는 제대로 돌아가기 위해서 원장을 공유하는 참여자들이 정직하게 행동해야 하며 이를 보장할 수 있는 방법이 있어야 하며, 누군가 속이려 들더라도 모두가 지닌 원장은 같은 내용을 유지해야 하는 방법 또한 존재하야 한다. 이런 골칫거리가 비트코인에서의 비잔틴 장군의 문제이다.
여기서 비잔티움 장애 허용(Byzantine Fault Tolerance)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티움 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래다.
특징
비잔티움 장애
첫번째 솔루션은 전달된 메시지가 위조될 수 있다는 시나리오로 시작한다. 하지만 이 때 배반한 장군의 수가 전체 장군 수의 3분의 1과 같거나 넘지 않는 경우, 비잔티움 장애에 해당하는 것으로 한다. 3분의 1 또는 그 이상의 배반자가 있으면, 하나의 지휘관과 두 중위 문제(one Commander and two Lieutenants problem)로 간주할 수 있으며, 이처럼 지휘관이 배반자인 경우는 해결할 수 없다. 한 명의 배반자 지휘관 A와 두 중위 B, C가 있다고 가정하자. A가 B에게 공격하라고, C에게는 후퇴하라고 명령하는 경우 A의 메시지를 전달받은 B, C는 누가 배반자인지 알 수 없다. A가 아니라 중위 B와 C가 배반했을 수도 있기 때문이다. 따라서 n명의 지휘관이 있고 그중 t명이 배반자인 경우 오직 {\displaystyle n>3t} {\displaystyle n>3t}이고 커뮤니케이션이 동시에 이루어져야만(synchronous; bounded delay) 솔루션이 있다.
비잔티움 장애 허용
두 번째 솔루션은 메시지의 서명이 위조될 수 없다를 가정한다. 보안이 중요한 시스템(security-critical system)에서 디지털 서명은(공개 키 암호화로 형태로 구현) 임의의 배반자 지휘관이 있는 상황에서 비잔틴 장애 허용을 제공한다. 하지만 안전이 중요한 시스템(safety-critical system)에서 CRCs 등은 대부분의 상황에서 적용될 수 있는 간단한 에러를 찾는 코드를 낮은 비용에 제공하며, 이는 비잔틴 장애와 비잔틴 장애가 아닌 것 모두에 가능하다. 따라서 암호화된 디지털 서명 방식은 별도의 보안 위협이 있지 않은 한, 시스템에서 안전이 중요한 역할은 아니다. 또한 Lamport, Shostak, Pease는 앞서 서술한 두 솔루션 외에도 모든 지휘관이 서로 소통할 수 없는 경우 등 다양한 경우에 관해서도 서술했다.
각주
참고자료
- L. Lamport, R. Shostak, M. Pease, "The Byzantine Generals Problem", people.eecs.berkeley.edu, 1982-06
같이 보기
| ||||||||||||||||||||||||||||||||||
