검수요청.png검수요청.png

"비잔틴 장애 허용"의 두 판 사이의 차이

위키원
이동: 둘러보기, 검색
(→‎합의 알고리즘)
(→‎합의 알고리즘)
 
(사용자 4명의 중간 판 54개는 보이지 않습니다)
1번째 줄: 1번째 줄:
−
“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야하며, 또 모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 [[사토시 나카모토]]와 [[비트코인]] 개발 작업을 협업했던 [[제임스 A 도날드]]가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도날드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘[[두 장군의 문제]]’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘[[비잔틴 장군의 문제]]’로 확장이 된다.  
+
'''비잔틴 장애 허용'''<!--비잔티움 장애 허용, 비잔틴장애허용, 비잔티움장애허용, BFT, Byzantine Fault Tolerance-->(BFT; Byzantine Fault Tolerance)이란 장애가 있더라도 전체의 3분의 1을 넘지 않는다면, 시스템이 정상 작동하도록 허용하는 [[합의 알고리즘]]이다. '''비잔티움 장애 허용'''이라고도 쓴다. 블록체인의 분산원장 체계는 제대로 돌아가기 위해서 원장을 공유하는 참여자들이 정직하게 행동해야 하며 이를 보장할 방법이 있어야 한다. 만약 악의적인 노드가 존재하여 누군가 속이려 들더라도 모두가 지닌 원장은 같은 내용을 유지해야 하는 방법 또한 존재해야 한다. 이런 골칫거리가 비잔틴 장군의 문제이다.
  
−
분산원장 체계는 제대로 돌아가기 위해서 원장을 공유하는 참여자들이 정직하게 행동해야 하며 이를 보장할 수 있는 방법이 있어야 하며, 누군가 속이려 들더라도 모두가 지닌 원장은 같은 내용을 유지해야 하는 방법 또한 존재하야 한다. 이런 골칫거리가 [[비트코인]]에서의 비잔틴 장군의 문제이다.
+
비잔틴 장애 허용(BFT)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래이다. 비잔틴 장애 허용을 알기 위해서는 두 장군의 문제와 여기서 파생된 비잔틴 장군의 문제를 먼저 알아야 한다. <ref name="바이낸스">바이낸스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명  ]〉, 《바이낸스 아카데미》, 2018-06-12</ref>
  
−
여기서 '''[[비잔티움 장애 허용]]'''(Byzantine Fault Tolerance)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티움 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래다.<ref>바이넌스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명  ]〉, 《바이넌스 아카데미》, 2018-06-12</ref>
+
==개요==
 +
[[비트코인]] 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 이러한 접근 방식은 항공기의 항법장치 분야에서 처음 적용이 되었다. 항법장치는 항공기의 위치를 제공하는 계기인데, 이것이 올바르게 작동을 하려면 항공기 곳곳에 설치된 센서들이 항상 올바르고 같은 정보를 보내야 한다. 이때 한 센서라도 다른 정보를 주게 된다면 재빨리 다른 센서와 비교해 어느 값을 따를지 결정을 해야 하므로 비잔틴 장군의 문제가 발생하게 된다. 하지만 중요한 것은 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 항법장치가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다. 이러한 설계를 컴퓨터 공학에서 '''비잔틴 장애 허용'''(BFT:Bizantine Fault Tolerance)라고 부른다. 당시 학자들은 비잔틴 장애 허용의 가장 기본적인 전제가 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명했다. 항법장치의 센서가 세 개일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 항법장치에서 비잔틴 장애 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러 개 만든 후, 데이터가 필요한 설비에 여러 개의 라인을 통해 송신한다. 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지를 확인하고 상호 비교를 통해 비잔틴 장군의 문제를 해결하여 합의의 무결성을 확보하는 방법으로 설계된 것이다. 결국 데이터의 수와 전송 경로를 동시에 늘려서 하나의 센서로도 여러 개의 센서를 설치한 효과를 얻은 것으로 해석이 되지만 이는 수학적으로 비잔틴 장군의 문제를 해결했다기보다는 현실적으로 문제 발생 확률을 줄인 시도였다. 이처럼 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하도록 만든 시스템 설계이다.
  
 +
컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며 [[사토시 나카모토]]는 항공기 분야의 해결책과 다르게 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 하였다. 블록체인 분야에서의 비잔틴 장애 허용 시스템은 보통 [[합의 알고리즘]]이라고 부르게 되며 [[비트코인]]은 [[작업증명]]이라는 합의구조를 처음 도입하여 비잔틴 장군의 문제를 해결하였다.
 +
 +
==초기 솔루션==
 +
1982년 Lamport, Shostak, Pease가 여러 솔루션을 제시했다. 이들은 비잔티움 장군 문제가 충직한 부관(Lieutenant) 모두가 지휘관(Commander)이 내린 명령과 일치하게, 같은 행동을 해야 한다는 "Commander and Leutenants" 문제로 좁혀질 수 있다고 말했다.
 +
 +
* 첫 번째 솔루션은 전달된 메시지가 위조될 수도 있다는 시나리오를 가정한다. 하지만 이때 배반한 장군의 수가 전체 장군 수의 3분의 1 이상과 같거나 넘지 않는 이상 비잔티움 장애 허용으로 간주한다. 3분의 1 혹은 그 이상의 배반자가 있을 경우는 하나의 지휘관과 두 부관 문제(one Commander and two Lieutenants problem) 문제로 간주할 수 있으며, 즉, 지휘관이 배반자인 경우 해결할 수 없다. 한 명의 배반자 지휘관 A와 두 부관 B, C가 있다고 가정하자. A가 B에게 공격하라고, C에게는 후퇴하라고 명령하는 경우 A의 메시지를 전달받은 B, C는 누가 배반자인지 알 수 없다. A가 아니라 부관 B와 C가 배반했을 수도 있기 때문이다. 따라서 n명의 지휘관이 있고 그중 t명이 배반자인 경우 오직 <math>n>3t</math>이고 커뮤니케이션이 동시에 이루어져야만(synchronous; bounded delay) 솔루션이 있다.
 +
 +
