코스모스의 Tendermint — 블록체인 합의 알고리즘 분석(3)

1. 비잔티움 장군의 문제와 Byzantine Fault Tolerance​

비잔티움 장군의 문제(Byzantine General’s Problem)은 레슬리 램포트 외 2명이 쓴 논문 《The Byzantine Generals Problem》에서 처음 제시된 컴퓨터 공학의 난제로, 블록체인과 같은 분산 시스템의 보안 문제와 매우 밀접한 관련이 있다. 이를 대략적으로 정리하면 다음과 같다.

빨간색으로 표시된 배신자가 존재하는 상황에서는 공격이 실패로 돌아감; 비잔티움 장군의 문제.

적 도시를 침공하기 위해 비잔티움 제국의 장군들이 각자의 부대를 이끌고 도시를 포위하고 있다. 이 상황의 전제로는 세 가지가 존재한다.

1. 장군들 사이에는 적과 내통하는 배신자가 존재하고, 모든 장군들은 해당 배신자가 누군지는 모르나 배신자가 존재한다는 사실을 모두 알고 있다.
2. 충성스러운 장군들이 계획에 맞춰 한꺼번에 도시를 공격한다면, 함락에 성공한다.
3. 공격 계획에 대한 장군들 간의 소통은 전령(messenger)에 의해서만 이루어질 수 있다.​

이러한 상황에서, 배신자들은 충성스러운 장군들 간 소통을 방해함으로써 도시에 대한 공격이 실패로 돌아가도록 조작할 것이다. 배신자들의 방해 공작에도 공격에 대한 합의가 잘 이루어질 수 있을지에 대한 문제를 ‘비잔티움 장군의 문제’라고 한다.​

이는 블록체인 네트워크에서 굉장히 중요한 개념이다. 만약 네트워크 참여자 중 악의적인 의도를 가진 노드가 존재한다면, 트랜잭션이나 블록을 조작하여 이중 지불 등 치명적인 문제를 발생시킬 수 있기 때문이다. 즉, 악의적인 노드가 있는 상황에서도 올바른 합의가 이루어질 수 있는 알고리즘이 탑재되어야 한다.​

이러한 문제를 방지할 수 있는 알고리즘을 비잔틴 장애 허용(Byzantine Fault Tolerance; BFT)이라고 한다. BFT는 쉽게 말하면 다수결을 따르는 합의 알고리즘으로, 일부 악의적인 노드가 존재하여도 정직한 참여자가 다수라면 올바른 방향의 합의가 가능하다는 것이다.​

이전 글들에서 본 POW와 POS도 BFT를 구현하고 있다. 이를테면, 비트코인의 POW에서는 해시 경쟁을 통한 블록 생성과 이후 블록이 올바른지에 대한 검증을 진행함으로써 비잔티움 장군의 문제를 효과적으로 방지한다. 수학적으로 완벽한 BFT가 보장되지는 않으나, 현실적으로 비잔티움 장군의 문제로 인한 네트워크 오류 등을 겪을 가능성이 매우 적다.

블록체인 합의 알고리즘 분석 — 비트코인의 작업증명 (1)

이더리움 Gasper에서는 블록 검증 및 epoch 경계 페어의 supermajority link 생성을 위해 2/3 이상의 투표수(=ETH)를 요구한다.​

블록체인 합의 알고리즘 분석 — 이더리움 Gasper의 지분증명 (2)

2. Practical Byzantine Fault Tolerance​

이후 더 수학적으로 엄밀한 BFT를 위한 연구를 통해 PBFT, Practical Byzantine Fault Tolerance라는 개념이 등장한다. 구엘 카스트로와 바바라 리스코브의 논문 《Pratical Byzantine Fault Tolerance》에서는 PBFT에 대한 자세한 설명을 통해 다음 명제를 증명함으로써, 블록체인에서 올바른 합의에 대한 도출을 할 수 있는 이론적인 기반을 이끌어냈다.

• 비동기 네트워크에서 악의적 노드가 f 개일 때, 총 노드 수가 3f+1 이상이면 해당 네트워크의 합의를 신뢰할 수 있다.​

이에 대해 자세히 알아보자. PBFT는 다음과 같은 구조를 가지고 있다.

PBFT의 메세지 처리 구조. 3이 악의적인 노드로 메세지에 응답하지 않는다.

