PoW 를 통한 비잔틴 오류 허용 (비잔틴 장군 문제) 해결 과정

블록체인에 대한 개념과 사토시 나카모토에 대한 이야기를 할 때 빠지지 않는 코스로 잠깐이라도 비잔틴 장군 문제 혹은 비잔티움 장군 문제, 비잔틴 오류 허용 에 대해 이야기가 나오곤 한다. 그런데 대부분 '아 무언가 신뢰할 수 없는 환경에서 어려운 문제를 풀게 해서 신뢰를 얻어내게 했구나' 정도로 이해하면 다행이고, 설명하는 사람들 조차도 어떤 과정으로 그러한 신뢰를 갖게 하였는지에 대해서는 상세히 모르고 설명하는 케이스가 대부분이었다. 

아래는 PoW

▌두 장군의 문제

불확실한 통신 상황에서 상호 동기화를 시도할 때의 문제점으로,

이건 중간의 통신 장애가 있는 경우 어떻게 공격 시간을 전달할것인가라는 문제이며 아직까지 이에 대한 해결방안은 나오지 않았다.

위 처럼 장군 A1, A2 는 가운데 B 에 있는 적들을 공격해야 하는데, 동시 공격하지 않으면 이길 수 없는 상황이다.

A1, A2 사이를 흐르는 강이 있으나, 건너는 경우 연락병이 포획될 가능성이 있다.

이러한 상황에서, A1, A2 는 시간을 합의하고 상호 확답을 받아야 한다. 

이 문제는 비잔틴 장군의 문제와는 다른 문제이다. 

▌비잔틴 장애허용, 비잔틴 장군 문제

300명의 병력이 있는 비잔틴 성을 100명씩의 병력을 가진 장군 5명이 치려함

이기려면 적 병력보다 많은 병력이 공격해야 함

장군들은 연락병을 보내 소통 가능함

장군들 중에는 배신자가 있어 서로 신뢰 불가함

문제) 서로 신뢰할 수 없는데, 어떻게 공격 시각을 합의할 수 있는가? 

     . 가정 1 - 공격 시각은 상관 없음. 모두 한번에 공격할 수 있는 합의된 시각이면 됨

     . 가정 2 - 배신자는 병력을 분산시키려 하므로 이전 장군의 메시지와 다른 시각을 제시함

     . 가정 3 - 각 장군은 자신의 바로 다음 장군에게만 연락할 수 있음

     . 가정 4 - 배신자도 지정한 시간에 공격에 가담 함

<<문제 생기는 상황>>

1. @장군1 이 "9 AM" 공격시각을 적어 서명과 함께 @장군2 에게 보냄 
2. @장군2 는 @장군1 의 "9 AM" 공격시각을 보고 기억한 후 @장군3 에게 전달함
3. @장군3 은 배신자로, "9 AM" 메시지를 찢어버리고 "8 AM" 으로 고쳐서 @장군 4에게 전달함
4. @장군4 는 "8AM" 을 기억한 후 @장군5 에게 전달
5. @장군5 는 "8AM" 을 기억
6. 8AM 에 @장군3, @장군4, @장군5 가 쳐들어가지만 300명이므로 지게 됨

<<PoW 블록체인 해결>>

[새로운 규칙]

A. 장군은 메시지를 보내기 위해 반드시 10분의 시간을 들여야 함

B. 메시지는 모든 이전 장군의 메시지와 10분의 시간을 들였다는 증거를 포함하여 보내야 함

1. @장군1 이 "9 AM" 공격시각을 적어 10분간 작업하여 증거와 함께 @장군2 에게 보냄
2. @장군2 는 "9 AM" 메시지와 @장군1 의 10분 작업 증거를 보고 확신 후, @장군3 에게 "9 AM" 메시지 보냄
   1. @장군2 도 10분 간 작업 함
   2. @장군1, @장군2 의 메시지와 작업내용 모두를 포함하여 보냄
3. @장군3 은 배신자로 "8AM" 으로 메시지를 수정하여 보내고 싶으나 그냥 보낼 수 없음. 아래 중 택 1 해야 함.
   1. 속일 수 있는 유일한 방법
      1. @장군3 은 10분보다 빠르게 작업을 하여 "8 AM" 메시지를 만들어 냄
      2. @장군1, @장군2 의 총 20분 작업에 해당하는 메시지 모두를 남은 시간 내에 만들어 포함 시켜 보냄
   2. 안들키고 있으려면 "9 AM" 으로 보내기
4. @장군4, @장군5 모두 동일

[의미]

1. 만약 @장군3 이 "8AM" 으로 보냈다면, 모두 장군 3이 거짓임을 알게 됨
2. 만약 @장군2 가 배신자였다면 @장군2,3,4,5 모두 9AM 공격 가므로 이기게 됨
3. 만약 @장군1 이 배신자였다면 8AM 에 모두 함께 공격 가므로 이기게 됨

비잔틴 장군의 문제를 PoW 를 통한 블록체인 기술로 해결 한 예시이다. 블록체인은 "이전 메시지를 포함" 시킨 새로운 메시지로 이해할 수 있으며, 포함된 이전 메지시를 변경한 경우 변경(위조)되었다는 사실을 바로 알 수 있는 장부이다. PoW 는 "10분의 시간을 들여 메시지를 만드는 과정" 이며, 정말 그러한 작업을 하였는지를 단번에 검증해낼 수 있는 방법을 제공한다.

그러나 10분의 시간을 들이지 않고는 절대 새로운 메시지에 포함된 이전 메시지를 다시 만들어낼 수는 없는 알고리즘이며, 비잔틴 장군의 문제 해결에 가장 핵심이 되는 메커니즘인 것이다. 

출처: http://goodjoon.tistory.com/256 [Good Joon]