Safety 그리고 Liveness

 

💡Safety와 Liveness

합의 프로토콜은 다음의 두 속성을 만족시켜야 한다.

 

Safety: 시스템에 나쁜 일이 발생하지 않는다는 의미이며, 모든 정상적인 참여자는 같은 상태에 동의하여야 하고 그 상태는 유효해야 한다. 다시 말해, 문제없는 노드는 잘못된 합의를 하지 않는다는 의미이다.

Liveness: 시스템은 항상 살아있어야 한다는 의미이며, 결국에는 어떤 상태에 동의하여야 하고, 모든 참여자는 동의한 상태에 도달해야 한다. 다시 말해, 문제 없는 노드는 반드시 합의한다는 의미이다.

 

✓ FLP Impossibility

 

우선 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안 된다. 다른 값을 합의했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생성됐다는 것이다. 이런 특성을 분산 시스템에서는 합의의 Safety 라고 말한다. 합의는 언젠가 이루어져야 한다. 분산 시스템에서 합의는 노드 간의 메시지를 주고 받으며 각 노드의 상태를 변경시키며 이루어진다. 이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다. 모든 노드가 문제없이 합의를 할 수 있으면 이 시스템은 Liveness가 보장된다고 말한다. 쉽게 풀어 말하면 Safety는 문제 없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다는 것이고, Livenes는 문제없는 노드들은 반드시 합의한다는 것이다. 문제는 Byzantine Failure가 아닌 Fail-stop Failure가 하나만 있어도 Safety와 Liveness를 둘 다 만족하는 합의 알고리즘이 존재할 수 없다. 이를 FLP Impossibility 혹은 FLP Theorem이라고 한다. 따라서 합의 알고리즘을 선택한다는 것은 사실상 Safety와 Liveness 중 무엇을 선택하고 포기할지의 문제이다.

 

 

✓ Liveness over Safety

 

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

 

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

 

* 블록체인 설정에서 완결성은 일단 블록체인에 커밋되면 잘 구성된 모든 블록이 취소되지 않는다는 확인이다. 사용자는 거래할 때 거래가 완료되면 거래를 임의로 변경하거나 되돌릴 수 없다는 확신을 원한다. 따라서 블록체인 합의 프로토콜을 설계할 때 최종성이 중요하다. 현재, 나카모토 합의 기반 시스템에서 51% 공격과 이기적 채굴은 블록 취소 가능성을 허용하여 시스템의 건강을 위협한다. 이러한 프로토콜은 확률적 최종성을 제공하는 반면 다른 프로토콜은 절대적 최종성을 보장할 수 없다.

 

 

✓ Safety over Safety

 

safety를 중시하는 합의 알고리즘도 있다. 전통적으로 분산 시스템에서 연구되던 PBFT에 기반한 BFT 계열 합의 알고리즘들이 이 쪽에 속한다. Cosmos에서 사용하는 Tendermint가 대표적인 Safety를 보장하는 BFT알고리즘이다. BFT는 Byzantine Fault Tolerance이며, 이 알고리즘은 컴퓨터 시스템의 상태이며, 특히 분산 컴퓨팅 구성 요소가 실패할 수 시스템, 불완전한 거기 구성 요소가 실패했는지에 여부에 대한 정보이다.

 

Tendermint는 하나의 라운드가 Propose, Prevote, Precommit 3개의 단계로 나누어진다. 이 중 Prevote와 Precommit스텝에서 각가 2/3 + 1개 이상 모여야 합의가 이루어진다. 합의에 2/3 + 1개 이상의 동의가 필요하기 때문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성되는 일은 없다. 하지만 전송한 메시지가 시간 안에 도달하는 것을 보장하지 못하는 비동기 네트워크에서는 합의가 이루어지지 않아 블록이 생성되지 않을 수도 있다. 따라서 Liveness는 보장되지 않는다. FLP Impossibility 가 증명했듯이 Safety가 보장되는 경우 어떤 방법을 사용해도 비동기 네트워크에서 Liveness를 보장할 수 없다. 그래서 BFT 계열에서는 다른 네트워크 모델에서 Liveness가 보장됨을 증명한다.

 

비동기 네트워크 모델에서는 메시지가 전송되는 것이 보장되는 시간이 없다. 이는 메시지가 무한한 시간 후에 도착하는 것도 가정해야 하고 다시 말해서 전송한 메시지가 도착하지 않는 것을 가정해야 한다. 그렇다고 해서 정해진 시간 안에 메시지 전달이 보장되는 동기 네트워크 모델을 사용할 수는 없다. 이는 인터넷 규모의 네트워크에서는 비현실적인 가정이고, 이런 가정에서 Liveness를 증명하는 것은 아무 의미가 없기 때문이다. BFT 계열의 합의 알고리즘은 블록 생성을 위해 2번의 투표를 모아야 한다. 비록 Partial Synchronous Network Model에서는 언젠가 합의될 것이 보장되지만, 최악의 경우 몇 번의 라운드 동안 새 블록이 생성되지 않는 경우도 생긴다. 이는 TPS 저하를 초래한다.

 

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