DPOS 합의 알고리즘 - 백서에서 누락된 부분

안녕하세요 tmkor입니다. 이 글은 @dan이 쓴 DPOS Consensus Algorithm - The Missing White Paper을 번역한 글입니다. 개인적으로 아직 100% 파악이 된 내용이 아니라, 오역이 있을 수 있습니다. 따끔한 지적 부탁드리겠습니다!

백서에서 누락된 지분 위임 증명(delegated proof of stake) 줄여서 DPOS에 대하여 자세히 살펴봅시다. 이 글은 DPOS의 동작 원리와 안정성에 대한 이해를 목표로 합니다. 초기 DPOS에 대한 설명은 bitshares.orf에서 확인 가능합니다만, 실제 합의 과정에서 다루지 않는 부분에 대한 설명이 포함되어 있습니다.

모든 블록체인은 기본적으로 트랜잭션으로 작동되는 결정 상태 머신(deterministic state machine)입니다. 합의 알고리즘은 1) 트랜잭션의 순서를 결정, 2) 비정상적 트랜잭션을 필터링합니다. 동일한 트랜잭션 순서를 만드는 다양한 합의 알고리즘이 존재하지만, DPOS는 수년간 다수의 블록체인에서 운용될 정도로 안정적이며 보안이 뛰어날 뿐더러 효율적으로 동작합니다.

다른 합의 알고리즘과 마찬가지로, 블록 생산자들에 대한 검열은 있어서는 안됩니다. 모든 블록들은 오픈 소스로 만들어진 결정 상태 머신의 로직으로 검증되어야 합니다.

DPOS 알고리즘 요약

DPOS 알고리즘은 2단계로 이루어집니다. 첫 번째 단계는 블록 생산자 그룹 뽑기이고, 두 번째 단계는 블록 생산 일정 정하기입니다. 네트워크의 문제가 발생할 경우 자본가들은 큰 손실을 입게 되므로, 블록 생산자들을 뽑는 과정에서 자본가들이 결정권을 가지도록 해야합니다. 블록 생산자를 뽑는 과정은 분단위로 이루어지는 합의 과정에 비하면 큰 영향을 주지 않습니다. 그러므로, 이번 글은 블록 생산자들이 뽑힌 다음에 어떻게 합의에 이루는지에 초점을 맞추려 합니다.

알고리즘의 이해를 위해 3명의 블록 생산자(A,B,C)가 있다고 가정해 봅시다. 합의를 이루기 위해서는 정족수의 2/3 + 1명의 동의가 필요하므로, 예제 모형에서 C가 캐스팅 보트 역할을 합니다. 실제론 21명 혹은 그 이상으로 구성됩니다. 작업증명(proof of work)과 마찬가지로, 일반적인 규칙은 가장 긴 체인이 이기는 겁니다. 정상적인 참가자라면 더 긴 체인이 존재하면 곧바로 더 긴 체인으로 갈아탑니다.

대부분의 네트워크 상황에서 DPOS가 어떻게 동작하는지 보여드리겠습니다. 이 예제들을 보면 DPOS가 안정적이고 깨트리기 힘든 것임을 이해하실 겁니다.

일반적인 상황

일반적인 상황에서 블록 생산자들은 3초마다 블록을 만듭니다. 모두 자기 차례를 잘 지킨다면 자연스레 가장 긴 체인에 블록을 붙일겁니다. 블록 생산자가 정해진 블록 생성 시간대가 아닌 다른 시간에 만들 경우 부적합 처리 됩니다.

소수 포크(minority fork)

최대 1/3의 노드들은 해킹되거나 비정상으로 작동할 수 있으며, 이 경우 소수 포크가 이루어집니다. 예제의 경우 소수 포크는 1개의 블록을 9초마다 생성하며, 다수 포크는 2개의 블록을 9초마다 생성합니다. 정상적인 2/3의 노드로 이루어진 다수 집합은 항상 긴 체인을 가질 것입니다.

단절된 소수 그룹에서 이중 블록 생산

소수 그룹은 원하는대로 포크를 만들 수 있습니다만, 만들어진 소수 포크는 다수 그룹보다 많은 블록을 가지지 못하고 항상 짧습니다.

네트워크 절단

