분산시스템 및 컴퓨팅 [PBFT협의 알고리즘을 이용한 블록체인 구현]

4학년 1학기 분산시스템 및 컴퓨팅 과목을 수강했습니다. [ 최종 성적 : C+ ]

 

깃 레포 : https://github.com/Wcwdfu/Project_PBFT

GitHub - Wcwdfu/Project_PBFT: [24년 4학년 1학기] 분산시스템 및 컴퓨팅 팀프로젝트 : PBFT협의 알고리즘을

 학교 수업을 들으면서 어느정도 기간이 잡힌채 진했던 프로젝트들 중에서 유의미했다고 생각되는 활동들을 계속 남겨보고 있습니다.

 (업로드한 4개의 프로젝트중에 가장 퀄리티가 낮다고 생각됩니다... 충분히 어려운 내용이기도 했고 6전공을 들으면서 하기에 너무 벅찼던 것 같습니다. 그리고 딱 한번 보는 110점만점? 필기시험이 있었는데 평균이 90점 가까이 나온 시험에서 55점인가를 맞아버리며 뒤에서 3등을 해버리곤 이것이 고스란히 성적에 반영이 된듯 합니다ㅎㅎ)

 

 이 수업은 미들웨어인 하둡을 위주로 간단한 부분에 대한 실습과 더불어 분산시스템에 대한 대략적인 큰 개요 + 블록체인 에 대해서 크게한번 아주아주 간략히 훑어볼 수 있는 수업이였습니다. 인원이 30명이 채 안됬던것 같고 그렇게 기말고사가 프로젝트 대체로 진행되었습니다. 한 8~9팀 정도 있었던 것 같은데 모든인원이 본인이 하고싶은 주제를 작성해서 제출하면 교수님과 조교님이 거기서 선발하여 주제를 고르고, 주제가 선택된 사람이 팀장, 선택되지 못한 사람들이 팀원이 되어서 진행하는 구조로 시작했습니다.

 

 

처음에는 제 주제가 선택되어 저는 팀장이 되었었습니다. 근데 대부분의 프로젝트 등에서 팀장을 자처했었지만 분산시스템이라는 영역이 제겐 너무나도 생소했기때문에 제 주제 철회를 요청드렸고, 받아들여져서 팀원으로써 다른 팀에 합류하게 되었습니다.

 

 이때 한번쯤 들어봤던 카프카, 엘라스틱서치 등등 을 활용한 주제들이 나왔지만 2팀 정도가 블록체인 구현을 주제로 하고있었고, 이때가 아니면 블록체인에대해 경험해볼 기회가 없다고 생각해서 + 평소에도 코인투자에 지대한 관심이 있었고 web3에 대해 어느정도 주워들은 내용이 있었어서 + 재밌을것 같아서 블록체인 구현을 주제로 선정한 팀에 들어가게 되었습니다.

 

 

 

 그렇게 주제를 선정하다가, 이전년도 수업의 팀에서 이미 일반적인 블록체인을 구현으로 프로젝트를 진행했었기 때문에 저희팀은 차별점이 필요했고, 모여서 회의를 진행하던중, 일반적으로 모두에게 친숙한 public한 형태의 블록체인이 아닌 private한 형태의 블록체인에서 사용되는 합의 방식 중, pbft협의를 이용한 블록체인을 구현하는것으로 결정하였습니다.

 일반적으로 불특정 다수의 모든 참여자가 참여할 수 있는 public한 형태의 블록체인은 엄청나게 많은 노드가 존재하며, 블록을 추가하는데 사용하는 합의알고리즘은 pow, pos 등등을 사용하게 됩니다. 일차원적으로 말해 아마 비트코인은 pow, 이더리움이 pos를 사용합니다. 제 블로그 취지에 맞게 pow, pos가 뭔지는 인터넷에 널렸기때문에 자세히 다루지 않겠습니다. 따라서 저희는 p2p 네트워크 상에서 조금더 적은규모의 노드에서 충분히 신뢰가능한 참여자들 사이에서 비잔틴문제에 대한 해결책이 존재하는 pbft협의 알고리즘을 사용하는 방식으로 프로젝트를 진행하게 됩니다.

 

