[Blockchain Study] PBFT(Practical Byzantine Fault Tolerance)

PoW, PoS, DPOS 등 다양한 합의 알고리즘(Consensus Algorithm)이 블록체인에 나오고 있는 현재, 또 다른 중요한 합의 알고리즘을 꼽으라고 한다면 당연 PBFT일 것이다.

텐더민트(Tendermint), 네오(Neo) 등에서 사용할 뿐만 아니라 IBM이 만든 Hyperledger와 R3에서도 합의 알고리즘으로 PBFT를 사용하고 있으니, 중요 합의 알고리즘이라고 할 수 있다. 다만, 이들이 PBFT를 그대로 가져다 쓰지는 않으며, 자신들의 입맛에 맞게 변형하여 사용한다.

예를 들어 텐더민트의 경우, PBFT에 DPOS 개념을 추가했으며, 네오도 비슷하게 Bookkeeper를 두어 dPBFT(Delegated Practical Byzantine Fault Tolerance)라는 합의 알고리즘을 만들었다.

DPOS를 추가하든, Bookkeeper를 넣든 기본적으로 PBFT를 변형시킨 것이기 때문에 본래의 PBFT를 이해하고 있다면 PBFT를 변형한 다른 합의 알고리즘을 이해하는데 큰 도움이 될 것이다.

이에, 이번 Blockchain Study에서는 PBFT에 대해 간략하게 다뤄 볼 예정이다.

▣ PBFT는 어떻게 만들어졌을까.

"We believe that Byzantine Fault tolerant algorithms will be increasingly important
in the future because malicious attacks and software errors are increasingly common
and can cause faulty nodes to exhibit arbitrary behavior." - PBFT 논문 중 -

PBFT는 Practical Byzantine Fault Tolerance의 첫 글자를 딴 것으로, 1999년에 Miguel Castro와 Barbara Liskov가 논문을 통해 발표하면서 처음으로 세상에 알려지게 됐다.

Miguel과 Barbara가 PBFT를 만든 것은 두 가지 이유 때문이었다. 이들은 미래에 네트워크에 대한 악의적인 공격(Malicious Attack)과 소프트웨어 에러가 빈번하게 발생함에 따라 이를 막을 수 있는 방안이 필요하다고 생각했다. 그러나 해당 논문을 발표하기 전만 해도 이를 막을 수 있는 알고리즘 BFT(Byzantine Fault Tolerance)는 동기식 시스템에서만 구현됐을 뿐만 아니라 실제 사용하기에는 너무 느리다는 단점이 있었다.

Miguel과 Barbara는 비잔틴 장군 문제를 해결하는 동시에 비동기식 시스템에서 작동하고, 실제 사용할 수 있을 만큼의 성능(Performance)을 구현할 수 있는 새로운 알고리즘이 필요하다 생각했으며, 이에 PBFT를 만들게 됐다.

▣ PBFT는 (n-1)/3개 노드의 Attack을 방어한다
PBFT를 기반으로 한 네트워크는 전체 참여 노드를 n개라고 했을 때, (n-1)/3개의 이하의 노드가 악의적인 행동을 보인다 하더라도 합의를 정상적으로 이끌어 낼 수 있다.

예를 들어 전체 노드의 수가 7개라고 한다면, PBFT 상으로 2개의 노드가 악의적인 공격을 한다 하더라도 정상적인 합의를 이끌어 낼 수 있다. 만약 3개의 노드가 악의적인 공격을 한다면? 그 경우에는 악의적인 공격을 막을 수 없다.

따라서 PBFT 합의 알고리즘은 PoW(Hash의 50% 이상을 가지고 있어야 악의적 공격이 가능함)보다 악의적인 공격을 방어하는 측면에 있어서는 더 불리하다.

더 많은 악의적인 노드의 공격에 성공적으로 방어하려면 노드의 수를 늘려야 하지만, PBFT는 모든 노드들 간의 통신이 이뤄져야 하기 때문에 노드의 수를 늘릴수록 더 큰 Communication 비용(여기서는 시간)이 발생하게 된다. 블록체인에 대입해 생각해보면 노드의 수가 늘어나면 악의적 공격에 대한 방어는 더 잘 할 수 있지만, 블록 생성에 더 많은 시간이 필요해진다고 볼 수 있다.

