Ethereum Sharding Research Compendium

This is an ongoing curated list, entries will be added or removed to reflect the articles that have the most relevance to the current state of research.

Stateless clients and witnesses

• The stateless client concept: https://ethresear.ch/t/the-stateless-client-concept/172
• Efficient Merkle proofs and generalized SSZ light client proofs: https://github.com/ethereum/eth2.0-specs/blob/dev/specs/light_client/merkle_proofs.md
• Efficiency gains from batching and multi-state roots: https://ethresear.ch/t/detailed-analysis-of-stateless-client-witness-size-and-gains-from-batching-and-multi-state-roots/862/9 and https://ethresear.ch/t/multi-tries-vs-partial-statelessness/391
• State-minimized executions: https://ethresear.ch/t/state-minimised-executions/748
• A cryptoeconomic accumulator for state-minimized contracts: https://ethresear.ch/t/a-cryptoeconomic-accumulator-for-state-minimised-contracts/385
• Using polynomial commitments to replace state roots: https://ethresear.ch/t/using-polynomial-commitments-to-replace-state-roots/7095

Cross-shard communication

• Merge blocks anc synchronous cross-shard state execution: https://ethresear.ch/t/merge-blocks-and-synchronous-cross-shard-state-execution/1240
• Cross-shard locking: https://ethresear.ch/t/cross-shard-locking-scheme-1/1269 and https://ethresear.ch/t/cross-shard-locking-resolving-deadlock/1275 and https://ethresear.ch/t/sharded-byzantine-atomic-commit/1285
• Cross-shard yanking: https://ethresear.ch/t/cross-shard-contract-yanking/1450
• A simple synchronous cross-shard transaction protocol: https://ethresear.ch/t/simple-synchronous-cross-shard-transaction-protocol/3097
• Cross-shard receipt and hibernation/waking anti-double-spending: https://ethresear.ch/t/cross-shard-receipt-and-hibernation-waking-anti-double-spending/4748
• Fast cross shard on top of slow cross shard via optimistic conditional state objects: https://ethresear.ch/t/a-layer-2-computing-model-using-optimistic-state-roots/4481 and https://ethresear.ch/t/fast-cross-shard-transfers-via-optimistic-receipt-roots/5337

Basic information and specs

• Sharding FAQ: https://github.com/ethereum/wiki/wiki/Sharding-FAQ
• Beacon chain Casper FFG mini-spec: https://ethresear.ch/t/beacon-chain-casper-ffg-rpj-mini-spec/2760
• Beacon chain full spec: https://github.com/ethereum/eth2.0-specs/tree/master/specs/core
• Sharding mindmap: https://www.mindomo.com/zh/mindmap/sharding-d7cf8b6dee714d01a77388cb5d9d2a01
• Eth2 roadmap: https://pbs.twimg.com/media/ETaj8ruWAAM1AdG?format=jpg
• Design rationale: https://notes.ethereum.org/9l707paQQEeI-GPzVK02lA

Proof of stake theory

• Proof of stake FAQ: https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ
• Casper FFG paper: https://arxiv.org/abs/1710.09437
• Attestation committee-based full PoS chains: https://ethresear.ch/t/attestation-committee-based-full-pos-chains/2259

Casper FFG/GHOST/beacon chain simulations

• Main folder: https://github.com/ethereum/research/tree/master/clock_disparity
  • Node: lmd_node.py
  • Test script: lmd_test.py

Casper CBC

• A CBC Casper tutorial: https://vitalik.ca/general/2018/12/05/cbc_casper.html
• Casper CBC, Simplified!: https://medium.com/@aditya.asgaonkar/casper-cbc-simplified-2370922f9aa6
• Beacon chain-friendly CBC Casper: https://ethresear.ch/t/beacon-chain-friendly-cbc-casper/4710/2
• Bitwise LMD GHOST: https://ethresear.ch/t/bitwise-lmd-ghost/4749/5
• LMD GHOST implementations: https://ethresear.ch/t/comparing-lmd-ghost-implementations/4945/3

External links

• Info on general-purpose ZKP schemes: https://zkp.science/

Miscellaneous

Light clients

