https://blog.acolyer.org/2018/02/12/sok-consensus-in-the-age-of-blockchains/

비트코인을 시작으로 이더리움, 리플, EOS 등 여러 블록체인 플랫폼들이 등장함에 따라 기존 합의 알고리즘의 단점을 보완한 다양한 형태의 합의 알고리즘이 함께 등장하고 있다. 합의 알고리즘은 블록체인의 거래처리 성능, 소요 에너지, 보안, 개방성 등에 직간접적으로 영향을 미치는 만큼 해당 사업이 어느 가치에 중점을 두는지에 따라 합의 알고리즘의 형태도 다르다. 즉, 이제는 단순히 블록체인 백서를 읽는 것을 넘어 해당 프로젝트가 어떤 합의 알고리즘을 사용하는지에 유의할 필요가 있다.

따라서 본 글에서는 블록체인의 핵심 기반인 합의 알고리즘의 개요와 발전 과정에 따른 대표적인 몇가지 합의 종류를 소개해보고자 한다.

Contents Contributor : 최범규 PD, 김서진 PD

1. 합의 알고리즘 개요

블록체인은 데이터베이스의 상태를 유지하기 위해 중앙 관리시스템 없이 신뢰관계가 아닌 개인간에 전체 데이터베이스를 공유하는 분산장부시스템이다. 즉, 블록체인은 트랜잭션 정보를 기록한 일종의 분산 장부로서 각 노드가 자신의 장부를 가지고 있기 때문에, 각 장부의 내용은 동일하게 유지되어야 하는 문제가 있다.

합의 문제(Consensus Problem)

디지털 상에서는 디지털 복사로 인해 원본과 복사본을 구별하지 못하는, 즉 ‘이중 지불 문제’가 발생한다. 예를 들어, 전 재산이 1달러인 A가 1달러를 B에게 송금한다는 트랜잭션을 주변 노드에게 보내면서 C에게 1달러를 송금한다는 트랜잭션을 동시에 보낼 경우 블록체인 시스템에서 어느 것이 유효한 거래인지 합의를 하지 못하면 같은 가치가 이중 지불되는 문제가 발생한다. 기존에는 이러한 이중 지불 문제를 해결하기 위해 은행과 같은 신뢰 있는 제 3자에게 데이터 관리 권한이 위임되었으나, 이 역시 중개 수수료, 거래 지연, 단일 장애 지점(Single Point Of Failure)* 존재 등의 ‘3자 문제’가 존재한다.
반면, 블록체인은 ‘합의 알고리즘’을 통해 P2P네트워크 상에서도 제 3자/중앙 통제 시스템 없이 데이터베이스의 오류와 무결성을 보장한다. 즉, P2P네트워크 상의 다수의 피어(노드)들이 합의를 통해 하나의 DB(블록체인)을 유지하는 것이다. 이때의 합의 알고리즘은 노드가 새 트랜잭션 데이터와 블록을 어떻게 처리할 지를 통제하는 명령어이다.

2. 합의 알고리즘(Consensus Algorithm)

합의 알고리즘은 블록체인 상의 여러 합의 과정에 영향을 끼친다. 이 중 가장 대표적인 것이 1) 블록생성 권한 분배 방법과 2) 포크(fork, 분기) 발생시 하나의 체인을 선택하는 방법 이다.

1) 블록생성 권한 분배

비허가형(permissionless) 블록체인과 같은 경우, 각 노드는 특별한 자격제한 없이 블록을 만들 수 있다. 따라서 각 노드에서 블록을 아무런 노력 없이 쉽게 만들 수 있게 된다면 동시에 수많은 블록이 만들어질 수 있으며, 이는 각 노드가 하나의 블록체인에 합의하는 것을 거의 불가능하게 만들 수 있다. 따라서 블록체인에서는 합의 알고리즘에 따라 즉시 거래 처리를 하는 것이 아닌 각 노드가 일정시간 동안 거래를 모아서 처리하게 하며, 특정 조건을 맞춘 채굴자를 선정하여 블록을 생성하게 한다. 이때, 각 합의 알고리즘이 요구하는 채굴자의 특정 조건은 계산 능력, 토큰 보유 량 등 다양한 합의 조건이 나올 수 있다.

예) 작업증명(Proof of Work, POW)같은 경우에는 계산능력에 따라 채굴확률이 결정된다. 예를 들어, A의 계산능력이 1이고, B가 2이면, 이들의 채굴확률은 1:2로 결정되어, A가 1개 채굴할 때 B는 2개를 채굴할 수 있다는 것을 의미한다.

