Skip to content

Note for ECE 598PV, Spring 2021

https://courses.grainger.illinois.edu/ece598pv/sp2021/

Notations and Theorems

Notations

  • \(T\) hardness of POW (\(hash < T\))
  • \(\lambda\) mining rate
  • \(\beta\) fraction of adversial
  • \(\beta \lambda\) adversial power
  • \(\alpha = 1 - \beta\) fraction of honest nodes
  • \(\frac{\alpha}{1+\alpha\lambda} \lambda\) honest power when forking for delay

Bitcoin Theorems

  • Common Prefix
    • hold with exponential prop if \(\beta\lambda < \frac{\alpha \lambda}{1+\alpha\lambda\Delta}\)
  • Chain Growth
    • \(CG \ge \frac{\alpha \lambda}{1+\alpha\lambda\Delta}\)
  • Chain Quality
    • \(CQ \ge \frac{CG-\beta\lambda}{CG}\)

Remarks

  • 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
  • For nakamoto-like
    • Chain Growth + Chain Quility = Liveness
    • Common Prefix = Security

Module 1. --- Bitcoin

4.P2P network

  • Model as P2P model
  • expander graph =>gossip is O(logn)
  • can define GST here instead of 6.

5. Bitcoin system

  • UTXO model (set of unspent output)
  • TXs (special coinbase txs that mint coins)
  • Mempool

6. Bitcoin safety

  • Mining as a Poisson(\(\lambda\))
  • Common Prefix Property
  • Private Attack is the Worst for Longest Chain Protocol
  • Analysis
    • 0 Delay (Ideal)
    • Bounded Delay
      • Forking => Honest Power Down
      • Attack success if \(\beta\lambda > \frac{\alpha \lambda}{1+\alpha\lambda\Delta}\)

7. Bitcoin liveness

  • Chain Growth
    • \(CG \ge \frac{\alpha \lambda}{1+\alpha\lambda\Delta}\)
  • Chain Quality
    • \(CQ \ge \frac{CG-\beta\lambda}{CG}\)
  • Selfish Mining Attack
    • Ming and publish to replace honest block
  • Maximizing Chain Quality by Fruitchain
    • crpytography sortition of tx blocks and proposer blocks
    • proposer blocks and proposed txs not included in
    • CG is geranteed by hardness of \(T_{prop}\)
    • CQ is optimized by allowing past txs to be included

Module 2. --- Scaling Bitcoin

8. Scaling throughput

  • Bitcoin’s throughput is security limited
    • throughput \(= \alpha\lambda B\)
    • increase \(B\) => increase \(\Delta\)
      • \(\Delta \approx \frac{B}{C}+D\)
    • increase \(\lambda, \Delta\) => security down by theorem
  • GHOST fork choice rule
    • counter private attack
      • private cannot be heaviest
    • but suffers from balance attack
      • analyze the second moment to get \(E(|N_l − N_r|)\) by CS ineq
      • Sudo Yaun says there are "uncles" to prevent balance attack
  • Bitcoin-NG
    • proposer create tx blocks after elected
    • security problem: adaptive corruption => DOS attack
  • Prism 1.0
    • ~= Fruitchain
      • no sortition
      • tx blocks POW hardness is low to get high throughput
      • proposer blocks POW is high to get high security

9. Scaling Latency

  • Bitcoin’s latency is security limited
    • for \(\epsilon\) security (resp. to private attack), need \(k\) deep confirmation where
      • \(\epsilon = e^{-ck},~c=-\ln(4\alpha\beta)\)
      • the latency is thus given by \(\tau=\frac{k}{\alpha\lambda}=O(\frac{1}{\lambda}\log \frac{1}{\epsilon})\)
    • upperbound on error probability, https://arxiv.org/pdf/2011.14051.pdf
  • Prism
    • voter trees (similar to boosting in ML, use LoLN)
    • \(O(\frac{1}{\lambda})\) with the confirmation rule

