scalalang2

이더리움 Casper-FFG 지분증명 알고리즘 쉽게 이해하기

Ethereum Casper-FFG 지분증명

캐스퍼란 기존 작업증명(PoW)기반의 블록체인에 하이브리드 방식으로 지분증명(PoS)을 사용할 수 있도록 이더리움의 창시자 비탈릭 부테린이 제안한 아이디어이다. 그가 여러 매체에서 설명한 대로 캐스퍼는 다가오는 2020년 이더리움 2.0 버전의 비콘 체인에 적용 될 예정이다.

캐스퍼는 비탈릭 부테린이 2017년에 제출한 논문 “Casper the Friendly Finality Gadget”에서 소개되었으며 일반적인 블록체인에 적용하는 방법에 대해 다룬다. 이후 비탈릭 부테린은 2019년에 추가로 캐스퍼 관련 논문을 제출하였는데 이는 이더리움에 적용하는 방법에 대해 초점이 맞춰 있다. 오늘 우리는 그가 2017년에 처음 제출한 논문의 내용을 알아 볼 것이다.

요약: 캐스퍼는 PoW체인에서 PoS를 조합해서 사용하는 방법을 제시하는 합의 알고리즘이다.

소개순서

나는 크게 캐스퍼를 3장으로 나누어서 설명하려고 한다. 첫 장엔 지분증명을 구현하는 두가지 방법에 대해 소개하고 두번째 장엔 캐스퍼의 지분증명 구현 원리와 특징, 증명에 관한 이야기를 한다 마지막으로 지분증명 알고리즘에서 발생할 수 있는 문제점과 해결 방안을 소개한다.

지분증명을 구현하는 두가지 방법

1. Chain-based PoS

비탈릭 부테린은 그의 논문에서 지분증명을 구현하는 두가지 방법을 소개하는 것으로 시작한다. 지분증명은 크게 체인-기반 지분증명과 BFT-기반 지분증명으로 나뉜다. 체인-기반 지분증명이란 지분에 따라 작업증명의 난이도를 다르게 주는 방법이다. 지분이 많은 사람은 그 만큼 작업증명의 난이도가 쉬워져서 채굴할 확률이 증가하고 지분이 작은 사람은 난이도가 상대적으로 어려워서 채굴할 확률이 감소한다.

2. BFT-based PoS

BFT 기반 작업증명은 이미 30년 넘게 가까이 연구된 BFT 알고리즘을 활용하는 방법이다. BFT는 투표에 의해 한가지 값을 전체 노드가 합의하는 방안에 관한 연구인데 이 중 PBFT는 비동기 네트워크에서 전체 노드의 2⁄3 이상이 정직하면 합의에 이를 수 있다는 것을 수학적으로 증명한 것으로 유명하며 이는 이 후 하이퍼렛저, 텐더민트 등 여러 블록체인에서 활용하게 된다. 캐스퍼 또한 BFT를 기반으로 지분증명을 도입한다.

캐스퍼는 BFT기반으로 구현하되 4개의 개념을 추가했다.

1. Accountability (검증자의 의무)

검증자는 캐스퍼 프로토콜이 정의한 책임과 의무를 따를 필요가 있으며 프로토콜이 정의한 의무에 위배되는 행위를 할 시 스테이킹한 보증금 전액을 패널티로 삭감당한다.

2. Dynamic Validators (동적 검증인 집합)

EOS의 위임지분증명(DPoS)은 대표자 21명끼리 블록체인을 운영하며 블록을 검증하고, 동일하게 PBFT기반으로 지분증명을 하는 텐더민트에서는 100명의 검증인만이 블록체인에 참여한다. 반면, 이더리움의 설계 철학은 완전탈중앙성을 지향하기 때문에 누구나 검증인이 될 수 있어야 한다. 따라서 이 검증인들은 언제든지 네트워크에 참여하거나 이탈 할 수 있는 동적인 특성을 가지고 있기 때문에 이를 동적으로 관리할 필요가 있다.

작업증명 기반 블록체인에서는 노드를 운영하는 사람을 마이너라고 부른다면 지분증명 기반 블록체인에서 노드를 운영하는 사람을 검증인이라고 한다.

