[케블리] #44. 합의 알고리즘 마스터하기 - 1편 (PoW, PoS)

kblock (58)in #kr • 7 years ago (edited)

[그림 1. Consensus Algorithm]

합의란 ‘서로 의견이 일치하거나 혹은 그 의견’이라는 사전적 의미를 가지고 있습니다. 즉, 합의를 한다는 것은 특정 문제 혹은 사건과 관련하여 이해 관계를 맺고 있는 사람들 간의 의견을 일치해 가는 것을 말합니다. 블록체인을 공부하다 보면 우리는 심심치 않게 ‘합의 알고리즘’이라는 개념을 자주 접하게 됩니다. 그 만큼 합의의 개념은 블록체인의 원리를 이해하는데 있어서 가장 기초적이면서 동시에 가장 중요한 역할을 담당하고 있습니다.

이에 총 3편에 걸쳐서 합의 알고리즘에 대해 전반적으로 소개 및 이해하는 시간을 가지려고 합니다. 오늘 1편에서는 ‘왜 블록체인에 합의 알고리즘이 필요한지’, 그리고 가장 많이 알려져 있는 ‘작업증명(Proof-of-Work)과 지분증명(Proof-of-Stake)은 각각 어떠한 알고리즘을 구현하고 있는지’에 대해서 알아보도록 하겠습니다.

그 다음 편에서는 가장 주목 받고 있는 DPoS(Delegated Proof-of-Work) 에 대해서 심층 분석하는 시간을 가질 것이며, 마지막 3편에서는 그 외에 최근에 떠오르고 있는 다양한 합의 알고리즘들을 살펴 볼 예정입니다. 지금 이 순간에도 어떤 합의 알고리즘이 가장 좋고 효과적인지에 대해서는 아직 많은 논란이 있지만, 이번 시리즈를 통해서 합의 알고리즘에 대한 개념을 이해하고, 나아가 여러분들만의 합의 알고리즘에 대한 철학을 갖는 계기가 되었으면 좋겠습니다.

Why Consensus Algorithm?

‘합의 알고리즘’은 컴퓨터 과학에서 사용하고 있는 일종의 프로세스를 일컫는 것으로 보통 시스템이 분산화 되어 있을 때 시스템 간의 특정 데이터에 대한 동일한 값을 유지하기 위해 고안된 개념입니다. 그렇다면 블록체인에서 왜 합의 알고리즘이 필요할까요? 이는 블록체인 개념 자체와 그 이유를 같이 하고 있습니다. 블록체인은 수 많은 노드가 P2P 네트워크로 연결되어 트랜잭션을 처리하고 기록하는 ‘분산 원장 시스템’을 의미합니다. 해당 시스템 내의 모든 분산 원장에는 동일한 거래 기록 내용을 공유해야 합니다. 모든 노드가 동일한 하나의 체인을 가질 수 있도록 특정 메커니즘에 의하여 블록이 생성 및 연결되게 하는 것이 바로 ‘합의 알고리즘’입니다.

예를 들어 A라는 사람의 금융 거래 내역과 관련하여 한국에서는 1,000원의 잔액이 확인되는데 미국에서는 5,000원의 잔액이 확인된다면 많은 혼란이 발생할 수밖에 없습니다. 이에 블록체인은 합의 알고리즘에 의해서 한국에서 조회하든 미국에서 조회하든 동일한 가치의 잔액이 확인 될 수 있도록, 즉 모든 분산 원장이 동일한 데이터 값을 유지하도록 합니다. 만약 특정 노드에 의해 데이터 값이 조작되거나 이중 지불이 발생하는 등 합의 알고리즘이 정상 작동하지 않는다면 해당 블록체인 시스템은 신뢰성을 잃어버리기 때문에 효과적인 합의 알고리즘 구현은 무엇보다 중요한 요소라고 할 수 있습니다.

