BFT 프로토콜: PBFT와 Tendermint

1982년 Lamport, Shostak, Pease가 정식화한 비잔틴 장군 문제는 일부 참여자가 서로 모순되는 메시지를 보낼 때 분산 시스템이 합의에 도달할 수 있는지를 묻습니다. 이 문제의 이름은 공격을 조율해야 하지만 서로 충돌하는 명령을 보내는 배신자가 포함될 수 있는 비잔틴 장군들에서 유래했습니다. 전체 3f+1개 중 최대 f개의 악성 노드가 있어도 시스템이 올바른 합의에 도달하면 이를 비잔틴 장애 허용(BFT)이라고 합니다. BFT는 적대적 조건에서도 안전성을 요구하는 블록체인 합의의 표준으로 여겨집니다.

PBFT(Castro와 Liskov, 1999)는 최초의 실용적 BFT 프로토콜로, 실제 시스템에서 BFT를 효율적으로 운영할 수 있음을 보여 주었습니다. PBFT는 뷰(기간) 단위로 동작하며, 각 뷰에는 지정된 주 노드(지도자)가 있습니다. 정상 동작은 세 단계로 진행됩니다. 사전 준비 단계에서는 주 노드가 클라이언트 요청과 순서 번호를 브로드캐스트하고, 준비 단계에서는 복제본이 순서 정보와 함께 합의 내용을 브로드캐스트하며, 확정 단계에서는 복제본이 확정 확인을 브로드캐스트합니다. 복제본이 서로 일치하는 확정 메시지 2f+1개를 수집하면 요청이 실행됩니다. PBFT는 복제본의 1/3 미만이 비잔틴이라는 가정 아래 안전성과 생존성을 제공합니다.

PBFT의 주요 한계는 요청당 O(n^2)의 메시지 복잡도입니다. n개의 복제본이 준비 단계와 확정 단계에서 서로에게 메시지를 보내기 때문입니다. 복제본이 n=100개라면 요청 하나에서 대략 10,000개의 메시지가 발생합니다. 따라서 대규모 검증자 집합에는 PBFT를 사용하기 어렵습니다. BFT 연구 공동체는 20년에 걸쳐 이를 개선했습니다. BFT-SMART는 상수를 줄였고, HotStuff는 지도자 중계 모델을 통해 선형 메시지 복잡도를 달성했으며, 텐더민트는 공개 블록체인에 사용하도록 PBFT의 아이디어를 적용했습니다.

PBFT의 주 노드에 장애가 있다고 의심되면(시간 초과) 복제본은 뷰 변경을 시작합니다. 각 복제본은 이전 뷰에서 준비 완료된 값 등 자신의 상태를 담은 뷰 변경 메시지를 브로드캐스트합니다. 새 주 노드는 뷰 변경 메시지 2f+1개를 수집하고, 이전에 확정된 값과 상태 전환이 일관됨을 증명하는 새 뷰 메시지를 구성하여 브로드캐스트합니다. 뷰 변경에는 O(n^3)개의 메시지가 필요하므로 비용이 크며, 실제 운용에서 병목이 되었습니다. PBFT의 뷰 변경 인증서와 HotStuff의 연속 처리 설계 같은 최적화가 이를 해결합니다.

텐더민트(2014년, Kwon 작성; 2019년 코스모스에서 상용 운영)는 공개 블록체인 환경에 맞게 PBFT를 적용한 프로토콜입니다. 텐더민트는 블록마다 세 단계를 거칩니다. 제안 단계에서는 지도자가 제안 블록을 브로드캐스트하고, 사전 투표 단계에서는 검증자가 제안에 투표하며, 사전 확정 단계에서는 검증자가 사전 투표 2/3을 확인한 뒤 확정에 투표합니다. 검증자가 사전 확정 투표 2/3을 수집하면 블록이 확정됩니다(쿼럼 인증서). 검증자는 지분에 비례한 가중치를 적용하여 순환 순서로 제안자 역할을 번갈아 맡습니다. 확정 없이 라운드의 시간이 초과되면 검증자는 없음 투표와 함께 다음 라운드로 진행합니다.

텐더민트는 강한 안전성을 제공합니다. 지분의 1/3 미만이 비잔틴인 한 확정된 블록은 최종 상태가 되어 되돌릴 수 없습니다. 이는 동기식 최종성으로, 확정 후에는 분기가 발생하지 않습니다. 생존성을 위해서는 부분 동기식 네트워크가 필요합니다. 메시지 지연 시간이 제한되면 프로토콜은 계속 진행하지만, 지속적인 동기성을 요구하지는 않습니다. 안전성과 생존성 사이의 상충은 근본적입니다. 텐더민트는 안전성을 보장하기 위해 생존성을 희생하므로 네트워크가 분할되면 멈출 수 있지만, 비트코인 같은 체인은 생존성을 위해 안전성을 희생하여 일시적인 분기를 허용합니다.

