비탈릭의 캐스퍼 폭풍 트위터 파헤치기 (중)

A Tweet Storm explaining the History and State of Ethereum’s Casper Research by Vitalik Buterin

(상) 편에 이어서 비탈릭이 설명하는 캐스퍼의 역사와 현황에 대해 알아보겠습니다[1]. 이번 편에서는 다음 내용에 대해 이야기합니다:

  • 보증금 삭감의 두 가지 조건
  • 공격자가 명확하지 않은 경우에서 페널티 규칙
  • 블라드의 최신 메시지 기반 GHOST

캐스퍼 기술 용어의 번역은 국내 커뮤니티가 사용하고 있거나, 관련 번역글에서 사용한 단어를 사용했습니다. 비탈릭 부테린이 트위터에 첨부한 링크 글은 따로 각주에 표기하지 않았으며, 한국어 번역본이 있는 경우 함께 첨부하였습니다.

블라드 잠피르(Vlad Zamfir)가 주도하고 있는 캐스퍼 CBC는 Correct-by-Construct의 약어로, PoS에 최신 메시지 기반 GHOST(latest message-driven GHOST)를 적용한 완전한 PoS 방식입니다. 지난 글에서 알아봤듯 모든 서명을 DAG로 기록해 한 노드에서도 전체 블록체인 재생성이 가능하고, 기존 BFT보다 가용성이 높습니다.

이번 글에서 중점적으로 다룰 비탈릭 부테린(Vitalik Buterin)의 캐스퍼 FFG는 Friendly Finality Gadget의 약어로, PoW 방식으로 블록을 생성하고 일정 기간(체크포인트)마다 PoS 방식으로 확정성을 부여합니다. 잘못 행동한 검증자에게 합당한 페널티를 어떻게 줄 것인지 그 규칙의 철학과 방식에 유의해서 연구했습니다.

III. 2017년: 최소 삭감 조건

1999년 미구엘 카스트로(Miguel Castro)와 바바라 리스코프(Barbara Liskov)가 발표한 실용적 비잔티움 장애 허용(Practical Byzantine Fault Tolerance) 논문. 퍼포먼스 측정 결과 개발한 비잔티움 장애 허용 알고리즘을 이용한 NFS(네트워크 파일 시스템)가 디지털 유닉스에서 구현한 표준 NFS 속도의 97%에 달했다고 한다.

비탈릭의 28번 트윗처럼, 블록을 확정하는 데는 아래 두 가지 조건이 필요합니다.

  • 안전성(safety): 상충하는 두 블록이 확정되기 위해서는 ⅓ 이상이 삭감 조건을 어겨야 한다.
  • 실질적 생존성(plausible liveness): ⅔ 이상이 정직하다면 삭감 조건을 어기지 않고 새로운 블록을 확정할 수 있다. 즉 알고리즘이 멈추거나 검증자가 자신의 결정을 번복해야 하는 상황이 오지 않는다.

언뜻 보기에 두 조건은 같은 내용을 이야기하는 것 같지만 그렇지 않습니다. 예컨대 안전성은 충족했지만 실질적 생존성은 충족하지 않는 예시가 있습니다.

모든 검증자들이 서명 메시지를 단 한 번만 보낼 수 있는 알고리즘을 가정해봅시다. 한 블록이 2/3 이상의 서명을 받으면 그 블록은 확정되겠죠.

만약 아래 그림과 같이 HASH1와 HASH2 모두 확정되었다면, 두 해시 모두 최소 2/3 이상의 서명을 받았다는 뜻이므로 전체 중 1/3의 검증자가 겹치게 되고 이들의 보증금은 삭감됩니다. 이렇듯 안전성 조건을 충족합니다.

HASH1, HASH2 모두 2/3의 서명을 받아 확정되었다면 상충하는 두 해시에 서명한 1/3의 보증금은 삭감된다. Image by Vitalik Buterin

하지만 이 상황이 오기 전에, 1/2은 HASH1에 서명하고, 다른 1/2은 HASH2에 서명한 상황을 가정해봅시다. 충분히 발생할 수 있는 일이죠. 블록이 확정되기 위해서는 2/3 이상의 서명이 필요합니다. 이미 서명을 마친 검증자 중 1/6은 HASH1에서 HASH2로 옮기든지, HASH2에서 HASH1로 옮기든지 여하튼 자신의 이전 서명에 반하는 다른 서명을 해야 둘 중 어떤 블록이든 확정할 수 있습니다. 그렇지 않으면 영영 1/2 vs 1/2 의 싸움이 되고, 알고리즘은 멈추겠죠. 실질적 생존성이 충족되지 않습니다.

HASH1, HASH2 둘 중 하나가 확정되기 위해서는 보증금 삭감을 감수하고서라도 1/6이 결정을 번복해야 한다. 하지만 아무도 나서지 않는다면, 체인은 여기서 멈춘다. Image by Vitalik Buterin