이중지불의 문제
이중지불이란 말 그대로 하나의 지폐로 여러 번 결제하는 것을 말합니다. 현재 A의 계좌에는 1,000원이 있는데 A가 B와 C에게 각각 1,000원씩 이체하려고 합니다. 현실 세계에서 이런 일은 불가능합니다. 왜냐하면 은행 시스템이 A의 계좌를 추적 및 관리하고 있기 때문에 바로 차단이 되기 때문입니다. 그러나 온라인 네트워크 상에서 이중지불은 어려운 일이 아닙니다. 동일한 기기 내에서는 불가능하지만 물리적으로 멀리 떨어진 두 개의 지점에서는 동시에 접속하여 보내는 일은 가능합니다. A의 지갑에 대해서 한국에서는 B에게 1,000원을 보내고 미국에서는 C에게 1,000원을 보낼 수 있다는 이야기입니다. 그러나 블록체인 네트워크에서는 '합의 알고리즘'에 의하여 이중지불이 거절됩니다. 왜냐하면 이중지불이 되었다고 하더라도 모든 노드들은 동일한 내용의 분산 원장을 공유하고 있기 때문에 언젠가는 특정 시점에서 충돌이 발생하게 되고 결과적으로 두 거래 중 하나는 거부가 됩니다. 이러한 역할을 하는 것이 바로 합의 알고리즘이며 자세한 사항은 본문을 참고해주시기 바랍니다

물론 하나의 노드에 권한을 부여하여 블록 생성 역할을 전담한다고 하면 보다 쉽게 분산 원장을 유지할 수 있습니다. (블록체인에서의 블록 생성은 거래 내역을 입증 및 기록하는 것을 의미합니다) 그러나 이는 단일 실패 지점을 가지는 기존의 중앙 서버 방식과 큰 차이가 없을 뿐더러 블록체인의 핵심은 바로 특정 노드에 의존하지 않으면서 동시에 신뢰를 제공하는 것이기 때문에, 결과적으로 어떻게 개별 노드들이 자율적으로 블록을 생성하면서도 모든 노드들이 동일한 블록의 체인을 가질 수 있을까가 합의 알고리즘 논의의 관건이라고 볼 수 있습니다.

PoW: Proof-of-Work

작업증명(PoW)은 사토시 나카모토의 논문 ‘Bitcoin: A Peer-to-Peer Electronic Cash System’에서 처음 소개된 메커니즘으로 비트코인을 비롯한 여러 블록체인에 적용되어 있는 전형적인 합의 알고리즘입니다. 원리는 다음과 같습니다.

[그림 2. 작업증명 방식 (Proof-of-Work)]

네트워크에 참여하는 모든 노드는 블록 생성의 권한을 가집니다. 블록은 거래 내역들을 담고 있기 때문에 블록을 생성한다는 것은 해당 블록 내에 기록된 거래 내역들이 입증되었음을 의미합니다.
블록을 생성하기 위해서는 특정한 난이도의 해시(hash) 값을 구하는 수학적 연산을 수행해야 합니다. 해당 연산은 단순하지만 많은 처리 능력을 필요로 하며 해시 값을 찾는데 성공한 노드는 블록을 생성하게 됩니다.

원리는 간단해 보이지만 여기에는 치밀한 장치들이 설정되어 있습니다.

1) 블록들은 어떻게 연결되어 있는가

모든 블록체인은 기본적으로 자료 구조 관점에서 링크드 리스트(Linked List)의 방법으로 블록들이 연결되어 있습니다. 링크드 리스트란 각 노드(여기서는 ‘블록’)들을 포인터로 연결하여 관리하는 구조를 일컫습니다. 쉽게 말하자면 모든 블록들은 자신만의 고유한 블록 해시 값(위에서 말한 해시 값과 동일)을 가지고 있는데, 이 고유한 값은 앞에 연결되어 있는 블록의 블록 해시 값에 대한 정보를 가지고 있어야 합니다.

[그림 3. 링크드 리스트 (Linked List) - 출처: 블록체인 한 번에 이해하기]
예를 들어 Block 1, Block 2, Block 3 이렇게 블록들이 연결되어 있다고 가정했을 때 Block 3의 해시 값에는 Block 2의 해시 값에 대한 정보가 담겨 있어야 하며, 다음으로 Block 4를 이어 붙이기 위해서는 Block 3에 대한 해시 값을 기반으로 다른 정보(거래 내역 등)들과 조합하여 Block 4의 해시 값을 구해야만 연결이 됩니다. 따라서 모든 블록들은 한 줄로 연결되어 있으며 블록 간에는 해시 값을 매개로 연결이 된다고 볼 수 있습니다.

