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

zzase·2021년 12월 31일

[블록체인] 기본 이론

목록 보기

5/7

지금까지 블록체인의 기본 이론, 구조와 종류를 공부했고 이번 글에서는 해시함수와 함께 블록체인의 핵심 알고리즘이라 불리는 '합의 알고리즘'에 대해 공부하고 블록체인의 종류마다 어떤 합의 알고리즘을 사용하는지 학습한다.

개요

우선 합의 알고리즘이란 이름 그대로 블록체인의 참여자들이 합리적이고 효율적인 의사결정을 내릴 수 있게 하는 알고리즘이다.

합의 알고리즘이 필요한 이유는 앞 글에서 설명한 블록체인의 핵심인 신뢰성을 보장하기 위함이다.

분산원장 시스템 기반인 블록체인에는 신뢰성에 관한 두 가지 문제점이 있었는데 블록체인은 이 문제를 해결하기 위해 합의 알고리즘을 만들고 제시한 것이다.

여기서 말한 두가지 문제점은 이중 지불과 비잔티움 장군의 딜레마가 있다.

이중지불

이중 지불이란 원본 파일에 저장된 가치(통장에 있는 돈)를 지불하고 , 지불 전 원본 파일을 복사하여 다른 사람에게 또 지불하는 것을 말한다. 예를 들어 같은 계좌로 모바일 이체와 온라인 송금을 동시에 누르는 것이다.

중앙기관(은행)이 있는 기존 거래 시스템에서는 이러한 일들을 방지하기 위해 중앙기관에서 무조건 순서대로 받으며 처음 거래를 승인하고 나중 거래를 잔액부족이라고 거절한다. 하지만 블록체인 구조에서는 이런 중앙기관이 없기 때문에 이를 중앙기관 없이도 해결하는 방안을 제시해야 했다.

비잔티움 장군의 딜레마

비잔티움 장군 문제는 1982년 논문에서 처음 언급된 문제로 분산 처리 시스템에서 발생할 수 있는 오류와 관련된 개념이다. 앞서 "퍼블릭 블록체인은 참여자의 제한이 없는 대신 그만큼 악의적인 참여자도 존재할 수 있다."라고 설명했었는데(읽고오기) 이를 예를 들어 설명한 문제라고 생각하면 된다.

300명의 병력이 있는 비잔티움 성을 함락시키기 위해 각 100명의 병력을 갖고 있는 장군 5명이 협동하여 치려한다.

성을 함락시키기 위해서는 300명보다 많은 병사가 필요하다.

왕의 명령(중앙기관)으로 5명에게 동시에 몇시에 공격하라 라는 메시지를 보내면 되지만 분산 시스템에서는 이들이 장군이자 곧 왕이고 서로 동등한 위치에 있기 때문에 명령이 아닌 신뢰를 바탕으로 한 약속이어야 한다.

이들은 연락병을 통해 몇시에 치자는 연락을 하며 오른쪽 방향으로 가장 가까운 장군부터 연락한다.

이들 중에는 배신자가 있을 수 있다.

장군 1 이 "9 AM" 공격 시각을 적어 서명과 함께 장군 2에게 보냄
장군 2는 장군 1의 "9 AM" 공격 시각을 보고 기억한 후 장군 3에게 전달함
장군 3은 배신자로, "9 AM" 메시지를 찢어버리고 "8 AM"으로" 으로 고쳐서 장군 4에게 전달함
장군 4는 "8AM"을 기억한 후 장군 5에게 전달
장군 5는 "8AM"을 기억
8AM에 장군 3, 장군 4, 장군 5 가 쳐들어가지만 300명이므로 지게 됨

이와 같은 이유로 인해 배신자는 절대 메시지를 훼손하거나 수정할 수 없는 알고리즘이 필요한 것이다.

정의

PoW(작업 증명, Proof of Work)

위와 같은 문제들을 해결하기 위해 나카모토 사토시는 POW를 만들어내고 비트코인이 탄생했다

