Casper FFG Overview
Changelog
- Glossary.epoch: epoch length 수정, vitalik 제안 추가
Intro
이더리움은 설계 단계에서 부터 합의 알고리즘을 PoW가 아닌 PoS를 사용할 계획이었습니다. Casper FFG는 기존의 PoW 합의 알고리즘 위에서 Economic finality를 제공해 준다는 의미에서 Casper the Friendly Finality Gadget 라는 이름을 붙였습니다. 최근 논의되는 Full Casper Chain v2에서는 Casper와 샤딩을 함께 도입하여 비콘 체인(beacon chain)에서 Full PoS를 적용하려는 시도가 보입니다. 이더리움 재단에선 비콘 체인이 기존의 메인 체인을 대체하여, 이더리움에서 PoW 합의 알고리즘을 제거하여 PoS만을 적용하려는 계획을 가지고있는 것 같습니다.
물론 Full Casper Chain의 설계와 스펙은 추후 변경될 여지가 있습니다. 하지만 핵심인 Casper는 충분한 public review를 거쳤고, 더이상 논의될 부분은 많지 않아 보입니다. Vitalik과 Virgil이 작성한 Casper의 첫 번째 버전인 Casper FFG논문을 한글로 정리합니다.
Glossary
- Proposal mechanism: 블록 체인에 포함될 새로운 블록을 제안하는 방법입니다. 기존의 PoW 에 해당합니다.
- Casper: Proposal mechanism이 제안한 새로운 블록을 PoS 합의 알고리즘을 이용하여 Finalize 하는 프로토콜입니다.
- Validator: Casper의 합의 과정을 이루는 참가자입니다. 32 ETH를 Casper컨트랙트에 deposit한다면 누구나 validator가 되어 PoS에 참여할 수 있습니다.
- Dynasty: 합의에 참가하는 validator의 집합을 가리킵니다. dynasty에 누구나 참여하고 나갈 수 있기 때문에 동적인 validator의 집합입니다. dynamic validator set, active validator set 으로도 불립니다.
- 2/3 of Validators: validator의 숫자가 아니라 모든 validator가 deposit 한 Ether의 2/3 를 가리킵니다.
- Epoch: 연속된 50개의 블록들은 한 epoch에 포함됩니다. FFG에 반영된 것은 아니지만, epoch length를 exponential하게 증가시키자는 Vitalik의 제안이 있습니다.
- Checkpoint (block): 각 epoch들의 마지막 block을 가리킵니다. Genesis block 또한 checkpoint 입니다. (엄밀히 말하면, Casper FFG가 적용되는 시점의 블록일 것입니다.) Casper는 모든 블록들을 합의하지 않고 checkpoint들만 합의를 거쳐 finalize 합니다. Finalized checkpoint의 조상(ancestor) 블록들은 모두 암시적으로 finalized됩니다.
block chain, block tree, block height과 동일한 개념으로 checkpoint chain, checkpoint tree, checkpoint height이 있습니다.
(h(c) 는 checkpoint c 의 checkpoint height을 의미합니다.) - Conflicting checkpoints: 두 checkpoints는 다른 branch에 있을 때 conflict 합니다. PoW 블록체인의 Fork 가 일어난 경우와 동일합니다.
- Vote: PoS 합의를 이룰 때 사용하는 메시지입니다. validator는 두 checkpoints (source, target) 에 대해 target checkpoint는 source checkpoint의 자손(descendent)이 맞다고 생각하면 Vote 메시지를 RLP로 인코딩하여 Casper 컨트랙에게 전달합니다. (vote(vote_msg))
따라서 모든 이더리움 클라이언트들은 Vote 메시지들을 알 수 있습니다. 만약 Casper Commandments를 위반하는 Vote 메시지를 발견한다면, 이를 증거로 제출하여 해당 validator의 deposit을 slash 할 수 있습니다.
- Casper Commandments: Vote 메시지가 유효한 조건입니다. Casper Commandments를 위반하는 메시지를 보낸 validator의 deposit은 slash 됩니다.
- Supermajority link: 두 checkpoints (s, t) 간에 2/3 of Validators 이상이 Vote 를 했을 때 supermajority link가 존재합니다. 이 때 s 와 t 사이엔 100개 이상의 블록들이 존재할 수 있습니다. 즉, 여러 checkpoints를 생략할 수 있습니다. 이 때 s → t 를 이용하여 supermajority link를 표현합니다.
- Justified checkpoint: checkpoint c 는 아래 조건일 때 justfied 됩니다.
i) Genesis block 이거나
ii) justified checkpoint c` 와 c 사이에 supermajority link 가 존재하면
(c′ → c)
- Finalized checkpoint: Checkpoint c 는 justified 되었고, c → c′ 인 c′ 이 존재하고, c′ 이 c 의 direct child일 때 finalized 됩니다. direct child이기에 c′ 의 checkpoint height은 c 의 checkpoint height보다 1만큼 큽니다. (h(c′) = h(c) + 1)
Figure 3는 2개의 conflicting checkpoints를 보여주는 예입니다. a2 → a3이고, h(a3) = h(a2) + 1 이기 때문에 a2는 finalized checkpoint 입니다. 마찬가지로 b3 → b4 이고, h(b4) = h(b3) + 1 이기 때문에 b3 또한 finalized 되었습니다.
- Accountable Safety: 두 conflicting checkpoints가 동시에 finalized될 수 없습니다.
- Plausible Liveness: 적어도 2/3 of validators가 honest 하다면, 그리고 finalized checkpoint로 부터 children이 존재 한다면 supermajority link를 연결해 새로운 finalized checkpoint를 만들 수 있습니다.
Casper Commandments (slashing condition)
I 이 의미하는 것은, 동일한 checkpoint height의 다른 checkpoint를 target 으로 삼지 못하도록 합니다. 이로 인해 각 checkpoint height마다 유일한 justified checkpoint가 존재합니다. Figure 3 를 보면 ai, bj는 같은 checkpoint height에 위치하지 않는 것을 확인할 수 있습니다.
II이 의미하는 것은, checkpoint a_2 를 finalize 하는 Vote 메시지와 a_2 와 conflict 한 b_3 를 justify 하는 Vote 메시지를 동시에 보내지 못하도록 합니다. Figure 3 의 “violates II” 캡션이 a2 → a3 의 Vote span이 b2 → b3 Vote span안에 포함되는 것을 의미합니다.
이러한 Commandments를 위반한 것을 slashing condition을 충족한 것으로 간주하여 validator에게 패널티를 줍니다.
I 과 II 에 의해서 validator가 Slashing condition을 위반하지 않는 한 아래 특성 (i), (ii) 를 얻을 수 있고, (i), (ii) 에서 임의의 checkpoint height n 에 대한 특성 (iii), (iv) 또한 유추할 수 있습니다.
논문에선 이 특성들을 이용하여 Accountable Safety와 Plausible Liveness를 증명합니다. (하지만 이 글에서는 간략히 설명만 합니다.)
Accountable Safety
Casper FFG 가 동작하는 이더리움 클라이언트는 2개의 서비스를 추가적으로 재공해야 합니다. validator가 되고, Casper의 Vote 메시지를 보낼 수 있는 validator 서비스와 I, II 를 위반한 Vote 메시지들을 Casper 컨트랙에 고발하는 fisherman 서비스가 필요합니다. (Polkadot 의 fisherman과 목적이 유사하기에 제가 임의로 이름을 붙였습니다.) fisherman 들이 slashing condition을 위반하는 메시지들을 Casper 컨트랙의 slash(vote_msg1, vote_msg2) 함수를 이용하여 고발합니다.
동일한 checkpoint height에 있는 다른 두 checkpoint를 finalize 하는 supermajority link 는 I 을 위반합니다. 따라서 적어도 1/3 of validators 가 I 를 위반하였기에, 전체 validator deposit은 2/3 가 되어(slashing), vote 의 deposit의 합이 2/3 에서 1/2 로 감소합니다. supermajority link는 조건(2/3 of validators)을 충족하지 못하였기에 유효하지 않습니다.
(finalize 되는 시점과 slashing하는 시점에 의문을 가질 수 있습니다. c가 finalized 되는 정확한 시점은 c 의 direct child (c′) 가 justified 된 후 그리고 c′ 의 direct child (c′′) 가 proposed 된 이후에 finalized 됩니다. 즉, c′ 이후에 100 블록이 더 쌓여야 합니다. 따라서 slash condition 을 위반한 vote 들을 처리한 시간적 여유가 충분히 있습니다. 이 부분은 Dynasty 항복에서 자세히 다룹니다.)
Figure 3 는 height이 다른 a2 와 b3 가 동시에 finalized 되는 checkpoint tree를 보여줍니다. 이 때 a2 → a3 와 b2 → b3 가 동시에 존재하기 위해선 적어도 1/3 of validators가 II 를 위반해야 합니다.
Accountable Safety(책임있는 안정성?) 은 두 conflicting checkpoints가 동시에 finalized 되기 위해선 1/3 of validators가 slashing condition을 위반해야만 하기에, slashing 을 통해 supermajority link의 조건을 무효화시킬 수 있습니다. Casper 프로토콜을 위반하는 행위에 대해 반드시 처벌을 할수 있다는 의미에서 Accountable 이란 표현을 사용한 것 같습니다.
Plausible Liveness
I과 II를 위반하지 않는 한, 그리고 2/3 이상의 validators가 프로토콜을 따른다면, 언제나 새로운 checkpoint를 finalize 할 수 있음을 의미합니다. supermajority link가 더해지기 위해선 2/3 of validator가 필요합니다. checkpoint는 supermajority link에 의해 justified 되고, finalized 되기 때문에, 2/3 of validators가 I과 II 를 위반하지 않는다면, 언제든 supermajority link를 만들 수 있습니다.
Dynamic Validator Set, Dynasty
누구나, 언제나 32 ETH 이상을 deposit 하면 validator가 될 수 있습니다. 그리고 validator는 언제든 logout하여 deposit한 이더를 되찾을 수 있습니다. 합의에 참여하는 동적인 validator set 을 dynasty 라고 합니다. 이 때 block 의dynasty d는 지금까지 finalized된 조상 checkpoint들의 수 입니다. Epoch은 100개의 블록이 쌓일 때 마다 1씩 증가하고, checkpoint 또한 epoch의 마지막 블록이기에 finality 와 관계 없지만, dynasty는 finalized 될 때 마다 1씩 증가합니다.
Validator에 참여하기 위하여 deposit 메시지를 호출합니다. 이 때 validator는 곧바로 dynasty에 참가하지 않습니다. deposit TX가 포함된 dynasty를 D 라고 한다면, validator는 D+2 시점부터 dynasty에 합류하게 됩니다. 이 시점을 startDynasty라고 부릅니다. 마찬가지로 dynasty에서 나오기 위하여 logout() TX 를 보내면, 해당 블럭의 dynasty + 2 일 때 dynasty에서 나오게 됩니다. 이를 endDynasty라고 합니다. endDynasty 이후 약 4개월에 걸친 withdrawal delay가 지난 후 Validator가 되기위해 deposit했던 이더를 돌려받을 수 있습니다. 만약 withdrawal delay 이전에 I 혹은 II 를 위반한 증거를 발견하면 deposit을 slash 합니다.
Dynasty가 동적인 경우, Accountable Safety가 유효하지 않을 수 있습니다. I 혹은 II 를 위반하여 2 conflicting checkpoints c, c′ 가 생겼지만, dynasty가 완전히 다르다면 slashing할 validator가 없을 수 있습니다. 이를 보완하기 위하여 forward validator set, rear validator set 으로 구분하였습니다.
forward validator set 은 block dynasty d 가 startDynasty ≤ d < endDynasty 인 집합을, rear validator set 은 startDynasty < d ≤ endDynasty 인 집합을 의미합니다.
checkpoint 가 finalized 되면 dynasty 는 forward validator set 에서 rear validator set 으로 바뀌게 됩니다. 이제 dynasty 를 이용하여 supermajority link와 finalized를 다시 정의해야 합니다.
- front / rear validator set 모두 각각의 2/3 이상이 vote 해야 supermajority link가 추가됩니다.
- c → c′ 일 때, checkpoint c 가 finalized 되기 위해선 forward validator set 과 rear validator set 의 vote 가 필요합니다. 이 때 c를 justify 하는 vote 와 supermajority link c → c′ 를 만들기 위한 vote 는 c′의 direct child가 proposed 되기 전에 c′ 의 블록체인에 포함되어야 합니다. 즉, c′ 이후 100 블록 이내에 c를 finalize 하기 위한 모든 vote가 포함되어야 합니다. dynasty 가 d+1 으로 증가할 때 두 front validator set과 rear validator set 을 동시에 알아야하는대, 가장 활발하게 login상태인 시점이 c′ 이후 100 블록 이내이기 때문입니다.
Long range revision Attack
2/3 of validator가 dynasty에서 나온 후 약 4개월에 걸친 withdrawal delay이후 deposit을 다시 돌려받습니다. 이 때 Long range revision attack은 validator가 이더를 돌려 받고, 과거의 checkpoint부터 conflicting 한 checkpoint를 만드는 것을 의미합니다.
c′ 이후의 블록들은 c의 highest justified checkpoint이 생성된 시점 이후에 생성됩니다. 따라서 Long range revision Attack을 막기 위해서 노드의 local time, 블록의 timestamp, 그리고 최대 통신 지연시간 δ 를 이용합니다.
미래 시점에서 보낸 블록을 reject하고, δ 이전에 생성된 블록을 finalized checkpoint로 받아들이지 않도록 하여 Long range revision Attack을 막습니다.
Catastrophic Crashes
Dynasty가 일시적으로 offline 되어, 합의 과정을 이루지 못하는 상황이 발생할 수 있습니다. “inactive leak” 은 vote를 하지 않는 validator의 deposit을 조금씩 감소시키는 것을 의미합니다.
왼쪽 체인이 2/3 of validators A 가 vote하여 finalized 되었습니다. 이후 A 가 offline 된다면 해당 dynasty에서 A가 아닌 나머지 validators B는 당장은 supermajority link를 생성하지 못하지만 inactive leak에 의해 A의 deposit이 1/2 of B까지 감소한다면, 2/3 of validators는 B가 됩니다. 따라서 오른쪽 체인을 finalize 해서 A가 없어도 Casper가 올바르게 동작하도록 합니다.
마치며
이제 Casper 컨트랙 구현체인 simple_casper.v.py, Validator를 운영하는 가이드, 그리고 실제 클라이언트의 구현 내용들을 살펴보면 좋을 것 같습니다. 하지만 구현은 아직 마무리되지 않은 Full Casper Spec을 따르기 때문에, 스펙이 변경되면서 구현 또한 변할 수 있습니다.