2) 해시 값을 구하는 수학적 연산이란 - 작업증명의 개념

모든 블록들은 고유한 해시 값을 가진다고 했는데 해시 값을 구하기 위해서는 앞에 연결할 블록의 해시 값 이외에도 다른 정보들을 입력 값으로 가져옵니다. 그 중에 하나가 ‘Nonce’라는 값인데 다른 정보와의 차이점은 바로 주어지는 값이 아니라 직접 구해야 하는 값이라는 점입니다. Nonce 값을 구해야만 최종적으로 해당 블록의 해시 값을 구할 수 있습니다. Nonce 값을 구하기 위해서는 특정 수학적 연산을 수행(‘작업증명’ 혹은 ‘채굴’을 의미)해야 하는데 복잡한 연산은 아니지만 반복적인 작업을 필요로 하는 단순 연산으로 높은 컴퓨팅 파워를 가질수록 유리합니다. 비트코인의 경우 평균 10분이 소요되도록 설계되어 있는데 기술 발전 등의 문제에 대응하기 위해 해시 난이도를 주기적으로 조절하고 있습니다.

3) 누가 컴퓨팅 파워를 사용할 것인가 - 보상의 개념

작업증명에는 높은 컴퓨팅 파워와 막대한 양의 전기 비용이 들기 때문에 이에 대한 보상이 없다면 아무도 작업증명을 하지 않게 됩니다. 이에 성공적인 작업증명에 대한 보상으로 새로 발행되는 암호 화폐(‘비트코인’)와 작업증명이 이루어진 블록에 기록되어 있는 거래 수수료(‘비트코인’)를 지급 받게 됩니다. 이러한 보상은 작업증명에 대한 동기 부여 및 유인의 역할을 하게 되며 이러한 이유에서 블록체인과 암호 화폐는 불가분의 성격을 지니게 됩니다.

4) 블록이 동시에 여러 개 생겨난다면 - 충돌

블록 생성은 노드 단위에서 개별적으로 그리고 자율적으로 진행되기 때문에 작업증명의 과정에 있어서 두 개 이상의 노드가 거의 동시에 블록을 생성하는 현상(‘Fork’ 혹은 ‘충돌’)이 발생할 수 있습니다. 이는 분산 장부 내용에 불합의가 존재함을 의미하며 모든 노드의 분산 원장은 동기화되어야 한다는 블록체인의 기본 개념과도 불일치 합니다. 따라서 이를 해결하기 위해 보편적으로 사용되는 방법은 분기가 발생했을 때, 해당 시점에서 더 많은 작업증명이 수행되어 길이가 더 긴 블록을 선택하는 것입니다.

예를 들어 마지막 블록이 'Block P'인 블록체인에서 미국과 호주에서 동시에 해시 값을 찾아 내어 각각 'Block P'에 대해서 'Block A'와 'Block B'를 생성했다고 가정해 봅시다.

[그림 4. 마지막 블록이 'Block P'인 블록체인 네트워크]

[그림 5. 미국과 호주에서 동시에 각각 'Block A'와 'Block B' 생성 ]

[그림 6. 'Block A'와 'Block B'가 공존하는 포크(fork) 발생]

처음에는 일시적으로 미국과 호주를 중심으로 별개의 체인이 분리(fork)되지만 결과적으로 해당 블록들은 네트워크 상에서 어느 순간 만나서 충돌을 일으키게 됩니다. 이때 'Block A'에 대해서 연결된 블록이 없고 'Block B'에 대해서는 누군가가 해시 값을 찾아 'Block X'를 연결했다면 결과적으로 'Block B'에 대해서 더 많은 작업증명이 이루어졌기 때문에 더 긴 체인을 형성한 'Block B'의 체인을 선택하게 되고 'Block A'는 고아 블록이 됩니다.

[그림 7. 'Block B'에 연결된 새로운 블록인 'Block X'의 생성]

