PBFT 최대한 직관적으로 정리 - 1. 합의 알고리즘, 부분 동기 네트워크, Safety 및 Liveness

PBFT 최대한 직관적으로 정리 - 1. 합의 알고리즘, 부분 동기 네트워크, Safety 및 Liveness

 

목차

0. 이 글을 읽기 전에

1. 배경 및 개요

   1.1. 블록체인과 분산 합의 알고리즘

   1.2. 부분 동기 네트워크

   1.3. Safety 및 Liveness 

   1.4. PBFT 개요

2. 합의 알고리즘 (Normal Case)

3. 합의 알고리즘 (View Change)

4. 결론

5. 출처

 

위 내용들은 이번 포스트에서 전부 다루지 않고 점차적으로 작성해나가면서 글을 포스트할 예정이며,
내용 및 목차 구성은 글을 작성함에 따라 수정될 수 있습니다.

 

0. 이 글을 읽기 전에

  이 글은 블록체인 관점에서 합의 알고리즘으로써의 PBFT에 대해 설명하는 글입니다. PBFT 논문에서 언급된 내용 전체를 설명하지않으며 수학적 증명같은 깊은 내용도 다루지 않습니다. 이 글은 블록체인에 대한 기본적인 이해는 있지만 처음 PBFT에 대해 접하는 사람이 이해할 수 있도록 직관적이고 쉽게 작성할 예정입니다. 저 역시 이 내용에 대해 100% 완벽한 이해를 하고 있진 않으며, 개인적인 공부 및 내용 공유를 목적으로 하고 있으므로 틀린 내용이 있을 수도 있습니다. 궁금하신 점이나 틀린 내용이 있는 경우 댓글로 알려주시면 감사하겠습니다.

 

1. 배경 및 개요

  PBFT (Practical Byzantine Fault Tolerance)는 Byzantine Fault Tolerance 문제 (비잔틴 장군 문제)를 해결하기 위해 1999년에 논문 (Castro, Miguel, and Barbara Liskov. "Practical byzantine fault tolerance." OSDI. Vol. 99. No. 1999. 1999.)에서 소개된 분산 합의 알고리즘이다. 처음 발표될 당시 PBFT는 분산 컴퓨팅 간의 상태를 동일하게 맞추기 위한 분산 알고리즘으로 소개 되었으며, 요즘은 블록체인에서 사용하는 블록 합의 알고리즘으로 많이 사용 되고 있다. 이 글 역시 블록체인에서의 블록 합의 알고리즘의 맥락으로 PBFT를 설명할 것이다.

 

    1.1. 블록체인과 분산 합의 알고리즘

  블록체인은 서로 신뢰할 수 없는 노드들이 유지하고 있는 "분산 데이터 저장소"이다 (분산원장 이라고도 한다). 물론 블록체인이 갖고 있는 암호화폐, 스마트컨트랙트, DApp 등과 관련된 가치를 앞세워 블록체인을 더 폭 넓게 정의할 수 있다. 하지만 여기서는 단순히 분산 데이터 저장소로 정의해도 충분하다. 블록체인의 가장 큰 특징은 데이터 저장소를 신뢰기관이 중앙집중 방식으로 관리하는 것이 아니라 서로 신뢰할 수 없는 여러 노드 (개인, 기관)들이 함께 관리한다는 점이다. 이러한 상황에서 각 노드들이 동일한 데이터 저장소 즉, 동일한 블록체인을 가지고 있을 수 있도록 보장해주는 것이 PBFT와 같은 합의 알고리즘의 목적이다.

 

  블록체인 네트워크 내의 각 노드는 모두 특정한 상태 (state)를 갖는다. 여기서 상태란 노드가 가지고 있는 데이터의 집합을 의미한다. 예를 들어, 그림 1 과 같이 노드 A와 노드 B는 "X: 1, Y: 2"의 데이터를 가지고 있다. 이 때 "X: 1, Y: 2"를 노드의 상태라고 하며, 이 경우 노드 A와 노드 B는 같은 상태이다. 반대로, 노드 C의 경우 "X: 1, Y: 5"의 데이터를 가지고 있으므로, 노드 A (노드 B)는 노드 C와 다른 상태이다.

그림 1. 노드 C는 노드 A, 노드B와 다른 상태이다

 

  블록체인에서 노드가 가진 데이터는 일련의 블록으로 이루어진 "블록체인"이다. 각 노드는 0번 블록(제네시스 블록), 1번 블록, 2번 블록, ..., N번 블록으로 이루어진 "블록체인" 데이터를 가지고 있으며, 앞선 예시처럼 표현하면 "Block#0: aaaaa, Block#1: bbbbb, Block#2: ccccc, ..., Block#N: xxxxx"와 같이 표현할 수 있다. 블록체인에서는 노드들이 "블록체인"을 동일한 상태로 유지하기 위해 합의 알고리즘을 수행한다. 블록체인을 사용하는 사용자 (Client)가 노드 A에게 Block#2를 조회했을 때의 결과와 노드 B에게 Block#2를 조회했을 때의 결과는 동일해야한다 (그림2).

