비잔틴 장애 허용

“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야하며, 또 모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 사토시 나카모토와 비트코인 개발 작업을 협업했던 제임스 A 도날드가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도날드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘두 장군의 문제’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘비잔틴 장군의 문제’로 확장이 된다.

분산원장 체계는 제대로 돌아가기 위해서 원장을 공유하는 참여자들이 정직하게 행동해야 하며 이를 보장할 수 있는 방법이 있어야 하며, 누군가 속이려 들더라도 모두가 지닌 원장은 같은 내용을 유지해야 하는 방법 또한 존재하야 한다. 이런 골칫거리가 비트코인에서의 비잔틴 장군의 문제이다.

여기서 비잔티움 장애 허용(Byzantine Fault Tolerance)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티움 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래다.

두 장군의 문제

두 장군의 문제(Two Generals Problem)는 1972년 등장한 일종의 가상 실험이다. 이 실험에서 가정은 1. 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양 옆에 주둔한 상황이며 2. 두 장군은 적군을 점령하기 위해 두 부대가 같은 날, 같은 시각에 공격을 하려 한다. 3. 이때 연락을 주고받아야 하는데 이를 담당하는 연락병은 직접 적군의 도시를 통과해야하며 4. 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정 하에 진행이 된다.

장군A는 B에게 메시지를 보냈지만 잘 전달 됐는지 확신을 하지 못한다. 이에 B가 메시지를 잘 받았으면 A에게 확인 답장을 보내야 하는데 B도 마찬가지로 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다. 이에 B를 안심시키고 함께 공격하기 위해 A가 답장을 받았다고 재답장을 해야 하지만 이 역시 B에게 잘 도달했는지 장담하지 못한다. 결국 이는 두 장군이 같은 수준의 합의에 도달할 수 없고 이러한 불확실성은 결국 함께 적군의 도시를 공격할 수 없다는 의미이다. 이후 이 문제는 실제로 해결이 불가능한 것으로 증명됐으며 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 같은 내용의 거래기록을 갖는데 까지 도달하지 못한다는 의미이다.

비잔틴 장군의 문제

비잔틴 장군의 문제(Byzantine Generals Problem)는 1982년 래슬리 램포트, 마샬 피즈가 함께 쓴 논문에서 소개 된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. 비잔틴 장군의 문제는 광활한 영토 각 지역마다 장군들이 통치하는 것을 가정한다. 이웃나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 높아지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.

이러한 비잔틴 장군의 문제를 블록체인에 적용해 본다면, 각 장군들은 하나의 노드가 되며, 노드들은 현 시스템 상태에 합의를 달성할 수 있는 방법을 찾아야 한다. 분산화 된 네트워크의 대다수의 참가자들은 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 하는 것이다. 그러므로 분산화 된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 3분의 2 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것이다. 이는 네트워크 참여자 대다수가 악의적으로 행동하기로 결정할 경우, 시스템이 실패하거나 공격을 당할 수 있음을 의미하게 된다. 비트코인 상에서는 참여자가 수 만 명이 될 수 있기 때문에 사토시 나카모토 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.

비잔틴 장애 허용

비트코인 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군들 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 항공기 분야에서 예를 들게 된다면 항법 장치 즉, 네트워크가 올바르게 작동하려면 설치된 센서들(장군)이 올바른 정보를 알려줘야 한다. 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 네트워크가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다. 이를 컴퓨터 공학에서 비잔틴 장애 허용(BFT:Bizantine Fault Tolerance)라고 부른다.

학자들은 비잔틴 장애 허용의 가장 기본적인 전제가 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명했다. 항공기 분야에서 센서가 세 개 일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 항공기 분야에서 비잔틴 장애 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러 개 만든 후, 데이터가 필요한 설비에 여러 개의 라인을 통해 송신한다. 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지 여부를 확인하고 상호 비교를 통해 비잔틴 장군의 문제를 해결하여 합의의 무결성을 확보하는 방법으로 설계된 것이다. 결국 데이터의 수와 전송 경로를 동시에 늘려서 하나의 센서로도 여러 개의 센서를 설치한 효과를 얻은 것으로 해석이 되지만 이는 수학적으로 비잔틴 장군의 문제를 해결 했다기보다는 현실적으로 문제 발생 확률을 줄인 시도였다. 간단히 말해, 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하다. 컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며 사토시 나카모토는 항공기 분야의 해결책과 다르게 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 하였다. 이를 보통 합의 알고리즘이라고 부르게 되며 비트코인은 PoW라는 합의구조를 도입하여 비잔틴 장군의 문제를 해결하였다.

