Polkadot 합의 파트 2: GRANDPA
Polkadot Blog의 Polkadot Consensus Part 2: GRANDPA 번역입니다. 2019년 12월 18일 Joe Petrowski에 의해 작성된 글이며, Polkadot 팀에 번역 허가를 받았습니다.
이번 글을 폴카닷 합의 시리즈 파트 2입니다. 도입은 파트 1을 참고하세요.
시리즈 도입에서, 컴퓨터 네트워크의 세 가지 질문은 합의 알고리즘으로 답변할 수 있음을 설명하였습니다. GRANDPA는 두 번째 질문에 대한 답변입니다.
- 다음 상태 변경에 대한 제안은 누가하게 됩니까?
- 어떤 변경 셋을 완결로 볼 것입니까?
- 누군가 규칙을 어기면 어떻게 됩니까?
GRANDPA는 폴카닷의 완결 장치 (finality gadget)입니다. 이 장치의 목적은 캐노니컬 체인 (canonical chain)을 결정론적으로 확정하는 것입니다. 즉, GRANDPA는 어떤 변경 상태를 완결로 볼 것인지 결정합니다. GRANDPA의 검증인은 직접 블록을 생성하지 않으며, 대신 블록 생성 모듈 (파트 3에서 논의)에서 블록을 가져오게 됩니다.
블록 생성과 안전¹을 분리시키는 것에 대한 이점 중 하나는 — 일반적으로 공학적으로 우수하다는 것을 제외하고 — GRANDPA가 블록에 대해 많은 제약을 두지 않게 된다는 것입니다. GRANDPA는, 블록 생성 시스템이 GRANDPA의 포크 선택 규칙에 따라 확정적 보안을 가질 것과 블록 헤더가 부모 블록를 가르키는 포인터를 포함하고 있을 것을 요구합니다. 마지막으로 라이트 클라이언트가 체인을 따르고 있다는 것을 보장할 것이 있습니다.
GRANDPA 프로토콜
GRANDPA는 검증인이 블록이 아닌 체인에 투표한다는 면에서 다른 BFT (Byzantine fault-tolerant) 블록체인 알고리즘과 다릅니다. 프로토콜은 투표를 과도적으로 적용하여 GRANDPA 알고리즘으로 충분한 표를 얻은, 완결된 것으로 간주되는 가장 높은 블록 번호를 찾습니다. 이 과정을 통해 여러 블록을 한 라운드에 완결할 수 있습니다.
여러 블록을 한 라운드에 완결한다는 것은 완결을 방해하던 병목을 제거하였다는 측면에서 의미가 큽니다. GRANDPA는 다른 PBFT 파생 모델과 같이 O(n²) 복잡도를 갖습니다. 즉, 노드 수를 두 배로 늘리면 보내야하는 메시지 수는 4배가 되는 것입니다. 완결 프로세스가 블록 생성의 일부인 합의 시스템에서는 생성된 하나의 블록마다 이러한 메시지들을 전송해야 합니다. 블록 생성을 다른 모듈에서 분리함으로써 좀 더 효율적인 방법 (BABE에서 O(n))으로 블록을 생성할 수 있고 한 라운드에 여러 블록을 함께 완결시킬 수 있습니다.
예시로 쿠사마 노드의 로그 메시지를 살펴보겠습니다.
Idle (24 peers), best: #664257 (0x706c…76b7), finalized #664253 (0xe4ab…4d2a)
Imported #664258 (0xee71…6321)
Idle (24 peers), best: #664258 (0xee71…6321), finalized #664256 (0x809a…a5d8)한 라운드에서 GRANDPA는 세 개의 블록 (664,254에서 664,256까지) 을 완결하였습니다.
위 로그 메시지는 GRANDPA가 어떻게 여러 블록을 한 라운드에 완료하는지 그 방법을 예시적으로 보여줍니다. 왼쪽의 어두운 회색 블록은 이전에 완결된 것이며, 우측의 회색 점이 나타내는 검증인은 새로운 라운드에 투표를 전송합니다. 세 블록이 다수의 지지를 받아 완결되었습니다.
GRANDPA 라운드
투표자는 새로운 블록을 완결하기 위하여 다음을 수행합니다.
- “primary”로 지정된 노드는 이전 라운드에서 완결될 수 있다고 판단되는 가장 높은 블록을 브로드캐스트합니다.
- 네트워크 지연 후, 각 검증인은 완결되어야 한다고 생각하는 가장 높은 블록에 대한 “pre-vote”를 브로드캐스트합니다. 검증인의 대다수가 정직하다면, 블록은 primary가 브로드캐스트한 체인을 더 길게 확장합니다. 이 새 체인은 마지막으로 완결된 체인보다 여러 블록 더 길 수 있습니다.
- 각 검증인은 pre-vote 셋에 의해 완결할 수 있는 가장 높은 블록을 계산합니다. pre-vote 셋이 마지막으로 완결된 체인을 확장하는 경우, 각 검증인은 체인에 “pre-commit”을 전파합니다.
- 각 검증인은 새로 완결될 체인의 커밋 메시지를 형성하기에 충분한 pre-commit을 수신할 때까지 기다립니다.
다른 비잔틴 장애 허용 알고리즘 (PBFT와 Hotstuff)과의 미묘하지만 중대한 차이점은 임계 경로 변경이 없다는 것입니다. primary는 각 라운드마다 변경되지만, 이 변경은 비동기 네트워크에서 새로운 라운드를 시작하기 위한 것에 불과합니다. 부분 동기화 네트워크에서는 primary를 할당하지 않더라도 프로토콜은 항상 진행될 수 있습니다.
프로토콜의 단계는 검증인의 pre-vote 또는 pre-commit의 3분의 2 이상이 있을 때 완료할 수 있습니다. 결정론적 완결성을 갖기 위해서는 검증인의 수를 제한해야 합니다. 이는 무제한의 검증인 집합을 가질 수 있는 확률론적 완결성 체인과는 다릅니다. 투표자 집합을 선택하는 방법은 GRANDPA 프로토콜 외부에서 정의됩니다(파트 4 참조).
GRANDPA는 차등 투표를 지원합니다. 예를 들어 더 많은 위임을 받은 검증인이 더 많은 표를 행사하는 방식의 GRANDPA를 체인에 구현할 수 있습니다. 하지만 폴카닷에서는 모든 검증인이 하나의 동등한 한 표를 행사합니다. 이러한 가중치 결정 방식은 네트워크 상의 몇몇 노드들이 지분을 독점하는 것을 금하기 위한 것입니다.
책임있는 안전: 문제가 발생한 경우
GRANDPA는 안전 위반에 대한 검증인 책임을 묻는 책임있는 안전이라는 기능이 있습니다. 서로 다른 체인에 있는 두 블록이 완결되는 경우, 안전 위반이 발생합니다. 책임있는 안전은 사고 발생 후의 사후 조사와 유사합니다.
그렇다면 어떻게 두 개의 상충되는 체인이 완결될 수 있을까요? BFT 시스템은 항상 감내 가능한 결함 검증인의 수가 전체 검증인의 일부—GRANDPA는 전체의 1/3 — 라는 필요 조건을 기반으로 합니다. 두 상충하는 체인이 완결되기 위해서는 검증인 집합이 이 필요 조건을 충족하는데 실패해야 합니다; 적어도 검증인의 1/3이 이 두 체인 모두에게 투표해야합니다.
이 예제에는 10명의 검증인이 있으며, 시스템이 허용할 수 있는 최대 결함 검증인 수는 3입니다(f = (10–1) / 3). 4명의 결함 검증인 (빨강)과 네트워크 파티션으로 인해 각 정직한 검증인 그룹 (파랑)은 서로 다른 블록이 완결되었다고 판단할 것입니다.
두 상충하는 체인에 투표하는 것을 모호함 (equivocating)이라고 부릅니다. 이 모호함은 BFT 시스템에서 보편적으로 인식되는 문제입니다. GRANDPA는 모호함을 탐지할 수 있습니다.
모호함을 탐지한 경우, 다음 블록을 완결하기 위한 투표 시점에 블록 완결이 정상적으로 처리되지 않은 원인을 노드에게 질의합니다. 정직한 검증인은 블록에 대한 투표, 두 번째 라운드에서 pre-vote나 pre-commit으로 이에 응답해야 합니다.
그 다음 두 번째 질의를 진행합니다: 첫 번째 라운드의 pre-vote는 어떤 내용이었습니까? 이때 다른 검증인들에 대한 보고와 함께, 피어로부터 받은 모든 표를 공개하라고 요구합니다. 이 정보를 바탕으로 두 상충되는 체인에 투표한 검증인들을 찾아낼 수 있습니다. 상충된 체인 모두에 투표한 검증인들은 무거운 처벌을 받게 됩니다. 그리고 이 문제는 체인 로직의 흐름상 발생할 수 있는 문제일 뿐 합의 알고리즘 자체의 문제는 아닙니다.
안전 결함이 발생하면, 네트워크는 상충하는 체인 중 어떤 체인을 완결로 볼 것인지 선택하는 하드 포크를 수행합니다. 책임있는 안전을 통해 폴카닷은 체인을 공격한 검증인이 처벌받을 것이며, 검증인 그룹에서 제외된다는 사실을 보장받을 수 있습니다.
GRANDPA가 가용성과 유효성을 지원하는 방법
위 로그 메시지를 기억하십니까? 완결된 블록은 최선의 블록보다 두 블록 전에 있었습니다. 이러한 지연은 블록 생성과 완결 구분의 이점이라고 할 수 있습니다.
Idle (24 peers), best: #664258 (0xee71…6321), finalized #664256 (0x809a…a5d8)폴카닷을 포함한 상호 운영 시스템으로서의 블록체인은 데이터 가용성 문제를 갖게 됩니다. 한 콜레이터가 검증인에 블록을 제출하였는데, 다른 패러체인 (parachain)의 콜레이터는 그 블록을 본 적이 없다고 상상해보십시오. 블록을 제출한 콜레이터가 오프라인 상태라면 어떤 일이 벌어질까요? 검증인은 어떤 패러체인 콜레이터든 해당 블록을 요청할 수 있도록 일정 기간 동안 완전한 블록을 저장할 책임이 있습니다.
검증인은 블록에 투표하기 전 블록을 실행해야 합니다. 그리고 우리는 실제로 검증인들이 그렇게 하는지 확인하고 싶습니다. 폴카닷의 피셔맨 (fishermen)노드는 블록을 실행하고 검증인의 잘못된 행동을 보고합니다. 잘못된 행동의 예시로는 유효하지 않은 패러체인 블록이 릴레이 체인에 포함되도록 제안하는 행위 등이 해당됩니다.
유효하지 않은 블록이 완결되거나 콜레이터가 재현할 수 없는 블록이 완결되는 상황은 바람직하지 않습니다. 체인의 끝 몇 블록 전에 완결되도록 유지함으로써 피셔맨이 블록 정합성을 검증하고 가용성에 대해 검증인에 도전할 수 있습니다.
이번 글에서 어떻게 캐노니컬 체인을 결정할 것인지 논의하였지만, 선택의 대상이 되는 이 체인들이 어디서, 어떻게 시작하였는지는 아직 이야기되지 않았습니다. 바로 그 부분에 관한 것이 BABE와 관련한 부분입니다. 시리즈의 파트 3에서 이야기하도록 하겠습니다.
[1] 완결된 블록이 물리 법칙 같은 방식으로 완결된 것이 아니기 때문에 “완결성”보다 “안전성”이라는 용어를 더 선호합니다. 다만 GRANDPA가 완결이라는 표현을 쓰기 때문에 완결되었다고 하는 것입니다. 나는 “완결”이라는 단어보다 합리적 기대를 포함한 단어인 “안전”을 훨씬 더 선호합니다. 예를 들어 우리는 항공 여행이 안전하다고 생각합니다. 하지만 때때로 항공기가 추락한다는 사실을 알고 있습니다. 그리고 항공기 추락 시, 그에 대한 조사 프로세스와 특정 당사자에게 책임을 물을 수 있는 법적 수단이 존재합니다.
디사이퍼(DECIPHER)는 “건강한 블록체인 생태계 조성에 기여한다” 라는 미션 아래 블록체인에 대해 연구하고 이를 실용적으로 응용하는 서울대 블록체인 연구 학회입니다. 2018년 3월에 처음 조직 되어 현재까지 블록체인 기술을 다방면에서 연구하고 산업계에 응용하고 있는 100명 이상의 회원들을 배출해왔습니다. 다양한 팀별 연구활동과 프로젝트, 컨퍼런스 개최, 서울대학교 블록체인 강의 개설, 유수 기업들과의 산학협력과 파트너십 체결을 해오며 국내 최고의 블록체인 학회로 자리 잡았습니다.
