쉽게 이해하는 블록체인 기술(3): 합의 알고리즘

오늘은 암호화폐에서 합의 알고리즘에 대해서 알아봅니다.

합의 알고리즘은 왜 필요할까요?

앞에서 언급한 것과 같이 P2P 네트워크에서 다수의 피어가 존재하고 이 피어들이 하나의 블록체인(DB)를 유지하기 위해서 이 피어들, 더 구체적으로 채굴자들이 합의를 해야 합니다.

따라서, 블록체인 기술의 핵심은 합의 알고리즘이고, 암호화폐에서 제일 어려운 부분도 합의 알고리즘입니다.

먼저 합의 알고리즘은 채굴자들이 하는 것이라는 것이 중요합니다.

즉, 이것은 누가 블록을 채굴을 할 것, (즉, 채굴확률을 어떻게 결정할 것)인지와 어느 체인이 유효한지를 결정합니다.

먼저 채굴하는 방법에는 1) 작업증명(Proof of Work, PoW)와 2) 지분증명(Proof of Stake)가 있습니다.

작업증명은 작업, 즉 계산 능력에 따라 채굴 능력, 즉 채굴 확률이 결정됩니다.

즉, 내가 채굴 능력이 1이고, 친구가 2이면, 이들의 채굴확률은 1:2로 결정이 됩니다. 내가 1개 채굴할 때 친구는 확률적으로 2개를 채굴할 수 있는 것입니다.

이와 마찬가지로, 지분 증명은 지분량, 즉 소유한 코인 개수에 따라 채굴 확률이 결정이 됩니다.

합의 알고리즘은 경쟁방법과 비경쟁 방법으로 구분할 수 있습니다.

먼저 경쟁방법은 경쟁을 통해서 하나의 DB, 즉 블록체인을 유지하는 방법입니다.

이와 달리 비경쟁적 방법은 블록체인을 구분하는 방법을 사용하며, 구체적으로 블록에 표시를 삽입하여 구분합니다.

먼저, 경쟁 방법은 비트코인, 라이트코인과 같이 PoW를 사용하는 모든 코인이 해당합니다.

이들은 계산 능력 경쟁을 통해서 하나의 블록체인을 유지합니다... 구체적으로는 경제적 원리인 손해를 보지 않기 위해서 행동하기 때문에 하나의 블록체인을 유지하는 것입니다.. 이 부분은 뒤에 나옵니다.

이 방법의 단점은 경쟁을 하게 되므로 항상 포크(fork)가 발생합니다.

이와 달리 비경쟁 방법은 블록에 채굴자의 디지털 서명 등을 삽입하는 방법을 사용하며, 포크를 막을 수 있습니다.

합의 알고리즘은 두가지가 가장 중요합니다.

책임성은 채굴자가 잘못(공격)을 하면, 그에게 경제적 손해를 입혀서 하나의 블록체인을 유지하게 됩니다.

이에 대한 부분은 뒤에서 구체적으로 다룹니다.

또한 확정성(finalization)은 포크가 발생하지 않도록 확정하는 것을 말합니다.

PoW은 확정성이 없으며, 비트코인의 경우 확률적으로 6컨펌(6개 블록의 생성) 이후에 하나의 블록체인을 유지한다고 생각하는 것입니다. 이것은 사토시가 자신의 계산으로 임의적으로 정한 규칙입니다.

합의 규모는 PoW의 경우 채굴자 전체가 되며, 비경쟁 방법은 일정한 채굴자들이 투표하는 방법을 사용합니다.

그러면, 먼저 경쟁적 블록생성 방법에 대해서 알아보겠습니다.

경쟁방법으로 비트코인의 PoW를 예로 설명하면 아래와 같습니다.

PoW는 네트워크에 있는 채굴자들이 독자적으로 해시 계산(블록해시를 계산 함)을 하고, 이것이 특정 목표(비트코인의 경우 타겟(target))보다 작거나 같으면, 승리하는 게임입니다.

즉, 누가 target 보다 작은 블록해시를 빨리 찾는가라는 게임을 합니다.

특정 채굴자가 원하는 블록해시를 찾으면, 이를 네트워크에 전파하고 바로 다음 블록해시를 찾게 되며, 이를 전파받은 이웃 채굴자들은 이 블록을 검증하여 통고하면, 이를 이웃 채굴자에게 전파한 후 다음 블록해시를 찾게
됩니다.

