LIB의 충돌에 따른 DPOS 합의 실패 수정사항 #2718
Translated Contents
원문: https://github.com/EOSIO/eos/issues/2718 (EOSIO Dawn 4.0 글의 합의 알고리즘 설명 링크의 글을 번역하였습니다.)
본 페이퍼는 DPOS 알고리즘의 개선사항을 설명하며, 다음의 개선사항들은 DPOS 3.0 프로토콜을 따르는 노드 네트워크가 합의에 실패할 확률을 낮추기 위함이다. 우리는 ‘합의에 실패하는 것 (falling of consensus)’을 ‘두 노드가 서로 다른 두 개의 블록이 ‘irreversible (비가역의/돌이킬 수 없는)’ 하다고 결론 내리는 것’이라고 정의한다.
배경(Background)
비트코인과 같은 작업 증명 방식의 블록체인은 ‘가장 긴 체인’룰에 의해 합의를 정의한다. 이 룰을 사용할 경우 그 어떤 블록도 비가역 승인을 받았다고 볼 수 없다 (역자 주: 비가역(irreversible)은 ‘번복할 수 없다’는 뜻이며 블록을 만들어 없앨 수 없는 상태가 된다는 것을 의미한다). 누구든 예전 블록에 더 긴 체인을 생산할 수 있으며 노드는 바뀔 것이다. 이로부터 우리는 비트코인의 높은 비가역 확률은 포크를 바꾸려는 노력의 경제적 비용에 기반한다고 결론 내릴 수 있다.
Bitshares는 Delegated Proof of Stake (위임 지분 증명 방식)를 소개했다. 이 알고리즘을 사용할 경우 지분(토큰)을 가진 ‘stakeholder’들은 블록 프로듀서를 선출한다. 블록 프로듀서들은 의사 무작위 방식으로 섞이고 절대적인 시간 슬롯에 배정되는데, 이 시간 동안 블록을 생산하거나 하지 않을 수 있다. 대부분의 프로듀서들이 블록을 만들어나갈 블록체인은 훨씬 적은 수의 프로듀서들이 만들어갈 블록체인에 비해 빠르게 길어질 것이다. 두 체인이 다른 스피드로 자라난다고 가정하면, 더 빠른 쪽이 결국 가장 긴 체인이 될 것이다. 따라서, 원래의 DPOS 알고리즘은 비트코인과 비슷하게, 블록이 체인에 더해지게 되면 다른 체인이 블록을 되돌릴 수 없도록 보장한다.
이런 DPOS 스케줄링 알고리즘의 특징은 관찰자(observer)에게 많은 정보를 제공한다는 것이다. 예를 들어, 관찰자는 사라지는 블록의 빈도에 기반하여 그들이 소수 체인에 올라갔다는 것을 감지할 수 있다. 21 프로듀서들과 함께, 한 노드가 그들이 소수 포크에 위치해 있을지도 모른다는 것을 단 두 개의 연속적으로 놓친 블록 (6초가 걸리는)으로 알 수 있다. 이는 유저에게 네트워크가 불안정하며 승인을 위해 더 오래 기다려야 한다는 것을 경고할 수 있다. 마찬가지로, 한 트랜잭션 후의 21블록 안에 어떤 프로듀서라도 블록을 놓치지 않았다면 해당 블록은 되돌릴 수 없다고 확신할 수 있다.
거의 없는 합의 실패 (DPOS 2.0)
DPOS 2.0에서는 마지막 비가역 블록의 개념을 소개했다. 이는 2/3+1의 블록 프로듀서들이 승인한 가장 최근의 블록이다. 이론적으로는 2/3+1 의 프로듀서가 한 체인에 한 블록을 승인한 경우 다른 포크가 있을 수 없다는 것이다.
그렇지만, 진취적인 사람들은 네트워크 분할이 네트워크를 두 체인으로 나누는 임의의 시나리오를 고안했다. 정상적인 경우 둘 중 하나의 체인이 다시 2/3+1의 프로듀서들과 연결될 때까지 한 체인 혹은 두 체인 모두 마지막 비가역 블록의 생성을 중지할 것이다. 연결이 재개될 경우 모든 것은 제자리를 찾으며, 모든 노드들은 진정한 하나의 체인에 수렴할 것이다. 즉 경쟁 조건(race condition)이 생성되는데, 이는 두 섭셋이 동시에 포크를 바꾸는 것을 의미하며 두 포크는 다른 블록에 대해 2/3+1 합의를 달성하게 된다. 이런 일이 벌어지게 되면 포크의 두 사이드에 있는 노드들은 동기화될 수 없게 되는데, 왜냐하면 어느 것도 마지막 비가역 블록을 풀 수 없기 때문이다. 이 경우에는 수동 개입이 요구된다.
이런 상황에서 하나 혹은 두 포크 모두 어느 포크든 2/3+1의 프로듀서의 합의를 얻지 못하면 비가역성을 이룰 수 없을 것이다. 소수(minority) 체인은 (다수 체인 대비) 1/2의 스피드로 성장할 수 있지만, 비가역 승인을 기다리는 노드들은 더 이상 짧은 체인의 거래를 받아들이지 않을 것이다.
어떤 서비스에 있어서 이러한 실패는 번복될 경우 손해가 되는 하나의 블록을 생성한다. 우리의 계산에 따르면, 이 시나리오가 일어날 확률은 6 컨펌을 필요로 하는 비트코인 블록을 되돌릴 확률보다 훨씬 낮다. 이는 3년 이상 큰 문제없이 돌아갔던 Bitshares나 Steem과 같은 실제 테스팅 결과에서 볼 수 있었다.
DPOS 3.0 + BFT (비잔틴 장애 허용)
EOSIO는 블록체인 간 통신 (Inter-blockchain communication; IBC)을 소개한다. IBC는 한 체인이 다른 체인에 효율적으로 거래의 완료(final)를 증명할 수 있게끔 한다. IBC에 있어서 ‘finality’는 아주 중요한데, 한 블록체인이 메시지를 승인할 경우 두 체인이 실수를 되돌리기가 쉽지 않으며 그것이 바람직하지도 않기 때문이다.
한 블록체인이 비트코인 예치금을 승인하려고 노력하는 상황을 상상해보자. 유저는 그가 참조하는 블록 위에 6개의 블록 헤더를 더한 모든 비트코인 블록 헤더를 제출할 것이다. 이 증거를 기반으로 블록체인은 돌이킬 수 없는(irreversible) 액션을 취한다. 이제 비트코인이 포크 하고 위의 여섯 블록을 번복한다면 어떨까? 이 블록체인은 번복이 불가능할 것이고 이전에 승인되었던 비트코인 거래를 거절(reject)할 것이다. 이런 상황은 수동 개입이나 하드 포크를 요할 것이다. 하드 포크나 인터벤션은 연결된 모든 체인에 영향을 미칠 것이다. 이는 실행 불가능한 선택지이다.
비잔틴이 아닌 상황에서(non-byzantine situations), 안전하고 믿을 수 있는 IBC를 보장하기 위해 DPOS3.0 + BFT에서는 마지막 비가역 블록(Last Irreversible Block; LIB)이 어떻게 계산되는지에 대한 수정사항을 추가한다. 이번 수정사항을 통해 우리는 두 노드가 LIB에 대해 다른 결론에 이르는 것이, 최소한 1/3의 블록 프로듀싱 노드가 의도적으로 악의를 가진 게 아닌 이상 불가능함을 증명했다. 나아가 우리는 한 노드의 악의적인 행위 또한 증명할 수 있다.
DPOS의 핵심은 생성되는 각각의 블록들이 이전 블록에 대한 표(vote)라는 것이다. 이 모델에 의하면 2/3 이상의 프로듀서가 특정 블록을 만들면 그 블록은 2/3 이상의 표가 있다. 이론적으로 이는 좋아 보이나, 비잔틴이 아닌 블록의 프로듀서가 다른 시간대에 다른 포크를 생성할 확률이 존재한다. 그들이 블록을 만들 때, 각 체인에 나타나는 블록 번호에 대해 간접적으로 상반된 표를 던질 수 있다.
프로듀서 A, B, C가 있는 네트워크를 가정해 보자. 네트워크에 장애가 생겨 두 블록 프로듀서가 짧은 시간 동안 커뮤니케이션을 하지 못하게 되는 상황에, 프로듀서 A는 블록 N을 T시간에 생성하고, B는 블록 N을 T+1시간에 생성한다. 이제 프로듀서 C가 블록 N+1을 T+2시간에 B의 블록 N(T+1시간)에 생성하여 연결을 끊는다고 생각해 보자. 이렇게 되면 A는 C의 블록 N+1을 알게 되고, A는 긴 포크로 이동할 것이다. 다음에 A는 B의 블록 N을 간접적으로 승인하는 블록을 만들게 되는데 이는 A의 이전 블록 N과 충돌하게 된다 (그림1).
DPOS 2.0 룰에 따르면, A의 블록 N이 A, B, C로부터 받은 표를 갖고, 2/3+1 컨펌에 따라 비가역이 된다 (그림 2).
DPOS 3.0에서는 A가 이전에 대체 블록 N을 컨펌했다는 사실을 알리도록 요구한다. 이 사실이 알려짐에 따라 네트워크는 B의 블록 N에 투표하였기 때문에 A의 블록을 카운트하지 않을 것이다. 이는 B의 블록 N만 두 표를 얻도록 할 것이고, 비가역 승인을 받기에 부족할 것이다.
DPOS 3.0에서는 B의 블록 N이 직접적인 비가역 승인을 절대 받지 못하는데, 2/3+1을 위해 A, B, C의 표를 모두 얻어야 하며 A는 대체 블록 N에 표를 던지기 때문이다. 대신, A가 N+2를 만들고 B가 N+3을 생성함에 따라 N+1 블록이 비가역이 될 것이다 (그림 4). 이는 블록 N+1이 2/3+1을 달성하기 위해 필요한 세 표를 주는 것이다. C의 블록 N+1이 비가역이 됨에 따라, B의 블록 N 또한 비가역이 될 것이다.
이 알고리즘을 실행하기 위해 각 블록 프로듀서들은 가장 높은 블록 번호 (H: 이전의 어떤 포크에서든 승인했던 블록 헤더)를 포함해야 한다. 블록 N이 [H+1, N] 범위에서만 적용된다면 비가역을 위한 표를 받을 수 있다.
겹치는 범위의 블록에 사인한 블록 프로듀서들은 비잔틴으로 간주되며, 그들의 부정행위에 따른 암호화된 증거를 생성해야 한다.
이 정보로 이제 우리는 단순한 증거를 만들었다. 한 블록 높이가 같은 높이의 다른 두 블록에 동시에 2/3+1 표를 얻으려면 적어도 1/3의 프로듀서들이 충돌하는 범위에 사인해야 한다는 것이다. 이는 만약 정직한 네트워크가 두 정상 그룹 (사이즈 1/3인) 이 두 대체 체인을 만들고 한 악의적 그룹이 1/3의 사인을 두 포크에 동시에 해야 가능한 일이다. 현실적으로, 좋은 연결 상태의 네트워크 하에서 두 다른 비가역 블록을 만들기 위해서는 2/3+1의 프로듀서가 악의적이어야 한다.
본 규칙에 따르면 프로듀서들이 비잔틴 상태에 사인할 수 있는 두 가지 경우가 있다:
두 블록을 같은 블록 번호로 간접적 혹은 직접적으로 사인하는 경우
같은 블록 시간으로 두 블록을 사인하는 경우
디폴트 소프트웨어를 돌리는 진실된 노드는 위의 행동을 하지 않을 것이다. 따라서, 실패한 시도들에 대해 모든 악의적 행위자를 사소하게 처벌하는 것이 가능하다.
크레딧
문제에 대한 솔루션은 Bart, Arhag, 저자(Dan Larimer)들이 B1팀의 다른 멤버들과 협동하여 발견하였습니다.