그림2. 노드 A와 노드 B로부터 얻어온 블록 데이터는 항상 동일해야한다

  물론 합의 알고리즘에 따라 일정 시간 동안은 다른 상태일 수도 있다 (safety를 잠시동안 유보, 또는 finality 유보). 예를 들어, PoW (Proof of Work), PoS (Proof of Stake)와 같은 경쟁합의 방식에서는 최신 블록인 Block#N의 상태가 다를 수 있다. 이 이유는 경쟁 합의 방식은 여러 노드가 합의하에 하나의 블록을 생성하는 방식이 아니라, 각 노드가 우선 블록을 생성한 후 경쟁을 통해 가장 긴 길이를 가진 블록체인이 유효한 블록체인으로써 살아남는 구조이기 때문이다. 이러한 이유 때문에 PoW를 사용하는 비트코인의 경우 블록 생성 후 1시간은 지나야 블록 안의 데이터가 확정된 것으로 간주된다 (1시간 = 평균 블록 생성 시간간격 10분 x 6블록). 1시간이 안된 블록은 다른 노드에 의해 만들어진 블록과의 경쟁에 밀리고 해당 블록에 포함된 데이터는 버려질 수있기 때문이다. 이더리움에서는 경쟁에 밀린 블록을 uncle 블록으로 사용하기도 한다. 

 

  블록체인에는 가장 큰 문제는 악의적인 노드 (비잔틴 노드, Byzantine Node)가 존재한다는 것이다. 그림 3과 같이 각 노드는 서로를 신뢰할 수 없기 때문에 수신한 메시지가 데이터가 진짜인지, 가짜인지 또는 메시지에 적혀있는 송신자가 정말 맞는지 아무것도 보장할 수 없다. 이러한 행동을 하는 악의적인 노드가 존재하는 블록체인 네트워크에서 선량한 (착한) 노드들은 서로 데이터를 주고받음으로써 같은 블록체인(상태)를 유지하고자 한다. 이처럼 악의적인 노드가 존재하는 상황에서 노드들이 서로 동일한 블록체인을 유지하는 알고리즘을 분산 합의 알고리즘이라고 한다. PBFT는 이러한 분산 합의 알고리즘 중의 하나이다.   

그림3. 블록체인 네트워크에서 받은 메시지는 함부로 믿을 수 없다

 

 

    1.2. 부분 동기 네트워크

  블록 합의 알고리즘으로써의 PBFT에 대해 조금 더 깊이 이해하기 위해서는 PBFT에서 가정하고 있는 네트워크 환경인 "부분 동기 네트워크"를 이해해야한다. 이는 블록체인의 가장 중요한 2가지 속성 (property)인 "안전성 (safety)"과 "생기성 (liveness)"과 관련된다.

 

  부분 동기 네트워크를 이해하기 위해서는 우선 "동기 네트워크"와 "비동기 네트워크"에 대해 알아야 한다. 동기 네트워크 (Synchronous Network)는 노드 간의 메시지 교환이 항상 성공하며 규칙적인 네트워크이다. 1) 메시지가 유실되지도 않고, 2) 메시지가 알려진 시간 (약속된 시간) 내에 반드시 도착하며, 3) 먼저 보낸 메시지가 항상 먼저 도착하는 이상적인 네트워크 상황이다. 이는 비현실적인 상황이므로 단순히 다른 네트워크 유형과의 비교군으로써의 가치만 있다.    

 

  비동기 네트워크 (Asynchronous Network)는 노드 간의 메시지 교환에서 그 무엇도 보장되지 않는 네트워크이다. 1) 메시지가 유실되거나, 2) 메시지가 무한히 지연되거나, 3) 메시지의 도착 순서가 변경될 수 있다. 이는 지극히 현실적인 네트워크 이지만, 메시지가 무한히 도착하지 않는다는 가정은 오히려 너무 가혹하므로 대부분의 합의 알고리즘은 부분 동기 네트워크 (Partial Synchronous Network) 상황을 가정한다. 

 

 부분 동기 네트워크 (Partial Synchronous)에서는 1) 메시지가 유실되거나, 2) 유한 시간동안 지연되거나, 3) 메시지의 순서가 변경될 수 있다 (그림 4). 비동기 네트워크와의 차이는 2번째 조건에 있다. 유한시간 동안 메시지가 지연된다는 것은 전송된 메시지가 언젠가는 도착한다는 뜻이다. 

