[Blockchain] 합의 알고리즘의 특성과 완결성

yooni·2022년 3월 4일

BFT CAP blockchain finality liveness safety

Blockchain

목록 보기

13/36

❗️ 합의 알고리즘의 중요성
블록체인에서는 트랜잭션 정보를 기록한 분산 장부의 일관성을 유지하는 것이 중요하며, 이는 중앙집중적 방식이 아닌 개별 노드들의 자율적 합의에 따라서 결국 모든 노드가 같은 블록체인 이미지를 가지도록 하는 것이다.
비트코인에서 쓰인 합의 알고리즘은 이런 역할을 충실히 수행했지만 성능과 에너지 낭비 측면에서 많은 단점을 갖고있다. 비트코인 이후의 블록체인 시스템들은 성능과 에너지 문제를 해결하기 위해 다양한 특성을 가진 독특한 방식의 합의 알고리즘을 도입하고 있다. 합의 알고리즘은 성능, 에너지, 보안, 개방성 등의 가치 중 어디에 중점을 두는가에 따라 다양한 형태로 개발될 수 있다.

1. 합의 알고리즘의 2가지 속성

어떤 합의 알고리즘이 네트워크에서 통용되기 위해서는 아래 두 가지 특성을 가지고 있어야 한다.

Safety (시스템에 나쁜 일이 발생하지 않는다.)
정상적인 참여자는 같은 상태에 동의해야 하고 그 상태는 유효해야 한다. 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안된다. 즉, 문제 없는 노드는 잘못된 합의를 하지 않는다. 합의 알고리즘이 safe하지 않으면 블록에 포크가 발생하게 된다.
Liveness (시스템은 항상 살아있어야 한다.)
모든 참여자는 결국에는 어떤 상태에 동의해야 한다. 문제 없는 노드는 반드시 합의를 한다. 합의 알고리즘이 live하지 않으면 영원히 합의하지 못하고 교착상태에 빠질 수 있다.

1-1. FLP Impossibility (FLP Theorem)

Fail-Stop-Failure가 하나만 있어도 Safety와 Liveness를 둘 다 만족하는 합의 알고리즘은 존재할 수 없다. 비동기 네트워크 내에서는 Safety와 Liveness를 둘 다 만족시킬 수 없다는 것이다. 즉 비동기 네트워크 내에서는 합의 문제를 완벽하게 해결할 수 있는 분산 알고리즘이 존재하지 않는다. 블록체인 구동 네트워크 역시 비동기 네트워크이므로 블록체인 시스템의 완벽한 합의 알고리즘은 존재하지 않는다. 따라서 합의 알고리즘을 선택한다는 것은 Safety와 Liveness 중 무엇을 선택하고 무엇을 포기할지에 대한 문제이다.

✔️ Fail-Stop-Failure
전통적 분산 시스템에서는 여러 노드들이 메시지를 주고받으며 상태를 변화시킨다. 이 때 모든 노드가 정상적인 경우만 가정할 수는 없다. 시스템이 감당할 수 있는 에러의 종류를 시스템의 Failure Model이라고 부르며 총 6 계층으로 분류된다. Fail-Stop-Failure에서는 문제가 발생한 노드는 더이상 상태가 변하지 않지만, 문제가 발생하기 이전의 상태를 돌려준다.

1-2. Liveness > Safety (PoW)

🖍 잘못된 합의가 이루어질 수 있지만 어떻게든 합의는 한다.

PoW (Nakamoto Concensus)

더 어려운 문제를 푼 체인이 있다면, 그 체인을 유효한 체인으로 판단한다. (비트코인 합의 알고리즘)

더 긴 체인을 만들 해시파워만 있다면 현재 합의된 블록을 언제든지 대체할 수 있다. 이 알고리즘은 태생적으로 최대 7TPS 정도까지만 처리할 수 있다. 또한 작업 증명으로 인한 에너지 낭비 문제도 제기된다. 이 방식은 완결성(Finality)이 보장되지 않으며, Liveness를 위해 Safety를 희생한 케이스이다.

Liveness를 중시하는 Nakamoto Concensus에서 출발한 합의 알고리즘들은 향후 Safety를 보장할 방법을 추가하며 발전했다. 이더리움의 Casper, the Friendly Finality Gadget이 대표적이다.

1-3. Liveness < Safety (BFT 계열)

🖍 잘못될 가능성이 있다면 블록을 만들지 않는다.

BFT 계열의 합의 알고리즘

