Sawtooth PBFT 소개

Contents

Hyperledger Sawatooth는 컨센서스(consensus API)와 SDK를 이용해서 동적 컨센서스를 지원한다. 컨센서스의 지원을 위해서 RAFT도 널리 사용하지만 비잔틴 결함 허용(BFT - Byzantine Fault Tolerance)은 아니기 때문에, 적대적 신뢰특성(상호신뢰를 할 수 없는)을 가지는 컨소시엄 네트워크에는 적합하지 않다.

이러한 간격을 메우기 위해서 PBFT(Practical Byzantine Fault Tolerance) 합의 알고리즘을 선택하고 있다. 2018년 Sawtooth PBFT 컨센서스 엔진에 대한 작업을 시작했으며 첫번째 안정버전을 릴리즈하기 위해서 계속 개발 중이다. 여기에서는 PBFT 알고리즘을 요약하고 Sawtooth 에서 어떻게 작동하는지 설명한다.

PBFT는 MIT의 Miguel Castro 와 Barbara Liskov가 1999년에 작성한 논문 Practical Byzantine Fault Tolerance에 소개됐다. 당시의 다른 알고리즘과 달리 PBFT는 비동기 환경에서도 작동 할 수 있도록 디자인된 최초의 Byzantine fault tolerance algorithm 이었다. PBFT는 신중하게 정의됐으며, 잘 확립되었고 이해도 역시 높기 때문에 Hyperledger Sawtooth를 위한 탁월한 선택이 될 수 있다.

PBFT는 Raft와 몇 가지 유사한 점이 있다.

• 복권 스타일 알고리즘과 달리 리더 기반이며 non-forking 이다.
• 공개등록을 지원하지 않는다. 대신 관리자가 노드를 추가하거나 제거 할 수 있다.
• 전체 피어링이 필요하다. (모든 노드들은 다른 모든 노드들과 반드시 연결되야 한다.)

PBFT는 BFT(Byzantine Fault tolerance)를 제공하는 반면, Raft는 충돌 내결함성만 지원한다. BFT를 제공한다는 것은 네트워크에 잘못된 노드가 있다고 하더라도 안정적으로 작동할 수 있다는 것을 의미한다. PBFT 네트워크에서는 필요로하는 최소한의 네트워크가 올바르게 작동하는 한, 특정 노드가 네트워크를 조작하지 못하게 할 수 있다.

PBFT논문에 상세한 알고리즘이 정리되어있다. 여기에서는 Hyperledger Sawtooth 맥락에서 알고리즘의 핵심 포인트를 요약할 것이다. 원문에서는 모든 분산 애플리케이션에서 광범위하게 적용 할 수 있다. 이 것을 블럭체인에 특정해서 설명하려 한다.

PBFT 네트워크는 0에서 n-1까지의 일련의 노드들로 구성된다. 여기에서 n 은 네트워크에 있는 노드의 갯수다. PBFT 네트워크에서는 허용 가능한 불량(bad) 노드 갯수가 정의된다. 이 허용 가능한 불량 노드의 갯수를 상수 f라고 한다. 불량 노드의 갯수가 f를 초과하지 않는 한 이 네트워크는 제대로 작동한다. PBFT에서 상수 f는 전체 노드의 1/3로 정의할 수 있다. 네트워크가 제대로 작동하기 위해서는 1/3 이상이 부정직한 상태가 되면 안된다.

네트워크는 일련의 view를 따라서 이동한다. 주어진 노드가 처리해야 할 일련의 데이터의 범위다. Kafka를 이용해서 구성 할 경우 이 view는 offset으로 기술될 것이다.

위 그림을 보자. 이 네트워크는 4개의 노드로 구성되어있다. node 0 이 primary 노드이고 3은 결함(faulty) 노드다. 이 네트워크에서 3번 노드로는 어떠한 메시지도 전송하지 않을 것이다. 이 네트워크는 (4-1)/3 즉 하나의 결함노드를 허용한다.

Primary 노드는 현재 뷰를 확인해서 블럭을 만들고 네트워크에 게시한다. 각 노드들(Node 1, Node 2)은 이 블럭이 유효한지 확인하기 위한 검증을 수행한다.

이때 Primary 노드는 블럭을 브로드 캐스팅한다. Pre-prepare 메시지에는 4개의 핵심정보를 포함한다.

1. Primary 노드가 게시판 블럭의 ID
2. 블럭의 번호
3. Primary's의 view number
4. Primary 노드의 ID

