Safety & Liveness - FLP impossibility으로 보는 블록체인

블록체인이 유행하면서 블록체인의 수만큼 다양한 합의 알고리즘이 나오고 있다. 이는 어째서일까? 애초에 왜 다양한 블록체인이 나오고 있는 것일까? 이는 근본적으로 합의 알고리즘이 무엇을 할 수 있고 무엇을 할 수 없는가에서 기인한다. 좋은 합의 알고리즘은 무엇을 보장해야 할까?

FLP impossibility

우선 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안 된다. 다른 값을 합의했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생성됐다는 것이다. 이런 특성을 분산 시스템에서는 consensus의 safety라고 말한다.

또한, 합의가 언젠가는 이루어져야 한다. 분산 시스템에서 합의는 노드 간의 메시지를 주고받으며 각 노드의 상태를 변경시키며 이루어진다. 이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다. 모든 노드가 문제없이 합의를 할 수 있으면 이 시스템은 liveness가 보장된다고 말한다.

쉽게 풀어 말하면 safety는 "문제없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다"라는 것이고, liveness는 "문제없는 노드들은 반드시 합의를 한다"라는 것이다. 문제는 byzantine failure가 아닌 fail-stop failure가 하나만 있어도 safety와 liveness를 둘 다 만족하는 합의 알고리즘이 존재할 수 없다. 이를 FLP impossibility 혹은 FLP theorem이라고 한다. 따라서 합의 알고리즘을 선택한다는 것은 사실상 safety와 liveness 중 무엇을 선택하고 무엇을 버릴까 하는 문제이다.

Liveness over Safety

비트코인이 사용하는 합의 알고리즘은 사토시 나카모토가 처음 제안하였기 때문에 nakamoto consensus라고도 불린다. Nakamoto consensus는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 더 긴 체인을 만들 해시 파워만 있으면 언제든지 현재 합의된 블록을 다른 블록으로 대체할 수 있다. 이런 방식을 블록체인에서는 finality가 보장되지 않는다고 말하고 FLP impossibility에서는 liveness를 위해서 safety를 포기했다고 말한다.

Liveness를 중시하는 nakamoto consensus에서 출발한 합의 알고리즘들은 한정적인 상황에서 safety를 보장할 방법을 추가하는 방식으로 발전해갔다. 이더리움에서 구현되고 있는 Casper the Friendly Finality Gadget이 대표적이다. Casper는 기존의 PoW로 liveness를 보장하며 블록을 생성하지만 50 블록마다 투표하여 safety가 보장되는 지점을 만든다.

Safety over Liveness

이와 반대로 safety를 중시하는 합의 알고리즘도 있다. 전통적으로 분산 시스템에서 연구되던 PBFT에 기반한 BFT 계열 합의 알고리즘들이 이쪽에 속한다. Cosmos에서 사용하는 Tendermint가 대표적인 safety를 보장하는 BFT 알고리즘이다.

Tendermint는 하나의 라운드가 propose, prevote, precommit 3개의 단계로 나누어진다. 이 중 prevote와 precommit 스텝에서 각각 2/3+1개 이상 모아야 합의가 이루어진다. 합의에 2/3+1개 이상의 동의가 필요하기 때문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성되는 일은 없다. 하지만 전송한 메시지가 시간 안에 도달하는 것을 보장하지 못 하는 비동기 네트워크에서는 합의가 이루어지지 않아 블록이 생성되지 않을 수 있다. 따라서 liveness는 보장되지 않는다.

FLP impossibility가 증명했듯이 safety가 보장되는 경우 어떤 방법을 사용해도 비동기 네트워크에서 liveness를 보장할 수 없다. 그래서 BFT 계열에서는 다른 네트워크 모델에서 liveness가 보장됨을 증명한다.

비동기 네트워크 모델에서는 메시지가 전송되는 것이 보장되는 시간이 없다. 이는 메시지가 무한한 시간 후에 도착하는 것도 가정해야 하고 다시 말해서 전송한 메시지가 도착하지 않는 것을 가정해야 한다. 그렇다고 해서 정해진 시간 안에 메시지 전달이 보장되는 동기 네트워크 모델을 사용할 수는 없다. 이는 인터넷 규모의 네트워크에서는 비현실적인 가정이고, 이런 가정에서 liveness를 증명하는 것은 아무 의미 없기 때문이다. 그래서 tendermint는 정해진 시간 안에 메시지가 도달하는 것이 보장되지만 그 정해진 시간을 알 수 없다는 partial synchronous network model을 사용한다.

Partial synchronous network는 정해진 시간 내에 메시지가 도착하는 것이 보장되는 모델이다. 다만 이 정해진 시간이 무엇인지 노드는 알지 못한다. 이는 꽤나 현실적인 모델이다. 현실의 네트워크도 omission failure가 발생하지 않는 한 언젠가는 메시지가 도착하기 때문이다.

BFT 계열의 합의 알고리즘은 블록 생성을 위해 2번의 투표를 모아야 한다. 비록 partial synchronous network model에서는 언젠가 합의될 것이 보장되지만, 최악의 경우 몇번의 라운드 동안 새 블록이 생성되지 않는 경우도 생긴다. 이는 TPS 저하를 초래한다.

BFT 계열 알고리즘은 이런 문제를 해결하기 위한 방향으로 발전해왔다. 2018년 3월에 발표된 Hot-stuff이라는 프로토콜이 대표적이다. Hot-stuff에서 블록은 validator들의 투표를 포함한다. 이 투표를 commit-certificate(a.k.a. CC)이라고 한다. Hot-stuff은 기존의 BFT 계열의 알고리즘과 다르게 CC가 없는 블록도 생성될 수 있다. 그저 이 블록들은 finality가 보장되지 않을 뿐이다. 이 CC가 없는 블록들은 뒤에 CC가 있는 블록의 finality가 보장되면 그때 finality가 보장된다. 시간 당 블록 생성량을 올리기 위해서 safety를 어느 정도 포기하는 것이다.

마치며

이상으로 liveness의 극단에 있는 nakamoto consensus에서부터 safety에 극단에 있는 tendermint까지 블록체인에서 사용되는 다양한 합의 알고리즘을 알아봤다. 중요한 것은 safety와 liveness는 trade-off이지 둘 중 누군가가 더 우월한 특성은 아니라는 것이다. 자신이 구현하려는 서비스의 종류에 따라 safety와 liveness가 어느 정도 필요한지를 판단하여 알맞은 합의 알고리즘을 사용하는 블록체인을 선택해야 한다.