blockchain-topics

blockchain-topics.md

Blockchain

• p2p
  • Kademlia
  • Turbine (Solana)
  • libp2p?
  • gossip?
• Consensus. References: decentralizedthoughts
  • Common knowledge and Two Generals Problem
  • Mis-spend vs double-spend
  • Security models
    • Network: Synchrony, Asynchrony, Partial synchrony
    • Simulation: Public-key infrastructure (PKI), proof-of-work, permissionlessness
    • Game theoretic: Honest, Byzantine, Strategic
  • Three-phase commit
  • Nakamoto consensus
    • Dynamic participation / The sleepy model of consensus
    • Availability-Accountability Dilemma
    • Availability-Finality Dilemma
    • With proof-of-work
    • With proof-of-stake
    • (LMD) GHOST
    • Ouroboros
    • Goldfish
  • Classical Consensus
    • CAP Theorem and FLP Impossibility
    • 3N bound
    • With proof-of-stake
    • Tendermint
    • BA* (Algorand)
    • DAG-based, e.g. Narwhal/Bullshark
    • Proof-of-history / Tower BFT
  • Hybrid
    • fork-choice + Casper FFG
    • fork-choice + GRANDPA
    • Babylon
  • Avalanche Consensus (Metastability)
  • Maximal Extractable Value
• Data availability
  • Erasure coding
  • Data availability oracles
    • Poisoning lazy oracle nodes
  • Data availability sampling
    • Lone sampler attack
    • Sample validity proof (link to polynomial commitments)
    • Sample fraud proof
      • 2D erasure codes
      • Coded Merkle Tree (CMT)
      • Authenticated Coded Dispersal (ACeD)
• Execution
  • Fraud proofs
  • Validity proofs
  • Proposer-builder separation (PBS)
    • Censorship resistance
• Cross-Communication
  • Multi-sig
  • Block headers

Cryptography

References: Boneh & Shoup

• PRNG
• Elliptic curves. References: Knapp "Elliptic Curves", "A first course in modular forms"
  • Computational properties
  • Security properties
• Pairings
• Commitment schemes
  • Integer commitments
  • Vector commitment schemes
    • Merkle Tree
    • Patricia Merkle Tree
    • Verkle Tree
    • Jellyfish Merkle Tree
  • Polynomial commitment schemes
    • Kate-Zaverucha-Goldberg (KZG)
    • Diophantine ARguments of Knowledge (DARK)
• Zero-knowledge (ZK). References: "Proofs, Arguments, and Zero-Knowledge", ingonyama-zk/ingopedia
  • Definitions
    • PCP, IPs, IOP
    • Simulators and extractors
    • PZK ⊂ SZK ⊂ CZK
    • Honest-verifier zero-knowledge (HVZK)
    • Non-interactivity
  • Arithmetization
    • CZK = IP = PSPACE
    • Groth16
    • PLONKish (TurboPLONK, UltraPLONK)
    • Arithmetic intermediate representation (AIR) / Reed-Solomon Proximity Testing (RPT)
  • Information-theoretic (IT) proof system
    • Sigma protocol
    • Linear PCP
    • Inner product argument (IPA)
    • Polynomial IOP
      • Fast Reed-Solomon Interactive Oracle Proofs of Proximity (FRI)
    • MPC-in-the-head
    • Algebraic holographic proof
  • Gadgets
    • Lookup arguments: plookup/plonkup, Caulk
    • BigNumbers
    • Foreign-field arithmetic
    • Cryptographic primitives
      • zk-friendly hashes
        • Reinforced Concrete
  • Cryptographic compiler
    • Fiat-Shamir transform
    • Preprocessing (per-circuit vs universal vs public-coin), trusted setups, and transparency
  • Recursive proofs
  • Protocols
    • Pinocchio
    • Groth16
    • Bulletproofs
    • PLONK
    • STARK
    • Plonky2
    • Halo2
    • Marlin
    • Fractal
    • BooLigero
    • Hyrax
    • deVirgo
  • Frontends
    • DSLs
    • zkVMs
      • zkEVM
      • RISC-V
      • OlaVM
      • Miden VM
    • Arithmetic and boolean circuits
    • R1CS, QAP
  • Hardware acceleration
    • FPGAs and ASICs
    • Modular arithmetic hardware
    • Multi-scalar multiplication (MSM)
    • Fast Fourier Transform (FFT)
    • Parallel/Distributed proving
• Distributed Key Generation (DKG)
• Homomorphic Encryption (HE)
  • Fully Homomorphic Encryption (FHE)
• Secure multi-party computation (MPC)
• Universal composability (UC)
• Lattice-based Cryptography

Applications

• Smart contract platforms
  • Contract theory
  • Ricardian contracts
  • Runtimes
    • Bitcoin Script
    • EVM
    • AVM (Avalanche)
    • cosmwasm
    • Sealevel (Solana)
    • Fuel VM
    • MoveVM
    • Endo (Agoric)
• Oracles
• Decentralized Finance (DeFi)
  • Atomicity
  • DEX
    • AMMs
      • CFMMs
  • Stablecoins
  • Perpetual swaps/futures
    • vAMM
  • Algorithmic money markets
  • Liquidity Mining and Protocol-Owned Liquidity
• Decentralized storage
• Social choice
  • Quadratic voting
  • Quadratic funding
  • Liquid democracy
  • Decentralized courts
• Radical Markets
  • Harberger taxes
• Web-of-trust
  • Self-Sovereign Identity (SSI), Soulbound Tokens (SBTs)

Software security

• Composability
  • Async composability
• Object capabilities
• Offer safety
• Testing
  • Formal Verification / Property-based testing
  • Fuzz testing
  • Static analysis