[Makers Basic 13] 블록체인의 문제점과 대안2
비잔티움 장군 문제(Byzantine Generals Problem)
비잔티움 장군 문제는 레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 처음 언급되었습니다. 이 논문에서 적군의 도시를 공격하라는 비잔티움 제국군의 여러 부대가 지리적으로 떨어진 상태에서 각 부대의 지휘관들이 중간에 정보의 변경이 이루어질 수도 있는 전령을 통해서 교신하면서 공격 계획을 세우는 상황을 가정하고 있습니다.
이 부대의 지휘관 중 일부에는 배신자가 섞여 있을 수도 있고, 배신자는 규칙을 충실히 따르는 충직한 지휘관들과 달리 규칙에 얽매이지 않고 마음대로 행동 할 수 있습니다.
이 때 배신자의 존재에도 불구하고 충직한 지휘관들이 동일한 공격 계획을 세우기 위해서는 충직한 지휘관들의 수가 얼마나 있어야 하며, 이 지휘관들이 어떤 규칙에 따라 교신해야 하는지에 대한 문제가 비잔티움 장군 문제입니다.
다시 말해서, 분산 처리 시스템에서 데이터를 주고 받을 때 통신의 문제가 발생하거나 혹은 악의적으로 정보를 변경하는 행위에 대해서 전체 시스템이 올바른 합의를 어떻게 이룰 수 있는 지를 빗대어 표현한 것입니다.
비잔티움 장군 문제에서는 장군으로 표현하였지만 블록체인에서는 각각을 노드라고 생각하면 쉬울 것 같습니다. 악의적인 노드나 해킹으로 인하여 노드의 오작동이 발생하여도 네트워크는 여전히 신뢰도 있는 서비스를 제공할 수 있어야 합니다.
블록체인의 경우에는 하나의 주체가 네트워크를 구성하는 것이 아닌 신뢰관계가 아닌 노드들에 의해서 네트워크를 구성합니다. 이로 인하여 각각의 노드들은 조작 가능성을 가지고 있기 때문에 블록체인 시스템은 이를 해결하여 신뢰성을 보장하여야 합니다.
비잔틴 장애 허용(Byzantine Fault Tolerance)
비잔틴 장군의 문제를 블록체인으로 해결한 것을 보여주는 좋은 예시가 있어서 찾아보았습니다. 원본 참고
예시)
300명의 병력이 있는 비잔틴 성을 100명씩의 병력을 가진 장군 5명이 공격하려고 하는 데, 이기려면 적 병력보다 많은 병력이 공격해야 한다. 장군들은 연락병을 보내 소통 가능하지만, 장군들 중에 배신자가 있어서 서로 신뢰가 불가능하다.
문제) 서로 신뢰할 수 없는 데, 어떻게 공격 시간을 합의할 수 있을 까?
가정1:공격시각은 상관없음, 모두 한번에 공격할 수 있는 합의 된 시각이면 됨
가정2:배신자는 병력을 분산시키려 할 것이므로 이전 장군의 메시지와 다른 시각을 제시함.
가정3:각 장군은 자신의 바로 다음 장군에게만 연락 할 수 있음.
가정4:배신자도 지정한 시간에 공격에 가담 함.
문제가 생기는 경우 예시
- @장군1 이 “9 AM” 공격시각을 적어 서명과 함께 @장군2 에게 보냄
- @장군2 는 @장군1 의 “9 AM” 공격시각을 보고 기억한 후 @장군3 에게 전달함
- @장군3 은 배신자로, “9 AM” 메시지를 찢어버리고 “8 AM” 으로 고쳐서 @장군 4에게 전달함
- @장군4 는 “8AM” 을 기억한 후 @장군5 에게 전달
- @장군5 는 “8AM” 을 기억
- “8AM “에 @장군3, @장군4, @장군5 가 쳐들어가지만 300명이므로 지게 됨
PoW를 통한 해결
새로운 규칙 2가지
A. 장군은 메시지를 보내기 위해 반드시 10분의 시간을 들여야 함
B. 메시지는 모든 이전 장군의 메시지와 10분의 시간을 들였다는 증거를 포함하여 보내야 함
- @장군1 이 “9 AM” 공격시각을 적어 10분간 작업하여 증거와 함께 @장군2 에게 보냄
2. @장군2 는 “9 AM” 메시지와 @장군1 의 10분 작업 증거를 보고 확신 후, @장군3 에게 “9 AM” 메시지 보냄
- @장군2 도 10분 간 작업 함
- @장군1, @장군2 의 메시지와 작업내용 모두를 포함하여 보냄
3. @장군3 은 배신자로 “8AM” 으로 메시지를 수정하여 보내고 싶으나 그냥 보낼 수 없음. 아래 중 택 1 해야 함.
A. 속일 수 있는 유일한 방법
1. @장군3 은 10분보다 빠르게 작업을 하여 “8 AM” 메시지를 만들어 냄
2. @장군1, @장군2 의 총 20분 작업에 해당하는 메시지 모두를 남은 시간 내에 만들어 포함 시켜 보냄(블록체인에서 해시 파워로 나머지 노드들의 성능을 압도한다는 것을 의미)
B. 안들키고 있으려면 “9 AM” 으로 보내기
4. @장군4, @장군5 모두 동일
[의미]
- 만약 @장군3 이 “8AM” 으로 보냈다면, 모두 장군 3이 거짓임을 알게 됨
- 만약 @장군2 가 배신자였다면 @장군2,3,4,5 모두 9AM 공격 가므로 이기게 됨
- 만약 @장군1 이 배신자였다면 8AM 에 모두 함께 공격 가므로 이기게 됨
이렇게 비잔틴 장군의 문제를 작업증명 방식으로 해결 한 예시였습니다.
블록체인은 ‘이전 메시지를 포함’ 시킨 새로운 메시지로 이해할 수 있고, 포함된 이전 메시지를 변경한 경우에는 이를 변경(위조)되었다는 사실을 바로 알 수 있게 됩니다.
