캐스퍼의 단짝 유령 친구, LMD GHOST
DSRV Research는 더 많은 사람이 Web3를 이해하고 참여하는 데 기여하기 위해, 블록체인과 관련된 지식을 연재합니다.
Disclaimer: 이 글은 정보 전달을 위한 목적으로 작성되었으며, 특정 프로젝트에 대한 투자 권고, 법률적 자문 등 목적으로 하지 않습니다. 모든 투자의 책임은 개인에게 있으며, 이로 발생된 결과에 대해 어떤 부분에서도 DSRV는 책임을 지지 않습니다. 본문이 포괄하는 내용들은 특정 자산에 대한 투자를 추천하는 것이 아니며, 언제나 본문의 내용만을 통한 의사결정은 지양하시길 바랍니다.
LMD GHOST: 이더리움 2.0의 Fork Choice Rule
[이더리움 2.0 합의 알고리즘 시리즈]
0. Safety and Liveness
1. Casper, the Friendly Finality Gadget
2. LMD Ghost
3. Gasper
안녕, 내 이름은 캐스퍼! 다들 나 안 보고 싶었어? 오늘은 내 유령 친구인 LMD GHOST를 소개해주려고 해. 내 친한 친구인 만큼 다들 좋아해 줬으면 좋겠네.
본문에서는 이더리움 2.0을 향한 흥미로운 (그리고 험난한) 여정에서 나타난 두 번째 유령, LMD GHOST에 대하여 알아보고자 합니다. 이전 아티클에서 다루어 본 첫 번째 유령, 캐스퍼는 생성된 블록들 중 일부를 중간중간 확정시킴으로써 블록체인의 상태가 일정 수준 이전으로 돌아가는 것을 막는 역할을 했다면 LMD GHOST는 블록체인이 여러 갈래로 갈라져 포크가 발생하는 경우 어떤 포크를 선택할 것인지를 정하는 Fork Choice Rule의 일종입니다. Fork Choice Rule은 나카모토 컨센서스의 Longest Chain, 즉 ‘포크가 발생하면 더 긴 체인을 선택한다’는 규칙에 대하여 알아볼 때 언급되었던 내용입니다. LMD GHOST는 여기에서 조금 더 발전한 모양새를 갖추고 있는데, 한번 자세히 알아보겠습니다.
메시지와 뷰(View)
Fork Choice Rule을 이해하기 위해서는 분산된 환경의 네트워크에서 각각의 검증인들이 어떻게 상호작용하는지 짚어보는 것이 도움이 됩니다. LMD GHOST가 적용될 이더리움 네트워크는 여러 명의 검증인들로 구성되어 있고, 각 검증인들은 서로 메시지를 주고받음으로써 네트워크가 동작하도록 합니다. 전송하는 메시지가 어떤 내용을 담고 있는지에 따라 이더리움 비콘체인의 검증인들은 1) 블록을 제안하거나, 2) 여러 블록 중에서 어떤 블록을 지지한다고 투표하거나, 3) 원래는 검증인이 아니었던 사람을 새로이 검증인으로 참여시키거나, 4) 다른 검증인들의 악의적인 행동을 고발하는 증거를 제출하는 등의 행동을 할 수 있습니다. [1]
그렇다면 이제 “네트워크 뷰(Network View)”를 정의할 수 있습니다. 네트워크 뷰란, 이렇게 검증인들이 서로에게 전송한 모든 메시지를 모두 포함하는 시각입니다. 그러나 실제로 네트워크를 구성하는 각각의 검증인들은 네트워크 지연(Latency) 등의 이유로 네트워크 뷰에 포함된 모든 메시지들을 확인하지 못할 가능성이 있습니다. 그래서 각각의 검증인들은 네트워크를 바라보는 그들만의 뷰를 가지고 있다고 표현해볼 수 있습니다. 이 개념을 수식화하여 표현해보자면, view(NW, T)는 T라는 시간에서의 네트워크 뷰를, view(V, T)는 T라는 시간에서의 특정 검증인 V의 뷰를 표현합니다.
위의 그림과 같은 예시를 보면 메시지와 뷰에 대해 보다 명확히 이해할 수 있습니다. 네트워크를 구성하는 검증인들은 메시지를 다른 검증인들에게 전송하고, 메시지를 받은 검증인은 그 메시지를 다시 다른 검증인들에게 전파할 수 있습니다. 만약 2번 검증인이 캐나다에 있고, 5번 검증인이 영국에 있는데 모종의 이유로 둘을 잇는 네트워크에 문제가 생겨 메시지가 정상적으로 전달되지 못하는 상황이 발생한다면 2번 검증인이 5번 검증인에게 보낸 “메시지 2”를 확인하지 못하게 될 수 있습니다. 따라서 view(validator 5, T)는 “메시지 2”를 제외한 “메시지 1”과 “메시지 7”이 됩니다.
이렇게 각각의 검증인이 메시지를 누락하여 이해할 가능성이 있음에도, 결국엔 시간이 흐르면 정상적인 검증인끼리 하나의 상태, 즉 한 갈래의 블록체인으로 합의를 할 수 있도록 하는 것이 바로 합의 알고리즘의 역할입니다. 합의 알고리즘을 구성하는 여러 메커니즘 중에서도 Fork Choice Rule은 만약 포크가 발생했을 때 특정 검증인이 스스로 이해하고 있는 뷰를 기반으로 어떤 포크를 선택할지 결정하는 역할을 합니다.
각각의 검증인마다 다른 뷰를 가진다는 것은, 곧 그들이 취합한 정보가 다르다는 것을 의미합니다. 예를 들어 Longest Chain을 Fork Choice Rule로 사용하고 있는 블록체인의 경우, 어떤 검증인은 네트워크 지연 등의 이유로 특정 블록들을 확인하지 못할 수 있고, 다른 검증인들과 똑같이 자신의 입장에서 “가장 긴 체인”을 정당한 포크로 선택하더라도 취합한 정보가 다르기 때문에 결과적으로 다른 검증인이 고르지 않은 다른 포크를 선택할 가능성이 있습니다. LMD GHOST 또한 Fork Choice Rule의 일종으로, 위의 그림에서 5번 검증인과 2번 검증인처럼 서로 다른 뷰를 가지고 있다면, 각 검증인이 취합한 메시지가 다르기 때문에 다른 포크를 선택하는 결과를 가져올 수 있습니다.
증언(Attestation)
이더리움 2.0의 Fork Choice Rule인 LMD GHOST는 “Latest Message Driven Greediest Heaviest Observed SubTree”의 약자입니다. 이름을 찬찬히 살펴보면 어떤 방식으로 Fork Choice가 이루어지는지 유추해볼 수 있는데, 우선 LMD, 즉 Latest Message Driven이 무엇을 의미하는지 알아보겠습니다.
여기에서 “message”란, 여러 종류의 메시지 중에서도 “attestation(이하, 증언)”이라는 종류의 메시지를 뜻합니다. 이더리움 2.0에서는 블록이 생성되면 검증인들이 해당 블록에 대한 증언 메시지를 전송함으로써 새롭게 생성된 블록이 기존 체인에 연결되어야 한다는 의사를 표현할 수 있습니다. 만약, 새롭게 생성된 블록이 여러 개라면, 그중에서 어떤 블록이 기존 체인에 연결되어야 하는지도 증언 메시지를 통해 투표합니다.
위의 그림은 위에서 아래로 진행하는 블록체인에서 발생한 포크들과 증언 메시지들(동그라미)을 표현합니다. 이렇게 표현된 블록들을 나무를 닮았다고 해서 “블록 트리”라고 부르고, 가장 밑단에 있는 블록들을 잎사귀에 비유하여 “리프 블록(leaf block)”이라고 합니다. LMD GHOST는 블록체인의 가장 먼저 생성된 블록인 제네시스 블록에서부터 리프 블록까지 순서대로 따라가다가 포크가 발생한 경우, 더 많은 증언 메시지가 지지하고 있는 블록을 선택합니다. 헷갈릴 수 있지만, 이때 고려하는 증언 메시지는 제네시스 블록부터 발생한 모든 증언 메시지가 아닌, ‘최신의’ 증언 메시지들입니다.
각각의 검증인들은 latest_messages 라는 이름으로 저장된 정보를 유지하고 있는데, 여기에는 각 검증인들로부터 받은 증언 메시지 중에서 가장 최신의 메시지가 무엇인지가 저장됩니다. [2]
@dataclass
class Store(object):
time: uint64
genesis_time: uint64
justified_checkpoint: Checkpoint
finalized_checkpoint: Checkpoint
best_justified_checkpoint: Checkpoint
blocks: Dict[Root, BeaconBlock] = field(default_factory=dict)
block_states:
Dict[Root, BeaconState] = field(default_factory=dict)
checkpoint_states:
Dict[Checkpoint, BeaconState] = field(default_factory=dict)
latest_messages:
Dict[ValidatorIndex,LatestMessage] = field(default_factory=dict)즉, LMD GHOST는 “각각의 검증인들로부터 받은 가장 최근 증언 메시지”를 바탕으로 여러 갈래의 포크 중 하나를 선택합니다. 만약 A라는 검증인으로부터 1시간 전에 증언 메시지를 받고 다시 10분 전에 증언 메시지를 새롭게 받았다면, 1시간 전에 받은 메시지는 무시하고 가장 최근에 받은 메시지만 포크를 선택할 때 고려합니다.
각 검증인들마다 고유한 뷰가 있다는 것을 상기하면, 각 검증인들마다 이해하는 “최신의” 메시지가 다를 수 있다는 것을 알 수 있습니다. 만약 A라는 검증인이 1시간 전에 보낸 증언 메시지는 받았지만, 10분 전에 보낸 증언 메시지는 받지 못했다면, 그 메시지를 성공적으로 수신한 다른 검증인들과는 다르게, 내가 이해하는 “최신의” 증언 메시지는 바로 1시간 전에 받은 증언 메시지가 됩니다.
이렇게 각각의 검증인들이 이해하는 최신의 증언 메시지는 다를 수 있지만, 그렇게 취합한 정보를 바탕으로 LMD GHOST, 즉 “가장 많은 최신의 증언 메시지가 지지하는 포크를 선택한다”는 원칙을 사용하는 것은 모두가 같습니다.
LMD GHOST
LMD GHOST의 정확한 알고리즘은 위와 같은데, 조금 더 풀어 설명해보겠습니다. 각 검증인들은 모두 제네시스 블록에서 시작하여 리프 블록까지 자식 블록들을 따라가며 어떤 체인을 정본으로 인정할 것인지 (즉, 어떤 체인이 Canonical Chain인지) 결정합니다. 그 과정에서 매 블록 높이마다 각 검증인의 뷰를 기준으로 같은 블록 높이의 여러 블록 중에서 가장 많은 증언 메시지를 받은 블록을 선택합니다.
예를 들어 블록 높이 10까지 블록이 생성된 체인에서 블록 높이 11의 새로운 블록을 생성해야 하는 상황을 가정해보겠습니다. 새로운 블록을 생성하기 이전에, 검증인은 LMD GHOST를 통해 어떤 체인이 Canonical Chain인지 확인하고, 그 위에 새로운 블록을 생성해야 합니다. 따라서 검증인은 다른 검증인들이 전파한 최신 증언 메시지들을 취합하고, 그를 바탕으로 블록 높이 0부터 Canonical Chain을 확정합니다. 블록 0에서 1, 2까지는 한 갈래의 체인이었다가 블록 높이 3에서 포크가 발생했다면, 이때 최신 증언 메시지들이 더 많이 지지하는 포크를 Canonical Chain으로 확정하고 다시 블록 높이 4, 그리고 5로 점차 확정시켜 나가는 방식입니다.
여기서 증언 메시지는, 각 검증인들이 보유하고 있는 지분만큼 가중된 만큼의 영향력을 가집니다. 즉, 64 ETH를 가지고 있는 검증인의 한 표는 32 ETH를 가지고 있는 검증인의 두 표와 같은 영향력을 가집니다.
단순화된 예시를 통해 조금 더 살펴보겠습니다. 만약 이더리움 네트워크에 A, B, C, D, E 다섯명의 검증인이 있고, 각 검증인들은 같은 양의 지분을 가지고 있다고 가정해보겠습니다. 정확한 블록 생성 메커니즘에 대해서는 추후 작성될 Gasper에 대한 글에서 더 자세히 다룰 예정이지만, 우선 최대한 단순화하여 검증인 A → B → C → D → E 의 순서대로 돌아가며 블록을 제안한다고 생각해보겠습니다. 왼쪽에서 오른쪽으로 블록체인이 진행한다고 했을 때, 각 블록의 블록 높이는 아래와 같습니다.
그리고 아래와 같이 각 검증인들이 순서대로 블록을 만들었다고 가정해보겠습니다.
💡 DSRV's Tip; 블록을 생성하는 메시지와 증언 메시지는 서로 같은 것인가요?
같지 않습니다. 실제 이더리움 2.0에서는 훨씬 더 많은 검증인이 존재하고, 따라서 블록을 제안하는 것이 아닌 증언 메시지를 전파하는 과정이 따로 존재합니다. [3] 자세한 내용은 이후 Gasper 아티클의 “위원회(Committee)”와 관련된 부분에서 다루겠지만, 본문에서는 보다 쉽게 이해하기 위해 ‘블록을 생성하는 것이 곧 증언 메시지를 전파하는 것과 같다'고 가정하겠습니다.그렇다면, 위와 같은 체인에서는 파란색으로 표시된 블록들이 바로 가장 최신의 증언 메시지를 표시합니다. 검증인 A, B, C, E의 경우를 보면, 이전에 생성했던 블록들은 이후 블록들이 새롭게 생성됨에 따라 무시되는 것을 볼 수 있습니다. D는 자신이 블록을 생성해야 할 두 번째 차례에 블록을 성공적으로 생성하지 못했습니다. 따라서 D의 최신 증언 메시지는 그대로 첫 번째 생성된 블록으로 유지된다는 것을 알 수 있습니다.
이렇게 정해진 최신 증언 메시지를 바탕으로 LMD GHOST가 어떻게 동작하는지 알아보겠습니다. 아래의 그림과 같이 블록이 이미 생성된 현재, LMD GHOST를 통해 어떤 포크가 Canonical Chain인지 결정하는 과정을 따라가 보겠습니다.
파란색으로 표시된 블록들이 최신 증언 메시지이므로, 이들은 모두 1만큼의 지지를 표현할 수 있습니다. 각각의 검증인들이 모두 같은 양의 지분을 가진 것으로 가정하고 있기 때문입니다. 최신 증언 메시지를 표현하는 블록들의 부모 블록(왼쪽 블록)은, 자식 블록들이 가지고 있는 증언 메시지를 모두 합산한 점수를 갖게 됩니다.
그렇다면, 이 점수들을 바탕으로 아래 LMD GHOST 알고리즘의 작동 방식에 따라 생각해 보겠습니다.
LMD GHOST는 제네시스 블록(가장 왼쪽)에서 시작하여 오른쪽으로 나아가며 어떤 체인이 Canonical Chain인지 결정합니다. 블록 높이 3에서 최초로 포크가 발생한 것을 확인할 수 있는데 이러한 경우, 보다 높은 점수를 가지고 있는 아래쪽 포크를 선택하게 됩니다. 다시 블록 높이 5에서도 세 갈래의 포크가 발생한 것을 볼 수 있는데, 이 경우에도 역시 더 높은 점수를 가지고 있는 가운데 포크를 선택하게 됩니다.
여기에서 GHOST, 즉 “Greediest Heaviest Observed SubTree”가 무엇을 뜻하는지 알 수 있습니다. 지금까지 살펴본 메커니즘은 “해당 블록의 SubTree, 즉 자식 블록들이 더 많은 증언 메시지(Greediest, Heaviest)로부터 지지받을 경우 선택한다”로 요약할 수 있기 때문입니다.
Longest Chain vs LMD GHOST
위의 예시에서는 결국 가장 긴 체인이 Canonical Chain으로 결정되었는데, 그렇다면 Longest Chain과 LMD GHOST는 같은 결과를 내는 Fork Choice Rule일까요? 대부분의 경우에는 맞습니다. LMD GHOST를 사용하면 Longest Chain과 같은 결과를 내는 경우가 많습니다. 그러나 아래와 같은 상황에서는 LMD GHOST와 Longest Chain이 다른 결과를 도출합니다.
Longest Chain에 따르면, 가장 긴 체인이 Canonical Chain으로 선정됩니다. 즉, 블록 높이가 4까지 밖에 가지 못한 체인들에 비해 블록 높이 5로 가장 긴 체인이 연결된 맨 위의 포크가 Canonical Chain이 됩니다.
반면, 같은 상황에서 LMD GHOST를 사용하면 더 많은 증언 메시지의 지지를 받은 아래쪽 포크가 Canonical Chain으로 선정됩니다. 네트워크 지연이 심각한 상황에서는 위의 그림처럼 포크가 여러 갈래로 발생할 수 있습니다. 같은 블록 높이에서 포크가 많이 발생하여 블록 높이가 높아지지 않더라도, 많은 자식 블록들이 지지하는 부모 블록이 더 정당한 블록이라고 할 수 있지 않을까요? LMD GHOST는 바로 이러한 생각을 반영합니다. [4]
“Sticky” LMD GHOST
LMD GHOST는 “달라붙는(Sticky)” 속성을 가진다는 점도 장점으로 꼽을 수 있습니다. 달라붙는다는 것이 어떤 의미인지 알아보기 위해 5명의 검증인 A, B, C, D, E 중에서 B가 의도적으로 다른 포크를 만들어 공격을 시도하고 있다고 가정해보겠습니다. 상황은 아래의 그림과 같습니다.
검증인 A가 두 번째 블록을 생성할 당시, 어떤 뷰를 기준으로 판단했는지 알아보겠습니다.
검증인 A가 B의 블록 다음이 아닌 아래쪽 포크를 선택하여 블록을 선택한 이유는 위와 같은 뷰를 가지고 있었기 때문입니다. 아래쪽 포크는 A, C, D, E 총 4개의 최신 증언 메시지가 지지하고 있지만, 위 쪽 포크는 B 하나의 증언 메시지 밖에 지지하고 있지 않습니다. 따라서 검증인 A는 위의 뷰를 바탕으로 LMD GHOST 알고리즘이 Canonical Chain이라 가리키는 아래쪽 포크에 새로운 블록을 더합니다.
이번엔 검증인 A가 세 번째 블록을 새롭게 더하는 상황을 생각해보겠습니다.
검증인 A의 뷰에는 가능한 경우의 수가 여러 가지 있습니다. 검증인 A가 정상적으로 최근에 생성된 모든 블록들을 모두 확인했다면 1번 뷰를 가질 것이지만, 만약 네트워크 지연으로 인하여 검증인 C의 두 번째 블록을 확인하지 못했다면 2번 뷰를 가질 것입니다. 그러나 어떤 경우에도 LMD GHOST에 의해 위쪽 포크가 아닌 아래쪽 포크를 Canonical Chain으로 선정한다는 것은 달라지지 않습니다. 따라서 검증인 A는 위쪽 포크가 아닌, 아래쪽 포크에 새로운 블록을 추가해야 합니다.
만약 A 또한 B가 만든 포크에 가담하여 체인을 공격하고자 한다면, LMD GHOST가 선정하는 Canonical Chain에서 벗어나 다른 포크에 블록을 생성해야 합니다. 이렇게 정해진 메커니즘을 어기고 임의적으로 블록을 생성하는 행위는 검증인 A의 지분 삭감 등 페널티를 수반하기 때문에 [5] 검증인 A는 공격을 위해 상당한 비용을 지불해야만 합니다.
또한 A의 블록에 뒤따라 검증인 B와 C 또한 위쪽 포크에 가담하여 블록을 생성해야 비로소 LMD GHOST로 위 쪽 포크가 선택되게 됩니다. (위쪽 포크의 점수는 3, 아래쪽 포크의 점수는 2.)
이렇게 LMD GHOST를 사용하여 포크를 선택하는 블록체인에서는 한쪽 포크에서 다른 한쪽 포크로 넘어갈 때 누군가는 정해진 규칙을 어기고 비용을 떠안아야 공격에 성공할 수 있습니다. 이렇게 한번 LMD GHOST로 결정된 포크를 벗어나 다른 포크가 Canonical Chain으로 인정받기 어렵다는 의미에서 LMD GHOST를 “달라붙는”, 또는 “끈적한” 성질을 가지고 있다고 표현합니다. 그리고 이렇게 공격을 위해서는 누군가가 정해진 규칙을 어긴다는 점에서 쉽게 공격을 식별할 수 있다는 장점도 있습니다.
마무리: Gasper
길었던 이더리움 2.0 시리즈도 마지막 한 편만을 남겨두고 있는데요, 다음 아티클 주제는 바로 Gasper입니다. 들어본 적이 없음에도 벌써 단어가 익숙한 것 같다면, 맞습니다. 지금까지 이더리움 2.0 시리즈를 통해 알아본 캐스퍼(Casper)와 (LMD) GHOST, 이 두 단어를 적절하게 조합하게 되면 “Gasper”가 만들어집니다. Gasper는 본문에서 여러 번 인용된 논문인 “Combining GHOST and Casper”에서 소개되었는데요, “GHOST와 Casper를 합쳤더니 Gasper가 되었다.”라는 부분이 꽤 재밌는 작명인 것 같습니다.
직관적인 이름을 가지고 있는 만큼, Gasper가 어떤 방식으로 동작할지 상상은 해볼 수 있을 것 같습니다. LMD GHOST의 메커니즘을 어느 정도 계승했을 테니, 블록이 생성되고 증언(Attestation) 메시지가 여기저기에서 전파되는 그림이 그려집니다. 만약 그렇다면, 어차피 증언 메시지의 개념이 사용되는 것이니 똑같이 캐스퍼의 투표 과정에서도 이 방식을 응용해볼 수 있지 않을까요? 이렇듯 Gasper에서는 캐스퍼와 LMD GHOST가 긴밀히 연결되는 모습을 확인하실 수 있습니다. 귀중한 시간을 들여 여기까지 읽어주신 독자분들께 감사드리며, DSRV Research는 다음 시간, 시리즈의 마지막 글로 다시 찾아오도록 하겠습니다.
Written by
Seokjoong Yoon, DSRV Researcher (Twitter @imlearning_eth)
Reviewed by
Owen Hwang, DSRV Research Manager (Twitter @journeywith_eth)
Youngbin Park, DSRV Researcher (Twitter @bin0_0bin)
Illustrations by
Heeyoung Moon, DSRV Brand Designer
💊 Key Takeaways
- LMD GHOST는 여러 갈래의 포크 중에서 어떤 포크를 선정할지 정하는 메커니즘인 Fork Choice Rule입니다.
- LMD GHOST는 가장 많은 증언 메시지로부터 지지를 받은 포크를 선택합니다.
- LMD GHOST에서 LMD, 즉 Latest Message Driven은 포크 선택 시 각 검증인이 가장 최근 전파한 증언 메시지만 고려한다는 것을 의미합니다.
- LMD GHOST는 Longest Chain과 비슷한 결과를 도출하지만, 네트워크 지연이 심각한 상황에서는 다른 결과를 도출할 수 있습니다.
- LMD GHOST를 사용하는 블록체인에서 공격을 시도하기 위해서는 누군가가 정해진 규칙을 어기고 그에 따라 부과되는 패널티를 감수해야 하는 상황이 발생할 수 있습니다. 이러한 속성을 “sticky”하다고 부릅니다.
References:
[1] V. Buterin et al. Combining GHOST and Casper. 2020. p.4
[2] Ethereum Github — Ethereum 2.0 Phase 0 — Beacon Chain Fork Choice
[3] V. Buterin et al. Combining GHOST and Casper. 2020. p.13. “At time (i + 1/2), the middle of slot i = jC + k, each validator V in committee Sk computes B’ = HLMD(view(V, i + 1/2)), and publishes an attestation α, which is a message containing […]”
[4] V. Buterin. A CBC Casper Tutorial. 2018.
[5] V. Buterin. A CBC Casper Tutorial. 2018. “A and C illegally switch over to support B’s block (and can get penalized for this) […]”
