Decenter University+ chain

공유하기

닫기

[비트코인개론]<3>컴퓨터 공학의 난제를 풀다 '비잔틴 제국의 문제'

'배신자 섞인 장군들이 보내는 메시지를 어떻게 믿을 것인가'
작업증명 거친 장부만 수용키로
82년 이후 컴퓨터공학 난제 해결 "획기적 사건"

  • 김흥록 기자
  • 2018-04-30 14:22:51
[비트코인개론]3컴퓨터 공학의 난제를 풀다 '비잔틴 제국의 문제'

“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야 하고요, 또 모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 하지요. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제입니다.”

이 말꼬리 잡는 암호문 같은 문구는 제임스 A 도날드라는 인물이 2008년 11월 13일 아침 7시 께 사토시 나카모토에게 보낸 이메일의 일부분이다. 제임스 A 도날드는 2008년 사토시 나카모토가 비트코인을 개발한다는 소식을 알린 이후 이와 관련해 이메일을 여러 차례 주고 받으며 사토시와 함께 작업한 인물로 알려져있다.

도날드가 메일에서 이야기한 내용은 컴퓨터 네트워크 분야에서 주로 다루는 ‘두 장군의 문제(Two Generals Problem)’에서 출발한다. 두장군의 문제는 이후 ‘비잔틴 장군의 문제(Bizantine Generals Problem)’로 확장한다. 비트코인에 앞서 여러 전자 화폐 시스템들이 풀려고 도전했지만 완전히 풀지 못했던 바로 그 문제다.

분산원장 체계는 제대로 돌아가기 위해서는 넘어야 할 산이 많다. 원장을 공유하는 참여자들이 정직하게 행동할 것이라고 어떻게 보장할 수 있을 것인가. 누군가 속이려 들더라도 모두가 지닌 원장이 같은 내용을 유지할 수 있는 방법이 있을까. 이런 골칫거리가 비트코인에서의 비잔틴 장군의 문제다.

사토시는 어떤 방법으로 비잔틴 장군의 문제를 풀었을까.

[비트코인개론]3컴퓨터 공학의 난제를 풀다 '비잔틴 제국의 문제'
아군인 A1와 A2는 B를 점령하기 위해서는 인편을 통해 공격시간 등을 주고 받아야 하지만, 메시지가 B의 지역을 무사히 지났는지 확신하기 힘들어 결코 합의에 달하기 어렵게 된다.

두 장군의 문제는 1972년 등장한 일종의 가상 실험(사고 실험)이었다. 두 아군 부대의 장군 A와 B가 적군이 점령한 한 도시의 양옆에 주둔한 상황이다. 적군을 점령하려면 두 부대가 한 날 한시에 공격을 해야 하지만 연락을 주고 받기 위해서는 연락병이 직접 적군의 도시를 통과해야만 한다. 항상 적군이 메시지를 중간에 가로챌 위험에 처해 있는 셈이다.

A는 B에게 공격 일시를 담은 메시지를 보냈지만 잘 도달했는지 확신을 하지 못한다. 이에 B가 메시지를 잘 받았다면 A에게 확인 답장을 보내줘야 하는데 B역시 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다. 이에 B를 안심시키고 함께 공격을 하기 위해서는 A가 답장을 받았다고 재답장을 해야 하지만 이 역시 B에게 잘 도달 했는지 장담하지 못한다. 결국 A와 B 두 장군은 자신이 마지막으로 보낸 메시지가 잘 도착했는지 항상 확신할 수 없는 상황에 빠지게 된다. 이는 두 장군이 같은 수준의 합의에 도달할 수 없고 이 불확실성은 결국 함께 적의 도시를 공격할 수 없다는 의미다. 이후 이 문제는 실제로 해결이 불가능한 것으로 증명됐다. 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 결코 같은 내용의 거래기록을 갖는 데까지 도달하지 못한다는 의미다.

장군이 두 명이 아니라 여러명인 상황을 가정한 것이 비잔틴 장군의 문제다. 제임스 도날드가 메일에서 직접 남겼듯 1982년 래슬리 램포트와 로버트 쇼스택, 마샬 피즈가 함께 쓴 논문에서 소개 된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제다. 비트코의 참여자는 두 명이 아니라 수만명이 될 수 있으므로 두 장군의 문제보다 여러명의 참여자가 있는 비잔틴 장군의 문제가 사토시 입장에서는 보다 직접적으로 뛰어넘어야 할 장애물이었다.

