[블록체인] - 이더리움_Consensus

  지난 글까지는 이더리움의 Smart Contract와 DApp에 대해서 정리해 보았다. 이번 정리글에서는 이더리움의 Consensus 과정에 대해서 정리해 보려고 한다.

---

1. 이더리움의 PoW와 PoS

 이더리움은 원래 비트코인과 동일한 PoW(작업증명) 합의 프로토콜을 사용해왔다. 그러다가, 2022.09 The merge라는 이름으로 대규모 업데이트를 진행한 뒤, PoS(지분증명) 합의 프로토콜로 변경되었다.

 

 Pre-Merge(PoW 사용 시기)에는 비트코인과 동일하게 block header 안에 difficulty와 mixHash 필드가 존재했다. 이는 PoW 난이도 계산과 검증을 위한 필드들이었다. 하지만, Post-Merge(PoS 전환 이후)에는 해당 필드들이 빠지고 대신 PoS에서 필요한Consensus Layer가 추가된 것을 확인할 수 있다. Consensus Layer에 대해서 살펴보면 다음과 같다.

• slot: PoS에서 블록 제안이 이루어지는 12초 간격의 시간 단위
• parent-root: 이전 블록의 헤더(root)
• state-root: 이더리움 전체 상태를 저장하는 Merkle Patricia Trie의 root
• signature: 블록 찬성 의지를 밝히는 서명이 들어간다.
• randao: validator를 어떤 슬롯에 배치시킬지 정하는 random #
• graffiti: 블록 제안자가 넣을 수 있는 임의의 문자열
• deposit-root: Validator들이 ETH를 예치(deposit)한 기록의 Merkle root

- PoW Pros and Cons

 다음으로 PoW의 장단점에 대해서 정리해 보려고 한다. 

 

• Pros
  • PoW는 Neutral하다. 즉, 예치를 할 필요가 없다는 뜻이다. 그렇기에 보상도 0에서 쌓여가는 구조를 가진다.
  • PoW는 비트코인과 수년간 보안성과 탈중앙화 측면에서 검증이 되어왔다.
  • PoS와 달리 비교적 구현이 쉽다.
• Cons
  • PoW는 너무 많은 에너지를 쏟아야 하며, 초기 투자 비용도 매우 크다.
  • PoW에서 채굴을 원한다면 전용 장비가 필요하다.
  • 계속해서 computation(Hash power)를 늘려야하기 때문에, 특정 mining pool이 지나치게 커지면 네트워크를 잠재적으로 지배할 수 있어 탈중앙화에서 멀어질 위험이 있다.

---

2. PoS

 이제 PoS에 대해서 자세히 정리해 보려고 한다. PoS는 분산된 노드들이 블록체인 상태에 동의할 수 있도록 하는 프로토콜과 보상, 경제적 아이디어가 합쳐진 메커니즘이다. 이더리움은 이러한 Proof-of-stake-based 합의 메커니즘을 사용하는데, 이 메커니즘의 보안은 rewards와 penalties로부터 나온다.

 

 프로토콜에는 validator가 어떻게 무작위이면서도 공정하게 선정되는지, 트랜잭션과 제안된 블록에 대한 vote가 어떻게 이루어지는지 나와있다. 또한, validator가 부정행위를 했을 때 어떤 식으로 처벌되는지에 대한 방법도 이미 대비되어 있다.

 

 비트코인과 마찬기지로, 블록이 분기되는 fork 상태가 발생하긴 하지만, 거의 드물게 일어난다. 그렇지만 이에 대한 방책도 이미 마련되어 있다.

 

 PoS에서 분기가 잘 일어나지 않는 이유는 간단하다. 12초마다, 즉 1 슬롯마다 랜덤으로 1명의 block propser가 선택된다. 슬롯마다 하나의 블록만 제안되기 때문에, 이론상 분기가 일어날 일은 없다. 그렇지만, 다음과 같은 상황에서 분기가 발생할 수 있다.