[그림 8. 길이가 더 긴 'Block B' 체인 선택 및 고아 블록이 된 'Block A' ]

그렇다면 고아 블록에 담겨 있던 거래 내용들은 어떻게 될까요? 다행히 거래 내역이 취소되거나 유실되지 않고 블록체인에 포함되지 않은 거래로 취급하여 결국에는 다른 블록에 포함되게 됩니다.

여기서 중요한 점은 우선 첫번째로 블록 간의 충돌은 작업증명(PoW)만의 문제는 아니라는 것입니다. 따라서 합의 알고리즘이 작업증명이 아니더라도 블록 간의 충돌은 발생할 수 있으며 그에 따른 해결 방법으로 위의 방법을 사용할 수 있습니다. 두번째로 그렇기 때문에 작업증명에서 충돌이 발생했을 때 위의 해결 방법만 있는 것은 아닙니다. 일례로 이더리움에서는 고아 블록을 버리지 않고 엉클 블록으로 명명하고, 메인 체인에 이들을 포함시키는 GHOST 계열의 알고리즘을 사용하여 충돌 문제를 해결하였습니다.

GHOST 계열의 알고리즘
GHOST 알고리즘에서는 메인 체인을 선택하는 데 있어 가장 긴 체인을 선택하는 것이 아니라 가장 무거운 체인을 채택합니다. 단순히 얼마나 많은 자식 블록들이 이어져 있는지 뿐만 아니라 얼마나 많은 엉클 블록(고아 블록)들을 가지고 있는지를 모두 고려하여 결정되는 메커니즘인 셈입니다. 이러한 메커니즘은 마이닝 후에 버려지는 블록의 갯수를 줄이는 효과를 가져옵니다. 다만 지나친 집중 현상을 막기 위해 유효 엉클 블록 개수는 최대 7개로 한정하고 있습니다.

거래 내역 변경 및 삭제 불가
블록체인은 링크드 리스트 방법으로 연결되어 있다는 점과 충돌(fork) 발생 시 길이가 더 긴 체인을 선택한다는 점 때문에 한 번 완료된 거래 내역에 대해서는 변경이나 삭제가 불가능합니다. 예를 들어 Block 1, Block 2, ..., Block 100까지 연결되어 있는 블록체인이 있다고 합시다. 이 때 Block 10 안에 있는 거래 내역을 수정하게 되면 Block 10의 해시 값은 바뀌게 되고 이에 기존 해시 값에 연결(링크드 리스트)되었던 Block 11과는 다른 새로운 Block 11을 채굴해야 합니다. 충돌이 발생하는 것과 동일합니다. 그러나 블록체인은 합의 알고리즘에 의해서 길이가 더 긴 체인을 선택하기 때문에 결과적으로 기존의 긴 체인이 선택 및 유지되게 됩니다. 물론 이론적인 측면에서 만약 엄청난 연산 능력을 가진 악의적인 노드가 있다면 거래 내역을 변경 및 삭제가 가능(51% 공격 - 지분증명 방식에서 다룰 예정)하지만 현실적으로 51% 이상의 연산 능력을 보유하는 것은 불가능에 가까울 뿐더러 가능하다고 해도 그럴 만한 경제적 유인 동기가 없습니다. 왜냐하면 가장 높은 연산 능력을 보유하고 있다는 것은 가장 많은 블록을 생성할 수 있다는 것이고, 따라서 거래 내역 변경으로 인하여 블록체인의 신뢰성이 깨지게 된다면 가장 많이 피해보는 노드는 당연히 가장 많은 블록을 생성할 수 있는 높은 연산 능력을 가진 노드이기 때문입니다.

PoS: Proof-of-Stake

작업증명의 합의 알고리즘은 블록체인 시대를 알리는 1등 공신이 되었습니다. 하지만 시간이 지날 수록 과도한 에너지 소비 및 채굴의 독점화가 발생하기 시작했고 이에 새로운 합의 알고리즘에 대한 논의가 시작되었습니다. 그렇게 나온 합의 알고리즘이 바로 지분증명(PoS)입니다. 지분증명이란 참여자의 소유 지분(Stake)이 블록 생성 권한에 반영이 되는 알고리즘을 일컫습니다. 원리는 다음과 같습니다.

