블록체인 - 완벽한 합의 프로토콜은 불가능?

블록체인에서 가장 중요한건 블록의 동기화를 이루는것이다 

 

이때 중요한건 합의 프로토콜이다

 

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

 

• Safety 
  • 시스템에 악의적인 일이 발생하지 않는다 
  • 모든 정상적인 참여자는 같은 상태에 동의해야 하고, 그 상태는 유효 해야한다 
  • 결과적으로 문제 없는 노드는 잘못된 합의를 하지 않는다
• Liveness
  • 시스템은 항상 살아 있어야한다 
  • 결국엔 어떤 상태에 동의 해야한다 
  • 모든 참여자는 동의한 상태에 도달해야한다
  • 결과적으로 문제 없는 노드는 반드시 합의 한다

하지만 분산 시스템에 위 두가지 속성을 만족시키기는 어렵다 

 

FLP Impossibility를 통해서 알아보자 

FLP는 1985년 피셔(Fischer), 린치(Lynch), 패터슨(Paterson)이 공동으로 만든 논문에서 나온 이론이다 

이는 비동기식 네트워크 환경에서 실패할 가능성이 있는 노드가 단 하나라도 있을 경우 'Safety', 'Liveness' 이 두 가지 속성을 모두 만족하는 합의 알고리즘은 존재할 수 없음을 증명하였다

 

이는 비동기 네트워크 특성상 통신 지연시간을 예측할 수 없어 특정 문제로 인해 노드가 작동에 실패한 것인지 아니면 단순히 네트워크 지연으로 인해 응답 시간이 오래 걸린 것인지 알 수 없기 떄문이다  

 

네트워크는 Synchronous Network, Asynchronous Network 구분 할수 있는데 

동기성 네트워크는 통신시 네트워크 정보 전파 시간을 조절가능한걸 의미하는데, 모든 노드들은 자신이 보낸 메시지에 도달하는 시간을 조절, 예측을 할수 있고 방해하는 어떤 경우의 지연도 일어 날수가 없음을 의미한다 

 

반대로 비동기성 네트워크는 메시지를 전송하고 전파하는 과정에서 네트워크의 정보 전파 시간을 예측할 수 없는 경우를 의미한다 

 

동기성과 비동기성을 중첩한 경우도 있는데 이경우도 비동기성 네트워크 환경에서 실패 가능성이 단 하나라도 있을 경우

'Safety', 'Liveness' 이 두 가지 속성을 모두 만족하기 힘들다고 한다 

(Paxos와 같이 궁극적으로 최종 합의가 되는 경우는 가능하지만, 시간의 범위가 정해진 경우는 불가능하다)

 

FLP Impossibility 에 따르면, 분산 네트워크는 다음 조건들을 만족한다고 가정을 했다

• Termination
  • 모든 동작하는 노드들은 언젠가는 어떤 값을 결정한다
• Agreement
  • 노드들은 모두 동일한 값을 결정한다
• Validity
  • 결정된 값은 어떤 과정을 통해 결정되어야 한다
  • 가령, 노드가 어떤 메시지를 받던 항상 0 의 값을 출력하는 알고리즘을 가지고 있다면 이를 만족시키지 못한다

 

FLP Impossibility 는 다음의 가정을 바탕으로 크게 두 가지로 정리하여 증명 한다

 

1. 비동기성 네트워크에서 노드의 합의는 결정성(Deterministic)을 가지지 않고, 노드의 실패 여부 등으로 인해 비결정성(Non-deterministic)을 가지게 된다
2. 1.의 정리를 바탕으로 아직 합의가 이루어지지 않은 상황은 무한히 합의가 이루어지지 않는 상황으로 이어지는 것이 가능하다

이는 합의가 발생하지 않을 수 있다는 의미이며

비동기성 네트워크에서는 합의가 보장되는 합의 알고리즘은 불가능하다는 것이다

