이더리움 업그레이드: 합의의 기초 지식 (하)
글: Ben Edgington
번역: tiao
본문은 『합의의 기초 지식』 챕터의 후반부입니다. 전편은 『이더리움 업그레이드: 합의의 기초 지식』에서 확인할 수 있습니다.
포크 선택 규칙
우리가 보았듯이 네트워크 지연, 네트워크 중단, 메시지 수신 순서 오류, 악의적인 피어 노드 등의 다양한 이유로 인해 네트워크 상의 노드들은 결국 네트워크 상태에 대해 서로 다른 시각(view)를 가지게 됩니다. 궁극적으로는 네트워크상 모든 정확한 노드들이 역사에 대해 일관된 선형적 시각을 가지고 시스템 상태에 대한 공통된 견해를 형성하기를 희망합니다. 프로토콜의 포크 선택 규칙(fork choice rule)은 이러한 일치를 달성하기 위한 것입니다.
주어진 블록 트리와 각 노드의 네트워크에 대한 로컬 시각을 기반으로 하는 결정 기준이 있을 때, 포크 선택 규칙은 사용 가능한 모든 분기(branch) 중에서 가장 최종적인 선형 정규 체인(regular chain)이 될 가능성이 높은 분기를 선택하도록 설계되었습니다. 즉, 노드가 정규 시각에 접근하려 할 때 블록 트리에서 잘릴 가능성이 가장 낮은 분기를 선택하게 됩니다.
포크 선택 규칙은 특정 분기의 맨 위 블록(헤드 블록이라 함)을 선택함으로써 암묵적으로 하나의 분기를 선택합니다.
모든 정확한 노드에게 있어 어떤 포크 선택 규칙이라도 반드시 만족해야 하는 첫 번째 기준은 선택된 블록이 유효하고 프로토콜 규칙을 따르며 그 모든 조상 블록들도 유효해야 한다는 점입니다. 무효한 블록은 모두 무시되며, 무효 블록 위에 구성된 모든 블록 역시 자체적으로 무효가 됩니다.
이러한 전제 하에 포크 선택 규칙의 다양한 사례들이 존재합니다.
-
이더리움과 비트코인의 작업 증명 프로토콜은 「가장 무거운 체인 규칙」[4] (때때로 「가장 긴 체인」이라고 불리기도 하지만, 이는 완전히 정확하지 않음)을 사용합니다. 헤드 블록은 작업 증명 아래에서 누적된 「작업량(work)」이 가장 많은 체인의 꼭대기에 위치합니다.
-
이더리움 지분 증명 Casper FFG 프로토콜의 포크 선택 규칙은 「가장 높은 합리적 검사점(checkpoint)을 포함하는 체인을 따르는 것」이며 이미 확정된 블록을 절대로 롤백하지 않습니다.
-
이더리움 지분 증명 LMD GHOST 프로토콜의 포크 선택 규칙은 이름에 그 내용이 반영되어 있습니다. 「최대 탐욕적, 최대 중량 자손 서브트리(Greedy Heaviest Observed SubTree)」를 채택합니다. 이는 검증자들이 블록과 그 후속 블록들에 투표한 양을 집계하는 것을 포함하며, Casper FFG와 동일한 규칙도 적용됩니다.
두 번째와 세 번째 예시는 각각 해당 챕터에서 더 자세히 설명하겠습니다.
여러분도 눈치챘겠지만, 이러한 포크 선택 규칙들은 모두 블록에 숫자 형태의 점수를 부여하는 방법입니다. 승리하는 블록—즉 헤드 블록—은 가장 높은 점수를 가집니다. 핵심 아이디어는 모든 올바른 노드가 언젠가 특정 블록을 볼 경우, 자신이 가진 네트워크에 대한 다른 시각 여부와 관계없이 그 블록이 헤드 블록임을 명확히 인정하고 그 분기를 따라야 한다는 점입니다. 따라서 모든 정확한 노드들은 궁극적으로 창세기 블록부터 시작되는 단일한 정규 체인에 대한 공통된 시각에 도달하게 됩니다.
리오거나이제이션(Reorgs) 및 롤백(reversions)
노드가 새로운 블록(또한 지분 증명에서는 블록에 대한 새로운 투표)을 수신하면, 새 정보를 바탕으로 포크 선택 규칙을 다시 평가합니다. 가장 일반적인 경우는 새로운 블록이 현재 헤드 블록으로 간주하는 블록의 자식 블록이며, 따라서 새로운 헤드 블록이 되는 것입니다.
그러나 때때로 새로운 블록은 블록 트리 내 다른 블록의 후손일 수도 있습니다. (노드가 새로운 블록의 부모 블록을 아직 갖고 있지 않은 경우, 해당 부모 블록을 얻기 위해 피어 노드에 요청해야 하며, 마찬가지로 누락한 다른 블록들에 대해서도 요청해야 합니다.)
어떤 경우든, 갱신된 블록 트리에서 포크 선택 규칙을 실행했을 때 이전의 헤드 블록과 다른 분기의 헤드 블록을 가리킬 수 있습니다. 이런 일이 발생하면 노드는 리오거나이제이션(reorg, reorganisation의 줄임말)을 수행해야 하며, 이를 롤백이라고도 합니다. 노드는 기존 체인에 포함되었던 블록들을 제거하고(롤백), 새로운 헤드 블록이 있는 분기의 블록들을 채택해야 합니다.
다음 다이어그램에서, 노드는 블록 F를 헤드 블록으로 평가하고 있으므로 자신의 체인이 블록 A, B, D, E, F로 구성됩니다. 노드는 블록 C를 알고 있지만, 자신의 체인 시각에는 포함되지 않습니다. 블록 C는 사이드 분기(side branch)에 위치합니다.
시간이 지난 후, 노드는 현재 헤드 블록 F 위가 아니라 블록 C 분기 위에 구성된 블록 G를 수신합니다. 포크 선택 규칙의 세부사항에 따라 노드는 여전히 F를 G보다 더 나은 헤드 블록으로 평가하여 G를 무시할 수 있습니다. 그러나 여기서는 포크 선택 규칙이 G가 더 나은 헤드 블록임을 나타낸다고 가정합니다.
블록 D, E, F는 블록 G의 조상이 아니므로 노드의 정규 체인에서 제거되어야 합니다. 이 블록들에 포함된 모든 거래나 정보는 마치 수신된 적이 없었던 것처럼 롤백됩니다. 노드는 블록 B 처리 이후의 상태로 완전히 되돌아가야 합니다.
블록 B로 되돌린 후, 노드는 블록 C와 G를 체인에 추가하고 이를 적절히 처리할 수 있습니다. 이 과정이 끝나면 노드는 체인의 재구성을 완료한 것입니다.
나중에 블록 F 위에 구성된 블록 H가 등장할 수도 있습니다. 만약 포크 선택 규칙이 새로운 헤드 블록이 H여야 한다고 판단한다면, 노드는 다시 한 번 리오거나이제이션을 수행하여 블록 B까지 되돌린 후 H 분기의 블록들을 다시 구축합니다.
작업 증명과 이더리움의 지분 증명 프로토콜 모두에서 블록 전파의 네트워크 지연 때문에 짧은 1~2개 블록의 리오거나이제이션이 드물지 않습니다. 체인이 공격당하거나 포크 선택 규칙 자체 또는 클라이언트 구현에 결함이 없는 한 매우 긴 리오거나이제이션은 극히 드물어야 합니다.
안전성(Safety)과 작동성(Liveness)
합의 메커니즘을 논의할 때 자주 등장하는 두 가지 중요한 개념은 안전성(safety)과 작동성(liveness)입니다.
안전성
비공식적으로 말해, 어떤 알고리즘이 「나쁜 일이 전혀 발생하지 않는다면」 [5], 그 알고리즘은 안전하다고 간주됩니다.
블록체인 환경에서 발생할 수 있는 나쁜 일의 예로는 암호화폐의 이중 지출(double-spend)이나 서로 충돌하는 두 개의 검사점(checkpoint)이 확정되는 경우 등이 있습니다.
분산 시스템에서 안전성의 중요한 측면 중 하나는 「일관성(consistency)」입니다. 즉, 특정 블록 높이에서 특정 계정의 잔액과 같은 체인의 진행 상태에 대해 서로 다른(정직한) 노드들에게 질문했을 때, 어느 노드에 묻더라도 항상 동일한 답변을 얻어야 합니다. 안전한 시스템에서는 각 노드가 체인의 역사에 대해 영원히 변하지 않는 동일한 시각을 갖습니다.
실제로 안전성은 우리 분산 시스템이 「원자화된 작업 하나씩만 수행하는 중앙 집중식 인스턴스처럼 동작한다」는 의미입니다. (Castro와 Liskov의 표현). Vitalik의 중앙 집중화 분류에서 안전한 시스템은 논리적으로 중앙 집중화되어 있습니다.
작동성
다시 말해, 어떤 알고리즘이 「결국 좋은 일이 발생한다면」, 그 알고리즘은 작동성(liveness)을 갖는다고 간주됩니다.
블록체인 환경에서는 일반적으로 체인에 항상 새로운 블록을 추가할 수 있다는 의미로 해석합니다. 즉, 거래를 포함하는 새로운 블록을 생성할 수 없는 정체 상태에 빠지지 않는다는 뜻입니다.
「가용성(Availability)」은 이 문제를 바라보는 또 다른 시각입니다. 나는 체인이 가용하기를 원하며, 이는 내가 정직한 노드에 유효한 거래를 보내면 언젠가는 체인을 확장하는 블록에 포함될 것임을 의미합니다.
둘 다 동시에 가질 수 없다!
CAP 정리는 분산 시스템 이론에서 유명한 결과로, 어떤 분산 시스템도 (1) 일관성(consistency), (2) 가용성(availability), (3) 분할 내성(partition tolerance)을 동시에 제공할 수 없다고 주장합니다. 분할 내성은 노드 간 통신이 신뢰할 수 없는 상황에서도 시스템이 정상적으로 작동할 수 있는 능력을 의미합니다. 예를 들어, 네트워크 장애로 인해 노드들이 서로 통신할 수 없는 두 개 이상의 그룹으로 분리될 수 있습니다.
블록체인 맥락에서 CAP 정리를 쉽게 입증할 수 있습니다. 아마존 웹 서비스(AWS)가 다운되어 AWS에서 호스팅되는 모든 노드들이 서로 통신은 하지만 외부와는 통신할 수 없게 되었거나, 한 국가가 모든 출입 연결을 차단하여 어떤 gossip 트래픽도 통과할 수 없는 상황을 상상해 보세요. 이 두 경우 모두 노드들을 A와 B처럼 서로 관련 없는 두 그룹으로 분리하게 됩니다.
A 그룹 네트워크에 연결된 계정이 거래를 보냈다고 가정해 보겠습니다. A 그룹의 노드들이 그 거래를 처리하면, 결국 거래를 보지 못한 B 그룹의 노드들과 최종 상태가 달라집니다. 따라서 전체적으로 모든 노드 간의 일관성을 잃게 되며, 이는 곧 안전성을 잃는 것입니다. 이 상황을 피하는 유일한 방법은 A 그룹의 노드들이 거래 처리를 거부하는 것이지만, 이 경우 우리는 가용성과 작동성을 잃게 됩니다.
요약하자면 CAP 정리는 우리가 신뢰할 수 없는 네트워크, 즉 인터넷 위에서 운영해야 하기 때문에 어떤 상황에서도 안전성과 작동성을 동시에 갖는 합의 프로토콜을 설계할 수 없다는 것을 의미합니다 [6].
이더리움은 작동성을 우선시한다
양호한 네트워크 상황에서는 이더리움 합의 프로토콜이 안전성과 작동성을 모두 제공하지만, 네트워크가 원활하지 않을 때는 작동성을 우선시합니다. 네트워크 분할 상황에서는 분할된 양측의 노드들이 계속해서 블록을 생성할 것입니다. 그러나 이제 확정성(finality, 안전성의 속성)은 양측에서 동시에 발생하지 않습니다. 각 측에서 관리하는 지분(stake) 비율에 따라 한쪽은 계속 확정성을 얻거나, 양쪽 모두 더 이상 확정성을 얻지 못하게 됩니다.
궁극적으로 분할이 해결되지 않는 한, 양측은 새로운 게으름 방출(inactivity leak) 메커니즘 덕분에 결국 다시 확정성을 회복하게 됩니다. 그러나 이는 궁극적으로는 안전성 실패로 이어집니다. 각 체인은 서로 다른 역사를 확정하게 되며, 두 체인은 영원히 조정 불가능하고 독립적인 상태가 됩니다.
확정성(Finality)
다음 챕터에서는 확정성에 대해 자세히 다룰 예정이며, 이는 체인의 안전성 속성입니다.
확정성은 일부 블록들이 절대 롤백되지 않는다는 것을 의미합니다. 블록이 확정되면, 네트워크의 모든 정직한 노드들이 해당 블록이 체인의 역사에 영원히 남을 것이라는 데 동의합니다. 따라서 그 모든 조상 블록들도 체인의 역사에 영원히 남게 됩니다. 확정성은 피자에 대한 지불을 현금처럼 돌이킬 수 없게 만듭니다. 이것은 이중 지출에 대한 궁극적인 보호 장치입니다 [7].
클래식 PBFT나 Tendermint와 같은 일부 합의 프로토콜은 매 라운드(각 블록마다)마다 확정성을 제공합니다. 한 번 라운드의 거래가 체인에 포함되면 모든 노드는 그것이 영원히 존재할 것임에 동의합니다. 한편으로, 이러한 프로토콜은 매우 「안전」합니다. 거래가 체인에 포함되면 절대 롤백되지 않습니다. 반면에 작동성 장애에 취약합니다. 노드들이 합의에 도달할 수 없다면 — 예를 들어, 노드의 3분의 1 이상이 종료되거나 이용 불가능한 경우 — 더 이상 거래를 체인에 추가할 수 없으며 체인은 멈추게 됩니다.
비트코인의 나카모토 합의와 같은 다른 합의 프로토콜은 본질적으로 확정성 메커니즘이 전혀 없습니다. 언제든지 더 무거운 대안 체인이 나타날 가능성이 항상 존재합니다. 이런 일이 발생하면 모든 정직한 노드들은 이전에 처리했던 거래들을 롤백하면서 체인을 재구성해야 합니다. 블록이 몇 개의 확인(confirmations)을 받았는지와 같은 경험적 방법은 확정성에 대한 근사치일 뿐이며 보장은 없습니다 [8].
이더리움의 합의 계층은 작동성을 우선시하지만, 유리한 상황에서는 확정성 방식으로 안전성을 제공하려고 노력합니다. 이것은 양쪽의 이점을 모두 취하려는 시도입니다. Vitalik은 이렇게 변론했습니다 [9]:
일반적인 원칙은 사용자에게 「가능한 한 많은 합의」를 주는 것입니다. 합의에 참여하는 노드들이 > 2/3라면 우리는 일반적인 합의를 얻습니다. 그러나 < 2/3라면 아무것도 하지 않고 멈추는 것이 아니라, 새로운 블록의 보안 수준이 일시적으로 낮아지더라도 체인은 계속 성장할 수 있습니다. 개별 애플리케이션이 낮은 보안 수준에 만족하지 않는다면, 블록들이 확정될 때까지 자유롭게 무시할 수 있습니다.
이더리움의 합의 계층에서 확정성은 곧 Casper FFG 메커니즘에 의해 제공되며, 우리는 곧 이 메커니즘을 살펴볼 것입니다. 그 원리는 모든 정직한 검증자들이 정기적으로 최근 검사점 블록에 대해 합의하며, 이 블록들을 절대 철회하지 않는다는 것입니다. 그러면 이 블록과 그 모든 조상 블록들은 「확정된」 블록이 됩니다. 즉, 절대 바뀌지 않으며, 네트워크의 어떤 정직한 노드에게든 이들 블록이나 그 조상 블록에 대해 묻더라도 항상 동일한 답을 얻게 됩니다.
이더리움의 확정성은 「경제적 확정성(economic finality)」입니다. 이론적으로 프로토콜은 체인 역사에 대한 두 가지 모순된 시각, 즉 서로 충돌하는 두 개의 검사점을 확정할 수 있습니다. 그러나 이것은 거대하고 정량화 가능한 비용이 들기 때문에 거의 발생하지 않습니다. 극단적인 공격이나 실패 상황을 제외하고는, 확정된 것은 확정된 것입니다.
Casper FFG 파트에서는 이러한 확정성 메커니즘의 작동 방식을 심도 있게 다룹니다.
참고 자료
레슬리 램포트(Leslie Lamport)가 참여한 작품은 언제나 읽을 가치가 있습니다. 그가 Shostak과 Pease와 함께 1982년에 발표한 원조 논문 『비잔틴 장군 문제(The Byzantine Generals Problem)』는 많은 통찰을 제공합니다. 오늘날의 기준으로 보면 그들이 제안한 알고리즘은 매우 비효율적이지만, 일반적인 합의 프로토콜을 추론하는 데 훌륭한 소개가 됩니다. 또한 Castro와 Liskov가 1999년에 발표한 획기적인 논문 『실용적 비잔틴 장애 허용(Practical Byzantine Fault Tolerance)』도 마찬가지로, 이는 이더리움의 Casper FFG 프로토콜 설계에 큰 영향을 미쳤습니다. 하지만 여러분은 이러한 「고전적」 방법을 2008년 비트코인 백서에서 나카모토가 설명한 작업 증명의 우아한 단순성과 비교해보고 싶을지도 모릅니다. 작업 증명이 가진 장점이 있다면 바로 그 단순성입니다.
본문에서 언급한 Gilbert와 Lynch의 2012년 논문 『CAP 정리에 대한 시각(Perspectives on the CAP Theorem)』은 일관성과 가용성(또는 우리의 맥락에서는 안전성과 작동성) 개념을 깊이 있게 탐색하며, 읽기 쉬운 편입니다.
포크 선택 규칙의 클라이언트 구현 간의 차이로 인해 이더리움 비콘 체인은 2022년 5월에 7개 블록의 리오거나이제이션을 경험했습니다. 당시 이러한 차이는 알려져 있었으며 무해하다고 여겨졌습니다. 그러나 실제로는 그렇지 않았습니다. Barnabé Monnot의 이 사건에 대한 설명은 매우 교훈적입니다.
Vitalik의 블로그 글 『결제 확정성에 관하여(On Settlement Finality)』는 확정성 개념에 대해 더 깊고 섬세한 탐구를 제공합니다.
우리가 구축하고자 하는 시스템의 이상은 정치적으로는 탈중앙화되어야 하며(허가 없이 참여 가능하고 검열 저항 가능하게), 아키텍처적으로도 탈중앙화되어야 하며(단일 장애 지점 없이 강건하게), 그러나 논리적으로는 중앙화되어야 한다는 것입니다(일관된 결과를 얻기 위해). 이러한 기준들은 합의 프로토콜을 어떻게 설계할지를 크게 좌우합니다. Vitalik은 『탈중앙화의 의미(The Meaning of Decentralization)』라는 글에서 이러한 문제들을 탐구하고 있습니다.
TechFlow 공식 커뮤니티에 오신 것을 환영합니다
Telegram 구독 그룹:https://t.me/TechFlowDaily
트위터 공식 계정:https://x.com/TechFlowPost
트위터 영어 계정:https://x.com/BlockFlow_News
@LXDAO_Official
