블록체인 네트워크의 통신비용 효율성을 고려한 PBFT 합의과정 연구

Ⅰ. 서 론

4차 산업혁명의 핵심기술로 소개되며 차세대 기술로써 인정받은 블록체인은 발표초기 비트코인과 같은 암호화폐 기술을 위주로 소개되었으나 이더리움(Ethereum), 하이퍼 레저(Hyper ledger)등의 기술의 발전에 힘입어 최근에는 금융, 공유경제, IoT, 물류 등 여러 분야에 걸쳐 활용되고 있다[1].

Grand View Research의 보고서는 블록체인의 2015년 시장규모가 509백만 달러 규모이고 연평균 37.2% 성장을 거듭하여 2027년에는 7,592백만 달러까지 성장할 것으로 전망하였다[2].

블록체인은 분산된 네트워크에 연결된 모든 노드에 동일한 데이터를 분산저장 및 공유하는 기술이다[3].

블록체인은 기록된 내용에 대하여 모든 노드가 동일한 데이터를 저장할 수 있도록 검증하고 합의한다. 이러한 합의 과정은 합의 알고리즘(Consensus algorithm)을 통하여 처리되며 합의 알고리즘을 통하여 데이터의 정확성이 유지되므로 합의 알고리즘은 블록체인의 핵심기술이라 할 만큼 중요하다[4].

블록체인은 사용자 범위에 따라 퍼블릭(Public) 블록체인과 프라이빗(Private) 블록체인으로 구분할 수 있다[4].

퍼블릭 블록체인은 비허가(Permissionless) 방식이라 하며 허가받지 않은 임의의 다수가 참여할 수 있다. 프라이빗 블록체인은 허가(Permissioned) 방식이라 하며 허가된 노드들만의 참여로 이루어진다. 블록체인 플랫폼의 형태가 비허가 또는 허가 방식인지에 따라 사용자 환경이 달라지므로 전혀 다른 형태의 합의 알고리즘을 사용할 수 있다.

비허가 방식의 경우 노드들의 채굴을 위한 과도한 노력과 지분 보유를 요구하는데 반해 허가 방식은 신뢰기반의 노드들만이 참여하기 때문에 채굴 등의 노력이 필요 없으며 선출된 대표 노드들을 통한 인증 및 합의를 통하여 투명한 거래내역 합의가 가능하다.

표 1은 블록체인의 타입에 대하여 표로 정리한 것이다. 본 논문에서는 허가된 사용자들만으로 구성된 프라이빗 블록체인의 합의 알고리즘 중 대표적으로 사용되는 PBFT의 처리 프로세스 및 활용 사례를 살펴보고 PBFT의 단점인 네트워크 통신비용의 효율적 관리를 위하여 수정된 PBFT를 제안한다.

Table 1.

Blockchain type[5]

Ⅱ. 연구 배경

최근 공공기관, 기업을 중심으로 프라이빗 블록체인을 활용한 활용이 증가하고 있다. 2장에서는 공공기관의 블록체인 활용 사례와 프라이빗 블록체인의 합의 알고리즘을 상세하게 살펴본다.

2.1 공공기관의 블록체인 활용

Maximize market Research의 2017년 보고서는 공공분야의 블록체인 활용 시장규모에 대하여 2017년 1억 달러에서 2024년에는 75억 달러의 규모로 성장할 것으로 전망하였다[6].

국내 공공기관의 블록체인은 대부분 신원인증, 온라인 투표, 의료 정보 공유, 복지 급여 관련 데이터공유 등이다.

표 2는 2020년 KISA에서 추진하는 공공기관 블록체인 시범사업의 사례 중 일부이다. 표 2의 사례는 대부분 신뢰기반 노드 간 연결을 기반으로 하는 프라이빗 블록체인 플랫폼을 사용하여 각 노드 간 투명한 데이터 공유, 데이터 이력 관리, 인증 등의 서비스 제공을 목적으로 한다.

Table 2.

Blockchain application cases of public institutions[7]

최근에는 디지털 ID를 활용하여 블록체인에 도입하는 사례가 소개되었으며 경상남도는 분산형 신원증명(DID)을 기반으로 시민 및 학생카드를 제작하고 공공시설을 활용할 수 있도록 하는 플랫폼을 추진할 예정이다. 공공기관 중 보건복지부는 다수의 정부 지자체와 중복으로 관리되는 서비스에 대한 정부 재정의 효율적 운영을 위하여 중복서비스 지급 지자체 및 정부 부처 간 블록체인으로 연결하여 복지 급여의 중복 지급을 개선할 예정이다.

2.2 프라이빗 블록체인 합의 알고리즘

