Proof of Stake - Casper

지난 포스팅에서 이더리움의 POW 알고리즘인 Ethash에 대해 알아보았습니다.

이더리움은 작업을 증명하기 위해 소비되는 에너지 낭비를 줄이고, 중앙 집중화의 위험을 줄이기 위해 Proof of Stake 로 전환을 시도하고 있습니다. Proof of Stake는 코인을 보유하고 있는 사람이 새로운 블록 생성에 참여하는 방식입니다. 코인을 보유하고 있는 양에 따라 영향력이 달라지며, 작업 증명 방식에 비해 중앙화 비용이 훨씬 증가하게 됩니다.

하지만 단순히 중앙화를 위한 비용을 증가 시키는 것만으로는 블록체인의 안전성을 유지하는데 충분하지 않습니다. 비트코인의 경우 기존 블록체인을 대채하기 위한 새 블록체인 분기를 만드는데 전기세 이외에는 비용이 발생하지 않습니다. 따라서 분기를 만드는데 실패해도 기존 장비를 채굴하는데 사용해도 그만입니다. 이더리움의 POS에서는 블록체인을 의도적으로 분기(조작한 블록이 인정받도록 하는 행위)하는 경우 보유한 코인을 잃도록 설계해 공격자들이 함부로 블록체인을 조작할 수 없습니다.

이더리움의 POS 알고리즘인 Casper FFG는 아직 미완성으로 앞으로 해결해야 할 문제(경제적 인센티브 등)들이 남아있습니다. 새로운 알고리즘을 도입하는 경우 기존의 공격방식을 차단할 수 있지만 새로운 공격방식에 노출될 수 있기 때문입니다. 이번 포스팅에서는 Casper FFG의 기본 원리에 대해 다루어보겠습니다.

Casper Protocol

이더리움은 POS 도입 첫번째 단계로 Smart Contract으로 동작하는 Casper FFG를 발표했습니다. Casper FFG는 작업 증명과 지분 증명을 함께 사용하는 하이브리드 방식의 지분 증명 시스템 입니다. 이번 포스팅에서는 간단한 경우의 Casper Protocol이 어떻게 작동하는지 알아보겠습니다. 간단한 경우란 것은 검증자(Validator, POW에서의 Miner)가 변하지 않는 상황을 말합니다. 실제 상황에서는 검증자의 숫자, 영향력등이 매번 바뀌게 됩니다. 이 경우는 다음 포스팅에서 다루어보겠습니다.

The "checkpoint height" of a block with block height 100 * k is simply k

Casper는 모든 블록에 적용되지 않고 100블록(Epoch)마다 적용됩니다. 이 블록을 Checkpoint라고 합니다. Checkpoint의 높이는 블록의 높이(번호)와 비례합니다. 100 블록마다 생성되기 때문에 100으로 나눈 값을 Checkpoint의 높이 h(c) = k 로 표시합니다. Casper가 아직 미완성 상태이기 때문에 Checkpoint 사이의 블록 갯수는 바뀔 수 있습니다.

Proof of stake's security derives from the size of the deposits, not the number of validators.

Checkpoint는 검증자들의 투표를 통해 생성합니다. 검증자가 되기 위해서는 Casper Contract에 보증금을 예치해야합니다.

보증금은 블록 보상이나 패널티에 따라 변동할 수 있습니다. 이 보증금의 크기에 따라 투표의 가중치가 결정됩니다. 투표 결과는 검증자의 투표 수로 집계하지 않고 보증금 가중치에 의해 결정됩니다. 이번 포스팅에서는 모든 검증자들이 같은 금액의 보증금을 예치 한 것으로 가정하겠습니다.

검증자는 투표 메시지를 이더리움 네트워크에 전파해서 투표에 참여할 수 있습니다. 투표 메시지는 부모/자녀 Checkpoint의 해시, 부모/자녀 Checkpoint의 높이, 

그리고 이 네가지 요소를 개인키로 암호화한 서명이 포함됩니다.

Casper 투표과정

검증자의 2/3이 투표한 Checkpoint는 부모 Checkpoint와 Supermajority link로 연결되며, Justified로 상태가 바뀝니다. 이후 손자 Checkpoint가 선택되어 Justified 된다면 자녀 Checkpoint는 Finalized 되어 블록체인에 완전히 포함됩니다. 이 과정을 아래 슬라이드로 나타내보았습니다.

