[Technology] 비잔틴 장애 허용(BFT, Byzantine Fault Tolerance) v1.5

비잔틴 장애 허용(Byzantine Fault Tolerance, BFT)

딱딱하고 학문적인 내용이지만, '블록체인'이 여러노드들이 존재하는 네트워크로서 가장 난이도가 높은 장애를 처리하는 방식, 즉 비잔틴장애(Byzantine Fault)를 다루고 있는 혁신이기에 한번쯤은 알아볼 필요가 있다는 판단에 나름대로 정리하여 공유합니다   -Wukong


□ 비잔틴 장군 문제란 
 ㅇ 배경 : 네트워크에서는 다른 이(노드)와 주고받은 메세지가 정상인지 아닌지 판단할수 없기에 100%는 아니어도 대세를 따르는 판단을 하기 위하여 나름대로의 기준을 찾는 방법이 필요하였다. 
  ㅇ 상황 : 두 명 이상의 장군들이 그들의 공동의 적을두고 공격(후퇴)해야하는 상황에서 하나 이상의 장군(들)이 배신자가 될 수 있다.
  ㅇ 조건 : 지휘관과 중위(들)이 있는 전장에서, 성공적으로 목적을 달성하려면 합의를 이루어야 하고, 따라서 지휘관과 모든 중위가 같은 결정(공격, 퇴각 등)을 내려야 한다.
  ㅇ 정의
    - 비잔틴 장애 모델(Byzantine Fault Model) : 각자 다른 이(노드)의 상태를 모르며 본인이 제대로 된 메시지를 주고받았는지 잘못된 메세지를 주고받았는지 모르는 상황에서 악의적으로 메세지를 보내는 일부(노드)가 있는 상태를 뜻한다. 이는, 분산시스템을 구축시 가장 어려운 상황이면서도 반드시 극복해야하는 문제다. 
    - 비잔틴 장애 허용(Byzantine Fault Tolerance) : 앞서 언급한 비잔틴 장애 모델에서도 정상적으로 작동하는 상태를 뜻한다. 일반적으로, 전체에서 배신자(노드)가 1/3일때까지는 정상작동한다.


 <https://tokenpost.kr>


"왜 배신자가 전체의 1/3이상이면 비잔틴장애(작동불능)가 발생하나"

