비잔틴 장애 허용

“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야하며, 또 모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 사토시 나카모토와 비트코인 개발 작업을 협업했던 제임스 A 도날드가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도날드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘두 장군의 문제’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘비잔틴 장군의 문제’로 확장이 된다.

분산원장 체계는 제대로 돌아가기 위해서 원장을 공유하는 참여자들이 정직하게 행동해야 하며 이를 보장할 수 있는 방법이 있어야 하며, 누군가 속이려 들더라도 모두가 지닌 원장은 같은 내용을 유지해야 하는 방법 또한 존재하야 한다. 이런 골칫거리가 비트코인에서의 비잔틴 장군의 문제이다.

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

두 장군의 문제

두 장군의 문제(Two Generals Problem)는 1972년 등장한 일종의 가상 실험이다. 이 실험에서 가정은 1. 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양 옆에 주둔한 상황이며 2. 두 장군은 적군을 점령하기 위해 두 부대가 같은 날, 같은 시각에 공격을 하려 한다. 3. 이때 연락을 주고받아야 하는데 이를 담당하는 연락병은 직접 적군의 도시를 통과해야하며 4. 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정 하에 진행이 된다.

장군A는 B에게 메시지를 보냈지만 잘 전달 됐는지 확신을 하지 못한다. 이에 B가 메시지를 잘 받았으면 A에게 확인 답장을 보내야 하는데 B도 마찬가지로 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다. 이에 B를 안심시키고 함께 공격하기 위해 A가 답장을 받았다고 재답장을 해야 하지만 이 역시 B에게 잘 도달했는지 장담하지 못한다. 결국 이는 두 장군이 같은 수준의 합의에 도달할 수 없고 이러한 불확실성은 결국 함께 적군의 도시를 공격할 수 없다는 의미이다. 이후 이 문제는 실제로 해결이 불가능한 것으로 증명됐으며 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 같은 내용의 거래기록을 갖는데 까지 도달하지 못한다는 의미이다.

비잔틴 장군의 문제

비잔틴 장군(Byzantine Generals Problem)의 문제는 1982년 래슬리 램포트, 마샬 피즈가 함께 쓴 논문에서 소개 된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. 비트코인 상에서는 참여자가 수 만 명이 될 수 있기 때문에 사토시 나카모토 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.

비잔틴 장군의 문제는 광활한 영토 각 지역마다 장군들이 통치하는 것을 가정한다. 이웃나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 높아지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.