Sharding, Casper → Serenity!

Devcon4 참관기

Published in

Tokamak Network

17 min readDec 5, 2018

온더는 이더리움 블록체인의 확장성 솔루션 Plasma 체인을 연구개발하는 회사입니다. 온더의 비전은 이더리움 블록체인 기술의 사용성을 제고시키고, 암호경제와 현실경제를 연동시켜 지금보다 더 나은 세상을 만드는 것입니다.

Devcon4 에서 Serenity 와 관련한 유익한 발표들이 많았습니다. 기본적인 샤딩의 Overview와 함께 Devcon4에서 다뤘던 주제들을 살펴보도록 하겠습니다. 아래 정보들은 현재 리서치 진행중인 부분도 있어 세부적인 내용은 변경될 수 있습니다. 따라서 이 글의 목적은 개괄적인 아이디어와 관련 이슈들을 파악하는 것입니다.

1. Sharding (Overview)

비탈릭이 작성한 https://vitalik.ca/files/Ithaca201807_Sharding.pdf 의 기본적인 샤딩 아이디어를 간단히 살펴보겠습니다. 일반적인 컴퓨터가 O(c) 의 연산 능력을 가지고 블록체인의 총 load가 O(n) 일 때 아래 삼각형의 세 특성을 다음과 같이 설명할 수 있습니다.

Decentralization: 모든 노드가 O(c)의 연산 능력만을 가진 상황에서 시스템이 동작할 수 있음.
Security: 마이너 혹은 검증자의 일부 (e.g. 33%) 의 공격에도 시스템이 올바르게 동작할 수 있음.
Scalability: 시스템이 O(n) > O(c) 인 load 를 처리할 수 있음. 오늘날의 블록체인은 O(n) <= O(c) 인 load 만 처리할 수 있습니다.

앞으로 “O(n) > O(c) 이기 때문에” 라는 표현이 매우 자주 등장합니다.

샤딩에서는 O(n) > O(c) 이기 때문에 필연적으로 각 노드는 데이터의 일부만을 검증할 수 있습니다. 가령 N = 100 * C 이라고 한다면, 각 노드는 전체 블록체인의 1%만을 검증할 수 있는데, 자신이 검증하지 않은 데이터가 공격자에 의해 손상되었을 경우를 1% 공격 이라고 부릅니다.

모든 데이터를 직접 검증할 수 없기 때문에 (O(n) > O(c)), 아래와 같은 방식을 통해 간접적으로 검증을 시도하여 기존의 full validation (in a single node)과 동일한 수준의 Security 를 가진 프로토콜을 구현하는 것이 샤딩의 목적입니다.

Committee voting: 특정 샤드 블록이 메인 블록에 포함될지를 투표를 통해 결정합니다. 하지만 검증자의 다수(e.g. 2/3)가 정직해야 한다는 security assumption 을 가집니다. (Honest majority)
Cryptoeconomic: incentive / disincentive 를 통해 사용자가 프로토콜에 “올바르게" 참여할 수 있도록 유도합니다.
Cryptographic: hash function, digital signature, zk proof, signature aggregation 등 암호학의 유용한 도구를 사용합니다.
Probabilistic: 공격이 발생할 수 있는 확률이 매우 작다면 (2⁻⁴⁰) 를 이를 무시하고 안전하다고 간주합니다. hash collision, zk proof verification 등에 사용됩니다.

Minimum safe committee size

Casper FFG(Overview, Paper)는 참여자의 2/3 이상이 정직해야 한다는 security assumption 을 (약하게) 가지기 때문에, 랜덤 샘플링을 통해 선정된 Committee 의 2/3 이상이 공격자가 아니도록 검증자를 충분히 확보하여야 합니다. 즉, “Committee의 수가 N, 전체 검증인에서 공격자의 비율이 P, 전체 검증인 중 N명의 committee 를 무작위하게 뽑을 때 해당 committee 에 공격자가 1-P 만큼 선택될 확률(honest majority가 깨질 확률)을 t라고 한다면, t는 무시할 수 있을 만큼 작아야 합니다.”

공격자일 확률이 이항분포를 따르고 P = 1/3, N = 111 일 때 committee의 1-P = 2/3 이상이 공격자가 될 확률 t는 t < 2⁻⁴⁰ 로 충분히 작습니다. 이는 해당 자료의 파이선 코드를 아래와같이 사용할 경우 확인이 가능합니다.

만약 공격자가 RANDAO 가 생성한 RNG를 40비트 만큼 조작할 수 있을 경우, t가 80비트 이하의 확률로 더 낮아지도록 하기 위해선 committee 의 수(N)를 231로 늘리면 됩니다. 혹은 P = 2/5, t < 2⁻⁴⁰와 같은 좀 더 엄격한 룰을 적용하고자 한다면 N >= 315 이면 됩니다.