한편, PBFT에서는 노드의 수를 3X+1의 형태로 만드는 것이 더 효율적이기 때문에 3X+1의 형태로 노드의 수를 둔다. 예를 들어, 노드의 수를 4개인 네트워크와 5개인 네트워크를 비교해 보자. 어차피 4개, 5개인 네트워크가 방어할 수 있는 비잔틴 장군 문제는 노드 1개까지이다. 두 네트워크 모두 2개 이상의 노드가 악의적 공격을 진행하면 방어할 수 없다. 반면, 4개보다 5개는 더 많은 Communication 비용이 소모되기 때문에, 4개가 5개 노드를 가진 네트워크보다 유리하다고 할 수 있다.

이 때문에 네오의 노드도 4개(3x1+1), 코스모스의 검증인(Validator)도 100개(3x33+1)인 것이다.

▣ PBFT의 합의 과정
PBFT의 합의 과정은 다음과 같다.

1. 먼저 Client가 모든 노드에 현재 상태에 대한 Confirm을 요청한다.(논문에서는 Primary 노드에만 요청을 하나, 현재 대부분의 블록체인을 보면 모든 노드에 요청을 하도록 설계되어 있다.)

2. 모든 노드들 중 선정된 Primary Node는 트랜잭션을 Client로부터 받은 트랜잭션을 전부 모은다.

3. Primary Node는 트랜잭션을 모아 만든 블록을 다른 노드(Replica)들에게 전부 전파한다.

4. 모든 노드가 Primary Node로부터 블록을 받는다.

5. 블록을 받은 노드들은 자신이 블록을 블록을 받았다는 사실을 다른 모든 노드들에게 전파한다.

6. 각 노드는 다른 노드들이 블록을 받았는지 여부를 취합하며 이 수가 2/3 이상일 경우, 해당 블록을 검증한다.

7. 블록의 유효성을 검증한 결과값을 다른 노드들에게 전부 전파한다.

8. 각 노드는 다른 노드들이 보내준 블록 유효성 검증 결과값을 취합하며, 전체의 2/3 초과하여 동일한 결과값을 보냈을 경우 해당 결과값을 참으로 인식하고 이에 맞는 행동을 진행한다
   -2/3를 초과한 노드가 블록이 유효하다는 결과값을 보냈을 때, 블록을 자신의 블록체인에 추가한다.
   -1/3 이상의 노드가 블록이 유효하지 않다는 결과값을 보냈을 때, 블록을 블록체인에 추가하지 않는다.

9. 현재 상태(State) 값을 Client에 보내준다.

이 과정에서 만약 악의적 행동을 하는 노드가 없다고 가정하면, Primary를 제외한 다른 노드들은 총 (n-1) * 2번의 통신을 하도록 되어 있다. 즉 4개의 노드가 있는 상황에 각 노드는 6번의 통신을, 5개의 노드가 있는 상황이라면 8번의 통신을 다른 노드들과 해야 한다.

한편, 전체 통신량(Client와의 통신까지 포함)의 경우, 2n^2번 발생하게 된다. 결과적으로 노드는 1차 함수 형태(즉 하나씩)로 증가한다 했을 때, 전체 통신량은 2차 함수로 증가하므로 전체 네트워크가 부담해야 하는 통신량은 갈수록 훨씬 커진다. 이는 더 많은 노드가 참여할수록 합의에 도달하는 시간은 노드 증가보다 더 크게 늘어남을 의미한다.

따라서 적정 수준의 노드를 갖추지 않고 무작정 노드를 늘린다면, PBFT의 합의는 제대로 이뤄지지 못한다. 또한, 각 노드는 다른 모든 노드들과 긴밀하게 통신을 해야하여 서로를 무조건 알고 있어야만 한다.

▣ PBFT는 Fork가 발생하지 않는다.
악의적 공격과 합의 속도에 대한 Trade off가 있는 반면, PBFT의 합의 과정에 따른 특성 상, 하드포크가 발생하지 않는다.

위에서 PBFT의 합의 과정을 보았듯이, 네트워크에서 합의에 참여하고 있는 모든 노드들과 가/부 여부를 주고 받아야 하며, 블록을 생성하려면 다른 노드의 동의를 2/3 초과하여 받아야 한다. 각 검증에 참여한 노드들이 모두 이 과정에 참여하기 때문에 PoW에서 발생하는 자연적인 분기(Fork)가 발생하지 않는다는 특징이 있다.

즉, PoW의 경우, 서로 다른 두 개의 채굴자가 동시에 문제를 맞춰 각각의 블록을 최장 체인으로 한 블록체인이 두 개(혹은 그 이상) 생겨날 수 있으나, PBFT에서는 모든 노드가 합의하기 때문에 이와 같은 형태의 분기가 발생하지 않는 것이다.