• 선택된 block proposer가 offline일 경우
• 선택된 block proposer가 개인적인 이유로 블록을 제안하지 않은 경우
• 선택된 block proposer가 공격자인 경우
• 네트워크 지연이나 네트워크 파티션 때문에 블록이 일부 validator에게 도착하지 않고 해당 validator가 바로 다음 block proposer가 된 경우

 위와 같은 상황을 대비하기 위해서, PoS에도 합의 프로토콜이 필요했다.

 

---

3. Gasper(Casper FFG + GHOST)

 본격적으로 PoS의 합의 프로토콜을 정리하려고 한다. PoS의 합의 프로토콜은 Gasper라고 부른다. 이는 Casper FFG(Friendly Finality Gadget) 방식과 GHOST 방식을 합친 것으로, 위에서 정리한 분기가 일어났을 때 필요한 합의 프로토콜이다.

 

 이더리움에서 과거 PoW 방식에서는 비트코인과 같이 longest-chain rule을 사용해왔다. 그렇지만, 이더리움은 PoS를 사용하기 때문에 분기 상황 시 합의 프토토콜도 업데이트되어야 했다. 업데이트된 방향은 longest-chain보다는 weight, 즉 더 무게가 무거운 체인이 canonical chain이라고 받아들여지는 방식이다.

 

 Casper FFG와 GHOST가 어떤 방식으로 이더리움에서 합의 프로토콜을 지키는지 간단히 정리하면 다음과 같다.

• Casper FFG: 어떤 블록이 finalized된 상태로 선택될지 투표로 정하고, 네트워크가 동일한 체크포인트를 기준으로 상태를 동기화할 수 있게 한다.
• GHOST: fork(분기)가 일어났을 때, 어떤 chain이 canonical chain인지 결정하기 위한 알고리즘이다.

 이러한 Gasper 방식을 통해 validator들에게 어떻게 보상하고 penalty를 줄지 정할 수 있다.

 

- Finality

 Casper FFG와 GHOST 방식에 대해서 더 자세히 정리하기 전에, 블록의 상태 중 하나인 Finality에 대해서 정의해야 한다.

 

 블록이 제시되었을 때, 블록체인에 포함되기 위해서는 블록은 다음 두 단계를 통과해야 한다.

• 모든 Validator 중 2/3가 제안된 블록에 대해서 찬성해야 한다. 2/3가 찬성했다면 이 블록은 justified 상태가 된다.
• 어떤 체크포인트 블록 A가 justified이고, 그 다음 블록 B가 다시 2/3 이상 찬성을 얻어 A위에 쌓이다면, A는 finalized 상태가 된다.

 즉, finalized 되었다는 것은 해당 블록이 canonical chain에 사실상 되돌릴 수 없게 고정되었다는 의미이다.

 

 이러한 finality 특징으로 인해 다음 두 공격에 대해 방어를 할 수 있다.

• Slashing: active하게, 즉, 규칙을 능동적으로 위반한 경우이며, 해당 validator를 제거한다.
• Inactivity Leaks: passive하게, 즉, 규칙을 어쩔 수 없이 위반한 경우이며, 해당 validator의 stake에서 일정 ETH를 환수한다.

 차례대로 그 이유를 살펴보자.

 

 2/3 이상의 동의를 얻어야 canonical chain에 올라갈 수 있기 때문에, 공격자는 다음과 같은 상황에 놓이게 된다.

• 전체 validator 중 2/3를 소유하거나 조작할 수 있어야 한다.
• 잘못된 체인을 finality까지 밀어붙이려면 결국 1/3 ETH를 스스로 파괴해야 한다.

 즉, 공격자는 시스템을 공격하기 위해서 weight를 늘려야한다. weight를 늘리기 위해서는 새로운 체인을 강제로 만들거나 두 체인을 동시에 finality로 추진해야 한다고 가정해보자.

 

 즉 분기가 일어난 두개의 각 블록이 2/3 이상의 찬성이 필요한 상황이다. 그런데, 2/3 + 2/3 = 4/3으로 이미 1을 넘어간다. 즉 전체 validaotr의 투표수를 초과하게 된다. 이 말은 두 체인에 동시에 2/3의 validator가 투표했다는 의미이며, 이는 최소 1/3이 중복 투표를 했다는 의미이다.

 

 이더리움 PoS에서 validator는 반드시 서명을 남긴다. 따라서 누가 중복 투표를 했는지 완전히 투명하게 드러나며, 중복 투표는 명백한 규칙 위반이다. 이는 Slashing에 해당하며, 최소 1/3의 validator는 즉시 slash되어 stake를 잃고 퇴출당한다. 결국 공격자는 최소 2/3을 유지할 수도 없게 되고, 공격 역시 실패하게 된다.

 

