LFT – loopchain consensus algorithm

저번 포스팅에서는 블록체인을 위한 합의 알고리즘 중, 기존의 상태 머신 복제 프로토콜에서 활용하던 BFT(Byzantine Fault Tolerance)계열 합의 알고리즘에 대해 설명하였습니다. BFT 계열 합의 알고리즘은 머신의 개수나, 지분을 통하여 투표를 하여 합의하는 방식으로 에너지 낭비가 없고 즉각적인 합의가 가능하다는 장점이 있습니다.

블록체인 기술 연재 시리즈

블록체인 기술 개요
스마트 컨트랙트(Smart Contract) 개요 -1
스마트 컨트랙트(Smart Contract) 개요 -2
loopchain SCORE(Smart Contract On Reliable Environment
합의 알고리즘 개요
작업증명(PoW, Proof-of-work)과 지분증명(PoS, Proof-of-stake)
BFT 기반 합의 알고리즘

이번 포스팅에서는 loopchain에서 사용하는 합의 알고리즘인 LFT에 대해서 공개하겠습니다.  LFT는 Tendermint나 PBFT(Practical Byzantine Fault Tolerance)와 마찬가지로 BFT 계열 합의 알고리즘입니다. 기존의 상태 머신 복제 프로토콜중 하나인 Raft를 비잔틴 노드의 공격을 극복할 수 있도록 개선한 알고리즘 입니다.

LFT

LFT는 현재 loopchain에서 사용하는 합의 알고리즘입니다. 그러나 loopchain은 Pulgin형태로 합의 알고리즘이 구현되어있기 때문에 필요에 따라 PBFT와 같은 다른 합의 알고리즘을 사용할 수 있습니다. 추후에 loopchain은 github를 통해 오픈소스 프로젝트로 공개될 것이기 때문에 직접 다운로드 받고 실행 시킬 수 있습니다.

LFT는 기존 PBFT를 사용하는 합의 알고리즘에서 발생하는 통신 오버헤드를 Piggybacking을 이용하여(네트워크에서 메시지를 통합하여 통신 오버헤드를 감소시키는 방법) 줄였으며 Spinning (리더를 매번 교체하는 기법)기법을 이용하여 악의적인 노드가 네트워크의 합의를 해치지 않는 범위에서 네트워크에 문제를 일으킬수 있는 특정 노드의 트랜잭션 거부 문제,  리더에 의한 네트워크 지연과 같은 문제를 해결하였습니다. 또한  기존 알고리즘들이 가지고 있던 지나치게 복잡한 리더 선정 알고리즘을 단순화 하였습니다.

LFT Normal Process

위 그림은 LFT 알고리즘의 합의 과정에 대한 그림입니다. 네트워크가 시작되면 검증 노드(검증을 통해 합의에 참여하는 노드)들은 사전에 결정되어 있는 리더 노드에게 처리를 원하는 트랜잭션을 전송합니다. 리더 노드는 수집한 트랜잭션을 이용하여 블록을 생성하고 자신의 서명과 함께 다른 모든 검증 노드에게 전송합니다.

각 검증 노드들은 블록을 받으면 1) 현 리더가 블록을 생성했는지 확인하고, 2) 블록의 높이와 이전 블록 해시가 올바른지 확인 3) 블록의 데이터가 올바른지 확인합니다. 검증 노드는 1~3번이 옳다면 Vote 데이터를 생성하여 네트워크의 모든 노드들에게 전파합니다. Vote 데이터를 전체 노드에게 전파하는 것은 매우 중요한데 이는 리더 노드가 비잔틴일 경우 정족 수 이상의 노드들에게만 블록을 전파하여 특정 노드들을 네트워크로 부터 분리하도록 시도할 수 있기 때문입니다. 이러한 문제를 방지하기 위해 모든 피어에게 Vote 데이터를 전파하며 이는 기존 Raft 알고리즘과의 다른 점입니다. 이 과정에서 블록을 못받은 노드는 블록이 생성되었는지에 대한 정보를 알 수 있고 다른 노드에게 블록을 요청할 수 있습니다.