2) 포크(fork; 분기) 발생시 하나의 체인 선택

https://steemit.com/kr/@loum/3

http://homoefficio.github.io/2017/11/19/%EB%B8%94%EB%A1%9D%EC%B2%B4%EC%9D%B8-%ED%95%9C-%EB%B2%88%EC%97%90-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0/

노드 간 떨어져 있는 거리와 전송속도에 따라 특정 시점에서 노드 마다 블록체인이 다르게 구성될 수 있다. 예를 들어 A국가에 있던 노드에는 파랑블록 다음에 빨강블록이 자식으로 연결되어 있는 상태*(자식으로 연결되었다는 의미는 바로 앞 블록의 블록해쉬를 포함하고 있음을 의미)였는데, 초록블록이 뒤늦게 전달되어 파랑블록 다음에 자식으로 연결됨으로써 포크(fork)가 발생한다. 이렇듯 한 부모에 대해 자식 블록이 여러 개가 생기는 상황을 포크(fork)라고 하며, 포크가 된 상황은 각 노드가 소유하고 있는 분산장부 간에 일치되지 않는 상태를 유발하게 된다.

따라서 이러한 불일치 문제를 해결하기 위해 각 블록체인은 블록체인 별로 합의 규칙을 정하여 모든 노드가 파란블록에 대해 빨강블록이 자식이 될지, 초록블록이 자식이 될지 동일하게 결정한다. 이것을 해결하는 대표적인 방법이 비트코인에서 쓰이는 가장 긴 체인을 선택하는 방법이다. 한 노드가 초록블록을 부모로 하여 분홍블록을 만들고 분홍 블록을 모든 노드에게 전파를 하면, 초록블록은 자식 블록이 연결됨으로서 빨간블록보다 긴 체인을 형성하게 되어 초록블록이 속한 체인이 메인 체인이 된다.

참조: 2018 Electronics and Telecommunications Trends_[블록체인과 합의 알고리즘]

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

블록체인 합의 알고리즘은 합의 문제 뿐만 아니라, 비잔틴 장군 문제 즉, 악의적인 노드가 분산 시스템에 참여한 상황에도 신뢰 있는 서비스를 제공할 수 있느냐는 문제를 해결하였다. 비잔틴 장군문제는 1982년 레슬리 램포트의 논문에서 처음 언급된 것으로, 지리적으로 떨어진 상태에서 각 부대의 지휘관들이 배신자의 존재에도 불구하고 충직한 지휘관들의 수가 얼마나 있어야 하며, 이 지휘관들이 어떤 규칙을 따라 교신해야 동일한 공격 계획을 세울 수 있는지에 대한 문제다. 이때, 블록체인이 부정직한 노드를 처리하는 가장 큰 무기는 정직한 다수의 힘과 보상 및 처벌의 효과다. 특정 노드가 위조된 트랜잭션을 보내거나 유효하지 않은 트랜잭션 데이터나 블록을 승인하더라도 채굴을 통한 보상을 향한 다수의 열망이 시스템 무결성을 해치려는 부정직한 노드의 욕망보다 훨씬 크고 강력하기 때문이다(출처: 블록체인 무엇인가?_다니엘 드레셔).

이렇게, 합의 알고리즘은 분산 네트워크 상에 있는 다양한 문제들을 해결하기 위한 방법으로 연구되어 왔다. 합의 알고리즘은 블록생성 권한 분배 방식, 블록생성 및 검증 방식 등에 따라 다양한 형태를 띄는데, 보다 효율적인 합의와 높은 보안, 탈중앙화를 갖춘 블록체인을 만들기 위해 현재까지도 다양한 합의 알고리즘 형태가 개발중에 있다.

합의 알고리즘의 대표적 종류와 그 발전 과정

1. 작업증명 (Proof of Work, POW)

PoW의 기본 개념은 1993년 Cynthia Dwork 와 Moni Naor에 의해 처음 고안되었으며, 1999년에 이르러 Markus_Jakobsson 과 Ari Juels에 의해 Proof of Work 라는 명칭이 붙게 되었다. 이러한 개념을 비트코인의 창시자, 나카모토 사토시가 비트코인에 적용하며 널리 알려지게 된다.

