[알쓸신블] 제2장 비잔티움 장군의 딜레마

ABOUTTHETICO 0 38

비잔티움 장군의 딜레마의 탄생 배경을 찾아보는 중, 약 1970년도 NASA의 ‘분산화 컴퓨팅 프로젝트 갈릴레오’에 대하여 찾게 되었습니다. 해당 프로젝트의 진위 여부를 찾아내지 못하였지만, 비잔티움 장군의 딜레마를 이해하는 것에 좋은 예시가 되어 글에 포함시킵니다.

 

‘비잔티움 장군 문제’ 의 탄생

이전부터 비슷한 문제가 논의된 것으로 알고 있지만, 비잔티움 장군 문제는 레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 처음 언급됐다.

(해당 예제의 사실 여부는 완벽하게 파악 되지 않았습니다.)

 ‘비잔티움 장군 문제'는 1970년대 활발했던 ‘분산화 컴퓨팅’에서 비롯 되었다고 생각한다. 1970년대 NASA는 비용절감을 위하여 슈퍼 컴퓨터가 아닌, 민간인 컴퓨터의 컴퓨팅 파워를 임대하기로 하였고, 민간인 컴퓨팅 파워 모집 공고를 냈다. 슈퍼 컴퓨터 운용 비용 보다, 민간인 컴퓨팅 파워를 임대하는 편이 효율이 좋았기 때문이다.
 하지만 ‘1+1 = 2’라는 답을 제출해야하는 컴퓨터가 ‘1+1 = 3’이라는 답을 제출하여 문제가 생겼다. 즉, 옳은 컴퓨팅 파워를 제공하는지 옳지 않은 컴퓨팅 파워를 제공하는지 판단 할 수 없었다.


출처 : (https://history.nasa.gov/computers/Ch6-3.html)

 

이러한 이유로 ‘분산화 컴퓨팅'은 실패 했고, 위 예제를 포함한 다양한 원인들로 ‘비잔티움 장군 문제'라는 논문이 발표 되었다.

 

비잔티움 장군 문제

  • 5명의 장군은 각각 100명의 병력을 소유하고 있다.
  • ‘류짱의 성’ 에는 300명의 병력이 있어, 4명의 장군(400명)이 동시에 공격을 해야 한다.
  • 지리적인 문제로 각 장군은 자신의 오른쪽 장군에게만 소통할 수 있다.
  • 5명의 장군 중에 배신자 있을 수 있다.

 

  • 4명의 장군이 동시에 공격하기 위해서는 배신자를 찾아내거나, 배신자가 없기를 기도하는 수 밖에 없다.

  • 1번 장군은 오후 3시에 공격하자는 서신을 보낸다.

  • 4번 장군은 서신을 수정하여 오후 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번 장군에게 다음과 같은 깜지를 전달 한다.

[1번 장군이 2번 장군에게] / [2번 장군이 3번 장군에게] / [3 -> 4]

메시지를 전달 할 때마다, 전달 되는 메시지의 양은 늘어나게 될 것이다.

 

 

4번 장군은 5번 장군에게 시간을 ‘거짓'으로 전달 해야하지만, 3개의 메시지에는 ‘3시 공격’이란 메시지가 적혀있다.

이전과 같이 4번 장군이 ‘조작된 메시지'를 넘기려해도 5번 장군은 1~3번 장군이 작성한 메시지를 함께 받게 된다. 약 75%의 메시지는 ‘오후 3시’약 25% 메시지는 ‘오후 4시'를 표시하고 있을 것이다.

 

여기서 5번 장군은 이전과는 다르게 선택을 할 수 있다. 75%를 믿을 것인지, 25%를 믿을 것인지.

 

 

 

아무리 최선을 다하여 메시지를 적어도, 한계가 존재 할 것이다.

일정 시간(블록 생성 시간) 동안 작업을 하여, 다음 사람에게 넘기고 다음 사람도 일정 시간 동안 작업을 하므로 조작을 불가능하게 만드는 것이다.

비트코인은 Proof Of Work를 통하여 ‘비잔티움 장군 문제'를 해결 했다고 평가 받고 있다

 

[참고 문헌]

비잔티움 장애 허용 - 위키백과, 우리 모두의 백과사전
이 분야의 연구는 비잔티움 장애(Byzantine faults)라고 불리는 시스템에 생길 수 있는 임의의 장애를 견딜 수 있는 시스템을 만들기 위한 것이 목적이다. 이 비잔티움 장애는 단지 시스템이 멈추거나 에러…ko.wikipedia.org
[Blockchain Study] PBFT(Practical Byzantine Fault Tolerance) - Steemit
PoW, PoS, DPOS 등 다양한 합의 알고리즘(Consensus Algorithm)이 블록체인에 나오고 있는 현재, 또 다른 중요한 합의 알고리즘을 꼽으라고 한다면 당연 PBFT일 것이다…steemit.com
블록체인의 기본개념 - PoW와 PoS 알아보기
비트코인과 관련해 채굴(Mining)이라는 말, 많이 들어보셨을 겁니다. 비트코인으로 이뤼진 모든 거래는 블록안에 블록체인에 저장됩니다. 블록체인 상에 존재하는 블록의 유효성을 검증하는 방식을 PoW(Proof…brunch.co.kr


 

출처: 류기혁, http://bitly.kr/IkQh

0 Comments