안녕하세요. SKKRYPTO 7기 오성민입니다. 이 글을 통해 '비잔틴 장군 문제'와 이를 해결하기 위한 '합의 알고리즘'에 대해 알아보고, 이 알고리즘이 블록체인에 어떻게 적용되는지 살펴보겠습니다.
Introduction
2008년 비트코인을 시작으로 많은 암호화폐들이 만들어졌습니다. 각 암호화폐들이 저마다 다른 메커니즘을 가지고 있지만, 거의 모든 암호화폐가 가진 공통점은 그 핵심 요소로 블록체인을 가진다는 것입니다.
일부 예외가 있지만, 블록체인은 기본적으로 일종의 '분산화된 디지털 장부'로써 기능하도록 설계되었습니다. 이 장부는 네트워크의 분산된 노드*들에 의해서 유지됩니다. 블록체인의 이러한 특징 덕분에 금융 거래가 중개자 없이 안전하게 이루어질 수 있는, 즉 '신용이 필요 없는' 경제 시스템을 구축할 수 있습니다. 이러한 이유로 암호화폐는 '신뢰'에 강하게 의존했던 기존의 전통적 금융 시스템을 대체할 수단으로 주목받고 있습니다.
Q. 노드가 무엇인가요?
A. 컴퓨터, 네트워크 분야에서 노드는 메세지를 생성하고, 수신하고, 전달할 수 있는 기본 단위입니다. 일반적으로 스마트폰, 컴퓨터와 같은 물리적 통신 기기 각각을 노드라고 하지만, 물리적 실체가 없는 가상의 노드가 존재하기도 합니다.
대부분의 분산화 컴퓨팅 시스템이 그러하듯이, 암호화폐의 참여자들은 정기적으로 현재 블록체인의 상태에 대한 합의를 가져야 합니다. 그러나 분산화된 네트워크에서 안전하고 효율적으로 합의에 이르는 것은 매우 어려운 일입니다.
분산화된 네트워크에서 일부 노드가 악의적으로 행동하더라도 전체가 합의에 도달할 수 있을까요? 이것이 바로 BFT라는 개념을 처음 등장시킨 '비잔틴 장군 문제'의 근본적인 질문입니다.
비잔틴 장군 문제
비잔틴 장군 문제는 1982년에 처음 제안된 것으로, 비잔틴의 장군들이 다음 작전에 대한 합의를 도출하는 과정에서 의사소통의 문제가 발생할 수 있음을 보여주는 논리적 딜레마입니다.
이 문제에서는 각 장군이 자신의 군대를 가지고 있으며, 공격하고자 하는 도시 주변의 서로 다른 곳에 위치해있다고 가정합니다. 장군들은 공격과 후퇴 중 하나를 선택해야 하는데 모든 장군들이 같은 결정을 내리기만 한다면 공격을 하든 후퇴를 하든 작전은 성공적으로 진행됩니다.
이 상황을 정리해보면 아래와 같습니다.
- 각 장군은 공격과 후퇴 중 하나를 선택해야 한다.
- 결정을 내린 후에는 변경할 수 없다.
- 모든 장군들은 같은 결정을 하기로 합의해야 한다.
위에서 언급된 의사소통의 문제는 각 장군이 다른 장군과 소통하기 위해서는 전령을 보내서 편지로 소통하는 방법밖에 없다는 사실에서 비롯됩니다. 즉, 비잔틴 장군 문제의 핵심은 편지가 중간에 사라지거나, 전달이 지연될 수 있다는 점입니다.
한가지 더 고려해야 할 점은 장군들 중에 배신자가 있을 수 있다는 점입니다. 배신자 장군은 악의적으로 행동하여 다른 장군들을 교란시키고 결국 작전의 실패를 유도할 것이기 때문에, 편지가 제대로 전달되었다고 하더라도 안심할 수 없다는 것입니다.
이 딜레마를 블록체인에 그대로 적용해보면 각 장군은 노드를 의미합니다. 모든 장군이 다음 작전에 대해 합의해야 한다는 상황은 블록체인의 모든 노드들이 시스템의 현재 상황에 대한 합의를 이루어야 한다는 상황과 대응됩니다. 즉, 우리의 블록체인 작전 (블록체인에 대한 하나의 단일한 상태에 대한 합의가 이루어져야 한다는 작전)이 실패하지 않기 위해서 각 노드들이 합의해서 같은 행동을 실행해야 한다는 것입니다.
BFT (Byzantine Fault Tolerance)
BFT란, 비잔틴 장군 문제에서 비롯되는 결함에 대해 저항할 수 있는 시스템의 특성을 의미합니다. 즉, BFT 시스템은 일부 노드들이 악의적으로 행동하더라도 정상적으로 작동될 수 있습니다.
비잔틴 장군 문제를 풀고 BFT에 도달할 수 있는 방법은 여러가지가 있습니다. 그리고 블록체인 시스템에서 BFT를 이룰 수 있게 하는 알고리즘을 우리는 소위 '합의 알고리즘'이라고 부릅니다.
합의 알고리즘
합의 알고리즘은 분산화된 환경에서 시스템이 완만하게 작동하도록 하는 메커니즘입니다. 합의 알고리즘은 일부 사용자가 악의적으로 행동하더라도 시스템 내의 모든 사용자들이 하나의 상태에 동의하도록 보장해야 합니다. (위에서 살펴본 BFT를 말하는 것입니다.)
사실 중앙화된 환경에서는 한 주체가 시스템 전체를 제어할 수 있는 권력을 가지고 있습니다. 그리고 대부분의 경우 그 한 주체 자신이 원하는대로 시스템을 운영합니다. 이러한 환경에는 많은 사용자들이 합의에 이르기 위한 복잡하고 민주적인 절차가 존재하지 않습니다.
그러나 분산화된 환경에서는 '합의 알고리즘'에 의해서 민주적으로 사용자들 간에 합의에 이를 수 있게 됩니다. 이 합의 알고리즘이 블록체인에 어떻게 활용되는지 알아보겠습니다.
암호화폐는 사용자(노드)들의 잔액이 블록체인이라고 하는 데이터베이스에 기록됩니다. 따라서 모든 노드들이 동일한 데이터베이스의 사본을 가지고 있어야 합니다. 만약 그렇지 않다면, 여러 정보들 사이의 충돌이 발생하고 암호화폐의 존재 자체가 무의미해질 것입니다.
Public Key Cryptography (비대칭 암호화)라는 방식으로 나의 코인을 다른 사람이 사용하는 것을 막을 수는 있지만, 하나의 단일한 데이터베이스에 모두가 합의하는 방법을 찾지 않는 이상 위에서 언급한 문제는 해결할 수 없습니다.
Q. Public Key Cryptography가 무엇인가요?
A. Public Key Cryptography (PKC)는 비대칭 암호화라고도 불리는 암호화 방식입니다. PKC에서는 한 쌍의 개인 키와 공개 키를 사용합니다. 이러한 특징 덕분에 PKC가 암호화폐 기술에 근본적으로 내재하는 여러 문제점들을 해결할 수 있습니다.
PKC 방식에서 공개 키는 정보를 암호화 하는 데 사용되고, 개인 키는 정보를 복호화 하는 데 사용됩니다. 쌍을 이루는 공개 키와 개인 키는 별개의 독립된 개체이기 때문에 개인 키가 유출될 걱정 없이 안전하게 공개 키를 상대에게 전달할 수 있습니다.
공개 키로 암호화 된 정보는 그에 대응하는 하나의 개인 키로만 복호화될 수 있습니다. 따라서 상대에게 나의 정보를 안전하게 전달하고 싶다면 상대방의 공개 키를 이용해 나의 정보를 암호화해서 상대에게 전달하면 됩니다.
Proof of Work (PoW)
비트코인의 창시자 사토시 나카모토는 위 문제를 해결하기 위해 Proof of Work (PoW)라는 개념을 블록체인에 적용하였습니다. PoW는 위에서 언급한 합의에 대한 문제뿐만 아니라, 이중 지불(Double Spending) 문제도 해결할 수 있습니다.
Q. 이중 지불 문제가 무엇인가요?
A. 이중 지불 문제란 디지털 결제 시스템에서 발생할 수 있는 문제입니다. 디지털 파일은 제한 없이 복사가 가능하기 때문에, 가치가 담긴 파일을 복사해서 동시에 2개 이상의 결제를 진행하면, 판매하는 입장에서는 자신이 제공받은 가치가 사본인지 아닌지 알 수 없기 때문에 발생하는 문제입니다. 이 문제를 해결하지 못하는 프로토콜은 근본적으로 보안에 취약하다고 할 수 있습니다. 즉, 디지털 화폐는 단순한 '데이터'이기 때문에, 사람들이 이를 복사해서 여러 곳에서 사용하는 것을 막지 못한다면 그 시스템은 붕괴할 것입니다.
블록체인은 누구나 볼 수 있는 커다란 데이터베이스입니다. 따라서 누구나 이중 지불이 일어나는 것은 아닌지 확인할 수 있습니다. 다음과 같은 상황을 생각해보세요. 당신과 3명의 친구들이 하나의 칠판을 가지고 있습니다. 누구든 자신이 가진 것을 전송하고 싶으면, 칠판에 적으면 됩니다. ("범수가 모언이에게 5원을 줬다.", "모언이가 정근이에게 2원을 줬다" 처럼요.)
그리고 추가로, 거래가 일어날 때마다 그 돈이 어디에서 온 것인지 작성하면 됩니다. 예를 들어서 모언이가 정근이에게 2원을 준다면 아래와 같이 작성하면 되겠습니다. "모언이가 정근이에게 2원을 줬다, 이전에 범수에게 받은 돈을 가지고."
이러한 방법으로, 우리는 돈의 흐름을 모두 추적할 수 있습니다. 만약 모언이가 정근이에게 준 2원을 가지고 다른 거래를 하고자 한다면, 모두가 그 사실을 알 수 있을 것입니다. 따라서 아무도 그 거래가 칠판에 적히는 것을 용납하지 않을 것입니다.
이러한 방식이 위의 예시에서와 같이 작은 규모의 네트워크에서는 효과적일 수 있습니다. 네트워크 구성원들이 서로를 잘 알고, 허위로 칠판에 기록을 남기지 않을 것이라고 믿을 수 있기 때문입니다. 그런데 만약 10,000명 규모의 네트워크에서는 어떨까요? 누구도 남을 믿고 칠판을 맡길 수 없을 것입니다.
이러한 이유로 PoW라는 개념이 등장합니다. 이 개념 덕분에 악의적인 사람이 본인이 사용할 권리가 없는 돈을 사용할 수 없게 되었습니다. 게임이론과 암호화의 조합을 통해 PoW 알고리즘이 누구나 블록체인을 규칙에 따라 업데이트 할 수 있도록 만들었습니다.
그렇다면 PoW는 어떻게 작동하는 것일까요? 우리가 위에서 예시로 든 칠판이 바로 '블록체인'입니다. 그러나 블록체인에서는 위의 예시처럼 거래 내역을 하나씩 기록하는 것이 아니라 블럭으로 묶어서 저장하게 됩니다. 우리가 거래 내역을 네트워크에 전달하면, 사용자들이 그 거래내역을 포함한 후보 블록을 생성합니다. 거래 내역들은 자신이 포함된 후보 블록이 확정되어서 블록체인에 추가되었을 때 비로소 유효한 것으로 인정됩니다.
그러나, 사용자 입장에서 블록을 추가하는 일은 비용이 듭니다. 따라서 사용자들이 블록을 추가하기 위해 자신의 자원을 사용하도록 유도할 수 있는 혜택을 줘야합니다. 여기서 자원이란 블록체인에 블록을 추가하기 위해 블록의 데이터를 해시하는데 사용되는 컴퓨팅 파워를 말합니다.
Q. 데이터를 해시하는 게 무엇인가요?
A. 이 질문에 대한 답을 하기 위해서는 일단 해시 함수에 대해서 알아야 합니다. 해시 함수에 임의 길이의 데이터를 입력하면, 고정된 길이의 데이터가 반환됩니다. 그리고 입력한 데이터에서 아주 조금만 값이 변해도 반환되는 해시 값은 완전히 달라지게 됩니다. 그리고 해시 함수의 중요한 특징 중 하나는 입력 값을 넣으면 해시 값을 쉽게 얻을 수 있지만, 해시 값을 가지고 원래 데이터가 무엇이었는지 알아내는 것이 거의 불가능하다는 것입니다. 이러한 해시 함수에 데이터를 넣어서 해시 값을 반환받는 과정을 '해시 한다' 라고 표현할 수 있습니다.
PoW에서, 블록을 추가하기 위해서는 해시 값이 특정 조건을 만족하는 데이터(블록)를 제출해야 합니다. 하지만 어떤 데이터가 그 조건을 만족시키는지는 알 수 없습니다. 따라서 조건을 만족하는 해시 값이 나올 때까지 데이터를 조금씩 바꿔가면서 해시하기를 반복하는 방법밖에 없습니다.
다시 말해서, 만약 당신이 블록을 생성하길 원한다면, 일종의 찍기 게임을 하는 것입니다. 당신은 거래 내역들에 대한 정보를 모두 모아서 해시할 것입니다. 그러나 거래 내역들은 변경되지 않기 때문에 항상 같은 해시 값을 얻을 것입니다. 이를 피하기 위해 당신은 계속해서 변화시킬 수 있는 작은 정보를 블록에 추가해야 하는데 이를 '논스'라고 합니다. 당신은 해시를 할 때마다 논스를 조금씩 변경시키며 조건을 만족하는 해시 값을 찾으려고 할 것이고, 이를 '채굴'이라고 말합니다.
만약 당신이 조건에 부합하는 해시 값을 찾았다면, 새로운 블록을 네트워크에 발표할 수 있는 권한을 갖습니다. 그러면 네트워크의 다른 참여자들은 당신이 발표한 새로운 블록을 검증하고 자신들의 블록체인에 업데이트 합니다. 이로서 모든 노드가 현재 블록체인의 상태에 대한 합의에 이를 수 있게 되었습니다.
오늘날, 컴퓨터의 연산 능력이 향상되면서 암호화폐들의 해시 값 조건이 점점 더 어려워지고 있습니다. 이는 새로운 블록이 너무 빠르게 발견되지 않게 하기 위한 장치입니다.
그렇다면 PoW 방식은 악의적으로 행동하는 노드에 어떻게 대응할까요? 위에서 알아본 PKC를 이용한 디지털 서명을 활용해 BFT에 이를 수 있습니다.
디지털 서명이란 당신의 거래 내역을 개인 키로 암호화하는 것을 말합니다. 당신의 개인 키로 암호화된 데이터는 당신의 공개 키로만 복호화 될 수 있으므로, 네트워크의 모두가 해당 거래내역이 당신의 공개 키로 복호화되는지 확인할 수 있습니다.
이러한 원리를 이용해 부적절한 거래 내역을 포함하고 있는 블록은 네트워크에 의해서 거절당하게 됩니다. 따라서 허위로 거래 내역을 작성하고 이를 블록으로 등록하기 위해서는 많은 컴퓨팅 파워를 소모하게 되고, 보상도 받을 수 없으므로 이를 시도할 유인이 사라지게 되는 것입니다.
이로서 PoW가 어떻게 노드들 간의 합의를 이룰 수 있도록 하는지, 또 악의적인 노드에는 어떻게 대응하는지 알아보았습니다. 다음 시간에는 PoS 등 다른 합의 알고리즘의 작동 원리에 대해 알아보도록 하겠습니다.
