위키원
비잔틴 장애 허용
비잔틴 장애 허용(BFT; Byzantine Fault Tolerance)이란 장애가 있더라도 전체의 3분의 1을 넘지 않는다면, 시스템이 정상 작동하도록 허용하는 합의 알고리즘이다. 비잔티움 장애 허용이라고도 쓴다. 블록체인의 분산원장 체계는 제대로 돌아가기 위해서 원장을 공유하는 참여자들이 정직하게 행동해야 하며 이를 보장할 수 있는 방법이 있어야 한다. 만약 악의적인 노드가 존재하여 누군가 속이려 들더라도 모두가 지닌 원장은 같은 내용을 유지해야 하는 방법 또한 존재해야 한다. 이런 골칫거리가 비잔틴 장군의 문제이다.
비잔틴 장애 허용(BFT)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래이다. 비잔틴 장애 허용을 알기 위해서는 두 장군의 문제와 여기서 파생된 비잔틴 장군의 문제를 먼저 알아야 한다. [1]
개요
비트코인 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군들 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 이러한 접근 방식은 항공기의 항법장치 분야에서 처음 적용이 되었다. 항법장치는 항공기의 위치를 제공하는 계기인데, 이것이 올바르게 작동을 하려면 항공기 곳곳에 설치된 센서들이 항상 올바르고 같은 정보를 보내야 한다. 이때 한 센서라도 다른 정보를 주게 된다면 재빨리 다른 센서와 비교해 어느 값을 따를지 결정을 해야 하기 때문에 비잔틴 장군의 문제가 발생하게 된다. 하지만 중요한 것은 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 항법장치가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다. 이러한 설계를 컴퓨터 공학에서 비잔틴 장애 허용(BFT:Bizantine Fault Tolerance)라고 부른다. 당시 학자들은 비잔틴 장애 허용의 가장 기본적인 전제가 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명했다. 항법장치의 센서가 세 개 일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 항법장치에서 비잔틴 장애 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러 개 만든 후, 데이터가 필요한 설비에 여러 개의 라인을 통해 송신한다. 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지 여부를 확인하고 상호 비교를 통해 비잔틴 장군의 문제를 해결하여 합의의 무결성을 확보하는 방법으로 설계된 것이다. 결국 데이터의 수와 전송 경로를 동시에 늘려서 하나의 센서로도 여러 개의 센서를 설치한 효과를 얻은 것으로 해석이 되지만 이는 수학적으로 비잔틴 장군의 문제를 해결 했다기보다는 현실적으로 문제 발생 확률을 줄인 시도였다. 이처럼 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하도록 만든 시스템 설계이다.
컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며 사토시 나카모토는 항공기 분야의 해결책과 다르게 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 하였다. 블록체인 분야에서의 비잔틴 장애 허용 시스템은 보통 합의 알고리즘이라고 부르게 되며 비트코인은 작업증명이라는 합의구조를 처음 도입하여 비잔틴 장군의 문제를 해결하였다.
두 장군의 문제
두 장군의 문제(Two Generals Problem)는 1972년 등장한 일종의 가상 실험이다. 이 실험에서 가정은 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양 옆에 주둔한 상황이며 두 장군은 적군을 점령하기 위해 두 부대가 같은 날, 같은 시각에 공격을 하려 한다. 이때 연락을 주고받아야 하는데 이를 담당하는 연락병은 직접 적군의 도시를 통과해야하며 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정 하에 진행이 된다.
장군A는 B에게 메시지를 보냈지만 잘 전달 됐는지 확신을 하지 못한다. 이에 B가 메시지를 잘 받았으면 A에게 확인 답장을 보내야 하는데 B도 마찬가지로 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다. 이에 B를 안심시키고 함께 공격하기 위해 A가 답장을 받았다고 재답장을 해야 하지만 이 역시 B에게 잘 도달했는지 장담하지 못한다. 결국 이는 두 장군이 같은 수준의 합의에 도달할 수 없고 이러한 불확실성은 결국 함께 적군의 도시를 공격할 수 없다는 의미이다. 이후 이 문제는 실제로 해결이 불가능한 것으로 증명됐으며 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 같은 내용의 거래기록을 갖는데 까지 도달하지 못한다는 의미이다.[2]
비잔틴 장군의 문제
비잔틴 장군의 문제(Byzantine Generals Problem)는 1982년 래슬리 램포트, 마샬 피즈가 함께 쓴 논문에서 소개 된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. 비잔틴 장군의 문제는 광활한 영토 각 지역마다 장군들이 통치하는 것을 가정한다. 이웃나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 높아지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.
이러한 비잔틴 장군의 문제를 블록체인에 적용해 본다면, 각 장군들은 하나의 노드가 되며, 노드들은 현 시스템 상태에 합의를 달성할 수 있는 방법을 찾아야 한다. 분산화 된 네트워크의 대다수의 참가자들은 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 하는 것이다. 그러므로 분산화 된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 3분의 2 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것이다. 이는 네트워크 참여자 대다수가 악의적으로 행동하기로 결정할 경우, 시스템이 실패하거나 공격을 당할 수 있음을 의미하게 된다.[1] 비트코인 상에서는 참여자가 수 만 명이 될 수 있기 때문에 사토시 나카모토 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.
“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야하며, 또 모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 사토시 나카모토와 비트코인 개발 작업을 협업했던 제임스 A 도날드가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도날드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘두 장군의 문제’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘비잔틴 장군의 문제’로 확장이 된다.
결론적으로 비잔티움 장군 문제는 다양한 시나리오에 광범위하게 적용되고 있는 비잔티움 장애 허용 시스템을 탄생시킨 흥미로운 딜레마이다. 블록체인 산업 외에도, 항공, 우주, 원자력 산업에 비잔티움 장애 허용 시스템이 사용되고 있다. 암호 화폐 관점에서, 좋은 합의 매커니즘과 함께 효율적인 네트워크 커뮤니케이션을 확보하는 것은 모든 블록체인 생태계에 필수적인 것이다. 이러한 시스템을 보호하는 데는 지속적인 노력이 필요하며, 현존하는 합의 알고리즘은 몇 가지 한계(확장성과 같은)를 아직 극복하지 못했다. 그럼에도 불구하고, 작업 증명과 지분 증명은 비잔티움 장애 허용 시스템에 관한 아주 흥미로운 접근들이며, 잠재력을 가진 애플리케이션들은 광범위한 혁신을 불러일으키고 있다.[3]
합의 알고리즘
합의 알고리즘은 블록체인 네트워크에서 합의를 달성하는 메커니즘으로 정의가 가능하다. 가장 일반적인 예로 비트코인의 작업증명(PoW, Proof of Work)을 들 수 있다.블록체인 중 가장 처음 제시된 비트코인의 합의 알고리즘 중 작업증명방식(Proof of Work, POW)는 타임스탬프(Timestamp)와 서명(Sign, 블록체인에서는 Key)을 통해 이 문제를 해결한다. '장군은 메시지를 보내기 위해 10분의 시간을 가지며, 메시지는 모든 장군의 메시지와 메시지를 보내기 위해 10분을 들였다는 증거를 포함한다.' 라는 규칙이 추가됨에 따라 중간의 비잔틴 장군이 존재하더라도 다른 장군들은 이 장군이 거짓임을 밝혀낼 수 있다. 혹은 초기에 메시지를 받은 장군이 존재하더라도 앞선 시나리오처럼 정직한 장군들이 성을 함락할 수 있게 된다. 비트코인을 설계할 당시 사토시 나카모토는 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다. 우선 비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 룰을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이같은 여러 숫자들을 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했는데 퍼즐을 푸는 과정이 곧 작업증명이며 수학 퍼즐이 풀리면 블록이 만들어지며 이를 채굴이라고 한다. 작업증명을 수행해 퍼즐이 풀렸다면 결국 블록은 부정이 없도록 각종 룰을 지킨 정상 거래들을 모아 정상적인 방법으로 만든 원장이라는 의미이다. 마지막에 나온 블록의 고유 값이 정상이면 계산과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 좋다는 의미이다. 비트코인은 결국 작업증명을 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. 작업증명을 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요 없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행과 중앙기관의 역할은 이러한 비트코인 시스템 내에서 사라졌으며 비잔틴 장애 허용을 달성하는 가장 똑똑한 접근으로 여겨지고 있다.
비잔틴 장애 허용 기반 합의 알고리즘
기존 알고리즘은 가상화폐가 필요하다는 문제 외에도 부분 분기가 일어날 수 있다는 문제가 있다. 간단하게 작업증명 알고리즘을 예로 들면 A와 B블록이 거의 동시에 생성될 경우 각 노드는 자신의 선택에 따라 A와 B블록 중 하나를 선택한다. 이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 된다. 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에서는 적용이 어려운 문제점이 있다.
- 실용적 비잔틴 장애 허용(PBFT)
- 실용적 비잔틴 장애 허용(Practical Byzantine Fault Tolerance, PBFT)은 분산시스템이 약속된 행동을 하지 않는 비잔틴 노드가 존재할 수 있는 비동기 시스템일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘이다. 실용적 비잔틴 장애 허용은 기존의 비잔틴 장애 허용(BFT) 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있게 하였다. 합의는 다음과 같이 수행한다.
- 리더가 클라이언트들의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에 전파한다.
- 리더의 메시지를 받은 노드들은 다른 노드들에서 받은 메시지를 다시 한번 나머지 노드들에게 전파한다.
- 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메시지(정족수 이상의)가 무엇인지 다른 노드들에게 전파한다.
- 앞의 과정이 끝나면 모든 노드들은 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 된다.
- 실용적 비잔틴 장애 허용은 두번의 브로드캐스트 과정을 이용해 비잔틴 리더나 비잔틴 검증 노드가 네트워크 분기를 위해 이상한, 혹은 임의의 메시지를 보내도 네트워크의 모든 노드는 같은 메시지를 가질 수 있게 하였다. 이러한 실용적 비잔틴 장애 허용 알고리즘은 IBM Fabric 0.6v이나 1.0v의 Orderer서비스, R3 Corda의 Notary와 같은 프라이빗 블록체인에서 사용하고 있다.
- 텐더민트(Tendermint)
- 텐더민트(Tendermint, DPoS + PBFT)는 코스모스(Cosmos)에서 사용하는 합의 알고리즘으로 실용적 비잔틴 장애 허용 알고리즘을 공개 및 비공개 블록체인에 맞도록 개량한 합의 알고리즘이다. 텐더민트는 전통적인 합의 알고리즘이 블록체인에 적용된 의미있는 사례이며 위임 지분 증명(Delegated Proof-of-Stake, DPoS) 개념과 실용적 비잔틴 장애 허용 개념을 섞어 공개 및 비공개 블록체인에서 사용할 수 있도록 한 합의 알고리즘이다. 텐더민트의 전체 합의 프로세스는 실용적 비잔틴 장애 허용와 거의 유사하다. 텐더민트 프로세스에서의 의도는 실용적 비잔틴 장애 허용의 Pre-Prepare, Prevote는 Prepare, Precommit은 실용적 비잔틴 장애 허용의 Commit으로 매칭시키면 이해가 쉽다. 텐더민트는 앞에서 언급하였듯이 실용적 비잔틴 장애 허용에 위임 지분 증명 개념을 추가하여 블록체인에 적합한 합의 알고리즘을 개발하였다. 차이점을 간단히 요약하면 기존의 실용적 비잔틴 장애 허용은 하나의 노드가 하나의 투표를 하는 방식으로 투표를 받아 가장 많은 투표를 받은 블록을 승인하지만 텐더민트는 지분(Stake)을 기반으로 투표를 한다. 텐더민트는 투표를 할때 Locking 메커니즘을 통해 투표에 참여한 지분을 네트워크에 동결시키고 이를 해제하는 메커니즘을 통해 이중 투표 문제를 막고 지분으로 네트워크를 유지한다. 또한 이중 투표 시도와 같은 블록체인을 공격하려는 악의적인 행위를 하면 지분을 빼앗는 방법으로 기존의 블록체인이 네트워크 공격 노드에 아무런 처벌을 하지 않던 문제(Nothing of Stake)를 해결했다.[4]
각주
- ↑ 1.0 1.1 바이낸스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이낸스 아카데미》, 2018-06-12
- ↑ tyami, 〈PBFT(Practical Byzantine Fault Tolerance) 공부해보자〉, 《네이버 블로그》, 2018-05-05
- ↑ 바이낸스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이낸스 아카데미》, 2019-08-08
- ↑ 아이콘루프, 〈BFT 기반 합의 알고리즘〉, 《더 루프 블로그》, 2017-06-21
참고자료
- tyami, 〈PBFT(Practical Byzantine Fault Tolerance) 공부해보자〉, 《네이버 블로그》, 2018-05-05
- energist, 〈(Blockchain Study) PBFT(Practical Byzantine Fault Tolerance)〉, 《스팀잇》, 2018년 4월
- 바이낸스 아카데미, 〈비잔티움 장애 허용 설명〉, 《바이낸스 아카데미》, 2018-06-12
- 홍석주(Seokju Hong), 〈Consensus over Byzantine Fault (1) - The Problem〉, 《깃허브》, 2018-02-06
- 홍석주(Seokju Hong), 〈Consensus over Byzantine Fault (2) - PBFT(1)〉, 《깃허브》, 2018-02-19
- 홍석주(Seokju Hong), 〈Consensus over Byzantine Fault (3) - PBFT(2)〉, 《깃허브》, 2018-02-22
- 바이낸스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이낸스 아카데미》, 2019-08-08
- TokenPost, 〈PBFT(Practical Byzantine Fault Tolerance, 실용적 비잔틴 장애 허용)〉, 《TOKENPOST》
- 아이콘루프, 〈BFT 기반 합의 알고리즘〉, 《더 루프 블로그》, 2017-06-21
같이 보기
- 합의 알고리즘
- 프랙티컬 비잔틴 장애 허용
- 경량 비잔틴 장애 허용
- 위임 프랙티컬 비잔틴 장애 허용
- 텐더민트 비잔틴 장애 허용
- 비잔틴 장군의 문제
- 두 장군의 문제
- 텐더민트
- 실용적 비잔틴 장애 허용
