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

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

위키원
이동: 둘러보기, 검색
잔글 (92.118.234.18(토론)의 편집을 Asadal의 마지막 판으로 되돌림)
1번째 줄: 1번째 줄:
* 부정적 평가: 로커스체인은 판매 당시 절대 손실을 보지 않는다며, 사우디 아람코 석유기업과 빈살만 왕세자, 청와대까지 개입되어 있다고 언급하며 허위사실로 코인을 판매하였다는 주장이 있다(블룸테크놀로지에서는 사실무근이라고 함). 현재 로커스체인 피해자들의 단체소송이 진행중에 있다.<ref>피치원 미디어,<[http://www.pitchone.co.kr/12352/ 피치원단독석유코인 ‘로커스체인’800억원대 사기코인 논란,투자피해자 50여명 검찰고소]> </ref>  또한, 회사 월급이 밀리고 직원 70%가 1년새 나가버린 회사이며, "어떻게든 한탕 하려고 하는 게 아니냐."는 부정적 평가도 과거 있었다. krcryptoanalyst , 〈[https://steemit.com/kr/@krcryptoanalyst/ceo-cofounder  로커스체인의 CEO와 COFOUNDER가 대표와 사장으로 있는 '블루사이드'와 로커스체인 추가 정보 (긴 글 주의)]〉, 《스팀잇》, 2018-05-10
+
'''비잔틴 장애 허용'''<!--비잔티움 장애 허용, 비잔틴장애허용, 비잔티움장애허용, 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>
  
== 평가에 관한 참고자료 ==
+
==개요==
* 로커스체인 사기피해자 카페: https://cafe.naver.com/locusvictim
+
[[비트코인]] 이전까지, 컴퓨터 공학에서는 비잔틴 장군 문제를 극복하는 방법으로 장군 중 잘못된 메시지를 보내는 경우에도 전체 시스템은 돌아가도록 하는 방향으로 접근했다. 이러한 접근 방식은 항공기의 항법장치 분야에서 처음 적용이 되었다. 항법장치는 항공기의 위치를 제공하는 계기인데, 이것이 올바르게 작동을 하려면 항공기 곳곳에 설치된 센서들이 항상 올바르고 같은 정보를 보내야 한다. 이때 한 센서라도 다른 정보를 주게 된다면 재빨리 다른 센서와 비교해 어느 값을 따를지 결정을 해야 하므로 비잔틴 장군의 문제가 발생하게 된다. 하지만 중요한 것은 여기서 한 센서라도 잘못된 정보를 준다고 하더라도 항법장치가 멈추지 않게 계속 작동할 수 있도록 설계가 되어야 한다. 이러한 설계를 컴퓨터 공학에서 '''비잔틴 장애 허용'''(BFT:Bizantine Fault Tolerance)라고 부른다. 당시 학자들은 비잔틴 장애 허용의 가장 기본적인 전제가 전체 참여자의 최소 3분의 2는 정상 작동하는 선량한 참여자여야 한다는 점을 규명했다. 항법장치의 센서가 세 개일 때 두 개가 정상 작동한다면 하나의 신호를 무시해도 승객들은 무사히 목적지에 도착할 수 있게 된다. 항법장치에서 비잔틴 장애 허용 방법은 하나의 센서에서 동일한 내용의 데이터를 여러 개 만든 후, 데이터가 필요한 설비에 여러 개의 라인을 통해 송신한다. 이렇게 여러 라인을 통해 받은 동일한 데이터에 대해 이상 신호가 발생하는지를 확인하고 상호 비교를 통해 비잔틴 장군의 문제를 해결하여 합의의 무결성을 확보하는 방법으로 설계된 것이다. 결국 데이터의 수와 전송 경로를 동시에 늘려서 하나의 센서로도 여러 개의 센서를 설치한 효과를 얻은 것으로 해석이 되지만 이는 수학적으로 비잔틴 장군의 문제를 해결했다기보다는 현실적으로 문제 발생 확률을 줄인 시도였다. 이처럼 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패를 막기 위한 시스템으로 비잔틴 장애 허용 시스템은 일부 노드가 고장 나거나 악의적으로 행동하더라도 계속 작동이 가능하도록 만든 시스템 설계이다.
  
*강서구 기자,<[https://www.thescoop.co.kr/news/articleView.html?idxno=38464 ‘석유 코인’ 로커스체인은 왜 송사에 휘말렸나]>,더스쿠프, 2020-03-04
+
컴퓨터 공학과 마찬가지로 블록체인에서도 비잔틴 장애 허용을 달성하는 다양한 접근들이 존재하며 [[사토시 나카모토]]는 항공기 분야의 해결책과 다르게 참여자 모두가 가장 최신의 원장을 동일하게 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 하였다. 블록체인 분야에서의 비잔틴 장애 허용 시스템은 보통 [[합의 알고리즘]]이라고 부르게 되며 [[비트코인]]은 [[작업증명]]이라는 합의구조를 처음 도입하여 비잔틴 장군의 문제를 해결하였다.  
  
*이정일 기자,<[https://www.onnews.or.kr/2020/06/%EA%B0%80%EC%83%81%ED%99%94%ED%8F%90-%EB%A1%9C%EC%BB%A4%EC%8A%A4%EC%B2%B4%EC%9D%B8-%EC%82%AC%EA%B8%B0%EC%82%AC%EA%B1%B4-%ED%94%BC%ED%95%B4%EC%9E%90%EB%93%A4-%EC%97%84%EB%B2%8C%ED%83%84%EC%9B%90/ 가상화폐 로커스체인 사기사건 피해자들 엄벌탄원서를 검찰에 제출]>,대한장애인신문, 2020-06-19
+
==초기 솔루션==
 
+
1982년 Lamport, Shostak, Pease가 여러 솔루션을 제시했다. 이들은 비잔티움 장군 문제가 충직한 부관(Lieutenant) 모두가 지휘관(Commander)이 내린 명령과 일치하게, 같은 행동을 해야 한다는 "Commander and Leutenants" 문제로 좁혀질 수 있다고 말했다.
*김선민 기자,<[http://m.newsway.co.kr/news/view?tp=1&ud=2019121808321366046 가상화폐 로커스체인 투자자들, 개발사 대표 사기·배임 혐의로 고소]>,뉴스웨이,2019-12-24
 
 
 
*장익창 기자,<[http://www.bizhankook.com/bk/article/19146 9000억대 사기 밸류인베스트 투자 연루업체 이번엔 '가상화폐' 사기 의혹 신라젠 주가조작 혐의 이어 '로커스 체인' 도마 위… 블룸 측 "활성화 위해 최대한 노력".]>,비즈한국,2019-12-17
 
  
*방윤영 기자,<[https://www.google.com/amp/s/m.mt.co.kr/renew/view_amp.html%3fno=2019121714254348415 7000억대 사기 'VIK파생피해' 로커스체인 고소]>,머니투데이,2019-12-17
+
* 첫 번째 솔루션은 전달된 메시지가 위조될 수도 있다는 시나리오를 가정한다. 하지만 이때 배반한 장군의 수가 전체 장군 수의 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) 솔루션이 있다.
  
*추광규 기자,<[http://m.shinmoongo.net/132863 ‘문재인 대통령 해외특보’ 주장하던 여성 정체 알고보니....]>,신문고뉴스,2019-12-17
+
* 두 번째 솔루션은 메시지의 서명이 위조될 수 없다는 전제로 한다. 보안이 중요한 시스템(security-critical system)에서 디지털 서명은(대개 현대의 컴퓨터 시스템에서 공개키 암호화로 구현됨) 임의의 배반자 지휘관이 있는 상황에서 비잔틴 장애 허용을 제공한다. 하지만 안전이 중요한 시스템(safety-critical system)에서 CRCs 등은 대부분의 상황에서 적용될 수 있는 간단한 에러를 찾는 코드를 낮은 비용에 제공하며, 이는 비잔틴 장애와 비잔틴 장애가 아닌 것 모두에 가능하다. 따라서 암호화된 디지털 서명 방식은 별도의 보안 위협이 있지 않은 한 안전이 중요한 시스템에서 좋은 선택은 아니다.
  
*김광일 기자,<[http://www.pitchone.co.kr/12352/ [피치원단독]석유코인 ‘로커스체인’800억원대 사기코인 논란,투자피해자 50여명 검찰고소]>,피치원미디어,2019-12-17
+
* 또한 Lamport, Shostak, Pease는 앞서 서술한 두 솔루션 외에도 모든 지휘관이 서로 소통할 수 없는 경우 등 다양한 경우에 관해서도 서술했다.
  
*시민단체 약탈경제반대행동 페이스북, <[https://m.facebook.com/permalink.php?story_fbid=1709226042546788&id=707725899363479 로커스체인 사건 고소 기자회견]>,2019-12-17
+
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>
  
*원성훈 기자, <[http://www.newsworks.co.kr/news/articleView.html?idxno=458888 피해자모임 "부부사기꾼, 총 320억 다단계 합작에도 징역 1~4년 뿐"]>,뉴스웍스,2020-05-28
+
==두 장군의 문제==
 +
'''[[두 장군의 문제]]'''(Two Generals Problem)는 1972년 등장한 일종의 가상 실험이다. 이 실험에서 가정은 두 아군 부대의 장군 A와 B가 적군이 점령한 도시 양옆에 주둔한 상황이며 두 장군은 적군을 점령하기 위해 두 부대가 같은 날, 같은 시각에 공격하려 한다. 이때 연락을 주고받아야 하는데 이를 담당하는 연락병은 직접 적군의 도시를 통과해야 하며 이러한 연락병이 가진 메시지는 항상 적군에게 뺏길 위험이 존재한다는 가정하에 진행이 된다.
  
*박기영 기자,<[https://m.etoday.co.kr/view.php?idxno=1892348#cb [피플] 이민석 변호사 “사기꾼은 진화 중…솜방망이 처벌 강화ㆍ검경 합동 수사로 막아야”]>,이투데이,2020-05-10
+
장군 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>
  
*이가영 기자,<[https://n.news.naver.com/article/025/0002990675 “이철은 조희팔급 사기꾼”…VIK 피해자들, MBC에 사과 요구]>,중앙일보,2020-04-06
+
==비잔틴 장군의 문제==
 +
[[파일:비잔틴 장군 문제.jpg|썸네일|500픽셀|'''비잔틴 장군의 문제''']]
 +
'''[[비잔틴 장군의 문제]]'''(Byzantine Generals Problem)는 1982년 [[래슬리 램포트]], [[마샬 피즈]]가 함께 쓴 논문에서 소개된 이후 컴퓨터 공학의 고전적인 난제로 꼽히는 문제로 두 장군의 문제에서 더 나아가 장군이 여러 명인 상황을 가정한 것이다. 비잔틴 장군의 문제는 광활한 영토 지역마다 장군들이 통치하는 것을 가정한다. 이웃 나라 공격이 성공하려면 같은 날, 같은 시각에 모든 장군이 이끄는 병력을 집중시켜야 하는데, 이러한 목적을 달성하기 위한 메시지가 올바르게 전달되지 못하면 병력이 분산되어 공격은 실패하게 된다. 또한 장군들 가운데 배신자가 있다면 이러한 가능성은 더욱 커지게 된다. 여기서 비잔틴 장군 문제의 핵심은 동일한 내용의 메시지를 장군들끼리 공유할 수 있는 방법을 찾는 것이다.
  
*원성훈 기자,<[http://www.newsworks.co.kr/news/articleView.html?idxno=432460 2000억 사기 사건에 2년 6개월 실형... '솜방망이 처벌' 규탄]>,뉴스웍스,2020-02-12
+
이러한 비잔틴 장군의 문제를 [[블록체인]]에 적용해 본다면, 각 장군은 하나의 [[노드]]가 되며, 노드들은 현 시스템 상태에 합의를 달성할 수 있는 방법을 찾아야 한다. 분산화된 네트워크의 대다수의 참가자는 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 한다. 그러므로 분산화된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 3분의 2 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것이다. 이는 네트워크 참여자 대다수가 악의적으로 행동하기로 할 경우, 시스템이 실패하거나 공격을 당할 수 있음을 의미하게 된다.<ref name="바이낸스"></ref> [[비트코인]] 상에서는 참여자가 수만 명이 될 수 있기 때문에 [[사토시 나카모토]] 입장에서는 두 장군의 문제보다 비잔틴 장군 문제가 직접적인 장애물이었다.
  
*원성훈 기자,<[http://www.newsworks.co.kr/news/articleView.html?idxno=446058 V.I.K. 피해자들 "1조원대 사기꾼 이철, 황당한 잡설...모집책·비호세력 전원 구속하라"]>,뉴스웍스,2020-04-06
+
“모두가 X를 안다는 사실로는 충분하지 않습니다. 모두가 X를 안다는 사실도 모두가 알아야 하며, 또 모두가 X를 안다는 사실을 우리가 모두 다 안다는 사실도 전원이 알아야 한다. 이는 비잔틴 장군의 문제처럼, 분산 데이터 시스템에서 오래된 난제이다.” 이는 2008년 11월 13일 [[사토시 나카모토]]와 [[비트코인]] 개발 작업을 협업했던 [[제임스 A 도널드]]가 사토시에게 보낸 이메일의 일부 내용이다. 제임스 A 도널드가 보낸 말꼬리를 계속 잡는 문구는 컴퓨터 네트워크 분야에서 주로 다루는 ‘[[두 장군의 문제]]’(Two Generals Problem)에서 출발한다. 이후 이 문제는 ‘[[비잔틴 장군의 문제]]’로 확장이 된다.
  
*인터넷뉴스신문고 블로그,<[https://m.blog.naver.com/3658290/222007420034 가상화폐 ‘로커스체인’ 피해자들...“가담자 전원 구속해야”]>,인터넷뉴스신문고,2020-06ㅋ21
+
결론적으로 비잔티움 장군 문제는 다양한 시나리오에 광범위하게 적용되고 있는 비잔티움 장애 허용 시스템을 탄생시킨 흥미로운 딜레마이다. 블록체인 산업 외에도, 항공, 우주, 원자력 산업에 비잔티움 장애 허용 시스템이 사용되고 있다. 암호화폐 관점에서, 좋은 합의 메커니즘과 함께 효율적인 네트워크 커뮤니케이션을 확보하는 것은 모든 블록체인 생태계에 필수적이다. 이러한 시스템을 보호하는 데는 지속적인 노력이 필요하며, 현존하는 합의 알고리즘은 몇 가지 한계(확장성과 같은)를 아직 극복하지 못했다. 그런데도, 작업 증명과 지분 증명은 비잔티움 장애 허용 시스템에 관한 아주 흥미로운 접근들이며, 잠재력을 가진 애플리케이션들은 광범위한 혁신을 불러일으키고 있다.<ref>바이낸스 아카데미, 〈[https://www.binance.vision/ko/blockchain/byzantine-fault-tolerance-explained 비잔티움 장애 허용 설명  ], 《바이낸스 아카데미》, 2019-08-08</ref>
  
*김경탁 기자,<[http://www.newbc.kr/news/articleView.html?idxno=9168 [이슈집중] 채널A발 ‘유시민 구지가’ 사건…이철 그리고 VIK에 대한 모든 것]>, 뉴비씨, 2020-04-01
+
==합의 알고리즘==
 +
'''[[합의 알고리즘]]'''은 블록체인 네트워크에서 합의를 달성하는 메커니즘으로 정의할 수 있다. 가장 일반적인 예로 [[비트코인]]의 [[작업증명]](PoW, Proof of Work)을 들 수 있다. 블록체인 중 가장 처음 제시된 비트코인의 합의 알고리즘 중 작업증명방식(Proof of Work, POW)는 타임 스탬프(Timestamp)와 서명(Sign, 블록체인에서는 Key)을 통해 이 문제를 해결한다. '장군은 메시지를 보내기 위해 10분의 시간을 가지며, 메시지는 모든 장군의 메시지와 메시지를 보내기 위해 10분을 들였다는 증거를 포함한다.'라는 규칙이 추가됨에 따라 중간의 비잔틴 장군이 존재하더라도 다른 장군들은 이 장군이 거짓임을 밝혀낼 수 있다. 혹은 초기에 메시지를 받은 장군이 존재하더라도 앞선 시나리오처럼 정직한 장군들이 성을 함락할 수 있게 된다. 비트코인을 설계할 당시 [[사토시 나카모토]]는 참여자 모두가 가장 최신의 원장을 같이 보유할 수 있다는 점을 수학적으로 보장할 수 있도록 했다. 우선 비트코인은 참여자가 돈을 받는 순간부터 보내는 순간까지 지켜야 할 기본적인 규정을 특정한 숫자로 표현되도록 설계해놓고 있다. 사토시는 새로운 블록을 만들 때 이런 여러 숫자를 모아 이를 기초로 새로 만들 블록의 고유번호를 찾는 일종의 퍼즐 게임을 풀도록 했는데 퍼즐을 푸는 과정이 곧 작업증명이며 수학 퍼즐이 풀리면 블록이 만들어지며 이를 [[채굴]]이라고 한다. 작업증명을  수행해 퍼즐이 풀렸다면 결국 블록은 부정이 없도록 각종 규정을 지킨 정상 거래를 모아 정상적인 방법으로 만든 원장이라는 의미이다. 마지막에 나온 블록의 고윳값이 정상이면 계산과정에 들어간 모든 숫자 역시 올바른 값이므로 수학적으로도 이 값을 수용해도 좋다는 의미이다. 비트코인은 결국 작업증명을 거친 블록을 받아들이는 방식의 합의 구조를 갖추고 있다. 작업증명을 거친 블록을 실시간 공유함으로써 참여자들은 다른 장군들이 부정을 저질렀는지 걱정할 필요 없이 결국 모두가 항상 같은 원장 상태에 도달해 있게 되는 셈이다. 은행과 중앙기관의 역할은 이러한 비트코인 시스템 내에서 사라졌으며 비잔틴 장애 허용을 달성하는 가장 똑똑한 접근으로 여겨지고 있다.
  
*Krcryptoanalyst,<[https://steemit.com/kr/@krcryptoanalyst/xx-x 로XX체X 의문 정리+추가로 나온 의문점]>, 스팀잇
+
===비잔틴 장애 허용 기반 합의 알고리즘===
 +
기존 알고리즘은 가상화폐가 필요하다는 문제 외에도 부분 분기가 일어날 수 있다는 문제가 있다. 간단하게 작업증명 알고리즘을 예로 들면 A와 B블록이 거의 동시에 생성될 경우 각 노드는 자신의 선택에 따라 A와 B블록 중 하나를 선택한다. 이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 된다. 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에서는 적용이 어려운 문제점이 있다.
  
*Krcryptoanalyst,<[https://steemit.com/kr/@krcryptoanalyst/2raghn 충격 코인 리뷰 로커스체인 필독(블룸테크놀로지,코인지니어스)]>,스팀잇
+
* '''프랙티컬 비잔틴 장애 허용'''(PBFT)
 +
[[파일: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) 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있게 하였다. 합의는 다음과 같이 수행한다.
  
*토큰포스트,<[https://www.tokenpost.kr/article-19199 로커스체인 개발사 블룸, 코인사기 의혹]>,토큰포스트
+
# 리더가 클라이언트들의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에 전파한다.
 +
# 리더의 메시지를 받은 노드들은 다른 노드들에서 받은 메시지를 다시 한번 나머지 노드들에 전파한다.
 +
# 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메시지(정족수 이상의)가 무엇인지 다른 노드들에 전파한다.
 +
# 앞의 과정이 끝나면 모든 노드는 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 된다.
  
*내외신문,<[http://www.naewaynews.com/news/articleView.html?idxno=106392 [을의반란31화] 1조원대 다단계 사기 밸류인베스트코리아모집책과 정관계 법조계 비호세력을 직접 단죄 위해 만든 '금융피해자연대' 결성]>내외신문,2020-04-04
+
: [[프랙티컬 비잔틴 장애 허용]]은 두 번의 브로드캐스트 과정을 이용해 비잔틴 리더나 비잔틴 검증 노드가 네트워크 분기를 위해 이상한, 혹은 임의의 메시지를 보내도 네트워크의 모든 노드는 같은 메시지를 가질 수 있게 하였다. 이러한 [[프랙티컬 비잔틴 장애 허용]] 알고리즘은 IBM Fabric 0.6v이나 1.0v의 Orderer 서비스, R3 Corda의 Notary와 같은 프라이빗 블록체인에서 사용하고 있다.
  
*김선민 기자,<[http://m.blockstreet.co.kr/news/view?tp=1&ud=2019122410193865373 가상화폐 로커스체인 투자자들, 개발사 대표 사기·배임 혐의로 고소]>, 블록스트리트,2019-12-24
+
* '''텐더민트'''(Tendermint)
 +
: [[텐더민트]](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>
  
*허준 기자,<[http://naver.me/xbcrPBOT 줄소송에 CEO 잠적설까지...심란한 연말 보내는 韓 블록체인 업계]>,파이낸셜뉴스,2019-12-18
+
* '''우로보로스 비잔틴 장애 허용'''
 +
: 애초에 [[카르다노]]는 기존 지분 증명 프로토콜이 가지고 있는 한계, 그 중에서도 특히 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>
  
*조인디,<[https://cobak.co.kr/community/9/post/287484 석유코인 '로커스체인' 투자자들, 사기 혐의로 개발사 단체고소]>,코박 커뮤니티
+
* '''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.onnews.or.kr/2020/03/로커스체인-사기방조-혐의로-밸류인베스트코리아/ 로커스체인 사기방조 혐의로 밸류인베스트코리아 자회사 대표 김광수 고발]>,대한장애인신문,2020-03-31
+
{{각주}}
  
*코인니스,<[https://cobak.co.kr/community/9/post/255630 로커스체인 사기 의혹]>,코박 커뮤니티
+
== 참고자료 ==
 +
* 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
  
*추광규 기자,<[http://m.shinmoongo.net/135690 '밸류인베스트코리아’...법원과 검찰은 사기꾼의 친구?]>, 신문고뉴스,2020-05-28
+
== 같이 보기 ==
 +
* [[합의 알고리즘]]
 +
* [[프랙티컬 비잔틴 장애 허용]]
 +
* [[경량 비잔틴 장애 허용]]
 +
* [[위임 프랙티컬 비잔틴 장애 허용]]
 +
* [[텐더민트 비잔틴 장애 허용]]
 +
* [[우로보로스 비잔틴 장애 허용]]
 +
* [[간단한 비잔틴 장애 허용]]
 +
* [[비잔틴 장군의 문제]]
 +
* [[두 장군의 문제]]
 +
* [[위임지분증명]]
 +
* [[텐더민트]]
  
*강신업 변호사,<[https://m.blog.naver.com/lawyerksu/221755239158 ‘문재인 대통령 해외특보’ 주장하던 여성 정체 알고보니....]>,법무법인 하나 블로그,2019-12-18
+
{{합의 알고리즘|검토 필요}}

2020년 7월 15일 (수) 20:45 판

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