비잔틴 장군 문제

비잔틴 장군 문제란?

블록체인에 대해 공부하면 한 번쯤 들어봤을 비잔틴 장군 문제(# Byzantine Generals Problem)에 대해 알아보겠습니다.

비잔틴 장군 문제는 위와 같이 성을 공략하는 방법에 대한 딜레마 입니다. 적의 성에는 적군이 많이 있기 때문에 한 번에 모두 공격을 해야만 성을 함락할 수 있습니다. 지휘관이 내일 10시에 일제히 성을 공격하자고 각 장군들에게 전령을 보내 공격을 진행 합니다. 이 때 장군들 사이 혹은 소식을 전하는 전령들 중에 첩자가 존재해 10시가 아닌 8시에 공격하자고 전달합니다. 이렇게 되면 어떤 장군은 제대로 전달 받아 10시에 공격하고, 어떤 장군은 첩자에게 속아 8시에 공격하게 됩니다. 이렇게 전력이 분산되어 결국 성을 함락하지 못하게 됩니다. 
첩자가 있는 이런 상황에서 어떻게 하면 성을 함락할 수 있을지 찾는 문제를 비잔틴 장군 문제라고 합니다.

이 문제가 블록체인하고 무슨 관계가 있는지 알아보겠습니다. 우리는 중앙화된 금융환경에 살고 있습니다. 각각의 은행들의 통제하에 돈을 입금하기도 하고 출금하기도 합니다. 수수료나 이자를 주면서까지 이렇게 은행을 사용하는 이유는 개인간에는 신뢰가 없기 때문입니다. 모두를 믿을  수 있으면 좋겠지만 나와 거래하는 사람중에 사기꾼이 끼어 있을수도 있기에 은행이라는 신뢰할 수 있는 기관을 통해 거래를 진행하는 것입니다.

이렇게 은행들을 믿고 거래를 하다가 은행이 망하게 된다면 내 모든 재산을 잃게됩니다. 그래서 중앙에서 벗어나 사용자끼리 서로 믿으며 거래할 수 있는 금융환경을 만들자는 것이 블록체인 입니다. 여기서 장군들이 바로 우리들이고, 성을 공략하는 것이 거래를 정상적으로 진행하는 것입니다. 여기에 사기꾼이나 해커가 끼어있어도 거래가 정상적으로 진행되게 하는 것이 비잔틴 장군 문제의 해법과 같은 것 입니다.

두  장군 문제

이런 문제를 해결할 때 쉬운 방법은 가장  단순한 형태로 만드는 것입니다. 그래서 먼저 장군이 두 명 있을 때 어떻게 성을 공략할 수 있을지 생각해 보는 것입니다. 결론적으로 말하자면 장군이 두 명일 때에는 이 문제를 해결할 수 없습니다. 서로를 신뢰할 수 없기 때문에 답을 낼 수 없습니다. 문제를 쉽게 해결하기 위해 단순화 하였는데 더욱 문제를 어렵게 만든 꼴이 됩니다. 여러명의 장군이 있는 경우가 더 쉽게 해결이 가능합니다. 

흔히 블록체인을 해킹 하려면 블록체인의 51% 이상의 네트워크보다 빠르게 체인을 만들어야 한다고 합니다. 이 51%가 두 장군 문제에서는 두 명밖에 없기 때문에 50%를 넘지 못해서 해결이 안되는 것입니다. 즉 장군이 3명 이상이라면 과반수인 51%가 넘는 장군이 합의 되면 그것이 맞다고 여기는 것입니다.

 

비잔틴 장군 문제

그럼 이제 원래의 비잔틴 장군 문제를 생각해 보겠습니다. 여러명이 있는 경우 어떻게 진짜 공격 명령과 가짜 공격 명령을 구분할 수 있을까요? 

장군들에게 풀기는 어렵지만 결과 확인은 쉬운 문제를 출제해서 문제를 풀도록 합니다. 풀기는 어렵지만 결과 확인이 쉬운 문제가 무엇인지부터 알아보겠습니다. 예를 들어 634,744란 숫자가 있습니다. 이 숫자는 두 수의 곱으로 만든 숫자입니다. 두 수가 무엇인지 찾는건 어렵습니다. 하지만 7,213 이라는 하나의 숫자를 알고 있다면 634,744 / 7,213을 계산하여 88이라는 숫자를 쉽게 찾을 수 있습니다. 이것이 풀기는 어렵지만 결과 확인은 쉬운 문제의 예 입니다. 

실제 블록체인에서는 해시(Hash)라는 것을 찾는데 위 숫자 계산처럼 확인은 쉽지만 풀기는 어려운 문제를 열심히 풀고 있습니다. 아무 문제나 출제하는 것이 아니라 바로 지휘관의 명령을 해시로 바꿔 문제를 출제합니다. 이렇게 하면 지휘관의 명령을 수정하게되면 해시값이 달라져 바로 잘못된 명령임을 알 수 있게 됩니다.

블록체인이 에너지를 엄청 소비하고 있는 이유가 바로 이 계산을 하기 때문 입니다. 이것을 작업 증명(Proof of Work)라고 하는데 에너지 소모가 너무 커서 비트코인이 아닌 이더리움의 경우 이제는 작업 증명이 아닌 지분 증명(Proof of Stake)이라는 것으로 바꿔 에너지 소모를 줄이고 있습니다.

이렇게 문제를 풀고, 명령을 전달해준 장군의 서신까지 동봉하여 다른 장군에게 전달하는 것입니다. 이렇게 하면 중간에 명령을 바꿀려고 해도 이전 장군들의 명령까지 전부 바꾸고, 그들이 푼 문제의 답도 다시 찾아서 만들어야 합니다. 문제를 푸는데 10분씩 시간을 주는데 첩자가 정보를 바꾸려면 다른 모든 장군의 문제 푸는 속도를 압도해서 문제도 빨리 풀고, 이전 문제까지 전부 해결해야 합니다. 10분안에 이 모든것을 할 수가 없기 때문에 해킹이 불가능 하다는 말이 나오는 것입니다.

 

정리

간단하게 비잔틴 장군 문제를 알아보았습니다. 블록체인 합의에서 핵심이 되는 문제로 지금도 다양한 방법으로 비잔틴 장군 문제를 해결한 여러 블록체인이 나오고 있습니다. 지금은 블록체인의 열기가 조금 사그라 들었지만 계속 발전하고 있는 분야입니다.