Hotstuff - HackMD

--- slideOptions: transition: fade theme: white --- <style> .reveal { font-size: 20px; } .reveal pre { border: none; box-shadow: none; } .reveal .slides { text-align: left; } .reveal .slides section>* { margin-left: 0; margin-right: 0; } </style> # Hotstuff ## BFT Consensus in the Lens of Blockchain By Maofan Yin, Dahlia Malkhi, Michael K. Reiter, Guy Golan Gueta, and Ittai Abraham. --- ### Hotstuff > A **leader-based** **Byzantine fault-tolerant** replication protocol for the **partially synchronous model**. - _leader based_ - with leader selection out of scope of the paper. - _byzantine fault-tolerant_ - in regards to the _Byzantine Generals Problem_. - _partially synchronous model_ - Safety at all times even in asynchronous networks. - Liveness once network becomes synchronous. --- ### Constributions - **Linear communication and view change** with O(#replicas). Difference to PBFT. - **Optimistic Responsiveness**: Consensus at the pace of actual (vs. maximum) network delay. Difference to Tendermint and Casper. --- ### Related work #### Classics - Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. "The byzantine generals problem." ACM Trans. Program. Lang. Syst., 4(3):382–401, 1982. - Fischer, Michael J., Nancy A. Lynch, and Michael S. Paterson. "Impossibility of distributed consensus with one faulty process." Journal of the ACM (JACM) 32.2 (1985): 374-382. - Dwork, Cynthia, Nancy Lynch, and Larry Stockmeyer. "Consensus in the presence of partial synchrony." Journal of the ACM (JACM) 35.2 (1988): 288-323. - Castro, Miguel, and Barbara Liskov. "Practical Byzantine fault tolerance." OSDI. Vol. 99. No. 1999. 1999. --- ### Related work #### Blockchain - Nakamoto, Satoshi, and A. Bitcoin. "A peer-to-peer electronic cash system." Bitcoin.–URL: https://bitcoin.org/bitcoin.pdf (2008). - Buchman, Ethan. Tendermint: Byzantine fault tolerance in the age of blockchains. Diss. 2016. - Buterin, Vitalik, and Virgil Griffith. "Casper the friendly finality gadget." arXiv preprint arXiv:1710.09437 (2017). --- ### Basic Hotstuff ( ) New View messages (1) **Prepare Phase**: Ensure a leader does not send different proposals to different replicase (Equivocation). (2) **Pre-Commit Phase**: Solve _hidden lock problem_ and thus achieve linear view changes. (3) **Commit Phase**: Ensure that a commit proposal stays commited. ( ) Decide message --- ### Quorum Certificate (QC) Collection of - n - f signatures - for a leader proposal (prepare, pre-commit, commit) - for a specific view number. --- ### 1. Prepare Phase 4 nodes with one leader and 3 replicas out of which one might be byzantine (safety in async networks with n = 3k + 1). ```mermaid sequenceDiagram participant Leader participant Replica A participant Replica B participant Replica C Note over Leader,Replica C: Transition into new view. Replica A->>Leader: prepareQC Replica B->>Leader: prepareQC Replica C->>Leader: prepareQC Leader->>Replica C: Broadcast MSG(PREPARE, current Proposal, highest QC) Note over Replica A,Replica C: SafeNode predicate either:<br/>(a) proposal extends from current lockedQC<br/>(b) highestQC.viewNumber > lockedQC.viewNumber Replica A->>Leader: VOTEMSG(PREPARE, m.node) Replica B->>Leader: VOTEMSG(PREPARE, m.node) Replica C->>Leader: VOTEMSG(PREPARE, m.node) ``` --- ### SafeNode Predicate Either one has to be true: (a) proposal extends from current lockedQC ```mermaid graph LR Genesis --> ... --> lockedQC.node --> newQC.node ``` (b) newQC.viewNumber > lockedQC.viewNumber Given that newQC with view number 11 exists, conflicting proposal for lockedQC with view number 10 can not possibly been decided as otherwise honest replicas would not have signed newQC. ```mermaid graph LR Genesis --> ... -->|view 9| decidedValue -->|view10| lockedQC10.node --> someFailure decidedValue -->|view12| newQC11.node style someFailure fill:#FF0000 ``` --- ### 2. Pre-Commit Phase ```mermaid sequenceDiagram participant Leader participant Replica A participant Replica B participant Replica C Note over Leader: Wait for n - f PREPARE votes. Leader->>Replica C: Broadcast MSG(PRE-COMMIT, _, prepareQC) Note over Replica A,Replica C: prepareQC <- prepareQC Replica A->>Leader: VOTEMSG(PRE-COMMIT, m.node) Replica B->>Leader: VOTEMSG(PRE-COMMIT, m.node) Replica C->>Leader: VOTEMSG(PRE-COMMIT, m.node) ``` --- ### 3. Commit Phase ```mermaid sequenceDiagram participant Leader participant Replica A participant Replica B participant Replica C Note over Leader: Wait for n - f PRE-COMMIT votes. Leader->>Replica C: Broadcast MSG(COMMIT, _, precommitQC) Note over Replica A,Replica C: lockedQC <- precommitQC. Replica A->>Leader: VOTEMSG(COMMIT, m.node) Replica B->>Leader: VOTEMSG(COMMIT, m.node) Replica C->>Leader: VOTEMSG(COMMIT, m.node) ``` --- ### Hidden Lock Problem Violates liveness even in synchronous (bounded by Δ) networks. Solved through either: - 2nd (pre-commit) phase in Hotstuff (_Optimistic Responsiveness_). - By waiting Δ amount of times before leader changes in Tendermint and Casper. ```mermaid graph LR Genesis --> ... --> b' --> b b' --> b'' ``` What happens when we do **two**-phase (prepare & commit) Hotstuff with _Optimistic Responsiveness_? ```mermaid sequenceDiagram participant Leader 1 participant Leader 2 participant Replicas ... participant Replica Y participant Replica Z Note over Leader 2,Replicas ...: Network Partition Leader 1->>Replica Z: Broadcast MSG(COMMIT, _, precommitQC(b)) Note over Replica Y: lockedQC <- precommitQC(b). Replica Y->>Leader 1: VOTEMSG(COMMIT, b) Note over Leader 1,Replica Z: Transition into new view with Leader 2 Leader 2->>Replica Z: Broadcast MSG(PREPARE, b'', prepareQC(b') Replicas ...->>Leader 2: Some VOTEMSG(PREPARE, b'') Replica Z->>Leader 2: VOTEMSG(PREPARE, b'') Replica Y->>Leader 2: VOTEMSG(REJECT, b'') Note over Leader 2: No majority yet Note over Replicas ...: 2f transition into new view Replicas ...->>Leader 2: Single missing VOTEMSG(PREPARE, b'') from malicious replica Leader 2->>Replica Z: Broadcast MSG(COMMIT, _, prepareQC(b'') Note over Replica Z: lockedQC <- prepareQC(b'') Replica Z->>Leader 2: Honest replica VOTEMSG(COMMIT, b'') Note over Leader 1,Replica Z: Repeat ``` --- ### Chained Hotstuff - 3 phases are structurally the same. - Have each leader only do _PREPARE_ phase. Driving block of previous leader along the way. ![](https://i.imgur.com/X6YFGIA.png) --- ### Comparison | | Best Case Latency | Normal Case Communication | View Change Communication | View Change Responsiveness | | -------- | -------- | -------- | ---|---| | Bitcoin | 1 | O(n) | - | - | | PBFT | 2 | O(n²) | O(n²) | **Yes** | | Tendermint / Casper | 2 | **O(n)** | **O(n)** | No | | Hotstuff | 3 | **O(n)** | **O (n)** | **Yes** | --- ### Additional Sources - [ZK-TLV 0x09 - Ittai Abraham - The Bitcoin Breakthrough in the less of Distributed Computing (Part 1)](https://youtu.be/IUwsxssViqc) - [ZK-TLV 0x09 - Ittai Abraham - State Machine Replication from traditional to modern (Part 2)](https://youtu.be/-RcYagFNyLU) - [ZK-TLV 0x09 - Ittai Abraham - The HotStuff approach to BFT (Part 3)](https://youtu.be/ONobI3X70Rc) - [ZKPodcast: Consensus Algorithms & HotStuff with Ittai Abraham](https://www.zeroknowledge.fm/127) - [Murat Buffalo: Hotstuff Blog Post](https://muratbuffalo.blogspot.com/2019/12/hotstuff-bft-consensus-in-lens-of.html)

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.