3. Defenses (악의적인 공격에 대한 방어책)

지분증명은 기존 작업증명과 그 방식이 현저히 다르기 때문에 공격 가능성 또한 많이 다르다. 비탈릭은 논문에서 지분증명에서 발생할 수 있는 여러 공격방법과 방어에 대해 설명해 두었다. 본 포스트에서는 캐스퍼의 동작원리와 특징을 설명한 뒤 캐스퍼 프로토콜의 공격 방법과 방어책에 대해 서술한다.

4. Modular Overlay (오버레이 모듈화)

캐스퍼는 그 자체로는 이더리움만을 위한 지분증명 알고리즘은 아니다. 작업증명을 사용하고 있는 어떤 블록체인이라도 캐스퍼 알고리즘을 도입하면 작업증명과 지분증명을 하이브리드 방식으로 사용할 수 있다고 강조한다. 캐스퍼를 이해하는데 중요한 내용은 아니기 때문에 이 글에서는 자세히 설명하지 않는다.

캐스퍼 알고리즘 설명

본격적으로 캐스퍼를 설명하기 이전에 설명하는 순서부터 소개하고자 한다.

가정. 블록체인에서 분기(Fork)는 필연적으로 발생한다.

우리는 개념적으로 블록체인 하면 일렬로 연결되는 링크드-리스트 자료구조를 떠올리기 쉽다.

블록체인 하면 이런 링크드-리스트 모양의 자료구조를 떠올릴 것이다.

하지만 실제로는 네트워크의 지연과 엄청나게 많은 노드 수 때문에 포크는 필연적으로 발생한다. 이더리움의 경우 현재 운영되고 있는 노드만 7,000여개로 아메리카, 아시아, 유럽 등 전 세계에 분포되어있다. 만약 아시아와, 아메리카에서 동시간대에 블록 채굴에 성공하고 이를 공유한다면 나머지 사용자는 이 생성된 두개의 블록 중 어느것을 블록체인에 포함될 지 결정해야 하기 때문에 분기(Fork)는 매 순간 발생한다. 다만, 실제 블록체인에 기록되지 않을 뿐이다. 따라서, 실제로 블록체인은 아래와 같이 트리 구조로 구성된다.

하지만 실제 블록체인은 수 많은 분기에 의해 트리구조를 띄게 된다.

위와 같은 트리 모양의 블록체인이 존재할 때 작업증명 기반 블록체인에서는 아래 그림처럼 가장 길이가 긴 체인(Longest Chain)을 실제 블록체인으로 기록한다. 그 이유는 그 어려운 작업증명 과정을 거쳐서 형성된 체인 중 가장 높이가 길기 때문에 블록이 번복될(Revert) 가능성이 적기 때문이다. 이렇게 블록체인 트리 중 하나의 분기를 선택하는 규칙을 분기선택규칙(Fork Choice Rule)이라고 한다. 캐스퍼에서는 모양은 유사하지만 다른 분기선택규칙을 가지고 있다. 이는 추후에 설명할 것이다.

기존 블록체인은 이 분기중 가장 긴 체인을 선택해서 합의를 한다.

정의 1. 체크포인트 (Checkpoint)

지금 부터는 캐스퍼 프로토콜에서 정의하는 용어 여섯가지를 소개할 것이다. 체크포인트 블록이란 매 100번째 마다 생성되는 블록이다. 제네시스 블록은 자동으로 체크포인트 블록이 된다. 그러므로 (블록 높이) % 100 = 0 이 되는 블록은 체크 포인트 블록이 된다. 검증인들은 생성된 체크 포인트에 투표를 하게 된다.

체크포인트 블록이 100번째 마다 생성되는 이유는 투표를 하는 과정이 자원을 많이 먹기 때문이다. PBFT알고리즘은 참여자가 많을 수록 합의 프로세스가 느려지는 특성을 가지고 있는데, 생성되는 모든 블록마다 투표하면 에너지 낭비가 심하게 발생한다. 따라서 캐스퍼에서는 100번째 블록 마다 투표를 진행한다. (이 문제는 나중에 블라드 짐라크가 Casper CBC에서 DAG를 이용하여 다른 방안 제시하였다.)