+) 2022년 5월 당시 계산되 자료에 따르면 실제로 이 공격을 강제로 시도하려면 약 100억 달러 이상의 ETH를 태울 각오가 필요하다고 논문에 기재되었다.

 

- Inactivity Leak

 Gasper는 plausible liveness 상황을 보장한다. 즉, 전체 validator의 2/3가 정직하게 투표하고 있다면, 공격, 지연, 일부 validator의 오프라인 같은 외부 요소와 상관없이 체인은 계속해서 finality를 만들 수 있어야 한다.

 

 그런데 일부 validator가 네트워크 단절이나 장애로 인해 어쩔 수 없이 규칙을 지키지 못하는 상황이 장기간 지속된다면, 더 이상 finality를 만들지 못하게 되고, 이는 곧 liveness 문제로 이어질 수 있다.

 

 이때, 이더리움 PoS는 Inactivity Leak을 통해 오프라인 상태인 validator들의 stake를 서서히 줄인다. 지분이 줄어들면 온라인 상태인 validator가 다시 전체 지분 중 2/3이상을 차지하게 되고, 그러면 체인은 다시 finality를 만들 수 있어 liveness를 유지하게 된다. 즉, 오프라인 validator의 지분이 점차 감소하면서 정상적으로 투표하는 validator 집단이 전체 2/3을 회복하는 구조이다.

 

 이렇게 아무리 어쩔 수 없이 규칙을 위반했다고 하더라도 penalty를 주지 않으면 블록체인이 다시 finality를 만들 수 없는 상태가 길어질 수 있다. 이런 상황이 지속되면  공격에 취약해지기 때문에, Inactivity leak 방식을 통해 비활성 validator의 stake를 조금씩 감소시켜 체인이 빠르게 정상 liveness를 회복하도록 돕는다.

 

- Fork Choice: GHOST

 이제 본격적을 합의 프로토콜이 이루어지는 과정을 살펴보려고 한다. 먼저, 분기가 발생한 경우 GHOST 알고리즘을 사용하는 경우이다.

 

 이더리움에서 대체로 분기는 다음과 같은 상황에 발생한다.

• P2P 네트워크 상태에서, 특정 validator의 link가 갑자기 끊겼다.
• 그 사이에 새로운 블록 A가 생성되어 전파되었고 일부 validator들에 의해 확정(attested)되었다.
• 재연결 후, 하필 그 validator가 다음 block proposer가 되었다.
• 이전에 생성된 블록 A를 보지 못했기 때문에 A의 부모 블록에 자신의 블록을 이어붙여 새로운 체인 분기를 만든다.

 이러한 경우, GHOST 알고리즘을 통해 어느 쪽 chain이 canonical chain이 될지 결정해야 한다.

 

 정확히 정의하면, 이더리움의 PoS는 LMD-GHOST 방식을 이용한다.

• GHOST(Greedy Heaviest SubTree)는 말 그대로 여러 체인 중 가장 무거운 서브트리 방향으로 내려가 canonical chain을 선택하는 방식이다.
• LMD(Last Message Driven)는 validator 한 명이 여러 번 attestation을 하더라도, 그 중 가장 최근 메시지만 weight로 인정한다는 의미이다. 즉, weight는 블록의 수가 아니라 validator들의 최신 attestation이 만든 투표량으로 계산된다.

결국, LMD-GHOST는 가장 많은 validator의 최신 attestation이 몰려 있는 방향을 canonical chain으로 선택하는 fork-choice 규칙이다. 다음 그림 예시를 살펴보자.

 그림에 대해서 설명하면 다음과 같다.

