비트코인은 어떻게 비잔틴 장군의 딜레마를 해결했나? (feat. 게임이론)

bumblebee2018 (58)in #kr • 7 years ago (edited)

비트코인을 설명할때는 항상 비잔틴 장군의 딜레마 이야기가 나옵니다.

분산형 시스템의 난제라는 비잔틴 장군의 딜레마를 어떻게 사토시 나카모토가 비트코인을 통해 해결했다는 것일까요?

그리고 사토시 나카모토가 게임이론을 이용해 블록체인을 설계했다는 이야기도 있습니다.

게임이론이 뭐길래, 블록체인을 유지하는 중요한 이론이라고 하는걸까요?

블록체인은 51%의 선의의 노드에 의해 유지된다는 이야기는 뭔 소리일까요?

누군가 쉽고 명쾌하게 설명한 분이 있나 싶어서 여기 스팀잇의 글들을 검색해봐도 찾지 못했습니다.

그냥 비트코인은 비잔틴 장군의 딜레마를 해결했고 비트코인에서 게임이론이 중요하다고 합니다.

왜? 와이? 뭣땀시?

스팀잇, 네이버 다 검색해도 제가 이해할만큼 명쾌하고 쉽게 설명된 글은 없었습니다.

그래서 범블비 @bumblebee2018 가 공부하고 또 공부하고, 고민하고 또 고민해 봤습니다.

공부한 바를, 최대한, 쉽게 설명해 보겠습니다.

비잔틴 장군의 딜레마에 대한 설명을 먼저 해보겠습니다.

적을 공격하는데 과반이 참여해야만 승리(분산 시스템을 유지)하는 싸움에서 누군가 배신자가 있을수 있는 5명의 장군들이 멀리 떨어져 있어 얼굴 맞대고 토론은 못하고 빠른 속도로 달려갈수 있는 전령(인터넷 네트워크)만 보낼수 있는 상황에서 어떻게 공격시간에 대한 합의를 이룰 것이가에 대한 문제입니다.

원래는 여러명의 장군인데 생각하기 편하게 5명의 장군으로 했습니다. 그러면 과반은 3명 이상이니까, 최소 3명 이상이 동시에 공격해야 승리(분산 시스템을 유지)할수 있다는 이야기가 됩니다.

3명, 7명, 1000명 이런걸로도 설명 가능합니다. 하지만 설명의 편의상...
2명은 안되요. 2명이면 "과반"이 아니라 "모"아니면 "도"라서.

아쒸, 쉽게 설명한다더니 이게 무슨 멍멍이 소리야?

죄송합니다. ㅠ.ㅠ

장군 5명은 편의상 A B C D E로 부르겠습니다.

이 5명의 장군중 일부는 합의를 이끌어내서 공격을 성공으로 이끌고 싶어하고 일부는 배신자입니다.

이들이 합의를 이끌어 낼수 있도록 돕기 위해 사카시 나카모토는 작업증명 방법을 씁니다.

즉, 아무나 공격 시간을 주장할수 있는 것이 아니고 문제를 최대한 빨리 푼 사람이 공격시간을 주장할수 있게 한겁니다. 그리고 그 문제는 푸는데 10분 가량 걸립니다.

문제 푸는 순서야 무작위겠지만, 편의상 A가 제일 먼저 풀어서 그 답과 함께 9시 공격을 주장합니다. 여기서 중요한것은 비트코인의 작업증명에서 답과 주장은 서로 묶여 있습니다. 답을 그냥 두고 주장만 바꿀수 없습니다.

두번째로 B가 풀었는데 B의 선택은 둘 중 하나입니다. 선의를 가졌다면 똑같이 9시 공격을 주장할것이고 악의를 가진 배신자라면 10시를 주장해서 혼란을 주려 할겁니다.

B가 배신자라도 10분만에 A가 풀었던 문제의 또다른 답과 자신의 답, 2가지를 동시에 풀어서 A의 주장까지 10시로 바꿀 이유는 없습니다. 답과 주장은 묶여 있기 때문에 A의 답은 그대로 두고 주장만 고치려면 들통 납니다.
2문제를 10분만에 풀자면 2배로 빨리 풀어야 하니 그런 식으로 배신하기는 매우 어렵습니다. 그리고 그건 9시 공격 주장에서 10시에 다같이 공격하자는 주장으로 바뀐거라 배신의 의미도 없습니다.

아마도 A의 9시 주장은 그대로 두고 그냥 10시 주장 하나를 더해서 9시, 10시 두 주장이 동시에 전달되도록 할겁니다.
그러나 배신자가 B혼자라면 나머지 장군들은 9시든, 10시든 어느 한쪽으로 의견을 모으려 할 것이고 결과적으로 B의 배신은 실패합니다. 9시로 의견이 모이든 10시로 모이든 배신자 1명을 제외하면 4명의 장군이 동시 공격을 할것입니다.

만약 B가 배신하지 않아서 똑같이 9시로 주장했다고 하겠습니다.
세번째로 C가 답을 풀었는데 배신하고 10시로 주장하고 싶으면 이번에는 B가 배신하는 경우와 달리 C는 10분만에 B가 푼 문제의 또다른 답까지 찾아서 B 주장까지 한꺼번에 8시(9시나 10시 외의 다른 어떤 시간이든)로 바꿔야만 합니다.
왜냐하면 A, B가 9시로 주장한 상태에서 혼자 10시로 주장해봐야 더 있는지 없는지도 모를 다른 배신자가 도와주지 않으면 그 의견은 버려지기 때문입니다. C는 배신하려다가 계산 빨리 하느라고 머리에 쥐가 납니다. 범블비 @bumblebee2018 머리도 쥐가 납니다. 폭발 직전입니다.

그다음 순서인 D, E는 더 말할 것도 없습니다.
A, B, C가 똑같이 9시로 주장한 상태에서는 그중 하나나 둘의 주장을 조작하지 않고 자신만 10시라고 주장하면 100% 배신은 실패합니다. 이미 9시에 과반의 주장이 모여 있는 상태라서 그렇습니다.

이런식으로 사토시 나카모토는 비잔틴 장군의 딜레마를 해결했습니다.

비트코인으로 비잔틴 장군의 딜레마 해결하기 참 쉽죠? ㅋㅋ

범블비 너 좀 맞고 시작하자, 퍽퍽퍽,,,, 헉, 컥컥...