블록체인 확장성 솔루션 시리즈 4–2 :: Sharding Q&A / Code Review
Jongbok Lee(Jongbok Lee)
SeJin OH (Se Jin OH)
Geore Han(Han Geore)
Special Thanks to Jihyeok Choy(Jihyeok Choy) , Jeongho Jeon(Jeongho Jeon) Jaeyun Kim(Jaeyun Kim)!
Seoul Nat’l Univ. Blockchain Academy Decipher(@decipher-media)
서울대학교 블록체인 학회 ‘디사이퍼(Decipher)’에서 블록체인의 스케일링 솔루션에 관한 글들을 시리즈로 연재합니다. 시리즈의 네 번째 주인공은 Ethereum의 “Sharding”입니다. 4–1. Sharding Overview, 4–2.Sharding Q&A / Code Review로 나누어 설명합니다.
앞 글에서는 샤딩의 개념과 전반적인 작동 원리에 대해 알아보았다. 다시 한 번 용어 정리가 필요하다면 4–1 Sharding Overview 를 참고하면 도움될 것이다. 이번 글에서는 샤딩 Q&A와 코드 리뷰를 통해서 좀 더 깊이있고 자세한 내용을 다뤄보도록 하겠다. 코드 리뷰는 ethereum github에 구현된 sharding_manager.v.py를 참고해서 작성하였다.(2018년 6월 25일 기준) 샤딩은 지금도 끊임없이 발전하고 있는 중이므로 계속해서 새로운 내용이 업데이트 되고 있다는 것을 염두에 두기를 바란다.
[Sharding Q&A]
아래에서부터 다음의 5개 질문을 다룰 예정이다.
Q1. 샤딩에서 발생할 수 있는 1% 공격이란 어떤 공격이고 이에 대한 대응책은 무엇인가?
Q2. 샤딩이 PoS 합의 알고리즘에 기반할 때, pseudo-random sampling은 어떻게 동작하는가?
Q3. Casper FFG(PoS)와 샤딩은 어떤 관계인가?
Q4. Cross-shard communication이란 무엇이고 다른 샤드 간 트랜잭션 전송은 어떻게 실현되는가?
Q5. 현재 샤딩의 구현 상태는? (2018년 6월 25일 기준)
- 샤딩에서 발생할 수 있는 1% 공격이란 어떤 공격이고 이에 대한 대응책은 무엇인가?
샤딩에서 발생할 수 있는 주요 공격은 1% 공격이다. 1% 공격은 전체 네트워크를 여러 개의 샤드로 분할하는 샤딩의 특성으로부터 비롯된다. 예를 들어, 샤드가 100개로 나뉘어져 있을 때 공격자는 특정 샤드를 공격하기 위해서 전체 네트워크의 hash power 중 오직 1%만으로도 샤드를 비잔틴 상태로 만들 수 있다.
1% 공격에 대한 대응책으로는 앞 글에서 설명했던 pseudo-random sampling이다. Pseudo-random sampling을 통해 샤드에서 검증 작업을 수행하는 collator들을 주기적으로 변경해줌으로써 collator들이 하나의 샤드에서 공모할 가능성을 낮춰준다.
2. 샤딩이 PoS 합의 알고리즘에 기반할 때, pseudo-random sampling은 어떻게 동작하는가?
Pseudo-random sampling은 매 period, 각각의 샤드에 대해 committee(검증인 집단)을 구성하는 방식으로 발생한다. 랜덤 시드에서 특정한 랜덤값을 추출하는데, 이는 아래의 코드 리뷰에서 좀 더 자세히 소개될 것이다.
Pseudo-random sampling의 프로세스는 다음과 같다. 우선, 각 샤드에는 일정한 수의 collator(e.g. 150)가 지정되며 각 샤드에서 collation을 검증하는 collator는 해당 샤드의 pool에서 가져온다. Pool은 collator들의 주소로 이루어졌으며, 12시간에 한 번 혹은 그것보다 더 빈번하게 sampling 될 수 있다.
Pool의 sampling 주기는 dishonest collator들의 공격 주기에 따라 영향 받는다. 예를 들어, dishonest collator들의 공격 주기가 6시간이라면, sampling 주기는 6시간 보다 짧아야 한다.
중요한 점은 Pseudo-random sampling을 통해 collator들이 ‘강제로’ 배정된다는 것이다. Collator들이 주기적으로 sampling된다는 점, 그리고 collator들은 자신이 검증할 샤드를 선택할 수 없다는 점, 이 두 가지 점이 collator간의 모의를 막는 핵심 요소다.
3. Casper FFG(PoS)와 샤딩은 어떤 관계인가?
일반적인 PoW는 finality가 확률적이고, 잠정적이다. 이는 PoW에서는 공격자들의 공격(e.g. 51%공격)에 따라서 체인이 변경될 수 있다는 것이다. 반면, Casper FFG(PoS)는 finality가 확정적이다. PoS의 validator들의 투표에 의해 finalized된 블록은 이후에 변경되지 않는다.
샤딩에서 샤드 체인은 메인 체인에 pegged되어 있다. 매 period마다 샤드 체인에 collator가 랜덤하게 배정되므로, collator는 자신이 어떤 샤드 체인에 배정되는지 알기 위해서 SMC를 관찰해야 한다.
Collator는 샤드 체인에 배정되면 그 샤드 체인의 정보를 sync해야 한다. 이 때, Casper FFG(PoS)의 finality가 확정적이라는 점이 중요한데, 그 이유는 메인 체인과 수많은 샤드 체인 간 정보를 sync하는데 불확실성을 줄여주기 때문이다.
4. Cross-shard communication이란 무엇이고 다른 샤드 간 트랜잭션 전송은 어떻게 실현되는가?
이더리움에서 샤딩이 실현되면 샤드 내 트랜잭션 뿐만 아니라 샤드 간 트랜잭션 요청도 발생할 것이다. 이 때 샤드 간에 트랜잭션을 전송하는 것을 Cross-shard communication이라고 한다. Cross-shard communication은 트랜잭션의 결과로 생기는 receipt에 기반해서 실현되기 때문에 Receipt-based communication이라고도 한다. 여기서 핵심은 Receipt에 담긴 merkle proof가 하나의 샤드에서 메인 체인을 거쳐 다른 샤드로 이동한다는 것이다.
아래 그림을 통해 Cross-shard communication의 구체적인 프로세스를 이해해보자. 우선, 두 개의 샤드(샤드 M, 샤드 N)이 있고, 샤드 M의 account A에서 샤드 N의 account B로 트랜잭션을 보낸다고 가정한다.
1) 샤드 M의 account A의 잔액을 100코인만큼 차감하고 receipt를 만든다. Receipt를 포함한 merkle proof가 생성된다.
2) 트랜잭션이 collation에 포함되고 메인 체인의 블록에 포함되기를 기다린다.
3) 메인 체인의 블록에 트랜잭션이 포함되면 SMC가 샤드 N으로 receipt를 전달한다. 샤드 N은 Receipt를 전달 받고,
3–1) Receipt가 unspent인지 확인하고,
3–2) 샤드 N의 account B의 잔액을 100코인만큼 증가시킨다.
그 후 receipt를 spend한다.
4) 샤드 N에서 receipt를 소모했음이 메인 체인을 거쳐 샤드 M으로 전달한다. 샤드 M은 보유하고 있던 트랜잭션의 receipt를 삭제한다. 이로써 트랜잭션의 전 과정이 완료된다.
5. 현재 샤딩의 구현 상태는? [Code Review]
코드 리뷰는 크게 여섯 파트로 나눠서 설명하겠다. 각각을 이해하기 위해 핵심적인 부분을 제외한 일부는 생략되었으므로, 자세한 코드는 ethereum github을 통해 확인하는 것을 추천한다.
이전 포스트에서 샤드 체인이 동작하는 프로세스를 다음과 같이 설명했다.
Proposer/Collator가 SMC에 deposit 예치함으로써 등록(Register_notary)
-> Proposer/Collator가 특정 Period에 샤드에 배정(get_member_of_committee)
-> Collator가 proposer가 생성한 proposal에 투표.
2/3이상의 투표를 받으면 collation 생성(submitvote)
-> Collation header를 SMC에 전송(addheader)
-> Proposer/Collator 해제(Deregister_notary)
-> Proposer/Collator에게 deposit 반환(Release_notary)
코드 리뷰 역시 위의 샤드 체인 동작 프로세스에 따라 진행하도록 하겠다.
Shard chain Registering & Pseudo-Random Sampling process
우선 본격적인 코드리뷰 전에 몇 가지 개념을 소개하겠다. 본 리뷰에서는 Notary라는 개념이 등장하는데, Notary는 샤딩의 참가자를 의미하며 proposer와 collator를 합친 개념이다. Notary는 pool과 registry에 등록되어야만 자신의 역할을 수행할 수 있다.
Pool과 Registry는 잘 구분해서 이해해야 하는 개념이다. Pool과 Registry는 notary의 데이터를 관리한다. Pool은 notary의 address를, Registry는 Deregistered, pool_index, deposit 3개의 데이터를 관리한다. Deregistered는 notary가 해제된 period, pool_index는 notary의 index, deposit은 notary의 예치금이다. Notary는 Deregistered period로부터 일정 기간(lockup period)만큼 지난 후에야 자신의 예치금을 돌려받을 수 있다.
마지막으로 Committee는 특정 Period에 샤드에 배치되는 notary의 집합이다. Committee 등록은 SMC의 pseudo-random sampling을 통해 발생한다. Notary는 반드시 committee에 등록되어야만 collation 검증에 참여할 수 있다.
1. Register_notary
샤딩의 notary 등록은 2가지 검사로부터 시작한다. 첫째로, 메시지 호출자(msg.sender)가 보내는 예치금(msg.value)이 지정된 값(NOTARY_DEPOSIT)보다 커야하며(2) 둘째로, Msg.sender가 registry에 등록되어 있지 않음을 확인해야 한다.(3)
조건을 만족하면, Msg.sender를 notary pool과 registry에 등록한다.(7, 11) Deregistered, pool_index, deposit이 기록된다. Deregistered는 0으로 기록되는데, 이는 notary가 deregistered되지 않았음을 의미한다.(11~14) 마지막으로 RegisteryNotary 이벤트를 처리하고 마무리한다.(18~20)
2. Get_member_of_committee
이제 Notary가 Register되었으니, 실제 collation 검증을 수행할 committee를 구성해야 한다.
Get_member_of_committee는 특정 period에 샤드에서 collation 검증을 수행할 notary를 선출한다. Get_member_of_committee는 Shard_id의 조건을 검사함으로써 시작한다.(6) 한 Period에서 committee의 수는 정확히 샤드 체인의 수와 같다.
다음은 Sampled_index를 만드는데 이것이 SMC의 pseudo-random sampling이다. 이더리움의 스마트 컨트랙트에는 랜덤 함수가 없다. 그래서 이러한 과정을 통해 랜덤 값을 만든다. Sampled_index는 세 가지 값(Entropy_block_number, shard_id, index)으로 만든다. Entropy_block_number는 이전 period의 마지막 블록이다. 이 세 가지 값은 period와 샤드, notary의 index에 따라 계속 변하기 때문에 pseudo-random sampling을 가능하게 한다. (19~30)
세 가지 값을 합친 후 sha3함수로 해시를 만들고 sample_size로 나눈다. 그 결과 Notary pool에서 sampled_index에 해당하는 값을 committee의 멤버로 선출한다.(32)
3. Submit_vote
Submitvote는 committee에 속한 notary들이 proposal에 포함된 트랜잭션 및 데이터가 유효한지 투표한다. 투표 결과 일정 정족수(⅔)가 넘는 proposal은 collation으로 채택되고, 그 header가 SMC에 제출된다.
Submitvote는 여러 조건을 검사하면서 시작한다. 그 중에서 중요한 것은 Msg.sender가 committee의 멤버 인지 확인하고(16) Notary가 아직 투표하지 않았음을 확인(21)하는 것이다. Notary는 반드시 committee의 멤버여야 하며, 중복 투표는 불가능하다. 검사를 마친 후 Notary의 vote count를 업데이트한다.(24) 이는 Notary의 투표가 반영되었음을 의미한다.
Submitvote를 호출할 때마다 vote count는 1씩 증가한다. Vote count가 증가하다가 정족수(QUORUM_SIZE, committee의 2/3이상)보다 크거나 같아지면, collation이 채택(is_elected)된다. (27~31) Collation이 채택된다는 의미는 collation header가 SMC로 보내질 준비가 되었다는 것이다.
그리고 collation의 period를 현재 period로 업데이트 한다. 마지막으로 Submitvote 이벤트를 처리하고 마무리 한다.(34~41)
4. Add_header
Add_header는 투표 이후 생성된 collation header를 메인 체인의 SMC에 전송한다. Notary의 투표에 의해 채택된 collation은 반드시 SMC의 검증을 거쳐야만 유효한 collation이 된다. Add_header는 우선 샤드 ID, period, 그리고 처음 제출된 header인지를 검사한다.(7~12)
한 Period에 하나의 샤드에서는 오직 한 개의 collation header만 제출될 수 있다.(12)
Collation records에는 collation의 3가지 정보(chunk_root, proposer, is_elected)가 저장된다. (14~17) Chunk_root는 블록의 transaction_root와 같은 개념이다. Chunk_root는 collation 내의 트랜잭션들의 정보를 담고 있다.
Records_updated_period는 현재 period를 기록한다. Collation header를 제출했으므로, current_vote를 초기화한다.(24) 마지막으로 Addheader 이벤트를 처리함으로써 마무리된다.(27~30)
5. Deregister_notary
Notary는 collation 검증을 그만두고 싶으면 deregister_notary를 호출한다. Deregister_notary는 msg.sender가 registry에 notary로 등록되어 있는지 검사하는데서 출발한다.(2)
그 다음 Notary를 notary pool에서 제거한다. Notary pool에서 index 값을 none으로 바꾸고, notary pool의 크기를 1만큼 뺀다.(6~8) Notary registry는 deregistered를 통해 deregister가 발생한 period를 기록한다.
Deregistered를 통해 현재 period에서 deregister되었음을 기록한다.(10) 마지막으로 DeregisterNotary 이벤트를 처리한 후 마무리 된다.(12~13)
6. Release_notary
Notary가 deregister된 이후에 실제 자신의 deposit은 release_notary를 호출함으로써 되찾을 수 있다. Release_notary는 3가지 조건을 검사함으로써 시작된다. 제일 중요한 것은 Msg.sender가 이미 deregister되었는지 확인하는 것이다.(3) Release는 이미 Deregister된 notary에 한해서 가능하기 때문이다. Release는 deregister period보다 최소 LOCKUP_LENGTH만큼 지난 후에 가능하다.(4~5)
Release가 되면 msg.sender의 모든 정보는 registry에서 삭제된다. Msg.sender의 Deregistered, pool_index, deposit이 모두 0으로 초기화된다 (10~13)
Msg.sender가 registry에서 제거되었음을 기록하고, msg.sender에게 deposit을 반환한다.(17) 마지막으로 ReleaseNotary 이벤트를 처리함으로써 마무리된다.(19~21)
샤딩은 지금도 계속해서 업데이트 되고 있다. 최근 이더리움 재단에서는 Casper FFG(PoS)와 샤딩이 결합된 개념인 “beacon chain”이라는 연구 결과를 발표했다. 이렇듯 이더리움 재단은 이더리움의 확장성 문제를 해결하기 위해 본격적인 박차를 가하고 있고, 그 중심에는 샤딩이 있다.
확장성 문제는 블록체인이 당면한 현실이고 이 문제에 많은 논의와 자원이 집중되고 있는 만큼, 이 문제에 지속적인 관심을 갖는다면 블록체인과 이더리움의 현주소를 이해하는데 큰 도움이 될 것이다.