반대로, 안전성은 충족하지 않지만 실질적 생존성은 충족하는 경우도 있습니다. 그리고 고민 끝에 요이치 히라이[Yoichi Hirai; 이더리움 형식 검증(formal verification) 엔지니어]의 주도로 안전성과 실질적 생존성을 모두 충족하는 알고리즘도 고안해냈습니다. 핵심적인 변화는 바로 투표하고 결과를 보는 것이 아니라, 준비(prepare) 메시지를 보낸 해시에만 서명할 수 있게 됐다는 것입니다. 하지만 이 글에서 상세히 다루기에는 아직 갈 길이 머니까(트윗이 아직 45개나 남았습니다!) 참고하기 좋은 글을 첨부하고 넘어가도록 하겠습니다.

  • 비탈릭이 27번 트윗에서 언급한 Minimal Slashing Conditions의 국문 번역
  • 디사이퍼의 블록체인 확장성 솔루션 시리즈 1–1 :: Casper Overview

처음에 비탈릭이 생각한 네 개의 삭감 조건 중 두 조건을 의무 사항이 아닌 합의 모델의 디자인 옵션으로 두고, 결과적으로 두 개의 삭감 조건을 만들었습니다. 첫째, 검증자는 같은 타겟 높이(target height)에서 두 개 이상 투표할 수 없습니다. 둘째, 검증자는 투표한 타겟들 사이에는 투표할 수 없습니다.

두 개의 삭감 조건. 마찬가지로 자세한 내용은 여기에서 읽을 수 있다. Retrieved from Minimal Slashing Conditions.
요나탄 솜폴린스키(Yonatan Sompolinsky)와 아비브 조하(Aviv Zohar)가 2013년 발표한 논문에 따르면 GHOST는 각 블록이 결국에는 완전히 수용되거나 완전히 버려지게 되며, 50% 공격에 저항성을 가지고 있다. 여기서 GHOST란 The Greedy Heaviest-Observed Sub-Tree의 약자로, 블록에서 트리(tree) 현상이 발생했을 때 가장 많은 하위 트리(sub-tree)들이 관측된 체인을 메인 체인으로 선택하는 방식이다.
가장 긴 체인을 메인체인으로 채택하는 나카모토 컨센서스와 GHOST 방식으로 채택한 체인은 다르다. 맨 아래의 A 공격 체인이 가장 긴 체인을 바꿀 수는 있지만, GHOST 방식일 때는 메인 체인을 바꿀 수 없다. Image by Yonatan Sompolinsky, and Aviv Zohar.

블라드가 선호한 포크 선택 규칙은 최신 메시지 기반 GHOST입니다. 블라드는 GHOST를 PoS 합의 알고리즘에 적용해 처음부터 온전히 PoS만으로 이더리움이 동작하게 연구하고 있습니다.

반면 비탈릭이 선호한 포크 선택 규칙은 먼저 PoW로 블록을 생성하고, 체크포인트(제네시스 블록으로부터 매 50개 블록)마다 투표를 통해 확정하는 방식입니다.

IV. 2017년: 누가 공격했는지 명확하지 않은 경우에 대한 페널티

비탈릭의 말처럼, 원인을 하나로 특정할 수 없는 비단일귀인결함(non-uniquely attributable faults)의 경우에는 누가 공격을 했는지 명확하게 알 수 없습니다. 예를 들어, B가 “A로부터 메시지를 받지 못했다”고 말한다면 우리는 두 가지 상황을 추측해볼 수 있습니다. 첫째, A가 메시지를 보낸 적이 없거나 둘째, B가 메시지를 받지 못한 척 하는 것입니다. 하지만 B의 주장만 듣고는 둘 중 어떤 설명이 진실인지 알 수 없죠. 이를 화자-청자 결함 등가(speaker-listener fault equivalence)라고 합니다.

만일 프로토콜에서 70%의 검증자 메시지만 체인에 포함되어있고, 30%는 포함되어 있지 않다면, 화자-청자 결함 등가에 의하면 실제로 30%가 오프라인으로 전환해서 메시지를 보낸 적이 없거나/70%가 30%를 검열한 뒤 그들로부터 메시지를 받지 못했다고 거짓말을 하고 있을 수 있습니다.이런 경우에 누구에게 페널티를 줘야 할까요? 이에 대해서는 크게 세 가지 학파(school of thoughts)가 있습니다.

비탈릭은 피해의 삼각형(The Triangle of Harm)이라는 글에서 프로토콜(유저), 소수, 다수 검증자 간에 일어날 수 있는 네 가지 공격의 종류를 설명했습니다.

  • 소수가 프로토콜을 공격하는 것: 피니 공격(Finney attacks)
    PoW에서 채굴자가 충분히 컨펌받지 않은 트랜잭션을 이중지출하는 것
  • 소수가 다수를 공격하는 것: 페더 분기(feather forking)
    PoW에서 원하지 않는 트랜잭션이 포함된 블록이 한 번 컨펌받았을 때 이를 되돌리는 것
  • 다수가 프로토콜을 공격하는 것: 일반적인 51% 공격
  • 다수가 소수를 공격하는 것: 51% 검열 공격
    카르텔에 속해있지 않은 소수로부터 온 모든 블록을 수용하지 않는 담합

