Network model
Consensus algorithm을 구현할 때 고려해야 하는 network model에 대해서 알아보자.
블록체인 또는 분산 시스템에서는 네트워크 모델이라고 하는 노드가 서로 대화하는 설정을 정의해야 한다.
서로 다른 프로토콜은 작동하도록 설계된 환경에 따라 서로 다른 네트워크 모델을 채택한다.
메시지를 삭제하고 임의의 메시지 지연을 유발할 수 있는 불안정한 네트워크에서 잘 작동하도록 설계된 모델도 있고 인트라넷과 같이 매우 안정적인 채널에 최적화된 모델도 있다.
Safety, liveness
어떤 합의 알고리즘이 네트워크에서 통용되기 위해서는 safety, liveness라는 특성을 가지고 있어야 한다.
Safety
노드 간 합의가 발생했다면 어느 노드가 접근해도 그 값은 동일해야 한다. 다른 값을 합의 했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생겼다는 것이다.
블록체인의 finality와 동일한 개념이다.
Liveness
합의 대상에 문제가 없다면 네트워크 내에서 반드시 합의가 이루어진다라는 특징이다.
분산 시스템에서 합의는 노드 간의 메시지를 주고받으며 각 노드의 상태를 변경시키며 이루어진다. 이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다.
FLP impossibility
비동기 네트워크에서 비잔틴 노드가 아닌 한 노드에 문제가 생겼을 때 합의에 이를 수 없다는 개념이다.
비동기 네트워크 내에서 safety와 liveness를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것은 불가능하다.
비동기 네트워크에서는 어떤 한 노드에서 문제가 발생했을 경우 그 노드에서 합의가 됐는데 단순히 응답이 오래 걸리는 건지, 합의 과정에서 충돌이 발생해서 응답하지 않는 건지 알 수 없기 때문에 생기는 문제이다.
동기 모델 (Synchronous model)
Time bound Δ가 있어서 모든 메시지가 Δ안에 도착하는 것이 보장된다.
모든 메시지는 미리 결정된 시간 내에 전달 되어야 하고 모든 참여자는 메시지 전달에 걸리는 시간을 알고 있다.
동기 모델을 가정한 합의 알고리즘의 예로는 비트코인의 PoW가 있다. 비트코인은 10분 안에 네트워크에 연결된 모든 노드에 블록이 도착한다는 전제 하에 합의 알고리즘이 설계되어있다. Liveness는 보장되지만 safety는 보장되지 않는 것이다. Safety가 보장되지 않기 때문에 비트코인은 블록이 동시에 여러개 생성될 수 있고 2, 3 블록이 지난 후에야 완전히 블록을 확정할 수 있다.
비동기 모델 (Asynchronous model)
메시지가 정해진 시간 내에 도착한다는 보장이 없다. 하지만 메시지가 언젠가 도착한다는 보장은 있다.
장점
네트워크 지연에 대해 아무런 전제도 하지 않기 때문에 훨씬 견고한 합의 알고리즘을 설계할 수 있다.
실제 네트워크의 속도에 비례해 합의를 진행할 수 있다.
단점
알고리즘이 복잡하고 속성을 증명하기 어렵다.
합의 자체가 불가능한 경우가 생긴다. (FLP impossibility)
단 하나의 노드라도 fail-stop하면 합의가 불가능하다.
Fail-stop : 단순히 노드가 고장나서 멈추는 형태의 오동작.
Byzantine-fault : 악의적인 행동을 포함하여 임의의 동작을 할 수 있는 것.
부분 동기 모델
부분 동기 모델은 네트워크가 동기 상태와 비동기 상태를 번갈아 오간다고 가정한다.
네트워크에 GST(Global Stabilization Time)라는 이벤트가 있는데 GST가 언제 일어날지는 알 수 없지만 일단 일어나고 나면 정해진 시간 내에 모든 메시지가 도착한다.
GST 이전에는 비동기 모드로 있다가 GST 이후에 동기 모드가 된다고 생각할 수 있다.
노드 입장에서는 언제 GST가 일어났는지는 모른다.
네트워크가 비동기인 상태에서도 항상 safety를 보장하고 동기 모드가 되면 liveness를 보장한다. BFT 계열의 합의 알고리즘은 대부분 부분 동기 모델을 가정하고 있다.
예시
블록체인이 구동되는 네트워크는 비동기 네트워크이다. 비동기 네트워크에서 Safety와 Liveness를 동시에 완벽히 만족하는 합의 알고리즘은 설계할 수 없다.
비트코인은 동기 네트워크를 가정하여 Liveness를 만족하고 Safety를 어느 정도 포기했다.
이더리움은 평균 15초의 블록생성 시간을 가지는 동기 네트워크를 가정한 프로토콜을 사용한다.
텐더민트는 부분 동기 네트워크를 가정하여 Safety를 만족(One block finality)하고 Liveness는 일부 희생했다. 비트코인과 이더리움처럼 Time bound가 설정되지만 시스템 매개변수가 아닌 실제 네트워크의 속도에 따라 결정된다.
Reference
Last updated