✔️ 비잔틴 장애 허용 (Byzantine Fault Tolerance)
이 개념은 블록체인 기술이 나타나기 이전에도 분산 컴퓨팅 환경에서 쓰이던 합의 알고리즘이 있다. 대표적으로 비잔틴 장군 문제를 해결하기 위한 비잔틴 장애 허용(Byzantine Fault Tolerance) 이며, 블록체인의 합의 알고리즘으로 사용될 수 있다.

Cosmos에서 사용하는 Tendermint가 Safety를 보장하는 대표적인 BFT 알고리즘이다. FLP Impossible에서 증명된 바와 같이 비동기 네트워크에서 Safety가 보장된 경우, Liveness를 보장할 수 없다. 비동기 네트워크 모델에서는 Liveness가 보장되지 않으므로 메시지가 전송에 보장된 시간이 없다. 메시지가 무한한 시간 후에 도착할 수도, 메시지가 도착하지 않을 수도 있다. BFT 계열 알고리즘에서는 다른 모델 네트워크를 사용해야 한다. Tendermint에서는 정해진 시간 안에 메시지가 도달하는 것은 보장되지만 그 시간은 알 수 없다는 Partial Synchronous Network Model을 사용한다.

BFT 계열 합의 알고리즘은 블록 생성을 위해 2번의 투표를 진행해야 한다. Partial Synchronous Network Model에서는 언젠가는 합의될 것을 보장하지만, 최악의 경우 수 차례의 라운드 후에도 새로운 블록이 생성되지 않을 수 있다. 이는 TPS 저하로 이어진다. BFT 계열 알고리즘은 이러한 문제를 해결하기 위한 방향으로 발전해왔다. 2018년 3월 발표된 Hot-Stuff 프로토콜이 대표적이다.

2. 완결성 (Finality)

블록체인에 일단 커밋되면 구성된 모든 블록이 취소되지 않는다는 확인, 거래가 완료되면 거래가 임의로 변경되거나 되돌릴 수 없다는 확신

블록체인 합의 알고리즘 설계시 중요하게 고려해야 할 또 다른 개념이 완결성(Finality)이다. 이러한 비가역성은 블록체인의 대표적인 특징 중 하나이다. 되돌려진 블록은 큰 금액의 손실을 초래하거나 분산 응용 프로그램의 기본 작업에 영향을 줄 수 있다. 따라서 완결성을 이해하는 것은 강력한 블록체인 플랫폼을 구축하고 애플리케이션을 개발할 플랫폼을 선택하는 데 모두 중요하다.

새로운 블록록이 생성되어 블록체인에 추가되면, 추가된 블록은 절대 되돌아가 고쳐질 수 없다. 이러한 완결성은 어느 정도의 시간이 걸린다. 대부분의 블록체인은 느린 TPS를 개선하고자 Probabilistic Finality를 제공한다. Tendermint와 같은 PBFT 기반 프로토콜에서는 Absolute Finality를 제공한다.

2-1. 완결성의 종류

Probabilistic Finality (확률적 완결성)

트랜잭션이 포함된 블록이 체인 깊숙이 가라앉을수록 트랜잭션이 되돌려지지 않을 확률이 높아진다. 블록이 깊을수록 해당 블록을 포함하는 포크가 가장 긴 체인일 가능성이 높아진다. 따라서 어느 정도의 시간을 기다려야 트랜잭션이 완결성을 갖춰 비가역적인 상태가 된다. 비트코인의 경우 트랜잭션을 수행하기 전에 비트코인 블록체인 깊이가 6블록이 될 때까지의 시간인 1시간을 기다려, 트랜잭션을 되돌릴 가능성이 매우 낮음을 확인하는 것이 좋다. 이렇듯 완결성은 블록체인의 보안성 측면에서 중요하지만, 블록이 추가될 때까지 기다려야 하는 사용자의 편의성과도 밀접한 연관이 있다.

PoW를 사용하는 비트코인의 경우 블록이 채굴되는 평균 시간은 10분이며 완결성까지는 6번의 검증을 거쳐 1시간이나 소요된다. 이더리움 역시 PoW를 사용하지만 블록이 채굴되는 평균 시간은 15초이고, 완결성까지는 25번의 검증을 거쳐 6분이 소요된다.

Absolute Finaility (절대적 완결성)

트랜잭션이 블록에 포함되고 블록이 체인에 추가되면 즉시 완료된 것으로 간주한다. 이 때 리더가 블록을 제안하고 검증인 위원회가 충분한 비율로 블록을 승인해야 커밋이 된다.

Economic Finality (경제적 완결성)

블록을 되돌리는 경우 금전적 비용이 얼마나 많이 드는지를 판단한다.

2-2. PoW와 PoS의 완결성