퍼블릭 블록체인은 모든 노드가 신뢰가 없다는 가정에 기반하며 신뢰가 없는 네트워크에서 신뢰를 유지하는 방법으로 블록 생성 시 작업 증명방식 등과 같이 과도한 노력을 통하여 채굴을 하도록 하여 네트워크의 가치를 지키려는 노력을 한다[8]. 그에 반해 프라이빗 블록체인은 모든 노드가 신뢰를 가지고 있다는 가정에 기반 한다. 따라서 과도한 컴퓨팅 파워나 지분확보를 위한 노력이 필요 없다.

프라이빗 블록체인 합의 알고리즘은 Paxos, Raft, PBFT로 나눌 수 있다[9].

Paxos는 악의적 노드가 존재한다는 가정을 기반으로 하는 fault Tolerance System에서 여러 프로세스들 간에 동일한 값을 정확하게 합의하기 위한 프로토콜이다.

Paxos는 여러 개의 값이 합의를 기다리지만 결국에는 하나의 값이 선택되며 이를 위하여 제안자(Proposer), 투표자(Accepter), 학습자(Learner)의 역할로 나누어진다. Paxos는 여러 단계 역할에 의하여 다중의 합의와 인증이 이루어지므로 정확한 데이터 관리가 가능하다. 하지만 프로토콜 동작이 복잡하고 연산을 위한 노력이 필요하여 많이 적용되지 않는다[9].

Raft는 Paxos의 단점을 보완하여 보다 간단하게 개발되었다. Raft는 클라이언트의 블록 생성 요청에 대하여 선출된 리더(Leader)에 의하여 처리되고 해당 결과가 로그(Log)에 쓰이게 되어 리플리카(Replica)라 불리는 개별 노드에 반영된다. 리더에 오류가 발생할 경우 리더 선출 프로토콜에 의해 빠르게 리더가 재선출 된다는 장점이 있다[10][11].

선출된 리더는 각 리플리카에게 메시지를 전송하며 확인된 결과는 클라이언트에게 Reply 된다. 이 과정에서 리더의 오류 등에 대한 돌발 상황이 발생할 수 있다.

프라이빗 블록체인 환경에서 모든 노드는 신뢰를 가지고 있다고 가정하므로 Raft합의 알고리즘에서 사용하는 리더 선정 및 리더 주도의 합의 과정은 네트워크 통신 시간을 크게 단축할 수 있다는 장점을 지닌다. 그림 1은 Raft 서버 노드간 상태 전이를 나타낸다.

Fig. 1.

Raft server node state metastasize[11]

Ⅲ. 블록체인 성능 평가를 위한 요소

3.1 수정된 PBFT 개요

2.3절에서 살펴본 바와 같이 PBFT는 다양한 장점이 존재하는 반면 노드 수 증가에 따라 네트워크 통신비용이 증가한다는 단점을 지닌다.

본 논문에서는 프라이빗 블록체인 환경 기반 허가된 노드에 대한 신뢰를 전제로 하여 기존 PBFT의 기술에 Raft의 리더 선출 알고리즘을 적용한 수정된 PBFT(이하 RB_PBFT, Raft Based PBFT)를 제안하였다.

RB_PBFT의 프로세스는 다음과 같다.

- Request : Client가 모든 노드에게 블록 Confirm을 요청한다.
- Delegate Selection : 선출된 Primary 노드는 연결 노드 중 기존 명성을 고려하여 유효성 검증을 위한 위임자를 선정한다.
- Pre-prepare : Primary 노드는 모든 노드에 블록 Confirm을 요청하고 위임자에게는 별도의 권한을 부여한다.
- Prepare : Replica들의 요청 확인을 취합한다.
- Commit : Replica의 요청 확인 건수와 위임자의 검증 확인에 따라 블록 생성 여부에 대한 상태를 Client에 전달한다.
- Reply : 위임자의 검증 확인을 다른 노드에게 전파한다.

위의 프로세스에 따라 그림 2와 같이 Delegate Selection Pre-prepare 과정을 추가하고 Prepare, Commit 과정에서의 권위가 있는 노드 중심의 인증 과정이 진행된다. 이를 통하여 합의과정에서의 네트워크 통신비용에 대한 부담을 줄이고 인증과정에서의 노드 간 신뢰 확보 및 최종성(Finality)을 보장할 수 있다.

Fig. 2.

RB_PBFT process

제안 내용은 기존 PBFT 대비 브로드캐스팅을 통한 합의 절차가 간소화됨에 따라 네트워크 통신비용이 최소 O(N)으로 나타낼 수 있다.

3.2 성능 평가

