DPOS BFT — 파이프라인 비잔틴 장애 허용

Orchid Kim
Orchid Kim in EOSYS
May 17, 2018 · 12 min read

Translated Contents

원문: DPOS BFT — Pipelined Byzantine Fault Tolerance

*역자의 말

어제 댄 라리머가 발표한 파이프라인 BFT-DPOS는 어떻게 빠른 finality를 달성할 것인지에 관해 이야기합니다. 캐스퍼, 텐더민트 등의 다른 합의 알고리즘과 DPOS-BFT를 비교하기도 하고, 유저 경험을 위해 EOSIO를 사용하는 유저가 어떤 선택을 할 수 있는지를 설명합니다. 금일 라리머는 트위터에서

“고마워요, @비탈릭, 저희가 EOSIO의 BFT finality 알고리즘을 개선할 수 있게 도와줘서 말이에요. 우리는 이미 EOSIO에 개선사항들을 적용했어요. 저의 파이프라인 DPOS BFT 합의에 관한 글을 확인해 보세요. (링크)”

라고 밝혔습니다. 과연 댄 라리머가 어떻게 합의 알고리즘을 개선했다는 것인지 다음 글에서 함께 보시죠!

우리가 알고 있는 두 종류의 일반적인 블록체인 합의 시스템이 있습니다. 하나는 정해진 그룹의 validator가 100%의 확률로 finality**를 결정하는(produce) 방법이고, 두 번째는 100%를 보장하지는 않지만 finality를 높은 확률로 보장하는 방법입니다.

(*역자 주: Finality는 ‘완결성’, ‘최종성’ 등으로 번역될 수 있으나 글의 주제인 만큼 원문 그대로 두었습니다. Finality는 간단히 말해 블록이 만들어진 후 최종적으로 거래가 완료되는 것을 의미합니다.)

블록체인 1세대의 합의 알고리즘**은 시간이 지남에 따라 finality 확률이 높아지도록 설계됐습니다. 이론적으로는 누군가가 돈을 많이 써서 제네시스까지 갈 수 있는 ‘긴’ 비트코인 블록체인을 따로(alternative) 마이닝할 수 있습니다.

**블록체인 1세대의 합의 알고리즘: Proof of Work, Proof of Stake, and BitShares’ Delegated Proof of Stake

최근의 합의 알고리즘들(HashGraph, Casper, Tendermint, DPOS BFT)은 역사 깊은 Paxos의 원리와 관련된 합의 알고리즘을 차용했습니다. 이런 모델들은 어떤 네트워크 조건에서든 참여자의 2/3가 정직하다면 확실한 finality를 이룰 수 있습니다.

객관적이고 확실한 100%의 finality는 블록체인 간 커뮤니케이션(inter-blockchain communication)을 지원하려는 체인이라면 필수적으로 갖추어야 할 중요한 요소입니다. 100%의 finality 가 보장되지 않는다면, 만약 한 체인이 복귀(reversion)될 경우 다른 연결된 체인들에 돌이킬 수 없는 막대한 파장을 일으킬 것입니다.

최근의 프로토콜 초록(abstract)들은 다음과 같은 내용을 포함합니다:

  1. 블록 제안(Propose block)

2. 모든 참여자가 블록을 인정함(pre-commitment)

3. 2/3 이상이 pre-commitment를 보내면 모든 참여자가 승인함(commitment)

4. 노드의 2/3+ 커밋을 받으면 블록은 확정(final) 됨

5. ⅓ 이상이 악의적일 경우와 악의적 행위의 증거가 모두에게 공개되는 경우, 이렇게 두 가지 경우가 발생하지 않는다면 finality를 위한 만장일치가 보장됨.

Abstract BFT Life Cycle (Image from the original article)

각기 다른 합의 프로토콜의 차이는 다음의 사항들에서 발생합니다:

  1. 언제, 누가 블록을 제안하는지 결정하는 부분

2. commitment가 어떻게 로깅되는지, 전달되는지 결정하는 부분

3. 비잔틴 행동이 어떻게 문서화되는지

4. 비잔틴 행동에 대한 처벌

이런 차이는 정치적이며 본질적으로 기술적입니다. 정치적 차이의 예시는 다음과 같습니다:

  1. DPOS는 제안자나 검증인 들을 스테이크를 통해 선출함

