PBFT

하이퍼레저 패브릭의 히스토리

하이퍼레저 패브릭 0.6 버전은 오더러가 없으며, 보증하는 부분과 커미팅하는 부분이 나뉘지도 않았다. Peer들끼리 아래와 같은 PBFT를 수행했다.

Pre-prepare 단계에서 트랜잭션을 모두 공유하고, Prepare 단계에서 각자 Peer들은 트랜잭션을 받았다는 것을 알리며, Commit 단계에서 각자 Peer들은 이 트랜잭션에 대해서 합의를 해준다라는 것을 모두에게 알리며 마지막으로 동료 Peer들의 합의 상태에 따라서 OK 인지 아닌지를 각자 확인해서 Reply 해준다.

이 알고리즘은 보통 2/3 이상의 합의가 있으면 통과이고, 대략 2n^2번의 커뮤케이션이 필요하게 된다. 즉 엄청나게 느리다. 처음 하이퍼레저 패브릭을 설계했을 때 허가형 블록체인으로 신뢰할 수 있는(믿을만한) 극소수의 노드를 대상으로 서비스 한다고 생각해서 그런 것 같다. 하지만 너무 느리다. 따라서 1.0에서는 아키텍쳐가 달라진다.

하이퍼레저 패브릭 1.0
=> Endorsing - Ordering - Validating 3단계 구조

PBFT 식으로 Peer들 간에 커뮤니케이션 하는 부분은 속도가 너무 느려서 없어지고 Endorsing - Ordering - Validating 3단계 구조를 기반으로 합의 알고리즘이 완성된다. Endorsing 에서는 보증 역할을 맡은 Peer들이 트랜잭션에 대해 실행을 하고 결과 값을 사인한 후에 클라이언트에 돌려준다.

여기서 Peer들간의 커뮤니케이션은 없다. 이런 값들을 오더러에게 전달하면 오더러는 트랜잭션에 순서를 매기고, 블록으로 완성한 후 Validator 에게 전달하면 Validatior에서는 보증이 어떻게 되있는지 확인하여 만족 시키면 장부에 기입한다.

PBFT
프랙티컬 비잔틴 장애허용은 분산컴퓨팅의 한 이론으로 BFT를 속도와 실용적인 측면에서 개선한 형태다. 이 방식은 블록체인 시스템에 있어서 약속된 행동을 하지 않고 고의로 잘못된 정보를 전달하는 비잔틴 노드가 존재할 수 있는 비동기 시스템일 때 모든 노드가 성공적인 합의를 이룰 수 있도록 개발된 증명 방식이라고 볼 수 있다.

PBFT 이해를 위한 사전지식 - FLP Impossibility

어떤 합의 알고리즘이 네트워크에 통용되기 위해서는 Safety와 Liveness라는 특성을 가지고 있어야 한다.

• Safety : 노드 간 합의가 발생했다면, 어느 노드가 접근하든 그 값은 동일해야 한다.
• Liveness : 합의 대상(Transaction 또는 블록체인에서 블록)에 문제가 없다면, 네트워크 내에서 반드시 합의가 이루어진다.

이 때까지 합의 알고리즘을 설계할 때 Safety를 Liveness보다 우선 적용되게 하여 알고리즘을 설계했다. 네트워크 안에 있는 모든 거래를 전부 합의하지 못해도 일단 합의된 거래는 네트워크 내에 있는 모두에게 동일한 값으로 제공되는 것이 훨씬 더 중요하다고 판단했기 때문이다. 그래서 과거의 합의 알고리즘의 관심사는

< Safety’를 충족시키는 상황에서 어떻게 하면 ‘Liveness’의 손실을 최소화할지 >의 고민이었다.

무조건적으로 Safety가 먼저였던 것이다.

비트코인이 주목받은 것도 합의 알고리즘 덕이다. 비트코인의 합의 알고리즘은 기존에 네트워크 합의 알고리즘에서의 Safety와 Liveness의 기본 전제를 완전히 뒤접어 버렸기 때문이다.

위에서 언급한 것처럼 기존의 알고리즘은 Safety가 확보되어 있는 상황에서 최대한으로 Liveness의 손실을 줄인다 였는데 비트코인은 모든 거래를 가감없이 수용하는 구조를 채택하여 Liveness 를 극대화하되, 하드포크가 발생할경우(가지치기가 많아질 경우) <최장 길이 체인 선택 알고리즘>을 활용해 Safety 문제를 해결했다.

