Introduction

네트워크로 연결된 분산 환경에서 동일한 데이터를 동일한 순서로 적용하기 위한 알고리즘을 합의 알고리즘이라고 부른다. 블록체인에서는 블록이 합의의 대상이 되는 데이터가 될 것이다. 블록체인 합의 알고리즘은 여러 노드가 블록을 생산하거나, 생산된 블록을 전달받은 후 블록체인을 확장시켜 나아갈 때 오직 하나의 체인(블록의 리스트)을 유지하기 위한 역할을 한다.

AERGO는 Enterprise를 위해 최적화된 버전을 release 하면서 향상된 성능과 사용성을 가진 합의 알고리즘으로 Raft를 지원하게 되어 이를 소개하고자 한다.

Enterprise 환경은 AERGO mainnet이 운영되는 Public network 환경과는 다른 성격을 가진다. 가장 큰 차이점은 기업들이 운영하는 블록체인은 보안이 확보된 Private network 환경에서 운영된다는 점이다. 이러한 환경에서는 Public network 환경처럼 악의적이거나 권한 없는 노드들이 임의로 블록을 생성하는 상황을 방지하기 위한, 복잡하고 무거운 합의 알고리즘을 사용할 필요성이 줄어든다.

Bitcoin 혹은 Ethereum의 POW(Proof of work)는 서버에 많은 부하를 준다는 단점이 존재한다. 이런 문제를 개선하기 위해 사용되는 EOS나 AERGO의 DPoS는 가볍고 빠르다. 하지만 생성된 블록의 즉각적인 Finality를 보장하지 못한다. Tendermint와 같은 BFT 계열의 합의 알고리즘을 사용하는 경우 블록의 즉각적인 Finality은 보장하지만 불필요하게 복잡하다.

Raft는 Private network 환경이라는 특성에 적합하도록 Byzantine Fault Tolerance를 포기한 대신 Chain에 추가되는 즉시 Finality가 보장되고, fork가 발생하지 않는다는 장점을 취했다.

이제 AERGO에서 Raft 합의가 어떻게 동작하는지 더 자세히 살펴보자.

RAFT 특징

노드 간의 가장 널리 사용되는 합의 알고리즘으로 Paxos가 존재한다. 하지만 Paxos 알고리즘은 높은 복잡도로 이해가 어렵고, 이로 인해 안정성이 검증되고 널리 사용되는 구현체도 제대로 존재하지 않는다. 따라서 Paxos와 동일한 안정성을 가지면서도 이해하기 쉽고, 구현하고 관리하기 쉬운 합의 알고리즘을 개발하고자 하는 목적으로 Raft 합의 알고리즘이 개발되었다.

Raft는 스탠포드 대학의 Diego Ongaro와 John Ousterhout에 의해 최초로 제안되었고 위의 장점들로 ETCD를 비롯한 많은 프로젝트에서 분산 환경에서의 노드 간 합의 알고리즘으로 채택하여 사용 중이다.

AERGO는 여러 Raft 구현체 중 ETCD 프로젝트에서 개발된 raft library를 사용하여 개발되었다.

이제 Raft가 어떤 장점을 가지고 있는지 살펴보자.

첫째, Raft는 CFT(crash fault tolerance)를 보장한다. 클러스트의 전체 노드 중 과반수 (n/2) 노드에 장애가 발생하기 전까지 클러스터는 정상적으로 동작함을 보장한다. 다만 Raft는 모든 노드가 정직하다는 가정하에 동작한다. 즉 Byzantine Fault Tolerant 하지 않다. 따라서 Raft는 private한 네트워크 환경에 적합한 합의 알고리즘이라고 할 수 있다.

둘째, Raft가 BFT계열의 합의 알고리즘과 다른 가장 큰 특징은 블록이 블록체인에 추가되는 즉시 Finality를 가진다는 점이다. 따라서 체인에 fork가 발생하지 않고 이로 인한 체인의 reorganization이 발생하지 않는다. 합의가 된 블록이 블록체인에 추가되는 순간 해당 높이에는 절대 다른 블록이 추가되지 않음을 보장한다. 또한 참여한 모든 노드가 동일한 높이에 동일한 블록을 추가함을 보장한다.