2. 캐스퍼(Casper)는 누가, 언제 제안을 할지 그리고 검증인 결정을 위한 스테이크 웨이트(bonded-stake-weight)를 결정하기 위해 작업 증명 방식에 의존함

3. DPOS는 객관적인, 주관적인 악의적 행동을 투표로 아웃시키는 방법으로 처벌함

4. 캐스퍼는 객관적으로 알 수 있는 악의적 행동만 bond slashing을 통해 처벌

정상 조건에서, 정치적 차이는 합의 알고리즘에 의존해 트랜잭션을 주문하고 finalize 하는 유저에게 매일매일의 영향을 주진 않습니다. 악의적 행동의 역치는 매우 높고, 패널티 또한 높아서 실리적인 이유로 일어나진 않을 것이기 때문입니다.

프로토콜의 기술적인 차이는 현실의 유저 경험에 영향을 줍니다. 그 예로 finality까지 걸리는 시간, finality의 정도, 대역폭(bandwidth), 그리고 증거 생성(proof generation)과 검증 오버헤드(validation overhead)입니다.

가장 간단한 알고리즘은 다음 블록이 처리되기 전에 한 블록의 합의가 완료되는 것입니다. 이 과정에는 모든 참여자가 다른 참여자에게 블록당 두 메시지를 보내는 것이 포함됩니다. 글로벌 네트워크에서는 빛의 속도 때문에 노드가 제안(proposal)을 보내고 2/3 이상의 커밋 메시지를 받는 데까지 걸리는 시간에 1초 정도의 지연을 발생시킵니다. 제가 관찰했던 모든 네트워크들은 대부분 2~3초의 지연 시간을 두었었습니다. 이런 단순한 프로토콜에는 또한 ‘타이머’라는 개념이 포함되는데, 이것은 현 제안의 타당성이 검증되지 못할 경우 새로운 제안을 제시하는 것입니다. 이 타이머는 예상되는 컨펌 시간보다 대부분 길죠.

캐스퍼와 같은 프로토콜은 오버헤드를 줄이기 위해 단기 합의를 위한 작업 증명 방식을 활용하고 finality가 100번째 블록씩 일어나도록 합니다(체크포인트). 즉, 캐스퍼 기반의 체인은 finality가 20~30초 안에 일어나는 것이죠.

DPOS BFT Pipeline Consensus

EOSIO에 적용된 현대의 비잔틴 위임 지분 증명은 프로포절과 선 커밋, 그리고 커밋 메시지를 전달하기 위해 파이프라인 접근을 합니다. 이는 정상적인 조건에서 각 블록이 한 블록의 finality를 결정하고 타임 슬롯별 하나의 프로포절을 요구함으로써 해결됩니다. 즉, 비잔틴 위임 지분 증명의 finality에 드는 비용(사인 증명, 해쉬 계산, 네트워크 밴드위스 등)은 예전의 DPOS 시스템(비트코인과 이더리움과 비슷하게 최종 consistency와 긴 체인 룰에 의존하던)의 비용과 같습니다.

오직 DPOS BFT만이 효율적으로 검증자(validator)를 무한으로 둘 수 있습니다(수가 늘어나면 더 지연되는 방향으로). 다른 프로토콜들은 finality를 위한 자원 요구사항이 참여자의 수가 O(2N) 명으로 늘어나죠. 각 블록 혹은 체크포인트마다 모두가 최소한 두 명과 얘기해야 하니까요. 더 많은 참여자가 개입될수록 더 많은 서명들(signatures)과 네트워크 오버헤드 그리고 저장공간이 필요해지고 그렇게 되면 지연시간은 늘어납니다.

DPOS BFT를 적용한 21개의 프로듀서와 2초의 블록 간격을 가정해봅시다. finality는 1분 후에 이뤄지지만 새로운 블록은 2초마다 finality에 도달합니다. 이는 비잔틴 컨펌을 파이프 연결(pipelining)함으로써 달성될 수 있습니다. EOSIO와 같은 플랫폼은 블록을 0.5초마다 생산하지만 제안자(proposer)들을 12블록마다 교체합니다. 이는 비잔틴 finality가 순수한 BFT DPOS 블록 컨펌 방식으로 따지자면 3분마다 일어난다는 뜻이죠. 결론적으로는 개별 블록으로 봤을 때 캐스퍼보다 10배가 빠르게 되고, 새로운 블록은 (캐스퍼가 30분인 것에 비해) 2초의 finality타임에 도달합니다.