정의 2. 투표 (Voting)

검증인이 보내는 투표 트랜잭션에는 현재 투표하고자 하는 체크 포인트의 블록과 투표하려는 블록 이전에 생성된 블록 정보를 포함하여 검증인 끼리 투표 메시지를 공유한다. 즉, 투표 메시지에는 이전, 현재 두개의 블록 정보가 포함된다. 따라서 정확히 말하면 검증인이 투표하는 것은 블록이 아닌 블록과 블록 사이의 연결성이다. 다만, 이전 체크포인트 블록은 반드시 안정된혹은 마감된 블록이어야 한다는 제약 조건이 있다. 만약 2/3가 넘는 검증인이 같은 에 투표하면 절대적 다수 링크를 생성하고 블록의 상태를 안정됨(Justified) 혹은 마감됨(Finalized) 으로 변경한다. 아래는 투표 트랜잭션의 내용이다.

정의 3. 절대적 다수 링크

절대적 다수 링크란 2/3이 넘는 검증인 같은 블록 연결성에 투표한 결과를 나타내며 s → t 로 표현한다. s는 이전 체크 포인트 블록, t는 이후 체크포인트 블록으로 두 블록사이의 연결성을 나타낸다.

지금까지 설명한 내용으로 검증인들은 체크포인트 블록이 생성될 때 마다 투표를 진행하는 것을 알 수 있다. 만약 두개의 분기가 발생했는데 절반의 검증인은 A분기에 나머지 절반은 B분기에서 생성된 체크포인트 블록에 투표한다면 2/3가 넘는 투표 결과가 없기 때문에 절대적 다수 링크는 생성되지 않는다. 캐스퍼에서는 이런 상황이 발생하면 재투표를 하지 않고 다음 체크포인트 블록이 생성될 때 까지 기다린다. 즉 절대적 다수링크에서 이전 체크포인트란 꼭 바로 이전 체크포인트일 필요는 없다.

절대적 다수 링크 A -> C의 예시

위 그림은 절대적 다수 링크가 체크포인트 블록 B를 건너 뛰어서 생성되는 모습을 보여준다.

정의 4. 안정된 블록 (Justified Block)

캐스퍼 프로토콜에서 제네시스 블록은 첫 번째 체크포인트 블록이며 동시에 안정된 블록이 된다. 안정된 블록이란 제네시스 블록이거나 절대적 다수 링크 이전 블록 → 이후 블록이 존재하고 이전 블록이 안정된 블록이면 이후 블록 또한 안정된 블록이 된다. 아래 그림은 안정된 블록 A, A1, A2를 보여준다.

Justified Block: A, A1, A2

이 특성으로 인해 체크포인트 중 에서도 안정된 블록들이 체인으로 이어져 있다는 것을 볼 수 있다. 이전 블록이 반드시 안정된 체크포인트 블록이어야 한다는 제약조건 때문에 아래 그림처럼 절대적 다수 링크를 생성할 수는 없다.

절대적 다수 링크 생성의 잘못 된 예시

정의 5. 마감된 블록 (Finalized Block)

마감된 블록이란 절대적 다수 링크가 존재 하고 이후 블록이 바로 이전에 안정화 된 체크포인트 블록의 자식이면 이전 체크포인트 블록은 마감된 블록이 된다. 캐스퍼 프로토콜은 마감된 블록의 이전 내용이 다시 번복(Revert)되는 일은 발생하지 않는다는 것을 보증한다.

정의 6. 충돌 (Conflict)

두개의 체크포인트가 같은 높이에 서로 다른 분기에서 존재하면 두 체크포인트 A, B를 충돌 상태로 정의한다. 아래 그림은 두 체크포인트 A, B가 서로 충돌된 상태를 보여준다.

다룬 분기에 존재하는 두 블록은 충돌로 정의한다.

검증인의 의무와 처벌

캐스퍼 논문에는 나와있지 않지만 이더리움 2.0 스펙 문서를 보면 검증인이 되려면 32 ETH (현재 시장가로 대략 1,000만원)을 이더리움 메인넷 컨트랙트에 예치해 두어야 한다. 이 예치금은 검증인이 규칙을 위반했을 때 즉시 모든 이더를 차감함으로써 검증인의 악의적인 행동을 억제한다. 그렇다면 검증인은 어떤 의무를 지켜야 할까? 캐스퍼 프로토콜은 검증인에게 두가지 의무를 준수할 것을 말한다.