10. Scales Horizontally (Sharding)

  • Key Observation:
    • Data Availability + Total Ordering is enough
    • Validity can be left to honest nodes and state commitment (if sharded)
  • Multiconsensus
    • Protocol
      • Node to Shard Allocation(N2S) engine(SOTA: Randhound (TODO) )
      • Consensus per Shard
    • Examples
      • Elastico, rapidchain and Omniledger
      • Ethereum 2.0 and Polkadot
    • Cons
      • Shard number cannot be large to guarantee adversial count
      • Subjective to Adaptive Adversary
  • Uniconsensus
    • Protocol
      • Consensus is mentained by all nodes, data are stored by shards
      • DSA (Dynamic Self Allocation) algorithm
    • Examples
      • Free2Shard(Prism + Tx Blocks Sharded) (TODO)
      • Aspen, Nightshade (TODO)
      • Lazyledger (Client Validation + Data Availability Consensus) (TODO)
      • Zilliqa partition validation
      • Polyshard use coded storage + computation (TODO)
  • Bootstraping uniconsensus chain
    • problem, cannot trust shard majority
    • state commitment + proof of fraud
      • State roots to reduce size
        • Merle Patricia Tries (see Ethereum Yellow paper)
      • Truebit, Arbitrum style binary searching to give fraud proof
  • X-shard TX
    • atomic swap (timeout/abort)
    • example: Atomix, Omniledger

11. Scales externally

  • Payment Channel
    • New primitives
      • mltisig
      • hash lock
      • time lock
    • Do off chain atomic swap (update secret to share new tx)
  • Side Blockchain
    • Face similar (if not identical) problem to uniconsensus sharding
    • Data availability problem
      • the problem is fatal compared to light clients
        • proposer need to decide whether to include the pointer
      • Fraud and data availability proofs: Maximising light client security and scaling blockchains with dishonest majorities (TODO)
    • Data availability oracle
      • SOTA: Authenticated Coded Dispersal (ACeD) (TODO)
      • make use of CIT(Coded Interleaving Tree) similar to CMT but push instead of pull

12. Scaling Energe with PoS

  • Naive Attempts
    • \(H(hash_{prev}, merkle\_root, pk_n) < T · stake\)
      • root as nonce
    • \(H(hash_{prev}, pk_n) < T · stake\)
      • no liveness
    • \(H(hash_{prev}, ts, pk_n) < T · stake\)
      • predictibility
    • \(VRF(hash_{prev},ts,sk_n) < T · stake\)
  • Resigning the Previous Blocks (???)
    • (But Blocks are hash linked)
    • Solution: KES
    • (But can still save past pk and give to adaptive adversary)
  • Nothing at Stake
    • https://eprint.iacr.org/2017/656
    • threshold = \(\frac{1}{1+e} \approx 26.89%\)
    • Boosting the threshold
      • Ouroboros PoS
        • \(VRF(hash_{genesis},ts,sk_n) < T · stake\)
        • Vulurable to bribing
      • c-Correlation PoS
        • change hash every c blocks
        • \(VRF(RandSource(parent),ts,sk_n) < T · stake\)
        • smooth transition
  • Dynamic Stake
    • Transfer fund between accounts in owned blocks (pk as nonce)
    • solution => s-truncated longest chain
      • calculate the s blocks after the fork, quicker => win
        • To start dynamic stake attack, it has to control all blocks mined with only small advantage
  • My Remarks
    • How is using ts safe? (time interval large enough to match \(\Delta\)?)
    • Does s-truncated longest chain satisfy the safety and liveness guarantee?
  • Dynamic Availability Using VDF
    • problem: time machine! mining past blocks is almost costless
    • SOTA: PoSAT
      • VDF assuming a bounded CPU speed
      • VRF given time bound L i.e. \(f^{t=L}(x)\) is a R.V.!
      • \(VDF(RandSource(parent),ts,sk_n) < T · stake\)
  • Long range attack (Solved?)
    • bride past stake
    • fixed by ?
      • checkpoint
  • My Remarks
    • The defense of long range attack seems open

13. Transaction order fairness

  • Possible Defs for Fair Orderings of Transactions
  • Attempt
    • k deep block can have k view of tx ordering
    • aggregate them get a ordering
  • Possible Application: Zero-Block Confirmation (In ref.)
  • Reference
    • Order-Fair Consensus in the Permissionless Setting
  • My Remarks
    • seems an open direction (less technical arguments)
    • consider "all miners" are malicious in tx ordering would be a more practical assumption
      • use game theory to solve!

