비잔틴 장애 허용(BFT)

위키백과에 정의된 비잔티움 장애 허용(BFT)

https://ko.wikipedia.org/wiki/%EB%B9%84%EC%9E%94%ED%8B%B0%EC%9B%80_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9

비잔티움 장애 허용(Byzantine Fault Tolerance)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티움 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래다.

이 분야의 연구는 비잔티움 장애(영어: Byzantine faults)라고 불리는 시스템에 생길 수 있는 임의의 장애를 견딜 수 있는 시스템을 만들기 위한 것이 목적이다. 이 비잔티움 장애는 단지 시스템이 멈추거나 에러 메시지를 내보내는 것과 같은 장애 뿐 아니라, 잘못된 값을 다른 시스템에 전달하는 등의 좀 더 그 원인을 파악하기 어려운 장애들까지 포함한다. 제대로 구현된 비잔티움 장애 허용 시스템에서는 미리 정해진 정도를 넘지않는 부분에서 어떠한 형태의 장애가 있더라도 정확한 값을 전달할 수 있다.

비잔티움 장군 문제비잔티움 장군 문제는 

레슬리 램포트와 쇼스탁, 피스가 공저한 1982년 논문에서 처음 언급됐다.^[1] 이 논문에서 저자들은 적군의 도시를 공격하려는 비잔티움 제국군의 여러 부대가 지리적으로 떨어진 상태에서 각 부대의 장군들이 (중간에 잡힐지도 모르는) 전령을 통해 교신하면서 공격 계획을 함께 세우는 상황을 가정하고 있다.

충직한 장군들은 합의된 규칙을 충실하게 따르며 이 외의 행동은 하지 않는다. 그러나 전체 장군 중 일부는 배신자일 수 있으며, 배신자는 규칙에 얽매이지 않고 마음대로 행동할 수 있다. 이 때 배신자의 존재에도 불구하고 충직한 장군들이 동일한 공격 계획을 세우기 위해서는 충직한 장군들의 수가 얼마나 있어야 하며, 장군들이 어떤 규칙을 따라 교신해야 하는지에 대한 문제가 비잔티움 장군 문제다.

사실 계획이 합리적인지도 판단한다면 더 좋으나, 이는 판단할 수 없으므로 포기하고, 오직 다수의 합의를 이끌어내는 것에만 초점을 맞춘다.

보장해야 하는 것은 아래와 같다.

1. 모든 충직한 장군들은, 같은 정보를 획득해야 한다. (누가 배신자인지 모르기 때문에, x번째 장군이 직접 보낸 메시지를 받았다 하더라도, 바로 사용할 수 없다.)
2. 만약 n번째 장군이 충직하다면, n번째 장군이 보낸 값은 충직한 장군들한테 같게 보내져야 한다.
   

PBFT(Practical Byzantine Fault Tolerance)

PBFT는 Byzantine Fault 모델로 Hyperledger Fabric과 Eris 등 컨소시엄형에서 이용하고 있는 블록체인 기반 기술에 많이 채택되고 있습니다.

PBFT는 네트워크의 모든 참여자를 미리 알고있어야 합니다. 참가자 1명이 프라이머리(Primary, 리더)가 되고 자신을 포함한 모든 참가자에게 요청을 보냅니다. 그 요청에 대한 결과를 집계한 뒤 다수의 값(2/3 합의)을 사용해 블록을 확정합니다. 

PoW나 PoS와는 달리 다수결로 의사결정한 뒤 블록을 만들기 때문에 블록체인의 분기가 발생하지 않습니다. 따라서 한 번 확정된 블록은 변경되지 않기 때문에 파이널리티를 확보할 수 있습니다. 또한 PoW와 같이 조건을 만족시킬 때까지 계산을 반복하지 않아도 되기 때문에 매우 고속으로 동작합니다.

부정 사용을 하고자 해도 과반수를 획득해야 하며 만약 프라이머리가 거짓말을 한다 해도 모든 참가자가 리더의 움직임을 감시해 거짓말이라고 판단한다면 다수결로 리더 교체를 신청할 수 있기 때문에 장애에 매우 강력한 내성을 지닌 알고리즘입니다.

하지만  참가자 전원과 의사소통을 해야 하기 때문에 참가자가 증가하면 통신량이 증가하고 처리량이 저하됩니다. PoW나 PoS는 수천개의 노드를 만들 수 있지만 PBFT는 수십개의 노드가 한계입니다.