샤딩 로드맵과 Prysmatic Labs 글에 따르면 기존의 이더리움 체인은 i) 기존의 메인체인, ii) PoS 비콘 체인(RANDAO, Phase 0), iii) 샤드 체인으로 나누어집니다. 샤드 체인이 각 어카운트의 데이터를 저장하고(Phase 1) 트랜잭션이 실행(Phase 2)되는 곳이며, 만약 해당 트랜잭션이 다른 샤드에 있는 어카운트와 통신해야할 경우 Cross-shard 트랜잭션(혹은 crosslink, Phase 2, 4)를 통해 이를 수행한다고 합니다.

사족으로 Phase 2 에서 eWASM과 Account abstraction 같은 기존에 논의되던 개선안이 적용될 예정이며, crosslink 는 우선은 Phase 2 에서 비동기적으로, Phase 4 에서 동기적으로 동작할 예정입니다. Phase 3 에서 트랜잭션 실행을 샤드 체인에서 별도의 executor 로 분리합니다.

Asynchronous cross-shard communication

샤드 M의 어카운트 A가 샤드 N의 어카운트 B에게 100 코인을 보내는 트랜잭션의 경우는 아래의 방식으로 처리할 수 있습니다.

해당 트랜잭션을 샤드 M에게 보내고 i) A의 코인 잔액에서 100 코인을 차감한 후 ii) receipt를 생성합니다. 해당 receipt은 상태에 저장되진 않지만 merkle proof 를 통해 증명가능합니다.
트랜잭션이 샤드 블록(collation)에 포함되기를 기다립니다.
1의 receipt와 해당 merkle proof가 포함된 트랜잭션을 샤드 N에게 보냅니다. 해당 트랜잭션은 receipt 가 처리되지 않았는지 확인하고 B의 코인 잔액을 100 증가시킵니다.
(Optional) 3의 트랜잭션또한 receipt를 생성합니다. 마찬가지 방식으로 receipt 을 샤드 M에 보낸 후, 추가적인 처리를 합니다. (만약 3의 트랜잭션이 revert 되었을 경우 4번 과정에서 샤드 N에서 전체 트랜잭션을 revert 처리할 수 있을 것 같습니다.)

실제로는 트랜잭션 하나가 단 두개의 어카운트에게만 영향을 끼치지 않고 여러 샤드 전체에 영향을 끼칠 수 있을 것입니다. 또한 동기적으로 여러 샤드에서 어카운트의 상태 데이터를 요청할 수 도 있습니다.

위와같은 atomic transaction을 처리하기엔 비동기적인 실행 모델을 적절하지 않습니다. 대표적인 예로 train and hotel problem이 있는데, 기차와 호텔 모두를 동시에 예약하는 atomic transaction 을 비동기적으로 실행할 경우 누구도 예약하지 못하는 상황에 빠질 수 있습니다. 이에 대한 대안으로 cross-sharding locking scheme, Cross-shard contract yanking, Simple synchronous cross-shard transaction protocol 등이 있지만 아직 리서치가 충분히 되지 않은 모습입니다.

Yanking

트랜잭션이 실행되는 컨트랙트 A가 샤드 N에 있을 때, 컨트랙의 상태를 receipt에 저장한 이후 이를 컨트랙트 B가 있는 샤드 M에게 전달합니다. 샤드 M에서 해당 receipt를 이용하여 컨트랙트 A의 상태를 이용한 트랜잭션의 처리가 가능합니다. 이 때 까지는 컨트랙트 A는 샤드 M에 있으며, 필요할 경우 다시 샤드 N으로 이동할 수 있습니다.

Train and hotel problem 의 경우 아래와같이 yanking 하여 해결할 수 있습니다.

샤드 N의 TrainBook 컨트랙을 추출하여 샤드 M에 yank 합니다.
HotelBook 컨트랙 혹은 TrainBook 컨트랙 하나라도 예약할 수 없다면 revert 합니다.
atomic 하게 호텔과 기차 모두를 예약합니다.
TrainBook 컨트랙을 샤드 N으로 다시 되돌립니다(yank back).

Fault proof

트랜잭션의 실행이 각 샤드체인에서 처리되기 때문에 실행 결과가 올바른지 검증하는 작업이 필요합니다. 트랜잭션의 실행은 트랜잭션 정보와 컨트랙트 어카운트의 bytecode 를 이용하여 EVM을 순차적으로 실행하는 것이기 때문에 실행 결과를 y=fn(fn−1(…(f1(x))…)) 로 표현할 수 있습니다.