비탈릭은 ‘PoW에서는 앞의 두 공격(피니 공격, 페더 분기)은 너무 큰 비용이 들기 때문에 어느 정도 방지가 되지만, 51% 공격과 검열 공격에 대해서는 거의 무방비하다’고 지적합니다. 이 경우 다수가 블록 보상을 얻게 되므로 전기세와 장비를 갖추느라 비용을 한 소수가 페널티를 받는 것과 같습니다. 비탈릭은 위에서 말했듯 화자-청자 결함 때문에 소수와 다수의 공격을 구분할 수 없으므로 캐스퍼에서는 양 쪽에 모두 페널티를 주는 방식으로 디자인한다고 말합니다.

또한 그리프(grief; 슬픔)라는 요소를 도입해 공격의 비용과 이득의 정량화를 시도했습니다. 그리프란 피해자가 잃은 돈을 공격자가 잃은 돈으로 나눈 값입니다. 만약 프로토콜 내에서 공격자가 1달러의 비용으로 피해자에게 3달러의 손해를 끼칠 수 있다면 그리프는 3입니다. 무슨 짓을 해도 다른 사람들에게 손해를 끼칠 수 없다면 그리프는 0이고, 비용을 들이지 않고도 손해를 끼칠 수 있다면 무한대입니다.

일반적으로 화자, 청자 이분법적으로 나뉘는 구조에서 그리프는 1 이하로 떨어질 수 없습니다. 비탈릭은 손해의 삼각형 글에서, 작은 스케일의 공격에서는 그리프를 1로 두지만 큰 스케일의 공격에 대해서는 체인이 두 개로 갈라져 하나는 화자가, 하나는 청자가 페널티를 받도록 하고 시장이 공격자를 판단해 체인을 선택하게 하는 방식을 택하는 걸 선호한다고 말합니다. 일반화하기 어려운, 매번 다른 상황을 반영하기 쉽기 때문이겠죠.

동시에 시장의 판단에 온전히 맡기는 것이 최선은 아니라는 생각에 2017년 12월, 클라이언트가 자동으로 검열을 감지할 수 있도록 의심 수준(suspicion score) 개념도 도입합니다.

비탈릭이 그리프와 의심 수준 등의 개념을 도입해가며 인센티브를 연구하고 있을 때, ‘양 쪽 다 크게 페널티를 주자’는 의견인 블라드도 연구를 계속하고 있었습니다. 다음 편에서는 2018년에 있던 비탈릭의 FFG 연구 진전을 포크 선택 규칙에 유의해 살펴보도록 하겠습니다.

두 편에 걸쳐 2015년부터 2017년까지의 캐스퍼 연구 진전을 알아봤습니다. 이번 편은 캐스퍼 연구에서 어떤 문제점들을 발견했는지, 어떻게 해결했는지 표면적으로 이해할 수 있도록 전달해드렸는데, 기술적으로 보다 깊게 이해하고 싶으신 분들은 아래 ‘함께 읽어보면 좋은 글’을 참고해주시기 바랍니다. Follow me and stay tuned! 👏👏


면책조항. 이 글은 매우 개인적인 의견을 담고 있으며, 해시드의 철학이나 다른 멤버들의 생각과 다를 수 있습니다. 글을 올리기 전에 최대한 내용을 신중하게 검토하지만, 읽는 이는 항상 정보를 주체적으로 받아들여야 합니다. 이 글에서 제공하는 정보의 이용 또는 비이용으로 인한 피해, 또는 부정확하거나 불완전한 정보 이용으로 인한 피해에 대한 책임을 지지 않습니다.
인용한 내용에 대해서는 미주에 출처를 표기하며, 별도 출처 표기가 없는 이미지는 저자가 직접 제작한 것입니다. 잘못된 내용에 대한 지적과 다양한 피드백을 환영합니다.

References

[1] Buterin, V. (2018, August 15). Retrieved from https://twitter.com/VitalikButerin/status/1029903234226216960

함께 읽어보면 좋은 글

[1] Buterin, V. (2017, March 2). Minimal Slashing Conditions. Retrieved from https://medium.com/@VitalikButerin/minimal-slashing-conditions-20f0b500fc6c (국문 번역: 유윤재. (2018. March 17). Retrieved from https://medium.com/dnext-post/이더리움-캐스퍼-알고리즘의-최소한의-삭감-조건-90da163d36a0)

[2] 김종호. (2018, April 17). 블록체인 확장성 솔루션 시리즈 1–1 :: Casper. Retrieved from https://medium.com/decipher-media/블록체인-확장성-솔루션-시리즈-1-1-casper-overview-3e0154487458

Like what you read? Give Leah Jang a round of applause.

From a quick cheer to a standing ovation, clap to show how much you enjoyed this story.