블록체인, 비잔틴 장군 문제(Byzantine Generals Problem)란?

 

비잔틴 장군 문제(Byzantine Generals Problem)란?

여러 장군들이 도시를 공격할지 아니면 철수할지에 대한 의사를 결정해야 하는 상황으로 가정합니다. 그러나 장군들은 서로 다른 위치에 있고, 오직 메신저를 통해서만 의사를 전달할 수 있습니다. 게다가 일부 장군들은 신뢰할 수 없는 배신자일 수 있습니다. 이 경우에는 모든 장군들이 동의하여 하나의 행동을 취해야 하는데, 배신자가 정보를 조작하거나 장군들 사이의 통신을 방해할 수 있습니다.

 

비잔틴 장군 문제의 목표는 신뢰할 수 없는 장군들이나 메신저가 있는 상황에서도 모든 정직한 장군들이 동일한 결정을 내릴 수 있도록 하는 것입니다.

 

모든 장군의 메시지가 모두 손실없이 정확하게 전달되어야 한다는 가정에서

100명의 병사를 가진 5명의 장군이 300명의 병력을 가진 하나의 성을 공격하는 상황을 가정한다면, 기본적으로 300명 보다 많은 병력이 일제히 공격해야 되기에 4명의 장군이 공격을 일제히 해야한다.

 

문제를 해결하기 위해서 다수결을 통한 결과 도출방식을 선택하게 된다면, 장군들은 철저히 다수결을 통해 과반이 이상되는 공격 시간을 선택해 공격을 할 때 배반한 장군의 수가 전체 장군의 수에서 1/3이 넘지 않는 경우 공격에 성공할 수 있다 라는 결론을 내릴 수 있습니다.

 

 

Byzantine Generals Problem 해결책을 적용한 시스템 사례

• Draper's FTP
• Honeywell's MMFCS
• SRI's SIFT
• PoW, Proof of Work
• pBFT, practical Byzantine Fault Tolerance

 

 

Byzantine Generals Problem

비잔틴 장군 문제는 1982년에 램포트(Lamport)와 쇼스탁(Shostak), 피스(Pease)가 작성된 논문에서 처음으로 제시하였습니다.

 

Byzantine Generals Problem 원문 문서

byz.pdf

1.19MB