#1. 같은 블록 높이에 중복 투표 하지 말 것

검증인은 같은 높이에 존재하는 블록에 중복 투표 해선 안되며, 이 규정을 어길 시 보증금 32 ETH를 전액 차감한다. 지분증명은 작업증명과는 다르게 블록 생성에 소모하는 컴퓨팅 자원이 엄청나게 작기 때문에 수 많은 블록을 생성할 수 있다. 이를 억제하기 위해 캐스퍼는 이 같은 규정을 두었다. 검증인들은 블록을 새성함으로써 얻는 보상인 2 ETH보다 악의적인 행동에 대한 패널티 32 ETH가 더 크기 때문에 중복투표금지 규정을 어기지 않을 것 이다.

중복 투표를 허용하면 다른 분기에서 같은 높이를 가진 마감 블록이 생성된다.

캐스퍼 프로토콜은 마감 블록(Finalized Block)이 생성되면, 그 블록 이전의 블록들이 내용이 변경되지 않음을 보장할 수 있도록 설계되었다. 따라서 다른 분기의 같은 높이에 마감 블록은 절대로 중복 생성되서는 안되며 만약 중복투표를 허용한다면 위 그림같이 다른 분기에 동시에 마감블록이 생성될 수 있다.

이 중복투표금지를 논문에서는 아래와 같이 표현하였다. h(x) 함수란 파라미터 x에 체크포인트 블록 해시를 넣으면 그 블록의 높이를 반환하는 함수이다.

h(a) = h(b) 가 되도록 투표하지 말 것, 이를 어길 시 보증금 32 ETH 전액 차감

#2. Nested Voting Prohibition

Nested Voting이란 캐스퍼 논문에서 사용하는 표현은 아니다. 이 규정을 논문에서는 아래의 수식으로 표현하였는데, 여기에 적절한 단어만 붙여주면 외우기 쉬울 것 같아서 Nested Voting이란 이름을 붙였다.

절대적 다수 링크 s1 → t1, s2 → t2가 있다고 가정할 때, h(s1) < h(s2) < h(t2) < h(t1) 이 되도록 투표하지 말것, 이를 어길 시 보증금 32 ETH 전액 차감

Nested 라는 단어는 내재적으로 포함된다는 것을 의미한다. 러시아에서 여행할 때 필수 기념품인 인형 마트료시카는 인형안에 또다른 인형이 반복적으로 포함되는데 아래 이미지를 보면 단어의 의미를 이해하는데 도움이 된다.

러시아 여행 필수 기념품 : 인형 마트료시카

다시, 원래로 들어와서 h(s1) < h(s2) < h(t2) < h(t1) 이 되도록 투표하지 말라는게 어떤 의미일까? 저 수학식을 블록체인 트리로 표현하면 아래 그림이 된다.

즉, Nested Voting 금지 규정이란 위 그림이 되도록 t1 블록을 생성하지 말라는 의미이다. 이 때, s2 → t2링크는 블록체인 트리 상 s1 → t1안에 포함되는 관계가 된다. 그렇다면 왜 이런 규정을 두었을까? 이는 검증인들이 중복투표를 하지 않을 때 서로 다른 분기에 마감블록이 동시에 생길 수 있는 유일한 방법이기 때문이다. t1 블록 바로 다음에 t1 → t1’ 절대적 다수 링크가 생성된다면 t1은 블록은 마감블록이 되며 그렇다면 서로 다른 브랜치에 s2, t1 두개의 마감블록이 생긴다. 따라서 캐스퍼는 검증인들에게 이렇게 투표하는 것을 금지한다.

Nested Voting을 허용했을 때 다른 분기에서 마감 블록이 동시에 생긴다.