본 포스팅에서는 LFT의 동작 방식에 대해 간략하게 설명하였습니다. 기존 알고리즘과의 비교 및 장애 상황 극복 시나리오 등의 자세한 내용은 LFT 백서를 통해 확인할 수 있습니다.

 

BFT 기반 합의 알고리즘

저번 포스팅에서는 공개 블록체인(Public Blockchain)에서 주로 활용하는 합의 알고리즘인 작업증명 알고리즘(Proof-of-Work)과 지분증명 알고리즘(Proof-of-Stake)에 대해 알아보았습니다. 이러한 알고리즘들은 확률적 합의 알고리즘으로써 특수한 데이터(PoW : Nonce , PoS : 지분 및 화폐의 나이)를 통해 블록의 유효성과 우선순위를 정하고 별도의 통신 없이 모든 노드가 합의를 하는 알고리즘이었습니다.

블록체인 기술 연재 시리즈

블록체인 기술 개요
스마트 컨트랙트(Smart Contract) 개요 -1
스마트 컨트랙트(Smart Contract) 개요 -2
loopchain SCORE(Smart Contract On Reliable Environment
합의 알고리즘 개요
작업증명(PoW, Proof-of-work)과 지분증명(PoS, Proof-of-stake)

이번 포스팅에서는 기존 확률적 합의 알고리즘의 문제점을 개선하고자 기존 분산시스템에서 상태 기계 복제(State Machine Replication)를 위해 활용한 BFT (Byzantine Fault Tolerance) 합의 알고리즘 방식을 활용한 블록체인 합의 알고리즘을 소개하도록 하겠습니다.

기존 합의 알고리즘의 문제

이전 포스팅에서 설명한 작업증명 알고리즘과 지분증명 알고리즘이 적용된 블록체인이 작동하기 위해서는 내부 가상 화폐 등의 보상 시스템이 꼭 필요합니다. 블록체인의 노드들이 작업증명 알고리즘에서 사용하는 에너지 낭비 방식의 채굴을 수행하는 이유는 블록체인 네트워크에서 주는 가상 화폐 보상을 얻기 위해서 입니다. 지분 증명 또한 마찬가지고 내부 화폐 및 보상이 없으면 블록을 생성할 이유도 없고 지분 증명 메커니즘 자체를 사용할 수 없게 됩니다.  때문에 가상 화폐 외의 다른 많은 서비스를 수행하는 사설 블록체인의 경우 이러한 내부화폐가 필요한 합의 알고리즘을 사용할 수 없습니다.

기존 알고리즘은 가상화폐가 필요하다는 문제 외에도 부분 분기가 일어날 수 있다는 문제가 있습니다.  간단하게 작업증명 알고리즘을 예로 들면 A와 B블록이 거의 동시에 생성될 경우 각 노드는 자신의 선택에 따라 A와 B블록 중 하나를 선택합니다. 이후 블록들이 확정되어야지만 이전 블록들이 확실하게 합의를 이루게 됩니다. 이러한 문제는 즉각적인 거래 확정을 요구하는 서비스에서는 적용이 어려운 문제점이 있습니다.

PBFT(Practical Byzantine Fault Tolerance) 

PBFT는 분산시스템이 약속된 행동을 하지 않는 비잔틴 노드가 존재할 수 있는 비동기 시스템일 때 해당 분산시스템에 참여한 모든 노드가 성공적으로 합의를 이룰 수 있도록 개발된 합의 알고리즘입니다(비잔틴 노드, 합의 알고리즘등의 용어가 이해 안가면 이전 포스팅에서 알아 보실 수 있습니다).  PBFT는 기존의 BFT 합의 알고리즘이 동기식 네트워크에서만 합의가 가능했던 문제를 해결하여 비잔틴 노드가 있는 비동기 네트워크에서 합의를 이룰 수 있게 하였습니다.

PBFT 알고리즘 동작 방식(출처)

위의 그림은 PBFT 알고리즘이 동작하는 방식을 나타낸 것입니다. 이러한 기존 분산 시스템에서 사용하던 합의 알고리즘은 Primary 혹은 Leader라 불리는 특별한 노드가 존재합니다. 이 노드는 클라이언트의 요청 순서를 정렬하고, 요청에 대한 결과를 기입하요 다른 노드들에게 뿌려주는 역할을 합니다.

합의는 다음과 같이 수행합니다. 1) 리더가 클라이언트들의 요청을 수집하여 정렬하고 실행 결과와 함께 다른 노드들에 전파합니다. 2) 리더의 메시지를 받은 노드들은 다른 노드들에서 받은 메시지를 다시 한번 나머지 노드들에게 전파합니다. 3) 모든 노드는 자신이 다른 노드에서 가장 많이 받은 같은 메시지(정족수 이상의)가 무엇인지 다른 노드들에게 전파합니다. 1) 2) 3)의 과정이 끝나면 모든 노드들은 정족수 이상이 동의한, 즉 합의를 이룬 같은 데이터를 가지게 됩니다.