본 논문에서는 기존 연구된 수식을 기반으로 수정된 PBFT의 특징인 선출알고리즘을 적용하여 수식을 변형하여 평가할 수 있도록 한다. 따라서 성능평가를 위한 별도의 실험환경은 필요하지 않으며 PBFT와 비교분석을 목적으로 한다.

RB_PBFT의 성능 평가를 위하여 2018년 보고된 연구논문의 평가항목을 참고하였다[2][14].

평가항목으로 권위 있는 노드 비율을 고려한 노드 수 대비 네트워크 통신비용과 초당 트랜잭션의 처리량을 적용하였다. 표 3의 평가요소는 네트워크 통신비용과 TPS이다. 상세 내용은 다음과 같다.

Table 3.

Performance evaluation factor[2][14][15]

① 네트워크 통신비용

전체 노드 수가 N으로 주어졌을 때 노드 간 합의 및 인증건수는 4, 16, 36 ⋯이다.

샘플 데이터를 통하여 R을 통하여 예측치를 계산하였을 때 f(x)=16x–13.33(≒2x²)를 유도할 수 있다. 동일한 조건에서 RB_PBFT의 네트워크 통신비용을 구하기 위한 수식을 그림 3과 같이 유도하였다.

Fig. 3.

Data sampling and formula extraction process

도출된 수식에 의하여 PBFT와 RB_PBFT의 네트워크 비용 증가량을 확인하기 위하여 다음과 같이 그래프로 노드 수 증가 대비 네트워크 통신비용을 특정하였다.

그림 4는 그림 3의 수식에 대하여 노드수를 1~11까지 증가하며 네트워크 통신비용을 측정한 것이다. RB_PBFT의 경우 PBFT 대비 노드수 증가에 따라 통신비용의 차이가 더욱 큰 것을 알 수 있다.

Fig. 4.

Network communication cost comparison analysis

② 초당 트랜잭션 처리량

총 노드 수 N에 대하여 블록 생성 시간을 t, 블록의 크기를 s_b, 트랜잭션의 크기를 s_t라 하고 네트워크 비용을 적용하여 다음과 같은 수정된 TPS 계산이 가능하다. 식 (1)은 기존 논문에 제시된 수식[17]을 적용하였으며 제안한 합의 알고리즘에 의하여 합의에 참여하는 노드의 비율인 ①을 반영하였다.

$\[ \begin{array}{c}\left(\left(s_b/s_t\right)\mathrm{*}\left(1/t\right)\right)/network cost\hfill \\ \begin{array}{c}\mathrm{*}\mathrm{ }\mathrm{n}\mathrm{e}\mathrm{t}\mathrm{w}\mathrm{o}\mathrm{r}\mathrm{k}\mathrm{ }\mathrm{c}\mathrm{o}\mathrm{s}\mathrm{t}\mathrm{ }:\mathrm{ }\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{p}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{a}\mathrm{l}\mathrm{ }\mathrm{t}\mathrm{o}\mathrm{ }\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{ }\mathrm{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\mathrm{ }\mathrm{o}\mathrm{f}\hfill \\ \mathrm{ }\mathrm{ }\mathrm{ }\mathrm{a}\mathrm{u}\mathrm{t}\mathrm{h}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{z}\mathrm{e}\mathrm{d}\mathrm{ }\mathrm{n}\mathrm{o}\mathrm{d}\mathrm{e}\mathrm{s},\mathrm{ }\mathrm{d}\mathrm{e}\mathrm{l}\mathrm{e}\mathrm{g}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{ }\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e},\mathrm{ }\mathrm{e}\mathrm{t}\mathrm{c}.\hfill \end{array}\hfill \end{array} \]$

(1)