노드는 primary 노드로부터 pre-preparing 메시지를 수신하면 메시지의 유효성을 검사하고 메시지를 내부로그에 추가한다. 메시지의 유효성 검사에는 메시지의 디지털 서명, 메시지의 view 번호가 노드의 현재 view 번호와 일치하는지 확인하며 현재 view가 primary로 부터 전송된게 맞는지를 확인하는 과정이 포함된다.

Pre-prepare 메시지는 primary node가 게시판 블럭을 공개적으로 승인(endorse)하고 네트워크가 해당 블록에 대해 합의 하는 방법으로 사용된다. 한 번에 하나의 블록만 검토 되도록하기 위해서 노드는 둘 이상의 pre-prepare 메시지를 허용하지 않는다.

노드가 블록과 블록에 대한 pre-preparing 메시지를 수신하고 모든 노드의 로그에 추가되면 노드는 preparing 단계로 넘어간다. Preparing 단계에서 노드들은 prepare 메시지를 네트워크의 다른 노드(자신을 포함) 브로드 캐스트한다.

다음 단계로 넘어가기 위해서는 노드는 동일한 블록 ID, 블록 번호, 및 view 번호를 가지며 다른 노드에서 온 2f+1 준비메시지를 수시 할 때까지 기다려야 한다. 위 예제의 경우 f= (4-1)/3 이므로 2개의 다른 노드로부터 메시지가 수신되야 한다. 2f+1 개의 prepare 메시지를 수신하면 노드는 이 단계에서 올바르게 작동하는 모든 노드가 일치하는지 확인 할 수 있다. 노드가 2f+1 개의 prepare 메시지를 승인하고 로그에 추가하면 commit 단계로 이동할 준비가 된다.

커밋 단계에서 노드 커밋 메시지를 모든 네트워크에(자신을 포함) 브로드캐스트한다. 다른 메시지 타입과 마찬가지로 커밋 메시지는 블럭 ID와 블럭 넘버, 노드의 view 넘버와 view ID번호를 가지고 있다. Preparing 단계에서와 마찬가지로 노드는 2f+1 개의 다른 노드로 부터 일치 커밋 메시지(matching commit message)를 받기 전까지 커밋 단계를 완료 할 수 없다. 다시 말해서 최소 2f+1 개의 노드로 부터 커밋 메시지가 수락되고 로그가 작성되면 노드는 안전하게 블럭을 커밋할 수 있게 된다.

Primary 노드가 커밋단계를 완료하면 pre-preparing메시지를 브로드캐스팅하고 전체 프로세스를 다시 시작한다.

BFT(Byzantine fault tolerant)를 유지하기 위해, 합의 알고리즘은 노드가 네트워크를 부적절하게 변경하거나 작업 진행이 무기한 중단되지 않도록 (항상 작동할 수 있도록)해야 한다. PBFT는 결함이없는 모든 노드가 Preparing 와 Committing 단계로 넘어가기 위한 합의를 이끌어낼 수 있도록 안정하게 유지해야 한다. 이를 위해서는 리더가 부적절한 행위를 하는 노드(잘못된 메시지를 생성하거나 아무것도 하지 않는)를 결정할 수 있는 매커니즘이 있어야 한다. PBFT는 뷰 변경을 이용해서 이 문제를 해결한다.

만약 primary view v가 실패한다면(primary가 잘못된 메시지를 보내거나 유효한 블럭을 제 시간안에 처리하지 못하는 경우) v + 1이 새로운 primary가 되고 view change message가 전체 네트워크에 브로드 캐스팅 된다. Primary 노드가 실제 결함이 있는 경우, 결함이 없는 모든 노드가 view change 메시지를 브로드캐스트한다. 새로운 view의 primary 노드(v+1)이 다른 노드로 부터 2f+1의 view change 메시지를 수신하면 view v+1에 대한 새로운 view 메시지를 모든 노드에 브로드캐스트한다. 다른 노드들이 새로운 view 메시지를 받으면 새로운 view 로 전환하고 새 primary 노드는 블럭을 게시하고 pre-prepare 메시지를 보내기 시작한다. 현재 네트워크에 결함이 있는 경우 네트워크가 새로운 primary 노드로 이동하기 때문에 노드 실패에도 계속 작업이 진행된다.

이 문서는 PBFT 합의 알고리즘의 기본적인 내용만 다룬다. Sawtooth PBFT의 자세한 내용을 담고 있는 문서를 소개하고 글을 마친다.

1. Original PBFT paper
2. Sawtooth PBFT RFC
3. Sawtooth PBFT source code

• Introduction to sawtooth PBFT