의견.png

"비잔틴 장애 허용"의 두 판 사이의 차이

위키원
이동: 둘러보기, 검색
(특징)
6번째 줄: 6번째 줄:
  
  
== 특징 ==
+
==두 장군의 문제==
===비잔티움 장애===
+
두 장군의 문제는 1972년 등장한 일종의 가상 실험이다. 이 실험에서 가정은 1. 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양 옆에 주둔한 상황이며 2. 두 장군은 적군을 점령하기 위해 부대가 같은 날, 같은 시각에 공격을 하려 한다. 3. 이때 연락을 주고받아야 하는데 이를 담당하는 연락병은 직접 적군의 도시를 통과해야하며 4. 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정 하에 진행이 된다.  
첫번째 솔루션은 전달된 메시지가 위조될 수 있다는 시나리오로 시작한다. 하지만 때 배반한 장군의 수가 전체 장군 수의 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) 솔루션이 있다.
 
  
===비잔티움 장애 허용===
+
장군A는 B에게 메시지를 보냈지만 잘 전달 됐는지 확신을 하지 못한다. 이에 B가 메시지를 잘 받았으면 A에게 확인 답장을 보내야 하는데 B도 마찬가지로 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다. 이에 B를 안심시키고 함께 공격하기 위해 A가 답장을 받았다고 재답장을 해야 하지만 이 역시 B에게 잘 도달했는지 장담하지 못한다. 결국 이는 두 장군이 같은 수준의 합의에 도달할 없고 이러한 불확실성은 결국 함께 적군의 도시를 공격할 수 없다는 의미이다. 이후 이 문제는 실제로 해결이 불가능한 것으로 증명됐으며 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 같은 내용의 거래기록을 갖는데 까지 도달하지 못한다는 의미이다.
두 번째 솔루션은 메시지의 서명이 위조될 수 없다를 가정한다. 보안이 중요한 시스템(security-critical system)에서 디지털 서명은(공개 키 암호화로 형태로 구현) 임의의 배반자 지휘관이 있는 상황에서 비잔틴 장애 허용을 제공한다. 하지만 안전이 중요한 시스템(safety-critical system)에서 CRCs 등은 대부분의 상황에서 적용될 수 있는 간단한 에러를 찾는 코드를 낮은 비용에 제공하며, 이는 비잔틴 장애와 비잔틴 장애가 아닌 것 모두에 가능하다. 따라서 암호화된 디지털 서명 방식은 별도의 보안 위협이 있지 않은 , 시스템에서 안전이 중요한 역할은 아니다.
 
또한 Lamport, Shostak, Pease는 앞서 서술한 두 솔루션 외에도 모든 지휘관이 서로 소통할 수 없는 경우 등 다양한 경우에 관해서도 서술했다.  
 
  
 
[[파일:Byzantine Agreement.jpg|썸네일|가운데|600픽셀|'''Byzantine Agreement'''(비잔틴장군의 동의)]]
 
[[파일:Byzantine Agreement.jpg|썸네일|가운데|600픽셀|'''Byzantine Agreement'''(비잔틴장군의 동의)]]

2019년 2월 21일 (목) 09:24 판

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

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

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


두 장군의 문제

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

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

Byzantine Agreement(비잔틴장군의 동의)

각주

참고자료

같이 보기


  의견.png 이 비잔틴 장애 허용 문서는 알고리즘에 관한 토막글입니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 이 문서의 내용을 채워주세요.