Gasper(Casper + LMD GHOST)에 대해 공부해보자!

요약)

1. The merge 업데이트에서 PoW → PoS로 consensus protocol을 변경.
2. 기존에 사용되던 Casper FFG와 LMD Ghost를 ETH2에 적절히 조합한 PoS consensus algorithm.

---

Fork-Choice-Rule: Nakamoto consensus (classic)

비트코인과 이더리움 1.0 PoW의 가장 근간이 되는 합의 프로토콜.

다른 말로 Longest Chain Rule이라고도 표현한다. 말그대로 Fork가 발생했을 때, 여러 Fork중, 더 긴 체인을 선택하는 (즉, 더 많은 hash power가 들어간 체인이 나열한 트랜잭션 순서를 valid하다고 인정하는) 프로토콜이다.

이렇게 인정된 체인을 Canonical Chain이라고 부른다.

---

Safety & Liveness

FLP impossibility: 결정론적(Safety)하고 비동기적인(Liveness)프로세스에서 합의에 이르는 것이 불가능하다는 것

• Safety: Finality로 fork발생 없이 오직 하나의 블록체인만을 유지할 수 있도록 하는 것.
• → consensus에 도달하지 못해, 무한 교착상태에 빠질 수 있음
• Liveness: 단 하나의 consensus에 도달하지 못하더라도, 불완전한 합의를 우선 진행하여 지연없이 새로운 블록을 계속 생성할 수 있는 것.
• → fork가 발생하여 이중지불문제를 야기할 수 있음

FLP inpossibility로 인해, 이 두 속성이 모두 충족되기 힘들기 때문에, 각 블록체인들은 이 두 속성의 비중을 조절하여 체인의 특성을 결정함.

 

---

Casper FFG

32block(1 epoch)마다 블록을 Finalize시키는 알고리즘

ETH1(Before The Merge)에서의 Casper FFG

Casper FFG는 이더리움이 PoW인 시절(ETH1)에도 존재하던 프로토콜이었는데, 원래는 그러한 Nakamoto Consensus에 의해 발생한 여러 Fork 중 Canonical Chain을 결정하기 위해 블록을 Finalize시켜 해당 블록을 checkpoint로 쓰기 위해 위해 사용되었다.

따라서, 이로 인해 51%공격 등의 공격이 발생한다고 해도, 체크포인트 이전의 블록은 수정하지 못하도록 하여 블록체인을 보호한다.

합의의 과정에서, 총 Staking Amount중, 자신의 예치금(deposit)이 차지하는 지분만큼 의결권을 행사할 수 있으며, 이 과정에서 전체 Validator의 $\frac{2}{3}$만큼 투표를 받으면, Supermajority Link로 인정받을 수 있으며, 이 Link와 연결된 checkpoint가 다음 checkpoint가 되는 구조이다.

ETH2 (After The Merge)에서의 Casper FFG

Slot, Epoch

The Merge이후, ethereum에서는 block의 개념보다, slot, epoch이라는 개념을 주로 사용하게 된다. 자세히 살펴보면, 1개의 블록(block)은 1개의 슬롯(slot)이라는, 12초의 단위시간으로 표현되며, 이러한 슬롯이 32개 모여 에폭(Epoch)이라는 384초(6.4분)의 단위시간으로 표현된다.

Casper FFG

Casper FFG는 매 32슬롯(1에폭)마다 여러 포크 중 하나의 포크를 선택하도록 하는데, 부모 체크포인트가 여러 자손 체크포인트 중 하나를 선택하도록 하는 것이 Casper FFG의 역할이다.

---

LMD GHOST

(Last Message Driven Greediest heaviest Observed SubTree)

네트워크 지연 등으로 인해 fork발생 시, fork를 선택하는 알고리즘

참조: Combining GHOST and Casper

Message = Attestation message

Fork가 발생했을 때, 어떤 블록을 기존 체인에 연결할지, Attestation Message를 통해 투표하는 프로토콜.

Combining GHOST and Casper

위 그림에서 사각형으로 표현된 것이 block(또는 slot), 원으로 표현된 것이 Message.

가장 많은 Last Attestation Message가 지지하고 있는 block이 인정되게 된다.

Last Attestation Message?

→ 그림에서 보이는 모든 원들을 말한다. 즉, 몇 번째 블록인지와 상관 없이, 모든, “가장 최근”의 Attestation Message.

이를 통해, 블록체인의 Safety를 어느정도 보장하게 된다.

---

Gasper

위에서 본 것과 같이, Casper FFG와 LMD Ghost는 모두 결국 Fork중, 어느 Fork를 인정할지를 선택하는 프로토콜이다. 그럼, 왜 이 둘을 구분하여 사용할까.

slot과 slot간의 관계 즉, slot 단위에서 발생하는 fork에 대하여 LMD Ghost에 의해 하나의 fork로 합의된다.

이렇게 만들어진 epoch은 Casper에 의해 체크포인트 블록을 연결(또는 확정)하는 단위로 사용된다. 즉, epoch과 epoch의 관계를 Casper를 통해 결정짓는다.