[그림 9. 지분증명 방식 (Proof-of-Stake)]

블록 생성 및 검증의 역할을 하는 Validator가 되기 위해서는 자신이 보유하고 있는 암호 화폐를 보증금의 형태로 락업하는 특별한 거래(Special Transaction)를 해야 합니다.
그 이후에는 새로운 블록을 생성하고 검증하는 절차는 모든 Validator가 참여할 수 있도록 하는 특정 ‘합의 알고리즘(Consensus Algorithm)’에 의해 이루어집니다.

여기서 중요한 점은 바로 특정 합의 알고리즘이 하나가 아니라는 것입니다. 이에 “지분증명 자체가 합의 알고리즘 아닌가”하는 의문이 드실 수 있습니다. 맞습니다. 그러나 여기서 말하는 특정 합의 알고리즘이란 지분증명이라는 큰 틀 안에서 블록 생성 및 검증, 그리고 보상에 관한 알고리즘을 말합니다. 따라서 그 방법에 따라 지분증명은 다양한 형태가 될 수 있습니다. 가장 대표적인 형태로 ‘Chain-Based Proof-of-Stake’와 ‘BFT-Style Proof-of-Stake’가 있습니다.

[그림 10. 지분증명 방식의 구분]

Chain-Based Proof-of-Stake에서는 10초 단위의 매 슬롯마다 하나의 Validator를 의사 랜덤하게 (pseudo-randomly) 선정합니다. 선정된 Validator는 블록 한 개를 생성할 수 있는 권한을 갖게 됩니다. 그러나 생성된 블록은 반드시 이전 블록 중 하나를 가리켜야 하는데 보편적으로 길이가 가장 긴 체인의 마지막 블록을 가리키게 됩니다. 이에 결과적으로 대부분의 블록들은 단일의 체인에 모이게 됩니다. 지분증명의 가장 기본적인 형태라고 볼 수 있습니다.

BFT-Style Proof-of-Stake에서는 Validator들에게 완전히 랜덤하게(randomly) 블록을 제안(propose) 할 수 있는 권한이 주어집니다. 다만 어떤 블록이 정규 블록인지에 대한 합의는 여러 라운드에 걸쳐 이루어집니다. 매 라운드 마다 모든 Validator는 특정 블록에 ‘투표’를 할 수 있습니다. 그리고 모든 라운드가 끝나면 Validator는 어떤 블록이 체인의 부분인지 아닌지 영구적으로 합의하게 됩니다. 특이한 점이 있다면 길이가 길거나 사이즈가 큰 체인의 블록이 남는 것이 아니라 많은 합의를 받은 단 한 개의 블록만이 남을 수도 있다는 것입니다.

필자가 지분증명의 개념을 이해하는데 있어서 가장 힘들었던 부분은 바로 다양한 형태의 PoS가 존재함에도 불구하고 잘 알려지지 않았다는 점이었습니다. 작업증명의 경우 대표적인 비트코인 사례가 표본이 되었지만 지분증명은 ‘참여자의 소유 지분이 블록 생성 권한에 영향을 미친다’는 의제를 큰 틀에서 공유하고 있을 뿐 세부적인 부분에 있어서는 많은 차이가 있습니다. 따라서 앞으로 지분증명의 합의 알고리즘을 공부하는데 있어 항상 염두에 두시길 바랍니다.

1) 51% 공격의 위험은 없을까

일반적으로 블록체인 네트워크의 51%가 동시에 공격을 진행하면 해당 블록체인은 신뢰성을 잃게 됩니다. 이를 ‘51% 공격’이라고 보통 부릅니다. 이에 지분증명 방식과 관련해서 51%의 지분을 보유한 사람이 존재한다면 쉽게 악의적인 공격이 가능하지 않냐는 우려가 생기기 시작했습니다. 왜냐하면 엄청난 에너지와 기타 자원(채굴기, 넓은 평지 등)을 소모해야 하는 작업증명과 달리 지분증명은 지분만 있으면 누구나 쉽게 블록 생성 권한을 가질 수 있기 때문입니다. 그러나 일각에서는 다음과 같은 이유로 오히려 지분증명이 작업증명보다 분산화가 잘되어 있다고 말합니다.