하지만 이것은 Safety를 확률적으로 확보하는 것이기 때문에 51% 공격과 같은 네트워크 공격이 성공할 경우 Safety를 보장할 수 없다.

그런데

비동기 네트워크 내에서는 Safety와 Liveness를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것이 불가능하다는 증명이 되었다. 이 증명을
FLP Impossibility 라고 한다.

비동기 네트워크에서는 어떤 한 노드에서 문제가 발생했을 경우 그 노드에서 합의가 됐는데 단순히 응답에 오랜 시간이 걸리는 건지 아니면 합의 과정에서 충돌이 발생해서 응답하지 않는 건지 알 수가 없기 때문이다.

비동기 네트워크란

네트워크는, 네트워크 내에서 주어진 프로토콜의 실행 라운드에서 메시지를 교환할 때 발생하는 대기 시간의 여부에 따라 크게 세 가지로 나뉜다.

• 동기 네트워크(Synchronous Network) : 노드가 메시지를 보내는 시간과 수신 노드가 메시지를 수신하는 시간 사이에 상한선이 존재하고, 그 시간 안에 반드시 메시지가 수신 노드에게 도착한다는 것을 보증하는 네트워크. 따라서 네트워크 사이에 데이터 통신이 ‘반드시’ 이루어져야 하는 경우에 사용한다. 단순하게 이해하자면, 어떤 메시지를 보내면, 정해진 시간 안에 반드시 응답이 도착하는 네트워크라고 생각하면 된다. 비행기나 우주선의 통신과 같이, 노드 간 통신이 반드시 필요한 네트워크에서 주로 사용된다.

• 비동기 네트워크(Asynchronous Network) : 노드가 메시지를 보내는 시간과 수신 노드가 메시지를 수신하는 시간 사이에 상한선이 없다. 즉 메시지가 수신 노드에게 제대로 도착했는지 여부를, 수신 노드가 응답하는 데 얼마나 시간이 걸리는지를 알 수 없다. 따라서 특정 노드가 임의로 메시지를 전송하지 않거나 거짓 데이터를 전송하는 배신행위가 가능한 네트워크이기도 하다. 인터넷이나 블록체인 네트워크가 여기에 해당된다.

• 부분 동기 네트워크(Partial synchronous Network) : 노드가 메시지를 보내는 시간과 수신 노드가 메시지를 수신하는 시간 사이에 상한선이 존재하지만, 그 상한선이 얼마인지는 알 수 없는 네트워크. 단순히 표현하자면 ‘노드와 노드 사이에 메시지가 도달하는 것은 보증하지만, 언제 도달할지는 알 수 없다’고 말할 수 있다. 네트워크에서 메시지가 도달하는 시간의 상한선이 유한(finite)한 것이 부분 동기 네트워크이고, 무한(infinite)한 것이 비동기 네트워크라는 점에서 비동기 네트워크와 차이가 있다.

⇒ < [steemit] - [케블리] 합의 알고리즘 이해하기 > 참고

블록체인이 구동되는 네트워크는 비동기 네트워크이다.

⇒ 송신, 수신 사이에 시간이 얼마나 걸릴 지 예상할 수 없고 특정 노드가 배신할 가능성도 있다.

따라서 비동기 네트워크에서 완벽한 합의 알고리즘은 존재하지 않는다.

다시 말해서 Safety와 Liveness를 동시에 완벽히 만족하는 합의 알고리즘은 설계할 수가 없다. 즉 블록체인에서 채택하는 합의 알고리즘은 둘 중 하나 정도는 포기해야한다는 것을 의미한다.

PBFT

이전의 합의 알고리즘과 마찬가지로 Safety를 확보하고 Liveness를 일부 포기하면서 비동기 네트워크에서도 합의를 이룰 수 있는 알고리즘이 바로 Practical Byzantine Fault Tolerance, PBFT 이다.

즉 네트워크에 배신자 노드가 어느 정도 있다고 해도 네트워크 내에서 이루어지는 합의의 신뢰를 보장하는 알고리즘이다.

PBFT를 간단히 요약하자면 비동기 네트워크에서 배신자 노드가 f개 있을 때 총 노드 개수가 3f+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘이다.