캐스퍼 프로토콜은 전체 검증인의 33% 미만이 악의적인 검증인이더라도(정확히 말하면 예치한 보증금의 33% 미만) 네트워크에 문제가 발생하지 않도록 설계 되었다. 즉, 전체 검증인의 33% 미만이 위 두 규칙을 어기더라도 다른 분기에서 동시에 마감 블록이 생성되지 않는다.

분기 선택 규칙 (Fork Choice Rule)

캐스퍼 프로토콜의 검증자들은 위 두가지 규정을 어기지 않는다면 보증금 32 ETH가 패널티로 차감되지 않는다. 검증인들이 위 두가지 규칙을 어기지 않더라도 네트워크에 문제가 발생할 수 있는 방법이 존재한다. 두 개의 검증자 그룹이 있다고 가정하자. 한 그룹 A는 전체 검증인의 절반이 있고, 그룹 B는 A그룹의 검증인을 제외한 나머지 절반의 검증자의 집합이다.

만약 A그룹은 A1, A2, A3, A4 .. An 순서로 오른쪽 분기부터 지그재그로 투표하고, B그룹은 반대로 B1, B2, B3, B4 .. Bn순서로 왼쪽 분기부터 지그재그로 투표한다면, 2⁄3 이상의 투표가 영원히 일어나지 않을 것이다. 이 경우 네트워크 사용자는 물론, 검증자 본인들 조차 블록이 생성되지 않아서 보상을 얻을 수 없기 때문에 이런 일이 발생하길 원치 않을 것이다.

캐스퍼 프로토콜은 원활한 합의를 위해 한가지 분기 선택 규칙을 제안한다.

가장 높이가 큰 안정화 블록이 존재하는 분기를 선택한다

검증인들이 위 규칙을 잘 따르면 분기가 많이 발생한다 하더라도 한가지 분기를 선택하기 때문에 원활한 합의에 이를 수 있고, 블록이 빨리 생성되야 보상을 받기 때문에 이 규칙을 따르지 않을 이유가 없다.

Dynasty

EOS, 텐더민트 같은 위임지분증명(Delegated Proof of Stake)를 사용하는 프로토콜은 검증인의 숫자가 각각 21명, 100명으로 고정되어 있기 때문에 검증인 집합의 변화가 잘 발생하지 않는다. 반면, 캐스퍼 프로토콜은 검증인의 합류와 이탈이 자유롭고 전체 검증인의 숫자를 시장에 맡기기 때문에 검증인의 숫자가 자주 바뀐다고 예상할 수 있다.

Dynasty는 검증인의 합류와 이탈이 발생할 때, 언제 투표권이 생성되고 언제 투표권이 상실되는지를 정의하는 기준 수치이다. 특정 블록 b의 dynasty란 제네시스 블록부터 b블록의 이전 블록까지 존재하는 마감 블록 수를 말한다. 모든 블록은 dynasty값을 가지고 있다. 예를 들어 아래 예시에서 블록 A3의 dynasty값은 1이 된다.

A3블록의 Dynasty값은 1이다.

새로운 네트워크 사용자가 검증인이 되기 위해 보증금을 예치하고, 기존 검증인이 이탈을 위해 보증금을 출금한다면 아래 규칙을 따라 투표권이 생성되고 상실된다.

사실 Dynasty에 대해 해야 할 이야기가 더 많지만, 내용이 길어지기 때문에 별도의 포스팅에서 이를 설명하려고 한다. 본 포스팅의 목적은 전체 흐름을 전달하는 것이 목적이기 때문이다.

특별하게 검증자들이 출금을 신청하면 바로 받지 못하고 4개월 이후에 예치한 보증금을 돌려받는 출금 지연 정책이 존재하는데, 이 정책이 존재하는 이유는 검증인들이 이탈한 직후 과거 블록 내용을 바꾸는 것을 방지하기 위함이다. 이는 바로 다음장에서 설명한다.

장거리 수정 공격 (Long Range Revision Attack)

장거리 수정 공격 (Long Range Revision Attack) 이란 악의적인 검증자가 검증자 그룹에서 이탈한 직후 과거 블록으로 돌아가 투표를 하는 행위를 말한다. 아래 그림인에서 검증자는 A1블록에서 검증인 선언을 취소했지만 블록 높이 1의 B1블록에서는 검증인 선언이 취소되지 않은 상태이기 때문에 투표가 가능하다. 이는 모든 지분증명 알고리즘에서 발생하는 공통적인 문제이기 때문에 지분증명 알고리즘마다 저마다의 해결책이 존재한다.

