비잔틴 장군 문제와 작업증명(PoW), 자산증명(PoS)

<출처: https://medium.com/all-things-ledger/the-byzantine-generals-problem-168553f31480>
블록체인은 비잔틴 장군 문제(Byzantine Generals Problem)라는 컴퓨터 과학 분야의 난제를 해결한 솔루션으로 유명하다. 비잔틴 장군 문제는 분산화 된 컴퓨터 시스템의 신뢰성 문제를 비잔틴 제국의 장군들이 처한 상황에 비유한 것으로 IT계의 노벨상이라고 불리는 튜링상 수상자 레즐리 램포트가 쇼스탁, 피스가 공저한 1982년 논문(The Byzantine Generals Problem, Leslie Lamport, Robert Shostak, Marshall Pease, 1982)에서 언급한 개념이다. 비잔틴 장군문제는 두장군 문제(Two generals' problem) 에서 파생되었다.

<출처: 위키피디아>

두 장군 문제는 두 장군이 이끄는 두 부대 A1 A2가 적군 B를 공격하여야 한다. 하지만 둘다 환경적인 영향으로 소통할 방법이 없고 오직 부대원을 보내 의사를 전할 수 있지만 부대원은 중간에 잡힐 수 있다. 전략상 같은 시간에 한꺼번에 공격을 해야 하지만 합의할 방법이 없고 오직 무한개의 메시지를 연락병에 의해 주고 받는 방법 밖에 없다. 예를 들어 지구상의 어벤져스와 우주의 가디언즈오브 갤럭시는 타노스를 동시에 공격해야 하지만 서로 연락할 방법이 없다. 오직 인턴인 스파이더 맨이나 사춘기 그루트 등을 서로 보내 의사를 확인하는 수 밖에 없지만 중간에 스파이더 맨이 타노스에게 잡힐 수도 있고 그루트가 반항심으로 도망쳐 버릴 수도 있기 때문에 어벤져스 멤버와 가디언즈 오브 갤럭시 멤버를 무한으로 지구와 우주를 왔다 갔다 하는 방법 밖에 없지만 이는 너무 시간이 많이 걸리고 비효율적이다.(슈퍼 히어로 들에겐 전혀 문제가 안될 수도 있겠다.)

<출처: 영화 어벤져스: 인피니티 워>
비잔틴 장군문제는 두장군문제를 일반화한 것이다. 공격하는 부대들이 세 부대 이상이고 각 부대에는 장군이 있으며 이 부대는 분산되고 고립되어 있어 연락할 수 있는 방법은 연락병을 통해 메시지를 보내는 방법 밖에 없으며 각 부대들 중에는 장군 혹은 부대원이 배신자가 섞여 있다. 이러한 상황에서 어떻게 동시에 공격하는 전략에 공동의 합의에 이를 수 있는지에 대해서 솔루션을 도출하는 것이다. 논문 상에서는 어떤 가정하에 해결할 수 있는 해결책을 도출하는데 우선 말로 메시지를 전할 때는 신뢰하는 장군들이 2/3가 넘을 때 공동의 합의를 도출할 수 있고 장군은 3명 이상이어야 하며 배신자가 m명일 때는 3m+1명의 신뢰자가 있어야만 한다. 만약 서명한 서신을 메시지로 전달한다면 장군이 세명이고 한 명의 배신자가 있더라도 합의에 이를 수 있으며 배신자가 m명일 때는 메시지의 경로(message path: 메시지를 직접 전해 듣는 것이 아닌 다른 장군들의 경로를 통해 듣는 것)가 m+1이 되면 합의가 가능하다고 한다. 하지만 이는 많은 시간과 에너지를 필요로 하므로 비효율적이다.(논문에서도 이를 언급한다.) 어벤져스, 가디언즈 오브 갤럭시에 와칸다군을 포함하여 생각하면 된다. 이들이 동시에 타노스를 공격했어야 하는데 비잔틴 장군 문제로 인해 어벤져스 인피니티 워에서는 결국 타노스에게 산발적으로 공격하는 바람에 모두 사라져 버리는 비극이 일어난다.

이 비잔틴 장군문제는 오랜 기간동안 컴퓨터 과학계의 난제로 남아 있었는데 비트코인의 합의 알고리즘안 작업 증명(Proof of Work)이 이 문제를 푸는 새로운 솔루션으로 떠오른다. 비트코인의 창시자 사토시 나카모토는 분산네트워크에서 임의의 참가자들 사이에서 네트워크를 약화시키려는 악의적인 공격으로 부터 안전하게 합의의 도달하여 업데이트 권한을 주고 시스템을 유지할 수 있을까에 대한 문제를 작업 증명 알고리즘을 도입하여 해결하는데 이는 Adam back의 hash cash 알고리즘을 이용하여 각 노드가 자신의 컴퓨팅 파워를 이용하여 블록의 논스(nonce)라는 수의 값을 찾아내는 노드에게 블록 업데이트 권한을 주고 비트코인으로 이에 대한 보상을 함으로써 시스템을 유지해 가는 것이다. 이를 비잔틴 장군문제에 대입한 에버노트 창업자의 유명한 설명이 있다.

“모든 장군이 수학문제를 풀기 시작한다. 이 문제는 모든 장군이 머리를 맞대면 10분 정도가 걸려야 풀린다. 한 장군이 답을 찾아내면 다른 모든 장군에게 그 답을 공표한다. 그러면 모든 장군은 다음 문제로 넘어가 또 답을 찾는다. 다음 문제 역시 푸는 데 10분 정도가 걸리는 문제다. 모든 장군은 그들 중 누군가가 바로 앞에서 찾아낸 정답에 새로운 문제의 답을 이어 붙이는 식으로 작업을 계속한다. 이 과정을 거쳐 12번째로 찾아내 앞선 답에 덧붙인 해답이 나오면 모든 장군은 확신할 수 있다. 이 과정에 참여한 컴퓨터 계산능력의 절반 이하를 가진 어떤 공격자도 이와 비슷한 길이로 정답 묶음을 만들 수 없다는 사실을 말이다. 즉 블록 12개로 이뤄진 블록체인은 사용자 다수가 체인 생성 작업에 참여했다는 사실을 방증한다. 이를 작업 증명 체계라고 부른다.” - 출처: 넥스트머티 비트코인, 김진화 지음

이 작업증명은 오랫동안 풀리지 않은 난제의 획기적인 해결책을 제시하기는 했지만 문제점도 있다. 컴퓨팅 파워를 이용해야 하기 때문에 엄청난 전력 소모를 해야 하고 분산화 되어야 할 업데이트 권한이 채굴자가 집중화 될 수 도 있는 가능성이 크기 때문에 중앙 집중화 된 방식과 차별이 없다는 주장도 있다. 이러한 문제점을 해결하기 위해 나온 새로운 개념의 합의 메커니즘들이 많은데 그 중에 하나가 자산증명(PoS: Proof of Stake) 이라는 합의 메커니즘이다. 자산증명은 자산 즉 암호화폐의 소유량에 비례하여 업데이트 권한을 주는 메커니즘이다. 블록에 자산 증명 리스트를 가지고 있어서 그 리스트의 자산의 합이 가장 큰 블록을 정당한 블록으로 합의하다. 특정화폐의 소유자일 수록 화폐가치의 유지 및 상승의 인센티브가 높기 때문에 신뢰성 있게 블록을 검증하고 업데이트 할 가능성이 높으며 작업 증명에 비하여 중앙 집중화의 위험성이 낮고 전력 소모를 줄일 수 있다는 장점을 가지고 있으나 참여 노드들이 자산을 두개의 블록에 한번에 베팅할 수 있는 Nothing at Stake(두개에 베팅해도 잃을게 없으므로)가 있어 네트워크 보안이 취약해 질 가능성이 있지만 이 문제점은 이러한 행위에 벌금을 부과하는 등의 조치로 개선안을 찾고 있는 상태다. 세계 2위 블록체인인 이더리움의 경우 현재 작업증명을 사용하고 있지만 자산증명으로 전환하는 것을 추진하고 있다.