PBFT는 두번의 브로드캐스트 과정을 이용해 비잔틴 리더나 비잔틴 검증 노드가 네트워크 분기를 위해 이상한, 혹은 임의의 메시지를 보내도 네트워크의 모든 노드는 같은 메시지를 가질 수 있게 하였습니다. 이러한 PBFT 알고리즘은 IBM Fabric 0.6v이나 1.0v의 Orderer서비스, R3 Corda의 Notary와 같은 프라이빗 블록체인에서 사용하고 있습니다.

Tendermint (DPoS + PBFT) 

Tendermint는 Cosmos에서 사용하는 합의 알고리즘으로 PBFT 알고리즘을 공개 및 비공개 블록체인에 맞도록 개량한 합의 알고리즘 입니다. Tendermint는 전통적인 합의 알고리즘이 블록체인에 적용된 의미있는 사례이며 DPoS(Delegated Proof-of-Stake) 개념과 PBFT 개념을 섞어 공개 및 비공개 블록체인에서 사용할 수 있도록 한 합의 알고리즘입니다.

Tendermint
Tendermint 합의 과정(출처 : https://tendermint.com/intro/consensus-overview)

Tendermint의 전체 합의 프로세스는 PBFT와 거의 유사합니다. Tendermint 프로세스에서의 Propose는 PBFT의 Pre-Prepare, Prevote는 Prepare, Precommit은 PBFT의 Commit으로 매칭시키면 이해가 쉽습니다.

Tendermint는 앞에서 언급하였듯이 PBFT에 DPoS개념을 추가하여 블록체인에 적합한 합의 알고리즘을 개발하였습니다. 차이점을 간단히 요약하면 기존의 PBFT는 하나의 노드가 하나의 투표를 하는 방식으로 투표를 받아 가장 많은 투표를 받은 블록을 승인하지만 Tendermint는 지분(Stake)을 기반으로 투표를 합니다. 투표하는 노드의 수 보다는 지분이 중요하죠.

Tendermint는 투표를 할때 Locking 메커니즘을 통해 투표에 참여한 지분을 네트워크에 동결시키고 이를 해제하는 메커니즘을 통해 이중 투표 문제를 막고 지분으로 네트워크를 유지하게 합니다.  또한 이중 투표 시도와 같은 블록체인을 공격하려는 악의적인 행위를 하면 지분을 빼앗는 방법으로 기존의 블록체인이 네트워크 공격 노드에 아무런 처벌을 하지 않던 문제(Nothing of Stake) 문제를 해결하였습니다.

이번 포스팅에서는 전통적인 BFT 알고리즘인 PBFT와 블록체인 합의 알고리즘인 Tendermint에 대해 알아보았습니다. 이러한 합의 메커니즘은 공개 블록체인 뿐 아니라 사설 블록체인에서 활발하게 연구되고 있는 알고리즘들 입니다. 다음 포스팅에서는 loopchain에서 사용하는 합의 알고리즘인 LFT에 대해 간략하게 소개하고 백서를 공개하도록 하겠습니다.

작업증명(PoW, Proof-of-work)과 지분증명(PoS, Proof-of-stake)

저번 포스팅에서는 컴퓨터 공학(Computer Engineering) 관점에서 합의 문제와 비잔틴 장군 문제에 대해 알아보았습니다. 이전 포스트는 앞으로 다룰 합의 알고리즘 개요에 대해서 설명했다고 볼 수 있습니다.

블록체인 기술 연재 시리즈
블록체인 기술 개요
스마트 컨트랙트(Smart Contract) 개요 -1
스마트 컨트랙트(Smart Contract) 개요 -2
loopchain SCORE(Smart Contract On Reliable Environment
합의 알고리즘 개요

이번 포스팅에서는 최초의 블록체인 어플리케이션인 비트코인에서 사용한 합의 알고리즘인 작업증명(Proof-of-Work)과 최근 공개 블록체인에서 많이 도입하고 있는 합의 알고리즘인 지분 증명(Proof-of-Stake)에 대해 알아보도록 하겠습니다.

작업증명(Proof-of-Work) 알고리즘

작업증명 알고리즘은 비트코인의 창시자인 나카모토 사토시(Satoshi Nakamoto)가 비트코인에 대한 이야기를 담은 논문 Bitcoin: A Peer-to-Peer Electronic Cash System에서 처음으로 제안한 비잔틴 합의 알고리즘입니다.

스크린샷 2017-06-01 오전 11.05.03.png
비트코인 블록 구조(출처 : mastering bitcoin)

블록체인 기술 개요 포스팅을 보신 분들은 아시겠지만 블록 데이터 해시 연결을 위해 블록에는 블록 헤더 데이터를 해시 함수로 계산한 블록 해시가 들어가고 이를 통해 해시 연결성을 검증해 블록체인 데이터가 중간에 위변조가 되지 않았음을 확인합니다.

작업증명 알고리즘을 사용하는 블록체인의 블록 해시는 Difficulty에 따라 선택된  Target 데이터 규격을 만족해야 합니다. 블록해시는 해시 알고리즘에 의해 만들어지기 때문에 Target데이터를 가지고 입력값을 알아낼 수가 없습니다. 즉, 블록체인의 노드는 조건을 만족하기 위해 Nonce라는 임의의 값을 계속 대입합니다. 임의로 대입한 Nonce값이 Target 데이터 조건을 만족하면 블록이 생성되는 것이죠.

이러한 작업증명 알고리즘이 무슨 소용일까 싶을 수 있습니다. 이러한 작업증명 알고리즘의 필요성은 네트워크의 모든 노드가 동시에 블록을 만들 수 없게 하는 것 입니다. 작업증명을 통과해야만 블록을 생성할 수 있고, 이를 위해서는 엄청난 에너지가 소모됩니다. 그리고 작업증명 알고리즘은 Difiiculty 조절 알고리즘을 이용하여 10분당 1~2개의 블록이 생성된다는 것을 보장합니다.

이 슬라이드 쇼에는 JavaScript가 필요합니다.

다음 블록 생성자에 의해 블록 분기가 합쳐지는 상황 (출처 : Mastering Bitcoin)

네트워크의 노드들은 다음 블록을 생성하기 위해 A와 B 중 하나의 블록을 선택하여 블록을 생성합니다. 다음 블록을 생성하는 노드는 A와 B중 하나의 블록에 연결한 블록을 생성합니다. 또다시 A를 선택한 노드와 B를 선택한 노드가 동시에 블록을 생성할 확률은 굉장히 낮겠죠. 나카모토 사토시는 확률 증명을 통해 블록 6개가 대립되는 블록이 계속 생성될 확률은 0에 가깝다는 것을 보였습니다.

작업증명 합의 알고리즘은 일시적으로 합의가 깨질 수 있으나 확률적으로 마지막엔 하나의 블록체인을 합의하게 되는 합의의 알고리즘 입니다. 작업증명 알고리즘은 기존 합의 알고리즘이 적은 수의 노드와 대다수는 올바른 행동을 한다는 가정(보통 3f+1 이상이 올바른 일을 해야 정상 운영, f는 잘못된 노드의 수)을 통해 작동하는 알고리즘인 것과 달리 글로벌한 규모의 완전히 오픈된 네트워크에서 운영할 수 있는 알고리즘 입니다.

그러나 작업증명 알고리즘은 느린 속도와, 낭비되는 에너지 문제가 심각합니다. 지금 비트코인 한 블럭을 생성하기 위해서는 위해선 5,000,000 TH/s(1 TH/s = 초당1,000,000,000,000번의 해시연산) 이상의 해시 파워가 필요합니다.

지분증명(Proof-of-Stake) 알고리즘

지분증명 알고리즘인 PeerCoin이라는 가상화폐에서 처음으로 발표한 합의 알고리즘입니다.  기존 작업증명 알고리즘의 에너지 낭비 문제와 Nothing at stake 문제를 해결하기 위해 만들어졌죠.

지분증명은 컴퓨팅 파워 낭비가 아닌 자신이 가진 돈 (stake)을 통해 블록을 생성합니다. 자신이 가지고 있는 지분(Stake)과 지분이 생성된 날짜에 의해 결정됩니다. 한번 블록 생성을 위해 사용된 지분의 날짜는 초기화되죠.

만약 A가 50번째 블록을 만들었는데 알고리즘에 의해 계산된 가중치가 60이고 B가 50번째 블록을 동시에 만들고 알고리즘에 의해 계산된 가중치가 80이라면 네트워크의 노드들은 가중치가 더 높은 B의 블록을 선택합니다. 이를 통해 블록이 동시에 많이 생성되어도 많은 노드에 의해 특정 블록이 선택되는 합의 알고리즘을 만들었습니다.

현재 지분증명 알고리즘은 PeerCoin에서 제안한 방식뿐 아니라 지분을 사용하는 모든 종류의 합의 알고리즘을 지칭합니다. Stake로 영향력을 나타내는 것을 동일하지만 내부 동작 방법은 알고리즘에 따라 굉장히 상이합니다. 예를 들면 Tendermint의 경우 전통적인 비잔틴 합의 알고리즘인 PBFT(Practical Byzantine Fault Tolerance)에 지분 개념을 추가한 합의 알고리즘을 만들었습니다.

이번 포스팅에서는 공개 블록체인에서 많이 채택하는 알고리즘인 작업증명 알고리즘과 지분증명 알고리즘에 대해 설명하였습니다. 이러한 합의 알고리즘을 확률적 합의 알고리즘이라고 합니다. 네트워크 통신 없이 특정 노드에서 생성한 특수한 데이터를 통해 합의 하는 방식이죠. 공개블록체인 뿐 아니라 인텔이 만들고 있는 프라이빗 블록체인 플랫폼인 Sawtooth LAKE의 경우 인텔 CPU에서만 생성할 수 있는 데이터를 가지고 합의하는 확률적 알고리즘인 PoET 합의 알고리즘을 사용합니다.

다음 포스팅에서는 최근 프라이빗 블록체인에서 많이 사용하는 PBFT 등의 전통적 방식의 합의알고리즘을 기반으로한 합의 알고리즘에 대해 알아보도록 하겠습니다.

합의 알고리즘 개요

이전 포스팅에서는 loopchain의 스마트 컨트랙트인 SCORE(Smart Contract On Reliable Environments)에 대해서 알아보았습니다.

블록체인 기술 연재 시리즈
블록체인 기술 개요
스마트 컨트랙트(Smart Contract) 개요 -1
스마트 컨트랙트(Smart Contract) 개요 -2
loopchain SCORE(Smart Contract On Reliable Environment)

이전 포스팅 들에서 설명한 스마트 컨트랙트(Smart Contract)의 경우 라이트닝 네트워크(Lighting Network)와 함께 블록체인을 응용한 서비스를 하는데 꼭 필요한  대표적인 기술입니다.  이번 포스팅에서는 블록체인을 지탱하는 핵심 기술분산합의 알고리즘에 대해 알아보도록 하겠습니다.

합의 문제(Consensus Problem) 

블록체인은 기본적으로 분산 시스템입니다. 합의 문제는 분산 시스템의 신뢰도를 보장하기 위해 나온 개념으로 블록체인이 나오기 전부터 존재하던 개념입니다. 이를 한 줄로 요약한다면 모든 분산 시스템에 참여하고 있는 모든 프로세스가 같은 결과 값을 결정해야 한다는 것입니다.  이것이 왜 필요할까요?

분산 컴퓨팅으로 이루어진 비행기 예매 시스템에 합의 알고리즘이 없다고 가정해봅시다. 손님 A와 손님 B가 같은 자리a를 동시에 예매 하였을 때 합의 알고리즘이 없다면 들어온 시스템에 따라 자리 a를 예매한 사람이 달라집니다. 이런 시스템 오류와 무결성을 보장하기 위하여 합의 문제를 해결하는 합의 알고리즘이 생겨났습니다.

스크린샷 2017-05-23 오전 8.56.04
합의 알고리즘이 없는 비행기 예매 시스템

합의 문제를 해결하는 합의 알고리즘은 3가지 조건을 만족해야 합니다.

  • 모든 Process가 같은 값을 결정
  • 결정된 데이터는 특정 Process에 의해 제안된 것이어야 함
  • 모든 시스템의 상태는 0이나 1로 결정 되어야 함(모두 1인지 0인지 판단 할 수 있어야 함)

대표적인 합의 알고리즘으로는 Paxos와 Raft가 있습니다. 블록체인에서도 합의 문제는 매우 중요합니다. 전재산 1000원을 가지고 있는 A가 1000원을 B에게 송금하는 메세지를 보내면서 C에게 송금한다는 메세지를 동시에 보냈을때 블록체인 시스템에서 합의를 하지 못하면 큰 문제가 생길 수 있습니다.

비잔틴 장군 문제(Byzantine General Problem)

블록체인은 합의 문제 말고도 비잔틴 장군 문제라는 분산 네트워크 문제를 해결하는 시스템입니다. 비잔틴 장군 문제는 분산 컴퓨팅의 아버지 레슬리 램포트(L. LAMPORT)가 논문을 통해 처음 으로 악의적인 노드가 분산 시스템에 참여한 상황을 모델링한 문제입니다. 비잔틴 장군 문제를 해결한 시스템은 악의적인 노드가 분산 시스템에 참여한 상황에서도 전체 시스템은 신뢰도 있는 서비스를 제공할 수 있다는 것을 보장합니다.

비잔틴 장군 문제

  • 흩어져 있는 비잔틴의 장군들이 성을 공격하려 합니다. 모든 장군들이 같이 공격을 한다면 이길 수 있는 상황
  • 장군들은 흩어져 있기 때문에 같은 시간에 공격하기 위해 메세지를 공유
  • 하지만 비잔틴 장군 들 중 첩자가 있어 중간에 메세지를 교체할 수 있음
  • 이때 모든 장군들이 같은 시간에 공격을 할 방법은?
0--xCD-El4LZ48dji1.png
비잔틴 장군 문제(출처 : https://goo.gl/OKSivi)

문제에서는 장군들로 표현하였지만 네트워크에 있는 악의적인 노드와 오작동 하는 노드를 첩자라고 생각하면 됩니다. 비잔틴 장군 문제를 해결하는 분산 시스템은 특정 노드가 해킹이나 오작동이 발생해 문제가 생겨도 네트워크는 여전히 신뢰도 있는 서비스를 제공할 수 있습니다. 대표적인 비잔틴 장애 허용(Byzantine Fault Tolerance)알고리즘으론 PBFT(Practical Byzantine Fault Tolerance)가 있습니다.

블록체인의 경우 하나의 주체가 네트워크를 구성하는 것이 아닌 신뢰관계가 아닌 노드들이 모여서 네트워크를 구성합니다. 또한 각각의 노드들은 네트워크 조작을 통해 부당한 이득을 취하는 게 가능합니다. 따라서 블록체인 시스템은 비잔틴 장군 문제를 해결해야만 합니다. 비잔틴 장군 문제를 해결함으로써 네트워크에 악의적인 노드가 존재하더라도 신뢰도 있는 시스템을 제공하는 것을 보장할 수 있습니다.

오늘 포스트에서는 합의 문제와 비잔틴 장군문제가 무엇인지에 대해 알아보았습니다. 다음 포스트에서는 공개 블록체인에서 위의 문제를 해결하기 위해 사용하는 대표적인 알고리즘인 작업증명(Proof of Work)과 지분증명(Proof of Stake)에 대해 알아보겠습니다.