• 블록 B에서 분기가 발생했다.
• LMD-GHOST 규칙에 따라 B의 자식 중에서 각 서브트리에 최신 attestation을 보내고 있는 View of Validator 수를 비교한다.
• C와 D 중 선택해야 하는데, B쪽에는 View of Validator가 2, C쪽은 5이기 때문에 C를 선택한다.
• C에서 다시 분기가 발생했고, E와 F 중 선택해야 한다.
• F쪽은 View of Validator가 2, E쪽은 3이기 때문에 E쪽이 canonical chain으로 선택된다.

LMD-GHOST의 수도코드를 살펴보면 다음과 같다.

B <- B_g (B_g = Gensis Block)
M <- the most recent attestations of the vlidators(one per validator)
while B is not a leaf block in G do
	B <- arg with max w(G, B', M)	# B' = child of B
    # w(G, B', M): the sum of the stake of the validators whose last attstations in M is
    # to B' or descendants of B'
return B

코드에 대해서 정리하면 다음과 같다.

• B에는 제네시스 블록, 즉 이더리움의 맨 처음 블록을 넣어준다.
• M에는 validator들의 가장 최신 투표(각 validator당 하나씩)를 대입한다.
• B가 트리 G에서 리프 블록이 아닐 때까지 다음 과정을 반복한다
  • 현재 B의 자식 블록들 B' 중에서 w(G, B', M) 중 가장 표가 많은, 즉, 무게가 가장 많이 나가는 블록을 선택해서 B에 넣는다.
• 그 후, B가 리프블록에 도달하면 B를 반환한다.

- Casper FFG

 다음으로 알아볼 이더리움에서 사용되는 합의 프로토콜 방식 중 하나는 Casper FFG이다.

 

 그 전에, slot과 epoch에 대해서 정리를 먼저 해야 한다. 각 정의는 다음과 같다.

• slot: 12초 간격 단위
• epoch: 1epoch 당 32 slot으로 이루어져 있다. 약 6분 24초 정도이다.

 이때, 각 에폭의 첫 번째 슬롯에서 제시된 블록을 "checkpoint" 또는 "epoch boundary block"이라고 한다.

 

 그리고, slot 마다 블록이 제시되는데, 블록을 제시하는 block proposer는 validator들 중 랜덤하게 선택된다고 정리했다. 더 자세히 정리하면, block propser는 다음과 같이 선정된다.

• 매 slot마다, committe(validator의 랜덤 부분집합)에서 validator가 선정된다.

 이때, committee라는 집단으로 나누는 이유는 네트워크 부하를 관리하기 위해서이고 전체 validator가 모든 slot마다 attestation을 하지 않아도 되도록 하기 위해서이다.

 

 그럼 committee로 선정된 validator들은 한 슬롯에서 어떤 일을 하는지 한 번 알아보려고 한다. 총 두 가지 일을 하는데 다음과 같다.

1. 현재 slot에 제안된 블록에 대해서 찬/반 투표
2. 이전 epoch에 체크포인트, 현재 epoch에 체크포인트 총 2개의 체크포인트 투표로, (A, B) 형태이다.
   • A = 마지막으로 justified된 checkpoint, B = 현재 epoch에서의 checkpoint

 

 Validator들이 하는 일에 대해서 알아보았으니 이제 본격적으로 Casper FFG가 어떻게 동작하는지 정리해보겠다. 다음과 같이 진행된다.

1. 슬롯에 committee들이 선정되고, committee 중 맨 앞의 validator가 block proposer가 된다.
2. committee 내 다른 validator들은 block proposer가 제안한 블록에 대해 투표한다.
3. 또한, validator들은 각자 생각하기에 옳다고 생각하는 이전 epoch의 checkpoint에 대한 투표, 현재 epoch에 대한 checkpoint에 대한 투표를 진행한다.

이때, 이전 epoch에 제안됐던 checkpoint는 justified된 상태라고 하고, 현재 epoch을 지나면서 해당 checkpoint가 다시 2/3 이상 동의를 얻는다면, 해당 블록은 finalized 상태가 된다. 또한, 현재 epoch이 진행되면서 현재 epoch의 checkpoint가 2/3 이상 동의를 얻는다면 해당 checkpoint는 justified 상태가 된다.

 

 즉, 간단히 말해서, 자식 checkpoint가 justified 상태가 되면, 부모 checkpoint는 finalized로 업그레이드 된다.

 

 위와 같은 과정을 반복하며 finalized 블록을 확장하는 방식으로 이더리움 블록체인은 liveness를 유지한다.

 

 이때, justified와 finalized 상태를 만들기 위한 조건을 정리하면 다음과 같다.