PoW는 '가장 긴 체인의 법칙'을 적용하기 때문에, 언제든 메인 체인이 바뀔 확률이 존재한다. 따라서 Finality를 보장받을 수 없다. 거대한 마이닝 집단에 의해 51% Attack을 받아 문제가 될 수도 있다.

반면 PoS에서는 한 번 검증받은 블록은 절대 변경이 불가능하게 되어 PoW에 비해 비교적 더 Finality를 보장한다. 따라서 한 번 메인 체인으로 인정된 블록은 영원히 불변한다. 또한 PoS는 사이버 펑크 정신을 계승할 수 있다. 사이버 펑크 정신이란 공격 비용을 방어 비용보다 높게 한다는 것으로, PoS에서는 공격비용 >= 방어비용 이기 때문에 PoW에 비해 공격에 대한 위협이 줄어들 수 있다.

PoW와 PoS의 완결성 문제를 해결하기 위해 PBFT(프랙티컬 비잔틴 장애 허용) 알고리즘이 많이 채택되고 있다.

3. CAP Theorem

확률적 완결성과 절대적 완결성 중 어느 하나가 더 바람직하다고 할 수는 없다. Eric Brewer의 CAP Theorem을 활용하여 이러한 완결성 절충 문제에 접근해볼 수 있다.

✔️ CAP Theorem
분산 시스템은 일관성이나 가용성 중 하나만 보존할 수 있다. 일관성(Consistency)은 모든 노드들은 같은 시간에 동일한 항목에 대해 같은 내용의 데이터를 사용자에게 보여주어야 한다는 것이며, 가용성(Availability)은 분산 시스템이 지속해서 가용하기 위해 장애없는 노드에 수신된 모든 요청은 반드시 응답되어야 한다는 것이다.
※ 이는 CAP 이론의 일부의 내용이며, 정확하게는 일관성/가용성/분할허용 세 가지 속성을 만족할수 없다는 내용이다.

단순 지불에 있어서 사용자는 가용성을 선호하는 경우가 많다. 가용성을 선호하는 많은 DAG 기반 프로토콜이 지불 지원에 초점을 맞추고 있다. 하지만 스마트 컨트랙트에 기반한 여러 dApp들은 완결성에 대해 다양한 선호도를 가질 수 있다.

가용성이 우선적인 dApp은 일부 부정확성에 관계없이 트랜잭션이 항상 통과될 수 있는 것을 선호할 것이고, 일관성이 우선적인 dApp은 부정확한 트랜잭션이 진행되는 것보다 전체 애플리케이션이 중단되는 것이 바람직하며 절대적인 최종 체인을 선호할 것이다. 이렇게 완결성은 사용자 경험에 근본적인 영향을 미친다.

4. Byzantine Fault Tolerance (BFT)

4-1. 기존 합의 알고리즘의 문제

PoW, PoS 알고리즘이 작동하기 위해서는 블록체인 시스템 내부적으로 코인 등의 보상 시스템이 꼭 필요하다. 보상이 없다면 블록을 생성할 이유가 없다. 내부 화폐라는 보상 없이는 합의 알고리즘을 사용할 수 없는 것이다.

또한 기존 알고리즘은 가상화폐가 필요하다는 것 외에 부분 분기가 일어날 수 있다는 문제가 있다. 작업증명 알고리즘에서 두 개의 블록이 동시에 생성될 경우, 각 노드가 둘 중 하나를 선택해야 한다. 또한 이후의 블록들이 확정되어야 이전 블록들이 확실하게 합의를 이루게 되기 때문에 즉각적 거래 확정을 요구하는 서비스에는 적용이 어렵다.

4-2. CFT vs BFT

CFT (Crash Fault Tolerance)
CFT는 분산시스템에서 노드가 비정상적인 충돌에 의해 문제가 생기더라도 나머지 시스템에서 서비스를 유지할 수 있게 하는 작동방식이다.
하이퍼레저 패브릭과 같은 컨소시엄형 블록체인 시스템에서는 보통 조직들이 신원확인을 통해 허가를 받은 상태에서 참여하기 때문에 악의적인 행위를 하지 않을 거라는 신뢰가 형성되어 있다. 따라서 특정 상황에 대한 노드 문제만을 염두에 둔 CFT 기반 알고리즘이 우선된다.
BFT (Byzantine Fault Tolerance)
반면 BFT는 더욱 복잡하고 악의적인 공격이 있을 수 있는 시스템에 적용된다. 비트코인의 경우 CFT, BFT 보다 높은 수준의 신뢰작업이 필요해 PoW 알고리즘을 사용한다.

4-3. BFT 알고리즘 (Byzantine Fault Tolerance)