위의 수식에 의하여 샘플 데이터를 활용한 PBFT와 RB_PBFT의 처리량 계산 수식을 R을 통하여 예측하고 다음과 같이 도출하였다. PBFT의 샘플 데이터에 의한 수식은 1.5x+3.178e-14((≒1.5x+3.2) 정도에 해당하며 RB_ PBFT는 13x+2의(≒x²) 수식이 도출된다. 다만 네트워크 상황에 따른 샘플 데이터의 변화 고려가 필요하다.

그림 6은 그림 5의 수식에 대하여 노드수를 1~11까지 증가하여 트랜잭션 처리량을 측정한 것이다.

Fig. 5.

Formula for transaction throughput

Fig. 6.

Transaction throughput analysis

RB_PBFT의 경우 PBFT 대비 노드수 증가에 따라 트랜잭션 처리량이 더욱 증가함을 알 수 있다. 하지만 본 논문에서 제안한 바와 같이 합의 알고리즘에 참여하는 노드 중 리더의 오류율에 대한 반영이 제외되어 있어 해당 사항을 포함하였을 경우 연산 비용이 증가할 수 있다.

Ⅳ. 결 론

본 논문에서는 대표적인 프라이빗 블록체인의 합의 알고리즘인 PBFT를 수정한 형태인 RB_PBFT를 제안하였다.

RB_PBFT는 PBFT 알고리즘의 장점인 데이터의 정확한 관리와 단점인 네트워크 통신비용 증가의 특징을 고려하여 Raft의 리더 선출 알고리즘을 적용시킨 형태이다. 제안한 내용은 프라이빗 블록체인은 허가된 노드들만 참여하는 네트워크라는 점을 고려하였으며 Raft의 리더 선출 알고리즘에 의하여 기존 PBFT에서 네트워크에 참여하는 모든 노드를 대상으로 진행한 검증 및 인증 과정을 단순화하였다.

RB_PBFT의 성능 평가를 위하여 네트워크 통신비용과 초당 트랜잭션 처리량으로 제한하여 수식을 통하여 PBFT와 RB_PBFT를 비교하였다. 성능 평가 시 권위 있는 노드의 비율이 적용될 수 있도록 기존 수식을 변형하였으며 돌발 상황이 발생하지 않는다는 가정 하에 데이터를 샘플링하고 새로운 수식을 도출하였다. 성능 평가의 결과 네트워크 통신비용은 PBFT 대비 RB_PBFT가 O(N²)과 O(N)의 결과로 분석되었으며 초당 트랜잭션 처리량 역시 1.5x와 13x의 비율로 변화됨을 분석하였다.

본 논문의 제한점은 네트워크에서 발생할 수 있는 외부요인과 돌발 상황을 고려하지 않았다는 점이다.

향후 권위 있는 노드의 발굴 및 해당 노드로의 통신에 대한 과부하가 요구될 경우 제시하는 수식에 해당 요인에 대한 변수가 추가되어야 할 것이다.

References

• Don Tapscott, "Alex Tapscott, Blockchain Revolution", Eulyoo Publishing Co, 2017.
• https://www.grandviewresearch.com/industry-analysis/blockchain-technology-market, [accessed: Mar. 03, 2020].
• Bang Jung-ho, "Public SW System Application Team Software Industry Promotion Headquarters", Korea IT Industry Promotion Agency, Blockchain Industry Status and Trends, 2018, No. 17, https://www.nipa.kr/index.jsp, . [accessed: Mar. 03, 2020]
• https://www.santanderbank.com/, [accessed: Mar. 03, 2020]
• Buterin Vitalik, "Ethereum white paper", https://github.com/ethereum/wiki/wiki/%5BKorean%5D-White-Paper, . [accessed: Mar. 03, 2020]
• Yonatan Sompolinsky and Aviv Zohar, "Secure High-Rate Transaction Processing in Bitcoin", https://fc15.ifca.ai/preproceedings/paper_30.pdf, . [accessed: Mar. 03, 2020]
• https://www.kisa.or.kr/notice/bid_View.jsp?cPage=1&mode=view&p_No=35&b_No=35&d_No=6995&ST=&SV=, [accessed: Mar. 03, 2020]
• Satoshi Nakamoto, "Bitcoin: A peer-to-peer electronic cash system", ttps://git.dhimmel.com/bitcoin-whitepaper/, , [accessed: Mar. 03, 2020]
• Dongyan Huang, Xiaoli Ma, and Shengli Zhang "Performance Analysis of the Raft Consensus Algorithm for Private Blockchains", IEEE Transactions on Systems, Man, and Cybernetics: Systems IEEE Trans. Syst. Man Cybern, Syst. Systems, Man, and Cybernetics: Systems, IEEE Transactions, 2020. [https://doi.org/10.1109/TSMC.2019.2895471]
• Raft.github.io/Raft.pdf [accessed: Mar. 03, 2020]
• https://www.geeksforgeeks.org/Raft-consensus-algorithm/, [accessed: Mar. 03, 2020]
• Yixin Li, Zhen Wang, Jia Fan, Yili Luo, Chunhua Deng, and Jianwei Ding, "An Extensible Consensus Algorithm Based on PBFT", 2019 International Conference on Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC) Cyber-Enabled Distributed Computing and Knowledge Discovery (CyberC), 2019 International Conference, 2019
• Crunchbase, Available: http://www.crunchbase.com, [accessed: Mar. 03, 2020]
• Jinseok Kim, "A Design of Secure and Efficient PBFT Consensus Algorithm in Blockchain", Master's Thesis for Soongsil University, 2019.
• S. H. Yoo, "Blockchain Consensus in D2D Communication Environment Safe and efficient using algorithm", Master Thesis for Ewha Womans University, 2018.