포크는 아래와 같이 실제 포크를 생각하고 만든 용어이고, 아래의 블록체인에서 2a, 2b가 포크 상태였다가 주체인이 2a로 결정되었고, 또한 5a, 6a가 포크가 2블록이 유지되었다가 5b, 6b가 주체인이 된 경우를 보여줍니다.

실제 비트코인의 경우 2b와 같이 하나의 블록이 포크가 나는 경우는 하루에 몇번있고, 5a, 6a와 같이 두개의 블록이 포크가 난 경우는 일주일에 몇번이 있다고 들었습니다.

하지만 3개의 블록이 포크가 난 경우는 소프트포크를 하려다가 하드포크가 된 v0.9(?)인가에서 한번 발생을 했고, 자연적으로 발생한 적은 없다고 합니다.

그래서, 거래소의 경우 3컨펌에 이체를 할 수 있게 해주는 것입니다.

PoW에서 하나의 블록체인을 유지하는 원리는 그 바탕에 경제적인 원리가 있습니다.

즉, 보상과 손해이며, 보상은 P2P 네트워크를 유지하도록 하며, 손해가 하나의 블록체인을 유지하는 원리입니다.

그러면, 왜 PoW에서 가장 긴 체인(the longest blockchain)이 하나의 블록체인을 유지하도록 할까요?

이것은 매우 중요한 것으로, 피어코인과 초기 PoS 합의 알고리즘도 PoW를 따라서 PoW와 같지만, 경쟁을 지분으로 하도록 하는 경쟁적 PoS 합의 알고리즘을 만들었습니다.

하지만, 이 알고리즘은 포크가 났을 때 하나의 블록체인으로 수렴을 잘 하지를 못했습니다.

이 문제를 nothing at stake라고 말하며, 포크 시 포크된 두 체인에 모두 베팅을 해도 전혀 손해가 없기 때문에 붙여진 이름입니다.

즉, 이것은 포크가 났을 때 채굴자가 두 체인에 모두 베팅을 하여 하나의 블록체인을 유지하기 힘들기 때문이었습니다.

그렇다면, PoW의 가장 긴 체인은 왜 포크 시 하나의 블록체인으로 될까요?

이것은 두 체인에서 모두 채굴을 하려면 계산 능력을 두 체인으로 나누어 계산을 해야하기 때문입니다.

이때문에 두 체인 중에서 유리한 체인을 골라서 유리한 체인에 모든 계산 능력을 집중하는 것이 보상에 유리하기 때문입니다.

즉, PoW의 가장 긴 체인은 채굴자가 손해를 보지 않기 위해서 하는 행동이 하나의 블록체인을 유지하는 원리가 되는 것입니다.

이 부분은 매우 중요하고,, 초기 PoS 개발자도 이해하지 못한 부분입니다.

그리고, 중요한 것이 합의 알고리즘의 가장 깊은 곳에는 항상 경제적원리가 있고, 하나의 체인을 유지하기 위해서 잘못했을 때 채굴자에게 손해를 입히는 방법을 사용한다는 것입니다.

실제 비경쟁적 PoS의 경우, nothing at stake를 해결하기 위해서 예치금을 도입하여 채굴자가 예치금을 예치한 후에 채굴을 할 수 있으며, 인출 요구 후 일정기간(예 1달) 후 인출이 가능하도록 하여서, 공격자가 누구인지를 가린 후 그에게 손해를 입히고 그 후 인출이 가능하도록 하고 있습니다.

아래는 비트코인의 블록해시의 예를 보여줍니다.

비트코인은 타켓보다 작은 블록해시를 찾는 게임이므로, 그리과 같이 블록해시의 앞 부분이 비슷하게 zero가 됩니다.

참고로, 블록해시 구하는 방법은 블록의 헤더부의 6개(80바이트로 고정됨)를 해시함수인 sha256에 넣어서 나온 256비트가 블록해시가 됩니다.

아래그림은 mastering bitcoin 2판의 그림입니다.

즉, 파란 블록체인을 찾은 후 북미에서 빨간 블록을 찾고, 동시에 호주에서 녹색 블록을 찾아서 빨간 블록과 녹색블록으로 포크가 난 경우를 보여줍니다.

이와 같이 포크는 지역적인 원인, 즉 블록의 전파시간의 차이 때문에 발생합니다.