1. request : 클라이언트(C)로부터 primary node(0)으로 블록 생성에 대한 합의 요청 메세지가 들어온다.
2. pre-prepare : primary는 해당 메세지를 검증하고, 복사하여 replica node(1,2,3)에 브로드캐스팅한다.
3. prepare : 각각의 replica node들은 전달받은 메세지를 확인하고 올바른지 검증한 후 본인을 제외한 다른 노드들에게 브로드캐스팅한다.
4. commit : prepare의 과정을 반복 수행한다.
5. reply : 각각의 replica node들은 일정 수 이상의 메세지를 받으면 클라이언트의 요청을 수용하는 것으로 합의하고, 클라이언트에게 하브이 완료 메세지를 보낸다.

​

이때 전체 노드의 개수를 n, 악의적인 노드의 개수를 f라고 하자. 해당 시스템에서 악의적인 노드는 본인이 받은 메세지를 브로드캐스팅하지 않는 방식으로 합의를 방해할 것이다. 만약 이러한 상황이하면 primary는 정상 노드라는 가정을 할 때, prepare 단계에서 각각의 replica node가 받을 수 있는 메세지의 총 수는 n-f 개이다. 악의적인 노드가 본인이 받은 메세지를 의도적으로 브로드캐스팅하지 않기 때문이다. 그런데 만에 하나, prepare 단계에서 응답하지 않았던 노드들이 악의적인 노드가 아니라면 어떻게 되는가? 즉, prepare 단계에서 각 노드들이 받은 메세지 n-f 개 중 f개는 악의적인 노드에 의한 메세지인 것이다. 이후 commit 단계로 넘어가게 된 상황에서 악의적인 노드 f개는 본인의 받은 메세지를 의도적으로 브로드캐스팅하지 않는다고 생각해보자. 그렇다면 정상 노드들이 받게 되는 메세지의 총 수는 n-2f 개 일 것이다. 이 상황에서 올바른 방식의 합의가 가능하려면, 다수결의 원칙에 의해 reply 단계에서 클라이언트로 전송되는 메세지 중 절반 초과가 정상 노드에 의한 메세지여야 하므로, n-2f > f 여야 한다. 즉, n > 3f 여야 하고, 이는 위에서 언급하였던 다음 명제로 이어진다.​

• 비동기 네트워크에서 악의적 노드가 f 개일 때, 총 노드 수가 3f+1 이상이면 해당 네트워크의 합의를 신뢰할 수 있다.​

PBFT의 특징은 비동기적 네트워크에서 노드들 간의 활발한 소통을 통해 악의적인 노드가 존재하는 상황에서도 합의가 가능하다는 것이다. 특히 POW 방식의 합의와 비교했을 때 높은 TPS와 완결성 보장에 있어 더 나은 퍼포먼스를 보인다. 현재 질리카, 네오, 그리고 프라이빗 블록체인이긴 하지만 IBM의 하이퍼렛저 패브릭과 같은 서비스에서 PBFT를 사용하고 있다.​

PBFT의 가장 큰 장점은 완결성이다. 이전에 살펴본 합의 알고리즘들은 체인의 완결에 있어 시간이 지연될 수 있는 여지가 존재한다. 예를 들어 비트코인의 POW에서는 블록 생성 후 6블록 동안(약 60분)의 검토를 통해 해당 블록의 완결성을 검토하기 때문에 트랜잭션이 즉시 처리되지 않는다. 또한 이더리움의 Gasper에서도 마찬가지로 한 epoch가 마무리되고 이전 EBP들과의 연결성(supermajority links)이 확인되어야 완결성을 획득할 수 있기 때문에, 비트코인만큼은 아니지만 거래 확정에 시간이 소모되는 것은 사실이다. 그러나 PBFT는 악의적인 노드가 전체의 1/3 이하라면 완결성이 보장된 블록이 즉시 생성되므로, 악의적인 포크 현상이 발생할 가능성이 거의 없고 완결성을 항상 유지할 수 있다.​

그러나 PBFT는 한 가지 단점이 있다. 합의 과정에서 노드들이 모두 연결되어 소통을 해야하기 때문에, 노드가 많아질수록 합의에 걸리는 시간이 기하급수적으로 커진다는 것이다. Yin Yang의 논문 《LinBFT : Linear-Communication Byzantine Fault Tolerance for Public Blockchains》에서는 해당 알고리즘의 시간복잡도가 n의 4승으로, 노드의 개수에 따라 소요 시간이 매우 빠른 속도로 증가함을 지적한다. 즉, 네트워크의 규모가 클수록 탈중앙화도는 높아지지만, 합의에 더 오랜 시간이 걸리고 확장성이 떨어진다는 것이다.

​

3. Tendermint​

