[블록체인] 블록체인 입문_합의 알고리즘

NAEMAMDAEROG·2022년 2월 7일

1. 합의 알고리즘

블록체인에서의 합의(분산 합의: Distributed Consensus) 는 참여자 중 누구에게 블록을 생성할 권한을 주는냐를 결정하는 것이다. 블록체인 네트워크는 중앙 기관 없이 참여자들끼리 서로 연결되어 있는 구조이기 때문에 결정을 내리기 위해서는 여러 사람들의 의견을 통일하기 위한 방법이 필요하다.

분산 합의가 이루어지기 위한 두 가지 조건

1. 올바른 참가자들 모두에 의해 같은 값으로 결정을 내리면서 합의 과정이 끝나야 한다.
2. 합의의 결과 결정된 값은 임의의 값이 될 수 없고, 적어도 하나의 올바른 참가자에 의해서 제안된 값이어야 한다.

분산 합의 알고리즘

분산 시스템에서 모두가 동일한 상태를 가지고 있을 수 있도록 하는 것.

분산 합의 시스템에서 기술적 문제들

노드가 제거되거나 악의적일 수 있다.
peer-to-peer 시스템이나 모든 노드가 서로 연결되어 있지 않다면 네트워크는 아주 불안전하다.
인터넷 연결 상태가 좋지 않으면 통신 실패 상태가 될 가능성이 있다.
모든 데이터를 관리하는 하나의 데이터 센터가 없기 때문에 다양한 통신에서 지연이 발생할 수 있다.
네트워크 지연으로 인해 분산 합의 시스템에서는 글로벌 시간이라는 개념이 없다. 모든 노드가 단순히 타임스탬프에 근거하여 이벤트의 순서를 합의하는 것이 불가능하다.

2. 분산 합의 알고리즘 종류

작업증명(PoW) : 목표값 이하의 해시를 찾는 과정을 무수히 반복함으로써 해당 작업에 참여했음을 증명하는 방식. 가장 대표적인 합의 알고리즘으로 Bitcoin, Ethereum, Litecoin, Zcash 등의 블록체인이 작업증명방식을 채택하고 있다.
지분증명(PoS) : 암호화폐를 보유하고 있는 지분율에 비례하여 의사결정 권한을 주는 방식. QTUM, Peercoin 등의 블록체인이 지분증명 방식을 사용하고 있다.
위임증명(DPoS) : 암호화폐 소유자들이 각자의 지분율에 비례하여 투표권을 행사하여 자신의 대표자를 선정하고, 이 대표자들끼리 합의하여 의사결정을 내리는 방식. EOS, Steem, Risk, Ark 등의 블록체인이 위임지분증명 방식을 채택하고 있다.
PBFT : 블록체인의 합의 알고리즘의 기본인 BFT를 확장한 형태로 Neo, R3, ICT, Tendermint 같은 블록체인들이 사용하고 있다.

3. Proof of Work (PoW)

