합의 알고리즘(consensus algorithm)이란 다수의 참여자들이 통일된 의사결정을 하기 위해 사용하는 알고리즘을 말합니다. 합의 모델, 합의 방식, 합의 메커니즘 또는 합의 프로토콜이라고도 한다. 블록체인 시스템의 경우 네트워크에 참여하는 모든 참여자들이 동일한 데이터를 복사하여 분산 저장하기 때문에 원본과 사본의 구별이 없으며, 통일된 의사결정을 내릴 수 있는 권위 있는 중앙(center)이 존재하지 않습니다. 이런 상황에서 합리적이고 효율적인 의사결정을 내릴 수 있는 다양한 알고리즘이 개발되었습니다.
1. 개요
블록체인은 탈중앙화를 추구하며 전 세계의 다양한 참여자가 P2P(Peer To Peer) 네트워크 방식으로 생태계를 유지하고 있어서 그 무엇보다 참여자의 의견 일치(합의)가 중요합니다.
합의 알고리즘은 블록체인 네트워크에 합의를 달성하는 메커니즘이라 정의할 수 있습니다. 탈중앙화된 블록체인은 분산화된 시스템으로 구성되어 있으며, 중앙 권위체에 의존하지 않기에, 분산화된 노드는 트랜잭션의 유효성에 합의가 필요합니다.
예를 들어 A라는 사람의 금융 거래 내역과 관련하여 한국에서는 1,000원의 잔액이 확인되는데 미국에서는 5,000원의 잔액이 확인된다면 많은 혼란이 발생할 수밖에 없습니다. 이에 블록체인은 합의 알고리즘에 의해서 한국에서 조회하든 미국에서 조회하든 동일한 가치의 잔액이 확인 될 수 있도록, 즉 모든 분산 원장이 동일한 데이터 값을 유지하도록 합니다. 만약 특정 노드에 의해 데이터 값이 조작되거나 이중 지불이 발생하는 등 합의 알고리즘이 정상 작동하지 않는다면 해당 블록체인 시스템은 신뢰성을 잃어버리기 때문에 효과적인 합의 알고리즘 구현은 무엇보다 중요한 요소라고 할 수 있습니다.
그렇기 때문에 이곳이 바로 합의 알고리즘이 시작되는 지점입니다. 합의 알고리즘은 프로토콜 규칙이 준수되고 있는지 확인하며, 모든 트랜잭션이 신뢰할 수 있는 방식으로 진행되는 것을 보장해, 코인이 한 번만 사용되도록 합니다.
합의 알고리즘은 분산화된 노드들이 어떤 버전의 블록체인이 진짜 버전인지 합의할 수 있게 합니다. 디지털 경제 시스템이 제대로 작동하기 위해서는, 현 상태의 블록체인에 합의하는 것이 필수적입니다. 작업증명 합의 알고리즘은 비잔티움 장군 문제를 해결하는 최고의 해결책으로 간주하며 이는 비트코인을 비잔티움 장애 허용 시스템으로 탄생시켰습니다. 이는 비트코인 블록체인이 51% 공격(또는 다수의 공격)과 같은 공격에 매우 강력함을 뜻합니다. 네트워크가 탈중앙화되어 있을 뿐만 아니라, 작업증명 알고리즘을 사용하기 때문이다. 마이닝 과정에 드는 높은 비용은 마이너들이 네트워크를 방해하기 위해 자신들의 자원을 투자하는 것을 무척 어렵게 한다.
물론 하나의 노드에 권한을 부여하여 블록 생성 역할을 전담한다고 하면 보다 쉽게 분산 원장을 유지할 수 있습니다. 그러나 이는 단일 실패 지점을 가지는 기존의 중앙 서버 방식과 큰 차이가 없을 뿐더러 블록체인의 핵심은 바로 특정 노드에 의존하지 않으면서 동시에 신뢰를 제공하는 것이기 때문에, 결과적으로 어떻게 개별 노드들이 자율적으로 블록을 생성하면서도 모든 노드들이 동일한 블록의 체인을 가질 수 있을까가 합의 알고리즘 논의의 관건이라고 볼 수 있습니다.
2. 합의 알고리즘 vs 프로토콜
알고리즘과 프로토콜은 흔히 바꿔서 사용되기도 하지만, 완전히 같은 것은 아닙니다. 간단히 말하자면, 프로토콜은 블록체인의 기본 규칙이며, 알고리즘은 이러한 규칙을 따르는 매커니즘으로 정의해볼 수 있습니다.
금융 시스템에서 광범위하게 사용되고 있는 것 외에도, 블록체인 기술은 다양한 사업에 적용될 수 있고, 다른 용도에도 적합할 수 있습니다. 그러나 어떤 상황에서든지, 블록체인 네트워크는 시스템 작동 방식을 결정하는 프로토콜 위에 구축될 것이며, 따라서 시스템의 모든 요소와 네트워크 참여자들은 기본 프로토콜 규칙을 따라야 할 것입니다.
프로토콜이 규칙이 무엇인지 규정한다면, 알고리즘은 이러한 규칙을 준수하고, 원하는 결과물을 도출해내기 위해 어떠한 절차를 거쳐야 하는지 시스템에 지시합니다. 예를 들자면, 블록체인 합의 알고리즘은 트랜잭션과 블록의 유효성을 결정하는 것입니다. 따라서, 비트코인과 이더리움은 프로토콜이며, 작업 증명과 지분 증명(PoS, Proof of Stake)는 이들의 합의 알고리즘입니다.
보다 자세히 설명하자면, 비트코인 프로토콜은 노드가 상호 작용하는 방법과 데이터가 전송되는 방법, 성공적인 블록 검증을 위한 필요 조건들을 정의한다는 점을 고려해야 합니다. 반면, 합의 알고리즘은 잔고와 서명을 검증하고, 트랜잭션을 승인하고, 실제로 블록의 유효성 검사를 실시하며, 이 모든 것은 네트워크 합의에 달려있습니다.
3. 합의가 작동하는 방식
노드는 합의 메커니즘에서 근본적인 역할을 합니다. 보류 중인 거래의 데이터를 평가하고 기록을 상호 참조한 후 승인 또는 거부 상태를 전달합니다. 예를 들어, 개인이 이미 소비된 코인으로 거래를 시도하면 대부분의 노드는 불변의 원장에 대해 이를 거부하여 시스템의 신뢰성과 정확성을 보장합니다.
또한 어떤 노드가 확립된 기록에 이의를 제기하기로 결정하면 네트워크 전체에 대한 회수를 호출해야 합니다. 노드의 2/3 이상이 동의하는 경우에만 거래가 블록체인에 확인, 배포 및 지워지지 않게 기록될 수 있습니다.
4. 합의 알고리즘 종류
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를 비판하는 많은 사람들은 공통된 질문을 던진다. 소수에 의해 관리되는 네트워크가 과연 탈중앙화가 맞냐는 것입니다. 이 점에 대해서는 각자가 생각이 다르겠지만, 기술적으로만 따지자면 노드의 소수 집중적 구조는 기존 블록체인 기술이 가지고 있는 가장 큰 강점인 '탈중앙화로 인한 보안성'을 잃어버리는 단점이 있습니다. 모든 네트워크가 소수에 집중되면 그만큼 공격에 취약해 지는 것은 당연한 일인 뿐더러 자신의 정체를 투명하게 공개해야 하는 증인에 대한 공격은 더욱 그렇습니다.
4) 비잔틴 장애 허용(Byzantine Fault Tolerance, BFT)
BFT는 1982년에 발표된 논문 비잔틴 장군 문제(Byzantine Generals’ Problem)을 해결하기 위해 제안되었습니다. 비잔틴 장군 문제란 비잔틴 제국의 여러 장군들이 하나의 적군을 공격하기 위해 출격을 하는데, 적군과의 전쟁에서 승리하기 위해서는 과반수 이상의 장군들이 같은 시각에 공격을 해야 합니다. 그러나 장군들은 오직 연락병을 통해서만 소통을 할 수 있으며 장군들 중에는 한 명 이상의 배신자가 존재하기 때문에 어떻게 출격 시각을 합의할 것인가가 중요한 문제가 됩니다.
이러한 이유로 BFT 계열의 알고리즘은 단순 고장난 노드 뿐만 아니라 악의적인 노드가 있음에도 전체 시스템이 안정적으로 동작하도록 하는 알고리즘을 일컫습니다.
이 중 PBFT(Practical Byzantine Fault Tolerance)은 BFT계열 프로토콜 중 실용적으로 쓰일 수 있는 가장 대표적인 프로토콜입니다. 리플리카 중 의사결정의 리더 역할을 하는 primary 노드가 있으며, primary 노드의 주도하에 순차적으로 명령이 수행될 수 있도록 합니다. 만약 primary 노드가 고장나거나 악의적인 행동을 하게 되면 일명 ‘view change’라는 절차를 통해 primary 노드를 바꿉니다. 일반적으로 여러 개의 리플리카로 구성되는 리플리카 시스템에서 전체 노드(N개) 중 몇 개의 노드가 문제가 있을 시(F개) 정상 동작하도록 설계가 되는데, PBFT 프로토콜의 경우, N=3F+1일 때 동작이 보장되는 프로토콜입니다.
4) 기타 알고리즘
그 외의 위의 해당하지 않은 다양한 종류의 합의 알고리즘이 있습니다. 이 중에서 PAXOS와 Raft 알고리즘을 알아봅니다.
a) PAXOS
사전 확인과 수락 요청 및 최종 합의의 2단계로 진행됩니다. 사전 확인 과정에서는 제안node노드가 합의 도출을 위한 제안 메시지를 각 투표 노드로 전달하며, 과반 수의 사전 확인 후 수락 요청 처리하비낟. 수락 요청 및 최종 합의 과정에서는 제안 노드의 수락 결과가 검증N노드에 취합되며 최종 합의 결과는 제안 노드에 전달하여 완료합니다.
b) Raft
Raft는 PAXOS 알고리즘을 보완한 형태의 합의 알고리즘으로써, 리더를 선출하고 해당 리더로 하여금 거래 처리 및 합의 도출 과정을 전담하게 하여, 프로세스를 단순화하고 합의속도를 향상 시켰습니다. 리더 선출 과정에서는 한번에 하나의 리더만이 존재하며, 선출주기는 별도로 지정되어 있지않고, 다음 리더 선출 시까지로 합니다. 참여자가 heartbeat timeout 시간(리더 노드가 본인의 생존을 노드들에게 알리고 동시에 응답을 받음으로써 각자 잘 살아있는지 서로의 생사를 확인 시간) 내에 메시지를 받지 못하면 리더가 없다고 판단하여 후보자가됩니다. 선출 진행시 과반수의 득표를 얻은 후보자가 없는 경우, 새로운 선출을 진행합니다.
합의 과정에서는 PAXOS와 유사한 구조로 합의를 진행하며, 리더만이 메시지를 전달하여 합의 절차를 진행할 수 있습니다. 1차적으로 메시지 수락에 대한 사전 확인을 과반수의 노드로부터 회신받고, 2차적으로 모든 노드로부터 확정을 회신을 받음으로 합의를 도출합니다. 리더 부재시 보든 과정은 중단되고 선출부터 다시 진행합니다.
5. 합의 알고리즘 정리
아래의 표는 앞서 설명한 대표 및 그 외 합의 알고리즘에 대한 설명 주소입니다.
1. https://101blockchains.com/consensus-algorithms-blockchain/
2. https://verticalplatform.kr/archives/9984
3. https://plisio.net/ko/blog/what-is-a-consensus-mechanism
4. http://wiki.hash.kr/index.php/%ED%95%A9%EC%9D%98_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
5. https://steemit.com/kr/@kblock/44-1-pow-pos
6. https://ettrends.etri.re.kr/ettrends/169/0905169005/33-1_45-56.pdf
7. https://academy.gopax.co.kr/beulrogcein-habyi-algorijeumiran-mueosingayo/
'[04] 블록체인' 카테고리의 다른 글
| 02. 블록체인 플랫폼 (1) | 2024.03.31 |
|---|---|
| 01. 블록체인(Blockchain) (1) | 2023.12.10 |