Byzantine Generals Problem

도시 주변에 여러 부대가 배치되어 있다고 상상해 보세요. 함께 공격하거나 함께 후퇴해야 합니다. 행동이 갈리면 큰 피해를 입을 수 있습니다. 지휘관이 명령을 보내지만 누군가 배신해 사람마다 다른 이야기를 할 수도 있습니다. 믿을 수 있는 참여자들이 어떻게 같은 행동에 도달할까요? 실제 전투의 기록이 아니라, 일치하는 기록이 필요한 컴퓨터를 설명하는 사고실험입니다. 예를 들어 공통 서비스를 제공하는 컴퓨터인 여러 서버가 어떤 결제를 이미 처리했는지 동일하게 판단해야 합니다. 각자 답변을 받았다는 사실만으로는 부족합니다. 그 답변들이 하나의 공통 결정으로 이어져야 합니다. [1] [9]

Leslie Lamport, Robert Shostak, Marshall Pease는 장애가 있는 환경의 합의를 다룬 1980년 연구에 이어 1982년 7월 이 유명한 형태로 문제를 제시했습니다. 배신자는 행동을 더 이상 예측할 수 없는 시스템 구성요소를 뜻합니다. 컴퓨터는 단순히 멈추기만 하는 것이 아닙니다. 한 이웃에게는 맞게, 다른 이웃에게는 틀리게 답하거나 메시지를 생략하거나 다른 것을 보았다고 주장할 수 있습니다. 공격뿐 아니라 프로그램 오류도 원인이 됩니다. 비잔틴 장애는 장치의 의도가 아니라 다른 참여자에게 관찰되는 행동을 설명합니다. BFT (Byzantine Fault Tolerance)는 정해진 조건에서 이런 행동을 견디는 능력입니다. [1] [2]

원래 문제에는 두 조건이 있습니다. IC1은 신뢰할 수 있는 모든 부하가 같은 명령을 받아들여야 한다는 조건입니다. IC2는 지휘관도 신뢰할 수 있다면 그가 실제로 보낸 명령을 받아들여야 한다고 덧붙입니다. 두 번째 조건이 없으면 ‘항상 후퇴하라’가 해답처럼 보이지만 정직한 지휘관을 무시하게 됩니다. 컴퓨터 시스템에서는 상충하는 결과를 막는 안전성과 결과에 도달할 수 있는 활성성을 구분합니다. 어떤 결과가 유효한지는 추가 규칙이 정합니다. 기록이 일치한다는 사실만으로 입력된 주장이 외부 세계에서 참이었다고 증명되지는 않습니다. [1] [9]

지휘관을 A, 부하를 B와 C라고 합시다. C는 A에게 공격 명령을 받았는데 B는 지휘관이 후퇴하라고 했다고 말합니다. B가 거짓말한 걸까요, A가 서로 다른 명령을 보낸 걸까요? 전달된 뒤에도 검증할 수 있는 서명이 없으면 C는 두 상황을 구별하지 못할 수 있습니다. B도 같은 불확실성에 놓일 수 있습니다. 늘 지휘관을 따르면 악의적인 A가 둘을 갈라놓을 수 있고, 늘 무시하면 정직한 지휘관에 관한 조건을 어깁니다. 따라서 세 참여자 중 한 명이 배신자일 수 있는 이 문제에서는 서명 없이 항상 성공하는 절차가 없습니다. 부족한 것은 더 빠른 컴퓨터가 아니라 상황을 구별할 정보입니다. [1] [9]

서명이 없는 고전적 모델에서 최대 m명의 배신자를 견디려면 최소 n ≥ 3m+1명이 필요합니다. n은 전체 참여자 수이고, m은 시스템이 견뎌야 할 최대 배신자 수입니다. 한 명에 대비하려면 네 명입니다. 표 하나를 더해 한 번 다수결을 한다는 뜻은 아닙니다. OM(m)은 들은 내용을 반복해서 전달하고 공통 규칙에 따라 평가하게 합니다. 기본 단계 OM(0)은 지휘관의 값이나 미리 정한 기본값을 채택합니다. 모델은 알려진 참여자, 직접 연결, 보낸 메시지의 정확한 전달, 직전 발신자 식별, 누락된 메시지 감지를 가정합니다. ‘서명 없음’이 ‘출처 확인이 전혀 없음’을 뜻하지는 않습니다. 이런 전제가 없다면 네 명이라는 숫자만으로는 아무것도 보장할 수 없습니다. [1] [9]

검증 가능한 디지털 서명인 Digital Signature가 있으면 B는 지휘관이 실제로 서명한 내용을 C에게 증거로 제시할 수 있습니다. 프로그램은 비밀 숫자 값인 개인 키로 서명을 만듭니다. 다른 참여자는 개인 키를 몰라도 대응하는 공개 키로 서명을 검증할 수 있습니다. 배신자는 믿을 수 있는 참여자의 명령을 몰래 바꾸거나 서명을 흉내 낼 수 없습니다. 서명 메시지 알고리즘은 서명된 값을 전파하고 공통 선택 규칙을 적용합니다. 이 모델에서는 앞서 설명한 정직한 다수 조건이 사라지지만, 위조 불가능한 서명과 전달, 라운드의 시간 조건은 여전히 필요합니다. Dolev와 Strong의 1983년 연구는 필요한 라운드 수를 더 다룹니다. 유효한 서명도 내용이 사실이거나 메시지가 제때 도착한다는 보장은 아닙니다. 개인 키를 도난당하지 않았다는 증거도 되지 않습니다. 특정 메시지의 출처를 증명할 뿐, 발신자를 모든 일에서 믿어도 된다는 뜻은 아닙니다. [1] [3]