• Justified
  • 어떤 블록 B에 대해서 B의 조상인 A에 대해서 (A,B)가 2/3 이상이 나온다면 B는 justified 된 블록이라고 한다.
• Finalized
  • 어떤 블록 B에 대해서 B가 justified 된 상태이고, B의 자식 C(height(C) = height(B)+1)에 대해서 (B, C)가 2/3 이상이 나온다면 B는 finalized 된 블록이라고 한다.

 

- Validator 선정 방식 - RANDAO

 그럼, Validator가 block proposer로 선정되는 방식에 대해서 더 자세히 정리해보려고 한다. 중요한 것은, 공평하고 랜덤하게 선택되어야 한다는 점인데, P2P 네트워크 특성상 서로를 신뢰하지 못한다. 그렇기 때문에 RANDAO라는 난수 생성 메커니즘을 사용한다.

 

 RANDAO는 pseudorandom process이며, 매 epoch마다 전체 validator 집합을 섞어서(shuffling) 각 slot의 block proposer 1명과 committee를 할당하는 데 사용된다. 이렇게 생성된 난수는 모든 validator가 동일하게 계산할 수 있으며 조작이 불가능 하다.

 

 이 방식을 통해 모든 validator가 동일한 확률로 block proposer로 선정될 수 있고, committees 또한 균등하게 구성될 수 있다.

 

 RANDAO에 대해서 더 자세히 설명하면, 다음 그림을 참고하면 된다.

 모든 참여자가 RANDAO를 확인할 수 있으며, 여러 validator가 순차적으로 난수 생성에 기여한다는 점에서 그림처럼 shuffle을 돌려가며 섞는 구조로 이해할 수 있다.

 

 실제로는 validator가 동일한 RANDAO를 넘기는 것이 아니라 각 validator가 자신의 서명의 해시값과 RANDAO를 XOR 연산을 한 뒤 새로운 RANDAO를 만든다.

 

 이 연산이 여러 validator에 의해 반복되며, 최종적으로 이를 사용해 proposer 선정 및 committee shuffling이 이루어진다.

 

- Voting Rule

 Casper FFG에서 투표를 할 때, 규칙이 존재한다. 2가지 규칙이 존재하는데 다음과 같다. 지금은 제안된 블록에 대한 찬반 투표가 아닌 checkpoint에 대한 투표에 대해서만 다룬다.

• 같은 height를 가진 블록들에 대해 중복 투표를 하면 안된다.
• Overlapping(=surround) Vote를 하면 안된다.

 첫 번째 규칙은 다음과 같은 경우이다.

 그림에 대해서 설명하면 다음과 같다.

• 체크포인트에 대한 투표로, 한 명의 validator가 (S1, T1), (S2, T2)로 투표를 진행했다.
• 이때, T1과 T2는 같은 height에 있다.

 이러한 중복 투표를 막아야하는 이유는, 동일한 height의 두 checkpoint에 투표하는 것은 validator가 두 개의 경쟁 fork에 동시에 투표한 것과 동일한 행동이기 대문이다. 이를 허용한다면 두 개의 canonical chain이 동시에 생기는 상황이 일어난다.

 

 두 번째 규칙은 다음과 같은 경우이다.

 그림에 대해서 설명하면 다음과 같다.

• 한 명의 validator가 (S1, T1)에 대한 투표를 한 후, (S2, T2)에 대한 투표를 진행한 것이다.

이런 식의 투표를 인정하게 된다면, finalized된 블록을 더 이어갈 수 없어 liveness를 유지할 수 없다.

 

따라서, Casper FFG는 위의 두 가지 투표 규칙을 정하고 위반한 경우 slashing을 적용한다.

---

4. Safety proof & Liveness proof

 이더리움의 Casper FFG는 Safety와 Liveness를 만족한다. 이 두 특징에 대해서 정리하면 다음과 같다.

