TIL) 합의 알고리즘 기초 : FLP Impossibility에서 Tendermint까지

 

블록체인의 블록을 어떻게 생성할 것인가?

 

이것이 블록체인에서 말하는 합의 알고리즘이다.

 

합의 알고리즘은 두 가지의 속성을 만족해야 한다.

- safety: 노드 간 합의가 발생했다면 어느 노드든 그 값은 동일해야 한다.
- liveness: 합의 대상에 문제가 없다면 네트워크 내에서 반드시 합의가 지속적으로 이루어져야 한다. 

 

 

1985년 Fischer, Lynch, and Paterson는 비동기 네트워크에서 safety와 liveness를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것이 불가능함을 증명하였다. 

 

비동기 네트워크에서는 어떤 한 노드에서 문제가 발생했을 경우 그 노드에서 합의가 됐는데 단순히 응답에 오랜 시간이 걸리는 건지, 아니면 합의 과정에서 충돌이 발생해서 응답하지 않는 건지 알 수 없기 때문이다.

블록체인은 비동기 네트워크로 구동되며 따라서 블록체인 상에서는 이론상 완벽한 합의 알고리즘을 구현할 수가 없다.

Fault Tolerance*가 가능한 네트워크를 구축하기 위해선 safety와 liveness 중 어느 한 부분을 포기해야 한다.

*Fault Tolerance : 잘못이 허용된 네트워크에서도 프로토콜이 유효하게 동작함

 

이를 합의 알고리즘 트릴레마라고 한다.

 

 

합의 알고리즘의 트릴레마를 해결하지는 못하지만,

 

나름의 trade-off를 통해 탄생한 여러 알고리즘들이 있다.

CFT (Crash Fault Tolerance) : fault tolerance 포기
CFT는 분산시스템에서 노드가 비정상적인 충돌에 의해 문제가 생기더라도 나머지 시스템에서 서비스를 유지할 수 있게 하는 작동방식이다. 

하이퍼레저 패브릭과 같은 컨소시엄형 블록체인 시스템에서는 보통 조직들이 신원확인을 통해 허가를 받은 상태에서 참여하기 때문에 악의적인 행위를 하지 않을 거라는 신뢰가 형성되어 있다. 

 

따라서 특정 상황에 대한 노드 문제만을 염두에 둔 CFT 기반 알고리즘이 우선된다.

 

BFT (Byzantine Fault Tolerance) : liveness 포기
BFT는 더욱 복잡하고 악의적인 공격이 있을 수 있는 시스템에 적용된다.

 

비트코인의 경우 CFT, BFT 보다 높은 수준의 신뢰작업이 필요해 PoW 알고리즘을 사용한다.

 

PBFT(Practical Byzantine Fault Tolerance) 알고리즘: liveness 포기
비동기 네트워크에서 배신자 노드가 f개 있을 때, 총 노드 개수가 3f+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘이다.

단점은, 노드가 모든 노드에게 메시지 전달하고 합의 과정 이뤄내야 하기 때문에 통신량 기하급수적으로 늘어나기 때문에 public 체인에서 liveness를 구현하기 어렵다. 

 

 

나카모토 컨센선스(PoW): Safety 포기

51% 공격이 가능하기 때문에 safety의 위험이 있다.

 

 

트릴레마 외에도 기존 합의 알고리즘의 작동방식에는 다음과 같은 문제가 있다.

- 보상 시스템이 필요함에 따라, 마이닝이 필요하다.
- 블록 A,B에 대한 합의가 이뤄진 후 하나는 버려지게 되며, 이는 에너지 낭비로 이어진다.

개선된 알고리즘을 만들기 위해선 여기에 추가적으로 선례들에서 나온 다음과 같은 문제점도 개선해야 한다. 

- 완결성
- 51% 공격과 비잔틴 결함: liveness와 safety
- 트랜잭션 수수료

 

 

 

그렇게 나온 것이 코스모스의 텐더민트 합의 알고리즘이다.

 

 

텐더민트는 DPoS + PBFT 방식으로 작동한다. 

 

보상을 받기 위해 스테이킹된 노드 중 리더(validator)로 선발된 노드끼리 합의를 진행한다.

 

합의는 기본적으로 PBFT 방식을 따르며 3단계(Propose, Prevote, Precommit)에 걸쳐 이뤄진다.

 

또한 선 합의 후 블록을 생성하기 때문에 네트워크 낭비의 문제를 해결하였다.

 

하지만 그런 텐더민트에도 한계점이 존재한다.

 

바로 합의를 이루기 위해서는 한 노드에서 두 번 이상의 처리가 필요하고, 노드 참여자가 많아질수록 이는 기하급수적인 부하를 발생시킨다는 점이다.

 

PBFT 방식에서 트랜잭션 처리를 위한 커뮤니테이션 수

 

 

이러한 한계점 때문에 텐더민트 합의 알고리즘을 사용하는 코스모스는 노드가 늘어날수록 트랜잭션 처리가 줄어드는, 확장성의 문제에 직면해있다.

 

 

 

 

참고

합의 알고리즘 - Safety & Liveness와 PBFT, IBFT

Practical Understanding of FLP Impossibility for Distributed Consensus

텐더민트 합의에 3단계가 필요한 이유