[알쓸신블] 제2장 비잔티움 장군의 딜레마
비잔티움 장군의 딜레마의 탄생 배경을 찾아보는 중, 약 1970년도 NASA의 ‘분산화 컴퓨팅 프로젝트 갈릴레오’에 대하여 찾게 되었습니다. 해당 프로젝트의 진위 여부를 찾아내지 못하였지만, 비잔티움 장군의 딜레마를 이해하는 것에 좋은 예시가 되어 글에 포함시킵니다.
‘비잔티움 장군 문제’ 의 탄생
이전부터 비슷한 문제가 논의된 것으로 알고 있지만, 비잔티움 장군 문제는 레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 처음 언급됐다.
(해당 예제의 사실 여부는 완벽하게 파악 되지 않았습니다.)
‘비잔티움 장군 문제'는 1970년대 활발했던 ‘분산화 컴퓨팅’에서 비롯 되었다고 생각한다. 1970년대 NASA는 비용절감을 위하여 슈퍼 컴퓨터가 아닌, 민간인 컴퓨터의 컴퓨팅 파워를 임대하기로 하였고, 민간인 컴퓨팅 파워 모집 공고를 냈다. 슈퍼 컴퓨터 운용 비용 보다, 민간인 컴퓨팅 파워를 임대하는 편이 효율이 좋았기 때문이다.
하지만 ‘1+1 = 2’라는 답을 제출해야하는 컴퓨터가 ‘1+1 = 3’이라는 답을 제출하여 문제가 생겼다. 즉, 옳은 컴퓨팅 파워를 제공하는지 옳지 않은 컴퓨팅 파워를 제공하는지 판단 할 수 없었다.
이러한 이유로 ‘분산화 컴퓨팅'은 실패 했고, 위 예제를 포함한 다양한 원인들로 ‘비잔티움 장군 문제'라는 논문이 발표 되었다.
비잔티움 장군 문제
비잔티움 장군 문제는 배신자의 존재에도 불구하고 옳은 지휘관들이 동일한 공격 계획을 세우기 위해서 얼마만큼 존재해야 하며, 어떤 규칙을 따라 교신해야하는지에 대한 문제다.
예제를 통하여 비잔티움 장군 문제에 대하여 간단히 알아보자.
- 5명의 장군은 각각 100명의 병력을 소유하고 있다.
- ‘류짱의 성’ 에는 300명의 병력이 있어, 4명의 장군(400명)이 동시에 공격을 해야 한다.
- 지리적인 문제로 각 장군은 자신의 오른쪽 장군에게만 소통할 수 있다.
- 5명의 장군 중에 배신자 있을 수 있다.
4명의 장군이 동시에 공격하기 위해서는 배신자를 찾아내거나, 배신자가 없기를 기도하는 수 밖에 없다.
4번 장군이 배신자라고 가정 했을 때, 4,5번 장군은 다른 시각에 공격(5번 장군은 조작된 서신을 믿는다.)을 가게 되므로, ‘류짱의 성' 공격에 실패하게 될 것 이다. 또한, 4번 장군이 배신자가 아니라고 가정하여도 장군들은 서로를 신뢰할 수 없고, 공격의 성공 여부를 ‘운'에 기댈 수 밖에 없다.
‘비잔티움 장군 문제’는 가능을 증명한 논문이 아닌, 불가능을 증명한 논문이였다.
비트코인의 솔루션 Proof Of Work
비트코인은 비잔티움 장군 문제를 POW 합의알고리즘으로 풀어냈다.
POW의 기본 개념은 1993년에 Cynthia Dwork 와 Moni Naor에 의해 처음 고안 되었고, 1999년에 Markus_Jakobsson 과 Ari Juels에 의해 Proof of Work 라는 이름이 붙게 되었다. 나카모토 사토시가 2008년에 발행한 비트코인 백서에 POW를 채택하면서 POW가 알려지게 되었다.
이전 예시와 연결지어 비트코인이 사용한 솔루션을 살펴보자.
- [조건 1] 1번 장군은 배신자가 아니다.
- [조건 2] 다음 장군에게 메시지를 전달하는 시간은 10분이다.
- [조건 3] 다음 전달 까지 쉬지 않고 메시지를 작성한다.
[1번 장군이 2번 장군에게] / [2번 장군이 3번 장군에게] / [3 -> 4]
메시지를 전달 할 때마다, 전달 되는 메시지의 양은 늘어나게 될 것이다.
이전과 같이 4번 장군이 ‘조작된 메시지'를 넘기려해도 5번 장군은 1~3번 장군이 작성한 메시지를 함께 받게 된다. 약 75%의 메시지는 ‘오후 3시’, 약 25% 메시지는 ‘오후 4시'를 표시하고 있을 것이다.
여기서 5번 장군은 이전과는 다르게 선택을 할 수 있다. 75%를 믿을 것인지, 25%를 믿을 것인지.
일정 시간(블록 생성 시간) 동안 작업을 하여, 다음 사람에게 넘기고 다음 사람도 일정 시간 동안 작업을 하므로 조작을 불가능하게 만드는 것이다.
비트코인은 Proof Of Work를 통하여 ‘비잔티움 장군 문제'를 해결 했다고 평가 받고 있다.
이번화에서 다루지 못한 실용적 비잔티움 장애 허용(PBFT)는 학습 후 업로드 하겠습니다.다음 화에서는 Hash에 대해서 다루어보겠습니다.