(비잔틴 문제란 간단히 말해 분산시스템에서의 신뢰성과 합의 문제를 설명하기 위해 고안된 이야기로 악의적인 요소나 오류에도 불구하고 안전한 합의를 이루는 것에 대한 이야기 입니다.)

 

 

(위 그림은 원본논문에서 가져온 그림이였던것 같습니다. pbft협의 알고리즘의 과정을 도식화한 그림입니다. )

음.. 결론부터 말하면 pbft협의 알고리즘에 대해 인터넷을 열심히 찾아봤지만 이때 분명히 느꼈던게 잘못된 정보도 있었고 그 어떤블로그에서도 진짜 이해하기쉽게 완벽하게 풀어쓴 블로그가 없다는걸 깨닫게 된것 같습니다. 원문으로된 영어논문까지 부분부분 필요한부분을 찾아서 읽어보게 되었는데요. 큰 그림에서는 어렴풋이 이해가 되도 이거를 python을 이용해 코드적으로 구현하려고 하니 의문점과 질문은 꼬리에 꼬리를 물어 계속해서 늘어났고 어느정도 머리로 이론이 이해가 되었어도 코드로 이걸 다시 구현하는게 다른차원의 문제라는것을 깨닫게 됬던 활동이였던 것 같습니다.

 

 저는 발표진행에 있어 pbft협의 알고리즘에 대한 소개와 일정 부분 구현을 담당했는데, 기억을 더듬에 간략히 소개해드리겠습니다. 먼저 말씀 드리자면 코드레벨에서도 이론적인 내용을 전혀 100%담지 못했습니다. 이는 아쉬운부분인것 같습니다.

 

 참, pbft협의 알고리즘을 단순하게 한마디로 정의한다면 전체 노드의 수가 3n+1개라고 할 때, n개 이하의 노드가 장애나 악의적인 다른 시도를 해도 안전하게 유효한 합의가 보장되는 알고리즘을 말합니다.

 

알고리즘의 시작입니다. 클라이언트가 작업요청을 primary node에게 전송합니다. primary노드 선정공식이 있는데 결론적으로 말하면 id가 낮은 값부터 오름차순으로 올라가게 됩니다. primary node는 바뀔 수 있기때문에 선정하는 공식이 존재하는거구요. 알고리즘 진행 과정에서 합의가 실패하는경우 primary node를 재선정하는 과정을 가지게 됩니다. 이를 view change라고 언급한다고 하구요.

 

 

 논문에서 Pre-prepare 단계 라고 부르는 구간입니다. 그러면 primary node는 v,n,d 라는 값을 포함해서 다른 노드들에게 메시지를 braod cast 합니다. 각 내용은 위 사진을 참고하시면 될것 같습니다.

 

 

 논문에서 prepare라고 부르는 단계입니다. 각 노드들은 primary node로 부터 받은 메세지들이 유효한지 검증을 진행합니다. 유효한 경우에 모든 노드에 prepare 라는 메세지를 전송하게 됩니다.

 여기서 구현상에 의문이 남아있습니다. 각 노드들은 검증단계에서 뭘 이용해서 검증하는지, 뭐에 기반한 데이터로부터 검증을 하는지 해소하지는 못했습니다. v,n,d값들을 통해 검증을 한다 해도 이 값들과 비교검증을 하기위한 비교군이 필요합니다. 그 비교군이 어디서 어떻게 오는지 깨끗히 이해되지 않아 저희는 아마 단순히 primary node의 v값만을 사용했던것으로 기억합니다. 

 

 논문상에서 commit 이라고 부르는 단계입니다. 이전 단계에서 broad cast된 prepare 메세지들을 2n개를 수집합니다. 

