이 글은 Byzantine Fault 문제에 대해 간략하게 제가 공부한대로 다뤄본 글입니다. 잘못된 부분에 대한 지적이나 글에 대한 코멘트, 그리고 스타벅스 아메리카노 기프티콘을 달게 받고 있습니다.

1. The Byzantine Generals Problem
2. Practical Byzantine Fault Tolerant algorithm (1)
3. Practical Byzantine Fault Tolerant algorithm (2)
4. Other BFT approaches, and Blockchain

옛날 이야기

옛날 옛적에 썩쥬 장군과 그의 부하들이 비잔티움 제국의 성을 공격하러 가고있었대요. 대충 썩쥬 장군과 n-1명의 부하들이 각각 전투력 100씩의 부대를 가지고 전투력 300짜리인 비잔티움 성을 함락시키려고 하고있습니다.

“너희들의 전투력 100, 나의 전투력 100, 합치면 우리의 전투력은 100n이다!” 라는 기적의 논리로, 썩쥬장군은 성을 함락시키려고 하고있습니다. 드디어 결전의 날 전날 밤입니다! 썩쥬장군은 결단을 내리고 모든 부하들에게 진군할지 퇴각할지 결정하여 서신을 보내야합니다. 그리고 부하들은 장군에게서 받은 서신을 다른 부하들에게도 돌릴겁니다.

하지만, 서신으로 모든 부하들의 합의를 이끌어낼 수 있을까요?

1. 서신을 보내던 병사가 비잔티움 제국 사람한테 들켜서 서신이 도착을 못 할 수도 있어요.
2. 썩쥬의 부하중 배신자가 있어서 자기 멋대로 행동해버릴 수 있어요.
3. 썩쥬의 부하중 배신자가 서신에 거짓말을 썼을 수도 있어요.

썩쥬장군은 골치가 아파요. 썩쥬장군은 다음을 보장할 수 있는 방법이 있으면 좋겠다고 생각했어요.

1. 배신자가 아닌 모든 부하들은 똑같은 행동을 할 것 (썩쥬장군도 통수칠 수 있습니다!)
2. 소수의 배신자가 껴있어도 배신자가 아닌 부하들이 썩쥬 장군이 내린 명령을 똑같이 이행할 수 있도록 할 것

위의 이야기는 L. Lamport의 The Byzantine Generals Problem[1]을 제 마음대로 각색한 것이고, Byzantine Generals Problem의 이해를 돕기 위한 이야기입니다.

BFT(Byzantine Fault Tolerance), in practice

그래서 이 문제 이야기를 갑자기 왜 꺼냈을까요? 분산시스템의 안전한 동작과 매우 큰 관련이 있기 때문입니다. 예를 들어 최근 뜨거운 감자로 떠오른 비트코인과 같은 암호화폐를 생각해봅시다. S. Nakamoto는 다음과 같은 문제를 비트코인에서 풀었다고 주장합니다.

비트코인 네트워크에 참여한 각 노드의 절반 이상이 정직하다면, 비트코인 네트워크를 이용해서 탈중앙화된 화폐를 만들 수 있다.

탈중앙화된 화폐를 만들었다는 것은 곧 Byzantine Generals Problem을 풀었다는 이야기가 됩니다. 비트코인 네트워크에 참여한 노드중 일부는 위/변조된 화폐를 이용하여 지불을 시도하거나, 이미 사용된 화폐를 다시 사용하려는 등의 거짓된 정보를 네트워크에 흘릴 수 있습니다. 그럼에도 불구하고 정직한 노드가 프로토콜을 충실히 따른다면 전체 네트워크에서 합의된 결론을 도출했다는 의미가 되겠죠.

이외에 분산시스템에서도 매우 중요한 의미를 가집니다. 단순한 장애가 아닌, 일부 노드가 해킹당해 정해진 프로토콜과 다르게 임의로 행동하는 상황을 생각합시다. 전체 분산시스템이 하나의 결과에 동의하지 못 하는 사태가 발생하고, 서비스 전체가 망가지는 결과를 초래할 수도 있습니다. 예를 들어, 일전에 소개한 Raft를 생각해봅시다. Raft는 해킹당한 노드가 갑자기 자기가 리더라고 주장하고 이상한 request를 다른 노드에 주장하는 상황은 고려하지 않습니다.

Lower Bound of BFT Consensus

3-Processor problem

3대의 프로세서 사이에 BFT한 합의를 도출하는 알고리즘은, 결론부터 말하자면 없습니다. Lamport는 [1]에서 이에 관해서는 증명이 상당히 많으며[2], 간단한 시나리오만을 언급하며 왜 3대의 프로세서가 있을 때 BFT 합의가 불가능한지를 보입니다. 아래는 그 시나리오입니다.

위 그림의 첫 번째 케이스는 부하중 한 명이 거짓말쟁이일 때, 두 번째 케이스는 썩쥬장군이 거짓말쟁이일 때를 나타냅니다. 거짓말쟁이를 제외한 나머지 두 정직한 노드는 똑같은 결론을 내릴 수 없게 됩니다. 부하 1의 입장에서 봤을 때, 공격할지 퇴각할지 결정을 못 하기 때문이죠.

Lower bound

위에서 보인 3대의 프로세서 사이의 BFT 합의가 불가능하다는 사실을 토대로, 최대 f개의 노드가 장애가 날 경우 필요한 노드의 개수는 최소한 3f+1개 이상이라는 것을 보이는 것은 쉽습니다. 3f개 이하의 프로세서들로 이루어진 클러스터들에서 합의가 된다는 것은 1개의 거짓말쟁이 노드와 2개의 거짓말쟁이 노드로 묶인 f개의 클러스터에서 정직한 노드들 또한 합의를 했다는 의미이기 때문입니다. 하지만 이는 위에서 말이 안 된다는 사실을 밝혔죠?

3줄 요약

1. Byzantine Generals Problem에 대해 간략하게 다뤘습니다.
2. 최대 f대의 서버가 동시에 실패할 수 있는 클러스터에서 BFT한 합의를 위해 필요한 최소 노드의 개수가 3f+1개인 것을 다뤘습니다.
3. 다음 글에서는 M. Castro가 1999년에 발표하고 여러 시스템에서 BFT한 합의를 위해 사용하고 있는 알고리즘인 pBFT 알고리즘에 대해 다룰 예정입니다.

Disclaimer

절대적으로 BFT한 합의 알고리즘이 BFT하지 않은 알고리즘보다 무조건 좋다는 생각은 하지 않습니다. BFT한 알고리즘은 그만큼 합의 과정이 복잡하여 합의 도출에 시간이 오래 걸릴 수 있고, 구현 또한 매우 어렵습니다. 각 알고리즘별로 가정하는 상황이 다르다는 것을 잘 알아둡시다.

References

[1] Lamport, L.; Shostak, R.; Pease, M. (1982). “The Byzantine Generals Problem”. ACM Transactions on Programming Languages and Systems. 4 (3): 382–401.

[2] Pease, M.; Shostak, R.; Lamport, L. Reaching agreement in the presence of faults. Journal of the ACM 27, 2 (Apr. 1980), 228-234.

이미지들은 직접 만든 이미지이거나 [1]의 figure를 가져왔습니다.