Honey Badger BFT, 실용적인 비동기 합의 프로토콜
CCS 2016 에서 발표된 Miller et al. “The Honey Badger of BFT Protocols” 23rd ACM Conference on Computer and Communications Security, 2016. 연구를 소개합니다.
[목차]
- 소개
- Honey Badger BFT 구조
- 성능 분석
Introduction
요약하자면 HoneyBadgerBFT(이하 HBBFT)는 비동기적으로 합의에 이를 수 있는 BFT(Byzantine Fault Tolerance) 프로토콜이다.
Synchronous BFT
기존의 동기적(Synchronous)인 BFT 프로토콜에는 시간 제한이 있다. 간단히 말해 Δ 라는 시간 제한을 두고 Δ 이내에 통신이 되지 않으면 유효하지 않은 것으로 처리한다. 그럼 Δ 는 어떻게 설정해야 할까.
Δ 가 너무 높으면 불필요한 대기를 해야 하므로 throughput 이 낮아진다. Δ 가 너무 낮으면 조금이라도 늦어진 통신을 모두 제하기에 시스템이 진행되기 힘들고 마찬가지로 throughput 이 낮아진다.
Δ 는 위를 고려하여 적절하게 설정되어야 한다. Δ 를 dynamic 하게 조절하는 방법들도 제시되었지만 근본적으로 문제를 해결할 수는 없었다.
PBFT (Practical BFT)
PBFT(Practical BFT)는 참여 노드가 정해져 있는 Private Blockchain 에서 널리 쓰이고 있다. PBFT 는 PoW 같은 합의 방법과 달리 즉각적인 Finality(최종성)를 가지고 보안, 성능 면에서 BFT 를 뛰어넘기에 말 그대로 ‘Practical’ 한 BFT로 불리며 사용되고 있다.
PBFT 의 구조를 간단히 짚어보자면, 네트워크 참여 노드 중 하나가 리더로 선출된다. 리더는 다음 블록에 포함시킬 거래 목록을 작성하여 나머지 노드들에게 전파한다. 노드들은 투표로 해당 거래를 블록화 할지 결정하게 된다.
PBFT 는 BFT 의 시간 요소를 최소화하였지만, 리더를 선출하는 과정에 여전히 시간 제한 Δ 를 사용한다.
Asynchronous BFT
Fischer et al. 은 그들의 논문 “Impossibility of Distributed Consensus with One Faulty Process” 에서 ‘분산 컴퓨팅 환경에서 비동기적인 합의는 불가능하다’는 것을 증명하여 FLP Impossibility 라고 명명했다.
그러나 비동기적인 프로토콜을 구현하기 위한 시도는 계속되어 왔다. 일례로 Cachin et al.은 그들의 논문 “Secure and Efficient Asynchronous Broadcast Protocols” 에서 비동기적인 프로토콜을 구현하는데 성공했다. 그러나 각 노드가 거래 당 전송해야 하는 비트 수가 O(N²)로 실용적(practical)인 것과는 거리가 멀었다.
고로 실현 가능한 비동기적 합의 프로토콜은 없었다.
Honey Badger BFT
Miller et al.은 이를 정면 반박하여 실용적인 비동기 BFT 프로토콜을 만들어냈다. PBFT 와의 비교를 통해 HBBFT 의 특징을 정리하면 다음과 같다.
- 비동기적임.
시간 제한 Δ 가 없기에 Δ 를 튜닝할 필요가 없다. 데이터 수신과 동시에 진행하기에 throughput 을 최대화 할 수 있다. - 리더가 없음.
리더가 없는 것의 장점은 두 가지다. 첫째, 단일 실패 지점(single point of failure)이 없다. 둘째, throughput 을 올릴 수 있다.
리더를 없애는 것이 throughput 을 올리는 이유는 다음과 같다. 이전에는 리더가 전체 노드에게 후보 거래의 집합을 전파했어야 했다. 예를 들어서 아래 그림과 같이 전파를 했기에 리더는 O(B*N) 만큼의 대역폭(Bandwidth)을 필요로 했다. (B는 블록 사이즈, N은 노드의 개수이다.) 그런데 HBBFT 에서는 각 노드가 B/N 의 크기를 N 명에게 전송하면 되기에 각자 O(B) 의 대역폭을 필요로 한다. 결과적으로 네트워크 대역폭을 십분 활용하여 throughput 을 올린다.
Architecture of Honey Badger BFT
우선 전체적인 구조는 다음 그림과 같다. 네 개의 계층, 여섯 개의 모듈로 이루어져 있다. 논문은 하위 모듈의 기능과 모듈 간 통신을 블랙박스화 하여 이해하는 것을 권고한다. 이 글에서도 그러한 설명 방식을 따르겠다.
상위 계층부터 아래로 내려가면서 이해해보겠다.
HBQ(Honey Badger Queue)
클라이언트 어플리케이션에서 입력한 거래를 큐(Queue)에 넣는다. HBQ 는 B/N 개의 거래를 무작위(random)로 뽑아 각 노드에게 전파한다. 이때 무작위하게 뽑힌 B/N 개의 거래 집합을 ‘contribution’ 이라고 부른다.
무작위하게 거래를 선정하는 이유는 다음과 같다. 후에 각 노드에 흩어진 N 개의 Contribution 이 모여서 블록을 형성하게 된다. 블록의 크기, 즉 Contribution 합집합을 가장 크게 만들기 위해서는 중복되는 거래를 최소화 해야 한다. 중복 거래 최소화를 위해 선택한 방법이 ‘무작위’인 것이다.
HB(Honey Badger)
HB 단계에서는 우선 contribution 들을 암호화한다. 암호화된 거래는 그 내용이 보이지 않기 때문에 adversary 는 특정 거래를 선별(cherry picking)할 수 없다. 이 암호는 후에 (adversary 수) + 1 만큼의 동의가 있으면 복호화 할 수 있다(Threshold Cryptography).
Contribution 들을 암호화 한 후에는 하위 모듈 ACS 에게로 암호화된 contribution 을 보낸다. ACS 는 일련의 과정을 통해 contribution 을 블록에 포함시킬지 여부를 결정하여 그 결과를 HB 에게 반환한다.
HB 는 contribution 을 복호화하여 최종 거래 리스트에 포함시킨다.
ACS (Asynchronous Common Subset)
HB 로부터 암호화된 contribution 을 받은 ACS 는 각 노드마다 전체 노드 개수 N 만큼의 RBC 와 BA 를 생성한다. 그리고 자신의 노드에 해당하는 RBC 에 본인의 contribution 을 input 으로 넣는다.
RBC 는 contribution 을 전체 노드와 나눠 가진 후 그 결과를 ACS 에게 반환한다. 이때 RBC 의 output 은 contribution 들의 유효성에 대한 각 노드의 의견이다.
RBC 결과를 받은 ACS 는 이를 하위 모듈 BA 에게 전달한다. BA 에서는 각 노드의 의견을 바탕으로 투표를 진행하여 contribution 을 최종 블록에 포함시킬지 결정한다. 그리고 이 결과를 ACS 에게 전달한다.
정리하자면 ACS 는 contribution 을 받아와서 그 contribution 의 포함 여부를 결정하는 모듈인 것이다.
이제 하위 모듈 RBC 가 실용적(practical)으로 데이터를 전파하는 방식, 그리고 BA 가 비동기적으로 합의에 이르는 방식에 대해 설명하겠다.
RBC(Reliable Broadcast)
RBC 는 효율적 전송과 검증을 위해 erasure coding 방법 중 Reed-Solomon coding 과 머클 검증(Merkle Proof)을 사용한다.
우선 Contribution 을 노드 개수 N 개의 조각으로 쪼갠다. 그리고 각 노드에게 하나의 조각을 전송한다. 이후에는 전체 노드들이 각자 받은 조각을 나눠 가진다.
이때 Reed-Solomon coding 을 이용하면 전체가 아닌 N-f 개의 조각으로 전체를 복구할 수 있다. (f 는 adversary 의 수.) 또한 머클 검증을 이용하여 조각이 해당 contribution에 포함되는지 판단할 수 있다. 만약 검증을 통과한 조각이 N-f 개 이상이면 전체 contribution 을 복구한다.
이렇게 해서 contribution 을 복구했으면 Yes 를, 그렇지 않으면 No 를 ACS 에 리턴한다.
BA(Binary Agreement)
BA 는 ACS 로부터 각 노드의 의견을 받는다. 이 input 을 가지고 BA는 두 번의 투표 과정과 한 개의 추가적인 안전 장치로 최종 블록 포함 여부를 결정하여 리턴한다.
- 첫 번째 투표
각 노드는 자신의 투표 결과를 전체 노드에 전파한다. 마찬가지로 다른 노드들이 전파한 결과를 받는다.
혹시 f+1 개 이상의 노드가 동일한 결과를 낸다면, 자신이 갖고 있던 결과를 f+1 개 결과와 동일하게 만들어 다시 전파한다. 예를 들어 f+1 개 노드가 Yes 를 외치는데 나는 No 를 외쳤다면, Yes 로 바꾸어 다시 전파한다.
그러다가 2f+1 개 이상이 동일한 결과를 낸다면 그 값을 bin_value 에 저장한다. 이때 bin_value 는 ‘대다수가 동의한 값’을 의미한다. - 두 번째 투표
bin_value 를 담은 메시지(AUX 메시지)를 전체 노드에 전파한다. 이때 각 노드는 N-f 개 이상의 AUX 메시지를 받으면 TPKE 로부터 common coin 을 발급받는다. 이때 common coin 값이 N-f 개의 AUX 값과 일치하면 최종 결과로 선정한다. 만약 다르다면 위 과정을 반복한다. - 추가적인 안전 장치, Common Coin
왜 AUX 값을 최종 결과로 하지 않고 common coin 을 두는 것일까. Common coin 을 두지 않고 N-f 의 AUX 값을 최종 결과로 사용하는 경우에 그 결과를 전체 노드의 2/3 이상이 동의했다면 문제가 없지만 1/3 에서 2/3 사이일 때에는 문제가 있을 수 있다. 확실하게 우세한 쪽이 없기에 랜덤한 결과가 나올 수 있다.
이를 방지하기 위해 f+1 개 이상의 노드가 요청해야만 생성할 수 있는 common coin 을 추가하였다. 즉 최종 결과로 adversary 가 제안한 결과가 나온 경우, 재투표를 진행한다.
이때 BA 의 두 번의 투표 과정에는 비동기적 결과 합의를 위한 장치가 있다. N-f 개의 결과를 받기 전까지는 절대 No 를 외치지 않는다. 동기적 프로토콜에서 일정 시간 제한 Δ 가 지나면 해당 결과를 No 로 판단한 것과 달리, 판단 근거를 결과 개수에 두어도 adversary 여부를 판단할 수 있게 한 것이다.
Fade Out
다시 ACS 레이어로 올라온다. 이제 각 contribution 에 대한 N 개 노드들의 BA 값을 비교한다. 2/3 이상의 노드가 보낸 결과값이 최종 결과다.
HB 로 올라온다. 받아온 contribution 들이 유효하다면 복호화하고 최종 리스트에 포함시킨다.
클라이언트 어플리케이션에서 최종 리스트를 확인하여 거래를 성사시킨다.
분석
HBBFT 의 성능을 분석해보겠다.
논문에서는 PBFT 의 진행이 방해를 받을 수 있다는 것을 보이기 위해 네트워크 지연을 만드는 시뮬레이터를 제시하고, 이것을 사용한 경우를 Worst 케이스로 봤다. 위 표를 보면, PBFT 는 Worst 한 경우 거래 당 비트 수로 표현되는 communication complexity 가 무한정 늘어난다.
이에 반해 HBBFT 는 Optimal 한 경우와 Worst 한 경우에 모두 O(N) 으로 유지된다. HBBFT 는 비동기 프로토콜로 네트워크에 지연이 있어도 추가적인 비트 전송을 수행하지 않는다.
위 그래프는 Batch 크기와 Communication 비용의 관계를 보이고 있다. 초반의 Communication 비용은 노드 수에 따라 영향을 받고 (Batch 크기로 표현되는)거래 수에는 영향을 받지 않는다. 그러나 Batch 크기가 늘어남에 따라 Communication 비용은 거래 수에 맞추어 증가하게 된다. 다른 요인이 아닌 거래의 수에 따라 Communication 비용이 결정된다고 볼 수 있다.
위 그래프는 Batch 크기와 Throughput 의 관계를 나타내고 있다. Throughput 은 Batch 크기가 증가하는 것에 비례하여 증가한다. 거래의 수가 (거의) 온전하게 Throughput 을 결정한다는 것, 즉 네트워크 대역폭을 십분 활용하고 있다는 것을 의미한다.
위 그래프는 PBFT 와 HBBFT 의 노드 수에 따른 Throughput 을 나타낸다. PBFT 는 앞서 말한 바와 같이 리더에게 (Batch Size) * (number of Nodes) 만큼의 네트워크 대역폭을 요구하기에 노드 수가 증가함에 따라 Throughput 이 감소하고 있다. 반면 HBBFT 는 노드 수의 증가에 영향을 받지 않고 대체로 고른(even) 결과를 보인다.
맺는 말
Honey Badger BFT 는 불가능하다고 여겨졌던 비동기적인 합의가 실용적으로 구현 가능함을 보였다. 관심이 있다면 FLP Impossibility 를 이해한 후에 HBBFT 가 이를 정면 반박할 수 있었던 이유에 대해 생각해보는 것을 추천한다. 또한 2016 년의 HBBFT 를 넘어서 최근 각광 받고 있는 Istanbul BFT 에 대해 알아보는 것도 좋을 것이다.
참고 문헌
글쓴이: 이준하