어딘가에서는 2n+1이라 하는 곳도 있었는데 제가 알아본바는 2n인것 같습니다. 이마저도 깨끗하게 해소되진 않았음을 알려드립니다..

 그래서 2n개의 메세지를 수신하는 이유는 다시 pbft협의 알고리즘의 정의를 생각하면 됩니다. 3n+1개에서 최대 n개 이하의 노드가 악의적인 행동을 해도 안전하게 합의를 진행하는 알고리즘입니다. 즉 2n+1개를 수신한다고 생각했을때, 이중 n개가 잘못된 노드라고 가정을 해도 n+1이 되면 과반이상이 정상노드인것으로 말할 수 있게되고, 여기서 2n+1이 아닌 2n개인 이유는 자기자신의 message는 제외하게되기 때문입니다. 여기서 자기자신은 정상노드인것으로 간주하는 듯 합니다.

 그렇게 2n개의 prepare 메세지들을 수집하게 되면 prepared certificate상태가 되는데 이상태가 되면 다시 모든 node들에게 commit 메세지를 broad cast하게 됩니다.

 여기서 또한번 모든 노드들은 commit mesage를 2n+1개를 수집할때까지 기다리게 되는데, ( 여기서는 2n개가 아니라 2n+1개인것으로 제 개인적으로는 결론내렸습니다.) 이 상태까지 만족한 노드들은 commit certificate상태가 되게 됩니다.

 

 이 과정도 블로그마다도 얘기가 달랐고 chat gpt도 당연히 말이 매번 달라졌습니다. 영어로된 원서는 더 난해하게 적혀있었고 더 큰 시간을 들였다면 완전히 해소할 수도 있었겠으나 당시에는 그렇게까지 할만한 여유가 없었음을 양해의 말씀을 드립니다 ...

 

 그렇게 앞서 위에서 본 prepared certificate 하면서 동시에 commit certificate한 노드들은 committed certificate 상태가 되며 클라이언트의 요청을 수용하게 됩니다. 그렇게 노드들은 클라이언트에게 결과를 응답하게 됩니다.

 

 

여기까지가 나름 한정된 시간에서 제가 알아본 pbft 협의 알고리즘 이였습니다. 본질적으로 보면 사실 당연히 수박겉핥기 느낌도 강했고 ... 이해가 가지 않는 부분도 여전히 많습니다. 합의 알고리즘에 있어 pow, pos, pbft협의 등등은 뭐가 더 낫고 낫지않고의 영역이 아닌 성격에 따라 달라지는 부분이며 각각의 장점과 단점이 존재하게 되는 구조이구요. 무엇보다 그래서 왜 굳이 어디서 private한 형태의 블록체인을 무슨목적과 장점을 근거로 사용하는 것이며, 소수의 신뢰가능한 참여자들로부터 네트워크를 형성한다는데 비잔틴 문제를 고려하고 있는건지 이해가 가지않는것이 투성이 입니다. 

 

 

 사진이 작아서 잘 안보이실 수 있습니다 ..만

그렇게 저희가 pbft협의 알고리즘의 대한 대략적인 컨셉을 흉내낸 프로젝트의 시연결과는 위와 같습니다.

각각의 피어를 일일히 추가해 주어야 하구요. 자동 양방향 연결되도록 구현하였기에 하나의 노드에서 연결하면 자동으로 반대노드에서도 연결이 진행됩니다.

악의 적인 노드 설정을 역할로써 on/off 방식으로 설정되게 구현하였습니다.

따라서 전체 노드수 3n+1에서 n개 이하의 악의적인 역할을 수행하는 노드가 있는 경우에 대해서도 정상 작동 하는것을 확인해볼 수 있었습니다.

 

 이렇게 합의 과정마다 로그를 출력하게 하여 어떤 일이 발생하는지 볼 수 있도록 하였습니다.

 

 

 

참고 자료

1. [케블리] #48. 합 알고리즘 이해하기 - PBFT Consensus Algorithm

https://steemit.com/consensus/@kblock/48-pbft-consensus-algorithm

2. 프랙티컬 비잔틴 장애 허용 기반 블록체인의 확장성과 내결함성 평가 및 비교 분석 – 이은영, 김남령, 한채림, 이일구

3. Practical Byzantine Fault Tolerance and Proactive Recovery

http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf

4. CASTRO, M.AND LISKOV, B. 1999b. Practical Byzantine fault tolerance. In Proceedings of the Third Symposium on Operating Systems Design and Implementation (OSDI), USENIX, New Orleans

https://css.csail.mit.edu/6.824/2014/papers/castro-practicalbft.pdf