비트코인 채굴 과정은 퍼즐 조각 맞추기와 유사하다. 퍼즐 조각 생성기는 해시 함수의 역할을 한다. 입력으로 들어온 값이 해시 함수를 통과하면 일정한 길이를 갖는 임의의 값으로 출력된다. 비트코인에서는 블록 내에 포함되어 있는 값을 0부터 1씩 증가시키면서 해시 함수에 넣는다. 해시 함수의 출력이 목표 값보다 작은 값이 나오면 채굴에 성공했다고 한다. 해시 함수의 특성상 결과를 전혀 추론할 수 없기 때문에, 목표 값보다 작은 값을 얻는 과정은 로또에 당첨되는 것에 비유할 수 있다. nonce 값을 증가시키면서 원하는 값을 얻는 과정에는 많은 컴퓨팅 자원이 소비된다.
작업증명 알고리즘의 필요성은 네트워크의 모든 노드가 동시에 블록을 만들 수 없게 하는 것이다. 작업증명 알고리즘은 Difficulty 조절 알고리즘을 이용하여 약 10분당 1개의 블록이 생성된다는 것을 보장한다. 동시에 블록이 생성되는 경우에는 길이가 더 긴 체인을 메인 체인으로 선택한다. 결과적으로 모든 참여자들이 동일한 순서로 연결된 블록체인으 유지하게 된다.
네트워크 전송 속도 지연으로 인해 네트워크 상에 체인의 분기가 발생하여, 두 개의 체인이 존재하는 상황을 가정해보자. 네트워크의 노드들은 다음 블록을 생성하기 위해 둘 중 하나의 체인을 선택하게 된다. 가장 긴 체인이 네트워크에서 선택되기 때문에 이러한 경우 더 긴 체인을 만들기 위해 경쟁한다. 이러한 경쟁은 6개의 블록이 생성되기 전에 보통 종료되기 때문에 이를 6 confirmation이라고 부른다. 사토시 나카모토는 확률 증명을 통해 분기된 체인과 원래의 체인이 6개 이상의 대립되는 블록을 생성할 확률이 0에 가깝다는 것을 증명했다.
6 confirmation은 자신이 생성한 거래는 그 거래가 포함된 블록 이후에 5개의 블록이 더 생겨야, 해당 트랜젝션이 완전하게 거래됐다는 것을 의미한다.

4. Proof of Stake (PoS)

작업 증명 합의 알고리즘의 문제

자원 낭비 문제
수학적 계산을 위해 컴퓨팅 파워를 많이 사용하기 때문에 에너지가 무의미하게 소비된다.
컴퓨팅 파워가 큰 채굴자의 영향이 커진다.
컴퓨팅 파워를 많이 가지고 있는 채굴자가 비트코인의 생성에 관여하며 이를 컨트롤할 수 있게 된다.

다양한 합의 알고리즘

1. 지분 증명(Proof of Stake)
자신이 갖고 있는 암호화폐의 양에 따라서 블록을 생성할 권한을 주겠다.

2. 위임 지분 증명(Delegated Proof of Stake)
지분으로 블록을 생성할 권한을 주지만, 위임된 몇몇의 참여자만 블록을 생성할 수 있도록 제한한다.

3. 권위 증명(Proof of Authority)
네트워크에서 자신의 평판/기여도에 따라서 블록을 생성할 권한을 부여하는 것이다.

지분 증명 (PoS)

지분 증명에서는 채굴이 일어나지 않기 때문에 채굴자가 존재하지 않고, 검증자(validator)가 존재한다. 검증자가 되기 위해서 각 참여자들이 일종의 보증금을 지불한다. 얼마의 지분을 staking(걸었는지) 했냐에 따라 검증자가 선택되며, 더 많은 지분을 보유하고 있을수록 검증자로 선택될 확률이 높다. 검증자는 자신이 가진 지분(Stake)에 비례한 확률로 블록을 생성할 권한을 얻게 되고, 블록을 생성한 후에는 자신이 원하는 체인에 블록을 연결하여 그에 대한 보상을 얻는다.
PoS는 지분에 비례하여 블록 생성의 권한을 얻기 때문에 중앙화 위험이 비교적 감소한다. 최종성(Finality)을 부여해 이미 체인에 연결된 블록들이 변경되기 힘들게 만든다. 공격자의 악의적인 행동이 발각되면 모든 자산을 0으로 만드는 패널티를 부여해 공격이 일어나지 못하도록 한다.
지분 증명을 사용하는 대표적인 블록체인으로는 Quantum, STRAT, NXT, ARDR, Ethereum 2.0 등이 있다.

PoW와 PoS의 비교

PoW는 강력한 보안성을 바탕으로 서비스가 남용되는 것을 쉽게 방지할 수 있다. 하지만 채굴 비용이 크기 때문에 개인 채굴자는 채굴할 수 없고, 채굴자들끼리의 단합을 조심해야 한다.
PoS는 경제적이며 친환경적인 합의 알고리즘이다. 블록 생산자의 탈중앙화의 안정성을 확보해주는 장점이 있다. PoS는 코인 보유량에 따라 블록을 생성한 보상을 받기 때문에 모든 참여자들이 이자를 받기 위해 코인을 보유하기만하여 유통량이 감소할 수도 있는 문제가 있다. 검증되지 않은 합의 알고리즘으로 보안성에 대해 확신할 수 없는 단점이 있다.