셋째, Simple하다. Protocol이 복잡하지 않고, 블록은 서버에 장애가 발생하지 않는 한 동일 서버에서 계속해서 생성된다. 블록을 생성한 노드에 장애가 발생하면 투표 과정을 거쳐 선정된 새로운 노드가 블록 생성을 담당하게 된다. 이러한 특성으로 여러 노드가 블록을 돌아가면서 생성하는 DPoS나 복잡한 합의 과정을 가지는 BFT계열의 합의 알고리즘보다 더 개선된 성능을 보일 수 있다.

RAFT Protocol

Raft 상에서 여러 서버 노드들은 network로 연결되어 클러스터를 이루고 각각 다음 3가지 상태 중 하나의 상태를 가지게 된다.

1. Leader
-블록을 생성하고 이를 클러스터전체에 전파하는 역할을 한다. 또한 합의 과정을 거치고 난 후 블록을 블록체인에 최종적으로 추가하는 일을 한다.

2. Follower
-Leader가 전달한 블록을 저장한 후 응답을 한다. 이 응답을 통해 Leader는 과반수 이상의 클러스터 노드들에게 블록 전달이 성공하였는지 판단 할 수 있다.

3. Candidate
-Follower 상태인 노드가 Leader 노드와 연결이 일정 시간 이상 끊기면 Candidate 상태가 된다. Candidate 노드는 투표 요청 메시지(Vote request)를 다른 노드에 보내서 과반수 이상의 노드들로부터 투표를 받게 되면 새로운 리더가 된다.

Fig 1. Raft 합의에서의 node 상태 전환

AERGO의 모든 노드는 Follower 상태에서 시작한다. 이 노드들 중에서 Raft 합의의 Leader 선출 과정을 거쳐 Leader를 새롭게 선정하게 된다. 오직 Leader 로 선출된 노드만이 블록을 생성할 수 있다. Leader 노드는 Leader 자격을 상실할 때까지 계속해서 블록을 생성하고, 생성한 블록을 Raft protocol을 통해 Follower 노드들에게 전파한다. 이를 통해 전체 클러스터는 동일한 블록체인을 유지해 나갈 수 있게 된다.

Raft protocol을 이용한 블록 생성 과정

이제 전체 노드들이 Raft protocol을 이용해서 블록을 생성하고, 이를 각자의 저장소에 저장하는 과정을 살펴보도록 하자. 전체 블록체인에 블록을 추가하는 과정은 크게 Propose, Commit, Apply 3단계로 이루어진다.

Fig2. Leader 노드에서 블록 생성 과정

1. Propose
– Leader 노드가 블록을 생성하고 블록에 포함된 Transaction들을 실행한 후 Follower 노드들에게 전파한다.

2. Commit
– Follower 노드는 Leader 노드가 전파한 블록을 받아서 저장소에 저장(단 실행은 Apply 단계에서 이루어진다)한 후 성공 응답을 보낸다. Leader 노드는 Follower 노드들로 부터 받은 응답이 전체 클러스터 노드의 과반수(N/2)가 될 때까지 기다린 후 Commit 성공한 것으로 판단한다. 이를 보장하는 것은 Leader 선출 알고리즘을 통해 이루어 진다. 새로운 Leader는 반드시 마지막 Commit을 포함한 노드들 중에서 선출된다. 새 리더는 추가되지 않은 모든 Commit된 블록을 블록체인에 추가하고 난 후, 다음 높이의 블록을 생성함으로써 Commit 된 블록이 반드시 블록체인에 포함됨을 보장하게 된다.

블록이 Commit 상태라는 의미는 무엇인가?
블록이 Commit 상태가 되면 이 상태로 클러스터의 전체 노드들이 중지되었다가 재실행 되더라도 이 블록이 절대로 유실되지 않는 상태라는 것을 의미한다.

3. Apply
– Leader는 Commit된 블록을 블록체인의 Top 블록으로 추가한다. Commit 정보는 Heartbeat 메시지를 통해 Leader로부터 Follower 노드들에게 주기적으로 전달된다. Follower 노드는 새로운 Commit 정보가 오면 저장해둔 블록을 실행하고 각자의 블록체인에 추가한다.

Leader 선출