텐더민트의 핵심 메커니즘은 투표 잠금입니다. 검증자가 라운드 r에서 블록에 사전 확정 투표를 보내면 해당 블록으로 잠깁니다. 이후 라운드에서 잠긴 검증자는 자신이 잠긴 블록에 대해서만 사전 투표를 할 수 있으며, 해당 블록이 확정되지 않았다는 증거를 받으면 없음 투표를 할 수 있습니다. 이를 통해 라운드 간 모순된 확정을 방지합니다. 검증자는 이후 라운드에서 다른 블록에 대한 폴카(사전 투표 2/3)를 받아 원래 블록이 확정되지 않았음을 증명해야만 잠금을 해제할 수 있습니다.

코스모스의 블록체인 간 통신(IBC)은 체인 간 전송을 위해 텐더민트의 즉시 최종성에 의존합니다. 텐더민트 경량 클라이언트는 검증자 집합과 최신 확정 정보(블록 헤더와 사전 확정 서명 2/3개)를 추적합니다. 체인 A에서 온 패킷을 검증하려면 체인 B의 IBC 모듈이 쿼럼 인증서를 검증하여 체인 A 검증자의 2/3가 해당 블록 헤더에 서명했는지 확인합니다. 따라서 IBC의 보안성은 텐더민트의 BFT 보장에 의존하며, 원본 블록이 확정되는 즉시 체인 간 전송이 최종 확정됩니다.

HotStuff(Yin 외, 2018년; 페이스북의 LibraBFT/DiemBFT의 기반이며 현재는 앱토스와 수이에 사용됨)는 별 모양 구조를 사용하여 합의 라운드당 O(n)의 메시지 복잡도를 달성합니다. 모든 검증자는 지도자에게 투표를 보내고, 지도자는 이를 임계값 서명(쿼럼 인증서)으로 집계한 뒤 쿼럼 인증서를 브로드캐스트합니다. HotStuff는 안전성 증명이 연속된 세 개의 쿼럼 인증서에 걸쳐 성립하는 3단계 연결 설계를 사용하여 연속 처리를 가능하게 합니다. 선형 복잡도 덕분에 HotStuff는 앱토스와 수이에서 배포된 것처럼 100~300명의 검증자에게 실용적입니다.

기업용 블록체인(하이퍼레저 패브릭, 베수, 쿼럼)은 검증자의 신원을 알고 있는 허가형 네트워크에서 BFT 합의를 사용합니다. 하이퍼레저 패브릭의 래프트 기반 순서 지정 서비스는 신뢰할 수 있는 컨소시엄에 충돌 장애 허용(CFT)을 제공하지만 비잔틴 장애는 처리하지 않습니다. 패브릭이 계획한 BFT 단계에서는 라이브러리 기반 구현인 SmartBFT를 목표로 합니다. R3 코다는 이중 지불을 방지하기 위해 BFT-SMART를 사용하는 공증인 클러스터를 사용합니다. BFT와 CFT 중 무엇을 선택할지는 신뢰 가정을 반영합니다. 검증자가 적대적으로 행동할 수 있으면 BFT가 필요하고, 단지 신뢰할 수 없을 뿐이라면 CFT로 충분합니다.

BFT를 이해하려면 BFT가 어떤 공격에 저항하고 어떤 공격에는 저항하지 못하는지 이해해야 합니다. BFT는 서로 다른 동료에게 모순된 메시지를 보내는 검증자와 충돌하거나 침묵하는 검증자를 처리합니다. 하지만 시빌 공격에는 대응하지 못합니다. 공격자가 가짜 신원을 만들어 검증자의 1/3을 통제하면 안전성을 무너뜨릴 수 있습니다. 이것이 공개 BFT 체인이 지분 증명 지분 가중치를 사용하는 이유입니다. 검증자 지분의 1/3을 확보하려면 실제 비용이 들므로 시빌 공격에 대한 저항성을 제공하기 때문입니다. 또한 BFT는 메시지가 결국 전달된다고 가정합니다(부분 동기성). 생존성 시간 제한보다 오래 지속되는 네트워크 분할은 체인을 멈출 수 있습니다.

안전성을 유지하면서 표준 BFT 프로토콜에서 비잔틴이 될 수 있는 검증자의 최대 비율은 얼마입니까?

BFT 프로토콜은 최대 1/3의 악성 검증자가 있어도 합의를 보장합니다. PBFT(1999년)는 BFT가 실용적임을 증명했지만 O(n^2)의 메시지 복잡도를 가집니다. 텐더민트는 즉시 최종성과 투표 잠금을 갖추도록 PBFT를 블록체인에 적용했습니다. HotStuff는 임계값 서명 쿼럼 인증서를 통해 O(n)의 복잡도를 달성하며 앱토스와 수이에서 사용됩니다. 코스모스 IBC는 검증된 체인 간 전송을 위해 텐더민트의 즉시 최종성을 사용합니다. 기업용 블록체인은 비잔틴 장애가 예상되는지 아니면 단순한 충돌 장애가 예상되는지에 따라 BFT-SMART 또는 래프트를 사용합니다.