비잔틴 장군문제

비잔틴 장군 문제(The Byzantine Generals Problem)란 고대 동 로마 제국(비잔틴 제국)을 비유한 시스템 문제이다.

상호 간에 통신을 통해 어떤 합의를 해야 하는 경우 통신에 문제가 발생하거나 고의로 정보를 변경해 가짜 정보를 전달할 가능성이 있을 때 전체가 올바른 합의를 형성할 수 있는지는 묻는 문제이다.

해당 논문의 요약에는 상황을 아래와 같이 설명하고 있다.

This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.

비잔틴 장군의 입장에서 상황을 살펴보자.

비잔틴 장군들은 예루살렘성(가정)을 공격하려고 한다. 각 장군들이 한마음으로 한시 한때에 공격하면 성을 함락하고 승리 할 수 있지만 합의된 계획을 세우지 못할경우 패배한다. 이 때 장군들 사이에는 배신자(합의된 메세지를 변조할 수 있는)가 있을 수 있을 때 어떻게 하면 하나의 계획으로 승리 할 수 있을까 라는 문제이다.(논문에 따르면 2/3 이상의 장군이 믿을 만할때 배신자의 방해에도 불구하고 승리 할 수 있다)

비잔틴 장군의 문제를 해결하기 위해 어느정도의 fault를 가정하는 비잔티움 장애 허용 시스템도 존재한다.

이제 블록체인의 입장에서 비잔틴 장군 문제를 바라보자. 블록체인은 비트코인에 사용된 분산원장의 기술에 기초한다. P2P 기반의 가상화폐에서는 악의적인 노드의 행동을 제한하는것이 굉장히 중요하다. 그래서 비트코인은 PoW라는 작업증명 알고리즘을 통해 비잔틴 장군 문제를 해결한다.

먼저, 각 노드에 풀기 어려운 문제를 제공하여 답을 찾아 올것을 주문한다. 이때 문제는 충분한 인원이 충분한 시간을 들여야 풀수 있는 문제이다. 확률적으로 찾을 수 있는 문제기 때문에 특정시간(10분)에 한번씩 답을 나온다면 해당 네트워크에는 충분한 노드가 답을 찾기 위해 노력하고 있다고 믿을 수 있다. 믿을 만한 수의 노드가 참여한 네트워트에서 선출된 하나의 노드가 블록을 생성함으로 신뢰할 만한 노드를 선정한다. 그리고 새롭게 생성된 블록은 이전에 존재하던 블록에 연결된다. 새롭게 생성된 블록을 받은 노드는 블록해쉬를 확인해서 확인된 블록은 새롭게 블록체인에 연결(새롭게 생성될 블록을 악의적으로 수정하기 위해서는 이전 모든 블록의 값을 수정해야해서 이론적으로 불가능)

 

PoW를 비잔틴 장군의 상황에 넣어서 이해해보자.

5명(A,B,C,D,E)의 장군이 있다.

  1. A장군이 B장군에게 10시에 공격하는 계획을 전달한다(최초의 블록)
  2. B장군은 A장군의 서명을 포함한 메세지를 10분정도 걸리는 암호화 작업을 진행한다. 이후 암호화 된 메세지를 C장군에게 전달한다.
  3. C장군은 B장군에게서 받은 메세지를 해석해서 A장군의 서명을 확인하고 B장군의 10분간의 암화화 작업 기록을 확인한다.
    배신자인 C장군은 이 작전이 실패하기를 바란다. 그래서 작전시간을 9시로 위조하고 10분간 암호화 작업을 진행한다. 그리고 D장군에게 전달한다.
  4. D장군은 메세지를 해석하고 A장군이 B장군에게 10시 공격계획을 전달한것과 B장군이 C장군에게 10시 계획을 전달한 것을 확인한다. 하지만 C장군의 암호화 작업을 확인한 결과 계획이 9시로 변경된것을 확인한다.
  5. D장군은 C장군의 메세지가 악의적으로 편집된 것을 확인하고 10시 공격 계획을 E장군에게 전달한다.

PoW과 비잔틴 장군의 예시가 정확히 맞지 않아 이해하는데 방해가 될 수도 있다. 그럼에도 예시를 넣어둔 것은 큰 틀에서 블록체인이 어떻게 비잔틴 장군 문제를 해결하는가를 설명하기 위해 작성하였음을 참고하시기 바란다.

 

* 참고 : http://goodjoon.tistory.com/256https://ko.wikipedia.org/wiki/비잔티움_장애_허용 , https://steemit.com/kr/@twinbraid/1npff , 블록체인 구조와 이론@위키북스, http://bnrg.cs.berkeley.edu/~adj/cs16x/hand-outs/Original_Byzantine.pdf(논문원본)


%d 블로거가 이것을 좋아합니다: