의견.png

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

해시넷
이동: 둘러보기, 검색
잔글
2번째 줄: 2번째 줄:
  
 
비잔틴 장애 허용(BFT)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래이다. 비잔틴 장애 허용을 알기 위해서는 두 장군의 문제와 여기서 파생된 비잔틴 장군의 문제를 먼저 알아야 한다. <ref name="바이낸스">바이낸스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명  ]〉, 《바이낸스 아카데미》, 2018-06-12</ref>
 
비잔틴 장애 허용(BFT)은 두 장군 문제(Two Generals Problem)를 일반화한 문제인 비잔티 장군 문제(Byzantine Generals Problem)로부터 파생된 장애 허용 분야 연구의 한 갈래이다. 비잔틴 장애 허용을 알기 위해서는 두 장군의 문제와 여기서 파생된 비잔틴 장군의 문제를 먼저 알아야 한다. <ref name="바이낸스">바이낸스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명  ]〉, 《바이낸스 아카데미》, 2018-06-12</ref>
 +
 +
==개요==
 +
[[비트코인]] 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군들 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 이러한 접근 방식은 항공기의 항법장치 분야에서 처음 적용이 되었다. 항법장치는 항공기의 위치를 제공하는 계기인데, 이것이 올바르게 작동을 하려면 항공기 곳곳에 설치된 센서들이 항상 올바르고 같은 정보를 보내야 한다. 이때 한 센서라도 다른 정보를 주게 된다면 재빨리 다른 센서와 비교해 어느 값을 따를지 결정을 해야 하기 때문에 비잔틴 장군의 문제가 발생하게 된다. 하지만 중요한 것은 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 항법장치가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다. 이러한 설계를 컴퓨터 공학에서 '''비잔틴 장애 허용'''(BFT:Bizantine Fault Tolerance)라고 부른다. 당시 학자들은 비잔틴 장애 허용의 가장 기본적인 전제가 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명했다. 항법장치의 센서가 세 개 일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 항법장치에서 비잔틴 장애 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러 개 만든 후, 데이터가 필요한 설비에 여러 개의 라인을 통해 송신한다. 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지 여부를 확인하고 상호 비교를 통해 비잔틴 장군의 문제를 해결하여 합의의 무결성을 확보하는 방법으로 설계된 것이다. 결국 데이터의 수와 전송 경로를 동시에 늘려서 하나의 센서로도 여러 개의 센서를 설치한 효과를 얻은 것으로 해석이 되지만 이는 수학적으로 비잔틴 장군의 문제를 해결 했다기보다는 현실적으로 문제 발생 확률을 줄인 시도였다. 이처럼 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하도록 만든 시스템 설계이다.
 +
 +
컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며 [[사토시 나카모토]]는 항공기 분야의 해결책과 다르게 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 하였다. 블록체인 분야에서의 비잔틴 장애 허용 시스템은 보통 [[합의 알고리즘]]이라고 부르게 되며 [[비트코인]]은 [[PoW]]라는 합의구조를 처음 도입하여 비잔틴 장군의 문제를 해결하였다.
  
 
==두 장군의 문제==
 
