비잔틴 장군 문제
Last updated
Last updated
이라고 하면 모두가 이 기술이 매우 신비하다고 느끼는 것 같습니다. 오늘은 블록체인의 분산 일관성 문제를 기술적인 관점에서 분석해 보겠습니다.많은 연구자들은 이 문제를 분산 분야의 유령이라고 부르는데, 이는 누구나 흔히 듣는 비잔틴의 일반적인 문제입니다.
비잔틴 장군 문제는 Leslie Lamport가 제안한 분산 P2P 네트워크의 통신 내결함성 문제입니다.
Leslie Lamport는 자신의 논문 The Byzantine Generals Problem: 한 그룹의 비잔틴 장군이 군대를 이끌고 도시를 포위했습니다. 문제를 단순화하기 위해 각 군대의 행동 전략은 공격 또는 철수로 제한됩니다. 일부 부대는 공격하고 일부 부대는 후퇴하면 재앙이 될 수 있기 때문에 장군들은 투표를 통해 모든 부대를 공격하거나 모든 부대가 함께 철수하는 전략에 동의해야 합니다. 장군들은 도시의 다른 방향에 있었기 때문에 메신저를 통해서만 서로 통신 할 수있었습니다. 투표 과정에서 각 장군은 메신저를 통해 다른 모든 장군에게 개별적으로 자신이 공격하거나 퇴각하기로 투표했음을 알립니다. 공통 투표 결과를 보고 행동 전략을 결정합니다.
통신 용어로 비잔틴 장군 문제를 설명하십시오. 신뢰할 수 있는 컴퓨터 시스템은 시스템의 다른 부분에서 가져온 정보와 충돌할 수 있는 결함 있는 구성 요소를 처리해야 합니다[1]. 메시지를 전혀 보내지 않고 다른 이웃에게 서로 다른 잘못된 메시지를 보내고 자신의 입력 값에 대해 거짓말을 합니다.[2]. 신뢰할 수 있는 컴퓨터 시스템은 하나 이상의 구성 요소 오류를 처리할 수 있어야 합니다. 실패한 구성 요소는 무시된 동작을 보여 시스템의 나머지 부분에 일관되지 않은 정보를 보냅니다.
분산 컴퓨팅에서는 서로 다른 컴퓨터가 통신 정보를 교환하여 합의에 도달하고 동일한 협업 전략 세트에 따라 행동합니다. 그러나 때때로 시스템의 구성원 컴퓨터는 오류로 인해 잘못된 정보를 보낼 수 있으며 정보를 전송하는 데 사용되는 통신 네트워크도 정보 손상을 초래할 수 있으므로 네트워크 구성원이 전체 협력 전략에 대해 서로 다른 결론에 도달하여 파괴 시스템의 일관성 섹스.
비잔틴 장군 문제는 전제 조건이 있는데, 메시지가 손실되는 신뢰할 수 없는 채널에서 메시지 전송을 통해 일관성을 달성하는 것은 불가능하므로 일관성 연구의 일반적인 가정은 채널이 신뢰할 수 있다는 전제에 구축하는 것입니다. 비잔틴 장군 문제의 핵심은 소수의 노드가 악을 행하도록 허용되었을 때 합의에 도달하는 방법의 문제입니다(메시지가 위조될 가능성이 있음).
비잔틴 장군 문제는 실제로 특정 조건에서 분산 시스템을 일관되고 올바르게 유지하는 방법의 문제입니다. 다음 2가지 조건을 만족하는 알고리즘으로 추상화할 수 있습니다.
조건 IC1. 충성스러운 모든 장군은 동일한 작전 명령을 내리고 명령을 실행하며(일반 처리 장치는 동일한 입력 값을 사용해야 함) 명령 일관성을 유지합니다.
조건 IC2.만약 충성스러운 장군이 전투 명령을 내리면 모든 충성스러운 장군은 그 장군이 내린 전투 명령을 따를 것입니다(입력 유닛이 정상이면 각 일반 유닛은 입력으로 제공하는 값을 사용해야 함). 특정 조건.
Leslie Lamport의 논문에서 Byzantine Generals Problem은 구두 메시지와 서명된 메시지의 두 가지 솔루션을 언급하며 알고리즘은 다음과 같습니다.
결론: 반군이 m인 경우 구두 합의 알고리즘(약칭 OM 알고리즘)이 "비잔틴 장군 문제"를 해결할 수 있도록 하려면 최소 3m+1 장군(배신 및 충성 장군 포함)이 있어야 합니다.
가정:
A1. 전송된 모든 메시지가 올바르게 전달될 수 있습니다.
A2 메시지 수신자는 메시지를 보낸 사람을 알고 있습니다.
A3. 누락된 메시지를 알 수 있음(반군이 메시지 전송에 협력하지 않으면 알고리즘은 기본값으로 대신 "후퇴")
증명 과정:
결론: 얼마나 많은 반군이 있더라도 충성스러운 장군은 같은 입장을 유지합니다.
가정:
A1. 전송된 모든 메시지가 올바르게 전달될 수 있습니다.
A2 메시지 수신자는 메시지를 보낸 사람을 알고 있습니다.
A3. 누락된 메시지를 알 수 있음(반군이 메시지 전송에 협력하지 않으면 알고리즘은 기본값으로 "retreat" 값을 대신 설정함)
A4.1 서명은 위조될 수 없으며, 일단 변조되면 찾을 수 있습니다.
A4.2 장군 서명의 진위 여부는 누구나 확인할 수 있습니다.
증명 과정:
