[Hyperledger Fabric] 블록체인에 사용되는 합의 알고리즘 3 - PBFT, DPoS, Paxos, Raft

3. PBFT(Practical Byzantine Fault Tolerance)

PBFT는 비잔틴 장군 문제를 해결하기 위한 알고리즘으로, 이를 이해하기에 앞서 비잔틴 장군 문제에 대해 알아야 한다.

​

Q. 비잔틴 장군 문제란?

1) 비잔틴의 장군들이 흩어져서 성을 공격할 때, 장군들이 동시에 공격해야만 승리할 수 있다.

2) 또한, 흩어져있기 때문에 공격 시간을 정하기 위해선 메시지를 주고받아야 한다.

3) 하지만 이때 배신자가 껴있어서 정확한 시간을 공유할 수 없는 경우가 생긴다. 그리고 장군들은 누가 첩자인지 찾아낼 방법이 없다.

4) 이 경우 어떻게 신뢰도 있는 메시지를 주고 받을 수 있을까?

​

아래는 비잔틴 장군 문제를 그림으로 표현한 것이고, 그림에서 왕관은 다른 장군들을 이끄는 리더 장군을 의미한다.

​

​

블록체인이 구동되는 네트워크는 비동기 방식이다. 따라서 비동기 네트워크에서의 완벽한 합의 알고리즘은 존재할 수 없다. 노드 간의 합의가 된 상황에서 어느 노드가 접근하든 동일한 값이어야 하는 safety와 트랜잭션 혹은 블록에 문제가 없다면 네트워크 내에서 반드시 합의가 이루어져야 하는 liveness를 보장할 수 없기 때문이다(safety와 liveness는 어떠한 합의 알고리즘이 네트워크에서 통용되기 위한 특성).

​

이러한 블록체인 네트워크에 비잔틴 장군 문제가 발생했다는 것은 블록체인 네트워크(비동기 네트워크)에서 배신자 노드가 발생하여 신뢰있는 합의를 도출해내기 힘든 경우이고, PBFT는 이러한 비잔틴 문제를 해결하기 위한 알고리즘이다. PBFT 합의 알고리즘은 배신자 노드 f개가 있을 때, 총 노드 개수가 3f+1개 이상이면 해당 네트워크에서 이루어지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한다.

​

PBFT 합의 절차에 대한 정리는 이 사이트(https://steemit.com/consensus/@kblock/48-pbft-consensus-algorithm)를 확인하면 된다. 논문 내용을 바탕으로 알기 쉽게, 수학적 근거를 바탕으로 정리되어 있다. 그런데 설명에 약간의 오류가 있으니 댓글 또한 꼭 참고해야 한다(노드 간의 메시지 수집에 대한 설명 잘못됨).

​

현재까지 블록체인에서 BFT를 합의 알고리즘으로 채택했다는 경우는 대부분 PBFT 합의 알고리즘을 조금씩 변형했다고 볼 수 있다고 한다. 대표적으로 Tendermint는 PBFT에 DPoS를 결합했고, 이더리움 Casper는 PoW 방식(채굴) 위에 PoS + PBFT 형태의 블록 검증 시스템을 제안했다고 한다. 또한, Hyperledger Fabric, R3, Riple, EOS 등 퍼블릭 뿐만 아니라 프라이빗 블록체인에서도 다양하게 사용되고 있다.

​

장점 : 이전의 PoW나 PoS와는 달리 다수결로 의사결정한 뒤에 블록을 생성하기 때문에 블록체인의 분기가 발생하지 않는다. 따라서 한 번 확정된 블록은 변경되지 않기 때문에 블록의 불변성을 보장한다. 또한 PoW와 같이 조건을 만족시킬 때까지 계산을 반복하지 않아도 되기 때문에 속도가 빠르다. 그리고 부정 사용을 하고자 해도 과반수를 획득해야 하고, 만약 부정 사용을 하더라도 모든 참가자가 리더의 움직임을 감시해서 거짓말이라고 판단한다면 다수결로 리더 교체를 신청할 수 있기 때문에 장애에 매우 강력한 내성을 가진 알고리즘이라 할 수 있다.

​

단점 : 언제나 참가자 전원과 의사소통을 해야하기 때문에 참가자가 증가할수록 통신량은 증가하고 처리량은 저하된다. PoW나 PoS가 수천개의 노드를 만들 수 있는 반면, PBFT는 노드의 개수가 수십개로 한정적이다.

​

​

​

4. 위임 지분 증명 (DPoS, Delegated Proof of Stake)

기존 PoS 알고리즘에서는 코인을 보유한 누구나 트랜잭션 검증에 참여하여 노드가 될 수 있었다. 하지만 많은 사람들이 검증에 참여하면 속도가 느려지므로, 이를 해결하기 위해 검증할 대표자를 투표하고 그들끼리만 검증하는 방식이다.

​

선출되는 노드의 숫자는 각 네트워크마다 다른데, 보통 합의가 동률로 나올 경우를 방지하기 위해 홀수로 선출한다. 선출되지 않더라도 투표에 참여한 노드는 코인을 얻을 수 있다. 컴퓨터를 켜고 노드를 돌릴 필요가 없기 때문에 일반 사용자 입장에서도 PoS 방식보다 편하다.

​

장점 : 기존 방식인 PoS보다 속도가 훨씬 빠르다.

단점 : 블록체인의 목적 중 하나인 탈중앙화와는 의미가 멀고, 소수의 대표자들이 누구인지 공개되므로 해커에게 노출된다.

​

​

​

​

**** 앞으로 설명할 Paxos와 Raft에 대한 설명은 블록체인에서의 합의 알고리즘보다는 분산 시스템에서의 합의(노드 간의 상태 공유) 알고리즘에 더 가깝다.

​

​

5. Paxos

가장 유명한 합의 알고리즘 중 하나이다. 여러 노드 사이에서 하나의 값을 합의하기 위한 synod 알고리즘과 이를 이용하여 동일한 순서로 오퍼레이션을 실행할 수 있도록 sequence number별로 오퍼레이션을 합의하는 알고리즘으로 구성되어 있다.

​

합의란 여러 프로세스로부터 제안을 받고 그 값들 중 하나의 값을 선택하면 선택한 값을 여러 프로세스들이 인지하는 문제이다. Synod는 합의를 proposer, acceptor, learner로 프로세스를 구분한다. 즉, 값을 제안하는 proposer와 하나의 값을 선택하는 acceptor, 그리고 선택값을 여러 프로세스들이 인지하도록 하는 learner로 나뉜다.

​

Paxos의 특징은 과반수의 동의를 얻었다면 그 동의 내용이 나중에 변경되지 않는다는 것이다. 리더를 중심으로 합의 형성을 수행하지만 Byzantine Fault 모델이 아니기 때문에 리더가 부정을 저지르는 경우엔 동기화되지 않는다. 그리고 참여자가 거짓으로 신고한 경우에도 동기화되지 않기 때문에 악의를 가진 참가자가 이는 환경에서는 운영하기 적절치 않다. 또한, 합의 형성에만 특화되어 있기 때문에 프로그램으로 구현하기 위해선 시스템적으로 검토해야 할 점이 많다.

​

생각보다 복잡하고 이해하기 어려운 알고리즘이였다. 관련 원서 논문을 읽기에는 시간이 부족해서 논문을 정리해놓은 블로그를 참고했다.

​

*참고 블로그

https://m.blog.naver.com/kmk1030/220700903506

http://blog.lastmind.io/archives/684

​

​

​

​

6. Raft

우선은 이 사이트(http://thesecretlivesofdata.com/raft/)에서 그림을 통해 Raft에 대해 더 쉽게 이해할 수 있다.

​

1) Raft 알고리즘의 노드는 Follower, Candidate, Leader 총 3가지의 state를 갖는다. 모든 노드는 follower state를 가지고 시작하며, 만약 follower가 leader의 응답을 받지 못 하면 candidate 상태로 전환될 수 있다.

​

2) 투표를 관리하기 위한 두 개의 timeout 설정이 있는데, 첫 번째는 Election timeout이다. 이는 Follower에서 Candidate로 전환되기까지 기다리는 시간을 의미한다. 두번째는 Heartbeat timeout이다. 주기적으로 리더가 메시지를 보내는데 이 heartbeat timeout 안에 보내야 leader가 살아있다고 판단한다. 만약 메시지가 timeout 내에 도착하지 않으면 노드는 바로 candidate이 된다.

​

3) Leader Election 과정

3-1) Election timeout이 끝나면 Follower는 Candidate가 되고, Election term을 시작한다. Candidate는 본인에게 투표하고, 다른 노드들에게 투표 요청 메시지를 전달한다. 이때 timeout이 시작되는데, 이 timeout이 끝나기 전까지 과반의 투표수를 획득해야 한다.

3-2) 만일 메시지를 받는 노드가 해당 Election term 내에서 투표를 하지 않았다면, 메시지를 전달해준 candidate에게 투표한다.

3-3) 투표를 마친 노드는 Election timeout이 초기화되고, 가장 많은 표를 받은 노드가 Leader로 선정된다.

3-4) 리더가 선정된 후, 시스템의 모든 변화는 리더를 통해 결정된다. 클라이언트가 리더에게 데이터를 전달하면, 리더는 데이터를 복제하여 follower에게 전달한다(이는 Append Entries 메시지를 통해 이루어짐). Follower는 전달받은 데이터를 commit하고 결과를 리더에게 전달한다. 리더는 이 결과를 다시 클라이언트에게 전달한다.

​

​

​

블록체인에서 주로 채택하는 합의 알고리즘이 퍼블릭인지 프라이빗인지에 따라 달랐다. 합의 알고리즘을 알아보면서 생각한 그 이유는 "non-Byzantine" 조건을 프라이빗 블록체인에선 가정하고 있기 때문인 것 같다. 여기서 "non-Byzatine" 조건은 교환할 정보의 위조가 없다는 의미이다. 프라이빗 블록체인은 누구나가 아닌 승인된 참여자들만이 네트워크에 참여할 수 있으므로 악의를 가지고 네트워크를 방해할 노드는 없을 것이다. 물론 있을 수 있지만, 기본적으로 없다는 전제 하에 Paxos와 Raft를 사용하는 것 같다.

​

(즉, 분산 시스템에서의 합의 알고리즘은 노드 간의 동일한 상태를 유지하기 위한 방법, 블록체인에서의 합의 알고리즘은 노드 간의 상호 신뢰를 할 수 없는 상황에서 어떻게 합의를 이룰 지 그에 대한 해결 방법)

​

​

​

​

[참고]

​

How the Byzantine General Sacked the Castle: A Look Into Blockchaiin

https://medium.com/@DebrajG/how-the-byzantine-general-sacked-the-castle-a-look-into-blockchain-370fe637502c

​

BFT 기반 합의 알고리즘

https://blog.theloop.co.kr/2017/06/21/bft-%EA%B8%B0%EB%B0%98-%ED%95%A9%EC%9D%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/

​

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

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

​

Dpos란 무엇인가 (Delegated Proof-of-Stake)

https://isnow.tistory.com/308

​

[미완] Distributed Consens 알고리즘 정리

https://not-for-me.io/post/blockchain/distributed/

​

Paxos Made Simple

http://blog.lastmind.io/archives/684

​

블록체인 합의 알고리즘 알아보기 2편(PBFT, Sieve, Tendermint, Raft, Paxos, PoA)

https://medium.com/landingblock-korea/6-%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-%ED%95%A9%EC%9D%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0-2%ED%8E%B8-pbft-sieve-tendermint-raft-paxos-poa-a8af8d6eaccd

​

Raft consensus algorithm

http://swalloow.github.io/raft-consensus

​

[컴][알고리즘] Raft 알고리즘

http://i5on9i.blogspot.com/2016/09/raft.html