==두 장군의 문제==
−
'''두 장군의 문제'''(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년 [[래슬리 램포트]], [[마샬 피즈]]가 함께 쓴 논문에서 소개 된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. 비잔틴 장군의 문제는 광활한 영토 각 지역마다 장군들이 통치하는 것을 가정한다. 이웃나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 높아지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.
+
'''[[비잔틴 장군의 문제]]'''(Byzantine Generals Problem)는 1982년 [[래슬리 램포트]], [[마샬 피즈]]가 함께 쓴 논문에서 소개 된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. 비잔틴 장군의 문제는 광활한 영토 각 지역마다 장군들이 통치하는 것을 가정한다. 이웃나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 높아지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.
  
 
이러한 비잔틴 장군의 문제를 [[블록체인]]에 적용해 본다면, 각 장군들은 하나의 [[노드]]가 되며, 노드들은 현 시스템 상태에 합의를 달성할 수 있는 방법을 찾아야 한다. 분산화 된 네트워크의 대다수의 참가자들은 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 하는 것이다. 그러므로 분산화 된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 3분의 2 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것이다. 이는 네트워크 참여자 대다수가 악의적으로 행동하기로 결정할 경우, 시스템이 실패하거나 공격을 당할 수 있음을 의미하게 된다.<ref name="바이낸스"></ref> [[비트코인]] 상에서는 참여자가 수 만 명이 될 수 있기 때문에 [[사토시 나카모토]] 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.
 
이러한 비잔틴 장군의 문제를 [[블록체인]]에 적용해 본다면, 각 장군들은 하나의 [[노드]]가 되며, 노드들은 현 시스템 상태에 합의를 달성할 수 있는 방법을 찾아야 한다. 분산화 된 네트워크의 대다수의 참가자들은 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 하는 것이다. 그러므로 분산화 된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 3분의 2 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것이다. 이는 네트워크 참여자 대다수가 악의적으로 행동하기로 결정할 경우, 시스템이 실패하거나 공격을 당할 수 있음을 의미하게 된다.<ref name="바이낸스"></ref> [[비트코인]] 상에서는 참여자가 수 만 명이 될 수 있기 때문에 [[사토시 나카모토]] 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.
  
−
“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야하며, 또 모두가 X를 안다는 사실을 우리 모두가 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 [[사토시 나카모토]]와 [[비트코인]] 개발 작업을 협업했던 [[제임스 A 도날드]]가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도날드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘[[두 장군의 문제]]’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘[[비잔틴 장군의 문제]]’로 확장이 된다.  
+
“모두가 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>
−
[[비트코인]] 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군들 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 이러한 접근 방식은 항공기의 항법장치 분야에서 처음 적용이 되었다. 항법장치는 항공기의 위치를 제공하는 계기인데, 이것이 올바르게 작동을 하려면 항공기 곳곳에 설치된 센서들이 항상 올바르고 같은 정보를 보내야 한다. 이때 한 센서라도 다른 정보를 주게 된다면 재빨리 다른 센서와 비교해 어느 값을 따를지 결정을 해야 하기 때문에 비잔틴 장군의 문제가 발생하게 된다. 하지만 중요한 것은 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 항법장치가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다. 이러한 설계를 컴퓨터 공학에서 '''비잔틴 장애 허용'''(BFT:Bizantine Fault Tolerance)라고 부른다. 당시 학자들은 비잔틴 장애 허용의 가장 기본적인 전제가 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명했다. 항법장치의 센서가 세 개 일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 항법장치에서 비잔틴 장애 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러 개 만든 후, 데이터가 필요한 설비에 여러 개의 라인을 통해 송신한다. 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지 여부를 확인하고 상호 비교를 통해 비잔틴 장군의 문제를 해결하여 합의의 무결성을 확보하는 방법으로 설계된 것이다. 결국 데이터의 수와 전송 경로를 동시에 늘려서 하나의 센서로도 여러 개의 센서를 설치한 효과를 얻은 것으로 해석이 되지만 이는 수학적으로 비잔틴 장군의 문제를 해결 했다기보다는 현실적으로 문제 발생 확률을 줄인 시도였다. 이처럼 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하도록 만든 시스템 설계이다.
 
−
 
 
−
컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며 [[사토시 나카모토]]는 항공기 분야의 해결책과 다르게 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 하였다. 블록체인 분야에서의 비잔틴 장애 허용 시스템은 보통 [[합의 알고리즘]]이라고 부르게 되며 [[비트코인]]은 [[PoW]]라는 합의구조를 처음 도입하여 비잔틴 장군의 문제를 해결하였다.
 
  
 
===합의 알고리즘===
 
===합의 알고리즘===
−
'''합의 알고리즘'''은 블록체인 네트워크에서 합의를 달성하는 메커니즘으로 정의가 가능하다. 가장 일반적인 예로 [[비트코인]]의 [[작업증명]]방식(PoW, Proof of Work)을 들 수 있다.블록체인 중 가장 처음 제시된 비트코인의 합의 알고리즘 중 작업증명방식(Proof of Work, POW)는 타임스탬프(Timestamp)와 서명(Sign, 블록체인에서는 Key)을 통해 이 문제를 해결한다. 1) 장군은 메시지를 보내기 위해 10분의 시간을 가진다. 2) 메시지는 모든 장군의 메시지와 메시지를 보내기 위해 10분을 들였다는 증거를 포함한다. 다음의 규칙이 추가  됨에 따라 중간의 비잔틴 장군이 존재하더라도 다른 장군들은 이 장군이 거짓임을 밝혀낼 수 있다. 혹은 초기에 메시지를 받은 장군이 존재하더라도 앞선 시나리오처럼 정직한 장군들이 성을 함락할 수 있게 된다. 비트코인을 설계할 당시 [[사토시 나카모토]]는 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다. 우선 비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 룰을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이같은 여러 숫자들을 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했는데 퍼즐을 푸는 과정이 곧 PoW이며 수학 퍼즐이 풀리면 블록이 만들어지며 이를 [[채굴]]이라고 한다. PoW를 수행해 퍼즐이 풀렸다면 결국 블록은 부정이 없도록 각종 룰을 지킨 정상 거래들을 모아 정상적인 방법으로 만든 원장이라는 의미이다. 마지막에 나온 블록의 고유 값이 정상이면 계산과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 좋다는 의미이다. 비트코인은 결국 PoW를 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. PoW를 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요 없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행과 중앙기관의 역할은 이러한 비트코인 시스템 내에서 사라졌으며 비잔틴 장애 허용을 달성하는 가장 똑똑한 접근으로 여겨지고 있다.
+
'''[[합의 알고리즘]]'''은 블록체인 네트워크에서 합의를 달성하는 메커니즘으로 정의가 가능하다. 가장 일반적인 예로 [[비트코인]]의 [[작업증명]](PoW, Proof of Work)을 들 수 있다.블록체인 중 가장 처음 제시된 비트코인의 합의 알고리즘 중 작업증명방식(Proof of Work, POW)는 타임스탬프(Timestamp)와 서명(Sign, 블록체인에서는 Key)을 통해 이 문제를 해결한다. '장군은 메시지를 보내기 위해 10분의 시간을 가지며, 메시지는 모든 장군의 메시지와 메시지를 보내기 위해 10분을 들였다는 증거를 포함한다.' 라는 규칙이 추가됨에 따라 중간의 비잔틴 장군이 존재하더라도 다른 장군들은 이 장군이 거짓임을 밝혀낼 수 있다. 혹은 초기에 메시지를 받은 장군이 존재하더라도 앞선 시나리오처럼 정직한 장군들이 성을 함락할 수 있게 된다. 비트코인을 설계할 당시 [[사토시 나카모토]]는 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다. 우선 비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 룰을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이같은 여러 숫자들을 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했는데 퍼즐을 푸는 과정이 곧 작업증명이며 수학 퍼즐이 풀리면 블록이 만들어지며 이를 [[채굴]]이라고 한다. 작업증명을  수행해 퍼즐이 풀렸다면 결국 블록은 부정이 없도록 각종 룰을 지킨 정상 거래들을 모아 정상적인 방법으로 만든 원장이라는 의미이다. 마지막에 나온 블록의 고유 값이 정상이면 계산과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 좋다는 의미이다. 비트코인은 결국 작업증명을 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. 작업증명을 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요 없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행과 중앙기관의 역할은 이러한 비트코인 시스템 내에서 사라졌으며 비잔틴 장애 허용을 달성하는 가장 똑똑한 접근으로 여겨지고 있다.
  
 
{{각주}}
 
{{각주}}
32번째 줄: 34번째 줄:
 
* 홍석주(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/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
 
* 홍석주(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
  
 
== 같이 보기 ==
 
== 같이 보기 ==

2019년 8월 12일 (월) 09:49 판

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

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

개요

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

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

두 장군의 문제

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

각주

  1. ↑ 1.0 1.1 바이낸스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이낸스 아카데미》, 2018-06-12
  2. ↑ tyami, 〈PBFT(Practical Byzantine Fault Tolerance) 공부해보자〉, 《네이버 블로그》, 2018-05-05
  3. ↑ 바이낸스 아카데미, 〈비잔티움 장애 허용 설명 〉, 《바이낸스 아카데미》, 2019-08-08

참고자료

같이 보기


  의견.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://wiki.hash.kr/index.php?title=비잔틴_장애_허용&oldid=127980"