1. FLP Impossibility

Fischer, Lynch, Paterson Impossibility

어떤 합의 알고리즘이 네트워크에서 통용되기 위해서는 Safety와 Liveness라는 특성을 갖고 있어야 합니다.
그동안 컴퓨터과학의 분산환경에서 합의 알고리즘을 설계할 땐, Safety를 Liveness보다 우선하도록 설계했습니다. 네트워크 내에서 모든 거래를 전부 합의하지는 못할지라도, 일단 합의된 거래는 네트워크 내에 있는 모두에게 동일한 값으로 제공되는 것이 더 중요하다고 보았기 때문입니다. 그래서 Safety를 충족하는 상황에서 어떻게 하면 Liveness의 손실을 최소화하는 지에 대한 것이 주된 고민이었습니다.
그런데 비트코인의 합의 알고리즘은 모든 거래를 가감없이 수용하는 구조를 채택하여 liveness를 극대화하고, 하드포크가 발생할 경우 "최장 길이 체인 선택 알고리즘"을 활용해 safety 문제를 보완했습니다. 그리고 블록이 쌓일수록 변경이 사실상 불가능해지는 구조를 활용해 "확률적으로" safety(블록체인 용어로 finality)를 확보했습니다.
하지만, 어디까지나 safety를 확률적으로 확보하는 것이기 때문에 51% 공격과 같은 네트워크 공격이 성공할 경우, safety를 보장할 수 없다는 단점을 안고 있습니다. 비트코인은 블록의 finality를 확률적으로 보장한다는 의미와 동일한 맥락입니다.
그런데, 비동기 네트워크 내에서 safety와 liveness를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것이 불가능하다는 것이 증명되었습니다. 이 증명을 FLP Impossibility라고 합니다. 비동기 네트워크에서는 합의 문제를 완벽히 해결할 수 있는 분산 알고리즘이 없다는 것을 증명했습니다. 관련된 논문은 참고자료의 Impossibility of Distributed Consensus with One Faulty Process를 참고하기 바랍니다. 비동기 네트워크에서는 어떤 한 노드에서 문제가 발생할 경우 그 노드에서 합의가 됐는데 단순히 응답에 오랜 시간이 걸리는 건지, 아니면 합의 과정에서 충돌이 발생해서 응답하지 않는건지 알 수 없기 때문입니다.

liveness: 실패하지 않은 모든 노드는 최종적으로 결정합니다.
safety: 결정하는 모든 노드(결정 후 실패한 노드 포함)는 동일한 값을 결정해야 합니다. 모든 노드가 동일한 초기 입력을 갖는다면 그 값이 유일하게 가능한 결정 값이어야 합니다.
fault tolerance: 모든 노드는 프로토콜이 노드 오류의 경우에도 유효해야 함을 요구합니다.

(cf) 비동기식 네트워크 모델에서 FLP Impossibility는 termination(liveness), agreement(safety), fault tolerance의 3가지 속성을 모두 달성할 수 없다고 주장합니다.

2. PBFT 합의 알고리즘

비동기성 모델에서 Safety를 확보하고 Liveness를 일부 희생하면서, 투표를 통해 합의가 이뤄진 블록만 생성합니다. (liveness를 희생하지 않는다면 어떤 상황에서도 블록이 생성되어야 합니다.) 비동기 네트워크에서도 합의를 이룰 수 있는 알고리즘이 바로 Practical Byzantine Fault Tolerance입니다. 네트워크에 배신자 노드가 어느 정도 있다고 가정하고 네트워크 내에서 이루어지는 합의의 신뢰를 보장하는 알고리즘입니다. 블록체인 합의 알고리즘 중 BFT 방식을 채택했다고 하는 경우, 대부분 PBFT 합의 알고리즘을 바탕으로 조금씩 변형된 것입니다.
하이퍼렛저가 대표적인 PBFT 합의 알고리즘을 사용합니다. 클레이튼도 비슷하지만, 허가된 노드들만 운영이 가능한 유사 DPoS 방식입니다.
Tendermint = PBFT + DPoS

배신자 노드가 f개 있을 때, 총 노드 갯수가 3f+1개 이상이면 해당 네트워크에서 이뤄지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘입니다. prepared certificate와 commit certificate를 거쳐서 reply로 가게 됩니다.

BFT에서 N = 배신자를 포함한 전체의 노드 수
F = 배신자의 수
N-F = 정직한 노드 수

가정)
메시지 안전성을 위해서 N-F>F를 만족해야 합니다.
다수결의 원칙인 비트코인이 PoW를 따르는 원칙과 같습니다. 즉
N > 2F를 따르고, N >= 2F+1의 공식을 따를 수 있습니다.(50%까지 내구성)
그러나 F도 메시지를 생성하기 때문에, N-2F>F를 만족해야 합니다.
즉 N > 3F를 따르니까, N >= 3F+1을 얻을 수 있습니다. (PBFT)

safety는 충족하지만, liveness를 희생했습니다.

참고자료
FLP Impossibility
https://levelup.gitconnected.com/practical-understanding-of-flp-impossibility-for-distributed-consensus-8886e73cdfe5
Impossibility of Distributed Consensus with One Faulty Process
https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf
PBFT 합의 알고리즘
https://steemit.com/consensus/@kblock/48-pbft-consensus-algorithm