Module 3: Beyond Bitcoin

14. Blockchain protocols with finality: Streamlet and HotStuf

Nakamoto-like favors liveness, while PBFT-like favors safety.
Note: for this lecture, the slide is much more readible. - Nakamoto-like - Probabilistic Safety Guarantee, Synchronous Network Assumption - Can we offer finality, and even if the network is not synchronous? - General Setting for PBFT protocols - permissioned, \(n\) fixed - proposer can be chosen randomly (RandHood) or round robin - need \(f < \frac{1}{3}\) (consider signature hiding) - When 2f+1 votes exist on a block they can form a Quorum Certificate (QC).

Streamlet

A naive textbook protocol - https://dahliamalkhi.github.io/posts/2020/12/what-they-didnt-teach-you-in-streamlet/ - Assumptions - partial sync (exists GST) - echo - rounds operate in lock-step with \(2\Delta\) duration - each node broadcast the message it receives to others - Protocol (in round, exists given partial sync) - proposal extends the longest notarized chain - all nodes vote (sign) for the first proposal they see from the round’s proposer if it extends their longest notarized chain(s). - When a block gains votes from more than \(\frac{2n}{3}\) distinct nodes, it becomes notarized. - Core Properties - Safety - The Hide and Reveal Attack - reveal blocks only to \(\frac{2}{3}-f < x < \frac{2}{3}\) nodes - 3-chain rule is safe - Given 3 consecutive blocks, the middle one can be confirmed - Proof correctness by contraction of two possible cases - Liveness - Once there are 5 consecutive rounds of honest proposers, a new honest block will be confirmed (the first two can be not notarized) - Echo is required or attacker can hide infinitely long and trick a node into dead lock - Notice that it progresses only during "periods of synchrony" - => await the slowest, not responsive - Efficiency - Message complexity: \(N^2(B+NV)\) - Delay: \(\approx 15 \Delta\) - from 5 consecutive rounds (\(2\Delta\)) of honest majority - better than BTC

Hotstuff

  • Contribution: First PBFT protocol that achieves
    • Linearity (of message complexity)
    • Responsiveness (advance at the speed of network delay)
    • Chain Quality
  • Assumption
  • Protocol
    • HighQC: QC with highest epoch number (for node i)
    • A block is linked to its parent via the parent's QC
    • Algo
      • A leader extends its HighQC
        • on receiving a new QC
      • A node votes for the proposal if it extends its highQC
        • the vote is only sent to the next leader
      • Final if 3-chain rule satisfied
  • Core Properties
    • Safety (same as Streamlet)
    • Liveness (responsive for event (new QC) driven))
  • Efficiency
    • Communication Complexity
      • Nodes only send message to next proposer \(O(N(B+V))\) (with cosig)
    • Delay: Responsive
  • Details and Notes
    • This is the protocol behind Diem (facebook => meta => silvergate)
      • https://developers.diem.com/docs/technical-papers/state-machine-replication-paper/
    • comparison to tendermint and casper (2-chain rule + partial sync => waiting)
      • https://dahliamalkhi.github.io/posts/2019/08/hotstuff-three-chain-rules/
    • PaceMaker for proposer election
    • Chained Hotstuff for parallelization
  • My Remarks
    • The leader is predictible thus adaptive corruptable!!
    • All leader-based protocols violate liveness unless a leader cannot proof it is leader and get corrupted
      • e.g. POW (sealed block), Snow Consensus

Remarks

  • Protocol Forensics
    • Can detect \(\frac{n}{3}\) double signing behavior if a fork ever happens
  • Conclusions
    • A permissionless architecture and is robust to adaptive adversaries
    • Liveness is weakened to favor security (finality)
    • Honest participation is needed now, unlike the longest chain protocol that allowed dynamic participation and even a single honest miner ensured liveness.
    • How to have both finality and dynamic availability (liveness even under varying participation levels of honest nodes) is the topic of L16.
Last update: 2023-09-15