Sharding Consensus and Contracts
Harmony is integrating Omniledger + Rapidchain + Chainspace for sharding consensus and contracts. Below are our notes on the latest research and roadmap. We’re looking for hires (see our 3x3 interview questions on culture and values) and collaborators (wine and ramen)!
And, our post on Harmony’s Networking: HIPv2 (id/loc, discovery, mobility, multi-homing, NAT traversal), RaptorQ (reliable, efficient multicast/unicast), and UDP Transport (with DCCP/QUIC-inspired congestion control).
Architecture and Insights
Harmony’s architecture centers around the problem of data availability. The key questions are:
- How fast can the network send data to update states?
- How small can the updates be encoded to minimize bandwidth?
- How final can transactions be guaranteed by a subset of the network?
Our insight is using fraud proofs and erasure coding to guarantee the efficiency and the security of transactions among 100k or more nodes.
Fraud proofs, with a long history in Bitcoin and Ethereum, are used to alert about invalid blocks to all nodes, including clients across shards or clients without the full states. Erasure encoding, also used in Information Dispersion Algorithm (IDA) and RaptorQ multicast protocol, makes optimal tradeoff between liveness and redundancy against attacks.
Moreover, we are studying the tradeoffs of Proof-of-Stake (see “Formal Barrier” below). In particular, using checkpoints as in Capser FFG versus instant finality with PoW + sharded PBFT requires some deeper comparison. Mining incentives and storage rents are the main cryptoeconomics issues for Harmony (or any next-generation base protocols) to design. Also, without a PoW base layer, are PoS and slashing secure against nothing-at-stake and long-range attacks (see “Problems in Cryptoeconomic Research”)? Are there effective measures against pooling to maximize decentralization?
There are a few other important open problems in scaling via sharding:
- Can the shard membership be fluid and fractional (see PolyShard)?
- Can randomness be generated efficiently for frequent resharding?
- Can the shard operate without leaders and use acyclic graphs (see Blockmania and GHOSTDAG)?
- Can scaling be possible without sharding but with sampling (see Avalanche)?
Many results there will help settle the hard problems of the cross-shard transactions, namely state sharding, UTXO vs account for bookkeeping, as well as client-driven vs chain-driven atomic locks. We will benchmark and optimize how semi-synchronous vs synchronous protocols work in practice (see OmniLedger, RapidChain and Vault).
Other advances help privacy and scaling computation, but seemingly not transaction performance for current applications. For examples, separating computation from verification (see Chainspace and Zexe) and specializing virtual machines for O(log n) verification (see Arbitrum) are groundbreaking results. However, few applications are compute-bound or verification-bound. Networks, in terms of making gigabytes of data available daily to many thousands of nodes, are the bottleneck.
There are also well-known techniques that awaits good engineering: WebAssembly backends, language designs with OCaml compilers (see Scilla and O(1) Labs), and HIPv2 + QUIC. We will use online petition as a realistic application (see Coconut) to stress test our prototype network.
Our long-term goals include using Coq to formally verify our consensus algorithm (see Velisarios and Toychain). We will also investigate many promising results from cryptography research, including stateless clients (see EDRAX) and proof systems for generalized domains (see rank-1 constraint satisfaction in Aurora).
- OmniLedger: A Secure, Scale-Out, Decentralized Ledger via Sharding (epfl)
https://eprint.iacr.org/2017/406.pdf short talk, long talk, code]
- Vault: Fast Bootstrapping for Cryptocurrencies (mit) https://dspace.mit.edu/bitstream/handle/1721.1/117821/1051460694-MIT.pdf
- Identity Aging: Efficient Blockchain Consensus (cambridge, eth) https://arxiv.org/pdf/1804.07391.pdf
- SABRE: Protecting Bitcoin against Routing Attacks (eth) https://arxiv.org/pdf/1808.06254.pdf
- RapidChain: Scaling Blockchain via Full Sharding (visa research, dfinity) https://eprint.iacr.org/2018/460.pdf [talk, erasure code]
- PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously (uw, uiuc)
https://arxiv.org/pdf/1809.10361.pdf [vs low-storage node]
- A Game-Theoretic Analysis of Shard-Based Permissionless Blockchains (u texas) https://arxiv.org/pdf/1809.07307.pdf
- Chainspace: A Sharded Smart Contracts Platform
Short talk, medium talk, long talk, company, code, example, e-petition
- Scilla: a Smart Contract Intermediate-Level LAnguage https://arxiv.org/pdf/1801.00687.pdf [verifier’s dilemma]
https://blog.zilliqa.com/provisioning-sharding-for-smart-contracts-a-design-for-zilliqa-cd8d012ee735 [network sharding, consensus protocol]
- Fraud Proofs: Maximising Light Client Security and Scaling Blockchains with Dishonest Majorities
https://arxiv.org/pdf/1809.09044.pdf (by al-bassam at ucl & vitalik buterin) [blog, talk, transcript, code, history]
(Execution traces, 25% with 2d coding, 15 samples for 1% error, interleaved challenges)
data availability: on plasma (paper), on bitcoin
- Coconut: Threshold Issuance Selective Disclosure Credentials with Applications to Distributed Ledgers
- A Scale-out Blockchain for Value Transfer with Spontaneous Sharding https://arxiv.org/pdf/1801.02531.pdf (epfl labs)
- Ethereum 2.0: Sharding and Proof-of-Stake
[talk, intro, faq, casper+sharding, spec, consensys, history, meetings, weekinethereum]
teams: prysmatic, parity, lighthouse, status nimbus, harmonyj, rocket pool
gitter: sharding, casper, research, evm 2.0
- Blockmania: from Block DAGs to Consensus
https://arxiv.org/abs/1809.01620 [source code, O(N²) msg, tendermint]
99% Fault Tolerant Consensus: achieving strong finality and 1%-honest-node consensus: threshold-dependent consensus (67% honest assumption for pbft, capser ffg, chain-based pos) and latency-dependent consensus (bounded network and clock; LinBFT)
- Arbitrum: Scalable, private smart contracts
https://offchainlabs.com/Arbitrum-USENIX.pdf [slides, talk, blog, company, discussion]
- PHANTOM, GHOSTDAG: Two Scalable BlockDAG protocols [zohar]
- Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies [gun sirer, perlin]
- Zexe: Enabling Decentralized Private Computation [m green, zcash]
- Aurora: Transparent Succinct Arguments for R1CS
https://eprint.iacr.org/2018/828.pdf [berkeley, mit, libiop, libsnark, scalable integrity]
Reed–Solomon codeword with Rank-1 Constraint Satisfaction (R1CS)
- Scalable Zero Knowledge via Cycles of Elliptic Curves
[O(1) labs code, blog, starkware talk, hearn’s blog, proof of proximity, mass tx validation]
- EDRAX: A Cryptocurrency with Stateless Transaction Validation
https://eprint.iacr.org/2018/968.pdf [by iohk, O(1) size]
- Mechanising Blockchain Consensus [zilliqa]
http://ilyasergey.net/papers/toychain-cpp18.pdf [github, slides]
- Velisarios: Byzantine Fault-Tolerant Protocols Powered by Coq [esop 2018]
Correct-by-construction Casper [talk, paper]
- Betting on Blockchain Consensus with Fantômette [PoS games]
- Formal Barriers to Longest-Chain Proof-of-Stake Protocols
https://arxiv.org/pdf/1809.06528.pdf [slides, talk]
Problems in Cryptoeconomic Research by Buterin