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/