DPOS BFT w/ optional Low-Latency Confirmation (Image from the original article)

DPOS 하이브리드 파이프라인 / 리얼타임 비잔틴 장애 허용

3분의 finality가 바람직하지 않은 경우와 특정 블록의 라이트 클라이언트 DPOS 증거가 너무 무겁게 되는 경우가 있습니다. 이런 경우, 블록체인은 BFT 선 커밋과 커밋 메시지를 기다리고 있는 블록에게 전달하기 위한 다른 디자인을 취할 수 있습니다. 이는 DPOS-BFT 체인의 finality 지연시간이 1~2초가 될 수 있도록 합니다 (추가적인 네트워크 오버헤드, 저장 요구사항, 그리고 CPU 사용에 따라 더 걸릴 수 있지만요). 텐더민트/코스모스와 같은 프로토콜과 다르게 동시에 ‘파이프라인 안에 있는’ 제안(proposal)이 여러 개가 있을 수 있습니다. 심지어 어떤 블록들은 네트워크 분리로 인해 ‘리얼타임’ 커밋을 받지 못할 수 있지만, 그럼에도 불구하고 결국에는 간접적으로 컨펌됩니다.

보안의 정도

블로그 포스트 혹은 SNS 보팅과 같은 앱에서 1초 안에 99.999%의 finality가 달성될 수 있음에도 100%의 finality를 기다린다는 것은 지나치다는 것을 오랫동안 알아 왔습니다. 캐스퍼와 같은 프로토콜은 다음 체크포인트를 기다리는 것이 과도할 경우 작업 증명 컨펌을 사용하는 옵션을 줍니다.

몇몇 풀노드들은 블록체인 스테이트만 요구할 경우 BFT 선 커밋과 커밋 메시지의 오버헤드의 처리를 그다지 신경 쓰지 않습니다. 블록 프로듀서(제안자/검증인)들이 실시간 합의에 도달할 수 있고 그들의 블록 헤더가 2분 후에 결국 BFT합의에 이른다는 것을 아는 것만으로 충분합니다.

각 합의 알고리즘은 유저를 위해 특정한 선택을 하고 각기 다른 방법으로 덜 안전한 변형을 둡니다. 텐더민트/코스모스/리플은 full finality 말고는 유저에게 선택지를 주지 않습니다. 이더리움은 작업 증명 방식으로 돌아갈 수 있도록 하고, DPOS-BFT는 원래의 DPOS개런티로 돌아갈 수 있도록 여지를 둡니다.

슬래싱 조건이 있는 캐스퍼 체크포인트 알고리즘에 레이어를 추가해서 DPOS BFT 블록 제안 시스템 위에 둘 수 있습니다. 이런 접근 방법은 선한 행동에 정치적이고 경제적인 인센티브를 부여한 여러 개별 검증자 셋을 만들 수 있습니다.

유저 경험

비잔틴 위임 지분 증명 방식은 최악의 상황에서 보통(no-worse)을 유지하면서 정상 케이스를 최적화합니다. 정상적인 상황에서 선출된 블록 프로듀서들은 법적 책임을 지며 매우 믿음직한 노드를 가진 신뢰받는 집단일 것입니다. 만들어진 블록이 finality에 도달할 확률은 99.999%인데, 이는 보통 유저가 1초 내에 거의 확정적인 finality를 달성할 수 있다는 것입니다. 이 정도라면 일상적인 금융 거래를 하기에 충분합니다. 자동차를 구매하는 것과 같은 큰 규모의 거래일 경우에는, 유저에게 확정적인 finality를 위해 몇 초를 기다리도록 요구하면 됩니다.

다른 프로토콜은 유저에 선택권을 주지 않지만, 위의 경우에 각 유저는 오버헤드와 딜레이를 얼마나 발생시킬지, 그리고 블록체인 간 통신을 위해 얼마나 큰 증거(proofs)를 요구할지를 결정할 수 있습니다.

결론

1980년대에 소개된 비잔틴 합의 원칙을 따르는 현대의 모든 합의 알고리즘은 안전하고 최종적인 state를 이룰 수 있습니다 (최악의 경우인 1/3의 비잔틴 참여자로 분리된 네트워크 상황을 포함하여). 오직 DPOS BFT와 EOSIO만이 네트워크 분리 없이, 100%의 정직한 노드일 경우 99.999%로 (finality를) 최적화할 수 있습니다. DPOS BFT는 이렇게 다른 프로토콜들이 제공하는 ‘안전에 대한 보장’을 포기하지 않고 성능을 최적화할 수 있습니다.