그림 4. 부분 동기 네트워크

 

  PBFT는 부분 동기 네트워크 상황을 가정하고 있으므로 모든 노드들 간의 메시지 교환에 있어서 모든 노드들은 메시지가 '언젠간' 도착할 것이라고 알고있다. 하지만 메시지가 '언제' 도착할지는 모른다. 각 노드는 도착하길 기대하고 있는 메시지가 1) 유실됐는지, 2) 비잔틴에 의해 의도적으로 전송이 안됐는지, 3) 유한시간 동안 지연되고 있는지 모르기 때문에 메시지를 하염없이 기다릴 수는 없다 (비록 메세지가 거의 다 도착하였더라도 수신측 노드는 알 수 없다). PBFT는 이러한 부분 동기 네트워크 상황에서도 노드들 간의 블록 합의를 이끌어 낼 수 있다.

 

  부분 동기 네트워크를 좀 더 직관적으로 해석하면, "메시지가 무한히 도착하지 않는다는 것은 네트워크에 결함이 있다는 뜻이므로 사람이 이를 알아채고 손대면 언젠간 네트워크가 복구되고 메시지가 전송될 수 있다"고 생각하면 쉽다. 즉, 부분 동기 네트워크는 가장 현실적인 네트워크 상황이다. 부분 비동기 네트워크에 대해 다른 글들을 읽다보면 "메시지 도착 시간은 알 수 없지만 상한 (bound)이 존재하며 그 상한은 시간에 따라 계속 달라진다", "부분 동기 네트워크는 시간에 따라 네트워크가 '동기 네트워크'와 '비동기 네트워크'로 번갈아 바뀌는 상황이다" 라는 설명이 있다. 모두 맞는 말이며 일단은 본인이 가장 이해하기 편한 형태로 알고 넘어가면 될 것 같다. 부분 동기 네트워크에 대해서는 추후 다른 합의 알고리즘을 다룰 때 좀 더 깊이 다룰 예정이다.

 

 

    1.3. Safety 및 Liveness

  위에서 언급한 "안전성 (safety)"과 "생기성 (liveness)"은 블록체인이 지켜야 할 가장 중요한 2가지 속성 (property)이다. 우리는 안전성과 생기성에 대한 개념을 분산 합의 알고리즘과 부분 동기 네트워크를 설명하면서 이미 간접적으로 살펴보았다.

  

  안전성은 (safety)는 "서로 다른 노드들이 가지고 있는 블록체인 (데이터 또는 상태)이 모두 동일한가?"에 대한 내용이다. 안전성이 보장되는 블록체인은 그림 2처럼 사용자가 다른 두 노드에게서 같은 데이터(Block#2)를 읽었을 때 동일한 결과 (bbbbb)가 반환된다. 만약 두 노드에게서 읽은 같은 데이터가 서로 다른 결과를 반환한다면 (노드 A의 Block#2 반환 결과는 bbbbb, 노드 B의 Block#2 반환 결과는 ccccc 인 경우) 이는 안전성이 보장 되지 않는 (안전성이 깨진) 블록체인이다.

 

  만약 블록체인에서 어떤 두 노드가 동일한 블록 번호에 대해 서로 다른 블록 (블록 번호는 동일하나 내부 데이터가 다름)을 가지며 이 상황이 여러 블록 번호에 대해 이어진다면 이를 "블록체인에서 포크(fork)가 발생했다" 라고 한다. 단순하게 보면 포크가 발생했다는 것은 블록체인의 안전성이 깨진 것으로도 볼 수 있다. 하지만 만약 블록체인의 포크가 1) 단기적으로 발생했거나 2) 의도적으로 발생한 경우는 허용되는 포크로 여겨지므로 "블록체인의 안전성이 깨졌다" 라고는 할 수 없다 (그림5). 전자의 경우 1.1에서 언급한 PoW와 같은 경쟁 합의 방식에서 발생하는 단기적인 포크가 해당되며, 후자의 경우는 이더리움/이더리움 클래식의 분리와 같이 블록체인의 정책, 기술 등에 큰 변화가 있어서 기존 방식을 따르는 블록체인과 새로운 방식을 따르는 블록체인으로 분리되는 포크가 해당된다. 이러한 상황을 빼고 '일반적', '장기적'으로는 "블록체인의 포크가 없는 것이 안전성이 보장되는 것이다" 라고 할 수 있다.

그림 5. 의도적인 Fork와 일시적인 Fork

그림 5.1. 비경쟁 합의에서의 Fork --> 깨진 블로체인