이러한 문제점을 효과적으로 보완한 프로토콜이 코스모스의 Tendermint이다. Tendermint는 PBFT와 DPOS가 결합된 합의 알고리즘을 사용한다. DPOS는 Delegated Proof-of-Stake의 줄임말로, 선출된 몇 개의 노드들이 코인 보유자들로부터 자산을 위임받아서 해당 자산을 통해 블록 생성 및 검증을 하는 형태의 POS 합의 알고리즘이다. 쉽게 이야기 하자면, 현대 정치의 대의 민주주의와 유사한 형태라고 할 수 있다. 비트코인과 이더리움은 일반 사용자도 채굴을 통해 네트워크 보안 및 유지에 기여할 수 있도록 설계된 반면, DPOS 합의 알고리즘에서는 투표를 통해 위임자(Delegators)를 선출하고, 위임자들에게 코인을 맡겨 블록 생성 및 검증을 하도록 만들었다. 위임자들이 따로 특별하게 존재하는 것이 아니라 직접 코인 보유자들에 의해 선출되기 때문에, 현대 정치의 선거와 같은 권력 집중에 대한 견제 구조가 만들어지므로 어느 정도의 탈중앙화가 시스템적으로 보장되었다고 할 수 있다.

PBFT에서는 성능의 제약으로 제한된 개수의 노드들만이 네트워크에 참여할 수 있는 구조이므로, 자칫하면 중앙화가 되는 문제가 발생할 수 있다. Tendermint에서는 DPOS를 도입함으로써 해당 노드들의 수를 늘리지 않더라도 어느 정도 탈중앙화도를 보장할 수 있는 시스템을 구축하였다. 코인 보유자에 의한 투표로 노드들의 권력에 대한 견제가 이루어질 수 있기 때문이다. 또한 이에 더해 이더리움의 Gasper와 유사한 방식으로 위임자들의 악의적인 행동에 대해 금전적인 제재가 부과되어, Nothing at Stake 문제 등을 방지할 수 있다.​

Tendermint의 합의 과정을 조금 더 자세히 알아보자. 우선, PBFT 방식에서 블록을 제안하고 해당 메세지를 모든 노드에게 브로드캐스트하는 primary node(리더)는 가중 라운드 로빈 방식(wieghted round-robin)으로 랜덤하게 선출된다. 해당 과정은 다음과 같다.

1. 각 밸리데이터마다의 가중치(weight)가 존재한다.
2. 가중치가 높은 밸리데이터가 리더로 설정되고, 새로운 블록을 제안한다.
3. 해당 블록에 대한 PBFT 합의 과정이 완료되면, 해당 밸리데이터의 가중치를 모든 밸리데이터 가중치의 합만큼 감소시킨다(맨 뒤로 보내는 것과 같은 효과).
4. 라운드가 진행됨에 따라 가중치는 각 밸리데이터의 투표권(=자산)의 양에 따라 증가한다.
5. 2부터 다시 반복된다.​

해당 과정의 코드는 아래 Github 링크에 자세히 나와있으니, 참고하길 바란다.

tendermint/validator_set.go at master · tendermint/tendermint

이더리움의 Gasper에서는 각 블록을 제안하는 밸리데이터를 랜덤하게 뽑았다면, Tendermint에서는 투표권에 기반한 우선순위를 통해 결정론적으로 블록 제안자를 뽑게 된다. 그런데 이는 다음 블록 생성자에 대한 정보가 알려진 것이나 다름 없으므로, 공격자 입장에서 해당 밸리데이터에 대한 디도스 공격을 실행한다면 블록의 생성을 막고 체인의 진행을 방해할 수 있게 된다. Tendermint에서는 밸리데이터 구성 시 sentry node를 도입함으로써 디도스 공격을 방지한다.

Tendermint 밸리데이터 설정 시 Sentry Node 도입을 통한 디도스 공격 방지.

해당 시스템을 이용할지 여부는 밸리데이터 각각이 결정하는 것이지만, 모든 밸리데이터들이 이를 이용할 것임을 예상할 수 있다. 이를 이용하지 않아 디도스 공격을 당해 제 차례에 블록을 제안하지 못하게 되는 경우, slashing condition에 의한 금전적인 손해를 입고 네트워크에서 퇴출될 것이기 때문이다.

​

아래 그림은 Tendermint의 합의 과정을 도식화한 것이다.

Tendermint의 합의 알고리즘.

용어가 조금 다르긴 하나, PBFT의 그것을 그대로 따르고 있음을 알 수 있다. 아래는 PBFT의 용어에 해당되는 Tendermint 합의 과정에서의 용어를 정리해 놓은 표이다.

Tendermint에서 prevote와 precommit 과정은 모두 구성원의 2/3 이상의 동의를 요구한다. 이를 폴카(Polka)라고 한다. 특히 precommit 과정에서 폴카가 확인되지 않을 경우, 같은 블록 높이에서 새로운 라운드를 열어 또다른 블록을 제안받게 된다.​