블록체인의 규칙에 의해 블록체인에 참여하는 모든 노드는 블록 생성의 권한을 가진다.(public)
이때 블록에 기록된 거래 내역들이 입증되었을 때만 블록이 생성된다.
블록을 생성하기 위해서는해시(hash) 값을 구하는 수학적 연산(SHA-256)을 수행해야 한다.
이때 해시값은 연결할 블록의 해시값을 포함한 다른 값들과 직접 구해야 하는 값(Nonce)을 모두 구해야 새로운 블록의 해시값을 구할 수 있다.
(높은 컴퓨팅 파워를 가질수록 유리. 비트코인 경우 10분 소요)
작업 증명에는 이처럼 컴퓨팅 파워와 전기 비용이 들기 때문에 작업증명에 대한 보상으로 암호화폐(비트코인)가 발행되고 체인에 블록이 추가되는 순간 그에 따른 수수료(비트코인)도 받게 되므로 비트코인은 절대적이다.
만약 블록체인의 마지막 블록에서 각각 다른 사람이 동시에 블록을 생성했다고 가정하면 이 블록체인은 마지막 블록만 다른 체로 분리(fork)되지만 한쪽 체인에서 또 블록을 생성하여 먼저 그다음 블록을 연결한다면 그 체인이 더 긴 체인이 되어 그 체인을 선택하여 최신 블록체인이 되고 다른 체인은 없어진다.
이때 없어진 체인의 마지막 블록을 고아 블록이라 부르게 되는데 이 블록에 담겨있던 정보는 없어지는 것이 아니라 블록체인에 아직 담기지 않은 정보로 취급하고 다른 블록에 포함되어 채택된 체인에 이어진다.

위 규칙 중 4번에 의거하여 우리는 이중 지불을 해결할 수 있다.

만약 한 사람이 100만 원을 A와 B에게 동시에 보내서 A와 B라는 두 개의 트랜잭션이 생겨도 블록에 담겨야만 거래가 인정되는데, 블록은 10분에 하나씩 생성되고 하나의 블록엔 하나의 정보만 들어가기 때문에 두 정보가 동시에 인정되는 일은 없다.

비잔티움 문제도 같은 이유로 해결 가능하다.

위 비잔티움 장군의 딜레마 조건에 아래와 같은 사항을 추가한다.

장군들은 메시지를 보내기 위해(블록을 생성하기 위해) 반드시 10분의 시간을 들여야 함

메시지는 모든 이전 장군의 메시지(이전 블록 해시)와 자신의 10분의 시간을 들였다는 증거(None)를 포함(자기 해시)하여 보내야 함

위와 같은 규칙이 추가될 경우 3번이 다음 장군에게 잘못된 메시지를 전달하려면 그전에 받은 1번 과 2번 두 명분의 10분간 작업의 작업 증거와 자신의 10분 작업 증거까지 10분 내로 작성해야 한다. 이는 사실상 불가능하다.

블록체인은 "이전 메시지를 포함" 시킨 새로운 메시지로 이해할 수 있으며, 포함된 이전 메지시를 변경한 경우 변경(위조)되었다는 사실을 바로 알 수 있는 장부이다.

PoW는 "10분의 시간을 들여 메시지를 만드는 과정"이며, 정말 그러한 작업을 하였는지를 단번에 검증해낼 수 있는 방법을 제공한다.

다시말해 PoW는 10분 안에 절대 새로운 메시지에 이전 메시지를 다시 만들어 포함할 수 없는 알고리즘인 것이다.

PoS(지분 증명, Proof of Stake)

작업 증명의 합의 알고리즘은 블록체인 시대를 알리는 1등 공신이 되었지만 시간이 지날수록 과도한 에너지 소비 및 채굴의 독점화가 발생하기 시작했고 이에 새로운 합의 알고리즘에 대한 논의가 시작됐다.
그렇게 해서 탄생한 게 바로 지분 증명(Pos)이다.

지분 증명이란 참여자의 소유 지분(Stake)이 블록 생성 권한에 반영되는 알고리즘이다.

블록 생성 및 검증의 역할을 하는 검증자가 되기 위해서는

자신이 보유하고 있는 암호 화폐를 보증금의 형태로 작업하는 특별한 거래를 해야 한다.
그 이후에는 새로운 블록을 생성하고 검증하는 절차는 모든 검증자가 참여할 수 있도록 하는

"특정 합의 알고리즘"에 의해 이루어진다.