비잔틴 장군 문제를 해결하는 방안, 알고리즘으로 비잔틴 장군 문제로부터 파생된 장애 허용 분야 연구의 한 갈래로 볼 수 있다.

✔️ 비잔틴 장군 문제 (Byzantine Generals Problem)
배신자가 있는 상황에서는 여러 장군들이 받은 명령을 진실이라과 확정하기 어렵다는 내용으로, 분산 컴퓨터 시스템에서 일부 노드의 장애와 해킹이 공격이 있으면 시스템을 안정적으로 운영하기 어렵다는 원리를 설명하기 위해 언급된 개념이다.

BFT 알고리즘은 이전에도 있었지만, 실제로 시스템을 구현한 것은 비트코인이 처음이다(나카모토는 주장한다). 비트코인은 PoW 알고리즘을 이용해 비잔틴 장군 문제를 해결하고자 했다. BFT와 PoW, PoS는 서로 아예 다른 개념이 아니라, 블록체인 분야에서의 BFT 시스템을 합의 알고리즘(PoW, PoS ...)이라고 부르게 된 것이다.

4-4. PBFT (Practical Byzantine Fault Tolerance)

텐더민트, 하이퍼레저 등에서 사용하는 합의 알고리즘이다. BFT를 속도와 실용성 측면에서 개선한 형태로, 기존 BFT가 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서의 합의를 이룰 수 있게 하였다. PBFT는 거래 확정 시간이 짧으며 PoW, PoS의 단점인 완결성 문제를 해결할 수 있기 때문에 블록체인 시스템에서 많이 채택되고 있다. 또한 PoS(지분 증명 방식)을 기본으로 하기 때문에 에너지 사용량이 적고 거래 비용이 작다.

이 방식은 일부 노드의 결과가 달라도 어느 정도 이상의 결과가 동일하면 합의가 이루어진 것으로 본다. 다수결의 원칙을 따르는 합의 알고리즘이다.

리더가 되는 노드0가 클라이언트의 요청을 받아 다른 노드(노드1~노드3)에 전파한다.
리더의 메시지를 받은 노드들은 메시지를 확인하고 다른 노드들에 다시 메시지를 전파한다. 모든 노드는 다른 노드에서 가장 많이 받은 메시지(승인 메시지)가 무엇인지를 확인하고 다른 노드들에 전파한다.
각 노드들은 각자 승인한 메시지를 모두 수신하고 정족수(혹은 과반수) 이상이 승인한 메시지가 무엇인지 확인함으로써 합의를 이룬 동일한 메시지를 보유하게 된다.

두 단계의 절차를 거쳐 합의를 검증하며 비잔틴 노드의 수가 전체의 33% 이하일 때 합의의 신뢰성을 수학적으로 보장한다. 네트워크에 참여하는 모든 노드에 메시지를 뿌리고 받기 때문에 노드의 수가 대규모로 늘어나면 복잡도가 증가해 확장성을 확보하기 어렵고 합의를 도출하기도 어려워진다. 100개의 노드로 운영하면 거래 확정에 약 6초가 걸린다. 합의 그룹의 각 노드는 모든 노드들과 두번씩 메시지를 주고 받아야 하므로 전체 노드 N의 제곱 수준의 커뮤니케이션 교환이 필요하게 된다. 따라서 PBFT 알고리즘은 프라이빗 블록체인에서 많이 사용된다.

4-5. Tendermint

Cosmos에서 사용하는 합의 알고리즘으로 전통적 합의 알고리즘이 블록체인에 적용된 의미있는 사례이다. DPoS(Delegated Proof-of-Stake)와 PBFT의 장점을 결합하여 퍼블릭 및 프라이빗 블록체인에서 사용할 수 있도록 개량한 알고리즘이다.

DPoS와 PBFT 방식을 개선하여 이중 지불에 대한 문제와 비잔틴 오류 허용 문제를 해결하기 위한 방안으로 네트워크 상의 1/3(33%)의 공격에도 안전한 합의 방식이다.

기존의 PBFT 방식이 개별 노드당 투표권을 행사하는 방식이었다면, 텐터민트 방식은 여기에 DPoS가 포함되어 지분 기반으로 투표를 진행하는 방식이다. 지분이 많은 노드의 신뢰도가 높아지는 방식으로 투표시에는 지분이 동결되어 다른 블록에 중복으로 투표할 수 없도록 만들어 이중 지불 문제를 해결했다. 또한 이중 투표 시도와 같은 악의적 행위를 발견하면 지분을 빼앗는 방법으로 기존 블록체인이 네트워크 공격 노드에 아무런 처벌을 하지 않았던 'Nothing of Stake' 문제도 해결하였다.