노드들 간에 네트워크 연결이 끊어져서 블록이 공유되지 못한다면 어떠한 포크도 다수 포크가 될 수 없습니다. 이러한 경우 가장 긴 체인은 소수 체인 중 가장 큰 체인이 될 것입니다. 네트워크 연결이 되살아나면 작은 소수 포크들은 자연스레 가장 긴 체인으로 옮겨탈 것이고 모호한 합의 상태는 원상복구 될 것입니다.

3개의 포크가 있을 때 2개의 포크가 동일한 길이를 가질 수 있습니다. 이러한 경우 작은 길이의 포크를 가지고 있는 3등 블록 생산자가 네트워크에 복귀할 때 캐스팅 보트 역할을 합니다. 홀수의 블록 생산자가 있으므로 동점(tie) 상황은 오래갈 수 없습니다. 나중에 기회가 된다면 2개의 포크가 같은 수의 블록 생산자를 가지고 있더라도 서로 다른 길이로 늘어나서 결국엔 동점상황을 해소하게 되도록 순서를 랜덤하게 섞는 블록 생산자 셔플링 과정을 다루도록 하겠습니다.

연결된 소수 그룹에서 이중 블록 생산

이번 시나리오에서는 소수 생산자 B가 2개 이상의 대체 블록을 만듭니다. 다음 생산자 C는 B가 만든 여러개 중 하나를 선택하겠지요. C가 고른 블록은 가장 긴 체인이 될 것이며, B가 만든 다른 노드(예:B1)를 사용하는 노드들은 바로 갈아탈 것입니다. 소수로 이루어진 나쁜 생산자들이 대체 블록을 몇개나 만들어 네트워크에 뿌리던간에, 어떤 블록도 한 라운드 이상 긴 체인에 포함될 수 없습니다.

최후의 비가역(irreversible) 블록

네트워크가 절단된 시간동안 여러개의 포크가 제각기 길어지게 됩니다. 크게 보자면 가장 긴 체인이 승리합니다만, 블록체인을 이용하는 사용자(observer)들은 특정 블록이 가장 긴 체인에 속하는지 확신을 얻길 원합니다. 그럴때는 2/3 + 1명의 블록 생산자가 컨펌(confirmation)하는지 보면 확실해집니다.

아래의 그림에서 B 블록은 C와 A에 의해 컨펌되었습니다. 즉, 2/3 + 1의 컨펌을 얻은 것입니다. 2/3의 블록 생산자가 정상적인 경우, 어떠한 경우에도 다른 체인이 더 길어질 수는 없습니다.

이 규칙은 비트코인의 6블록 컨펌과 유사해보입니다. 몇몇 똑똑한 사람들은 두개의 노드가 서로 다른 비가역 블록에 붙는 상황을 만들어 낼 수도 있습니다. 이 특수한 경우는 통신 지연을 제어할 수 있어야 하며, 한번도 아니고 분단위 간격으로 두번 제어할 수 있어야 합니다. 만약에 이러한 일이 일어난다면, 가장 긴 체인을 선택하는 규칙을 적용하면 됩니다. 우리는 이러한 공격이 발생활 확률은 0에 수렴하며, 경제적인 여파도 걱정할 만큼 크지 않다고 생각합니다.

생산자 정족수가 부족한 경우

생산자의 정족수가 불분명한 경우 소수 포크에서 블록 생산이 계속 이루어질 수 있습니다. 블록 소유자들은 그들의 투표를 변경하는 트랜잭션을 포함시킬 수 있습니다. 변경된 투표는 새로운 생산자 집합을 뽑는데 사용되고 블록 생산자 참여율을 100%로 복구시킬 것입니다. 이러한 일이 일어날 경우 소수 체인은 100% 미만의 참여율로도 점차적으로 다른 체인들을 잡아먹을 수 있습니다.

이러한 기간동안 모든 블록체인 사용자들은 블록 생산자의 참여율이 67%가 될 때까지 네트워크 상태가 유동적임을 알고 있어야 합니다. 이러한 상황에서 트랜잭션을 발생하는 사람들은 6 컨펌 이전에 승인하는 것과 유사한 위험을 지게 됩니다. 또한 합의 알고리즘이 완전히 다른 포크로 정착할 아주 작은 가능성이 있습니다. 실제로 비트코인의 3 컨펌이전의 블록을 허용하는 것보다는 훨씬 안전합니다.