0123456789

Supermajority link는 부모/자식 Checkpoint를 연결합니다. 자식 Checkpoint는  부모 Checkpoint보다 항상 높이가 높아야 하지만 항상 바로 다음 Checkpoint일 필요는 없습니다.

Justified는 연결된 부모 Checkpoint가 있는 경우를 말합니다. 다시 말하면 검증자의 2/3이 선택한 Checkpoint라는 뜻입니다.

Justified된 Checkpoint는 자녀 Checkpoint가 투표를 통해 Justified 될 때 Finalized 되었다고 부릅니다.

두 Checkpoint가 서로 다른 가지에 위치하는 경우 "충돌한다"고 부릅니다. 즉, 부모/자식 관계가 아닌 경우를 말합니다.

어떤 Checkpoint가 Finalized 되면, 충돌하는 Checkpoint는 Finalized 될 수 없습니다. 투표할 때 어기면 되는 2가지 규칙 때문입니다.

Casper 2계명

검증자들은 투표할 때 절대 어기면 안되는 2가지 규칙이 있습니다. 이 규칙을 어길 경우 보증금을 몰수 당하기 때문에 악의적인 검증자가 새로운 분기를 만들어 내는 것이 어렵습니다. 비트코인이었다면 채굴 장비가 불타버리는 것과 같은 이치입니다. 이런 위험 요소 덕분에 이더리움의 POS의 안전성이 유지됩니다.

1번 조항은 같은 높이의 Checkpoint에 투표할 수 없고, 2번 조항은 Checkpoint의 범위가 겹치는 경우에 투표할 수 없다는 뜻입니다.

Casper 2계명을 무력화하기 위해서는 이더리움의 POW 블록 생산자의 51%가 장악 되어야 합니다.

Casper 정리

2/3의 검증자가 Casper 2계명을 어기지 않는다면, 다음의 내용을 알아낼 수 있습니다.

1. 두 개의 Supermajority link는 서로 다른 높이의 자식 Checkpoint를 갖는다.

2. 두 개의 Supermajority link는 다른 Supermajority link의 범위를 포함하거나, 범위 안에 들어가지 않는다.

이 두 가지 특징으로 다음 내용도 알아낼 수 있습니다.

3. 특정 높이에서 Checkpoint를 연결하는 Supermajority link는 많아야 1개 존재한다.

4. 특정 높이에서 Justified 된 Checkpoint는 많아야 1개 존재한다.

이 네가지 특징으로 2가지 법칙을 도출할 수 있습니다.

정리 1. 두 개의 충돌하는 Checkpoint는 둘 중 하나만 Finalized 될 수 있다.

정리 2. Finalized 된 체인을 연장하는 자녀 Checkpoint가 있는 경우 Supermajority link는 언제나 새로운 Finalized Checkpoint를 만들기 위해 생성될 수 있다.

              

즉, 정리 1의 경우는 왼쪽 그림처럼 2계명의 두 번째 조항에 의해 a(m) Checkpoint에서 a(m+1) Checkpoint로 투표를 할 수 없기 때문에 더이상 Finalized 될 수 없습니다. 하지만 정리 2에 의해 Finalized 된 체인을 연장하는 경우에 a(m)을 Finalized 할 수 있습니다.

Casper에서 채굴 할 분기를 선정하는 방법

기존 POW 방식에서는 가장 긴 체인을 선택해 블록을 이어나가면 되었습니다. 하지만 POS에서도 기존 방식을 사용할 수 없습니다. 검증자들이 가장 긴 체인에 투표하지 않고 다른 분기에 투표를 하는 경우에 문제가 발생하기 때문입니다. 채굴자들은 가장 긴 체인에 채굴을 계속 이어나가기 때문에 가장 긴 체인의 Checkpoint에 투표하기 위해서는 2계명을 깨야만 합니다. 따라서 Casper에서는 Justified 된 Checkpoint를 포함하는 가장 높은 체인을 선택합니다.

아래 링크 덕분에 본 포스팅을 작성할 수 있었습니다. 감사합니다.

Casper the Friendly Finality Gadget

Casper Overview by Jung-Ho Kim

캐스퍼(Casper): 이더리움(Ethereum)의 지분증명(PoS) 방식의 합의 알고리즘 by Younghoon Moon

Ethereum PoS Overview: Casper FFG