비잔틴 장군 문제 (The Byzantine Generals Problem)란
고대 동로마 제국(비잔틴제국)을 비유한 분산 컴퓨팅 분야에서 예전
부터 풀지 못했던 시스템 문제 이다.
적군의 도시를 공격하려는 비잔티움 제국군의 여러 부대가 지리적
으로 떨어진 상태에서각 부대의 지휘관들이 전령을 통해 교신하면서 공격 계획을 세우는 상황을 가정하고 있다.
이 부대의 지휘관 중 일부에는 배신자가 섞여 있을 수 있고, 배신자는 규칙을 충실히 따르는 충직한 지휘관들과 달리 규칙에 얽매이지 않고 마음대로 행동할 수 있다.
충직한 지휘관들이 동일한 공격 계획을 세우기 위해서는 아래에 대한 문제를 해결 해야 한다.
- 공격을 성공 시키기 위해 충직한 지휘관들의 수가 얼마나 필요한가? (1/2이상, 51%)
- 이기려면 적병력보다 많은 병력이 동일 시각에 공격해야 함
- 이 지휘관들은 어떤 규칙을 따라 교신해야 신뢰된 전령을 받게 되는가?
- 전령에 풀기 어려운 문제를 제공(평균 10분)하여, 풀리면 이전 장군의 메시지와 함께 암호화 해서 전달
< PoW 작업 검증을 통한 해결 >
가. 5명의 장군(A, B, C, D, E)
나. 전령 암호화 생성 시간 10분
다. 암호화 시 10분이 걸렸다는 증표 포함 전달
- A장군은 B장군에게 9시 공격하는 계획을 암호화 하여 전달 한다. (10분 소요)
- B장군은 A장군의 암호문을 확인하고 즉시 푼다. (9시 공격 계획 확인)
- B장군은 A장군의 메시지 9시와 자신의 메시지 9시를 암호화 하여 C장군에게 전달 한다. (10분 소요)
- C장군은 B장군의 암호문을 확인하고 즉시 푼다. (9시 공격 계획 확인)
그러나, C장군은 배신자이므로 작전시간을 8시로 위조하고 암호화 하여 D장군에게 전달 하고자 한다.
하지만, 10분이라는 시간내 암호문을 풀어 내야 하고, 남은시간 동안 A장군, B장군 의 메시지도
변조 해야 하므로 불가능 - D 장군은 암호문을 확인하고, A장군이 B장군에게 9시 공격 계획한 메시지와 B장군이 C장군에게 9시
공격 계획을 전달 한것을 확인함 , 하지만 C장군의 메시지 확인 결과 8시로 변경된 것을 확인 - D 장군은 C장군이 위조한것을 확인하고 정상적인 9시 공격 계획을 암호화 하여 E장군에게 전달 한다.
- E장군은 10분 정도 걸려 풀어 (A, B, D 장군의 9시 공격 계획을 확인)
결론, C장군은 8시에 공격을 하지만 A, B, D, E 장군은 9시 공격을 수행하여 이기게 되고 C장군은 처형(=폐기)
* 위조 가능 조건 : 10분 보다 빠르게 암호화 하고 남은시간 내 A, B 장군 메시지를 모두 변조 해야 가능
비잔틴 장군의 문제를 PoW 를 통한 블록체인 기술로 활용한 예시이다.
블록체인은 이전 메시지(=이전블록)를 포함한 새로운 메시지(=블록)를 의미 하며,
포함된 이전 메시지를 변경할 경우 위조되었다는 사실을 바로 알수 있는 장부이다.
PoW 는 10분의 시간을 들여 메시지(블록)를 만드는 과정이며, 정말 10분이 걸렸는지 단번에
확인할수 있게 하는 방법을 제공한다.
PoW는 비잔틴 장군의 문제에 정확한 예시로 적절치 않으나(Consensus 생략),
블록체인 기술 中 작업 증명(PoW)이 비잔틴 장군 문제 (분산된 환경)를 어떻게 해야하는지 작성해봄