---
title: "Note: Principles of Blockchains at UIUC"
tags:
- research
- blockchain
- NTU
- note
author: Maxwill
lastUpdated: 2022/3/1
---

# Note: Principles of Blockchains at UIUC
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' = \beta \lambda$ adversial power
- $\alpha = 1 - \beta$ fraction of honest nodes
- $\alpha' = \frac{\alpha}{1+\alpha\lambda} \lambda$ honest power considering forks by network delay

### Bitcoin Theorems
- **Common Prefix**
- holds with overwhelming proprability if $\beta' < \alpha'$
(Nakamoto's block: worst case is private attack)
- **Chain Growth**
- $CG \ge \alpha'$
- **Chain Quality**
- $CQ \ge \frac{\alpha'-\beta'}{\alpha'}$

### Remarks
- To build a distributed ledger
- Chain, for determining the unique total ordering
- Block, for batch processing txs
- Blocktree (forking) is inevitable in the presence of asynchrony and adversary
- Consensus is required
- (non-triviality) decide when fork
- (security) ensure the choice will not change in the future
- (liveness) ensure new tx come in
- For nakamoto-like
- Chain Growth + Chain Quility = Liveness
- Common Prefix = Security
- Sharding is to avoid repetition of storage and computation
- To achieve (uni-consensus) sharding
- data availability
- data integrity
- shard liveness
- allow XCMPs

---

# Module 1. --- Bitcoin

----

## 1-3. Introduction, Cryptography Primitives, Longest Chain

----

## 4.P2P network
- P2P network instead of client server model
- unstructured d-regular overlay (abstract) network
- random d-regular graph => expander graph w.h.p. =>gossip is O(logn)
- more gossip layer details
- 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
- [Nakamoto Block Always Win](https://arxiv.org/pdf/2005.10484.pdf)
- 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 (2 for 1 mining)
- 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
- uncle blocks are rewarded to avoid this issue
- **Bitcoin-NG**
- proposer create tx blocks after elected
- security problem: adaptive corruption => DOS attack
- **Prism 1.0**
- ~= Fruitchain
- 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 rate
- 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)
- 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 (TODO)

----

## 12. Scaling Energy with PoS
[PoSAT: Proof-of-Work Availability and Unpredictability, without the Work](https://arxiv.org/abs/2010.08154)
- 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](https://eprint.iacr.org/2018/378.pdf)
- http://tselab.stanford.edu/downloads/PoS_LC_SBC2020.pdf
- 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:
- mining past blocks is almost (computationally) costless
- increase current stake can increase past stake (by recreating the chain but censor transactions?)
- solution: use VDF to create an arrow of time
- SOTA: [PoSAT](https://arxiv.org/pdf/2010.08154.pdf)
- 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**
- briding past stake is cheap
- fixed by checkpointing (ugly solution)
- 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 HotStuff
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](https://eprint.iacr.org/2020/088.pdf)
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](https://dahliamalkhi.github.io/posts/2019/08/hotstuff-three-chain-rules/)
- 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](https://arxiv.org/pdf/1710.09437.pdf) (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.

----

## 15. Permissionless Blockchains based on BFT Protocols: Algorand

### High Level
- random committee (N) from permissionless nodes (n)
- committee run pBFT
- instant finality since no forking (secure)

### Committee Selection Disribution

### Secret Committee Election

### Ephemeral key

### Algorand BFT

----

## 16. BFT + Longest chain? Finality Gadget and CAP theorem

### Hybrid Consensus
- fail!

### Finality Gadget
- two finality rule, client decides
- longest checkpointed chain

### FLP impossibility
- cannot achieve both finality and security under asynchrony

----

## 17. Bootstrapping blockchains
(game theory, economic model)
- Bootstrapping a POW blockchain
- mining incentives
- POA checkpointers for 51% attack
- hard forks and soft forks
- proof of burn
- Bootstrapping a POS blockchain
- Layer2

----

## 18. Data Privacy via Zero Knowledge Cryptography
https://courses.grainger.illinois.edu/ece598pv/sp2021/lectureslides2021/ECE_598_PV_course_notes18_v2.pdf

----

## 19. Privacy for Smart Contracts
- privacy bridge between zk UTXO world and programmable world
- zkay, zexe, kachina, zether