두장군의 문제와 비슷하지만 상황이 조금 다르다. 비잔틴 제국은 광활한 영토 각 지역마다 장군들이 통치를 했다. 이웃나라 공격이 성공하려면 한 날 한 시에 모든 장군들이 이끄는 병력을 집중시켜야 하는데, 멀리 떨어진 각 장군들이 정확한 공격 시간과 공격 장소, 참가 여부를 올바르게 전달하지 못한다면 병력이 분산돼 공격을 실패하고 만다. 장군들 가운데 첩자가 있어 공격 명령을 퇴각 명령으로 둔갑시킬지도 모를 일이고 실수로라도 잘못된 메시지를 전달할 가능성은 항상 있다. 사령관이 전달한 것과 동일한 내용의 전령이 각 장군들 사이 오가게 할 방법이 있을까. 아니, 적어도 틀린 메시지를 받더라도 이를 구분해낼 수 있을까. 항상 모두가 같은 답을 가진 상황을 유지하게 할 방법이 있을까. 이 같은 답을 찾는게 비잔틴 장군 문제의 핵심이다.

도날드가 던진 ‘모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 한다’는 지적은 결국 비트코인 참여자들이 서로가 가진 잔고나 송금 거래 내 역 등 모든 정보를 제한 없이 주고 받을 수 있는 것 뿐 아니라 네트워크 전체가 동일한 장부를 들고 있다는 사실을 확신할 방법이 있느냐는 질문이었다. 비트코인의 소유권부터 송금 상태, 송금의 유효성, 장부의 생성 과정 등 네트워크 전체가 배신자와 상관 없이 이런 정보를 동일하게 업데이트해 나갈 방법이 있는지를 묻는 질문이기도 했다.

비트코인 이전까지, 특히 컴퓨터 공학 분야에서는 비잔틴장군 문제를 극복하는 방법으로 장군들 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 항공기를 생각해보자. 항법장치가 올바르게 작동하려면 곳곳에 설치된 센서가 항상 같은 고도와 위치 정보를 보내야 한다. 한 센서라도 다른 정보를 준다면 재빨리 다른 센서들이 준 값과 비교해 어느 값을 따를지 결정해야 한다. 이는 비잔틴 장군의 문제다.

중요한 것은 어느 한 센서가 잘못된 신호를 준다고 해서 비행중 항법장치가 멈추는 일이 있어서는 안된다는 점이다. 비잔틴 장군의 문제가 발생하더라도 잘못된 메시지는 잘못된 채로 둔 채 계속 작동할 수 있도록 설계가 돼야 한다. 이를 컴퓨터 공학에서는 비잔틴 장애 허용(BFT·Bizantine Fault Tolerance)이라고 부른다.

학자들은 BFT의 가장 기본적인 전제로 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명해냈다. 센서가 세 개 일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 실제 항공기에는 고도 측정장비가 최소 3대 이상 들어가며 하나의 센서가 고장 났을 때를 대비한 예비 센서도 두고 있다. 위치 정보를 파악하는 관성항법장치 역시 통상 3대를 설치하며 이와 별도로 위성에서 위치정보를 받는 GPS 수신장치나 지상에 있는 항공기 위치 보정장치의 신호를 활용하기도 한다.

특히 보잉 777와 787의 자동항법 장치에는 비잔틴 장애 허용 기술을 직접 적용하고 있다고 한다. 국내에서 유일하게 보잉787 기종을 다루고 있는 대한항공 정비기술부/Avionics기술팀의 설명을 들어보자.

“최신 787등의 항공기들에서 적용되는 비잔틴 장군의 문제 관련 결함 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러개 만들어 내고, 이를 데이터가 필요한 설비에 여러게 라인을 통해 송신합니다. 자동항법장치에서는 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지 여부를 확인하고 상호 비교를 통해 무결성을 확보하는 방법으로 설계돼 있습니다.”

결국 데이터의 수와 전송 경로를 동시에 늘려 하나의 센서로도 여러 개의 센서를 설치한 것과 같은 효과를 얻는 것으로 풀이된다. 이는 수학적으로 비잔틴 결함이 일어나지 않는다는 것을 보장하기 보다는 현실적으로 문제 발생 확률을 줄이는 접근으로 보인다. 사토시 나카모토는 이와는 다른 접근을 취했다. 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다.

비트코인은 POW 라는 합의구조를 도입했다. 아담 백과 할 피니가 들고 나왔던 바로 그 개념이다. POW는 어떤 목표를 이루기 위해 일정한 연산을 투입하도록 하는 방식이다.(비트코인개론 1편 참조)

우선 비트코인의 구조부터 살펴보면, 비트코인은 참여자들이 만든 송금 거래를 수십개씩 모아 최신의 원장을 만들어 이어나가는 구조다. 가계부로 비유하면 가계부 한 페이지가 블록체인에서는 블록이 된다.

