Harmony Research Roadmap

**Updates in 2019/07: Harmony aims to bring the best research results to production. We’re hiring research engineers. Here’re our timeline and topics of research:

• 2019Q3: consensus (Hotstuff, Ava’s leaderless), staking (Ouroboros, Algorand), BEP2/EVM bridge, WASM
• 2019Q4: confidential assets (Eian’s Bulletproof, zk-DAI), unison E2E networking (HIPv2, RaptorQ, Quic)
• 2020H1: zEther, fraud proofs, oracles, formal verification, deepsea
• 2020H2: succinct proof, formal security, quadratic fairness

Sharding Consensus and Contracts

Harmony’s latest technical architecture is now detailed in our new whitepaper and token economics in our staking design.

Below are our notes on Omniledger, Rapidchain and Chainspace for sharding consensus and contracts. 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. 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

• 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

• 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
• SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies [paper, book by princeton]

Chainspace

• Chainspace: A Sharded Smart Contracts Platform
  https://arxiv.org/abs/1708.03778
  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
  https://arxiv.org/abs/1802.07344
  https://github.com/asonnino/coconut-chainspace
• A Scale-out Blockchain for Value Transfer with Spontaneous Sharding https://arxiv.org/pdf/1801.02531.pdf (epfl labs)

Others

• 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]
  https://eprint.iacr.org/2018/104.pdf
• Snowflake to Avalanche: A Novel Metastable Consensus Protocol Family for Cryptocurrencies [gun sirer, perlin]
  https://ipfs.io/ipfs/QmUy4jh5mGNZvLkjies1RWM4YuvJh5o2FYopNPVYwrRVGV
• Zexe: Enabling Decentralized Private Computation [m green, zcash]
  https://eprint.iacr.org/2018/962.pdf
• 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
  https://eprint.iacr.org/2014/595.pdf
  [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]
  https://vrahli.github.io/articles/velisarios.pdf [github]
  Correct-by-construction Casper [talk, paper]
• Betting on Blockchain Consensus with Fantômette [PoS games]
  https://arxiv.org/abs/1805.06786
• Formal Barriers to Longest-Chain Proof-of-Stake Protocols
  https://arxiv.org/pdf/1809.06528.pdf [slides, talk]
  Problems in Cryptoeconomic Research by Buterin

Resources

• Top conferences: IEEE S&P, ACM CSS, USENIX Security
• Related conferences: NDSS, NSDI, SOSP
• Specialized conferences: FC, Scaling Bitcoin, Breaking Bitcoin, Bpase