• Beacon chain light client syncing: https://notes.ethereum.org/Irbhsn63R0W6o-r0K9mBOA
• Casper FFG light client syncing: https://github.com/ethereum/eth2.0-specs/blob/dev/specs/light_client/sync_protocol.md

Storage maintenace fees / Rent

• A simple and principled way to compute rent fees: https://ethresear.ch/t/a-simple-and-principled-way-to-compute-rent-fees/1455
• Improving UX via a sleep/wake mechanism: https://ethresear.ch/t/improving-the-ux-of-rent-with-a-sleeping-waking-mechanism/1480
• Actor/asset model: https://ethresear.ch/t/ethereum-2-0-data-model-actors-and-assets/4117
• Common classes of contracts and how they would handle ongoing storage maintenance fees: https://ethresear.ch/t/common-classes-of-contracts-and-how-they-would-handle-ongoing-storage-maintenance-fees-rent/4441

Proofs of custody

• Availability traps: https://ethresear.ch/t/proposer-withholding-and-collation-availability-traps/1294
• Hash-based proofs of custody: https://ethresear.ch/t/extending-skin-in-the-game-of-notarization-with-proofs-of-custody/1639 and https://ethresear.ch/t/bitwise-xor-custody-scheme/5139
• 1-bit aggregation-friendly custody bonds: https://ethresear.ch/t/1-bit-aggregation-friendly-custody-bonds/2236
• Current scheme: https://github.com/ethereum/eth2.0-specs/blob/dev/specs/core/1_custody-game.md

Data availability proofs

• Fraud proofs and data availability proofs via erasure coding: https://arxiv.org/abs/1809.09044
• The polynomial commitment section in https://vitalik.ca/general/2019/09/22/plonk.html (a polynomial commitment can be used to commit to N pieces of data and then opened at 2N or more positions; any N openings can reconstruct the same original data)
• FRI as erasure code fraud proof: https://ethresear.ch/t/fri-as-erasure-code-fraud-proof/6610
• Coded Merkle trees: https://arxiv.org/abs/1910.01247

Randomness

• 30% sharding attack: https://ethresear.ch/t/30-sharding-attack/1340
• An (impractical) idea for unmanipulable entropy: https://ethresear.ch/t/an-impractical-idea-for-unmanipulable-entropy/1355
• RNG exploitability analysis (RANDAO): https://ethresear.ch/t/rng-exploitability-analysis-assuming-pure-randao-based-main-chain/1825
• RANDAO exploitability analysis, round 2: https://ethresear.ch/t/randao-beacon-exploitability-analysis-round-2/1980
• Low-influence functions (Iddo Bentov): https://arxiv.org/pdf/1406.5694.pdf
• Swap-or-not shuffle: https://github.com/ethereum/eth2.0-specs/issues/563

Timestamps

• Incentive worries around timestamps: https://ethresear.ch/t/highlighting-a-problem-stability-of-the-equilibrium-of-minimum-timestamp-enforcement/2257
• Network-adjusted timestamps: https://ethresear.ch/t/network-adjusted-timestamps/4187

Data structures

• Optimizing sparse Merkle trees: https://ethresear.ch/t/optimizing-sparse-merkle-trees/3751
• Implementation of sparse Merkle trees: https://github.com/ethereum/research/tree/master/trie_research/bintrie2
• Double-batched Merkle log accumulator: https://ethresear.ch/t/double-batched-merkle-log-accumulator/571

Misc misc

• Cheats, weaknesses and attacks: http://notes.ethereum.org/MwNgJgpgHFbAtAQwKwQvALNA7PW2p4AzAYwCYAjARgrGxIE4jgg=
• Data forgetfulness: https://ethresear.ch/t/sharding-and-data-forgetfulness/61
• Security in the bribing model: https://ethresear.ch/t/shard-security-in-the-bribing-model/1366
• Better Merkle trees: https://ethresear.ch/t/data-availability-proof-friendly-state-tree-transitions/1453/6
• BLS and STARK aggregate signatures: https://ethresear.ch/t/pragmatic-signature-aggregation-with-bls/2105
• Rate-limiting entry/exits instead of withdrawals: https://ethresear.ch/t/rate-limiting-entry-exits-not-withdrawals/4942/