Polkadot 합의 파트 3: BABE
Polkadot Blog의 Polkadot Consensus Part 3: BABE 번역입니다. 2019년 12월 18일 Joe Petrowski에 의해 작성된 글이며, Polkadot 팀에 번역 허가를 받았습니다.
폴카닷 합의 시리즈 파트 3 입니다. 도입은 파트 1, GRANDPA에 관한 논의는 파트 2를 참조하세요.
BABE (Blind Assignment for Blockchain Extension)는 또 다른 지분 증명 프로토콜인 Ouroboros Praos에서 영감을 받은 블록 생성 엔진입니다. 확률적 완결성을 제공하기 때문에 단독으로 사용될 수 있지만, GRANDPA와 같은 완결 장치와 결합할 수도 있습니다.
BABE는 슬롯 기반의 알고리즘입니다. BABE는 시간을 epoch으로 나누고, epoch을 슬롯으로 다시 나눕니다. 폴카닷에서 각 슬롯은 목표 블록 타임인 6초가 됩니다. BABE는 각 슬롯마다 블록을 작성할 한 작성자 (또는 여러 작성자)를 선택합니다.
슬롯에 작성자를 할당하기 위한 방법 중 하나로 단순하게 교대로 순서를 할당하는 방식이 있습니다. 그러나 이와같은 라운드-로빈 방식은 다음 작성자를 알 수 있기 때문에 공격자가 작성자를 공격할 수 있게 됩니다. 그렇기 때문에 슬롯 작성자가 스스로 작성자임을 증명할 때까지 슬롯 작성자가 누구인지 모르는 것이 이상적일 것입니다.
각 슬롯은 primary와 secondary 작성자 (혹은 “슬롯 리더")를 가질 수 있습니다. primary 슬롯 리더는 무작위로 할당됩니다. 그러나 무작위로 할당되기 때문에 때때로 리더가 없는 슬롯이 생길 수도 있습니다. 일관된 블록 타임을 보장하기 위해, BABE는 secondary 슬롯 리더를 라운드-로빈 시스템을 이용하여 할당합니다.
Primary 슬롯 리더
primary 리더십은 VRF (Verifiable Random Function)를 기반으로 부여됩니다. 블록체인 난수를 놓고 다양한 의견들이 존재합니다. 이러한 의견들을 요약하면, 많은 애플리케이션이 난수 생성에 의존하지만 온체인 상에서 결정적이면서 증명 가능하여 모든 사람이 임의적 (난수 생성자에게 이익이 되도록 조작되지 않은)이라는 사실에 동의되는 무작위성은 찾기 어렵다는 것입니다.
VRF는 의사 난수가 올바른 방식으로 생성되었다는 증거와 함께 난수를 생성합니다. VRF는 개인키를 포함한 일부 변수 값을 입력 값으로 사용합니다. BABE의 VRF는 epoch 랜덤 시드 (사전에 모든 노드가 동의한), 슬롯 번호 및 작성자 개인키를 사용합니다. 두 노드가 동일한 개인키를 갖지 않기 때문에, 각 노드는 각 슬롯에 대한 고유한 의사 난수 값을 생성할 수 있습니다.
각 작성자는 epoch의 각 슬롯에 대한 VRF를 평가합니다. 출력이 합의된 임계값 미만인 슬롯에 대해 검증인은 해당 슬롯의 블록을 작성할 권리가 있습니다. 임의로 슬롯을 할당하는 프로세스로 인해 primary가 없는 슬롯이 있을 수 있으며, 여러 primary가 존재하는 슬롯이 있을 수 있습니다. 이는 어떻게 처리할 것인지 이후에 논의할 것입니다.
Secondary 슬롯 리더
빈 슬롯을 처리하기 위해서, BABE 라운드-로빈 폴백을 사용합니다. 모든 슬롯은 secondary 리더가 있습니다. 슬롯 시작시 아무도 자신이 primary라고 주장하지 않으면 secondary가 블록을 작성합니다. 이 폴백은 모든 슬롯이 항상 블록 작성자가 존재한다는 사실과 일관된 블록 타임을 보장합니다.
BABE와 GRANDPA의 만남
지금까지는 GRANDPA가 체인을 완결하고, BABE가 새로운 블록을 생성하였습니다. 한 슬롯에 여러 리더가 있을 수 있기 때문에 일부 BABE 체인에 포크가 발생할 수 있습니다.
확장에 최선인 체인을 선택하는 첫 번째 규칙은 간단합니다: BABE는 GRANDPA에 의해 완결된 체인으로 구축되어야 합니다. 이것이 GRANDPA를 사용하기 위한 필요조건 중 하나입니다.
GRANDPA를 사용하기 위한 두 번째 필요조건은 블록 생성 알고리즘이 “최선의” 체인을 선택하는 방법이 있어야 한다는 것입니다. 이 속성은 BABE가 확률적 완결성을 가질 수 있게 합니다. (그러므로 GRANDPA 없어도 작동이 가능합니다.)
BABE에서 최선의 체인은 단순하게 가장 많은 블록을 작성한 primary의 체인입니다.
BABE에서 포크는 일반적입니다. GRANDPA 글에서 이야기하였듯이, 블록 생성의 복잡도는 O(n)입니다. 즉, 작성자는 모든 이에게 블록을 브로드캐스트 해야하지만, 모든 이가 다시 모든 이에게 전송할 필요는 없습니다 (GRANDPA에서와 같이). 그렇기 때문에 모든 이들이 완결되지 않은 체인 (이미지의 노란 블록)에 대해 동일한 뷰를 갖는 것은 아닙니다.
이 시스템을 통해 효율적인 방법으로 블록을 생성하고, GRANDPA로 블록 셋을 완결할 수 있습니다.
누구의 시계를 따를까?
시간을 기준으로 슬롯을 할당하지만 시간에 대한 하나의 뷰를 갖고 있지 않다는 것은 문제가 될 수 있습니다. 모든 컴퓨터에는 자체적인 시계를 갖고 있습니다. 우리는 단일 실패점 때문에, 중앙 시간 서비스 (NTP 서버라 불리는)를 사용할 수도 없습니다. NTP 서버를 공격자는 서버를 공격하여 시계에 대한 접근을 차단시켜 버리거나 기능을 제어하여 다른 노드에 변조된 시간을 전달해버리는 보다 악의적인 행동을 할 수도 있습니다.
한 시나리오를 생각해봅시다.
나는 당신으로부터 “8:42:00 입니다”라는 메시지를 받았습니다. 내 시계는 8:42:03입니다. 이는 세 가지 중 하나로 상황을 설명할 수 있습니다.
1.시계는 싱크가 맞아 있으나, 당신의 메시지가 네트워크에서 전달되는데 3초가 걸렸을 수 있습니다.
2. 메시지가 전달되는데 실제로 1초가 걸렸습니다. 시계가 2초간 동기화되지 않았습니다.
3. 당신은 시계에 보이는대로 이야기하지 않고 거짓말하였습니다.
이제 내 시계가 8:41:59일 때 이 메시지를 받았다고 상상해봅시다. 당신이 시계에서 본대로 정직하게 이야기해준 것이라고 믿는다면, 시계가 동기화되지 않은 상태이며, 내 시계를 앞으로 맞춰야 한다는 것을 알게 됩니다. 하지만 네트워크 상에서 전달되는데 얼마나 시간을 걸렸는지 모르기 때문에, 정확히 얼마만큼 동기화되지 않았는지 알 수 없습니다.
BABE는 상대적 시간을 이용하여 개별 컴퓨터의 시계에 슬롯 번호를 할당합니다. 노드는 블록을 수신하면서 수신 시간과 블록과 관련된 슬롯 번호를 확인합니다. 그런 다음 블록 타임에 슬롯 번호들을 추가하여 미래 슬롯을 예측하고, 그 데이터의 중위값을 사용합니다. 검증인은 사전에 작성할 슬롯 번호를 알고 있으므로 이에 대해 들어오는 블록을 확인할 수 있습니다.
지금까지 체인이 어떻게 만들어지고 (BABE) 어떻게 완결되는지 (GRANDPA) 논의하였습니다. 우리가 해결해야할 다음 문제는 사람들이 어떻게 이 프로토콜을 올바른 방식으로 실행할 수 있을까하는 것입니다. 이 시리즈의 마지막 파트에서 런타임이 BABE와 GRANDPA를 실행할 때, 어떻게 인센티브를 부여하고 오류에 대해 처벌하는지 논의해보도록 하겠습니다.
디사이퍼(DECIPHER)는 “건강한 블록체인 생태계 조성에 기여한다” 라는 미션 아래 블록체인에 대해 연구하고 이를 실용적으로 응용하는 서울대 블록체인 연구 학회입니다. 2018년 3월에 처음 조직 되어 현재까지 블록체인 기술을 다방면에서 연구하고 산업계에 응용하고 있는 100명 이상의 회원들을 배출해왔습니다. 다양한 팀별 연구활동과 프로젝트, 컨퍼런스 개최, 서울대학교 블록체인 강의 개설, 유수 기업들과의 산학협력과 파트너십 체결을 해오며 국내 최고의 블록체인 학회로 자리 잡았습니다.