면책조항: 블록원(block.one)은 소프트웨어 기업이며 EOS.IO 소프트웨어를 무료 오픈소스 소프트웨어로 제작합니다. 이 소프트웨어는, 특기할 만한 점으로, 이 소프트웨어를 도입하는 사용자가 다양한 기능을 갖춘 분산 애플리케이션 또는 블록체인을 시작할 수 있도록 합니다. 자세한 내용은 다음 사이트를 방문하십시오. https://github.com/eosio 블록원은 채택하거나 구현할 수있는 EOS.IO 플랫폼의 모든 버전에서 블록 프로듀서가가 되려는 사람에게는 경제적 지원을 제공하지 않습니다.

블록원은 EOS.IO 소프트웨어를 기반으로 하는 퍼블륵 블록체인을 론칭하지 않습니다. 자신들이 선택한 기능 및/또는 자신들이 선택한 서비스를 제공하도록, 자신들이 선택한 형태로 EOS.IO를 채택하며 구현하려는 제 3자, 커뮤니티 및/또는 블록 프로듀서가 되길 원하는 주체들의 단독 책임일 것입니다. 블록원은 그러한 기능을 채택하여 구현하거나 그런 서비스를 제공하거나 EOS.IO가 어떤 방식으로든 채택되고 구현된다는 것을 보증하지 않습니다.

이 문서는 블록원의 비전을 보여 주며 어떠한 보증도 아닙니다. 우리가 그 비전을 실현하도록 노력할 것이지만, 모든 측면이 모든 면에서 블록원의 단독 재량 하에 변경될 수 있습니다. 우리는 블록원의 비즈니스 전략, 계획, 전망, 개발 및 목표에 관한 진술과 같은 역사적 사실에 대한 진술 이외에 이 문서의 모든 진술을 포함하는 이 문서를 “미래 예측 진술”이라고 부릅니다. 이 진술은 예측일 뿐이며 미래의 사건에 대한 블록원의 현재의 믿음과 기대치를 반영하고 가정에 근거하며 언제든지 위험, 불확실성 및 변경의 영향을 받습니다. 우리는 급변하는 환경에서 사업을 운영합니다. 새로운 위험이 수시로 발생합니다. 이러한 위험과 불확실성을 감안할 때 이러한 미래 예측 진술에 의존하지 않도록 주의해야합니다. 실제 결과, 실적 또는 이벤트는 미래 예측 진술에 포함된 내용과 실질적으로 다를 수 있습니다. 실제 결과, 실적 또는 이벤트가 미래 예측 진술과 실질적으로 다른 원인이 될 수 있는 요인에는 시장 변동성, 자본, 재원 및 인력의 지속적인 가용성; 제품 수용; 어떤 새로운 제품이나 기술의 상업적 성공; 경쟁; 정부 규제 및 법률; 그리고 일반적인 경제, 시장 또는 사업 조건이 포함되며 이에 제한되지 않습니다. 블록원이 만든 모든 미래 예측 진술은 그것이 작성된 날짜에 대해서만 말하고 블록원은 새로운 정보, 후속 사건 또는 기타의 사건이건 간에 미래 예측 진술을 업데이트하거나 변경할 의무가 없으며 분명히 부인할 의무가 없습니다.

여기에있는 진술은 기술, 재무, 투자, 법률 또는 기타 조언을 구성하지 않으며 특정 상황이나 구현에 적용되지 않습니다. 이 문서에 포함된 내용을 구현하거나 활용하기 전에 해당 분야의 전문가에게 문의하십시오.

여기에서 표현된 아이디어와 정보는 전적으로 저자 개인의 것이며 블록원 또는 블록원 직원의 입장과 견해와 조언을 필연적으로 반영한 것은 아닙니다.

EOSYS

Founding Block Producer of EOS Mainnet in Chain Partners

Orchid Kim

Written by

Naeun Kim, Blockchain BD, EOS evangelist, Chatbot/VUI, M.S. in Cognitive Science, and Writer

EOSYS

EOSYS

Founding Block Producer of EOS Mainnet in Chain Partners