Blockchain Resources
- Block is for batch processing txs.
- Chain is for determining the unique total ordering.
- Blocktree (forking) is inevitable in the presence of asynchrony.
- Consensus is to
- (non-triviality) decide when fork
- (security) ensure the choice will not change in the future
- (liveness) ensure new tx comes in
- Sharding is to
- avoid full replication of storage and computation
- allow XCMP
- To achieve sharding in a uniconsensus scheme
- data availability
- data integrity
- shard liveness
TOC
TMP
Links
Ideas
- Arbitrage based fixed interest protocol (game theory)
- Tree shard (leveled consensus)
- Adding concurrency to smart contracts (prism: consensus is not the bottlenet)
- Blockchain+
- Network Topology
- potentially network coding problem
- Privacy
- Proof or Disproof
- Can we seal POS blocks?
- Can we encode computing program to computing result (one-way)?
- Can we provide tx order fairness with game theory?
Todo
- Blockchain Classes
- Chains
- [x] Arbitrum
- [ ] AVAX-C
- [ ] Casper(eth2.0)
- [ ] GRANDPA(polkadot)
- [ ] Nightshade(near)
- [ ] OHIE
- Primitives
- BFTs
- Data Availability Oracle
- State Commitment (Fraud Proof)
- Free2Shard
- Code Computings
- Cryptography
- hash, multisig, VRF, VDF, ZK-SNARK
- Sharding
- Polyshard
- [ ] Free2Shard
- [ ] Separating Agreement from Execution for Byzantine Fault Tolerant Services
- [ ] Lazyledger
Courses
- https://cs.nyu.edu/~mishra/
- https://ethresear.ch/
- https://courses.grainger.illinois.edu/ece598pv/sp2021/
- https://web.stanford.edu/class/archive/ee/ee374/ee374.1206/
- https://cs251.stanford.edu/syllabus.html
Entries and Must-Reads
- Survey Entry
- SOTA Consensus (Lasted Updated 2022/2/24)
- Prism: Deconstructing the Blockchain to Approach Physical Limits, 2019
- structured DAG based POW blockchain, physical limit
- Scalable and Probabilistic Leaderless BFT Consensus through Metastability
- HotStuff: BFT Consensus in the Lens of Blockchain
- Partial-sync, Linear, Responsive leader-based BFT based on 3-chain confirmation rule
- Uniconsensus Sharding
- Data Availability
- Fraud and Data Availability Proof
- Coded Merkled Tree
- Coded Interleaving Tree
- Layer 2
- Arbitrum (State Commitment)
- Longest Chain Analysis
- Bitcoin Backbone
- Nakamoto Always Win
- Rethinking Large-Scale Consensus
Network Model
- Randomized Gossip Algorithms, https://web.stanford.edu/~boyd/papers/pdf/gossip.pdf
- How Efficient Can Gossip Be? (On the Cost of Resilient Information Exchange)
- Consensus in the Presence of Partial Synchrony, 1988
- this paper defines partial sync with GST or unkown \(\Delta\)
- https://decentralizedthoughts.github.io/2019-06-01-2019-5-31-models/
- On the minimal synchronism needed for distributed consensus, 1987
- Impossibility of distributed consensus with one faulty process, 1985 (i.e. the FLP impossibility)
Primitives, Utils, Analysis
Nakamoto Analysis
- The Bitcoin Backbone Protocol: Analysis and Applications, 2015
- Liveness and Consistency of Bitcoin and Prism lockchains: The Non-lockstep Synchronous Case
- A Rational Protocol Treatment of 51% Attacks, 2021
- Everything is a Race and Nakamoto Always Wins, 2020
- Rethinking Large-Scale Consensus, 2020
Privacy
Cryptography Primitives
- Keeping Authorities “Honest or Bust” with Decentralized Witness Cosigning
- Byzcoin use this to reduce \(O(n^2)\) PBFT communication complexity to \(O(n)\) by multisigning
- Harmony claim to use BSL multisig to increase security
- JMT (Jellyfish Merkle Tree)
- CMT (Coded Merkle Tree)
- CIT (Coded Interleaving Tree)
Tx Order Fairness
- Order-Fair Consensus in the Permissionless Setting
Sharding
General
ECC
- Lagrange Coded Computing: Optimal Design for Resiliency, Security, and Privacy
- PolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously
- Scalable Network-Coded PBFT Consensus Algorithm
- Low Latency Cross-Shard Transactions in Coded Blockchain
- Dynamic Distributed Storage for Blockchains
- On the information theory of clustering, registration, and blockchains
XCMP
Near
Fraud and Data Availability Proof
State Commitment
Consensus
BFT
Dags
- HGraph
- Conflux
- IOTA paper (Tangle)
- Fantom (Lachesis Consensus)
- Prism: Deconstructing the Blockchain to Approach Physical Limits
Snow
- Avalanche (Snowflake Consensus)
- [ ] Blizzard: a Distributed Consensus Protocol for Mobile Devices (2 Layer Avalanche?)
- [ ] Asynchronous Epidemic Algorithms for Consistency in Large-scale Systems (A PhD thesis)
Solana
- https://medium.com/solana-labs/tower-bft-solanas-high-performance-implementation-of-pbft-464725911e79
- https://docs.solana.com/cluster/overview
- https://solana.com/solana-whitepaper.pdf
Sybil Resistance
POS
- Securing Proof-of-Stake Nakamoto Consensus Under Bandwidth Constraint
- Babylon: Reusing Bitcoin Mining to Enhance Proof-of-Stake Security
Layer 2
Side Chain
Rollup
Side Channel
Permissioned Blockchain
- Hotstuff
- IBM Hyperledger Frabic
Surveys
- A Survey of State-of-the-Art on Blockchains: Theories, Modelings, and Tools
- Scaling Blockchains: A Comprehensive Survey
- From blockchain consensus back to Byzantine consensus
- SoK: Sharding on Blockchain
- SoK: Diving into DAG-based Blockchain Systems
- SoK: Understanding BFT Consensus in the Age of Blockchains (Best)
- SoK: Communication Across Distributed Ledgers
- Deconstructing Blockchains: A Comprehensive Survey on Consensus, Membership and Structure
- A Survey of Distributed Consensus Protocols for Blockchain Networks
- Solutions to Scalability of Blockchain: A Survey
- Layer 2 Blockchain Scaling: a Survey
- Review of Techniques for Privacy-Preserving Blockchain Systems