검증인 선언 취소가 A1블록에서 발생했다.

하지만 B블록에서는 아직 선언인 취소를 하지 않았으니 재투표를 할 수 있다.

캐스퍼 에서는 이 같은 행위를 방지하기 위해 검증인 선언을 취소한 직후 4개월 이후에 보증금을 돌려받는 제도를 시행한다. 이 상황에서 검증인이 취할 수 있는 행동은 아래 세가지로 정리할 수 있다.

파괴적 충돌 (Castastrophic Crashes)

만약 어느날 검증인의 1/3이상이 갑자기 어떤 이유로 인해서 오프라인 상태가 되면 어떻게 될까? 1/3이상의 검증인이 오프라인 상태이기 때문에 나머지 검증인이 어떻게 투표를 하던 2⁄3이상의 합의를 이루어 낼 수 없기 때문에 전체 거래기록은 무한정 연기되는 상황이 발생한다.

많은 수의 검증인 그룹이 오프라인 상태가 되면 2/3이상의 합의가 불가능 하기 때문에 이에 대한 조치가 들어가야한다.

이러한 문제를 파괴적 충돌이라고 한다. 캐스퍼 논문에서는 이 상황에 대한 해결책이 존재하는데 이 방법을 소개하기 전에 2/3이상 합의의 의미를 다시 한번 상기시켜 줄 필요가 있다. 캐스퍼 프로토콜에서 2/3이상의 합의란 검증인의 수가 2/3이상이 아닌 검증인이 예치한 보증금의 숫자가 2/3이상인 경우를 의미한다. 캐스퍼는 파괴적 충돌의 상황을 방지하기 위해 오프라인 상태의 검증인들, 즉 투표하지 않는 검증인들의 보증금을 조금씩 삭감하는 방안을 제안한다.

다만, 이 방법은 현재까지도 이더리움 커뮤니티에서 논란이 되고 있다. 단순히 컴퓨터 조작 실수때문에 네트워크가 안되었던 것 뿐이라면 그들을 처벌하는게 정당한가?, 혹은 대다수의 검증인들이 소수의 검증인들의 투표권을 의도적으로 누락시킨다고 하면 이를 감지할 수도 없는데 투표하지 못한 소수의 검증인들을 처벌하는게 정당한가? 등 다양한 상황이 존재하기 때문에 간단하게 보증금을 삭감하는게 완벽한 해결책이 아닐 수 있다. 이 해결방안은 아직까지 많은 토론이 이루어 지고 있기 때문에 실제 이더리움 2.0에서는 이러한 정책이 도입되지 않을 수도 있다.

마치며

지금까지 이더리움 캐스퍼에 대해 최대한 수학적인 내용을 배제하고 말로 풀어서 설명했다. 캐스퍼 FFG는 완전한 PoS방식이 아닌데다가 이더리움의 특성상 현재는 작업증명 으로 돌아가고 있기 때문에 PoS로 넘어가기 전에 잠깐 시행하기 위한 방법으로 제시 되었다.

완전 PoS가 되려면 블록 제안자(Block Proposer)를 매 번 정해야 하는 등 여러 가지의 내용이 더 추가되어야 하는데 이는 Casper CBC에서 블라드 짐라크가 캐스퍼를 조금 변형하여 완전지분증명을 제안하였다.

현재, 이더리움 2.0은 Parity Client를 만든 패리티 테크놀로지와 여러 회사에서 이더리움 재단의 지원을 받고 비콘체인이란 이름으로 개발하고 있으며 2020년에 메인넷에 적용하는 것을 목표로 하고 있기 때문에 현재 2019년에서 이러한 주제로 공부하고 좋은 아이디어가 있다면 이더리움 커뮤니티에 제안하는 것도 의미있는 일이라고 생각한다. 나의 다음 포스팅 주제는 Dynasty와 동적 검증자 집합에 대한 내용을 다루고 Casper CBC의 논문을 읽고 이를 다시 정리해보려고 한다.