만일 비트코인의 블록생성시간을 10분에서 1분으로 줄이면, 포크는 더욱 많이 발생하게 됩니다.

아래는 2013년 11월 28일자의 포브스 기사를 보여줍니다.

당시 비트코인의 계산 능력은 전세계 최고 500대 슈퍼컴퓨터보다 약 256배 빨랐다고 합니다.

아래는 비트코인의 해시레이트를 보여줍니다.

2013년 보다 현재의 해시레이트는 엄청 증가한 것을 볼 수 있습니다.

그리고, 비트코인과 비트코인 캐시의 가격은 이들의 해시레이트의 비율과 비슷한 것을 볼 수 있습니다.

왜 이런 현상이 나올까요?

이것은 높은 해시 레이트(계산 능력)가 높은 보안 능력이기 때문입니다.

즉, 비트코인 네트워크가 더 높은 해시레이트를 가지면, 공격자도 더 높은 해시레이트를 가져야 가장 긴 체인을 만들 수 있기 때문입니다.

즉, 가장 긴 체인이라는 룰이 더 높은 해시 레이트의 보안 능력을 더 높여주는 것입니다.

아래는 비경쟁적 블록생성 방법을 보여줍니다.

비경쟁적 합의 알고리즘은 블록체인을 구분하는 방법으로 블록에 표시를 삽입하는 방법을 주로 사용합니다.

이 방법은 대부분 투표 시스템인 BFT 방법을 사용하며, 블록에 찬성을 한 채굴자들의 서명이 포함하는 방법 등을 사용합니다.

BFT 방법은 전체 투표자의 2/3 이상이 블록에 동의를 하면, 이 블록이 확정(finalization) 되며, 따라서 포크가 불가능해집니다.

이것은 투표 방법이므로, 투표인 수는 고정됩니다.

실제 예로 텐더민트 합의 알고리즘은 블록에 채굴자의 서명을 추가하고, EOS의 경우 TaPoS에 의해서 이전 블록해시가 거래에 포함됩니다.

즉, 블록 4b의 거래는 블록 3b의 블록해시를 포함하여서 거래가 어느 체인에 속하는지를 알 수 있습니다.

아래는 본인이 제안한 비경쟁적 합의 알고리즘에 대한 것입니다.

제가 제일 처음 제인한 합의 알고리즘은 2014.10.20이며, 제목은 Proof of Randomness로서 PoS 방법은 아닙니다.

당시 저는 합의 알고리즘이 단지 랜덤하게 다음 블록 생성할 채굴자를 결정하는 것같이 보여 이와 같이 랜덤한 방법을 사용했습니다.

또한 당시 PoW 합의 알고리즘을 보고, 모여서 가위바위보를 하면 될 텐데 왜 저렇게 전기를 많이 써가면서 할까라는 의문을 가졌습니다.

그 아래는 2015년 4월 1일에 작성한 저의 비경쟁적 합의 알고리즘을 보여줍니다.

이것은 비경쟁적 방법이고, PoS 방법을 사용했습니다. 시빌공격을 막을 수단이 지분 또는 채굴능력 외에 다른 것이 있기가 힘들다고 생각을 하고 PoS 방법을 사용한 것입니다.

또한 이것은 PoW나 투표 방법과 달리 계정 DB를 이용하여 다음 채굴자를 램덤하게 계산하는 방법을 사용했습니다. 좀 특이한 방법입니다.

즉, 계정 DB에서 PoS 방법을 사용하여 다음 채굴자를 결정하고, 이 채굴자가 살아있으면, 이를 네트워크에 알리고 블록을 생성하여 전파하는 방법입니다.

이때 이와 같은 방법을 사용한 것은 투표 방법은 모든 투표자가 자신의 선택을 전파해야 하므로, 트래픽이 투표자의 수와 같이 많이 발생합니다.

하지만, PoW의 방법은 승리자만 블록을 전파하여 네트워크 트래픽을 크게 줄이는 방법을 사용했고, 본인도 이런 방법이 좋은 방법이라고 생각하여 합의 과정에 네트워크 트래픽이 적게 발생하는 방법을 사용한 것입니다.

---

쉽게 이해하는 블록체인 기술(1) : https://steemit.com/kr/@loum/1

쉽게 이해하는 블록체인 기술(2): https://steemit.com/kr/@loum/6knvph-2