따라서 트랜잭션 실행의 검증을 위해서 fi() 의 실행 결과를 비교하고 만약 실제 실행 결과와 제출된 결과가 다를 경우 challenge 를 수행할 수 있습니다. 하지만 O(n) > O(c) 이기 때문에 전체 상태 또한 O(c) 이상일 수 있습니다. 따라서 fi() 만 단독으로 검증하기 위한 방법이 필요한데, 이를위해 merkle state trees(like asynchronous accumulators) 와 witnesses 를 이용한 stateless client model 이 사용될 수 있습니다.

Stateless model

[7], [8]에서 기존의 Patricia Tree 를 이용한 상태 저장 및 블록의 검증을 히스토리 기반의 검증으로 바꾸려는 시도가 논의되고 있습니다. 여기서 히스토리는 블록, 트랜잭션, receipt 등을 가리키며 immutable past, append-only 의 특성을 가지고있습니다. 그와 반면 상태는 히스토리를 기반으로 변경된 현재의 상태를 가리킵니다.

이더리움 1.0 에서는 블록의 유효성을 검증하기 위하여 상태에 의존해왔고, 히스토리는 단지 그 상태를 변경시키는 기록으로서의 역할만을 해왔습니다. 비유적으로 해당 글에서는 히스토리를 second-class citizen, 상태를 first-class citizen 이라 표현했습니다. 하지만 이더리움 2.0 에서는 “history first, state second” 입니다.

State Storage

샤딩 디자인에서 CA의 상태 스토리지는 명시적으로 저장되지 않습니다. 그 대신 CA의 상태 스토리지(기존의 Patricia trie)를 읽거나 변경시키는 트랜잭션은 witness (스토리지의 Merkle branch)를 포함해야 합니다. witness는 마이너 혹은 트랜잭션 생성자가 포함하며, 만약 witness 를 포함시키지 않은 트랜잭션을 보내고자 한다면 상태 스토리지를 위한 공간을 비용을 지불하여 rent 할 수 있습니다.

State-minimised executions

on-chain 에 기록된 log들만을 이용하면 normal stateful contract C와 동일한 state-minimised contract C’ 을 만들 수 있습니다. C’ 은 virtual state 를 가지며 다음과같이 유지됩니다.

C’은 특정 샤드 블록 높이에서 virtual state root 를 저장합니다.
사용자들은 [LOG T] 의 형태로 “virtual transactions”를 보냅니다.
C’의 virtual transaction 은 C의 전통적인 트랜잭션처럼 처리됩니다.
“executor” 들은 unconfirmed 상태의 최신 collation 에서의 virtual state roots 를 제안할 수 있습니다. 물론 이 때 executor 가 잘못된 데이터를 전달할 경우 TrueBit 과 같은 방식으로 검증 및 challenge를 할 수 있습니다.

Log accumulator

ethresearch에 18년 1월경 올라온 Double-batched Merkle log accumulator 에 따르면 stateless client 에서 사용할 history object 를 위한 이상적인 accumulator 를 “발견”했다고 합니다. asynchronous accumulator를 이용한 log accumulator 가 Patricia trie 보다 저렴한 이유는 3가지가 있습니다.

