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)!

Check out our talk on Systems and Language Design or our latest newsletter on China tour and Animoca’s partnership on games.

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

RapidChain

Chainspace

Others