합의 알고리즘

합의 알고리즘은 블록체인 네트워크에서 합의를 달성하는 메커니즘으로 정의가 가능하다. 가장 일반적인 예로 비트코인의 작업증명방식(PoW, Proof of Work)을 들 수 있다. 비트코인을 설계할 당시 사토시 나카모토는 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다. 우선 비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 룰을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이같은 여러 숫자들을 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했는데 퍼즐을 푸는 과정이 곧 PoW이며 수학 퍼즐이 풀리면 블록이 만들어지며 이를 채굴이라고 한다. PoW를 수행해 퍼즐이 풀렸다면 결국 블록은 부정이 없도록 각종 룰을 지킨 정상 거래들을 모아 정상적인 방법으로 만든 원장이라는 의미이다. 마지막에 나온 블록의 고유 값이 정상이면 계산과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 좋다는 의미이다. 비트코인은 결국 PoW를 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. PoW를 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요 없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행과 중앙기관의 역할은 이러한 비트코인 시스템 내에서 사라졌으며 비잔틴 장애 허용을 달성하는 가장 똑똑한 접근으로 여겨지고 있다.

참고자료

• 바이넌스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이넌스 아카데미》, 2018-06-12
• tyami, 〈PBFT(Practical Byzantine Fault Tolerance〉, 《네이버 블로그》, 2018-05-05

같이 보기

• 합의 알고리즘
• 프랙티컬 비잔틴 장애 허용
• 텐더민트 비잔틴 장애 허용

이 비잔틴 장애 허용 문서는 알고리즘에 관한 글로서 검토가 필요합니다. 위키 문서는 누구든지 자유롭게 편집할 수 있습니다. [편집]을 눌러 문서 내용을 검토·수정해 주세요.

블록체인 : 블록체인 기술, 합의 알고리즘, 암호 알고리즘, 알고리즘 □■⊕, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스 채굴 알고리즘 SHA-256 • X11 • X11고스트 • X13 • X14 • X15 • X16R • X17 • 그로스톨 • 네오스크립트 • 니스트5 • 리라2알이 • 미리아드-그로스톨 • 블레이크 • 블레이크2 • 블레이크B • 블레이크2B • 블레이크256R8 • 블레이크256R14 • 스컹크해시 • 스케인 • 스크립트 알고리즘 • 스크립트엔 • 엘비알와이(LBRY) • 이더해시 • 이퀴해시 • 제반 • 쿼크 알고리즘 • 큐빗 알고리즘 • 크립토나이트 • 크립토나이트 라이트 • 타임트래블10 • 텐서리티 • 파스칼 • 프로그작업증명(ProgPoW) 매칭 알고리즘 BM25 • FAISS • 경매 • 더치 경매 • 매칭 알고리즘 • 매칭튜터 • 벡터검색 • 비크리 경매 • 센디 • 집닥 • 튜다 • 틴더 추천 알고리즘 TF-IDF • 역문서빈도(IDF) • 용어빈도(TF) • 추천 알고리즘 • 콘텐츠 기반 필터링 • 협업 필터링 고급 검색 알고리즘 AND-OR 검색 트리 • 국소 검색 알고리즘 • 국소 다발 검색 • 모의정련 • 언덕 오르기 검색 • 유전 알고리즘 대항 검색 검색의 차단 • 알파베타 가지치기 • 전방 가지치기 • 최소최대 알고리즘 제약 만족 문제 국소검색 • 역추적검색 • 제약전파 게임이론 게임이론 • 공유지의 비극 • 내시균형 • 메커니즘 디자인 • 비협조게임 • 사회선택이론 • 역게임이론 • 제로섬게임 • 조정게임 • 죄수의 딜레마 • 치킨게임 • 팃포탯 • 협조게임 위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반