□  서술적 증명 검증 및 정리

  ㅇ (가정1) 1명의 지휘관과 2명의 중위가 전투에 임하며, 모든 이(노드)가 동일한 결정을 할때 공격(후퇴)이 성공한다.



    - (검증1) 위의 그림에서는 배신자가 중위2다. 지휘관은 중위1,2 모두에게 '공격'메세지를 보내지만, 배신자인 중위2가 중위1에게 그 반대인 '후퇴'메세지를 보내버린다.
    - 이때 중위1은 공격(지휘관의 메세지)을 할지 후퇴(중위2의 메세지)를 할지 고민만 할뿐 최종 결정을 하지 못하게 되어 실패한다.




    - (검증2) 위의 그림에서는 배신자가 지휘관임. 지휘관은 중위1에게는 '공격'메세지를, 중위2에게는 '후퇴'메세지를 보고, 중위2가 중위에게 그대로 '후퇴'메세지를 보낸다.
    - 이때  중위1은 공격(지휘관의 메세지)을 할지 후퇴(중위2의 메세지)를 할지 고민만 할뿐 최종 결정을 하지 못하게 되어 실패한다.
    =>(결론1) 전체(노드)가 3명이고 배신자가 1명이면, 네트워크가 정상작동하지 못한다.

 ㅇ (가정2) 1명의 지휘관과 3명의 중위가 전투에 임하며,  모든 이(노드)가 동일한 결정을 할때 공격(후퇴)이 성공한다.




    - (검증1) 위의 그림에서는 배신자가 중위3이다. 지휘관은 중위1,2,3 모두에게 '공격(v)'메세지를 보내지만, 배신자인 중위3이 중위2에게 그 반대인 '후퇴(x)'메세지를 보냄.
    - 이때 중위2은 공격(지휘관, 중위1의 메세지)을 할지 후퇴(중위3의 메세지)를 할지 고민하다 다수결에 따라 공격하기로 하고, 전체(노드)가 동일한 결정을 하여 공격(후퇴)에 성공한다.




    - (검증2) 위의 그림에서는 배신자가 지휘관임. 지휘관은 중위1에게는 '후퇴(x)', 중위2에게는 '공격(v)', 중위3에게는 '대기(z)'의 메세지를 보낸다.
    - 이때 중위1은 중위2로부터 '공격(v)', 중위3으로부터 '대기(z)' 메세지를 받아서 '후퇴/공격/대기(x/v/z)' 메세지 모두 갖게 되고,
    - 중위2도 중위1로부터 '후퇴(x)', 중위3으로부터 '대기(z)' 메세지를 받아서 '후퇴/공격/대기(x/v/z)' 메세지 모두 갖게 되고,
    - 중위3도 중위1로부터 '후퇴(x)', 중위2로부터 '공격(v)' 메세지를 받아서 '후퇴/공격/대기(x/v/z)' 메세지 모두 갖게 된다.
    - 결국, 전체(노드)가 동일한 메시지를 갖게되어 동일한 결정을 하게 되므로 공격(후퇴/대기)에 성공함
    => (결론2) 전체(노드)가 4명이고 배신자가 1명이면, 네트워크가 정상작동한다. 


  ㅇ (정리) 위의 검증의 결론1과 결론2로 비추어 볼때, (그리고 위에서 추가로 다루지 않은 4명보다 많은 경우까지 검증했을때)
    - 전체(노드)에서 배신자가 전체의 1/3보다 적을때 정상작동함을 알수 있고,
    - 가정1에서는 전체(노드)가 3명에 배신자가 1명, 가정2에서는 전체(노드)가 4명에 배신자가 1명임을 비추어볼때, 
      전체(노드)의 수 = N, 감당할수 있는 배신자 수 = f, 0보다 큰 임의의 수 = 1 

    => (정리) BFT : N > 3f  즉, N = 3f + 1이다.
          말하자면, 전체노드수는 배신자수의 3배는 초과해야한다는 식이 도출된다. 이것을 BFT합의방식의 블록체인에 적용하면, 전체 투표자 중에서 2/3이상이 동의할때에만 블록을 확정지을수 있다.


□  수학적 증명 검증 및 정리

  ㅇ 객관적인 검증을 위해서 수학적인 접근이 필요
    - 정족수(의사결정을 위한 최소인원)를 고려하면 배신자를 빼도 남아있는 누군가는 있어야한다 : N - f > 0 .
    - 어떤 합의회의체가 있다고 할때, 반대파가 시위로 불참해도 누군가는 회의에 나와 합의를 도출해야한다.
    - 그런데 정족수(N - f)가 충족이 되어도, 그 안에서 배신자가 더 많으면 안 된다 : (N - f) - f > f
       * 전체(노드)의 수 = N, 감당할수 있는 배신자 수 = f, 0보다 큰 임의의 수 = 1
    => (정리) 어찌어찌 합의회의체를 열어도 또 그 안에서 합의찬성파가 반대파보다는 많아야 가결될수 있다는 의미이며, 따라서 BFT : N > 3f  즉, N = 3f + 1



법적 고지 : 본 게시글은, 투자를 위한 정보제공을 목적으로 작성되었기에 투자결정은 신중을 기하여 주시기 바라며, 참고자료를 토대로 본인 판단하에 내용을 추가, 편집 등 작성되었기에 본인의 허락없이 복사, 배포, 편집 등을 할 수 없습니다.
<References>
1) http://bnrg.cs.berkeley.edu/~adj/cs16x/hand-outs/Original_Byzantine.pdf
2) https://medium.com/codechain/why-n-3f-1-in-the-byzantine-fault-tolerance-system-c3ca6bab8fe9

댓글 없음:

댓글 쓰기

[Bitcoin] 비트코인의 흥망성쇠(3부작) 1부 "역대 주요이슈 분석" // Bitcoin's Rise & Fall(Trilogy) Part1 v1.5

비트코인의 흥망성쇠 (興亡成衰) □ 에필로그   ㅇ 분석에 앞서     - 그동안 분석가로서 블록체인과 암호화폐가 지닌 기술 위주의 기본적 분석을 해왔으나, 투자자로서 유의미한 시세변동, 시세에 영향을 끼치는 이슈 등에 대한 분석글 작...