Jong-Ho Kim(Jason Kim)
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
*Note: 이 글은 서울대학교 블록체인 학회 디사이퍼에서 작성한 미디엄 아티클을 옮긴 글입니다. 이 글에서 설명하는 모든 내용은 2018년 4월 17일을 기준으로 합니다.
서울대학교 블록체인 학회인 ‘디사이퍼(Decipher)’에서 블록체인의 스케일링 솔루션에 관한 글들을 시리즈로 연재합니다. 시리즈의 첫 번째 주인공은 Ethereum의 “Casper the Freindly Finality Gadget”입니다. 1–1. Casper FFG Overview, 1–2. Casper FFG — Q&A 및 Code Review로 나누어 설명합니다.
첫번째 주제로 이더리움이 PoW(Proof of Work) 합의 알고리즘에서 PoS(Proof of Stake) 로 전환하기 위해 고민되고 있는 Casper 에 대해서 알아보고자 한다. Casper는 이더리움 창시자인 비탈릭 부테린(Vitalik Buterin)이 제시하는 “Casper the Friendly Finality Gadget”(FFG)와 이더리움 재단 연구원인 블라드 잠퍼(Vlad Zamfir)가 제시하는 “Casper the Friendly GHOST: Correct-by-Construction”(CBC)가 존재한다. FFG는 PoW와 PoS를 같이 가져가는 하이브리드 캐스퍼라고도 불린다. 이번 글에서는 비탈릭 부테린과 버질 그리피스(Virgil Griffith)가 작성한 “Casper the Friendly Finality Gadget” 논문을 중심으로 Casper FFG 에 대해 알아보도록 하자.
Proof of Work 의 문제는 무엇인가?
Casper 의 원리를 설명하기 전, 이더리움에서 이미 잘 동작하고 있는 PoW에서 PoS로 변경하려는 이유에 대해 알아보자. 이더리움 재단 연구원인 칼 플로리쉬(Karl Floersch)의 캐스퍼 발표자료를 보면 크게 두 가지로 정리된다. 첫번째로 PoW로 인해 소모되는 에너지를 줄일 수 있다는 것이다. PoW에서 블록을 생성하기 위해서는 특정 조건을 만족하는 해시값을 계산하는 일을 반복해야된다. 이러한 해시값 계산은 하드웨어가 전기를 소모하게 하고 이러한 전기 소모는 에너지의 낭비로 이어진다. Powercompare에 따르면 비트코인 채굴로 인한 전기 소모는 아일랜드나 대부분의 아프리카 나라들의 전기 소모량을 넘는 수준이라고 한다. Powercompare의 보고서가 2017년에 써졌는데 지금은 더 많은 국가들의 전기 소모량을 넘을 것이다. 이처럼 막대한 양의 에너지를 소모하는 시스템은 장기적으로 봤을 때 환경에 해롭기 때문에 에너지 소모량을 줄이기 위해 PoS가 필요하다고 주장한다. 두번째로는 ASIC(Application Specific Integrated Circuit)와 중앙화된 채굴 집단으로 인해서 메인 체인(블록 넘버가 가장 큰 블록을 포함한 체인)을 변경할 수 있다는 것이다. 즉, 완결성(Finality)의 부재이다. 완결성이란 이미 결정된 블록체인이 바뀌지 않는 것을 의미한다. ASIC 혹은 빠른 채굴 장비가 등장해서 기존에 가장 긴 체인 이외의 다른 가지의 블록을 빠르게 생성해나가 가장 긴 체인을 역전한다면, 메인 체인이 변경될 수 있다. 과거의 가장 긴 체인에 포함되어 있었지만, ASIC에 의해 새롭게 생긴 가장 긴 체인에는 포함되지 않은 트랜잭션이 있다면 갑자기 잔고가 변경될 수 도 있다. 이러한 문제점 때문에 PoS 도입을 통한 완결성이 필요하다.
캐스퍼 이전의 Proof of Stake 연구들
PoS 에서는 채굴자(Miner) 대신 검증인(Validator) 용어를 사용한다. 검증인이란 블록을 생성하기 위한 참가하는 사람을 의미한다. 이더리움 캐스퍼에서는 검증인이 되기 위해서 일정량 이상의 이더리움(2018년 3월 기준 1500ETH)을 예치해야한다. 그리고 검증인들이 모여있는 집단을 검증인 집단이라고 부르도록 하자. PoS는 캐스퍼에서 처음 등장하는 개념이 아니라 이전에도 존재하던 개념이다. 캐스퍼 이전에는 크게 두 가지의 PoS 디자인이 존재했다. 첫째로는 체인 기반의 PoS(chain-based Proof of Stake)이다. 무작위 랜덤 알고리즘이 특정 시간 간격으로 검증인 집단에서 검증인을 뽑고 블록을 만들 권한을 준다. 그리고 선정된 검증인은 블록을 생성한다. PeerCoin이나 BlackCoin이 이러한 방식의 PoS를 취한다. 두번째로는 BFT(Byzantine Fault Tolerant) 방식의 PoS가 존재한다. BFT-방식에서는 검증인 집단에서 무작위로 선출된 검증인에게 블록을 제안 할 수 있는 권리를 준다. 블록을 제안하는 것이 블록을 바로 생성하는 것은 아니다. 블록이 finalize 되려면 여러 차례의 투표 라운드 동안 ⅔ 이상의 검증인들이 특정 블록을 인정하는 투표를 해야한다. 이러한 과정을 통해서 블록이 영구적으로 체인에 포함되면 블록의 길이에 영향을 받지 않게 된다. Tendermint 가 BFT 방식의 PoS 방식을 이용한다. 이 과정도 Casper 만큼 복잡한 과정에 의해 이뤄지는데 Tendermint 의 PoS 방식에 관심이 있다면 “Tendermint: Consensus without mining” 을 읽어보길 바란다.
캐스퍼 프로토콜 이란?
하이브리드 PoW/PoS 시스템은 이더리움에 적용하는 첫번째 캐스퍼 버전이다. 검증인 집단이 변하지 않는다는 가정 하에 캐스퍼 프로토콜이 어떻게 동작하는지 알아보자. 우선 검증인이 되기 위해서는 캐스퍼 스마트 컨트랙트에 이더리움을 예치금(deposit)으로 맡겨야한다. 인센티브 로직이 스마트 컨트랙트에 있기 때문에 합의 과정을 통해 블록을 올바르게 생성했을 경우 예치금을 맡긴 검증인들에게 보상이 주어진다. 반대로 블록 합의 과정에서 잘못된 행동을 하였을 때 예치금을 몰수해서 처벌을 가한다. PoS의 안정성은 예치금의 크기와 비례한다. 규칙을 어겨 몰수되는 이더리움의 양이 클수록 규칙 위반에 따른 경제적 비용이 크기 때문이다. 캐스퍼 프로토콜에서 ⅔ 검증인은 검증인의 숫자가 아니라 검증인들이 가지고 있는 예치금의 ⅔ 임을 주의해야한다. 이제 이더리움을 예치하여 검증인이 된 사람들이 어떻게 투표를 하는지 알아보자.
FFG는 PoW를 병행하기 때문에 매 블록마다 투표를 진행하지는 않는다. 대신 제네시스 블록 혹은 제네시스 블록으로부터 매 50번째 블록마다 체크포인트라 부르고 체크포인트에 대해 투표를 한다. 투표에는 4가지 정보와 서명이 포함이 된다.
위의 표에 명시된것 처럼 source(검증의 근거)가 될 체크포인트와 target(검증의 대상)이 될 체크포인트, 그리고 각각의 체크포인트 블록의 높이가 투표의 항목으로 들어가고 <v, s, t, h(s), h(t)> 라고 표기한다 (v는 검증인을 의미한다). 여기서 주의할 것은 source가 target의 조상이 아니면 투표가 무효화되고 검증인이 검증인 집단에 속하지 않았어도 무효화 된다. 여기서 조상이란 source 가 target 보다 블록 높이가 낮고 같은 체인으로 연결되어져 있는 것을 의미한다. 이 투표는 검증인의 키에 의해 서명되서 제출된다. 이렇게 제출된 투표는 두 가지 규칙을 따르게 된다.
첫 번째는 target 체크 포인트의 높이가 같은 서로 다른 투표를 할 수 없다는 것이다.
위의 그림과 같이 체크포인트의 높이가 같은 두 개의 가지로 나뉘어 졌을 때, 검증인은 두 개의 체크포인트중 하나에만 투표할 수 있다. 블록 체인에서 높이가 같은 가지가 발생해서 경쟁하는 상황에서 투표를 해서 하나를 선택해야되는데 두 개 다 투표를 해버리면 어떤 가지를 메인 체인으로 할지 선택할 수 없기 때문이다.
두 번째 규칙은 자신이 투표한 source, target 체크 포인트 높이 안에 포함되는 다른 투표를 할 수 없다는 것이다.
위의 그림처럼 s2, t2 의 높이 안에 s1, t1 이 포함되는 투표를 할 수 없다. 첫번째 규칙이 높이가 같으면서 충돌하는 블록에 투표하는걸 막아줄 수 있지만, 높이가 다르면서 충돌하는 경우에는 막아줄 수 없다. 이 경우를 위해 두번째 규칙이 필요하다. 이에 대한 구체적인 논의는 “블록체인 확장성 솔루션 시리즈 1–2 :: Casper FFG — Q&A / Code Review” 에서 자세히 이야기해보겠다.
캐스퍼의 동작 과정
앞에서 살펴본 투표의 형식과 규칙을 가지고 어떻게 블록이 finalize 되는지 알아보도록하자. 그전에 캐스퍼를 설명하기위해 필요한 용어들을 정리하고 넘어가도록하자.
epoch: 검증인이 투표하는 체크포인트의 블록 간격, FFG에서는 현재는 50블록이다.
supermajority link: 적어도 ⅔ 검증인이 source A에서 target B로 투표를 한 경우. 체크포인트 A, B의 순서쌍을 supermajority link라 하고” A->B”로 표기한다.
conflict: 서로 다른 가지에 블록이 존재하는 경우 두 체크포인트는 충돌한다고 한다. 즉, 두 체크포인트가 서로의 부모 자식 관계가 아님을 의미한다.
justified: 제네시스 블록이거나 justified 된 C 체크포인트에서 C->C’인 supermajority link가 존재할 때 체크 포인트 C’가 justified 되었다고 한다.
finalized: 체크포인트 C가 justified 되었고 C의 직계 자손(direct child)인 C’에서 supermajority link C->C’가 존재할 때 체크포인트 C가 finalized 되었다고 한다. 직계 자손이라는 것은 체크 포인트의 높이 차이가 1인 경우를 의미한다.
생소한 부분이 많아서 개념만 보고서 이해하는게 쉽지 않을 수 있다. 따라서 이번에는 실제로 어떤 단계들을 거쳐서 투표가 진행되고 블록이 생성되고 체크포인트가 finalize 되는지 그림을 통해 단계적으로 살펴보고자 한다. 아래 그림에서 곡괭이를 들고 있는 사람들은 채굴자이고, 정장을 입은 사람은 검증인이다. 과정을 간단하게 보기 위해서 검증인은 총 4명이 있고 4명의 예치금은 각각 똑같아서 투표의 세기가 똑같다고 가정하자. 체크포인트는 제네시스 블록 다음의 체크포인트라고 하자. 즉 이전 체크포인트는 justified 되어있다.
체크 포인트에 검증인들이 투표를 한다. 투표는 스마트 컨트랙트에 메서드를 호출하는 것이므로 채굴자들에 의해 트랜잭션이 채굴되어야지 블록에 포함된다. 위의 그림에서는 4명의 검증인 중에서 3명이 투표를 제출한 상태이다.
그림 6. 캐스퍼 합의 과정 2 (출처: 칼의 캐스퍼 발표자료) 제출된 투표는 채굴 과정을 통해서 블록에 포함된다. 왼쪽의 채굴자가 2명의 검증인이 제출한 투표를 블록에 포함시켰고 현재 체크포인트는 ½ 의 승인을 얻었다.
그림 7. 캐스퍼 합의 과정 3 (출처: 칼의 캐스퍼 발표자료) 다음으로 오른쪽 채굴자가 ¼ 에 해당하는 투표를 채굴함으로써 체크 포인트는 총 ¾ 의 투표를 받게되고 ⅔ 이 넘었으므로 새로운 체크포인트(target)에 대해 supermajority link 가 생기고 justified 된다.
그림 8. 캐스퍼 합의 과정 4 (출처: 칼의 캐스퍼 발표자료) 다시 체크 포인트가 찾아오면 검증인들은 다시 투표를 제출하게 된다. ¾의 검증인이 source 를 justified 된 체크포인트(노란색)로 하고 target 을 새롭게 생성된 체크포인트로 하는 투표를 제출 하였다.
그림 9. 캐스퍼 합의 과정 5 (출처: 칼의 캐스퍼 발표자료) 3명의 검증인이 제출한 투표가 채굴자에 의해 블록에 포함됬고 새롭게 생긴 체크 포인트(노란색)가 ¾의 투표를 받아서 ⅔을 넘겨서 justified 되었다.
그림 10. 캐스퍼 합의 과정 6(출처: 칼의 캐스퍼 발표자료) ⅔ 이상의 검증인이 초록색 체크 포인트를 source 로 하고 노란색 체크포인트를 target 으로 하는 투표를 했기 때문에 그림과 같이 두 체크포인트는 supermajority link 로 연결된다. 그리고 초록색 체크포인트가 justified 되어있고 직계 자손(direct child)인 체크포인트가 supermajority link로 연결되므로 초록색 체크포인트가 finalize 되었다.
캐스퍼의 두 가지 정리
앞에서 설명한 과정들을 통해서 캐스퍼는 Accountable Safety와 Plausible Liveness 를 얻을 수 있다. Accountable Safety는 검증인이 규칙을 위반해 ⅓ 이상의 예치금 몰수 없이 두 개의 충돌하는 체크포인트가 finalize 될 수 없다는 것이다. Plausible Liveness는 예치금 몰수, 블록 딜레이와 같은 사건과 관계없이 ⅔의 검증인이 프로토콜을 따른다면, 어느 검증인의 예치금 몰수 없이도 새로운 체크포인트를 finalize 할 수 있다는 것이다. 이 두 가지 정리가 성립하는지 알아보기 전에 프로토콜 규칙에 의해 도출되는 속성을 살펴보자.
두 개의 캐스퍼 프로토콜을 이용해서 ⅔ 이상의 검증인이 몰수 조건을 위반하지 않는다면 네 가지 속성을 따른다고 할 수 있다.
- s1->t1, s2->t2 의 서로 다른 supermajority link 가 존재한다면, h(t1) 과 h(t2) 는 다르다.
- s1->t1, s2->t2 의 서로 다른 supermajority link 가 존재한다면, h(s1) < h(s2) < h(t2) < h(t1) 을 만족하는 s1, t1, s2, t2 가 존재할 수 없다.
- h(t) = n 인 s->t supermajority link 는 많아야 1개 존재한다.
- 높이가 n 인 justified 체크포인트는 많아야 1개 존재한다.
캐스퍼 프로토콜과 이로 인해 나타난 네 가지 속성을 통해서 앞에서 설명한 Accountable Safety 와 Plausible Liveness 를 증명할 수 있다. Accountable Safety 는 충돌하는 체크포인트 A, B 가 있다고 가정한 뒤 귀류법을 통해서 증명할 수 있고, Plausible Liveness 역시 위의 네 가지 속성들을 이용해서 손쉽게 증명할 수 있다. 자세한 증명과정은 문영훈님의 슬라이드를 참고하기 바란다.
이 두 가지 정리가 중요한 이유는 캐스퍼 프로토콜에 따라 증명되는 정리들이 성립하지 않으려면 ⅓ 이상의 예치금이 몰수당해야 된다는 것이다. ⅓ 이라는 수치는 supermajority link 가 생성되기 위해서는 ⅔ 검증인의 동의가 필요하기 때문에 구해지는 수치이다. 충돌하는 체크포인트 A, B가 존재하고 예치금이 같은 3명의 검증인 가, 나, 다가 있다고 가정하자. “가”는 A에 투표하고, “나”는 B에 투표한 상황에서 “다”가 A, B 모두에게 투표하는 경우. A, B 모두 ⅔ 검증인이 투표를 하여서 supermajority link 가 생성되고 justify된다. 그리고 추후 투표를 통해서 finalize 될 수 있다. 하지만 “다”는 첫번째 투표 규칙에 위반하였기 때문에 예치금을 몰수 당하게 된다. 3명중에 1명이 예치금 몰수를 당하게 되므로 ⅓ 이상의 예치금 몰 수 없이 두개의 충돌하는 체크포인트가 finalize 될 수 없게 되는 것이다. 즉 누군가 규칙을 벗어난 블록을 생성해서 포크를 일으키려면 경제적인 처벌을 받게 된다는 것이다. 검증인들은 이러한 경제적인 처벌을 감당하면서 까지 포크를 발생시킬 유인이 거의 존재하지 않을 것이므로 캐스퍼 프로토콜에서 정의된 규칙대로 움직일 확률이 높을 것이다.
동적인 검증인 집단
지금까지는 검증인 집단이 고정되어 있다는 가정하에 간단한 캐스퍼 프로토콜을 살펴보았다. 하지만 실제로 캐스퍼가 동작할 때는 고정된 검증인 집단이 아니라 수시로 변하는 검증인 집단을 가지고 동작한다. 검증인이 되기 위해 스마트 컨트랙트에 이더리움을 예치했는데 필요에 의해서 혹은 검증인을 그만 두고자 이더리움을 출금할 수도 있고, 새롭게 검증인이 되기 위해서 이더리움을 예치할 수 있기 때문이다. 검증인 집단의 변경에 대한 제약이 없을 경우, 한쪽 가지에 대해 투표한 검증인 집단이 모두 나가고 새로운 검증인 집단이 와서 반대쪽 가지에 투표한다면 규칙에 위배되지 않으므로 검증인 중 그 누구도 예치금이 몰수되지 않는다. 이러한 문제점을 해결하기위해서 입금/출금 이후 바로 검증인 집단에 참여/제외되는 것이 아니라 일정시간 뒤에 검증인 집단에 참여/제외 되게 해야한다. 이러한 문제를 해결하는 방법을 설명하기 전에 동적인 검증인 집단에서 추가되는 개념인 dynasty에 대해 알아보자. 블록 B의 dynasty 는 루트부터 블록 B의 바로 이전 블록까지 finalize 된 체크포인트의 수 이다. 그리고 검증인이 dynasty d 인 블록에 예치금을 입금하면 검증인은 dynasty 가 d + 2 일 때 부터 검증인 집단에 속하게 된다. 다시말하자면 이더리움을 예치하고 두번의 finalize가 일어나면 검증인 집단에 속하게 된다. d + 2 를 start dynasty 라고 부른다. 마찬가지로 검증인 집단에서 떠날 때도 dynasty 의 개념을 이용해야 한다. 검증인이 dynasty 가 d 인 블록에서 출금을 할 경우 dynasty 가 d + 2 일 때 검증인 집단을 떠나게 된다. 그리고 이는 end dynasty 라고 부른다.
동적인 검증인 집단의 문제를 좀 더 구체적으로 살펴보자. 위의 그림과 같이 체크포인트 S 에서 보라색 검증인 집단이 있었다고 하자. 그리고 충돌하는 체인이 발생했다고 하자. 이해를 돕기위해 첨언하자면 위의 그림에서 블록간의 점선으로 이어진 부분에도 수많은 블록이 존재한다. 체크포인트 S 를 finalize 하는 투표가 오른쪽 체인에서는 포함되고 왼쪽 체인에서는 포함이 되지 않았다고 하자. 이럴 경우 오른쪽 체인은 finalize 된 체크포인트가 하나 더 늘어서 dynasty 가 변경되고 검증인 집단이 변경된다. 하지만 왼쪽 집단은 dynasty가 그대로여서 검증인 집단이 바뀌지 않게된다. 이런 상황에서 블록이 계속 생성되고 추가적인 투표가 진행되어서 높이가 같은 체크포인트 C와 C’ 이 finalize 된다면 첫번째 투표 규칙에 위반되지만 검증자 집단이 다르기 때문에 아무도 예치금을 몰수 당하지 않는다. 이럴 경우 이전에 설명한 Accountable Safety를 만족하지 못하게 된다. 따라서 우리는 기존에 고정된 검증자 집단에 대한 정의들을 약간 수정할 필요가 있다. 따라서 새로 들어온 검증자 집단과 이전에 들어온 검증자 집단을 구분하여서 각각의 집단에서 ⅔ 이상의 투표를 받아야지 supermajority link 가 생기도록 정의를 변경하였다. 고정된 검증자 집단이 아닌 동적인 검증자 집단일 경우에 Accountable Safety 와 Plausible Liveness 를 증명하는 것은 캐스퍼 페이퍼에서 아직 미래 과제로 남겨두고 있다. 이처럼 아직도 캐스퍼는 완결된 메커니즘이 아닌 진화중인 메커니즘으로 문제점들이 충분히 존재할 수 있다. 하지만 PoW에서 PoS로 전환하는 첫 프로젝트로 큰 의의를 가지고 있다. 이것으로 Casper FFG 에 대해 알아보았고 다음 글에서는 FFG 를 조사하며 궁금했던 점을 Q&A 형식으로 풀어써본다. 그리고 앞서 설명한 캐스퍼 프로토콜이 코드에서는 어떻게 구현되었는지 살펴보려고 한다.
본 포스팅은 암호화폐 거래소 고팍스(@gopaxkr)의 후원을 받아 디사이퍼가 작성하였습니다.
다음글) 블록체인 확장성 솔루션 시리즈 1–2 :: Casper FFG — Q&A / Code Review