* 두 번째 솔루션은 메시지의 서명이 위조될 수 없다는 전제로 한다. 보안이 중요한 시스템(security-critical system)에서 디지털 서명은(대개 현대의 컴퓨터 시스템에서 공개키 암호화로 구현됨) 임의의 배반자 지휘관이 있는 상황에서 비잔틴 장애 허용을 제공한다. 하지만 안전이 중요한 시스템(safety-critical system)에서 CRCs 등은 대부분의 상황에서 적용될 수 있는 간단한 에러를 찾는 코드를 낮은 비용에 제공하며, 이는 비잔틴 장애와 비잔틴 장애가 아닌 것 모두에 가능하다. 따라서 암호화된 디지털 서명 방식은 별도의 보안 위협이 있지 않은 한 안전이 중요한 시스템에서 좋은 선택은 아니다.
 +
 +
* 또한 Lamport, Shostak, Pease는 앞서 서술한 두 솔루션 외에도 모든 지휘관이 서로 소통할 수 없는 경우 등 다양한 경우에 관해서도 서술했다.
 +
 +
1980년 비잔틴 장애 허용이 도입된 이후로 Draper's FTP, Honeywell's MMFCS. SRI's SIFT 등 여러 시스템 구조가 디자인되었다.<ref>〈[https://ko.wikipedia.org/wiki/%EB%B9%84%EC%9E%94%ED%8B%B0%EC%9B%80_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9 비잔티움 장애 허용]〉, 《위키백과》</ref>
  
 
==두 장군의 문제==
 
==두 장군의 문제==
−
'''두 장군의 문제'''(Two Generals Problem)는 1972년 등장한 일종의 가상 실험이다. 이 실험에서 가정은 1. 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양 옆에 주둔한 상황이며 2. 두 장군은 적군을 점령하기 위해 두 부대가 같은 날, 같은 시각에 공격을 하려 한다. 3. 이때 연락을 주고받아야 하는데 이를 담당하는 연락병은 직접 적군의 도시를 통과해야하며 4. 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정 하에 진행이 된다.  
+
'''[[두 장군의 문제]]'''(Two Generals Problem)는 1972년 등장한 일종의 가상 실험이다. 이 실험에서 가정은 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양옆에 주둔한 상황이며 두 장군은 적군을 점령하기 위해 두 부대가 같은 날, 같은 시각에 공격하려 한다. 이때 연락을 주고받아야 하는데 이를 담당하는 연락병은 직접 적군의 도시를 통과해야 하며 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정하에 진행이 된다.
  
