Sharding
Links
Papers
UTXO-based design proposals
Eleftherios Kokoris-Kogias, Philipp Jovanovic, Linus Gasser, Nicolas Gailly (EPFL), Ewa Syta (Trinity College), Bryan Ford (EPFL)
Shard consensus by ByzCoinX (PBFT on blockDAG), randomness by RandHound (MPC) and VRF-based sortition, UTXO-based (only cryptocurrency)
Identity blockchain manages the validator set
Atomix for X-shard communication
Adversary: >25%, mildly adaptive (on the order of epochs)
Mahdi Zamani (Visa Research), Mahnush Movahedi (Dfinity), Mariana Raykova (Yale University)
Gossip protocol built on Alon et al., 2004 (information dispersal algorithms w/ erasure code) Consensus on the hash of blocks
Inter-shard routing of transactions based on Kademlia
A representative committee generates an epoch randomness with verifiable secret sharing (VSS)
Bounded Cuckoo rule as shuffling algorith,
PoW is required to join a committee
Mustafa Al-Bassam, Alberto Sonnino, Shehar Bano, Dave Hrycyszyn and George Danezis
Shard consensus by BFT-SMART’s PBFT, UTXO-based (Objects with smart contracts, potentially with ZKP)
Sharded Byzantine Atomic Commit for X-shard communnicatiion
Checkpoints for Auditability (detecting malicious shard, a la fisherman)
Focusing on cross-chard communication, no discussion on validator election or rotation
Sourav Das, Vinith Krishnan, Ling Ren
Permissioned setting
There exists a single reference chain, which runs a consensus and many worker shards (no consensus)
Once a block is certified (i.e., signed by$ \ge f +1 replicas within the shard), the worker shard submits the cryptographic digest of the resulting state to the reference chain.
Present RIVET, a novel sharded system that has lower confirmation latency for cross-shard transactions compared to 2PC-based systems
Ranvir Rana, Sreeram Kannan, David Tse, Pramod Viswanath
Dynamic self-allocation algorithm that lets users allocate themselves to shards in response to adversarial action
Several attractive features unusual for
(a) the ability to handle the regime of large number of shards (relative to number of nodes)
(b) heterogeneous shard demands
(c) requiring only a small minority to follow the self-allocation
(d) asynchronous shard rotation
(e) operation in a purely identity-free proof-of-work setting.
Account-based design proposals
Jiaping Wang, ICT/CAS, Sinovation Ventures; Hao Wang, Ohio State University
Account/Balance model
Chu-ko-nu Mining to workaround the decrease of per-zone hashpower: Create multiple blocks in different zones by a single PoW
Hung Dang, Tien Tuan Anh Dinh, Dumitrel Loghin, Ee-Chien Chang, Qian Lin, Beng Chin Ooi (National University of Singapore)
Mildly adaptive adversary
Attested HyperLedger (AHL): PBFT without equivocation based on trusted log abstraction (attested append-only memory) enabled by TEE. The threshold is$ f + 1
PoET+ (improvement of PoET) for leader election
Shuffling shard committees by synchronous RNG (w/ sgx_read_rand)
SoK/Comparison
Gang Wang, Zhijie Jerry Shi (University of Connecticut), Mark Nixon (Emerson Automation Solutions), Song Han (University of Connecticut)
RSCoin, Elastico, Chainspace, Omniledger, Rapidchain
Georgia Avarikioti (ETH Zurich), Eleftherios Kokoris-Kogias (EPFL), Roger Wattenhofer (ETH Zurich)
Definition of security/scailability properties in sharding systems
General impossibility results (Section Ⅲ) and analysis of Omniledger, Rapidchain, Elastico, Monoxide (Ⅳ)
Others/Uncategorized
Songze Li, Mingchao Yu, A. Salman Avestimehr (USC), Sreeram Kannan (Univ. of Washington), and Pramod Viswanath (UIUC)
https://gyazo.com/abe07fef50ffa830b1df636d6dfbc8b5
Zuphit Fidelman (Technion) (Master Thesis)
Algorand Sharding
Runchao Han and Jiangshan Yu and Ren Zhang
Claim that none of existing proposals achieves self-balance and operability properties
Propose VRF-based approach
Public blockchain projects
Tutorials
ZILLIQA, OmniLedger, Chainspace, Saber
Sharding: Slides by Vitalik (2018.7)