다수 생산자의 오염

만약에 다수 생산자가 오염되어 무수히 많은 포크를 생산한다면, 각가의 포크들은 모두 2/3 이상의 컨펌을 가지게 됩니다. 이 경우 마지막 비가역적 블록 알고리즘 대신 가장 긴 체인 알고리즘을 사용하게 됩니다. 가장 긴 체인은 소수의 정상적인 노드가 선택한 가장 큰 다수 포크가 될 것입니다. 이러한 행동은 이해관계자들이 블록 생산자를 투표로 교체할 것이기 때문에 오래가지 않습니다.

트랜잭션으로 지분 증명 : TaPos (Transaction as Proof of Stake)

사용자는 현재 블록체인 상태가 어느정도 믿을만 할때 트랜잭션에 서명하게 됩니다. 이러한 믿음은 직전 블록의 인지에 기반합니다. 만약에 가장 긴 체인에 대한 합의가 변경된다면, 믿음은 깨질 수 있으며 이 경우 서명자는 트랜잭션을 철회하게 됩니다.

TaPos에서 모든 트랜잭션은 직전 블록의 해시값을 가지고 있으며, 직전 블록이 체인 기록에서 사라지게 되면 부적합한 트랜잭션으로 처리됩니다. 고아(orphaned) 포크에서 서명한 모든 트랜잭션들은 부적합 처리 되며 메인 포크에 포함될 수 없습니다.

이 과정의 부가적인 효과로 장기간의 대체 체인을 만드는 공격에 대한 보안성을 얻게 됩니다. 모든 트랜잭션은 블록체인을 직접적으로 컨펌하게 됩니다. 시간이 지날수록 모든 블록들은 이해관계잘에 의해 컨펌되게 되며, 위조 체인이 복제할 수 없는 것이 됩니다.

결정론적 생산자 셔플링

모든 예제는 라운드-로빈 방식의 블록 생산자 스케쥴링이었습니다.실제로 블록 생산자들의 순서는 N 블록마다 섞입니다. (N은 생산자의 숫자 입니다.) 이 무작위화는 블록생산자 B가 A를 항상 무시할 수 없도록 하며, 동일한 생산자 수의 포크가 여러개 있을 경우 동점(tie) 상황이 깨지는 것을 보장합니다.

결론

위임 지분 증명 (DPOS)는 자연스레 발생하는 모든 네트워크 분절 상황에서 안정적으로 동작하며, 심지어 다수 생산자의 오염 상황에서도 안전합니다. 다른 경쟁 알고리즘과 달리, DPOS는 다수 생산자가 고장난 상태에서도 동작합니다. 커뮤니티는 고장난 생산자를 대체하는 투표를 진행하며 100% 참여 상태로 복구하게 됩니다. 제가 알기로 다른 합의 알고리즘은 이렇게 다양한 고장 환경에서 안정적이지 않습니다.

궁극적으로 DPOS는 노드들의 성능이 좋으면서 서로 다른 블록 생산자를 선출하는 알고리즘으로 강력한 보안성을 얻게됩니다. 투표 승인 과정은 50%의 투표권을 가진 개인이라 할지라도 혼자의 힘으로는 한명의 블록 생산자도 뽑을 수 없습니다. DPOS는 100%의 정직한 노드들이 안정적인 네트워크 연결을 가질 때 최적의 성능을 가지도록 디자인 되었습니다. 이러한 경우 99.9%의 확신을 가지는 트랜잭션의 컨펌은 평균 1.5초에 이루어지며, 우아하며 탐지 가능한 형태로 성능이 하락하고 쉽게 복구할 수 있습니다.

다른 합의 알고리즘들은 배신자 노드가 존재하며 네트워크가 안좋은 명목 상태를 위해 디자인 되었습니다. 결과적으로 낮은 성능, 높은 지연시간, 높은 통신 오버헤드와 33%의 노드가 고장날 때 완전히 중단되는 네트워크가 되었습니다.

3년간 BitShares와 1년간의 Steem의 운영으로 우리는 모든 네트워크 환경과 소프트웨어 버그를 경험하였습니다. DPOS는 이러한 환경에서 효과적으로 운영되었으며 어떠한 블록체인보다 많은 트랜잭션을 처리하면서 합의를 유지하는 능력을 보여주었습니다.