Skip to content

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

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
      • zk-SNARK learning
  • 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
    • Free2Shard
  • 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
      • Snow Consensus Family
    • HotStuff: BFT Consensus in the Lens of Blockchain
      • Partial-sync, Linear, Responsive leader-based BFT based on 3-chain confirmation rule
  • Uniconsensus Sharding
    • Free2Shard, 2020
      • Also a good survey
  • 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

  • Arbitrum

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
Last update: 2023-09-15