왜 두 과정에서 모두 폴카를 요구하는 것일까? 한 번의 투표로 블록을 확정지을 수는 없을까? 이는 각 밸리데이터마다 view가 다르기 때문이다. 예를 들어서, 블록 1에 대해 찬성이 67표, 반대가 33표 나온 상황이라고 해보자. 그런데 Tendermint는 비동기적 네트워크를 가정하기 때문에, 각 밸리데이터마다 해당 투표에 대한 결과를 다르게 볼 수 있다. 이를테면 밸리데이터 A의 네트워크에는 67개의 찬성표가 먼저 도착하여, 2/3 이상이 찬성한 것으로 판단하고 블록을 승인할 수 있다. 한편, 밸리데이터 B의 네트워크에는 오류로 인해 반대 33표와 찬성 34표만이 도착할 수도 있다. 이 경우 B는 블록을 생성해야할지에 대해 올바른 판단을 내릴 수 없다. 이러한 상황을 방지하기 위해 두 번의 투표로 블록의 완결성을 확보하는 것이다.​

그런데, 이와 같은 상황이 두 번째 투표에도 반복된다면? 혹은, 특정 밸리데이터가 precommit 단계에서 마음을 바꿔 prevote 단계에서 투표한 블록과 다른 블록에 투표를 해버린다면? 투표를 두 번 하는 것에 대한 의미가 없어진다. 이를 방지하기 위해, Tendermint에서는 락(lock) 시스템을 도입한다. prevote 과정에서 폴카를 확인한 밸리데이터는 해당 블록을 잠근다(lock). 해당 밸리데이터는 이후 precommit 단계에서도 잠근 블록에 투표하여야만 한다. 만약 precommit에서 폴카가 이루어지지 않고 다음 라운드에서 새로운 블록이 제안될 경우, 해당 블록이 폴카를 달성한다면 이전 블록에 대한 잠금을 풀고 새롭게 제안된 블록을 잠그게 된다.​

이러한 방식으로 prevote와 precommit 과정의 폴카, 그리고 lock을 통해 생성되는 블록에 대한 완결성을 확보할 수 있게 된다.

​

Tendermint는 블록의 즉각적인 완결성과 높은 TPS라는 PBFT의 장점을 유지하면서, DPOS를 결합시켜 대의민주주의적인 탈중앙화를 추구하는 합의 알고리즘이다. 이는 ABCI(Application Blockchain Interface)와 결합되어 자체 블록체인을 이용한 Dapp을 개발하려는 사람들에게 매우 좋은 개발환경을 제공한다. 현재 바이낸스 스마트 체인(BSC), 카바(Kava), 그리고 스테이블코인 이슈가 있었던 테라(Terra) 등 여러 유명 블록체인 프로토콜들이 Tendermint로 합의 알고리즘을 구성하고 있다.​

다만 Tendermint에도 구조적인 문제점이 존재하는 것은 사실이다. PBFT에서 지적되는 가장 큰 문제점 중 하나는, 네트워크 자산의 1/3 이상을 차지하는 공격자를 막을 수 없다는 점이다. 이는 테라의 death spiral 과정에서 가시적으로 드러났다. 5월 13일 기준으로 테라의 스테이킹 자산 Luna의 가격이 폭락하여 약 $0.00015가 된 시점, 테라 네트워크에 대한 공격을 행하기 위한 1/3의 자산은 약 3천만원 수준으로 공격에 매우 취약한 상태가 되었다. 이를 깨달은 테라 파운데이션 측은 체인 중단 및 스테이킹 위임 기능을 막음으로써 체인에 대한 공격을 방지하였다. 합의 알고리즘 자체로 공격을 막은 것이 아니라, 외부적인 합의를 통해 공격의 가능성을 억지로 틀어막은 것이다.​

우리는 이러한 상황이 과연 테라에 대해서만 발생할지에 대해서 생각해 보아야 한다. Tendermint를 기반으로 하는 블록체인들은 BSC를 제외하면 상대적으로 소규모인 경우가 많다. 즉, 돈 많은 공격자가 마음만 먹으면 네트워크 자산의 1/3을 확보하는 상황이 발생할 수 있다. 물론 POS 기반의 금전적인 제재를 통해 자금 탈취는 일시적일 것이나, 해당 네트워크의 규모 및 신뢰 문제와 결부되어 테라와 같이 재기불능의 상황에 빠지는 경우가 또 발생할 수 있다. 따라서, Tendermint 기반의 프로토콜을 만드는 개발자와 이용하는 투자자 모두 해당 공격의 가능성을 충분히 인식하고 각자의 안전 장치를 설정해 두어야 할 것이다.