비잔틴 장군의 딜레마

블록체인을 언급할때 빠질수없는 것이 비트코인이고, 비트코인을 언급할때 반드시 이해해야할 문제가 "비잔틴 장군의 딜레마"가 아닐까 싶습니다. 이전까지 분산 컴퓨팅의 난제였던 비잔틴 장군의 딜레마를 비트코인에서 해결했기 때문입니다.

비잔틴 장군의 딜레마는 레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 처음 언급됐습니다. 다음 그림과 같이 비잔틴 시대에 적군의 성을 둘러싼 영지를 차지하고 있는 비잔틴 장군들이 있습니다. 적군의 성을 차지하기 위해 장군들은 같은날 같은시간에 동시에 과반수 이상의 군대로 공격을 해야합니다. 과반수 이상이 동시에 공격하지않는경우 전쟁은 반드시 패하게 됩니다. 각각의 장군들중에는 전투에 승리하는것을 원한지않는 배신자가 포함되어있지만 누구인지 알수가 없습니다. 장군들간의 연락은 반드시 1대1로 통신병을 통해서만 가능하고, 다수간에 동시연락을 할수가 없습니다. 전투에 승리하게 위해 장군들은 같은날 같은시간에 과반수 이상이 함께 공격에 참여할수 있는 방법을 생각해내야 합니다.

[그림 참조]

이 문제는 분산컴퓨팅에서 어떻게 신뢰를 얻을수 있는지에 대한 해법을 요구하고 있으며, 이것에 대한 해법은 다음과 같이 정의할수 있습니다.

모든 장군은 동시에 푸는데 10분이 걸리는 수학문제를 풀기를 시작하며 이 문제를 풀어야만 공격시간을 알수가 있습니다. 문제를 푼 장군은 다음 장군에게 문제의 해답과 풀이과정을 전달합니다. 다음 장군은 문제의 해답을 확인한후에 다시 10분간 문제풀기를 시작하여 해답을 찾고, 그것을 이전해답에 붙여서 연결하고 이 과정을 반복하여 연속된 해답을 만들어냅니다. 만약 중간에 배신자가 잘못된 정보를 보내기 위해 거짓정보를 포함하여 전달하게 되면, 이전값과 비교하여 잘못된 해답임을 바로 알수 있기때문에 해당 정보는 리스트에 포함되지않습니다. 이 과정이 모두 완료되면 모든 장군들은 정답리스트를 신뢰할수 있게되고, 공격시간이 정확한 시간임을 확신할수 있습니다.

비트코인을 개발한 사토시 나카모토는 그의 논문(영문,국문)에서 이 문제의 해결책을 제시하였습니다. 

비트코인에서는 거래의 목록을 이용하여 블록헤더를 생성하고, 고정된 블록헤더의 값과 함께 가변적인 Nonce값을 변화시켜, 10분간 특정 값보다 작은 Hash 값을 계산해냅니다. 이렇게 계산한 값을 블록에 포함하여 체인에 연결하고, 이과정을 반복하여 체인을 늘려갑니다.

비트코인에서의 합의 알고리즘인 작업증명(Proof of Work)은 이전글을 참고하시면 되겠습니다.