안녕하세요 tmkor입니다. 비잔틴 장애 허용(BFT)은 여러대의 노드로 구성되는 분산환경에서 비정상 노드가 존재하더라도 정상 작동하도록 하는 기법입니다. 분산컴퓨팅 영역에서 발전하였으며, 최근 블록체인의 핵심요소로 자리잡고 있습니다. 특히 비공개 블록체인(private blockchain)의 경우 BFT 기반의 알고리즘이 주로 사용됩니다. 이번 글에서는 BFT에 대한 이해를 돕기 위해 BFT가 무엇인지에 대한 유튜브 영상을 정리하여 보았습니다.
- 분산환경의 장애(failure)는 크게 2가지로 분류 가능.
- fail-stop : 노드가 멈춘 것
- 비잔틴 장애
- 비잔틴 장애란?
- 이상한 메시지(conflict message)를 보내는 배신자 노드가 존재하는 경우
- 원인 : Flaky node (잠수타는 애), Malicious node (이상한 메시지를 보내는 애)
- BFT 사용 예시
- 2명의 장군 문제 [문제편]
- 2명의 장군이 공격을 할지 퇴각을 할지 합의를 이루는 문제
- 파발을 통해서 메시지를 전달하는데, 파발이 적국을 지나야 하기 때문에 메시지가 전달이 될 수도, 안 될 수도 있음
- 합의를 이루는 프로토콜을 어떻게 설계할 수 있는가?
- 2명의 장군 문제 [해메는편]
- TCP/IP의 핸드쉐이크와 유사한 전략을 사용해보자
- A ---[SYN]---> B
- A <-[SYN+ACK]- B
- A ---[ACK]---> B
- 3번째 메시지가 유실될 때가 문제
- 메시지를 아무리 추가해도, 마지막 메시지에서 inconsistent state가 발생하므로 이런 전략으론 해결 불가함
- 완벽하게 비잔틴 문제를 해결할 수는 없음
- 현실 상황을 고려해서 문제를 완화해야 함
- Practical
- 예를 들어 모든 메시지가 유실되는게 아니라 일정 확률에 따라 유실된다던지..
- 하나의 메시지를 100명의 파발을 보내서 하나만 도착해도 된다던지.. 뭐 그러합니당
- 비잔틴 장군 문제에서 알고자 하는 것
- 얼마나 많은 비잔틴 노드 장애가 발생해도 시스템이 동작하는가?
- 그러한 시스템을 어떻게 구축하는가?
- 비잔틴 장군 문제 [문제편]
- n명의 비잔틴 장군이 있을 때
- 공격할지 말지를 투표로 정함
- 다수결로 공격 여부(합의)를 결정
- 그런데 말입니다
- 배신자 장군이 있다면?
- 절반 이상이 배신자라면?
- 3m + 1 장군이 있을 때, m 보다 큰 배신자가 있을 경우 해결 불가
- 3명의 장군 중 1명의 배신자가 있으면 모순에 빠짐
- 2개의 명령이 서로 다른데, 3개의 명령은 동등한 무게를 가지므로 비교 불가능
- 비잔틴 장군 문제 [해결편]
- 가정
- OM(m) 알고리즘
- 메시지를 수신
- peer들에게 메시지 전파
- majority 정렬
- OM(m) 알고리즘은 비용이 큼 (O(n^m+1))
- 쿨한 알고리즘이 많이 있으니 그걸 쓰시오~
