비잔틴 결함 허용

비잔틴 결함 허용은 일부 프로세스가 충돌하거나 악의적인 메시지를 보내는 등 임의로 실패할 수 있는 상황에서 합의에 도달하는 것에 대한 연구입니다.

Definition

비잔틴 결함은 악의적인 행동을 포함하여 구성 요소의 사양에서 임의로 벗어나는 것을 의미합니다. 비잔틴 결함 허용은 제한된 수의 이러한 결함이 있는 참여자에도 불구하고 분산 프로토콜이 정확성 조건을 충족하는 능력입니다.

Scope

이 주제는 비잔틴 장군 문제와 그것이 설정하는 엄격한 복원력 한계(f개의 임의 결함을 허용하기 위해 최소 3f+1개의 프로세스 또는 서명된 메시지), 동기식 구두 및 서명 메시지 합의 알고리즘, 그리고 PBFT 및 그 후손과 같은 실용적인 비동기식 비잔틴 결함 허용 프로토콜을 다룹니다. 이는 허가형 블록체인 및 고신뢰 복제 서비스의 신뢰 모델의 기반이 됩니다.

Core questions

• 주어진 수의 임의 결함을 허용하기 위해 얼마나 많은 올바른 프로세스가 필요한가?
• 디지털 서명은 비잔틴 합의의 복원력 한계를 어떻게 변화시키는가?
• 실용적인 비동기 시스템에 충분히 효율적인 비잔틴 합의를 어떻게 만들 수 있는가?

Key theories

비잔틴 장군 한계

인증되지 않은(구두) 메시지를 사용하는 경우, 비잔틴 합의는 프로세스의 3분의 2 이상이 올바른 경우에만 해결 가능합니다(n > 3f). 위조 불가능한 서명이 있는 인증된 메시지는 이 요구 사항을 완화합니다.

실용적인 BFT 복제

PBFT는 비잔틴 합의가 프라이머리와 3단계 프로토콜을 사용하여 상태 기계 복제와 함께 부분적으로 동기화된 시스템에서 실행될 수 있음을 보여주며, 최대 3분의 1의 결함 있는 복제본을 허용하면서 실용적인 성능을 달성합니다.

동기식 합의 알고리즘

동기식 모델에서 재귀적 구두 메시지 및 서명 메시지 알고리즘은 f+1 라운드에서 합의를 달성하며, 임의 결함을 허용하는 라운드 복잡성 비용을 보여줍니다.

Clinical relevance

비잔틴 결함 허용은 단순히 충돌뿐만 아니라 손상 또는 악의적인 행동에도 견뎌야 하는 시스템의 기반입니다. 여기에는 허가형 블록체인, 고신뢰 복제 서비스, 그리고 임의의 구성 요소 오류를 배제할 수 없는 항공전자 및 항공우주 제어 시스템이 포함됩니다.

History

Pease, Shostak, Lamport는 1980년에 합의 한계를 설정하고 1982년에 이를 비잔틴 장군 문제로 극화했습니다. 거의 20년 동안 비잔틴 합의는 실용화하기에는 너무 비용이 많이 드는 것으로 간주되었으나, 1999년 Castro와 Liskov의 PBFT가 효율적인 비동기식 비잔틴 복제를 시연하면서 이 분야를 부활시켰고, 이후 블록체인 합의에 영향을 미쳤습니다.

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

f개의 비잔틴 결함을 허용하기 위해 3f+1개의 프로세스가 필요한 이유는 무엇입니까?

올바른 프로세스는 f개의 결함 있는 프로세스가 거짓말을 하고 다른 f개의 프로세스가 느리거나 도달할 수 없는 경우에도 다수결 결정을 내려야 합니다. 결함이 있고 지연되는 참여자의 조합보다 올바른 다수가 항상 더 많은 표를 얻으려면 결함 있는 프로세스 수의 세 배 이상이 필요합니다.