[알고리즘] 비잔틴 장애 허용 (Byzantine Fault Tolerance)

개요 

비잔틴 장애 허용 : 컴퓨터 공학에서 부분 시스템의 문제가 발생하여도 잔체 시스템은 정상적으로 운용하도록 설계하는 것.

우주 방사선에 의한 반도체 고장 문제를 해결하기 위해 만들어진 기법입니다. 블록체인 기술에 적용되면서 블록체인 엔지니어들이 알아야 할 핵심 개념이 되었습니다. 

 

두 장군의 문제, 비잔틴 장군의 문제

비잔틴 장애를 허용을 이해하기 위해서는 두 가지 문제를 알아야 합니다. 

* 두 장군의 문제 

두 장군 A, B 사이에 적군 C가 있다고 가정합니다. 

 

장군 A는 장군 B에게 메세지를 전달하고 싶습니다. 그러나 중간에 있는 적군 C에 의해 메세지는 변조될 수 있습니다. 장군 B가 장군 A에게 메세지를 전달할 때도 동일한 문제가 발생할 수 있습니다.

 

그렇다면 적군 C가 변조하지 않은, 서로 동일한 수준의 합의(메세지)에 도달하도록 만드는 알고리즘이 있을까요? 없습니다. 수학적으로 불가능합니다. '두 장군의 문제'는 해결할 수 없는 문제입니다.

 

* 비잔틴 장군의 문제 

두 장군이 아닌 세 명 이상 장군이 있는 경우는 어떠할까요? 전체의 2/3 이상의 신뢰 가능한 장군이 확보된다면 해결할 수 있는 문제입니다. 그럼 전체의 2/3 이상의 신뢰 가능한 장군을 어떻게 확보할 수 있을까요? 어떠한 방식으로 비잔틴 장애 허용 시스템을 구축할 수 있을까요? 

 

비잔틴 장군 문제 해결 (비잔틴 장애 허용)

* 합의 알고리즘 : 비트코인의 작업 증명

합의 알고리즘은 비잔틴 장애 허용 시스템을 위해 고안된 해결 방법입니다. 비트코인 작업 증명(PoW)이 이 알고리즘을 사용합니다. 합의 알고리즘은 특정 값 이하의 해시를 찾는 과정으로 작업 참여를 증명합니다. 

P와 W의 비트코인 네트워크 상의 트랜젝션이 발생했다고 가정합니다.

 

트랜젝션이 발생하면 비트코인 네트워크 참여자들은 채굴을 사작합니다. 

 

많은 참여자들 중 참여자 C가 가장 빠르게 채굴에 성공하였습니다 (가장 먼저 특정 값 이하의 해시를 찾았습니다). 참여자 C는 비트코인을 보상받습니다.

채굴 속도는 무작위성 및 채굴 장비 성능에 좌우됩니다. 코인 채굴을 위해 그래픽카드를 구매하는 이유입니다. 채굴은 특정 값 이하의 임의의 해시를 찾는 과정입니다. 무작위성이 반드시 존재하기에 더 낮은 성능의 채굴 장비 참여자가 특정 값 이하의 해시를 남들보다 먼저 찾아 보상받을 수도 있습니다. 

 

악의적인 조직이 비트코인 네트워크 전체의 51%를 차지해야 악의적으로 개입 가능한 구조입니다. 현재 매우 방대해진 비트코인 네트워크 규모를 생각해 보면 51% 장악은 현실적으로 불가능합니다. 방대한 비트코인 네트워크 규모를 생각했을 때 비잔틴 장군의 문제를 해결할 수 있습니다. 

참고 자료 내 표현 해석
비트코인 상에서는 참여자가 수만 명이 될 수 있기 때문에 사토시 나카모토 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다
=> 현실적인 비트코인 생태계에서는 두 장군의 문제를 고려할 필요가 없음, 비잔틴 장군 문제를 해결하는 것이 주요 난제라는 말 
http://wiki.hash.kr/index.php/%EB%B9%84%EC%9E%94%ED%8B%B4_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9

 

다른 해결 방법으로는 PBFT( 프랙티컬 비잔틴 장애 허용 알고리즘 )이 있습니다. 

 

참고 자료 

위키원

https://bitcoin.org/bitcoin.pdf

우주방사선이 일으키는 ‘소프트에러’

두 장군 문제 - 위키백과, 우리 모두의 백과사전

위키원