−
장군A는 B에게 메시지를 보냈지만 잘 전달 됐는지 확신을 하지 못한다. 이에 B가 메시지를 잘 받았으면 A에게 확인 답장을 보내야 하는데 B도 마찬가지로 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다. 이에 B를 안심시키고 함께 공격하기 위해 A가 답장을 받았다고 재답장을 해야 하지만 이 역시 B에게 잘 도달했는지 장담하지 못한다. 결국 이는 두 장군이 같은 수준의 합의에 도달할 수 없고 이러한 불확실성은 결국 함께 적군의 도시를 공격할 수 없다는 의미이다. 이후 이 문제는 실제로 해결이 불가능한 것으로 증명됐으며 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 같은 내용의 거래기록을 갖는데 까지 도달하지 못한다는 의미이다.<ref>tyami, 〈[https://m.blog.naver.com/PostView.nhn?blogId=tyami&logNo=221268715771&proxyReferer=https%3A%2F%2Fwww.google.com%2F PBFT(Practical Byzantine Fault Tolerance]〉, 《네이버 블로그》, 2018-05-05</ref>
+
장군 A는 B에게 메시지를 보냈지만 잘 전달됐는지 확신을 하지 못한다. 이에 B가 메시지를 잘 받았으면 A에게 확인 답장을 보내야 하는데 B도 마찬가지로 이 메시지가 A에게 무사히 도달했는지 자신하지 못한다. 이에 B를 안심시키고 함께 공격하기 위해 A가 답장을 받았다고 재 답장을 해야 하지만 이 역시 B에게 잘 도달했는지 장담하지 못한다. 결국 이는 두 장군이 같은 수준의 합의에 도달할 수 없고 이러한 불확실성은 결국 함께 적군의 도시를 공격할 수 없다는 의미이다. 이후 이 문제는 실제로 해결할 수 없는 것으로 증명됐으며 비트코인으로 치면 잠재적인 배신자들이 섞여 있는 한 참여자들은 같은 내용의 거래기록을 갖는 데까지 도달하지 못한다는 의미이다.<ref>tyami, 〈[https://m.blog.naver.com/PostView.nhn?blogId=tyami&logNo=221268715771&proxyReferer=https%3A%2F%2Fwww.google.com%2F PBFT(Practical Byzantine Fault Tolerance) 공부해보자]〉, 《네이버 블로그》, 2018-05-05</ref>
  
 
==비잔틴 장군의 문제==
 
==비잔틴 장군의 문제==
−
비잔틴 장군(Byzantine Generals Problem)의 문제는 1982년 [[래슬리 램포트]], [[마샬 피즈]]가 함께 쓴 논문에서 소개 된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. [[비트코인]] 상에서는 참여자가 수 만 명이 될 수 있기 때문에 [[사토시 나카모토]] 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.  
+
[[파일:비잔틴 장군 문제.jpg|썸네일|500픽셀|'''비잔틴 장군의 문제''']]
 +
'''[[비잔틴 장군의 문제]]'''(Byzantine Generals Problem)는 1982년 [[래슬리 램포트]], [[마샬 피즈]]가 함께 쓴 논문에서 소개된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. 비잔틴 장군의 문제는 광활한 영토 지역마다 장군들이 통치하는 것을 가정한다. 이웃 나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 커지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.
 +
 
 +
이러한 비잔틴 장군의 문제를 [[블록체인]]에 적용해 본다면, 각 장군은 하나의 [[노드]]가 되며, 노드들은 현 시스템 상태에 합의를 달성할 수 있는 방법을 찾아야 한다. 분산화된 네트워크의 대다수의 참가자는 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 한다. 그러므로 분산화된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 3분의 2 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것이다. 이는 네트워크 참여자 대다수가 악의적으로 행동하기로 할 경우, 시스템이 실패하거나 공격을 당할 수 있음을 의미하게 된다.<ref name="바이낸스"></ref> [[비트코인]] 상에서는 참여자가 수만 명이 될 수 있기 때문에 [[사토시 나카모토]] 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.
 +
 
 +
“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야 하며, 또 모두가 X를 안다는 사실을 우리가 모두 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 [[사토시 나카모토]]와 [[비트코인]] 개발 작업을 협업했던 [[제임스 A 도널드]]가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도널드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘[[두 장군의 문제]]’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘[[비잔틴 장군의 문제]]’로 확장이 된다.
 +
 
 +
결론적으로 비잔티움 장군 문제는 다양한 시나리오에 광범위하게 적용되고 있는 비잔티움 장애 허용 시스템을 탄생시킨 흥미로운 딜레마이다. 블록체인 산업 외에도, 항공, 우주, 원자력 산업에 비잔티움 장애 허용 시스템이 사용되고 있다. 암호화폐 관점에서, 좋은 합의 메커니즘과 함께 효율적인 네트워크 커뮤니케이션을 확보하는 것은 모든 블록체인 생태계에 필수적이다. 이러한 시스템을 보호하는 데는 지속적인 노력이 필요하며, 현존하는 합의 알고리즘은 몇 가지 한계(확장성과 같은)를 아직 극복하지 못했다. 그런데도, 작업 증명과 지분 증명은 비잔티움 장애 허용 시스템에 관한 아주 흥미로운 접근들이며, 잠재력을 가진 애플리케이션들은 광범위한 혁신을 불러일으키고 있다.<ref>바이낸스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명  ]〉, 《바이낸스 아카데미》, 2019-08-08</ref>
 +
 
 +
==합의 알고리즘==
 +
'''[[합의 알고리즘]]'''은 블록체인 네트워크에서 합의를 달성하는 메커니즘으로 정의할 수 있다. 가장 일반적인 예로 [[비트코인]]의 [[작업증명]](PoW, Proof of Work)을 들 수 있다. 블록체인 중 가장 처음 제시된 비트코인의 합의 알고리즘인 작업증명방식(Proof of Work, POW)는 타임 스탬프(Timestamp)와 서명(Sign, 블록체인에서는 Key)을 통해 이 문제를 해결한다. '장군은 메시지를 보내기 위해 10분의 시간을 가지며, 메시지는 모든 장군의 메시지와 메시지를 보내기 위해 10분을 들였다는 증거를 포함한다.'라는 규칙이 추가됨에 따라 중간의 비잔틴 장군이 존재하더라도 다른 장군들은 이 장군이 거짓임을 밝혀낼 수 있다. 혹은 초기에 메시지를 받은 장군이 존재하더라도 앞선 시나리오처럼 정직한 장군들이 성을 함락할 수 있게 된다. 비트코인을 설계할 당시 [[사토시 나카모토]]는 참여자 모두가 가장 최신의 원장을 같이 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다. 우선 비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 규정을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이런 여러 숫자를 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했는데 퍼즐을 푸는 과정이 곧 작업증명이며 수학 퍼즐이 풀리면 블록이 만들어지며 이를 [[채굴]]이라고 한다. 작업증명을  수행해 퍼즐이 풀렸다면 결국 블록은 부정이 없도록 각종 규정을 지킨 정상 거래를 모아 정상적인 방법으로 만든 원장이라는 의미이다. 마지막에 나온 블록의 고윳값이 정상이면 계산과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 좋다는 의미이다. 비트코인은 결국 작업증명을 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. 작업증명을 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요 없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행과 중앙기관의 역할은 이러한 비트코인 시스템 내에서 사라졌으며 비잔틴 장애 허용을 달성하는 가장 똑똑한 접근으로 여겨지고 있다.
  
−
비잔틴 장군의 문제는 광활한 영토 각 지역마다 장군들이 통치하는 것을 가정한다. 이웃나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 높아지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.
+
===비잔틴 장애 허용 기반 합의 알고리즘===
 +
기존 알고리즘은 가상화폐가 필요하다는 문제 외에도 부분 분기가 일어날 수 있다는 문제가 있다. 간단하게 작업증명 알고리즘을 예로 들면 A와 B블록이 거의 동시에 생성될 경우 각 노드는 자신의 선택에 따라 A와 B블록 중 하나를 선택한다. 이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 된다. 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에서는 적용이 어려운 문제점이 있다.
  
−
==비잔틴 장애 허용==
+
* '''프랙티컬 비잔틴 장애 허용'''(PBFT)
−
비트코인 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군들 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 항공기 분야에서 예를 들게 된다면 항법 장치가 올바르게 작동하려면 곳곳에 설치된 센서가 항상 같은 고도와 위치정보를 알려줘야 한다. 한 센서라도 다른 정보를 준다면 재빨리 다른 센서들이 준 값과 비교해 어느 값을 따를지 결정해야 한다. 여기서 중요한 것은 어느 한 센서가 잘못된 신호를 준다고 해서 비행중 항법장치가 멈추는 일이 있어서는 안된다는 점이다. 비잔틴 장군의 문제가 발생하더라도 잘못된 메시지는 계속 둔 채 계속 작동할 수 있도록 설계가 되어야 한다. 이를 컴퓨터 공학에서는 '''비잔틴 장애 허용'''(BFT:Bizantine Fault Tolerance)라고 부른다.
+
[[파일:Pbft 작동방식.jpg |썸네일|500픽셀|'''프랙티컬 비잔틴 장애 허용''' 작동방식]]
 +
: [[프랙티컬 비잔틴 장애 허용]](Practical Byzantine Fault Tolerance, PBFT)은 1982년 발표된 "The Byzantine Generals Problem" 논문에서 제안되었으며,<ref>〈[http://itwiki.kr/w/%EB%B9%84%EC%9E%94%ED%8B%B4_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9 비잔틴 장애 허용]〉, 《공대위키》</ref> 분산시스템이 약속된 행동을 하지 않는 비잔틴 노드가 존재할 수 있는 비동기 시스템일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘이다. [[프랙티컬 비잔틴 장애 허용]]은 기존의 비잔틴 장애 허용(BFT) 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있게 하였다. 합의는 다음과 같이 수행한다.
  
−
간단히 말해, 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하다. 컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며, 이를 보통 합의 알고리즘이라고 부른다.
+
# 리더가 클라이언트들의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에 전파한다.
 +
# 리더의 메시지를 받은 노드들은 다른 노드들에서 받은 메시지를 다시 한번 나머지 노드들에 전파한다.
 +
# 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메시지(정족수 이상의)가 무엇인지 다른 노드들에 전파한다.
 +
# 앞의 과정이 끝나면 모든 노드는 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 된다.
  
−
[[파일:Byzantine Agreement.jpg|썸네일|가운데|600픽셀|'''Byzantine Agreement'''(비잔틴장군의 동의)]]
+
: [[프랙티컬 비잔틴 장애 허용]]은 두 번의 브로드캐스트 과정을 이용해 비잔틴 리더나 비잔틴 검증 노드가 네트워크 분기를 위해 이상한, 혹은 임의의 메시지를 보내도 네트워크의 모든 노드는 같은 메시지를 가질 수 있게 하였다. 이러한 [[프랙티컬 비잔틴 장애 허용]] 알고리즘은 IBM Fabric 0.6v이나 1.0v의 Orderer 서비스, R3 Corda의 Notary와 같은 프라이빗 블록체인에서 사용하고 있다.
  
−
==합의 알고리즘==
+
* '''텐더민트'''(Tendermint)
−
'''합의 알고리즘'''은 블록체인 네트워크에서 합의를 달성하는 메커니즘으로 정의가 가능하다. 가장 일반적인 예로 [[비트코인]]의 [[작업증명]]방식(PoW, Proof of Work)을 들 수 있다. 비트코인을 설계할 당시 [[사토시 나카모토]]는 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다. 우선 비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 룰을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이같은 여러 숫자들을 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했는데 퍼즐을 푸는 과정이 곧 PoW이며 수학 퍼즐이 풀리면 블록이 만들어지며 이를 [[채굴]]이라고 한다. PoW를 수행해 퍼즐이 풀렸다면 결국 블록은 부정이 없도록 각종 룰을 지킨 정상 거래들을 모아 정상적인 방법으로 만든 원장이라는 의미이다. 마지막에 나온 블록의 고유 값이 정상이면 계산과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 좋다는 의미이다. 비트코인은 결국 PoW를 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. PoW를 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요 없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행과 중앙기관의 역할은 이러한 비트코인 시스템 내에서 사라졌으며 비잔틴 장애 허용을 달성하는 가장 똑똑한 접근으로 여겨지고 있다.
+
: [[텐더민트]](Tendermint, DPoS + PBFT)는 코스모스(Cosmos)에서 사용하는 합의 알고리즘으로 [[프랙티컬 비잔틴 장애 허용]] 알고리즘을 공개 및 비공개 블록체인에 맞도록 개량한 합의 알고리즘이다. [[텐더민트]]는 전통적인 합의 알고리즘이 블록체인에 적용된 의미 있는 사례이며 [[위임 지분 증명]](Delegated Proof-of-Stake, DPoS) 개념과 [[프랙티컬 비잔틴 장애 허용]] 개념을 섞어 공개 및 비공개 블록체인에서 사용할 수 있도록 한 합의 알고리즘이다. [[텐더민트]]의 전체 합의 프로세스는 [[프랙티컬 비잔틴 장애 허용]]과 거의 유사하다. [[텐더민트]] 프로세스에서의 의도는 [[프랙티컬 비잔틴 장애 허용]]의 Pre-Prepare, Prevote는 Prepare, Precommit은 [[프랙티컬 비잔틴 장애 허용]]의 Commit으로 매칭시키면 이해가 쉽다. [[텐더민트]]는 앞에서 언급하였듯이 [[프랙티컬 비잔틴 장애 허용]]에 [[위임 지분 증명]] 개념을 추가하여 블록체인에 적합한 합의 알고리즘을 개발하였다. 차이점을 요약하면 기존의 [[프랙티컬 비잔틴 장애 허용]]은 하나의 노드가 하나의 투표를 하는 방식으로 투표를 받아 가장 많은 투표를 받은 블록을 승인하지만 [[텐더민트]]는 지분(Stake)을 기반으로 투표를 한다. [[텐더민트]]는 투표를 할 때 Locking 메커니즘을 통해 투표에 참여한 지분을 네트워크에 동결시키고 이를 해제하는 메커니즘을 통해 이중 투표 문제를 막고 지분으로 네트워크를 유지한다. 또한 이중 투표 시도와 같은 블록체인을 공격하려는 악의적인 행위를 하면 지분을 빼앗는 방법으로 기존의 블록체인이 네트워크 공격 노드에 아무런 처벌을 하지 않던 문제(Nothing of Stake)를 해결했다.<ref>아이콘루프, 〈[https://blog.theloop.co.kr/2017/06/21/bft-%EA%B8%B0%EB%B0%98-%ED%95%A9%EC%9D%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/ BFT 기반 합의 알고리즘]〉, 《더 루프 블로그》, 2017-06-21</ref>
 +
 
 +
* '''우로보로스 비잔틴 장애 허용'''
 +
: 애초에 [[카르다노]]는 기존 지분 증명 프로토콜이 가지고 있는 한계, 그 중에서도 특히 Grinding Attack을 막기 위해 설계된 지분증명(POS)기반 합의 프로토콜로 "[[우로보로스]](Ouroboros)"가 있는데, 이 기존의 Ouroboros의 디자인에서 영감을 얻은 새로운 BFT 원장 합의 프로토콜이 [[우로보로스 비잔틴 장애 허용]](Ouroboros-BFT)이다. 콘소시엄형으로 유지되는 카르다노 모드를 위한 작업물이며, Haskell과 Rust구현이 있다. 2018년 12월 18일에 1.4버전이 릴리즈되었으며, Cardano 1.5 릴리스는 Byron 코드 베이스에서 [[탈중앙화]]된 새로운 Shelley 환경으로 이동하게 되는 Cardano 프로토콜에 있어 중요한 이정표가 될 준비 과정에 있다고하며, 구체적으로 두 개의 하드 포크 방식으로 진행된다. 한동안 Byron과 Shelley를 같이 운영하고 사용자를 위한 원활한 전환이 이뤄지게 하려고 채택된 방식이며 업그레이드가 최대한 이른 시일 내 올바른 원칙에 기반하여 적절한 방식으로 완료될 수 있도록 하기 위한 것이다. 우로보로스 비잔틴 장애 허용을 사용하면 Shelley로의 구현 및 배포 시간을 단축할 수 있다.<ref>이승현,〈[https://hamait.tistory.com/1035 BFT 간략 정리 : PBFT , SimpleBFT, SBFT , BFT-SMaRt]〉, 《티스토리》, 2019-03-05</ref>
  
 +
* '''BFT-SMaRt'''
 +
: BFT-SMaRt는 비잔틴 장애를 허용하도록 설계되었다. 비잔틴 장애는 복제 시 편차가 생길 수 있다. 비잔틴 장애는 소프트웨어 버그 또는 복제본을 제어하여 자신의 동작을 제어하는 ​​숙련 된 적으로부터 발생할 수 있다. 따라서 이러한 복제본은 악의적인 복제본으로 처리된다. 비잔틴 장애 외에도 BFT-SMaRt는 서비스 거부 공격(DoS)을 허용하도록 설계되었다. 이러한 유형의 공격은 계산 및 통신이 완료되는 데 걸리는 시간을 늦출 수 있음으로 충돌/결함 복제본과 지연 복제본을 올바르게 구별할 수 없다. 그러나 이러한 계약 프로토콜이 올바른 복제를 제공하려면 악의적인 복제본의 수를 제한해야 한다. 또한, 시스템은 모든 계산 및 통신이 예상 시간 범위 내에서 수행돼야 한다. 앞에서 언급한 모든 가정을 고려할 때 BFT-SMaRt가 올바르게 실행되려면 서비스의 모든 복제본 중 1/3 미만은 언제든지 결함이 있을 수 있다. 따라서 총 복제본 수 <math>N</math>은 <math>N>=3f+1</math>이어야한다. 여기서 <math>f</math>는 결함이 있는 최대 복제본 수다.<ref>jcs47,〈[https://github.com/bft-smart/library/wiki/How-BFT-SMaRt-works How BFT SMaRt works]〉, 《GitHub》, 2018-10-30</ref>
  
 
{{각주}}
 
{{각주}}
  
 
== 참고자료 ==
 
== 참고자료 ==
−
* 바이넌스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명 ]〉, 《바이넌스 아카데미》, 2018-06-12
+
* tyami, 〈[https://m.blog.naver.com/PostView.nhn?blogId=tyami&logNo=221268715771&proxyReferer=https%3A%2F%2Fwww.google.com%2F PBFT(Practical Byzantine Fault Tolerance) 공부해보자]〉, 《네이버 블로그》, 2018-05-05
−
* tyami, 〈[https://m.blog.naver.com/PostView.nhn?blogId=tyami&logNo=221268715771&proxyReferer=https%3A%2F%2Fwww.google.com%2F PBFT(Practical Byzantine Fault Tolerance]〉, 《네이버 블로그》, 2018-05-05
+
* energist, 〈[https://steemit.com/crypto/@energist/blockchain-study-pbft-practical-byzantine-fault-tolerance (Blockchain Study) PBFT(Practical Byzantine Fault Tolerance)]〉, 《스팀잇》, 2018년 4월
 +
* 바이낸스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명]〉, 《바이낸스 아카데미》, 2018-06-12
 +
* 홍석주(Seokju Hong), 〈[https://suckzoo.github.io/tech/2018/02/06/bft-1.html Consensus over Byzantine Fault (1) - The Problem]〉, 《깃허브》, 2018-02-06
 +
* 홍석주(Seokju Hong), 〈[https://suckzoo.github.io/tech/2018/02/19/bft-2.html Consensus over Byzantine Fault (2) - PBFT(1)]〉, 《깃허브》, 2018-02-19
 +
* 홍석주(Seokju Hong), 〈[https://suckzoo.github.io/tech/2018/02/22/bft-3.html Consensus over Byzantine Fault (3) - PBFT(2)]〉, 《깃허브》, 2018-02-22
 +
* 바이낸스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명  ]〉, 《바이낸스 아카데미》, 2019-08-08
 +
* TokenPost, 〈[https://www.tokenpost.kr/terms/13960 PBFT(Practical Byzantine Fault Tolerance, 실용적 비잔틴 장애 허용)]〉, 《TOKENPOST》
 +
* 아이콘루프, 〈[https://blog.theloop.co.kr/2017/06/21/bft-%EA%B8%B0%EB%B0%98-%ED%95%A9%EC%9D%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/ BFT 기반 합의 알고리즘]〉, 《더 루프 블로그》, 2017-06-21
 +
* 〈[https://ko.wikipedia.org/wiki/%EB%B9%84%EC%9E%94%ED%8B%B0%EC%9B%80_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9 비잔티움 장애 허용]〉, 《위키백과》
 +
* 〈[http://itwiki.kr/w/%EB%B9%84%EC%9E%94%ED%8B%B4_%EC%9E%A5%EC%95%A0_%ED%97%88%EC%9A%A9 비잔틴 장애 허용]〉, 《공대위키》
 +
* 이승현,〈[https://hamait.tistory.com/1035 BFT 간략 정리 : PBFT , SimpleBFT, SBFT , BFT-SMaRt]〉, 《티스토리》, 2019-03-05
 +
* jcs47,〈[https://github.com/bft-smart/library/wiki/How-BFT-SMaRt-works How BFT SMaRt works]〉, 《GitHub》, 2018-10-30
  
 
== 같이 보기 ==
 
== 같이 보기 ==
 
* [[합의 알고리즘]]
 
* [[합의 알고리즘]]
 
* [[프랙티컬 비잔틴 장애 허용]]
 
* [[프랙티컬 비잔틴 장애 허용]]
 +
* [[경량 비잔틴 장애 허용]]
 +
* [[위임 프랙티컬 비잔틴 장애 허용]]
 
* [[텐더민트 비잔틴 장애 허용]]
 
* [[텐더민트 비잔틴 장애 허용]]
 +
* [[우로보로스 비잔틴 장애 허용]]
 +
* [[간단한 비잔틴 장애 허용]]
 +
* [[비잔틴 장군의 문제]]
 +
* [[두 장군의 문제]]
 +
* [[위임지분증명]]
 +
* [[텐더민트]]
  
−
{{알고리즘|토막글}}
+
{{합의 알고리즘|검토 필요}}

2022년 1월 6일 (목) 15:07 기준 최신판

비잔틴 장애 허용(BFT; Byzantine Fault Tolerance)이란 장애가 있더라도 전체의 3분의 1을 넘지 않는다면, 시스템이 정상 작동하도록 허용하는 합의 알고리즘이다. 비잔티움 장애 허용이라고도 쓴다. 블록체인의 분산원장 체계는 제대로 돌아가기 위해서 원장을 공유하는 참여자들이 정직하게 행동해야 하며 이를 보장할 방법이 있어야 한다. 만약 악의적인 노드가 존재하여 누군가 속이려 들더라도 모두가 지닌 원장은 같은 내용을 유지해야 하는 방법 또한 존재해야 한다. 이런 골칫거리가 비잔틴 장군의 문제이다.

비잔틴 장애 허용(BFT)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래이다. 비잔틴 장애 허용을 알기 위해서는 두 장군의 문제와 여기서 파생된 비잔틴 장군의 문제를 먼저 알아야 한다. [1]

개요[편집]

비트코인 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 이러한 접근 방식은 항공기의 항법장치 분야에서 처음 적용이 되었다. 항법장치는 항공기의 위치를 제공하는 계기인데, 이것이 올바르게 작동을 하려면 항공기 곳곳에 설치된 센서들이 항상 올바르고 같은 정보를 보내야 한다. 이때 한 센서라도 다른 정보를 주게 된다면 재빨리 다른 센서와 비교해 어느 값을 따를지 결정을 해야 하므로 비잔틴 장군의 문제가 발생하게 된다. 하지만 중요한 것은 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 항법장치가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다. 이러한 설계를 컴퓨터 공학에서 비잔틴 장애 허용(BFT:Bizantine Fault Tolerance)라고 부른다. 당시 학자들은 비잔틴 장애 허용의 가장 기본적인 전제가 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명했다. 항법장치의 센서가 세 개일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 항법장치에서 비잔틴 장애 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러 개 만든 후, 데이터가 필요한 설비에 여러 개의 라인을 통해 송신한다. 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지를 확인하고 상호 비교를 통해 비잔틴 장군의 문제를 해결하여 합의의 무결성을 확보하는 방법으로 설계된 것이다. 결국 데이터의 수와 전송 경로를 동시에 늘려서 하나의 센서로도 여러 개의 센서를 설치한 효과를 얻은 것으로 해석이 되지만 이는 수학적으로 비잔틴 장군의 문제를 해결했다기보다는 현실적으로 문제 발생 확률을 줄인 시도였다. 이처럼 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하도록 만든 시스템 설계이다.

컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며 사토시 나카모토는 항공기 분야의 해결책과 다르게 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 하였다. 블록체인 분야에서의 비잔틴 장애 허용 시스템은 보통 합의 알고리즘이라고 부르게 되며 비트코인은 작업증명이라는 합의구조를 처음 도입하여 비잔틴 장군의 문제를 해결하였다.

초기 솔루션[편집]

1982년 Lamport, Shostak, Pease가 여러 솔루션을 제시했다. 이들은 비잔티움 장군 문제가 충직한 부관(Lieutenant) 모두가 지휘관(Commander)이 내린 명령과 일치하게, 같은 행동을 해야 한다는 "Commander and Leutenants" 문제로 좁혀질 수 있다고 말했다.

  • 첫 번째 솔루션은 전달된 메시지가 위조될 수도 있다는 시나리오를 가정한다. 하지만 이때 배반한 장군의 수가 전체 장군 수의 3분의 1 이상과 같거나 넘지 않는 이상 비잔티움 장애 허용으로 간주한다. 3분의 1 혹은 그 이상의 배반자가 있을 경우는 하나의 지휘관과 두 부관 문제(one Commander and two Lieutenants problem) 문제로 간주할 수 있으며, 즉, 지휘관이 배반자인 경우 해결할 수 없다. 한 명의 배반자 지휘관 A와 두 부관 B, C가 있다고 가정하자. A가 B에게 공격하라고, C에게는 후퇴하라고 명령하는 경우 A의 메시지를 전달받은 B, C는 누가 배반자인지 알 수 없다. A가 아니라 부관 B와 C가 배반했을 수도 있기 때문이다. 따라서 n명의 지휘관이 있고 그중 t명이 배반자인 경우 오직 이고 커뮤니케이션이 동시에 이루어져야만(synchronous; bounded delay) 솔루션이 있다.
  • 두 번째 솔루션은 메시지의 서명이 위조될 수 없다는 전제로 한다. 보안이 중요한 시스템(security-critical system)에서 디지털 서명은(대개 현대의 컴퓨터 시스템에서 공개키 암호화로 구현됨) 임의의 배반자 지휘관이 있는 상황에서 비잔틴 장애 허용을 제공한다. 하지만 안전이 중요한 시스템(safety-critical system)에서 CRCs 등은 대부분의 상황에서 적용될 수 있는 간단한 에러를 찾는 코드를 낮은 비용에 제공하며, 이는 비잔틴 장애와 비잔틴 장애가 아닌 것 모두에 가능하다. 따라서 암호화된 디지털 서명 방식은 별도의 보안 위협이 있지 않은 한 안전이 중요한 시스템에서 좋은 선택은 아니다.
  • 또한 Lamport, Shostak, Pease는 앞서 서술한 두 솔루션 외에도 모든 지휘관이 서로 소통할 수 없는 경우 등 다양한 경우에 관해서도 서술했다.

1980년 비잔틴 장애 허용이 도입된 이후로 Draper's FTP, Honeywell's MMFCS. SRI's SIFT 등 여러 시스템 구조가 디자인되었다.[2]

두 장군의 문제[편집]

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

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

비잔틴 장군의 문제[편집]

비잔틴 장군의 문제

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

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

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

결론적으로 비잔티움 장군 문제는 다양한 시나리오에 광범위하게 적용되고 있는 비잔티움 장애 허용 시스템을 탄생시킨 흥미로운 딜레마이다. 블록체인 산업 외에도, 항공, 우주, 원자력 산업에 비잔티움 장애 허용 시스템이 사용되고 있다. 암호화폐 관점에서, 좋은 합의 메커니즘과 함께 효율적인 네트워크 커뮤니케이션을 확보하는 것은 모든 블록체인 생태계에 필수적이다. 이러한 시스템을 보호하는 데는 지속적인 노력이 필요하며, 현존하는 합의 알고리즘은 몇 가지 한계(확장성과 같은)를 아직 극복하지 못했다. 그런데도, 작업 증명과 지분 증명은 비잔티움 장애 허용 시스템에 관한 아주 흥미로운 접근들이며, 잠재력을 가진 애플리케이션들은 광범위한 혁신을 불러일으키고 있다.[4]

합의 알고리즘[편집]

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

비잔틴 장애 허용 기반 합의 알고리즘[편집]

기존 알고리즘은 가상화폐가 필요하다는 문제 외에도 부분 분기가 일어날 수 있다는 문제가 있다. 간단하게 작업증명 알고리즘을 예로 들면 A와 B블록이 거의 동시에 생성될 경우 각 노드는 자신의 선택에 따라 A와 B블록 중 하나를 선택한다. 이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 된다. 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에서는 적용이 어려운 문제점이 있다.

  • 프랙티컬 비잔틴 장애 허용(PBFT)
프랙티컬 비잔틴 장애 허용 작동방식
프랙티컬 비잔틴 장애 허용(Practical Byzantine Fault Tolerance, PBFT)은 1982년 발표된 "The Byzantine Generals Problem" 논문에서 제안되었으며,[5] 분산시스템이 약속된 행동을 하지 않는 비잔틴 노드가 존재할 수 있는 비동기 시스템일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘이다. 프랙티컬 비잔틴 장애 허용은 기존의 비잔틴 장애 허용(BFT) 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있게 하였다. 합의는 다음과 같이 수행한다.
  1. 리더가 클라이언트들의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에 전파한다.
  2. 리더의 메시지를 받은 노드들은 다른 노드들에서 받은 메시지를 다시 한번 나머지 노드들에 전파한다.
  3. 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메시지(정족수 이상의)가 무엇인지 다른 노드들에 전파한다.
  4. 앞의 과정이 끝나면 모든 노드는 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 된다.
프랙티컬 비잔틴 장애 허용은 두 번의 브로드캐스트 과정을 이용해 비잔틴 리더나 비잔틴 검증 노드가 네트워크 분기를 위해 이상한, 혹은 임의의 메시지를 보내도 네트워크의 모든 노드는 같은 메시지를 가질 수 있게 하였다. 이러한 프랙티컬 비잔틴 장애 허용 알고리즘은 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)를 해결했다.[6]
  • 우로보로스 비잔틴 장애 허용
애초에 카르다노는 기존 지분 증명 프로토콜이 가지고 있는 한계, 그 중에서도 특히 Grinding Attack을 막기 위해 설계된 지분증명(POS)기반 합의 프로토콜로 "우로보로스(Ouroboros)"가 있는데, 이 기존의 Ouroboros의 디자인에서 영감을 얻은 새로운 BFT 원장 합의 프로토콜이 우로보로스 비잔틴 장애 허용(Ouroboros-BFT)이다. 콘소시엄형으로 유지되는 카르다노 모드를 위한 작업물이며, Haskell과 Rust구현이 있다. 2018년 12월 18일에 1.4버전이 릴리즈되었으며, Cardano 1.5 릴리스는 Byron 코드 베이스에서 탈중앙화된 새로운 Shelley 환경으로 이동하게 되는 Cardano 프로토콜에 있어 중요한 이정표가 될 준비 과정에 있다고하며, 구체적으로 두 개의 하드 포크 방식으로 진행된다. 한동안 Byron과 Shelley를 같이 운영하고 사용자를 위한 원활한 전환이 이뤄지게 하려고 채택된 방식이며 업그레이드가 최대한 이른 시일 내 올바른 원칙에 기반하여 적절한 방식으로 완료될 수 있도록 하기 위한 것이다. 우로보로스 비잔틴 장애 허용을 사용하면 Shelley로의 구현 및 배포 시간을 단축할 수 있다.[7]
  • BFT-SMaRt
BFT-SMaRt는 비잔틴 장애를 허용하도록 설계되었다. 비잔틴 장애는 복제 시 편차가 생길 수 있다. 비잔틴 장애는 소프트웨어 버그 또는 복제본을 제어하여 자신의 동작을 제어하는 ​​숙련 된 적으로부터 발생할 수 있다. 따라서 이러한 복제본은 악의적인 복제본으로 처리된다. 비잔틴 장애 외에도 BFT-SMaRt는 서비스 거부 공격(DoS)을 허용하도록 설계되었다. 이러한 유형의 공격은 계산 및 통신이 완료되는 데 걸리는 시간을 늦출 수 있음으로 충돌/결함 복제본과 지연 복제본을 올바르게 구별할 수 없다. 그러나 이러한 계약 프로토콜이 올바른 복제를 제공하려면 악의적인 복제본의 수를 제한해야 한다. 또한, 시스템은 모든 계산 및 통신이 예상 시간 범위 내에서 수행돼야 한다. 앞에서 언급한 모든 가정을 고려할 때 BFT-SMaRt가 올바르게 실행되려면 서비스의 모든 복제본 중 1/3 미만은 언제든지 결함이 있을 수 있다. 따라서 총 복제본 수 은 이어야한다. 여기서 는 결함이 있는 최대 복제본 수다.[8]

각주[편집]

  1. ↑ 1.0 1.1 바이낸스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이낸스 아카데미》, 2018-06-12
  2. ↑ 〈비잔티움 장애 허용〉, 《위키백과》
  3. ↑ tyami, 〈PBFT(Practical Byzantine Fault Tolerance) 공부해보자〉, 《네이버 블로그》, 2018-05-05
  4. ↑ 바이낸스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이낸스 아카데미》, 2019-08-08
  5. ↑ 〈비잔틴 장애 허용〉, 《공대위키》
  6. ↑ 아이콘루프, 〈BFT 기반 합의 알고리즘〉, 《더 루프 블로그》, 2017-06-21
  7. ↑ 이승현,〈BFT 간략 정리 : PBFT , SimpleBFT, SBFT , BFT-SMaRt〉, 《티스토리》, 2019-03-05
  8. ↑ jcs47,〈How BFT SMaRt works〉, 《GitHub》, 2018-10-30

참고자료[편집]

같이 보기[편집]


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

블록체인 : 블록체인 기술, 합의 알고리즘 □■⊕, 암호 알고리즘, 알고리즘, 블록체인 플랫폼, 블록체인 솔루션, 블록체인 서비스
작업증명 경과시간증명(PoET) • 균형작업증명(ePoW) • 뻐꾸기 사이클 • 스펙터 • 온라인증명(PoO) • 유용한 작업증명(PoUW) • 이중작업증명(DPoW) • 작업증명(PoW) • 지연작업증명(DPoW) • 캐스퍼 알고리즘 • 프로그작업증명(ProgPoW) • 활동증명(PoA)
지분증명 담보지분증명(BPoS) • 리스지분증명(LPoS) • 무작위 지분증명(rPoS) • 복제증명(PoRep) • 시간소각 지분증명(ABPoS) • 우로보로스 지분증명(OPoS) • 유동지분증명(LPoS) • 익명지분증명 • 지분속도증명(PoSV) • 지분시간증명(PoST) • 지분작업증명(PoSW) • 지분증명(PoS) • 확률적 지분증명(SPoS)
위임지분증명 마스터노드 지분증명(MPoS) • 번앤언 위임지분증명(B&E DPoS) • 슈퍼노드 지분증명(SPoS) • 위임지분서비스증명(DPoSS) • 위임지분증명(DPoS) • 이중위임지분증명(DDPoS) • 인공지능 위임지분증명(AI DPoS) • 포뮬레이션증명(PoF) • 포크능력증명(PoF) • 하이퍼 위임지분증명(Hyper-DPoS)
비잔틴 장애 허용 간단한 비잔틴 장애 허용 • 경량 비잔틴 장애 허용(LBFT) • 라케시스 • 루프 장애 허용 • 미네르바 • 비잔틴 장애 허용(BFT) • 수정 연합 비잔틴 동의(mFBA) • 심센서스 • 아이작(ISAAC) • 연합 비잔틴 동의(FBA) • 우로보로스 비잔틴 장애 허용(OBFT) • 위임 프랙티컬 비잔틴 장애 허용(dPBFT) • 프랙티컬 비잔틴 장애 허용(PBFT) • 프랙티컬 비잔틴 장애 허용 플러스(PBFT+) • 텐더민트 비잔틴 장애 허용(TBFT) • 프리즘
기타 deb 합의 알고리즘 • 권위증명(PoA) • 기여도증명(PoD) • 네트워크증명(PoN) • 대역폭증명 • 두뇌증명(PoB) • 람다 합의 알고리즘 • 명성보증금증명 • 서비스증명(PoS) • 성능증명(PoP) • 소각증명(PoB) • 시공간증명(PoSt) • 시청증명(PoV) • 신뢰성증명(PoB) • 역사증명(PoH) • 오벨리스크 • 용량증명(PoC) • 저장증명(PoS) • 전문성증명(PoE) • 중요도증명(PoI) • 지지증명(PoS) • 참여증명(PoE) • 탄소감축증명(PoCR) • 트레이딩증명(PoT) • 흐름증명(PoF)
위키 : 자동차, 교통, 지역, 지도, 산업, 기업, 단체, 업무, 생활, 쇼핑, 블록체인, 암호화폐, 인공지능, 개발, 인물, 행사, 일반
원본 주소 "http://wiki1.kr/index.php?title=비잔틴_장애_허용&oldid=538161"