Giải thích thuật toán đồng thuận AptosBFT bằng toán học cơ bản

🧠 Bối cảnh:

AptosBFT là một thuật toán đồng thuận được thiết kế để đảm bảo mọi nút trong mạng blockchain đồng thuận với nhau, ngay cả khi một số nút bị lỗi hoặc độc hại (Byzantine).

AptosBFT là một phiên bản cải tiến của HotStuff, với mục tiêu tăng hiệu suất và độ an toàn.

🎯 Mục tiêu toán học:

Giả sử có tổng cộng n nút trong hệ thống. Ta gọi:

• f là số nút có thể bị lỗi (Byzantine).

• Điều kiện đảm bảo đồng thuận là:

  $$n \geq 3f + 1$$

→ Điều này đảm bảo rằng ít nhất 2f + 1 nút trung thực để đạt được sự đồng thuận.

⚙️ Cơ chế hoạt động đơn giản hóa:

1. Các giai đoạn chính:

HotStuff – và do đó AptosBFT – hoạt động theo vòng lặp 3 bước chính, được gọi là 3-phase commit:

2. Điều kiện toán học để chấp nhận:

Ở mỗi giai đoạn, ít nhất 2f + 1 validator phải ký tên vào block → tạo thành một quorum certificate (QC).

→ Đảm bảo rằng ít nhất 1 nút trung thực luôn nằm trong nhóm ký block → tránh các fork mâu thuẫn.

💡 AptosBFT cải tiến gì so với HotStuff?

a. Pipelining (xử lý song song):

Cho phép nhiều block được xử lý cùng lúc ở các giai đoạn khác nhau → tăng throughput.

b. Decoupling Safety & Liveness:

AptosBFT phân chia logic an toàn và tiến triển rõ ràng → dễ kiểm soát & mở rộng.

🧮 Ví dụ trực quan:

Giả sử có n = 7 nút → chịu được tối đa f = 2 nút bị lỗi.

→ Mỗi giai đoạn phải thu thập ít nhất 2f + 1 = 5 chữ ký.

Quy trình:

1. Leader đề xuất block A.
2. Nếu 5 nút (trong đó có ít nhất 3 nút trung thực) phản hồi → tạo QC(A).
3. QC này cho phép tiến đến giai đoạn tiếp theo và cuối cùng chấp nhận block A.

→ Dù có 2 nút "Byzantine" cố tình gửi sai dữ liệu hoặc giữ im lặng, thuật toán vẫn đạt được đồng thuận đúng.

✅ Tóm tắt bằng công thức:

• Quorum =

$$2f + 1$$

• Tổng số nút cần có:

$$n \geq 3f + 1$$

• Đảm bảo:

  $$\text{Safety (không có 2 block mâu thuẫn cùng được chấp nhận)} \\ \text{Liveness (nếu leader đúng, block sẽ được chấp nhận)}$$

🧩 Sơ đồ trực quan - Quá trình 3 pha (3-phase commit)

[ Leader đề xuất Block A ] ↓ [ Prepare ] → Gửi block A đến các validator ↓ [ Pre-commit ] → Các validator kiểm tra block A → Nếu hợp lệ, ký tên và gửi lại ↓ [ Commit ] → Nếu nhận đủ 2f+1 chữ ký → Commit block A ↓ [ Decide ] → Block A được ghi nhận là hợp lệ và thêm vào blockchain

🔄 Pipeline version (song song hóa):

Time → B1 →───→───→───→ Commit B2 →───→───→ Commit B3 →───→ Commit ... ... (Prepare)(Pre)(Commit)

🧑‍💻 Mã giả (Pseudocode) - đơn giản hóa

# Giả định: có n nút, f nút có thể lỗi
# Quorum cần thiết: 2f + 1 class Block: def __init__(self, data, parent_qc): self.data = data self.parent_qc = parent_qc self.qc = None # Quorum Certificate sau mỗi giai đoạn class Node: def __init__(self, id, is_byzantine=False): self.id = id self.is_byzantine = is_byzantine self.blockchain = [] def receive_block(self, block): if self.is_byzantine: return None # hoặc trả về phản hồi sai if self.verify_block(block): return self.sign(block) return None def sign(self, block): return f"signature_from_{self.id}" def verify_block(self, block): # Kiểm tra block hợp lệ return True class Leader(Node): def propose_block(self, data, parent_qc, validators): block = Block(data, parent_qc) # Phase 1: Prepare print("Prepare: gửi block đến validators") # Phase 2: Pre-commit votes = [] for v in validators: sig = v.receive_block(block) if sig: votes.append(sig) # Kiểm tra quorum if len(votes) >= 2 * f + 1: block.qc = votes print("Commit: block đã có đủ chữ ký") self.commit(block) else: print("Không đủ chữ ký → Hủy block") def commit(self, block): self.blockchain.append(block) print("Block đã được commit vào blockchain")

🔄 Giải thích:

• Leader tạo block mới dựa trên parent QC.
• Gửi block cho tất cả validator (Prepare).
• Validator kiểm tra → ký nếu hợp lệ (Pre-commit).
• Nếu đủ chữ ký → tạo QC → commit block (Commit).