PoW는 '작업증명방식'으로, '컴퓨터 연산을 통해 특정 Nonce 값(블록 헤더의 해시 값이 난이도에 제시된 값보다 작은 값이 나오게 하는 Nonce값)을 먼저 찾는 사람'이 블록을 검증(채굴) 할 권리를 부여 받게되는 구조이다. 심지어, 연결되는 블록이 많아 질 수록 해당 난이도는 점점 올라가게 된다. 이러한 값을 찾기위해서는 무작위 숫자를 넣어보며 대입하여 푸는 방법 밖에는 없기 때문에, 컴퓨팅 파워가 클 수록 연산능력이 높아 결국 채굴을 할 확률이 커진다는 의미이다. Proof of Work 이란 용어의 의미 대로, 작업(값을 찾기위한 연산)을 통해 블록의 유효성을 증명하고 채굴 권리를 얻어내는 방식인 것이다.

이렇게 컴퓨팅 파워에 의존하는 PoW의 구조 덕분에 PoW는 보안성을 가장 큰 장점으로 가지고 있다. 이는 블록체인의 가장 유명한 취약점인 '51% 공격' 을 손쉽게 방어 할 수 있는 구조이기 때문이다. 악의적인 공격자가 51% 공격을 하기 위해서는, 51% 이상의 컴퓨팅 파워를 확보해야 하지만 이는 현실적으로 천문학적인 비용을 필요로 하기에 이를 통해 공격자가 얻을 수 있는 이익은 비용보다 낮을 수 밖에 없다.

그러나 이러한 장점과 동시에 PoW 방식은 엄청난 전력 소비를 감당해내야 하는 비효율적인 문제를 안고 있다. 비트코인 채굴에 소모되는 전력량은 연간 약 48TWh(테라와트시)로 추정되며, 이는 연간 페루나 홍콩을 넘어 포르투갈이나 싱가포르의 연간 전력에 맞먹는 규모라고 한다. 또한 이러한 구조는 자연스럽게 기업형 채굴꾼들이 나타나게되어 특정 소수에게 채굴권이 집중되는 문제를 만들어 냈다. 이는 특히 비트코인을 비롯한 블록체인 기술의 핵심 미션인 '탈중앙화' 에 반대되는 현상이기도 하다.

2. 지분증명(Proof of Stake, PoS)

비트코인을 통해 가상화폐와 블록체인 기술에 대한 관심이 점점 높아지며 PoW 방식이 가지고 있는 문제점들을 해결하고자 하는 논의가 이루어졌고, PoW 방식의 대안으로 등장하게 된 것이 바로 PoS 방식이다. PoS의 개념은 2011년, Bitcointalk 포럼에서 처음 제안되었으며 이후 Peercoin, Nxt, Novacoin 등에 채택되었다. 최근에는 비탈릭 부테린이 PoW 기반의 Etherium을 PoS로 전환하겠다는 선언을 하며 더욱 관심이 높아진 합의 방식이다.

PoS는 '지분증명방식' 으로, 해당 코인을 많이 가지고 있는(지분을 많이 보유한) 만큼 블록에 대한 유효성을 검증 할 확률이 높아지는 구조이다. 그러나 단순히 지분이 많은 사람만이 선택되는 것은 아니며, 무작위로 선택되는 'Randomized block selection' 방법과 코인의 보유기간이 코인 지분과 함께 영향을 끼치는 'Coin Age based selection' 방법이 대표적이다. PoW에서는 채굴 행위를 통해 새로운 코인이 탄생하고 이를 채굴자가 취하는 것과 다르게, PoS에서는 해당 거래의 수수료만을 가져가게 된다는 차이점이 있으며 또한 본인의 코인 지갑을 네트워크에 연결시킴으로서 이자를 받을 수도 있다.

이러한 PoS 방식은 무엇보다 PoW 방식의 문제점들을 해결한다는 장점이 있다. 컴퓨팅 파워를 소비하지 않기에 하드웨어 인프라를 필요로 하지 않고 유지비용 또한 굉장히 저렴하며, 지분 및 보유기간에 따른 권한 부여를 통해 채굴 독점 문제에서 일정 부분 벗어날 수 있게되었다. 또한 PoS 방식은 코인보유기간 조건에 따른 코인 장기 보유가 유도되며, 이러한 점은 해당 코인의 시장 가치 유지에 긍정적으로 작용할 수 있다.