다음의 증명 정리를 바탕으로 FLP 이론을 3 가지의 경우로 간단하게 정리할 수 있다

1. 증명에서 가정되는 합의는 결정성(Deterministic)을 가진다
2. 노드가 실패할 수 있는 환경은 결정성(Deterministic)을 가지지 않는 환경이다
3. 결정성(Deterministic)을 가지지 않는 환경에서는 어떠한 경우에도 결정성을 가질 수 없다

 

FLP Impossibility 에서는 다음과 같은 증명을 통해 비동기식 네트워크에서는 ‘Safety’와 ‘Liveness’를 모두 만족하며 합의하는 것은 불가능하다고 이야기한다.

 

블록체인에서는 이 FLP Impossibility 를 우회하기 위해 다음과 같은 방법을 이용한다.

• 합의를 재정의한다. (Liveness over Safety)
• 비동기성을 포기한다. (Safety over Liveness)

 

Liveness over Safety?

- 비트코인이 사용하는 합의 알고리즘은 사토시 나카모토가 처음 제안 

- 나카모토 컨센서스, 나카모토 합의 라고도 불림

- 나카모토 컨센서스는  언제나 더 어려운 문제를 푼 체인이 있으면, 그 체인을 유효한 체인으로 판단함 

- 즉, 지금 있는 체인보다 더 긴 체인을 만들 해시 파워만 있으면, 언제든지 현재 합의된 블록을 다른 블록으로 대체 가능 

- 이런 방식의 블록체인에서는 Finality(완결성) 보장되지 않는다고 말함 

- FLP 에서는 Liveness를 위해 Saftey를 포기했다고 말함 

 

Safety over Liveness?

- 전통적으로 분산 시스템에서 연구되던 PBFT 기반한 BFT 계열 합의 알고리즘들이 이쪽에 속한다 

- Cosmos에서 사용하는 Tendermint가 대표적인 Safety를 보장하는 BFT 알고리즘임 

 

Tendermint의 동작방식에 대해 알아보자면 

하나의 라운드가 Propose, Prevote, Precommit 3개의 단계로 나뉘어진다 

이중 Prevote와 Precommit 스텝에서 각각 2/3+1개 이상 모아야 합의가 이루어짐 

합의에 2/3+1개 이상의 동의가 필요하기 떄문에 어떤 상황에서도 서로 다른 두 블록이 동시에 생성 되는일은 없다

그러나 전송한 메시지가 시간안에 도달하는것을 보장하지 못하는 비동기 네트워크에서는 합의가 이루어지지 않아 블록이 생성 되지 않을수 있음. -> Liveness가 보장 X

 

이것은 FLP 이론에서 증명했듯이 Safety가 보장되는 경우엔 Liveness를 보장함을 증명 할 수 없다고 우린 알고있다

그래서 BFT에서는 Liveness를 다른 네트워크 모델을 사용해서 보장됨을 증명 한다 

 

Tendermint에서는 그래서 Partial Synchronous Network Model을 사용하는데 

이 모델은 정해진 시간안에 메시지가 도달하는 것은 보장되지만 그 정해진 시간을 알 수없다는 꽤나 현실적인 모델을 제시하고 사용합니다 

 

Partial Synchronous Network Model은 정해진 시간 내에 메시지가 도착하는 것이 보장되는 모델인데, 다만 정해진 시간이 무엇인지 노드는 알지 못합니다 하지만 omission Failure가 발생하지 않는 이상 언젠가는 메시지가 도착하기 떄문에 나름 현실적인 모델이라고 할수있습니다 

 

단점이라고 하면 

BFT 계열 합의 알고리즘은 블록 생성을 위해 2번 투표를 하는데, 그중 Partial Synchronous Network Model 에서는 언젠가 

합의될 것을 보장하지만, 최악의 경우는 몇 번의 라운드 동안 새 블록이 생성되지 않는 경우도 생겨 TPS 저하를 초래 하게 됩니다