본문으로 이동
Financial Context Wiki

비잔틴 장군 문제: 상충 메시지 아래의 합의

비잔틴 장군 문제는 결함 참여자가 상충 정보를 보낼 때 정직한 참여자가 어떻게 합의하는지 묻는다. 합의 과제, 채널과 인증 가정, 결함 한도, 하한, 알고리즘과 배포를 따로 분석해야 한다.

업데이트

프로토콜 분석을 위한 교육 자료일 뿐입니다. 하나의 비잔틴 합의 모델을 해결했다고 해서 실제 네트워크의 안전성, 활성, 구현 정확성, 탈중앙화, 최종성 또는 자산 보호가 입증되지는 않습니다.

직접 답변

비잔틴 장군 문제는 메시지로 통신하는 정상 참여자가 일부 참여자의 임의 행동과 수신자별 상충 주장에도 어떻게 일관된 결정을 내리는지 묻는다. 군사 이야기는 분산 시스템의 상호 일관성을 설명하는 비유이지 역사적 사건이나 특정 블록체인 합의 알고리즘이 아니다.

지휘관과 부관 형태에서 IC1은 모든 충성 부관이 같은 명령을 따를 것을, IC2는 지휘관이 충성일 때 모든 충성 부관이 지휘관 명령을 따를 것을 요구한다. 합의만으로는 부족하다. 항상 후퇴를 선택하면 일치는 하지만 충성 지휘관의 유효한 공격 명령을 위반한다.

논문의 “구두 메시지” 모델에서 배신자가 최대 m명이면 n>3m일 때만 해가 있으며, 정수 인원에서는 n>=3m+1과 같다. 이 모델은 충성 참여자가 보낸 메시지가 정확히 전달되고, 수신자가 송신자를 알며, 예상 메시지의 누락을 감지할 수 있다고 가정한다. “구두”는 인증되지 않은 내용을 다른 참여자의 보고인 것처럼 위조할 수 있다는 뜻이지, 전령이 영원히 사라져도 감지할 수 없다는 뜻이 아니다.

논문의 “서명 메시지” 모델은 위조 불가능하고 공개 검증 가능한 서명을 추가해 복원력 결과를 바꾼다. 그러나 서명 내용의 진실성, 전달, 완전 비동기 종료, 도난 키 보호 또는 현대 프로토콜의 안전성을 보장하지 않는다. 비잔틴 장군 문제, 두 장군 또는 협조 공격 문제, FLP, BFT, 작업증명과 지분증명은 관련되지만 서로 다른 모델이나 구성이다.

분석 방법

  1. 합의 과제를 정의한다. 참여자, 입력, 출력과 정확한 합의, 유효성, 종료 속성을 적는다. 지휘관 형태에서는 “합의”만 쓰지 말고 IC1과 IC2를 명시한다.
  2. 신원과 채널을 정의한다. 점대점 메시지의 인증, 신뢰성 있는 전달, 순서, 재전송 방지와 귀속, 누락 감지 여부, 브로드캐스트가 기본 연산인지 반복 전송인지 밝힌다.
  3. 시간 모델을 정의한다. 지연 상한이 있는 동기, 미지의 안정화 시점 이후 부분 동기, 완전 비동기를 구분한다. 한 모델에 사라지는 전령을 넣고 다른 모델의 정리를 그대로 쓰면 안 된다.
  4. 결함 예산을 정의한다. 총 참여자 n, 최대 비잔틴 참여자 m, 정적 또는 적응형 장악과 누락, 상충 메시지, 공모, 키 도난, 채널 결함의 포함 여부를 기록한다.
  5. 정보를 재귀적으로 추적한다. 각 충성 참여자의 직접 주장과 중계 주장, 송신자 경로, 누락 기본값, 결정적 동률 규칙을 나열하고 두 로컬 관점에서 실행을 구별할 수 있는지 비교한다.
  6. 정리와 알고리즘을 함께 확인한다. 하한과 충분조건을 정확한 구두 또는 서명 모델, 연결성과 결함 예산에 대응시킨다. 임계값 부등식만으로는 구현도 증명도 아니다.
  7. 배포에 대응시킨다. 실제 프로토콜의 OM(m), SM(m) 또는 다른 기제, 메시지 도메인, 라운드, 잠금, 인증서, 구성원 변경, 타임아웃, 클라이언트, 최종성, 애플리케이션 확인 정책을 검증한다.

핵심 증명 기법은 구별 불가능성이다. 충성 참여자는 자신의 로컬 메시지만 본다. 두 실행이 똑같이 보이지만 유효성 때문에 다른 결정을 요구한다면 어떤 결정적 규칙도 항상 올바르게 고를 수 없다. 충분한 독립 참여자, 인증 증거, 시간 가정, 무작위성 또는 다른 구조를 추가해 실행을 구별 가능하게 만들거나 보장 자체를 바꾼다.

계산 예시

1. 구두 메시지 장군 셋이 배신자 하나를 견딜 수 없는 이유

n=3, m=1이라고 하자. 필요조건 n>3m은 3>3이 되어 거짓이다. 지휘관 A가 부관 B에게 ATTACK, C에게 RETREAT라고 말했다고 하자. B는 A가 배신자로 상충 명령을 보냈는지, C가 배신자로 A의 말을 거짓 보고했는지 구별할 수 없고 C도 대칭적인 불확실성을 겪는다.

해당 “충성 A” 실행에서 지휘관 명령을 보존하는 결정적 선택은 “배신 A” 실행에서 B와 C가 다르게 선택하게 만들 수 있다. 중계는 네 번째 독립 출처를 만들지 않으므로 IC1과 IC2를 함께 보장할 수 없다.