• Acccountable Safety: 만약, 두 conflicting 블록이 finalized 되었다면, 최소 1/3이 중복 투표를 한 것이고, 명백한 규칙위반이며, 모든 투표는 서명이 남기 때문에 어떤 validator가 규칙을 깼는지 명확히 특정할 수 있다. 해당 validator들은 slashing 당한다.
• Plausible Liveness: 2/3 이상의 정직한 validator가 존재하는 한, 새로운 블록은 justified, finalized되며, 체인은 계속 앞으로 나아갈 수 있다.

그럼, Casper FFG가 위 두 특징을 어떻게 만족하는지, 그리고 위의 두 투표 규칙이 왜 생겼는지 다음 두 증명을 통해 한 번 이해해보자.

- Safety proof

 먼저, 다음 그림을 한 번 참고해보자.

 이 Safety proof를 통해 왜 두 개의 규칙(중복 투표 금지, overlapping 투표 금지)이 생겼는지 알아보자.

 

 그림에 대해 설명하면 다음과 같다.

• 만약, A와 B가 conflicting 블록이고, 둘 다 finalized 되었다고 가정해보자. 그럼 다음과 같은 경우가 발생한다.
  • Case1: height(A) = height(B)
    • 이 경우, A와 B는 각각 모두 validator 중 적어도 2/3이 중복 투표한 결과이다.
    • 그렇기 때문에, 적어도 1/3의 validator는 규칙을 어긴 것이므로 slashing 해야 한다.
  • Case2: height(A) < height(B)
    • 이 경우, A가 finalized 되기 위해서는 자식인 C에 대해 2/3 이상의 validator가 (A, C) 형태로 투표했어야 한다.
    • B가 finalized 되기 위해서는 B0, B1,... 부터 이어온 순서가 있을 것이다.
    • 그 중, A의 height보다 큰 Bm이 있다고 가정해보자.
    • n = m-1에 대해서 (Bn, Bm)에 대한 투표가 2/3 이상 등장했고, Bm이 justified 되었다고 가정하면,
      
      • height(Bn) = height(A) 라면, A와 Bn은 서로 다른 체인 상의 conflicting checkpoint이다
        • 따라서, Double vote에 해당하므로 slashing되어야 한다.
      • 만약, height(Bm) = height(C) 라면, Bm과 C 역시 서로 다른 체인 상의 conflicting checkpoint이므로, double vote 상황이다.
      • 따라서, B(n) != A, B(m) != C이어야 하므로 위 그림과 같은 모습이 나타난다.
        • 이 구조는 overlapping(surround) 구조이다.
    • 따라서, Case2를 막기 위해서는 surround vote도 금지시켜야 한다.

 결론적으로, Safety Proof를 통해

1. Case1: Double Vote 위반
2. Case2: Surround Vote 위반

 따라서 두 규칙을 강제함으로써 Casper FFG는 Accountable Safety를 보장한다.

 

 

- Liveness Proof

 다음 그림을 한 번 살펴보자.

 그림에 대해서 설명하면 다음과 같다.

• P0를 justified 블록이라고 하고, Q보다 엄청나게 높은 블록이라고 가정하자.
• 그리고 P0의 후손들 중에서 height(Q)보다 높은 어떤 블록 P1을 선택한다고 하자.
• 이때 P1에 대해 P0, P1 형태의 투표를 validator 중 2/3 이상이 수행하면, P1은 justified 되고, P0는 finalized된다.
• 그 다음 동일하게 P1 자식 P2를 선택하여 (P1, P2) 투표를 2/3 이상이 된다면, P2는 justified 되고, P1은 finalized 된다.

 이렇게 validator 다수가 정직하게 하나의 체인을 선택해 투표를 계속 이어가는 한, 항상 새로운 checkpoint를 선택하여 justify하고 finalize할 수 있다.

 

 즉, 어떤 시점 Q가 있다 하더라도 height(Q)보다 높은 블록을 선택하면 됙, 이는 규칙 위반에 해당하지 않는다.

 

 따라서 규칙을 위반하지 않으면서도 2/3 이상의 정직한 validator가 존재한다면 이더리움 블록체인은 언제든 새로운 finalized 블록을 만들어낼 수 있고, Casper FFG는 Liveness를 만족한다.