위임 지분 증명(DPoS)

위임 지분 증명은 자신이 가진 지분을 이용해 블록 생성을 위한 투표를 한다는 점에서 지분 증명과 원리가 같다. 지분 증명을 직접 민주주의라고 한다면 위임 지분 증명은 간접 민주주의라고 할 수 있다. DPoS는 지분을 가지고 있는 사람들이 뽑은 소수의 대표들만 투표를 진행하기 때문에 블록이 빠르게 생성된다. 즉, DPoS는 네크워크 상의 검증자 수를 제한하여 높은 수준의 확장성을 제공하는 지분 증명의 변형이다.
위임 지분 증명을 사용하는 대표적인 블록체인으로는 Steem, EOS, ARK, RISK 등이 있다. Steem과 EOS는 검증자의 수가 21개로 정해졌고, ARK는 51개, RISK는 101개로 정해졌다.

5. BFT & PBFT

어떤 합의 알고리즘이 네트워크에서 통용되기 위해선 Safety와 Liveness라는 특성을 가지고 있어야 한다.
Safety : 노드 간 합의가 발생했다면, 어느 노드가 접근하든 그 값은 동일해야 한다.
Liveness : 합의 대상에 문제가 없다면, 네트워크 내에서는 반드시 합의가 이뤄진다.

FLP Impossibility : 비동기 네크워크 내에서는 Safety와 Liveness를 모두 완벽히 만족하는 합의 알고리즘을 설계하는 것이 불가능하다는 증명. 비동기 네트워크에서는 합의 문제를 완벽히 해결할 수 있는 분산 알고리즘이 없다.

비잔틴 장군 문제(Byzantine Generals Problem)
네트워크 내에 배신자가 있더라도 합의 내용에 문제가 없으려면 어떻게 해야 하는가

분산화된 네트워크의 대다수의 참가자들은 완전한 실패를 막기 위해 동일한 행동을 하기로 결정하고 이를 실천해야 한다. 분산화된 시스템에서 이러한 합의를 달성할 수 있는 유일한 방법은 최소 2/3 혹은 그 이상의 신뢰할 수 있는 정직한 네트워크 노드를 확보하는 것이다. 이는 네트워크 참여자 대다수가 악의적으로 행동하기로 결정한 경우, 시스템이 실패하거나 공격당할 수 있음을 의미한다. 비잔틴 장애 허용은 비잔틴 장군 문제의 딜레마에서 파생되는 실패들을 막기 위한 시스템이다. 비잔틴 장애 허용 시스템은 일부 노드가 고장나거나 악의적으로 행동하더라도 계속 작동할 수 있다. 비잔틴 장군 문제를 해결하는 방법은 하나 이상일 수 있으며, 따라서 비잔틴 장애 허용 시스템을 구축하는 다양한 방식이 있다. 블록체인에서도 비잔틴 장애 허용을 보통 합의 알고리즘이라고 부른다.

PBFT(Practical Byzantine Fault Tolerance)
Safety를 확보하고 Liveness를 일부 희생하면서 비동기 네트워크에서도 합의를 이룰 수 있는 알고리즘. 네트워크에 배신자 노드가 어느 정도 있다고 해도 네트워크 내에서 이뤄지는 합의의 신뢰를 보장하는 알고리즘.
현재까지 블록체인 합의 알고리즘 중 BFT 방식을 채택했다고 하는 경우 대부분 PBFT 합의 알고리즘을 바탕으로 조금씩 변형을 가했다고 볼 수 있다.
PBFT를 간단히 요약하자면, 비동기 네트워크에서 배신자 노드가 f개 있을 때 총 노드가 3f+1개 이상이면 해당 네트워크에서 이뤄지는 합의는 신뢰할 수 있다는 것을 수학적으로 증명한 알고리즘이다.