2. 구두 메시지 장군 넷과 배신자 하나

OM(1)에서 n=4, m=1이다. 지휘관이 세 부관에게 명령하고, 각 부관은 받은 값을 다른 둘에게 중계하며, 충성 부관은 같은 다수결과 기본값을 쓴다. 지휘관이 충성이고 v를 보내면 충성 부관은 v, v, 배신자의 가능한 x를 보고 v를 고른다.

지휘관이 유일한 배신자라면 세 부관은 모두 충성이고 각자 받은 내용을 그대로 중계한다. 따라서 모두 같은 지휘관별 주장 집합을 재구성하고 같은 결정 규칙을 적용한다. 지휘관의 “진짜 의도”는 회복하지 못해도 합의를 만족한다.

3. 구두 메시지의 일반 하한

n=7, m=2이면 7>6이 성립해 인원 조건을 만족하며 다른 가정 아래 재귀적 구두 메시지 구성은 배신자 둘까지 견딘다. n=6에서는 6>6이 거짓이다. n=10, m=3에서는 10>9가 성립한다. 부등식 통과는 필요조건일 뿐 라운드, 중계, 다수결, 기본값과 채널을 올바르게 구현해야 한다.

4. 서명이 바꾸는 것

세 장군 SM(1) 예시에서 배신 지휘관이 B용 ATTACK과 C용 RETREAT에 서명한다. 충성 부관이 둘 다 중계하므로 양쪽은 같은 집합 {ATTACK, RETREAT}을 얻고 지정된 같은 기본값, 예컨대 RETREAT를 고른다. 지휘관의 상충 행동은 귀속된다.

이 모델에서 서명은 충성자의 명령 위조나 감지 불가능한 변경을 막는다. 두 명령 중 어떤 것이 배신자의 “진짜 의도”인지 밝히지 않고, 제때 전달을 보장하지 않으며, 정상 개인키를 장악한 공격자의 이중 서명도 막지 않는다.

위험과 검토 실패

문제와 모델

  • 정확한 합의, 유효성, 종료 조건 없이 비유만 되풀이한다.
  • 문제를 역사적 포위, 단일 알고리즘 또는 블록체인의 동의어로 본다.
  • 신뢰할 수 없는 채널의 공통 지식을 다루는 두 장군 문제와 혼동한다.
  • 감지 불가능한 영구 손실을 추가하면서 이를 제외한 구두 메시지 정리를 인용한다.
  • n>3m을 모든 인증, 비동기, 가중, 무허가 또는 자원 기반 프로토콜에 적용한다.
  • 충돌, 누락, 상충, 임의 계산, 채널 결함과 키 침해를 같은 결함으로 취급한다.
  • 참여자 수를 독립 주체, 지분, 해시 파워 또는 위원회 가중치와 같게 본다.
  • 유효성 조건에서 충성 지휘관과 배신 지휘관의 차이를 빠뜨린다.

알고리즘과 구현

  • 최종 다수만 보고 재귀 송신자 경로와 각 로컬 관점을 추적하지 않는다.
  • 구현마다 누락 기본값, 동률 규칙, 구성원 스냅샷 또는 순서가 다르다.
  • 프로토콜, 체인, 과제, 높이, 라운드, 값, 송신자와 구성원 시기에 묶이지 않은 메시지를 받는다.
  • 실행, 라운드, 포크, 네트워크 또는 구성원 변경을 넘어 메시지를 재생하거나 이어 붙인다.
  • 서명이 진실, 최신성, 권한 문맥, 전달, 가용성 또는 정직한 키 보관을 증명한다고 가정한다.
  • OM(m) 또는 SM(m)을 인용하면서 필요한 라운드, 중계, 검증과 연결성을 구현하지 않는다.
  • 한 배신자 위치만 시험하고 지휘관, 부관, 공모, 누락과 상충 사례를 시험하지 않는다.

배포와 해석

  • 정확한 안전성, 활성과 네트워크 가정 없이 합의 프로토콜이 “비잔틴을 해결했다”고 주장한다.
  • 바이트 합의를 애플리케이션 실행이나 오프체인 사실의 정확성 증명으로 본다.
  • 공통 클라이언트, 운영자, 클라우드, 키 시스템 또는 거버넌스의 상관 결함을 무시한다.
  • 필요한 최종성 전에 입금을 반영하고 브리지 자산을 발행하거나 비가역 행동을 결제한다.
  • 결함 허용 명칭에서 탈중앙화, 자산 안전, 법적 진실 또는 토큰 가치를 추론한다.

흔한 오해

  • 이 문제는 단순한 51% 공격이다. 정의된 합의 모델의 임의·상충 행동을 다루며 자원 다수 공격은 특정 프로토콜에 속한다.
  • 다수면 언제나 해결된다. 고전 구두 모델에서 배신자 m명을 견디려면 총수가 그 세 배를 넘어야 하며 충성자가 한 명 더 많은 것으로는 부족하다.
  • 전자서명은 메시지가 사실임을 증명한다. 키를 인증하고 무결성을 지키지만 악의적이거나 침해된 키는 거짓·상충 내용에 서명할 수 있다.
  • 원래 구두 결과는 불안정한 전달도 포함한다. 명시적 전달, 송신자 식별, 누락 감지를 가정하며 다른 시간·채널 모델에는 다른 결과가 필요하다.
  • 합의하면 현실을 알아낸 것이다. 별도 검증 규칙이 없으면 충성 노드도 무효 출력이나 잘못된 외부 데이터에 합의할 수 있다.

관련 주제

출처

탐색

위키 검색...