비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 룰을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이같은 여러 숫자들을 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했다. 퍼즐을 푸는 과정이 곧 POW다. 연산력을 투입하기 때문이다. 수학 퍼즐이 풀리면 블록이 만들어지며 이를 채굴이라고 한다.

POW를 수행해 퍼즐이 풀렸다면 결국 이 블록은 부정이 없도록 설계한 각종 룰을 지킨 정상 거래들을 모아 정상적인 방법으로 만든 원장이라는 의미다. 마지막에 나온 블록의 고유 값이 정상이면 계산 과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 된다는 점이 증명된다. 비트코인은 결국 POW를 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. POW를 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행의 역할은 비트코인 시스템 내에서 이렇게 사라졌다. 수많은 P2P 전자화폐 개발자들을 괴롭혔던 비잔틴 장군의 문제는 비트코인의 탄생으로 해결점을 찾게 됐다.

예를 들어 만약 특정 참여자가 두 개의 모순되는 거래를 만들어 배포 경우에는 어떻게 될까. 비트코인에서는 원하는 누구나 POW를 수행해 블록을 만들 수 있기 때문에 모순되는 거래가 각각 블록에 담기면 이는 문제가 된다. 장군들이 각각 다른 공격 시간을 건네받은 셈이다. 이에 비트코인 시스템은 참여자들이 POW를 수행하기 전에 전파 받은 거래에 모순이 있는지 한 차례 검증을 거치도록 하고 있다. 이와 별개로 모순 거래를 처리하는 비트코인의 원칙은 POW를 먼저 거친 거래를 받아들인다. 즉 두 모순된 거래를 장군들이 받았을 때 누구든 POW를 수행해 이 중 하나를 먼저 블록 안에 넣는데 성공한다면, 해당 블록안에 들어간 거래가 인정받는다. 이 거래를 담은 블록이 전체 네트워크에 전파되면 다른 참여자들은 해당 블록을 검증한 후 받아들이게 된다. 그러면 참여자들은 해당 블록안의 거래와 모순된 거래는 파기한다.

사토시는 그가 보낸 메일에서 이를 이렇게 설명한다. “그(장군)들은 공격시간이 언제인지는 특별히 신경쓰지 않습니다. 모두가 동의한다는 점이 중요하지요. 누구나 시간을 알릴 수 있고, 먼저 들은 시간이 공식 공격시간이 되는 겁니다.”

마스터링 비트코인의 저자 안드레아스 안토노풀로노스는 그의 책에서 비잔틴 장군의 문제를 해결한 비트코인의 공적을 이렇게 기술했다. “(작업증명 개념을 이용한) 이 해법은 분산 컴퓨팅 과학에서 획기적인 업적을 이룬 것이며 통화 뿐만이 아니라 다른 분야에도 적용 가능하다. 선거나 복권, 자산 등록, 디지털 공증 등 공정성을 입증해야 하는 분야에서 분산 네트워크에 대한 동의를 구하는데 사용 될 수 있다.”

/김흥록기자 rok@

△덧붙임

1. 사실 비잔틴 장군 문제는 역사적으로 존재한 실사례는 아니다. 1982년 논문을 발표한 저자들이 비잔틴 제국이라는 이름을 붙였을 뿐이다. 애초 알바니아 장군의 문제로 붙이려 했으나 저자들이 알바니아 측에 대한 배려로 누구도 기분 나쁘지 않은 이름을 따와 비잔틴 제국의 문제가 된 것 뿐이므로 블록체인을 이해하기 위해 비잔틴의 역사적 상황을 살펴볼 일은 아니다.

2. 제임스 아담스와 사토시 나카모토가 당시 주고 받은 편지 중 사토시가 메일을 보낸지 불과 47초 만에 도날드가 장문의 답장을 한 것으로 적혀있는 기록이 있다. 이에 몇몇 암호화폐 관련 해외 인터넷 커뮤니티에서는 사토시 본인이 제임스 도날드이며 편지를 주고 받는 것이 자작극이 아니냐는 의심을 받기도 했다. 물론 진실은 알 수 없다. 사토시가 주고 받았던 메일은 다음 링크에서 확인할 수 있다. (클릭)


<저작권자 ⓒ 디센터, 무단 전재 및 재배포 금지> XC
이 기사를 공유하세요.

이메일 보내기

보내는 사람

수신 메일 주소

※ 여러명에게 보낼 경우 ‘,’로 구분하세요

메일 제목

전송 취소

메일이 정상적으로 발송되었습니다
이용해 주셔서 감사합니다.

닫기