분산합의
블록체인에서 사용되는 다양한 합의컨센서스 알고리즘들을 소개하기 전에, 먼저 분산 합의distributed consensus 에 대해서 알아보겠습니다. 분산 합의는 신뢰할 수 없는 통신 네트워크에 의해서 연결된 프로세스들의 그룹 간의 합의에 도달하는 것을 다룹니다. 따라서 다수의 노드들이 참여해 있는 p2p 네트워크에서 합의가 필요한 상황에서 분산 합의가 필요합니다.
분산 합의의 기술적인 정의는 간단 합니다. 하나의 고정된 개수의 노드 또는 프로세스들이 있다고 생각해봅시다. 그리고 각각의 노드들은 어떤 입력 값을 갖습니다. 노드들이 모두 올바른 노드들이 면 괜찮겠지만, 실제로는 그렇지가 않을 수 있습니다. 노드들 중에서 일부는 잘못되었거나 의도적으로 악의적일 수 있기 때문입니다.
그래서 분산 합의 프로토콜이 발생 했을 때 두 가지 요구조건이 있습니다. 첫째 합의 프로토콜이 모든 올바른 노드들은 어떤 같은 값으로 결정을 하면서 끝나야 한다는 것 입니다. 둘째 이 합의한 값은 임의의 값이 될 수 없고, 적어도 하나의 올바른 노드에 의해서 입력한 값으로서 제안된 값이어야 한다는 것입니다. 이 두가지를 만족시킬 수만 있다면 분산 합의가 만들어질 수 있습니다.
분산 환경에서 합의(컨센서스)는 어려운 문제인데, 어떤 것들이 실제로 문제가 되는지 알아보겠습니다. 우선 참여한 노드들 중에서 노드 가 고장 나거나 잘못 동작할 수 있고, 노드가 의도적으로 악의적일 수 있습니다. 그래서 어떠한 노드들은 시스템 이나 프로세스를 전복시키기 위해서 고의적으로 나쁜 행위를 시도할 수도 있습니다.
또한 네트워크가 p2p 시스템이기 때문에 굉장히 불완전 합니다. 모든 노드 쌍이 서로 연결되어 있는 것은 아니고, 인터넷 연결 상태가 좋지 않아서 네트워크에 결함이 있을 수 있습니다. 그 다음으로, 모든 작업들은 인터넷을 통해서 어떤 것은 빨리 처리되고, 어떤 것은 늦게 처리되는 되기 때문에, 시스템에서 많은 대기시간이 있을 수 있습니다.
결국 이 높은 대기 시간의 한 결과 로서, 모든 컴퓨팅 노드들이 정확한 시간에 대한 타임 스탬프를 가지고 있지 않기 때문에 세계(글로벌) 타임의 개념이 없습니다.
두 장군 문제
앞에서 분산 환경에서의 합의가 어려운 점과 관련하여 컴퓨팅 영역에서 신뢰할 수 없는 링크를 통해 의사소통함으로써 행동을 조정하려는 설계 과제와 함정을 설명하기 위한 사고 실험인 "두 장군 문제 (Two Generals Problem)"가 있습니다. 이것은 통신 장애가 발생할 수 있는 모든 종류의 양자 간 통신에 적용될 수 있습니다.
이 문제의 상황을 설명하자면 오른쪽 그림과 같은 상황에서 두 군대(A1, A2)는 요새화된 도시(B)를 공격하길 원합니다. 그리고 두 장군이 통신 할 수 있는 유일한 방법은 계곡을 통해 연락병을 보내는 것입니다. 하지만 계곡에는 적군이 있어 연락 병이 포획되어 메시지 전달이 안정적이지 않을 수 있습니다.
두 장군은 사전에 공격하기로는 합의했으나 언제 공격할지 시각은 합의되지 않은 상황입니다. 두 장군은 공격을 성공시키기 위해서 도시를 동시에 공격해야만 합니다. 그렇지 않으면 단독으로 공격을 시도한 군대가 패배할 것입니다. 그래서 한 장군이 공격 시간을 정 하고 통신연락병을 통해서 합의하고 상대의 확답을 받아야 합니다. 결과적으로 이 사고 실험은 두 장군 이 어떻게 합의에 도달할 지를 고려하는 문제입니다.
이 문제의 해답은 아래의 3가지 특성을 가져야 하는데, consistency, validity, termination, 결론적으로 말씀드리면 불가능합니다. 왜냐하면 아래의 그림에서 볼 수 있는데 메시지뿐만 아니라 메시지 수신 확인도 원래 메시지처럼 손실될 수 있어서 무한한 메시지가 합의에 도달해야 하기 때문입니다.
비잔틴 장군 문제
비잔틴 장군 문제 (byzantine generals problem)는 앞에서 설명한 장군 문제를 일반화시킨 문제입니다.
해당 문제는 레슬리 램퍼트가 1982년에 작성한 논문에서 처음 언급되었고, 아래의 그림처럼 적군의 도시를 공격하려는 비잔티움 제국군의 여러 부대가 지리적으로 떨어져 있는 상태에서 각 부대의 장군들이 중간에 잡힐지도 모르는 전령을 통해 교신하면서 공격 계획을 함께 세우는 상황을 가정하고 있습니다.
문제를 정의하기 위한 상황을 설명하자면 비잔틴 제국의 여러 장군 들이 하나의 적군 도시를 공격하기 위해 출병한 상태입니다. 이때 적이 매우 강해서 과반수 이상의 장군들이 같은 시각에 공격해야만 승리하고 그렇지 않으면 패배하게 됩니다. 여기서 모든 장군들 간의 통신은 연락병을 보내는 방법밖에 없지만 연락병은 중간에 잡혀서 서신이 도착하지 않을 수도 있습니다.
또한 장군들 중에는 배신자가 있을 수 있어서 서로 신뢰할 수 없습니다. 그리고 배신자는 가짜 공격 명령을 보낼 수도 있고 서신을 받았을 때 자기 멋대로 행동할 수 있습니다. 이렇게 서로 신뢰할 수 없는 상황에서 장군들은 공격 시각을 어떻게 합의할까요?
결국 상호 간에 통신을 통해 어떤 합의를 해야 하는 경우 통신에 문제가 발생하거나 고의로 정보를 변경해 가짜 정보를 전달할 가능성이 있을 때 전체가 올바른 합의를 형성할 수 있는지를 묻는문제입니다. 앞에서 분산 시스템에서의 합의와 관련된 내용들을 설명했습니다. 왜 블록체인에서 합의 알고리즘이 필요한 것일까요?
블록체인은 수많은 노드가 P2P 네트워크로 연결되어 트랜잭션들을 처리하고 기록하는 분산 원장 시스템입니다. 해당 시스템 내의 모든 노드들은 동일한 트랜잭션 내용을 공유해야 합니다. 따라서 블록체인은 그 안에 있는 모든 노드가 동일한 하나의 체인을 바라볼 수 있도록 블록을 생성하고 연결하는 매커니즘이 필요한 것입니다.
트랜잭션들이 담긴 블록을 체인처럼 연결하고 모두에게 공유한다는 데이터베이스 구성에 대한 새로운 접근방식에 이 블록들을 어떻게 만들고, 체인에 어떻게 연결할 것인지 결정하는 합의 알고리즘이 더해져서 블록체인이란 기술이 완성되는 것입니다. 블록체인 기술을 기반으로 한 시스템은 중앙 서버에서 블록과 트랜잭션의 유효성을 판단해주지 않습니다.
때문에 전달된 정보가 문제가 없다는 것을 참여자들이 스스로 검증하고 그 유효성을 판단해야 합니다. 이뿐만 아니라 완전히 탈중앙화된 p2p 네트워크에서는 네트워크 지연 중복 수신 의도적인 변조 등의이유로 정보 전달 과정에 문제가 발생할 수 있습니다. 따라서 다음과 같은 문제들을 합의 수단을 통해서 해결해야 합니다.
첫째 특정 노드가 임의로 블록체인 을 조작하지 못하도록 해야 합니다. 둘째 블록과 트랜잭션 등의 유효성 여부를 검증할 수 있는 방법이 필요합니다. 셋째 블록을 체인에 연결할 때 동시에 두 개 이상의 유효한 블록체인이 존재한다면 이 중에 하나를 선택할 수 있는 규칙이 있어야 합니다.
비트코인이 발명되었을 때의 큰 발전은 이 이메일에서 Satoshi Nakamoto가 깊이 설명한 비잔틴 장군 문제에 대한 확률론적 해결책으로서 작업증명 (proof-of-work)을 사용한 것이었습니다. 아래 url 주소에 들어가면 이메일 전문을 확인할 수 있습니다. 지금까지 비트코인 체제가 유지 되는 것에서 우리는 분산 합의 문제에 대한 몇 가지 힌트를 얻을 수 있습니다.
우선 비트코인이 비잔틴 장군 문제 같은 분산 합의 문제를 완벽히 해결하지는 않습니다. 하지만, 화폐 시스템의 맥락에서는 문제를 해결하고 있습니다. 비트코인은 참가자들이 정직하게 행동하도록 화폐를 주는 인센티브를 도입했고 이것은 분산 합의를 해결하기 위한 힌트가 될 수 있습니다.
그다음 비트코인에서는 언제 합의 가 시작되고 끝나는지에 대한 특정한 시간에 대한 개념을 없앴습니다. 합의는 긴 시간에 걸쳐서 이루어지고, 이로써 임의의 개념을 포용했습니다. 마지막으로 확률적인 개런티를 통해서 시간이 지나면 지날수록 합의에 대한 확률은 더 커지고 단단해지며 합의가 실패할 확률은 기하급수적으로 줄어듭니다. 이렇게 확률적 보장은 분산 합의 를 위한 또 하나의 힌트가 될 수 있습니다.
PoW: Proof of Work
작업증명 (Proof of Work, PoW)은 복잡한 계산 문제의 해답을 가장 빨리 찾은 마이너의 블록을 블록체인에 연결하고 이러한 작업에 대해서 보상해주는 방식입니다. 이 방법에서는 블록헤더의 해시 값을 계산하는데 블록헤더에 있는 Nonce 값을 계속 변경하여 목표값보다 작거나 같은 값이 나올 때까지 계속 해시값을 반복적으로 계산합니다.
계산 문제를 빨리 풀기 위해서는 많은 양의 컴퓨터 연산 파워가 필요한 데, 블록을 생성하기 위해서 어려운 계산 문제를 수행하게 함으로써 악의적으로 블록을 위변조하여 블록체인을 조작하는 것을 막을 수 있습니다. 비트코인의 분산화된 합의는 네트워크 상의 노드들 사이에서 독립적으로 일어나는 아래의 프로세스에 따라 이루어집니다.
첫 번째 모든 풀 노드가 각 거래에 대해 독립적으로 검증을 실시합니다. 두 번째, 작업 증명 알고리즘을 이용하여 마이너들은 검증된 거래들을 새로운 블록에 추가합니다. 세 번째, 모든 노드들이 새 블록을 검증한 후 블록체인에 연결합니다. 네 번째, 모든 노드가 작업증명을 통해 연결한 체인들 중 가장 긴 체인을 선택합니다. 이 네 가지 프로세스 들에 대해 살펴본 후 네트워크 전체의 합의를 얻어내기 위해 네 가지 프로세스가 어떻게 상호작용하는지 알아보겠습니다.
PoS: Proof of Stake
합의 과정에서 불필요한 해싱 연산 을 통한 에너지 소비가 존재하기 때문에 장기적으로 PoW를 유지하기는 어렵습니다. 그래서 PoW의 문제점들을 극복하기 위해서 다른 합의 알고리즘인 Proof of Stake (PoS)가 언급되고 있습니다.
PoW의 문제점은 첫째로 컴퓨팅 파워 를 의미 없는 해시값을 찾아내는데 사용해야 해서 무의미한 에너지 소비를 증가시키는 자원 낭비 문제가 있습니다. 둘째로 빨라지는 블록생성 주기 를 PoW의 Difficulty로 유지하는데 한계 가 있기 때문에, 컴퓨팅 파워가 큰 마이너의 영향력이 커진다는 문제가 있습니다.
이 방식에서는 마이너(Miner)는 없고 검증자(Validator)가 존재합니다. 검증자(Validator)가 자신이 가진 지분 (Stake)에 비례한 확률로 블록을 생성할 권한을 얻게 되고, 블록을 생성한 후에는 자신이 원하는 체인에 블록을 연결하고 그에 대한 보상을 받는 방식을 의미합니다.
pos의 장점으로 더 이상 블록생성 을 위해서 마이닝이 필요 없기 때문에 에너지 비용이 절감한다는 점 그리고 지분에 비례하여 블록생성의 권한을 얻기 때문에 중앙화 위험이 감소한다는 점이 있습니다. 또한 Finality를 부여해 이미 체인 에 연결된 블록들이 변경되기 힘들게 만듭니다.
마지막으로 공격자의 악의적인 행동이 발각되면 모든 자산을 0으로 만드는 패널티를 부여해 공격이일어나지 못하도록 합니다. 이러한 장점들은 PoW의 단점을 보완 합니다.
DPOS: Delegated Proof Of Stake
DPOS(delegated proof of stake)의 경우 블록을 생성하는데 자신이 가진 지분을 이용하여 투표한다는 데에서는 PoS와 원리는 같습니다. 이 둘의 차이는 직접 민주주의와 간접 민주주의의 차이입니다. 둘 다 투표를 통해 후보자들 중 대표를 선출하지만, 직접 민주주의는 유권자들 각각이 자신의 권리를 직접 행사하고 간접 민주주의는 유권자가 뽑은 대표들이 투표를 진행하여 대표를 선출하는 방식입니다.
PoS는 직접 민주주의와 비슷하기 때문에 많은 사람들이 투표하려면 블록을 형성하는데 시간이 오래 걸립니다. 이를 해결하기 위해 간접 민주주의와 비슷한 DPOS가 등장하였습니다. 지분을 가지고 있는 사람들이 뽑은 소수의 대표들만 투표를 진행하기 때문에 블록이 빠르게 형성됩니다.
즉, DPOS는 네트워크 상의 검증자 수를 제한하여 높은 수준의 확장성을 제공하는 PoS의 변형입니다. 이러한 DPOS 방식을 채택하는 블록 체인에는 EOS, Bitshares, Steemit, Lisk , Ark 등이 있습니다.
PoA: Proof of Authority
권위증명 (Proof of Authority, PoA)는 stake로서 신분에 기반한 합의 메커니즘 을 통해서 상대적으로 빠른 트랜잭션들을 전달하는 블록체인과 함께 사용되는 알고리즘입니다. 조금 더 구체적으로는 PoA가 금전적 가치를 거는 것 대신에 한 검증자의 신원이 Stake의 역할을 수행하는 PoS의 변경된 형태입니다.
PoA기반의 네트워크에서는 검증 자로서 알려진 승인된 계정들에 의해서 트랜잭션과 블록들이 검증됩니다. 이 검증자들은 그들이 트랜잭션을 블록 단위로 넣을 수 있는 소프트웨어를 구동합니다. 이 과정은 자동화 되어있고, 검증 자가 컴퓨터를 계속 모니터링 할 필요가 없습니다. 하지만 authority node(컴퓨터)를 유지보수해야 합니다.
다른 consensus와의 차이점으로는, PoA로 개인은 검증자가 될 수 있는 권리를 얻을 수 있다는 것입니다. 따라서 그들이 얻은 지위를 유지할 인센티브가 있습니다. 명성을 신원 정보에 첨부함으로써, 검증자는 자신의 신원을 부정적인 평판에 붙이기를 원하지 않으므 트랜잭션 프로세스를 유지하기 위해 보상을 받게 됩니다.
이것은 PoS보다 더 강력하다고 간주 되는데, PoS에서는 두 당사자들 사이에서 지분이 동일할 때 각 당사자의 총 지분은 고려하지 않기 때문에 인센티브 가 균형을 잃을 수 있기 때문입니다. 추가적으로 PoA는 특정 검증인으로부터비 연속적인 블록 승인만을 허용하기 때문에 심각한 손상 위험이 권한 노드에 집중됩니다. 마지막으로 poa는 신뢰가 분산되는 poa 네트워크와 같은 개인 네트워크와 공용 네트워크 모두에 적합합니다.
참조
http://www.kmooc.kr/courses/course-v1:POSTECHk+CSED490U1+2021_T1/about
블록체인 입문
블록체인과 암호화폐 기술을 깊이 배우기에 앞서, 비 전공자들도 이해를 할 수 있는 수준으로 블록체인과 암화화폐에 대한 high-level 설명 및 응용 예시를 제공하고 실제 상황에 적용할 수 있다.
www.kmooc.kr