Raft에서는 리더만이 블록을 생성하며 특정 시점에 오직 하나의 리더만이 존재함을 보장한다. 이렇게 함으로써 추가되는 모든 블록은 즉각적으로 Finality를 갖는다. 따라서 Leader 선출 과정은 Raft의 가장 핵심이라고 할 수 있다.
– Leader 선출 과정은 아래와 같다.
– Follower 노드가 현재 Leader 노드 혹은 네트워크 장애로 heartbeat 메시지를 받지 못하게 된다
– Follower 노드가 Candidate 노드가 된다.
– Candidate 노드는 다른 노드들에게 투표 요청 메시지를 보낸다. 이때 자신의 진행 상태를 함께 보낸다.
– 투표 요청을 받은 노드는 Candidate의 상태가 자신의 상태와 같거나 자신의 상태보다 더 최신 상태 일 때만 찬성 응답을 보낸다.
– Candidate는 일정 시간 동안 과반수(n/2)로부터 찬성 응답을 받으면 Leader가 된다.

투표의 핵심은 다음 두 가지 이다.
– 한 순간에 Leader는 반드시 하나이다.
– 새로운 Leader는 이전 Leader의 마지막 Commit을 반드시 포함한다.

이 목표를 달성하기 위해 다음과 같은 제약 사항을 가진다. Follower 노드는 동시에 두 노드에 투표할 수 없다. 또한 자신의 노드에 저장된 Raft 진행 상태보다 더 과거 상태를 가진 노드에는 찬성표를 행사할 수 없다.
Raft 알고리즘은 위의 두가지 핵심 사항을 준수함으로써 투표로 Leader가 바뀌더라도 fork를 발생시키지 않고 블록체인을 확장시켜 나갈수 있음을 보장한다.

Membership 변경

AERGO는 raft 합의를 통해 동적인 노드의 추가/삭제를 지원한다. 이는 서비스를 멈추지 않고 클러스터를 유지보수 하기 위한 중요한 특징이다. 노드의 추가/삭제는 블록체인에 포함되는 시스템 트랜잭션을 이용해 수행된다.

Raft 멤버십 변경 요청은 Raft Log로 생성되어 Block을 추가하는 과정과 유사하게 Propose/Commit/Apply 과정을 거쳐 수행된다. 대략적인 과정을 살펴보자.

1. Propose 단계
– Leader 노드에서 멤버십 변경 transaction이 포함된 블록을 실행하면 Raft 멤버십 변경 요청이 생성된다. 생성된 요청은 Leader로부터 Follower 노드들에게 전달된다.

2. Commit 단계
– Follower 노드들로부터 과반수 응답을 받으면 멤버십 변경 요청이 Commit상태가 된다.

3. Apply 단계
– Commit된 멤버십 변경을 노드에 반영한다. 노드 추가라면 변경이 반영된 것을 확인한 이후에 새로운 노드를 시작해야 한다. 이 과정에서 핵심 포인트는 멤버십 변경 요청과 블록 추가 요청을 같은 process를 거쳐 처리한다는 점이다. 이와 같이 일관된 로직으로 동적 멤버 변경을 처리한다는 개념은 단순하면서 직관적인 Raft의 장점을 잘 보여준다.

Summary

AERGO의 Raft 합의 알고리즘은 다음과 같은 특성을 갖는다.
– crash fault tolerance 보장
– 블록의 즉각적인 finality 보장
– 동적인 멤버십 변경의 자유로움

이러한 Raft 합의의 특성은 블록의 finality가 무엇보다 중요시되며, 네트워크의 강력한 보안이 보장되어 있는 엔터프라이즈 환경에 특히 적합한 알고리즘이라고 볼 수 있다.
새롭게 적용된 Raft 합의를 적용하여 기존 DPOS 비해 더욱 향상된 성능과 사용성을 경험 할 수 있을 것이다.

—

합의의 개념을 파악하는 데 도움이 되는 글: Understanding Blockchain Fundamentals, Part 1: Byzantine Fault Tolerance
Raft에 관한 논문과 추가자료는 Raft github 을 참고한다
Raft에 대한 자세한 내용은 Diego Ongaro 와John Ousterhout의 슬라이드를 참고하자