TÓM TẮT
Fork Choice Rule là thuật toán quyết định chain hợp lệ khi network có nhiều fork cạnh tranh. Bitcoin dùng Nakamoto Longest Chain (chain dài nhất = chain đúng). Ethereum PoS dùng LMD-GHOST (subtree được nhiều validator vote nhất) kết hợp Casper FFG để đạt finality. Mỗi thiết kế có đánh đổi khác nhau giữa safety, liveness và độ phức tạp.
IFork Choice Rule là gì?
Fork Choice Rule (quy tắc chọn fork) là thuật toán mỗi node trong mạng blockchain dùng để xác định chain "chính thống" (canonical chain) khi tồn tại nhiều fork cạnh tranh nhau. Đây là một phần không thể thiếu của bất kỳ cơ chế đồng thuận nào.
Fork xảy ra tự nhiên trong mạng phân tán — do network latency, hai miner tìm ra block hợp lệ cùng lúc, hoặc validator không nhận được block đúng thời hạn. Fork choice rule đảm bảo tất cả node — dù nhận được block theo thứ tự khác nhau — cuối cùng đều đồng thuận về cùng một chain.
IITại sao fork xảy ra?
Accidental Fork (Fork tự nhiên)
Do network latency trong hệ thống phân tán: block của miner A broadcast đến node X trước block của miner B, nhưng node Y nhận ngược lại. Cả hai block đều hợp lệ — fork tạm thời xảy ra và được giải quyết bởi fork choice rule trong vài block tiếp theo.
Intentional Fork (Fork có chủ đích)
Soft fork, hard fork do protocol upgrade — một phần network chạy phiên bản mới, phần còn lại chạy cũ. Ví dụ: ETH/ETC split 2016, Bitcoin/Bitcoin Cash 2017. Fork choice rule trong trường hợp này phụ thuộc vào majority support theo quy tắc của từng phiên bản.
Malicious Fork (Fork tấn công)
51% attack: attacker với đủ hash power/stake cố tình tạo fork để double-spend. Fork choice rule phải được thiết kế để chống lại tình huống này — chain của honest majority phải thắng.
IIINakamoto Longest Chain (Bitcoin)
Rule đơn giản nhất và lâu đời nhất: chain hợp lệ dài nhất (tính theo accumulated proof of work) là canonical chain. Satoshi Nakamoto giới thiệu trong Bitcoin whitepaper 2008.
Cách hoạt động
- Mỗi block trong PoW có accumulated difficulty (tổng proof of work đã bỏ ra)
- Node luôn build tiếp lên chain có accumulated difficulty cao nhất
- Khi nhận block mới làm chain khác dài hơn, node switch sang chain đó (reorg)
- Với hash rate honest majority, chain của honest miners luôn dài hơn dài hạn
Ưu và nhược điểm
- Ưu: Cực kỳ đơn giản, dễ implement, battle-tested 15+ năm
- Nhược: Probabilistic finality — transaction chỉ "safe" sau nhiều confirmation. Uncle block (orphan block) waste proof of work. Dễ bị selfish mining attack.
IVGHOST và LMD-GHOST (Ethereum PoS)
GHOST — Vấn đề Longest Chain trong block time nhanh
GHOST (Greedy Heaviest Observed SubTree) được đề xuất 2013 để giải quyết vấn đề của Longest Chain khi block time ngắn: với block time 15s (Ethereum PoW), nhiều uncle block xuất hiện — longest chain bỏ qua work của uncle, gây lãng phí và centralization pressure.
GHOST thay vì chọn chain "dài nhất", chọn subtree "nặng nhất" — tính cả uncle block vào trọng số. Chain có nhiều block + uncle nhất được coi là canonical.
LMD-GHOST — Phiên bản cho Ethereum PoS
LMD-GHOST (Latest Message Driven GHOST) là fork choice rule của Ethereum sau The Merge. Thay vì hash rate (PoW), trọng số là validator stake weight thể hiện qua attestations (votes):
- Mỗi validator gửi attestation (vote) cho block họ cho là head of chain
- LMD-GHOST chỉ tính latest message (vote gần nhất) của mỗi validator — tránh validator cũ ảnh hưởng
- Tại mỗi fork point, chọn subtree được nhiều validator weight ủng hộ nhất
- Kết quả: head of chain là block được majority stake ủng hộ
VCasper FFG + LMD-GHOST (Ethereum)
Ethereum PoS không chỉ dùng LMD-GHOST — nó kết hợp với Casper FFG (Friendly Finality Gadget) để đạt finality thực sự, không chỉ probabilistic.
Phân công vai trò
- LMD-GHOST: Xác định head of chain (block mới nhất) — quyết định fork nào là canonical trong thời gian thực
- Casper FFG: Finalize checkpoint (epoch boundary) — sau khi 2/3 validator vote, checkpoint được finalize và không thể reorg
Epoch và Checkpoint
Mỗi epoch = 32 slot = ~6.4 phút. Cuối mỗi epoch, checkpoint được đề xuất. Nếu 2/3 validator (theo stake weight) attest cho checkpoint, nó được finalized. Sau finality, block không thể bị reorg — bất kỳ validator nào cố tình reorg sẽ bị slash (mất stake).
Kết hợp này giải quyết vấn đề của cả hai: LMD-GHOST cung cấp liveness (chain tiếp tục build dù có validator offline), Casper FFG cung cấp safety (finalized blocks không thể bị đảo ngược). Xem thêm tại Finality là gì.
VIGRANDPA (Polkadot)
Polkadot dùng kiến trúc tách biệt block production và finality: BABE (block production, tương tự LMD-GHOST) + GRANDPA (finality gadget).
GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix Agreement) có thể finalize nhiều block cùng lúc thay vì từng block một — hiệu quả hơn Casper FFG khi có nhiều validator. Nếu 2/3 validator đồng thuận, GRANDPA có thể finalize cả chuỗi block thay vì chỉ một checkpoint.
VIISo sánh các Fork Choice Rule
| Rule | Dùng bởi | Cơ chế | Finality | Độ phức tạp |
|---|---|---|---|---|
| Longest Chain | Bitcoin, Litecoin | Accumulated PoW | Probabilistic | Rất thấp |
| GHOST | Ethereum PoW (uncle) | Heaviest subtree | Probabilistic | Thấp |
| LMD-GHOST + Casper | Ethereum PoS | Validator vote weight | Deterministic (~12 phút) | Cao |
| BABE + GRANDPA | Polkadot | Block production + vote | Deterministic (nhanh hơn) | Cao |
| Tendermint BFT | Cosmos, Celestia | Round-based voting | Instant (per block) | Trung bình |
VIIISafety vs Liveness — Đánh đổi cốt lõi
Theo CAP theorem và FLP impossibility, không có fork choice rule nào có thể đồng thời tối ưu cả safety (không có conflicting finalized blocks) và liveness (chain tiếp tục tiến kể cả khi có node offline).
Safety-first (BFT systems)
Tendermint: không finalize block cho đến khi 2/3 validator đồng thuận — nếu quá nhiều validator offline, chain dừng lại. Đổi lại: instant finality, không reorg. Phù hợp cho ứng dụng cần absolute finality (payments, enterprise).
Liveness-first (Nakamoto Consensus)
Bitcoin: chain luôn tiến dù chỉ còn 1 miner — nhưng finality chỉ probabilistic, có thể reorg. Phù hợp cho mạng lưới global permissionless cần hoạt động liên tục.
Ethereum — Hybrid approach
LMD-GHOST đảm bảo liveness (chain tiếp tục build kể cả khi dưới 2/3 validator online), Casper FFG đảm bảo safety cho finalized checkpoints. Khi network partition xảy ra và dưới 1/3 validator online, chain vẫn build nhưng không finalize — safety được ưu tiên khi không đủ điều kiện.
Xem thêm về đồng thuận tại Proof of Stake là gì và Validator là gì.
❓Câu Hỏi Thường Gặp
Fork Choice Rule là thuật toán mỗi node dùng để xác định canonical chain khi network tồn tại nhiều fork. Bitcoin dùng Longest Chain (accumulated PoW), Ethereum PoS dùng LMD-GHOST (validator vote weight). Fork choice rule đảm bảo tất cả node đồng thuận về cùng một chain dù nhận block theo thứ tự khác nhau.
LMD-GHOST (Latest Message Driven Greedy Heaviest Observed SubTree) là fork choice rule của Ethereum PoS. Thay vì chain dài nhất, LMD-GHOST chọn subtree được nhiều validator stake weight ủng hộ nhất, chỉ tính latest vote của mỗi validator. Kết hợp với Casper FFG để đạt finality sau ~12 phút.
Longest Chain phù hợp với PoW vì proof of work tạo ra weight tự nhiên theo hash rate. LMD-GHOST cần biết latest validator vote — khái niệm không tồn tại trong PoW (không có validator set cố định). Mỗi fork choice rule được thiết kế phù hợp với cơ chế đồng thuận tương ứng.
Reorg (reorganization) xảy ra khi node phát hiện một fork khác dài/nặng hơn chain hiện tại và switch sang fork đó — các block trên chain cũ bị "orphaned". Fork choice rule quyết định khi nào reorg xảy ra. Với Ethereum PoS, sau finality (~2 epoch) reorg là không thể — attacker sẽ bị slash.
📚Tài liệu tham khảo
- Nakamoto, S. (2008). Bitcoin: A Peer-to-Peer Electronic Cash System.
- Sompolinsky, Y. & Zohar, A. (2015). Secure High-Rate Transaction Processing in Bitcoin (GHOST). FC 2015.
- Ethereum Foundation. Fork choice — Gasper consensus. ethereum.org/en/developers/docs/consensus-mechanisms/pos/gasper/
- Buterin, V. & Griffith, V. (2017). Casper the Friendly Finality Gadget. arxiv.org/abs/1710.09437