비잔틴 장군 문제, 믿을 수 없는 이들 사이의 합의

비잔틴 장군 문제는 일부 구성원이 거짓말을 하거나 고장 날 수 있는 상황에서, 나머지가 어떻게 하나의 결정에 확실히 합의할 수 있느냐를 묻는 문제다. 1982년 레슬리 램포트와 동료들이 장군들의 비유로 정리했다. 이 문제의 답은 은행 서버, 항공기 제어 장치, 그리고 블록체인처럼 여러 컴퓨터가 함께 하나의 기록을 지켜야 하는 시스템의 기초가 되었다.

장군들은 무엇을 고민하나

여러 명의 장군이 각자 군대를 이끌고 적의 도시를 둘러싸고 있다. 이들은 함께 공격하거나 함께 후퇴해야 한다. 일부만 공격하면 전멸한다. 장군들은 서로 떨어져 있어 전령을 통해서만 연락할 수 있다.

문제는 장군들 가운데 배신자가 섞여 있을 수 있다는 점이다. 배신자는 어떤 장군에게는 공격하자고, 다른 장군에게는 후퇴하자고 서로 다른 말을 전할 수 있다. 충성스러운 장군들은 누가 배신자인지 모른다. 이런 상황에서 충성스러운 장군들이 모두 같은 결정을 내리고, 그 결정이 합리적이도록 만드는 방법이 있을까.

배신자가 몇 명까지면 합의할 수 있나

램포트와 동료들은 놀라운 결론을 증명했다. 단순한 전령 메시지만 쓴다면, 전체 장군의 3분의 1 이상이 배신자일 때는 합의를 보장하는 방법이 없다. 거꾸로 배신자가 3분의 1 미만이라면, 충성스러운 장군들이 반드시 같은 결정에 이르는 절차를 만들 수 있다.

가장 작은 예로 장군이 세 명이고 그중 하나가 배신자라고 하자. 한 장군이 다른 두 장군에게서 서로 다른 말을 들으면, 누가 거짓말을 하는지 가려낼 수 없다. 배신자가 명령을 내린 장군일 수도, 명령을 전한 장군일 수도 있기 때문이다. 장군이 네 명 이상으로 늘고 서로 들은 내용을 다시 주고받으면, 다수결로 배신자의 영향을 걸러 낼 수 있다.

조건	합의를 보장할 수 있나
배신자가 전체의 3분의 1 미만	가능
배신자가 전체의 3분의 1 이상(서명 없는 메시지)	불가능
위조할 수 없는 서명을 쓰는 경우	더 많은 배신자를 견딜 수 있음

메시지에 위조할 수 없는 서명을 붙이면 상황이 나아진다. 배신자가 다른 장군의 말을 꾸며 낼 수 없기 때문이다. 오늘날의 전자 서명이 바로 이 역할을 한다.

컴퓨터는 왜 장군처럼 고민하나

장군은 비유일 뿐, 실제 주인공은 컴퓨터다. 비행기의 제어 장치는 같은 계산을 여러 대의 컴퓨터로 동시에 한다. 그중 하나가 고장 나 엉뚱한 값을 내놓아도 나머지가 올바른 결정에 합의해야 한다. 은행의 데이터베이스도 여러 서버에 같은 기록을 나눠 저장하고, 일부 서버가 멈추거나 오류를 내도 전체 기록이 어긋나지 않게 유지한다. 고장 난 컴퓨터는 배신자 장군처럼 서로 다른 정보를 내보낼 수 있다. 이런 상황을 견디는 성질을 비잔틴 장애 허용이라 부른다.

블록체인은 이 문제를 어떻게 풀었나

전통적인 방법은 참여하는 컴퓨터의 수와 정체를 미리 알고 있을 때 잘 작동한다. 그런데 누구나 들어오고 나갈 수 있는 인터넷에서는 참여자를 미리 알 수 없다. 한 사람이 가짜 참여자를 수천 개 만들어 다수결을 장악할 수도 있다.

비트코인은 여기에 다른 답을 내놓았다. 투표권을 사람 수가 아니라 계산 능력에 비례하게 만든 것이다. 다음 기록을 덧붙일 권리를 얻으려면 풀기 어려운 계산 문제를 먼저 풀어야 하고, 이 계산에는 실제 전기와 장비가 든다. 가짜 참여자를 아무리 많이 만들어도 계산 능력이 늘지 않으니 다수결을 장악할 수 없다. 대신 정직한 참여자들이 전체 계산 능력의 절반 넘게 갖고 있어야 한다는 새로운 조건이 생긴다.

남은 과제

누구나 참여하는 환경에서 빠르고, 안전하고, 에너지를 적게 쓰는 합의를 동시에 이루기는 어렵다. 계산 경쟁 방식은 안전하지만 막대한 전기를 쓰고, 다른 방식들은 에너지를 아끼는 대신 다른 종류의 공격에 대비해야 한다. 네트워크가 갈라지거나 메시지가 늦게 도착하는 현실의 조건까지 감안하면, 어떤 방식도 모든 장점을 다 가질 수는 없다는 사실이 이론적으로도 알려져 있다. 어느 쪽을 포기할지는 시스템마다의 선택으로 남는다.