서버가 답하지 않을 때 다른 서버는 멈춘 것인지 연결이 아주 느린 것인지 알 수 없습니다. Michael Fischer, Nancy Lynch, Michael Paterson이 1985년 발표한 FLP 결과는 이 불확실성을 엄밀하게 설명합니다. 여기서 프로세스는 실행 중인 프로그램입니다. 결정론적 절차는 상태와 입력이 같으면 다음 단계도 같으며, 그 단계를 무작위로 고르지 않습니다. 지연의 알려진 상한이 없는 완전 비동기 시스템에서는 프로세스 하나가 중단될 가능성만 있어도 결정론적 절차가 모든 허용된 실행에서 합의의 완료를 보장할 수 없습니다. 신뢰성 있게 전달되더라도 지연이 제한되지 않으면 마찬가지입니다. 합의가 절대로 이루어지지 않는다는 뜻은 아닙니다. 실제 시스템은 시간 가정, 적절한 장애 감지기 또는 무작위성을 추가합니다. 네트워크가 나뉘었을 때는 양립할 수 없는 결과를 확정하기보다 기다리는 것이 안전할 수 있습니다. [4] [13] [8]

Miguel Castro와 Barbara Liskov는 1999년 알려진 여러 복제본에서 실행되는 서비스를 위한 Practical Byzantine Fault Tolerance, PBFT를 설명했습니다. 복제본은 서로 다른 서버에서 같은 서비스를 실행하며 같은 요청을 계속 처리합니다. 보관해 둔 백업 파일을 뜻하는 것이 아닙니다. 기본 구성 n = 3f+1은 f개의 잘못된 복제본을 허용합니다. 서버 네 대 중 한 대가 비잔틴 장애를 일으킬 수 있고, 세 대씩 묶은 두 집합은 최소 두 대가 겹치므로 그중 적어도 한 대는 신뢰할 수 있습니다. 이런 필수 승인 집합을 정족수, 즉 quorum이라고 합니다. 겹친다는 사실만으로 충분하지 않으며 단계별 규칙과 리더 교체도 중요합니다. 구체적으로 prepared 상태에는 요청, pre-prepare 메시지, 주 복제본 이외의 서로 다른 복제본에서 온 일치하는 2f개의 prepare가 필요합니다. 로컬 확정에는 추가로 2f+1개의 commit이 필요하며 자신의 메시지를 포함할 수 있습니다. 출처 확인, 순서 번호, 체크포인트는 위조, 재전송 공격, 무한한 로그 증가에 대응합니다. 안전성은 시간 상한에 의존하지 않지만 진행을 위해서는 지연에 관한 추가 조건이 필요합니다. [5] [10] [11] [12]

Bitcoin에는 사전에 닫아 놓은 서버 명단이 없습니다. 새 계정마다 한 표를 준다면 공격자는 다수 계정을 만들어낼 수 있습니다. 이것이 Sybil Attack입니다. 그래서 Proof of Work는 블록 생성에 계산 작업을 요구합니다. 블록은 공동 거래 기록에 추가하는 거래 묶음입니다. 검증 프로그램을 실행해 규칙을 독립적으로 검사하는 컴퓨터인 Full Node는 먼저 무효한 블록을 거부한 뒤 유효한 가지 중 누적 작업량이 가장 큰 것을 따릅니다. Bitcoin은 OM이나 PBFT를 실행하지 않으며 일시적인 분기는 작동 방식의 일부입니다. 정직한 계산 능력이 충분하고 통신 조건이 적절하면 확인이 늘수록 기록이 바뀔 위험은 줄지만 절대적인 불가역성이 생기지는 않습니다. Bitcoin Backbone 연구는 기록의 일치, 체인의 성장, 정직한 참여자가 만들 수 있는 블록 비율에 관한 이런 조건을 분석합니다. [6] [7]

‘네트워크가 합의한다’는 말을 들으면 구체적으로 물어보세요. 누가 참여할 수 있고, 공격자는 무엇을 통제하며, 메시지는 얼마나 늦어져도 되고, 결정은 언제 바뀔 수 있을까요? Proof of Work도 모든 문제를 없애지는 않습니다. Eclipse Attack은 노드를 정직한 상대에게서 고립시키고, 검열은 거래를 제외하며, Selfish Mining은 채굴한 블록의 공개를 미룹니다. 소프트웨어 오류와 충분한 공격 우위로 기록 일부를 바꿀 가능성도 남습니다. 그래도 계산 능력의 과반수만으로 정상적인 Full Node가 자신의 규칙을 어기는 블록을 받아들이게 할 수는 없습니다. 장군의 이야기는 기술 이름만 믿지 말고 합의가 성립하는 조건을 살펴보라고 가르칩니다. [6] [7] [8]