PoW에서 51%의 해시파워를 가지는 비용 = 약 2,500억원
PoS에서 전 세계 자산의 51%를 보유하는 비용 = 약 25조원

이렇게 독점 권력을 갖기 위해서 지분증명 방식이 작업증명의 방식보다 약 100배 정도 비용이 더 들뿐만 아니라, 지분증명에서는 누구나 코인만 가지고 있으면 네트워크 참여가 가능하기 때문에 분산화가 더 잘되어 있다고 말합니다. 그러나 또 한편에서는 단순 수학적 계산으로 비교할 수 있는 부분이 아니라고 주장하기도 합니다. 왜냐하면 블록체인의 런칭 시기 및 화폐 발행량을 포함한 다양한 요인들로 인하여 51% 지분을 확보하는 비용이 천차만별일 수도 있기 때문입니다.

2) 초기 지분 보유량이 많을 수록 유리하지 않을까

처음 지분증명 방식이 제안되었을 때 초반에 지분을 많이 확보해 두면 블록 생성 권한을 지속적으로 갖게 되는 ‘불평등’의 문제가 제기되었습니다. 이에 대한 보완책으로 내놓은 것이 보유한 코인의 ‘양’과 ‘보유 일수’를 반영하는 것이었습니다. 대표적인 예가 바로 ‘Peercoin’입니다. 예를 들어 A가 10개의 코인을 10일 동안 보유했다면 100의 가치를 갖게 하는 것입니다. (만약 해당 코인을 사용한다면 100의 가치가 소모되고 처음부터 다시 시작됩니다) 이 경우에 보유 코인이 적어도 보유 일수가 길면 블록을 생성할 수 있는 확률이 높아지기 때문에 보다 균등하게 기회가 주어집니다.

3) Nothing-at-Stake 문제가 발생한다는데

Nothing-at-Stake란 말 그대로 잃을 것이 없다는 뜻입니다. 예를 들어 유효한 블록체인이 두 개 이상 존재하는 포크(fork) 상황이 발생했다고 가정해 봅시다. 작업증명 방식에서는 블록을 생성하는데 막대한 양의 컴퓨팅 파워와 전기를 소모하기 때문에 하나의 블록을 지정하여 그 다음 블록을 생성하게 됩니다. (다만 고아 블록이 될 가능성은 존재합니다) 그러나 지분증명 방식에서 Validator는 포크된 모든 블록에 지분을 투표할 확률이 높습니다. 왜냐하면 컴퓨팅 파워와 같은 기회 비용이 존재하지 않고 합의 방법에 별다른 제한이 없기 때문에 양쪽 모두에 지분을 증명해 놓아야 보상 받을 가능성을 높일 수가 있는 것입니다. 이에 Nothing-at-Stake 문제를 해결하기 위한 ‘Slash’ 제도가 도입이 됩니다. 만약 Validator가 여러 블록에 지분을 증명하거나 잘못된 블록에 지분을 증명하게 되면 해당 지분은 Slash, 즉 사라지게 됩니다. 또한 지분 증명 행위 자체에도 일정 수준의 보증금을 내게 하여 잘못된 행위를 할 경우에도 Slash 하는 등 ‘Nothing-at-Stake’를 ‘Something-at-Stake’로 만들어 해당 문제를 해결해 나가고 있습니다.

4) BFT, Byzantine Fault Tolerance란

대표적인 지분증명 방식 중 하나가 BFT-Style이라고 했는데 BFT(Byzantine Fault Tolerance)가 무엇인지 알기 위해서는 Byzantine Generals’ Problem을 알아야 합니다. Byzantine Generals’ Problem란 비잔틴 제국의 여러 장군들이 하나의 적군을 공격하기 위해 출격을 하는데, 적군과의 전쟁에서 승리하기 위해서는 과반수 이상의 장군들이 같은 시각에 공격을 해야 합니다. 그러나 장군들은 오직 연락병을 통해서만 소통을 할 수 있으며 장군들 중에는 한 명 이상의 배신자가 존재하기 때문에 어떻게 출격 시각을 합의할 것인가가 중요한 문제가 됩니다.