log witnesses는 state witnesses 와 다르게 insertion / deletion 에 대해서 매 번 업데이트 될 필요가 없습니다. 오직 단 한 번만 업데이트 됩니다. 이로 인해 validator 들이 지속적으로 log witnesses 를 업데이트 하지 않아도 되기에 많은 부분(shard synchronization, CPU / RAM resource)에서 간소화되는 이점들이 많습니다. 또한 log accumulator 를 프로토콜 레벨에서 사용할 수 있다면 receipt(~logs) 기반의 asynchronous cross-shard 트랜잭션을 처리하기 쉬울 것입니다. (log shard)
log witness 의 크기는 log(#objects in a single collation) 인 반면 state trie의 witness log(#total state objects) 입니다. state objects 는 objects in a single collation과 비교하여 누적되어 매우 빠르게 증가할 수 있습니다.
log shard와 custom execution model(like this) 를 이용하여 off-chain computation 을 이용할 경우 비용이 더 낮다고 주장합니다.

Data availability problem

stateless model 에서는 클라이언트가 검증에 필요한 데이터를 항상 가지고있지 않기 때문에 P2P 통신을 통해 데이터를 받아와야 하는데, 이 때 일부의 데이터가 누락될 수 있습니다. 가령 committee 가 합의한 블록을 로컬 클라이언트가 검증하려고할 때 일부 validator 가 데이터를 제공하지 않을 수 있습니다. 혹은 transaction witness 를 proposer가 제공해주지 않아 validator 가 합의를 하지 못할 수 있습니다. 이를 방지하기위해 데이터를 제공하는 측이 deposit 을 걸고 challenge 를 당할 경우 해당 데이터의 merkle branch 를 통해 응답할 수 있습니다.

Fault proof 에서는 ZKP(zero-knowledge proofs)을 이용하여 데이터의 정합성(validity)만을 확인할 수 있습니다. StarkWare 에서 이더리움에 적용할 ZKP 시스템을 연구 및 개발하고 있기에 이를 이용하여 fault proof 를 개선할 수 있습니다. 하지만 data availability는 데이터를 완전히 전달 받았는지에 대한 문제이기 때문에 ZKP 를 이용하여 해결할 수 없습니다.

Fisherman’s dilemma

만약 데이터 publisher 가 일부 데이터를 유실한 채 데이터를 전송했을 경우, fisherman 이 이를 감지하고 challenge 를 수행할 수 있습니다. (case 1) 하지만 fisherman 이 데이터가 모두 제공 되었음에도 불구하고 false challenge 를 수행할 수 도 있습니다. (case 2) 이 두 가지 경우 누가 malicious 행동을 하고있는지 판단할 수 있는 근거를 찾을 수 없습니다. 뿐만아니라 fisherman 의 보상이 0보다 클 때, 0일 때, 0보다 작을 때 경우 모두 취약점이 존재하기 때문에 challenge-based scheme 을 이용하여 data availability 를 “온전히” 해결할 수 없습니다.

Erasure coding

이에 대한 해결책으로 데이터의 일부가 유실되어도 복구할 수 있는 방법인 erasure coding을 이용합니다. Light client는 erasure code를 이용하여 확률적으로 블록의 data availability를 검증합니다. Block header에 기록된 merkle root를 이용하여 block body를 20개의 chunk로 나누어 네트워크에서 merkle branch를 다운로드 받습니다. 만약 모든 다운로드 요청이 유효한 응답을 받는다면 해당 블록 데이터가 available 하다고 판단합니다. 이는 네트워크에 적어도 유효한 블록 데이터를 제공하는 정직한 노드들이 있다는 honest minority assumption을 이용합니다.

Erasure coding의 proof는 one-dimensional Reed-Solomon code를 이용할 경우 원본 데이터와 동일한 사이즈를 가지지만, 다음과 같은 최적화를 통해 proof 생성 시간과 trade-off 하여, fault proof의 사이즈와 fault proof 검증 시간을 매우 줄일 수 있습니다. 물론 이는 zk-S[NT]ARK를 이용할 경우 proof 자체의 사이즈를 더 줄이고, block state transition 또한 함께 검증할 수 있으니 최적화 여지가 더 있습니다.

2. P2P network layer

기존의 블록체인과 다르게 샤딩에서는 더 작은 사이즈의 데이터를 많은 노드들로부터 빈번하게 다운로드 합니다. 가령 validator 가 다른 shard chain에 할당되어 해당 체인의 동기화 과정이 필요할 것이고, light client는 블록 검증을 위하여 여러 다른 노드와 erasure code를 주고 받아야 합니다. 따라서 기존의 devp2p(RLPx)가 아닌 libp2p를 p2p network layer로 이용합니다. 특히 libp2p를 데몬으로 돌려 네트워크를 client 단에서 처리하지 않으며, pub-sub 통신 패턴을 위해 gossipsub 을 이용한다고 합니다.

이 내용은 추후 리서치를 통해 별도의 글로 게시할 예정입니다.

References

[1] https://vitalik.ca/files/Ithaca201807_Sharding.pdf
[2] https://github.com/ethereum/wiki/wiki/Sharding-roadmap
[3] https://medium.com/prysmatic-labs/ethereum-sharding-biweekly-development-update-9-prysmatic-labs-f2b1ad55e825
[4] https://github.com/ethereum/wiki/wiki/Sharding-FAQs#how-can-we-facilitate-cross-shard-communication
[5] https://ethresear.ch/t/cross-shard-contract-yanking/1450
[6] https://eprint.iacr.org/2015/718.pdf
[7] https://ethresear.ch/t/history-state-and-asynchronous-accumulators-in-the-stateless-model/287
[8] https://ethresear.ch/t/the-stateless-client-concept/172
[9] https://ethresear.ch/t/state-minimised-executions/748/1
[10] https://ethresear.ch/t/double-batched-merkle-log-accumulator/571
[11] https://github.com/ethereum/research/wiki/A-note-on-data-availability-and-erasure-coding
[12] https://github.com/libp2p/specs/tree/master/pubsub/gossipsub