비잔틴 장군 문제

[ 최종수정 - 20x0508(금)20시30 ]

---

1. 시작 : Two Generals' Problem

①장군A1과 장군A2가 있고 공격할 대상인 도시가 있고 두 장군사이를 가로막는 계곡B가 있고 그 계곡B는 도시 수비군이 통제하고 있다. 

  

②두 장군은 동시에 공격해야 도시를 함락시킬 수 있고, 따로 공격하면 오히려 전멸한다.

③장군A1이 공격시간을 정하여 장군A2에게 연락병을 보내 전달했을 때 A1은 A2가 그 공격시간에 동의했는지 알기 전에는 공격을 개시할 수 없다. 일단 대기

④A2가 연락병으로부터 공격시간을 전달받은 경우. A1이 A2(=자신)의 공격시간 동의사실을 확인하고 공격 개시를 확정했는지 확인하기 전까지는 공격을 개시할 수 없다. 즉 확인사실을 전달하는 연락병을 A1에게 보내고 대기.

⑤ 이 부분이 딜레마의 핵심에 해당하는 데 A1이 A2로부터 온 연락병의 확인사실을 듣더라도 다시 A2가 그 확인사실을 확인한 사실을 알고 공격 개시를 확정하기 전까지는 공격을 확정할 수 없다. 그래서 다시 ③으로 돌아가 연락병을 보내고 대기해야 한다. 당연히 또 ④의 상황이 되고 ⑤와④가 무한반복될 뿐 대기상태를 풀 방법이 없다.

▶이 문제는 불확실한 통신 상황에서 상호 동기화를 시도할 때의 겪게되는 딜레마를 표현한 것인데 해결할 수 없는 것으로 판명된 최초의 컴퓨터 통신문제이고, 합의 알고리즘에 대한 연구가 시작되는 지점이다.

2. 문제의 확장 : 비잔틴 장군 문제
                     ( 문제를 제시한 논문 PDF 링크 )

▶Trusted Third Party의 존재를 배제한 상태에서 합의를 이끌어내기 위한 방법이 존재하는가?라는 질문에 대하여 다양한 방식의 시도들이 실패로 귀결된다는 사실을 증명하기 위해 사용된 비유이다.

▶두 장군 문제를 일반화한 문제로 소개되지만 여러 조건 설정에 따라 결국 본질적으로 두 장군 문제로 귀결되어 해결불가로 판정되는 경우도 있지만 그와는 다른 논리를 따르면서 실패로 증명되는 경우도 포함하므로 두 장군 문제와는 별개의 문제로 보는 것이 적절하다. 이 문제를 통해 본격적으로 합의알고리즘이 갖춰야 할 필수조건들에 대한 검토가 이루어 졌다는 측면에서 의미를 가진다. 

▶비잔틴 제국의 여러 장군들이 하나의 적군 도시를 공격하기 위해 출병한다. ▷적은 매우 강해서 과반수 이상의 장군들이 같은 시각에 공격해야만 승리하고, 그렇지 않으면 패배▷모든 장군들간의 소통은 연락병 보내는 방법 밖에 없다.▷장군들 중에는 배신자가 있을 수 있어서 서로 신뢰할 수 없다.( 배신자는 가짜 공격 명령을 보낼 수도 있다. )▷서로 신뢰할 수 없는데 공격시각을 어떻게 합의할까?

3. 문제의 해결 : 작업증명을 통한 합의알고리즘

조건1▶모든 메시지는 비가역적으로 누적된다.(=블록체인)

조건2▶모든 추가 메시지는 충분한 비용을 지불(=작업증명)하여 작성권한을 획득한 자에 의해서만 작성되고 작성권자는 메시지 기입을 원하는 자들로부터 신뢰에 상응하는 보상(=전송수수료)을 지급받고 그 보상에 따라 선별된 메시지를 가장 신뢰받는(=긴) 누적메시지에 추가한다.

조건3▶모든 추가 메시지는 작성 즉시 전체 네트워크로 공유되고, 추가메시지 작성권한을 획득한 자가 가장 긴 누적메시지를 찾아내지 못할 가능성은 없어야 한다.

악의1▶작업증명없이 추가블럭의 작성권한을 획득하려는 시도 : 현재의 256비트 암호체계를 뚫고 이런 권한을 획득하는 것은 정상적인 작업증명보다 훨씬 큰 비용을 요구하며, 사실상 얼마의 비용을 지불하더라도 기술적으로 불가능하므로 성공할 여지가 없다.

악의2▶정상적으로 작성권한을 획득한 자의 메시지 위조 시도 : 작성권한자는 수수료를 지불하고 편입되기를 원하는 메시지를 고를 수만 있고 그 메시지를 통제할 권한은 갖지 못한다. 메시지를 고르는 권한 자체도 지불 수수료와 대기순번에 따른 기계적인 선별일 뿐 자의적인 특정메시지의 배제도 불가능. 즉 정상적인 작성권한 획득자는 보상을 취할 뿐 메시지 자체에는 관여할 수 없으므로 시도는 실패한다.

악의3▶정상적으로 작성권한을 획득한 자가 가장 긴 체인을 배제하고 추가블럭을 생성하려는 시도 : 예를 들어 이미 100번 블록이 생성된 상황에서 99번 블록에 새로운 블럭을 붙이는 경우. 이후 증명을 얻은 자에게는 100번 블록을 가진 두 종류의 체인이 제시된다. 당연히 101번 블록은 먼저 생성된 100번 블록에 추가될 것이고 악의자가 생성한 블록의 무의미해진다. 이를 통해 어렵게 취득한 작성보상도 소멸하므로 이득은 없고 손해만 있는 행동을 할 여지는 거의 없으며 시도하더라도 실패한다. 즉 이중방어장치가 작동한다.

결론 또는 의미▶나카모토 사토시의 비트코인 네트워크에서 구현된 작업증명을 통한 합의알고리즘은 비잔틴 장군 문제를 푸는 데 필요한 요구조건을 제시했고, 그 조건을 만족시키는 시스템의 예시를 보여줬고, 그 예시는 문제를 실제로 풀었음을 증명했다는 의미를 가진다. 신뢰받는제3자의 개입(=확인,인증)없이도 P2P 네트워크 상에서 신뢰할 수 있는 합의를 누적하고 공유할 수 있는 기술적인 기반을 구축한 셈이다. 위에서 제시된 조건과 악의는 대충 이해를 돕기 위해 꽤 단순화하여 예시한 것으로 포괄적으로 상세한 검토는 이런 블로그가 아니고 논문을 뒤져서 확인해야 할 것임.

4. 특이점 : 신뢰받는제3자의 개입을 배제한 시스템

 여하튼 비트코인내지 블록체인이라는 기술적인 기반의 탄생은 꽤 의미심장한 특이점을 형성하고 있다는 생각이다. 우리가 아는 대표적인 신뢰받는 제3자는 경제에서는 전세계 통화의 기축을 이루는 FRB 달러 시스템이고, 정치에서는 유엔을 통해 공신력이 확인되는 국가시스템, 학술이나 문화 관련해서는 권위를 가진 저널 같은 형태를 취한다.

 여차하면 이런 걸 떠나서도 시스템이 구축되고 작동할 수 있다는 가능성이 제시된 셈인데 생각해보면 어마어마한 일이나 아직은 그냥 작은 불씨, 잠재력, 가능성에 불과할 뿐이고 갑자기 세상이 확 바뀔리는 만무하다. 뭐 그래도 조금씩 다음 단계는 여기 저기서 뜬금없는 형태로 기존의 단계를 잠식해 갈 것임은 피할 수 없어 보임.