Byzantium, thủ đô của Đế quốc La Mã Đông, đã từng là một trong những thành phố mạnh mẽ và giàu có nhất thế giới. Tuy nhiên, do lãnh thổ rộng lớn, Byzantium thường xuyên phải đối mặt với các cuộc xâm lược từ bên ngoài và các cuộc nổi dậy nội bộ. Để bảo vệ biên giới, Byzantium đã gửi nhiều đạo quân, mỗi đạo quân do các tướng lĩnh khác nhau chỉ huy. Đạt được sự thống nhất giữa những tướng lĩnh này trở thành một thách thức đáng kể.
Bài toán vị tướng Byzantine có mối quan hệ mật thiết với blockchain. Mạng lưới blockchain là một mạng lưới phân tán trong đó các nút, giống như các vị tướng Byzantine, phải đạt được sự nhất quán về giao dịch và dữ liệu trong một môi trường mạng không tin cậy.

Bài toán hai vị tướng

Vấn đề Hai Tướng là một trường hợp đặc biệt của vấn đề vị tướng Byzantine. Vấn đề và bằng chứng về tính không thể giải quyết của nó được đề xuất lần đầu tiên bởi E.A. Akkoyunlu, K.Ekanadham và R.V. Huber trong bài báo năm 1975 của họ “Một số Ràng buộc và Cân đối Trong Thiết kế Của Mạng Giao Tiếp.” Vào năm 1978, Jim Gray chính thức đặt tên vấn đề này là “Vấn đề Hai Tướng” trong cuốn sách của ông “Ghi chú về Hệ thống Vận hành Cơ sở Dữ liệu.” Ban đầu, nó được sử dụng để phân tích các vấn đề về đạt được sự nhất quán thông qua việc giao tiếp qua một liên kết giao tiếp không đáng tin cậy. Hiện nay, nó thường được sử dụng để minh họa các vấn đề về tính nhất quán và sự đồng thuận trong các hệ thống phân tán.

Định nghĩa vấn đề:
Hai đội quân của quốc gia A, mỗi đội được chỉ huy bởi một tướng, đều chuẩn bị tấn công một đội quân của quốc gia B. Đội quân của quốc gia B bị bao vây trong một thung lũng, với hai đội quân của A đặt trên hai ngọn đồi hai bên của thung lũng. Tuy nhiên, con đường duy nhất giữa hai đội quân của A đi qua thung lũng. Đội quân của B mạnh hơn so với mỗi đội của A một cách riêng lẻ, nhưng nếu cả hai đội quân của A tấn công cùng nhau, họ có thể đánh bại đội quân của B.
Vấn đề: Liệu có thể tạo ra một thuật toán cho phép hai tướng của hai đội quân A đồng ý thực hiện một cuộc tấn công đồng thời không? Thuật toán có thể bao gồm việc gửi và nhận tin nhắn.
Giải pháp: Bài toán Hai vị tướng cổ điển là không thể giải quyết được. Không có giao thức nào có thể đảm bảo hai đội quân của A sẽ phối hợp thành công cuộc tấn công của họ. Tuy nhiên, trong các hệ thống thực tế, các vấn đề có thể được giải quyết tương đối đáng tin cậy, chẳng hạn như với cơ chế "bắt tay ba chiều" trong giao thức TCP.

Bài toán vị tướng Byzantine

Bài toán vị tướng Byzantine được đề xuất lần đầu tiên bởi Leslie Lamport, người đoạt giải Turing năm 2013, trong bài báo năm 1982 của ông “The Byzantine Generals Problem.” Vấn đề mô tả cách đạt được tính nhất quán trong các hệ thống phân tán trong bối cảnh hành vi độc hại, như làm giả thông điệp.
Một số quân đội của Đế quốc Byzantine bao vây một thành phố địch, mỗi đội được chỉ huy bởi một tướng. Các đội quân Byzantine chỉ có thể giao tiếp thông qua người đưa tin. Sau khi quan sát lực lượng địch, các tướng Byzantine phải đạt đến kết luận giống nhau: chỉ khi hơn một nửa số quân đội Byzantine tấn công cùng nhau thì họ mới có thể chiếm được thành phố và đạt được chiến thắng.

Giải pháp: Nếu số tướng (node) trong một hệ thống Byzantine là Z và số tướng không đáng tin cậy (phản bội) là X, thì chỉ khi Z ≥ 3X + 1 thì một giao thức Byzantine Fault Tolerance (BFT) mới đảm bảo tính nhất quán của hệ thống.
Trong các hệ thống thực tế, các lỗi gây ra việc các nút không phản hồi được phân loại là "Lỗi Crash," trong khi các nút gian lận hoặc làm giả thông điệp được phân loại là "Lỗi Byzantine."

Phân loại thuật toán đồng thuận

Các hệ thống blockchain là một loại hệ thống phân tán, đặc biệt là chuỗi công khai như Bitcoin và Ethereum, gồm nhiều nút mạng cực kỳ phân tán và không tin tưởng lẫn nhau. Cơ chế đồng thuận blockchain đảm bảo rằng hệ thống blockchain luôn đạt được sự nhất quán dữ liệu mà không có các nhánh.
Dựa vào loại sự chịu lỗi, các thuật toán đồng thuận có thể được phân loại thành các thuật toán Không chịu lỗi Byzantine (CFT) và các thuật toán Chịu lỗi Byzantine (BFT).

Thuật toán không chịu lỗi Byzantine Fault Tolerance

Trong các hệ thống phân tán, các thuật toán khả năng chịu lỗi không phải là lỗi vị tướng Byzantine đảm bảo tính tin cậy của toàn bộ hệ thống phân tán khi các nút gặp sự cố hoặc ngưng hoạt động không kế hoạch (lỗi không phải là lỗi vị tướng Byzantine). Tuy nhiên, khi các nút độc hại làm giả hoặc can thiệp vào dữ liệu, các thuật toán khả năng chịu lỗi không phải là lỗi vị tướng Byzantine không thể đảm bảo tính tin cậy của hệ thống. Các thuật toán này chủ yếu được sử dụng trong các hệ thống phân tán doanh nghiệp đóng hoặc kiểm soát. Các thuật toán khả năng chịu lỗi không phải là lỗi vị tướng Byzantine đáng chú ý bao gồm thuật toán Paxos và thuật toán Raft.

Thuật toán chịu lỗi Byzantine

Các thuật toán Độ tin cậy lỗi Byzantine cho phép một hệ thống phân tán đảm bảo tính tin cậy ngay cả khi các nút gặp bất kỳ loại lỗi nào, miễn là số nút lỗi không vượt quá một tỷ lệ nhất định. Đơn giản là, miễn là số nút lỗi (do lỗi không phải Byzantine hoặc Byzantine) ít hơn một tỷ lệ nhất định của tổng số nút, các thuật toán Độ tin cậy lỗi Byzantine có thể đảm bảo tính tin cậy của hệ thống. Do sự hiện diện của nhiều nút mạng không tin cậy trong các hệ thống blockchain như Bitcoin và Ethereum, các thuật toán Độ tin cậy lỗi Byzantine chủ yếu được sử dụng trong các cơ chế đồng thuận blockchain. Các thuật toán Độ tin cậy lỗi Byzantine đại diện nhất bao gồm PBFT (Practical Byzantine Fault Tolerance), PoW (Proof of Work) và PoS (Proof of Stake).