이 문서는 DPOS (위임 지분 증명) 알고리즘의 개선 사항을 설명합니다. 개선된 DPOS는 DPOS 3.0 프로토콜을 따르는 노드의 네트웍이 합의에서 벗어나지 않도록 더욱 강하게 보장합니다. 합의에서 벗어난다(falling out of consensus)는 상황은 두 개의 노드가 서로 다른 블록을 비가역(변경불가확정) 상태에 도달했다고 결론을 내릴 때라고 정의합니다.
비트코인과 같이 작업 증명(proof of work)으로 동작하는 블록체인은 합의를 "가장 긴 체인" 규칙에 따라 정의합니다. 이 규칙을 사용하면 그 어떤 블록도 비가역 상태에 도달했다고 확인할 수 없습니다. 어떤 시점에서도 누구나 오래된 블록을 기반으로 더 긴 체인을 만들 수 있고 노드 역시 전환할 수 있습니다. 이런 관점에서 보면 우리는 비트코인이 포크를 변경하려는 시도의 경제적인 비용에 기반한 높은 확률의 비가역성만 제공한다는 결론을 내릴 수 있습니다.
BitShares는 위임 지분 증명을 도입했습니다. 이 알고리즘을 이용하면 지분참여자들은 블록 프로듀서를 선거로 선출합니다. 블록 프로듀서는 의사 무작위 방식으로(pseudo-randomly) 섞이고, 블록을 생산할 수도 있고 아닐 수도 있는 절대 시간 슬롯을 할당받습니다. 대부분의 프로듀서가 작성해가는 블록체인은 프로듀서가 거의 없는 블록체인보다 길이의 측면에서 훨씬 빨리 길어질 것입니다. 다른 속도로 길어지는 두 개의 체인이 있다고 가정하면, 더 빨리 길어지는 체인이 종국에 가서 가장 긴 체인이 될 것입니다. 그렇기 때문에, 원래의 위임 지분 증명 알고리즘은 비트코인과 유사한 보장을 제공했었습니다. 말하자면, 체인에 블록이 추가됨에 따라 블록 하나를 뒤집을 만한 다른 체인이 존재할 확률이 점점 더 낮아지기 때문입니다.
DPOS 스케줄링 알고리즘의 본질은 지켜보는 참관자들에게 많은 정보를 전달해주는 데 있습니다. 예를 들어, 놓친 블록의 빈도를 근거로 참관자가 속한 체인이 소수 체인(옮긴이 주: 짧은 체인)이 될 가능성을 탐지할 수 있습니다. 21개의 프로듀서가 있는 상황에서 노드는 딱 2번 연속으로 놓친 블록(6초)이 발생한 직후 자신이 소스 포크에 속해있을지도 모른다는 사실을 정확히 감지할 수 있습니다. 이렇게 하면 네트워크가 불안정한 경우 사용자에게 상황을 알리고 사용자는 확정이 완료될 때까지 조금 더 기다릴 수 있습니다. 마찬가지로 모든 프로듀서가 트랜잭션을 받아들이는 21개의 블록에서 놓친 블록이 없다면, 생성된 블록이 되돌려지지 않을 것이라고 확신할 수 있습니다.
(옮긴이 주: 기술백서 v1 기준에서 블록 생성은 3초마다 이루어집니다. 그래서 이 문서는 EOSIO 기술백서 v1을 기준으로 작성된 것으로 추정됩니다. 기술백서 v2 기준으로 본다면, 블록 생성은 0.5초마다 이루어집니다. 그러므로 '딱 2번 연속으로 놓친 블록'은 1초입니다. 이에 대해 깃헙 이슈 2718번의 덧글로 RalfWeinand는 위의 내용을 지적했습니다.)
DPOS 2.0에 들어서서 우리는 마지막-비가역-블록 개념을 도입했습니다. 이 블록은 블록 프로듀서 수의 2/3에서 1을 더한 프로듀서가 생성한 가장 최근에 만든 블록입니다. 이론적으로 보자면, 블록 하나를 승인한 체인 하나를 전체 프로듀서 수의 2/3에서 1을 더한 만큼의 프로듀서가 작성하고 있다면, 다른 포크가 존재하기는 불가능하다는 이야기입니다.
그렇긴 하지만, 진취적인 사람들은 네트워크가 나눠져서 두 개의 체인을 만드는 네트워크가 생기는 가상의 시나리오를 생각해왔습니다. 이런 경우 보통 하나 혹은 양쪽의 체인이 양쪽 어느 네트워크 하나가 프로듀서 수 2/3에서 1을 더한 수만큼의 프로듀서에 재연결되기 전까지는 마지막-비가역-블록을 그 다음 블록으로 확정하는 작업을 중단합니다. 이와 같이 정상적인 동작이 이루어지면, 모든 작업이 순조롭게 진행되며 연결이 정상화될 때 모든 노드는 하나의 진짜 체인으로 수렴할 것입니다. 그렇긴 하지만, 두 개의 부분집합이 동시에 포크를 전환해서, 양쪽의 포크가 서로 다른 블록 하나에 프로듀서 수 2/3에서 1을 더한 만큼의 투표에 도달한 상황에 처하는, 레이스 컨디션(race condition)이 존재합니다. 이런 상황이 발생하면 포크의 양쪽에 있는 노드들은 양쪽 모두 마지막-비가역-블록이 정해진 시점 이전으로 되돌리지 않을 것이므로, 양쪽의 노드들은 동기화할 수 없습니다. 이제 수동으로 조정해주어야 합니다.
이런 상황에서 하나 또는 양쪽 포크는, 포크의 어느 한 쪽에 프로듀서 수 2/3에 1을 더한 수를 만족했느냐에 따라서 비가역 지점을 확정해나가는 동작을 멈출 것입니다. 소수 체인은 절반의 속도로 작성될 지도 모릅니다만, 비가역 상태를 기다리는 노드들은 소수 체인에 수용되는 어떤 트랜잭션도 최종적인 상태라고 더이상 인정하지 않을 것입니다.
이런 장애 유형은, 역전되는 단일 블록을 초래하고, 몇몇 서비스는 손해를 입을지도 모릅니다. 우리의 추산으로는, 이런 일이 벌어질 확률은 6개의 승인을 얻은 비트코인 블록 하나가 역전되는 확률보다 훨씬 낮습니다. 이런 추정은 이와 같은 상황이 목격되지 않은 상태로 3년 동안 운영해온 BitShares와 Steem 양쪽의 실환경 테스트를 밑받침합니다.
EOSIO를 통해서 우리는 하나의 체인에서 일어난 트랜잭션이 최종적임(final)을 다른 체인에 효율적으로 증명할 수 있는 방법을 제공하는 블록체인간 통신(Inter-Blockchain Communicaion, 줄여서 IBC)을 도입했습니다. 하나의 블록체인이 다른 블록체인으로부터 메시지를 받아들이면, 실수를 바로잡기 위해서 양쪽 체인을 역전시키는 것이 쉽지도 않고 바람직하지도 않기 때문에, IBC에서는 최종성(finality)이 대단히 중요합니다.
블록체인 하나가 비트코인 예치금을 자신의 체인 안에 받아들이는 시도를 하는 순간을 상상해보세요. 사용자는 모든 비트코인 블록 헤더와 자신이 참조하는 블록 위에 이어서 만들어진 6개의 블록 헤더를 제출합니다. 이 증거에 따라서 블록체인은 비가역적인 액션을 실행합니다. 이제 비트코인이 포크되고, 증거에 포함된 블록 6개가 undo되었다고 상상해볼까요? 이 블록체인은 이전에 승인된 비트코인 트랜잭션을 불합격 처리할 수도 없고 비트코인 트랜잭션이 포함된 자신의 블록을 역전시킬 수도 없습니다. 그러한 사고가 발생하면 수동으로 조정하고/조정하거나 하드 포크(hard fork)가 필요합니다. 그러한 하드 포크/수동 조정은 연결된 모든 체인을 통해서 파문을 일으킬 것입니다. 이것은 실행 가능한 옵션이 아닙니다.
모든 비(非)-비잔틴 상황에서 안전하고 믿을 수 있는 IBC를 가능하게끔, DPOS 3.0 + BFT 방식은 마지막-비가역-블록(Last Irreversible Block, 줄여서 LIB) 계산 방식을 약간 변경합니다. 이 변경을 통해서 우리는 블록 프로듀서 노드의 최소 1/3이 의도적으로 악한 마음을 품지 않는다면 두 노드가 LIB와 관련하여 서로 다른 결론을 내리는 게 불가능하다는 점을 증명할 수 있습니다. 뿐만 아니라, 심지어 노드 하나의 악의적인 행동도 증명할 수 있습니다.
DPOS의 핵심 아이디어는 생성된 블록 각각이 모든 이전 블록에 대한 투표라는 점입니다. 이 모델을 사용하면, 프로듀서 2/3 이상이 특정 블록 하나를 기반으로 블록을 만들어왔다면 해당 블록이 2/3 이상의 투표를 얻은 것입니다. 이 상황은, 비(非)-비잔틴 블록 프로듀서들이 다른 시점에 다른 포크에서 블록을 작성할 가능성이 있다는 점을 제외한다면, 이론상 적절하게 들립니다. 만약 비(非)-비잔틴 블록 프로듀서들이 다른 포크에서 블록을 생산한다면, 포크된 각 체인에 나타나는 동일한 블록 넘버에 대해 결국 간접적으로 상충하는 표를 던지게 되는 상황에 처하게 됩니다.
블록 프로듀서 A, B, C가 참여하는 네트워크 하나를 생각해봅시다. 이 네트워크에 문제가 하나 발생한 탓에 두 개의 블록 프로듀서가 짧은 시간 동안 통신이 두절되었고, 시각 T에 블록 프로듀서 A는 블록 N을 생성하고 시각 T+1에 블록 프로듀서 B는 블록 N을 생성했다고 해봅시다. 이제 블록 프로듀서 C는 블록 프로듀서 B가 시각 T+1에 생성한 블록 N에 이어서 시각 T+2에 블록 N+1을 생성하면서 동점(tie)를 깼다고 해봅시다. 이런 상황이 발생하고 프로듀서 A가 프로듀서 C의 블록 N+1의 존재를 알게되면, 프로듀서 A는 더 긴 포크를 따라 전환할 것입니다. 프로듀서 A가 블록을 생성할 차례가 오면, 프로듀서 A는 자신이 이전에 생성한 블록 N과 상충하는 프로듀서 B의 블록 N을 간접적으로 승인할 것입니다.
DPOS 2.0 규칙에 따르면, 프로듀서 A가 만든 블록 N은 프로듀서 A, B, C로부터 투표를 받았을 것이며 그러므로 (2/3 + 1) 승인으로 인해 비가역 상태가 되었을 것입니다. DPOS 3.0에서 우리는 프로듀서 A가 자신이 다른(alternative) 블록 N을 승인했다고 공개하도록 요구합니다. 이와 같은 정보 공개 때문에 네트워크는 프로듀서 B가 만든 블록 N이 받은 투표수에서 프로듀서 A의 블록 하나를 뺄 것입니다. 그러면 프로듀서 B의 블록은 단 2개의 투표만 받은 셈이 되고, 이건 비가역 상태에 도달하기엔 충분하지 않습니다.
DPOS 3.0 규칙에 따르면, 프로듀서 B가 만든 블록 N은 직접적인 비가역 상태에 절대로 도달할 수 없습니다. 왜냐하면 비가역 상태에 도달하기 위해서는 프로듀서 A, B, C로부터 2/3 + 1 만큼의 투표를 얻어야 하고 프로듀서 A는 다른(alternative) 블록 N에 투표하기 때문입니다. 대신 프로듀서 A가 블록 N+2를 작성하고 프로듀서 B가 블록 N+2를 작성하면, 블록 N+1은 비가역 상태가 됩니다. 이렇게 해서 블록 N+1은 2/3 + 1에 도달하는 데 필요한 투표 3개를 확보합니다. 프로듀서 C가 만든 블록 N+1이 비가역 상태에 도달하면, 프로듀서 B가 만든 블록 N도 비가역 상태로 간주됩니다.
이 알고리즘을 구현하기 위해 각 블록 프로듀서는 임의의 포크에서 이전에 승인한 가장 높은 블록 번호 (H)를 블록 헤더에 집어넣습니다. 블록 N이 적용될 때, [H+1, N] 범위에 있는 블록에 대해서만 비가역성에 대한 투표를 받게 됩니다.
겹치는 범위에 있는 블록에 서명하는 모든 프로듀서는 비잔틴(배반자)으로 간주되며 잘못된 행동을 드러내는 암호 증명을 생성하게 됩니다.
이 정보를 이용하면, 임의의 블록 높이의 동일한 블록 높이를 가진 두 개의 서로 다른 블록이 2/3 + 1 만큼의 투표를 얻기 위해서는 최소 1/3의 블록 프로듀서가 상충하는 범위의 블록에 서명했다는 게 틀림없음을 증명하는 간단한 증거를 생성할 수 있습니다. 이런 상황은, 각각 1/3 크기의 선량한 프로듀서 두 그룹이 두 개의 다른(alternative) 블록을 생성하게 되는 어쩔 수 없는(honest) 네트워크 분할이 발생했고 나쁜 1/3으로 구성된 그룹이 양쪽 포크 모두에 서명하는 경우입니다. 실제로 접속이 잘 살아있는 네트워크 환경에서 비가역 상태로 간주되는 두 개의 다른 블록을 만들기 위해선 2/3 +1 만큼의 악의적인 프로듀서가 있어야 합니다.
이런 규칙 아래에서 프로듀서가 비잔틴(배반 행위)를 드러내는 서명을 하는 경우는 이제 두 가지 경우가 존재합니다.
- 직접 또는 간접적으로, 동일한 블록 번호를 가진 두 개의 블록에 서명하는 경우
- 동일한 블록 시간에 생성된 두 개의 블록에 서명하는 경우
기본 소프트웨어를 실행하는 정직한 노드는 이러한 일을 절대로 하지 않을 것입니다. 그러므로 나쁜 관계자 모두를 실패한 시도까지 처벌하기가 쉽습니다.
이 문제의 해결책은 블록원 팀의 몇몇 다른 멤버들과 Bart, Arhag과 제(댄 라리머)가 협업을 통해서 찾아냈습니다.
- 원문 : EOSIO/eos#2718
- 원문 작성자 : Daniel Larimer (bytemaster)
- 원문 작성 시점 : 한국표준시 2018년 5월 3일 12시 35분