그러나 PoS 방식 또한 결코 완전하지는 못하다. PoS 방식의 대표적인 문제점은 바로 'Nothing at Stake' 문제이다. 이는 적은 리소스 비용으로 인해 유효한 블록체인이 두 개 이상 존재하는 포크 상황에서, 참여자들이 보상 확률을 높이기 위해 두 개 이상의 블록체인 모두에 블록을 생성하는 행위를 할 수 있다는 것이다. 이러한 문제는 블록체인이 하나로 수렴되는 것을 어렵게 하며, 이 경우 악의적 공격에 대해 취약해지고 유효한 체인에 대한 합의를 빨리 이루지 못한다는 문제가 발생한다.

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

PoW 방식의 대안으로 야심차게 등장한 PoS 방식 또한 완전하지 못하다는 점이 드러나며, 이를 해결할 수 있는 대안으로서 EOS의 창시자 '댄 라리머'에 의해 제안 된 합의 방식이 바로 DPoS 이다. 이는 위임된 지분 증명 방식으로. PoS와의 차이점은 권한을 소수의 대표자에게 이양한다는 것이다. PoS가 직접 민주주의라면 DPoS는 간접민주주의이다. 지분 보유자들은 지분에 비례한 투표권을 행사하여 자신들을 대신하여 블록 생성과 검증, 네트워크 유지, 합의에 대한 권한을 소수에게 위임한다. 현재 가장 성공적인 사례인 'Steemit' 은 이러한 DPoS 방식을 채택해 21명의 증인(대표자)를 통해 DPoS 방식과 퍼블릭 블록체인의 가능성을 증명해주고 있다.

DPoS의 가장 큰 장점은 투표에 의해 선출 된 소수의 대표자들이 전체를 대신하여 블록을 생성한다는 점이다. 때문에 상대적으로 빠른 합의 속도와 비용이 적게 소요된다는 장점이 있다. 이와 동시에 전체 네트워크 관리와 프로젝트의 발전에 대해 아무런 관심이 없는 일반 이용자들은 오히려 편의성이 증가한다.

DPoS는 소수에 의한 효율성을 증명해냈지만, DPoS를 비판하는 많은 사람들은 공통 된 질문을 던진다. 소수에 의해 관리되는 네트워크가 과연 탈중앙화가 맞냐는 것이다. 이 점에 대해서는 각자가 생각이 다르겠지만, 기술적으로만 따지자면 노드의 소수 집중적 구조는 기존 블록체인 기술이 가지고 있는 가장 큰 강점인 '탈중앙화로 인한 보안성'을 잃어버리는 단점이 있다. 모든 네트워크가 소수에 집중되면 그만큼 공격에 취약해 지는 것은 당연한 일인 뿐더러 자신의 정체를 투명하게 공개해야 하는 증인에 대한 공격은 더욱 그렇다.

합의 알고리즘의 진화

본 글에서는 PoW 에서 DPoS 까지, 가장 널리 사용되는 세 가지의 합의 알고리즘을 언급했지만 이 외에도 PoI(Proof of Importance), PoA(Proof of Authority), BFT(Byzantine Fault Tolerance) 등 수 많은 합의 알고리즘이 제안되고 개발되어지고 있다. 어느 블록체인에나 적용가능한 완벽한 합의방식은 아직 존재하지 않기에 블록체인 기술은 아직 보편적 실용기술로 자리잡기까지는 수 많은 문제점이 있지만, 합의 알고리즘은 다양한 방향으로 계속해서 연구되어지고 있으며 이를 통해 빠르게 진화하고 있다는 점 또한 사실이다.

따라서 블록체인 기술을 통해 새로운 도전을 하고자 하는 사람들은 이러한 각각의 합의 알고리즘의 특징을 정확히 이해하고 특성에 맞게 활용해야 하며, ICO 참여자들 또한 이러한 점을 꼭 고려해서 참여 여부를 결정해야 할 것이다.

[출처]

"블록체인의 기본 개념 알아보기" (https://brunch.co.kr/@genier/11)
"Bitcoin Energy Consumption Index Chart", Digiconomist
임종철 외, "블록체인과 합의 알고리즘" ETRI 전자통신동향분석 제33권 제1호 (2018.02.)
"What is Proof of Stake?", Hackernoon (https://hackernoon.com/what-is-proof-of-stake-8e0433018256)
"쉽게 이해하는 블록체인 기술(3): 합의 알고리즘" (https://steemit.com/kr/@loum/3)
"합의 알고리즘 개요", theloop (https://blog.theloop.co.kr/2017/05/23/%ED%95%A9%EC%9D%98-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%9C%EC%9A%94/)
다니엘 드레셔, "블록체인 무엇인가?"