라벨이 BFT인 게시물 표시

Safety & Liveness - FLP impossibility으로 보는 블록체인

블록체인이 유행하면서 블록체인의 수만큼 다양한 합의 알고리즘이 나오고 있다. 이는 어째서일까? 애초에 왜 다양한 블록체인이 나오고 있는 것일까? 이는 근본적으로 합의 알고리즘이 무엇을 할 수 있고 무엇을 할 수 없는가에서 기인한다. 좋은 합의 알고리즘은 무엇을 보장해야 할까?FLP impossibility우선 아무 문제 없는 두 노드가 서로 다른 값으로 합의하면 안 된다. 다른 값을 합의했다는 것은 블록체인 관점에서 보면 같은 높이에 서로 다른 블록이 생성됐다는 것이다. 이런 특성을 분산 시스템에서는 consensus의 safety라고 말한다.또한, 합의가 언젠가는 이루어져야 한다. 분산 시스템에서 합의는 노드 간의 메시지를 주고받으며 각 노드의 상태를 변경시키며 이루어진다. 이때 문제없는 노드들은 무한 루프에 빠지지 않고 반드시 상태 변경이 종료돼야 한다. 모든 노드가 문제없이 합의를 할 수 있으면 이 시스템은 liveness가 보장된다고 말한다.쉽게 풀어 말하면 safety는 "문제없는 노드 사이에서는 잘못된 합의가 이루어지지 않는다"라는 것이고, liveness는 "문제없는 노드들은 반드시 합의를 한다"라는 것이다. 문제는 byzantine failure가 아닌 fail-stop failure가 하나만 있어도 safety와 liveness를 둘 다 만족하는 합의 알고리즘이 존재할 수 없다. 이를 FLP impossibility 혹은 FLP theorem이라고 한다. 따라서 합의 알고리즘을 선택한다는 것은 사실상 safety와 liveness 중 무엇을 선택하고 무엇을 버릴까 하는 문제이다.Liveness over Safety비트코인이 사용하는 합의 알고리즘은 사토시 나카모토가 처음 제안하였기 때문에 nakamoto consensus라고도 불린다. Nakamoto consensus는 언제나 더 어려운 문제를 푼 체인이 있으면 그 체인을 유효한 체인으로 판단한다. 즉, 지금 있는 체인보다 더 긴 체인을 만들 해시 파워만 …

Byzantine Fault Tolerance 시스템에서 N = 3f + 1인 이유

분산환경 시스템에서는 다른 노드가 보낸 메시지가 정상적이라고 보장할 수 없다. 이때 잘못된 노드가 모두에게 틀린 메시지를 보낸다면 문제가 쉽게 풀린다. 틀린 메시지를 보내는 노드를 차단하면 된다.하지만 일부 노드에게는 잘못된 메시지를 보내고, 일부 노드에게는 제대로 된 메시지를 보내는 경우는 문제 상황을 찾기 힘들다. 분산 시스템에서 각 노드는 다른 노드의 상태를 모르기 때문이다. 이런 식으로 일부 노드에게만 틀린 메시지를 보내는 노드를 가정하는 모델을 byzantine failure model이라고 부른다.Byzantine failure model은 네트워크에서 가장 풀기 어려운 모델임과 동시에 실제 네트워크에서 반드시 해결해야 하는 문제다. 특히 다른 노드를 신뢰할 수 없는 p2p에서는 반드시 Byzantine failure model을 가정하고 예외 상황을 처리해야 한다.그렇다고 인증된 노드만으로 구성된 분산 시스템이라고 byzantine failure model을 가정하지 않아도 된다는 것은 아니다. 노드 자체는 신뢰할 수 있는 사람이 관리하더라도 해킹당했을 수도 있고, 버그로 잘못된 메시지를 보낼 수도 있고, 하드웨어에 문제가 발생할 수도 있다.Byzantine failure model에서도 정상적으로 돌아가는 시스템을 byzantine fault tolerance (a.k.a. BFT)라고 말한다. 당연히 BFT라고 해도 무한히 많은 faulty 노드에 대해서 동작하지는 않는다. 그래서 보통 어떤 시스템이 BFT라고 말할 때 전체 노드 중 몇 개의 노드에 문제가 있을 때까지 동작하는지를 같이 말한다. 예를 들어 N = 5f라고 말하면, 전체 노드 중 1/5가 byzantine failure일 때 정상 동작하는 시스템이고 N = 3f + 1이라고 말하면, 전체 노드 중 1/3이 byzantine failure일 때까지는 문제없이 돌아가는 시스템을 말한다.같은 BFT라고 한다면, 감당할 수 있는 faulty 노드의 비율이 더 큰 시스템이 더 안전한 시…