Byzantine Generals’ Problem은 2개의 기본 가정을 전제하고 있습니다. 첫 번째 가정은 배신자를 제외한 모든 장군들은 명령이 유효하다고 검증이 되면 이를 충실히 수행합니다. 두 번째는 배신자 m명은 전체 장군 수 n명의 1/3을 넘지 않습니다. 이때 위의 문제를 해결하기 위한 방법은 다음과 같습니다. (Commander = 'C', Lieutenant = 'L')

C는 그의 명령 내용 {v}를 모든 장군들에게 보냄
각각의 L(i)에 대해서 C에게 받은 명령 내용을 {v(i)}라고 한다면
각각의 L(i) 또한 {v(i)}의 내용을 다른 모든 장군들과 공유
L(i)는 자신이 아닌 다른 L(j)로부터 명령 내용 {v(j)}를 수령
L(i)는 {v(1), v(2), … , v(n-1)} 중 다수의 가치를 차지하는 명령을 수행

이를 특정 장군의 관점, 예를 들어 L(2)의 관점에서 도식화하면 이해하기 쉽습니다.

1*IVMEKaA35NAM6sjKT_R2aA.png

[그림 11. L3가 배신자일 때]

1단계: C는 모든 장군들에게 명령 내용 {v}를 보냄
2단계: L2는 L1로부터 {v}를, L3로부터 {x}를 수령
3단계: L2는 {v, v, x} 중 다수의 가치를 차지하는 {v} 명령 수행

Commander가 배신자인 경우에도 마찬가지입니다.

[그림 12. Commander가 배신자 일 때]

1단계: C는 L1, L2, L3에게 각각 {x}, {y}, {z}를 보냄
2단계: L1은 {x}를 L2, L3에게, L2는 {y}를 L1, L3에게, L3는 {z}를 L1, L2에게 보냄
3단계: L1, L2, L3는 모두 {x, y, z}의 내용에 합의를 하게 되며 최종적으로 철수

문제의 핵심은 다수의 장군들이 특정 행동(출격)을 유도하는 것이 아닌 모두가 동일한 결정을 할 수 있게 하는 것이라고 보면 됩니다.

위의 알고리즘은 Byzantine Fault에 대한 해결책을 제시해 줍니다. 만약 특정 시스템이 다양한 요소들의 결과에 영향을 받아 움직이는 시스템이라고 한다면 이런 Byzantine Fault 문제를 잘 다루는 것이 중요합니다. Byzantine Fault Tolerance란 위와 같은 문제들을 다루는 방법에 대한 것으로 BFT-Style Proof-of-Stake란 분산화 되어 있는 블록체인 네트워크에서 악의적인 노드에 의해서 발생할 수 있는 문제들을 다수의 가치(Majority Value)로 해결하고 있음을 보여줍니다. (이는 사토시 나카모토가 비트코인을 처음 만들었을 때 이에 대한 해결책으로 제시한 작업증명 방식 논의에서 언급된 것으로 지분증명 방식만의 이슈는 아니라고 할 수 있습니다)

Conclusion

오늘은 정말 긴 분량에 걸쳐서 작업증명(Proof-of-Work)과 지분증명(Proof-of-Stake)에 대해서 알아보는 시간을 가졌습니다. 사실 처음에 필자가 합의 알고리즘에 대한 글을 쓰고자 결심했을 때는 이렇게까지 많은 내용이 있을 줄은 생각하지 못했습니다. 그러나 글을 쓰다 보니 합의 알고리즘과 관련하여 알아야 할 것들이 정말 많았으며 아직까지도 부족한 부분이 많다고 느껴질 정도입니다. 그래도 최대한 쉽게 그리고 자세하게 설명하고자 노력을 했고 블록체인에 입문하시는 여러분들에게 조금이나 도움이 되었길 진심으로 바랍니다. 다음 편에서는 미리 예고해 드렸듯이 위임된 지분증명(Delegated Proof-of-Stake)에 대해서 알아보도록 하겠습니다. 최근에 가장 주목받고 있는 합의 알고리즘인 만큼 많은 관심과 기대 부탁드립니다.