이러한 epoch과, slot의 개념이 있는 것은 알겠는데, 그래서 어떤 과정을 통해 검증(Validate)를 하는 것일까?

Committees

참조: DSRV Research

1. 매 slot마다 하나의 Validator집단을 랜덤하게 만든다.
2. 각 집단을 Committee(위원회)라 부른다.
3. 각 위원회에서 랜덤하게 한 명의 리더를 선출하여 이 리더는 블록을 제안한다.
4. 블록 제안자를 포함한 위원회의 모든 validator는 블록을 검증한다.
5. 한 에폭은 32개의 슬롯으로 이루어져있기 때문에, 전체 validator 집단을 32개로 랜덤하게 쪼개 슬롯에 배정하여 모든 validator가 한 epoch에서 validating에 참여할 수 있도록 함
6. 한 epoch이 끝나면, 다시 랜덤하게 commitee를 구성하여 위의 과정을 반복한다.

Validate (Block 검증)

LMD GHOST프로토콜에서, 한 명의 block proposer가 해당하는 committee에 블록을 제안하면, 해당 committee를 구성하는 validator들은 블록을 확인하고, 블록에 대한 Attestation Message를 broadcast한다. 이러한 Attestation Message를 통해 지지되는 Fork마다 LMD GHOST점수가 매겨지고, 다음 블록 생성자는 어떤 fork 위에 블록을 생성해야 하는지 결정하게 된다.

위에서 Finalize라는 개념이 등장했었는데, 이는 체크포인트를 확정짓는 과정에 속하게 된다. 여기서, 체크포인트는 각 epoch의 첫 번째 슬롯의 블록으로 설정하여 Finalize과정을 거치도록 한다. 이를 더 자세히 뜯어보자.

class AttestationData(Container):
    slot: Slot # attestation message 전파하는 slot number
    index: CommitteeIndex # validator가 속한 commitee number
    beacon_block_root: Root # fork결정에 대한 attestation message 즉, LMD GHOST
    source: Checkpoint # Casper FFG vote: last justified epoch's first block
    target: Checkpoint # Casper FFG vote: last epoch's first block

위의 코드는 Validator가 committee에 broadcast하는 Attestation message의 구조이다.

source와 target, 그리고 beacon_block_root가 중요한 내용인데, source는 가장 최근에 justificate된 즉, 현재 epoch이전에 인정된 epoch의 첫 번째 블록(체크포인트)를 의미한다. target은 이번 그 체크포인트의 다음 epoch의 체크포인트라고 생각되는 block을 가리킨다. 이를 통해, Casper FFG투표(Supermajority vote)를 진행할 수 있으며, BPFT(비잔틴 장군 문제)에 따라, $\frac{2}{3}$이상의 validator가 동의하면, epoch의 상태가 justified로 변한다. (여기서, justified는 finalized와 다른 개념으로, Finalized되기 이전의 상태를 말한다.)

그렇다면, Finalize는 어떤 과정을 거쳐 진행될 수 있을까?

1. Epoch0과 Epoch1의 checkpoint간 연결이 justified되었다고 하자.
2. Epoch2에서 블록을 검증하는 validator들이 Epoch1과 Epoch2의 Supermajority Link를 지지하는 투표를 한다.
3. 이 투표 비율이 전체 validator 수의 $\frac{2}{3}$이 되면, Epoch1과 Epoch2의 체크포인트 사이에 Supermajority Link가 생성되고, 이 Link가 Justified된다.
4. 이 과정을 통해, Epoch1은 Epoch0과 Epoch2 모두로부터 Supermajority Link가 생성되어 그 결과, Epoch1에 있는 체크포인트가 Finalize되어 더 이상 변경할 수 없게 된다.

이렇게 Casper FFG와 LMD GHOST가 합쳐져 Gasper가 만들어지게 된다.

---

추가적인 궁금증🤨

Fork가 발생하는 이유.

Q. 블록체인에서 Fork가 발생하는 이유를 두고, 51%공격, 그리고 네트워크 지연 등 이유로 Fork가 발생하는 것으로 알고 있는데, 한 Slot당 하나의 Committee가 구성되고, 한 Committee에서 한 Proposer가 block을 제안하는 구조에서, 대체 왜 Fork가 발생하는가?

A(Mentor Troy). 현재 이더리움 PoS에서 가장 흔히 fork (reorg)가 발생하는 이유는 네트워크 지연이라고 볼 수 있다. 예를들어, 1번 슬롯에서 A 밸리데이터가 정해진 시간 내에 N번에 해당하는 블록을 만들어서 전파해야하는데, 이 시간 내에 전달받지 못한 경우 이를 Missed로 처리하고 2번 슬롯의 밸리데이터가 만든 블록을 N번 블록으로 포함되게 된다. 그렇지만 일부 밸리데이터들은 A가 만든 블록을 수신했을 수도 있지만, vote를 받지 못했기 때문에 그 뒤로 이어나가지 않을 가능성이 크다. 이런 식으로 Reorg가 발생하곤 한다.

참고자료

https://arxiv.org/pdf/2003.03052

https://medium.com/curg/gasper-casper-ghost-5aa9c226265c