비탈릭의 캐스퍼 폭풍 트위터 파헤치기 (하)
A Tweet Storm explaining the History and State of Ethereum’s Casper Research by Vitalik Buterin
비탈릭의 캐스퍼의 역사와 현황에 대한 폭풍 트윗 해설 마지막 편입니다. 전 편에서는 이더리움의 PoS 전환과 함께 채택할 알고리즘과, 전반적으로 적용되는 페널티와 특수한 경우에서의 페널티 규칙을 다뤘습니다.
- 2014년: 보증금과 페널티 방식의 채택
- 2015년: 베팅에 의한 합의(consensus by bet)
- 2017년: 최소 삭감 조건
- 2017년: 누가 공격했는지 명확하지 않은 경우에 대한 페널티
이번 편에서는 비탈릭의 트윗 51번부터 75번까지 살펴보며 올해 캐스퍼 FFG에 있던 주요 변화, 즉각 메시지 기반 GHOST(immediate message-driven GHOST)에 대해 자세히 알아보고 앞으로 남은 캐스퍼 연구에 어떤 것이 있는지 짚어보겠습니다[1].
V. 2018년: FFG 컨트랙트 구현 계획의 폐기
FFG를 컨트랙트로 구현하면 기존에 있던 이더리움 프로토콜 위에서 진행할 수 있어 한결 간단합니다. 2017년 말 출시된 이더리움 테스트넷에서는 캐스퍼 FFG에서 유저들이 노드를 운영하거나, 검증자 역할을 할 수 있습니다. 합의 방식을 PoS로 전환하기 전에도 버그 리포트와 피드백을 받을 수 있고요. 하지만 모든 문제가 해결된 것은 아니었습니다.
우선 솔리디티를 사용하던 이더리움, dApp들과 호환되도록 EVM을 EWASM(Ethereum flavored WebAssembly)로 바꿔야 합니다. 체인이 하나 있는 캐스퍼에서 샤딩을 적용한 캐스퍼로 바꿔야 했습니다. 결국 비탈릭은 하이브리드 캐스퍼 FFG의 컨트랙트화를 취소하는 결정을 내리게 됩니다.
PoS에서는 검증자들이 서명을 하기 위해 트랜잭션을 생성하는데, 이미 유저들의 트랜잭션을 처리하기에도 바쁜 프로토콜에 추가로 초 당 수 만 건의 서명을 하나하나 받기란 비효율적입니다. 이럴 때 쓰이는 것이 BLS 서명 집합(BLS signature aggregation)입니다. BLS를 이용해 여러 공개 키에서 생성된 메시지를 하나의 서명으로 통합할 수 있습니다. 슈노(Schnorr; 비트코인 확장성 솔루션 중 하나)와 유사하지만, 슈노에서는 까다롭던 m-of-n 다중서명 문제를 해결할 수 있고, 블록 내의 서명을 하나의 트랜잭션으로 통합할 수 있는 등 단점을 보완한 방식이죠[2].
비탈릭은 BLS를 이용하되, 하나의 트랜잭션으로 처리되고 말기보다는 보안 효과를 얻고 싶었습니다. 59번 트윗에서 인용한 자신의 글 <증인 위원회 기반 풀 PoS 체인, 버전2>에서 간단한 높이 카운팅(simple height counting)을 이용한 포크 선택 규칙을 설명합니다.
제네시스 블록에서 시작해서 알고리즘이 현재 보고 있는 블록을 현재 블록(current block)이라고 칭한다.
- 현재 블록에 자식 블록(child block)이 없다면, exit한다.
- 현재 블록이 한 자식 블록을 갖고 있다면 해당 자식 블록으로 현재 블록을 설정한다.
- 현재 블록이 둘 이상의 자식 블록을 갖고 있다면 자식 블록이나, 그 후손 블록(descendants; 2대 이상의 자식 블록)에 더 많은 유효한 최신 서명이 있는 블록으로 이동한다.
위를 exit할 때까지 반복하고, 현재 블록을 헤드(head)로 반환한다.
예를 들어 다음 다이어그램에서 A, B… M이 최신 서명일 때, 헤드는 초록색 블록이 됩니다.
- A가 최신 확정된 블록의 유일한 자식이다.
- B가 C보다 더 많은 서명을 갖고 있으므로 B로 이동한다.
- (G H)에는 자신 혹은 후손 블록에 서명이 5개, F에는 3개가 있으므로 (G H)로 이동한다.
- (I J)와 M은 (G H)의 자식 블록이지만 (I J)에는 2개, M에는 1개의 서명이 있으므로 (I J)로 이동한다.
- (I J)에 자식 블록이 없으므로 exit한다.
저스틴 드레이크(Justin Drake)는 작년 12월에 합류한 이더리움 샤딩 연구자로, 더블 배치 머클 로그 어큐뮬레이터(double batch merkle log accumulator), 블롭 직렬화(blob serialisation), BLS를 이용한 실용적 서명 집합(pragmatic signature aggregation with BLS) 등에 대해 연구했습니다[3].
같은 문제에 대해 비탈릭은 블라드가 줄곧 밀어왔던 GHOST 방식을 사용해 솔루션을 제안합니다. 비탈릭이 이전에 썼던 글 <증인 위원회 기반 풀 PoS 체인> 버전 1, 2에서는 해결하지 못한 두 가지 문제가 있었습니다[4].
- 악의적인 제안자에 대한 저항성(Bad proposer resistance)
RNG 조작 등으로 인한 중간 규모의 악의적인 제안자가 있는 경우에는, 상대적으로 작은 검열만으로도 체인을 손상시킬 수 있다. - 안정성(stability)
포크 선택은 미래에 어떤 포크가 선택될지에 대한 훌륭한 예측이어야 한다.
예컨대 아래 모델에서, 빨간색 체인에 악의적인 제안자와 증인만 있다고 가정합시다. 회색 체인에는 모든 제안자가 악의적이지만 증인들은 1/4만 악의적이고 나머지는 정직하다고 가정합니다. 공격자가 A1을 전파한 뒤에 잠시 기다렸다가 B1이 들어있는 체인을 내는 상황입니다.
가장 긴 체인을 선택하는 나카모토 합의에 따르면, 손쉽게 공격 체인이 메인 체인이 되겠죠. 이 경우는 바로 위 59번 트윗에서도 설명했듯 GHOST 점수 매기기 방식을 사용해 방지할 수 있습니다. 정직한 검증자가 점점 더 많이 A1에 증언할수록 회색 체인이 메인 체인이 됩니다. 하지만 GHOST는 안정성이 부족하다는 단점이 있습니다. 예를 들어 아래 다이어그램을 보겠습니다.
하위 트리에 있는 투표 수를 합산하는 것이 PoW에서의 GHOST 방식입니다. 이를 그대로 PoS에 적용한다면 노란색 하위 트리가 96, 초록색 하위 트리가 111으로 초록색 하위 트리가 이기게 됩니다. 노란색 트리 맨 아래에 있는 65% 블록이 정당한 체크포인트(justified checkpoint; 2/3 이상의 투표를 받은 체크포인트)에 더 가까운데도 말이죠. 그렇다면 가장 최신 투표 수만 세는 방식으로 개선할 수 있을까요?
최신 투표 수를 센다면 노란색 체인이 51%, 초록색 체인이 20%으로 노란색 체인이 이기지만, 초록색 체인의 첫 번째 블록은 2% 증언만 더 받으면 정당한 체크포인트가 될 수 있습니다. 어쩌면 네트워크 지연시간이 길어서 늦게 도착한 2%의 증언으로 결과가 뒤집힐 수 있는 것입니다.
따라서 비탈릭은 하위 트리 중 최댓값을 가져오는 방식을 택했습니다. 이 말에는 최댓값 블록이 하위 트리 중 몇 번째에 위치해있든지, 어떤 블록이 2/3 이상의 투표를 받았다면 해당 블록의 이전의 블록들(ancestors)도 정당성을 얻는다는 의미가 포함되어 있습니다.
이런 방식에도 여전히 문제점은 남아있습니다. 다음 다이어그램을 보겠습니다.
포크 선택 규칙에 따르면 초록색 체인이 노란색 체인보다 정당한 체크포인트가 되겠지만, 실제로는 노란색 체인이 더 가능성이 높습니다. 초록색 체인은 2/3를 채우기 위해 추가적으로 7%p의 투표가 필요한데, 이미 모든 검증자가 노란색 체인에 40, 초록색 체인에 60만큼 투표했으므로 7%p의 검증자가 보증금이 삭감되는 걸 감수하면서 투표를 번복해야합니다. 반면 두 번째 세대를 보면 초록색 블록이 5, 노란색 블록이 51으로 시간이 조금 더 흐르면 노란색 체인이 정당한 체크포인트가 될 가능성이 훨씬 높죠.하지만 이런 경우는 아주 심한 공격자가 있거나 네트워크 지연시간이 높은 경우가 아니면 잘 일어나지 않습니다.
안전성(safety), 실질적 생존성(plausible liveness), 동적 검증자 집단에서의 작동 등 비콘 체인 메커니즘에 대해 궁금한 분들을 위해 비탈릭 글을 번역해두었습니다. 국내에 아직 잘 알려지지 않은 개발 내용입니다.
VI. 2018년, 그리고 앞으로: 최근 진행 사항
레슬리 램포트(Leslie Lamport)는 2013년 튜링상을 받은 컴퓨터 과학자로, 1982년 논문 비잔틴 장군 문제 (The Byzantine Generals Problem)의 제1저자입니다[5]. 비잔틴 장군 문제는 컴퓨터 시스템 내에서 하나, 혹은 그 이상의 구성원이 망가지더라도 원활히 운영될 수 있도록 디자인하는 것을 비유적으로 이르는 말입니다.
장군이 이끄는 각 부대들이 적진 근처를 둘러싸고 있고, 장군들은 서로 전령(messenger)을 통해서만 소통할 수 있습니다. 장군들은 언제 적진을 습격할지 전령을 통해 합의해야 하는데 이들 중 몇몇 장군들은 배신자여서 일부러 합의를 망치려고 할 수도 있습니다.
비탈릭은 레슬리 램포트의 논문에서 설명한 99% 장애 허용을 의심 수준에 활용할 수 있다고 말합니다. 비탈릭의 글은 어제 Kyuntae Ethan Kim 님이 자세히 번역해주셨으니 이를 참고하시기 바랍니다.
이렇게 세 편에 걸쳐 기나긴 캐스퍼 대장정을 마쳤습니다. 비록 비탈릭이 트윗 길이를 140자로 제한한 트위터의 의도를 잘 이해한 것 같지는 않지만(…) 말 그대로 2014년부터 2018년까지 캐스퍼의 오랜 역사와 현황, 앞으로 나아갈 길을 알아볼 수 있는 글이었습니다. 트윗에서 언급된 블라드, 저스틴을 비롯한 여러 연구진의 많은 시행착오가 녹아 있어서 세 편의 글로도 그들의 노고를 다 담아내지 못하는 것 같습니다.
너무 쉽지도 어렵지도 않은 난이도로 쓰인 글입니다. 지금 당장 읽으시면서 바로 이해하셔도 좋지만, 책갈피를 해두고, 시간이 날 때, 캐스퍼에 관심이 생겼을 때, 혹은 캐스퍼가 구현되었을 때 차분히 읽어볼 수 있는 도움되는 글이 되었길 바랍니다. 마지막으로 요약을 남기고 저도 이만 총총 물러나도록 하겠습니다. 감사합니다 :)
정리
Nothing-at-stake 문제의 해결
- Nothing-at-stake: 체인에서 포크가 발생해 검증자가 투표해야 하는 상황에서, 두 블록 모두에 투표해도 검증자 입장에서는 손해보는 게 없다는 문제점(무위험 베팅)
- 해결: 블록에 투표하는 검증자들이 보증금을 예치해두고, 서로 충돌하는 내용을 담은 메시지에 서명하면 보증금을 삭감하는 방식으로 페널티 부여
- 뇌물 공격(bribe attack) → 현재 잔고가 0인 검증자의 서명은 무효함.
CBC vs. FFG
포크 선택 규칙: 최신 메시지 기반 vs 즉각 메시지 기반 GHOST
Casper History and State
#HASHED
Check out our new Telegram Channel and other community links below! 🙂
- Telegram Channel : t.me/hashedchannel
- Telegram Lounge : t.me/hashedlounge
- Medium : medium.com/hashed-kr
- Facebook : facebook.com/hashedfund
- YouTube : youtube.com/c/hashedlounge
- Twitter : twitter.com/hashed_official
면책조항. 이 글은 매우 개인적인 의견을 담고 있으며, 해시드의 철학이나 다른 멤버들의 생각과 다를 수 있습니다. 글을 올리기 전에 최대한 내용을 신중하게 검토하지만, 읽는 이는 항상 정보를 주체적으로 받아들여야 합니다. 이 글에서 제공하는 정보의 이용 또는 비이용으로 인한 피해, 또는 부정확하거나 불완전한 정보 이용으로 인한 피해에 대한 책임을 지지 않습니다.
인용한 내용에 대해서는 미주에 출처를 표기하며, 별도 출처 표기가 없는 이미지는 저자가 직접 제작한 것입니다. 잘못된 내용에 대한 지적과 다양한 피드백을 환영합니다.
References
[1] Buterin, V. (2018, August 15). Retrieved from https://twitter.com/VitalikButerin/status/1029905492347215873
[2] Snigirev, S. (2018, June 25). Retrieved from https://medium.com/@snigirev.stepan/bls-signatures-better-than-schnorr-5a7fe30ea716
[3] https://ethresear.ch/u/justindrake/activity/topics
[4] Buterin, V. (2018, June 15). Retrieved from https://ethresear.ch/t/attestation-committee-based-full-pos-chains/2259
[5] Lamport, L., Shostak, R., & Pease, M. (1982). The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), pp. 382–401. http://dx.doi.org/10.1145/357172.357176
함께 읽어보면 좋은 글
[1] Buterin, V. (2018, August 7). A Guide to 99% Fault Tolerant Consensus. Retrieved from https://vitalik.ca/general/2018/08/07/99_fault_tolerant.html (국문 번역: 김균태. (2018, August 29). 99% 장애허용 합의를 위한 지침서. Retrieved from https://medium.com/hashed-kr/guide-to-99-fault-tolerant-consensus-kr-91cdab922b8e)
[Hashed Community]
Hashed Website: hashed.com
Facebook: facebook.com/hashedfund
Medium: medium.com/hashed-official
twitter: twitter.com/hashed_official
Telegram: t.me/hashedchannel