생기성 (liveness)은 "블록체인이 멈추지 않고 잘 작동하는가?"에 대한 내용이다. 어떻게 보면 굉장히 속편한 표현이지만 이게 맞다. 생기성이 보장되는 블록체인은 정상적인 동작 하에 0번 블록, 1번 블록, 2번 블록, ... 순서대로 잘 만들어진다. 물론 어떤 블록은 조금 빠르게 만들어질 수도 있고 어떤 블록은 상대적으로 조금 늦게 만들어질 수 도 있지만 결과적으로 보면 시간에 흐름에 따라 블록체인에 블록이 점점 붙어나간다. "결국 프로그램이 무한 루프 안돌도록 프로그램을 잘 만들면 되는거 아닌가?" 라는 질문을 할 수 있다. 그 말이 맞다. 하지만 블록체인은 여러 노드 (컴퓨터)가 네트워트 상으로 함께 동작하는 분산 컴퓨팅 기술이므로 알고리즘 상으로 빙빙 도는 상황이나 모두가 메시지를 기다리면서 멈춰버리는 상황이 안나오도록 하기 위해서는 정교한 알고리즘이 요구된다.

 

  만약 블록체인이 이 둘중 한가지라도 지켜지지 않는다면 그 블록체인은 사용자들로부터 신뢰를 잃고 사용되지 않을 것이다. 안전성이 지켜지지 않으면 블록체인 내의 데이터를 신뢰할 수 없으며, 생기성이 지켜지지 않으면 블록체인이 더 이상 작동하지 않기 때문에 사용하지 않을 것이다. 

 

  1985년에 발표된 "Impossibility of distributed consensus with one faulty process" 논문에서는 "비동기 네트워크에서는 분산 합의 알고리즘이 안전성과 생기성을 동시에 완벽하게 만족시키는 것은 불가능하다" 라는 것을 증명했다. 이를 "FLP Impossibility"라고 한다. 결국 부분 동기 (또는 비동기) 네트워크를 가정하는 블록체인은 안전성과 생기성 중 하나는 "완벽히 챙기고" 하나는 "어느 정도 포기"해야 한다. 안전성을 더 중요시 하는 것을 "safety over liveness"라고 하며 생기성을 더 중요시 하는 것을 "liveness over safety"라고 한다. 분산 합의 알고리즘은 둘 중 하나는 선택해야한다.  PBFT와 같은 비경쟁 합의 알고리즘들은 "safety over liveness"로써 노드들이 함께 생성할 블록을 합의한 후 생성 및 확정한다. 반면, PoW와 같은 경쟁 합의 알고리즘들은 "liveness over safety"로써 각 노드들은 각자 일단 블록을 생성하고나서 경쟁을 통해 승리한 블록을 확정된 블록으로 간주한다. 

 

 

    1.4. PBFT 개요

  PBFT의 기본 동작은 2/3 보다 많은 노드가 동의한 블록을 확정하는 방식이다. 또한 PBFT는 악의적인 노드 (비잔틴 노드)가 있는 상황을 가정한다. 전체 노드 수가 N일 때 PBFT에서는 최대 f = (N-1)/3 개의 비잔틴 노드만을 허용한다 (다시 말해, N = 3f + 1). 여기서 비잔틴 노드는 Fault 노드를 포함한다. 단순히 시스템 고장으로 인해 동작을 하지 않는 Fault 노드와 악의적으로 메시지를 이리저리 조작하여 블록체인을 깨뜨리려는 노드 모두를 비잔틴 노드로 간주한다. PBFT는 최대 f개의 비잔틴이 존재하는 상황에서도 Safety와 Liveness를 만족하는 블록 합의 알고리즘이다. 각 노드들은 메시지를 주고 받음으로써 어떤 블록을 추가할지 (어떻게 상태를 변경할지) 결정하고 확정된 블록을 생성한다. 그 결과로 모든 노드들은 동일한 데이터를 갖는 최신 블록을 블록체인의 추가한다. PBFT의 알고리즘은 Normal Case와 View Change로 나눌 수 있다. Normal Case는 safety를 만족하며 블록을 생성해나가는 정상적인 과정이며, View Change는 특정 노드에 문제가 생겼을 때 liveness를 만족하기 위한 복구 과정이다.

  다시 말하자면, PBFT의 목적은 3f + 1 개의 노드가 존재 할 때 (f는 비잔틴의 개수) 블록체인이 Fork가 발생하지 않고 (safety)연속적으로 블록을 생성(liveness)하는 것이다 (그림 6). 

그림 6. 합의 알고리즘의 목적

 

본격적인 PBFT 합의 알고리즘 동작에 관한 내용은 다음 글에서 작성할 예정이다.