Thuật toán đồng thuận Byzantine Fault Tolerance (BFT) là gì?

Byzantine Fault Tolerance (hay Hệ thống chịu lỗi Byzantine – BFT) được cho là có thể giải quyết được vấn đề của bài toán các vị tướng quân Byzantine. Đây cũng là một thuận toán đồng thuận Blockchain khá nổi tiếng mà chúng ta sẽ được tìm hiểu trong bài viết này.

Bài toán 2 vị tướng quân (2 Generals Problem)

Bài toán 2 vị tướng quân (2 generals problem) nói rằng: trong một môi trường mà vấn đề trao đổi (communication) có thể xảy ra lỗi thì không thể đảm bảo được sự thống nhất giữa 2 bên.

Nội dung của bài toán 2 vị tướng quân có thể được miêu tả như sau:

• 2 đội quân được lãnh đạo bởi 2 vị tướng A1 và A2, cùng tấn công một thành phố B nằm ở giữa.
• Hai vị tướng A1 và A2 chỉ có thể trao đổi thông qua việc gửi thư cho nhau, nhưng xảy ra một vấn đề là người đưa thư cần phải đi qua thành phố B, dẫn đến việc hoàn toàn có khả năng người đưa thư bị bắt, thư không thể gửi đến đích, hay được gửi đến đích nhưng nội dung bị sửa đổi
• Hai vị tướng A1 và A2 cần thống nhất với nhau về việc tấn công thành phố B, và thời gian cả 2 cùng xuất quân. Bởi cả 2 chỉ có thể chiến thắng khi và chỉ khi họ tấn công vào cùng một thời điểm. Hay nói cách khác, họ cần đạt được sự đồng thuận với nhau về thời gian tấn công

Tưởng chừng như bài toán có thể giải quyết một cách đơn giản là trong 2 người bầu ra một chỉ huy, và đó là người đưa ra mốc thời gian tấn công gửi cho người kia thế là xong. Nhưng vấn đề nằm ở chỗ làm thế nào (chỉ bằng cách gửi message và xử lý message nhận được) để cả 2 có thể biết một cách chắc chắn rằng: “Cả 2 chúng ta đã đồng thuận và sẽ cùng tấn công vào thời điểm XX:YY ngày ZZ”

Chúng ta hãy dành chút thời gian để nói rõ về vấn đề ở đây nhé!

• Vị tướng quân A1 có thể sẽ bắt đầu bằng cách gửi một message đến vị tướng A2, với nội dung “Hãy cùng tấn công vào 12:00 ngày 19/8”. Tuy nhiên, sau khi gửi thư, vị tướng A1 hoàn toàn không thể biết được liệu rằng người đưa thư có thể chuyển message an toàn đến cho vị tướng A2 hay không.
• Để chắc chắn, vị tướng A2 sẽ cần gửi một lời xác nhận đến cho vị tướng A1 với nội dung: “Tôi đã nhận được tin nhắn của anh, và sẽ cùng tấn công vào 12:00 ngày 19/8”. Tuy nhiên, một lần nữa, người đưa thư hoàn toàn có thể bị bắt, và vị tướng A2 sẽ lại rơi vào tình trạng lo lắng xem rằng không biết ông A1 có nhận được lời confirm của mình hay không.
• Để chắc chắn hơn, vị tướng A1 có thể sẽ tiếp tục gửi một message với nội dung “Tôi đã nhận được lời xác nhận của anh về kế hoạch tấn công vào 12:00 ngày 19/8 rồi”. Tuy nhiên, người đưa thư này lại có thể bị bắt.

Cứ như vậy, ta sẽ thấy một cách rõ ràng rằng, dù có trải qua bao nhiêu vòng xác nhận đi chăng nữa, cũng sẽ không có cách nào để cho từng vị tướng chắc chắn rằng người kia đã đồng ý với kế hoạch tấn công của mình. Cả hai đều luôn bị đặt trong trạng thái băn khoăn, nghi ngờ xem không biết cái tin nhắn cuối cùng mình gửi có đến được đích hay không.

Bài toán 2 vị tướng quân là bài toán về vấn đề truyền thông máy tính đầu tiên được chứng mình là không có lời giải.

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

Bài toán các vị tướng Byzantine được đưa ra bởi 3 nhà khoa học máy tính Leslie Lamport, Robert Shostak và Marshall Pease trong một báo cáo khoa học mang tên “The Byzantine Generals Problem” vào năm 1982. Đây là bài toán tổng quát hoá của bài toán 2 vị tướng quân.

Bài toán các vị tướng Byzantine miêu tả về một nhóm các vị tướng trong đội quân Byzantine (quân đội đế quốc Đông La Mã), tiến hành vây hãm 1 thành phố. Các vị tướng cần trao đổi để đạt được đến 1 thoả thuận về kế hoạch tấn công thành phố đó. Trong trường hợp đơn giản nhất, họ thoả thuận về việc nên tấn công hay rút lui. Một số có thể muốn tấn công, nhưng một số thì lại muốn rút lui, và vấn đề là nếu chỉ có một bộ phận tấn công riêng lẻ, thì họ sẽ gặp thất bại, và đó là kế hoạch tồi tệ hơn việc cùng tấn công hoặc cùng rút lui.

Mọi thứ sẽ trở nên phức tạp khi mà một vị tướng sẽ có thể gửi tin nhắn đi cho các vị tướng khác. Chẳng hạn như trong trường hợp có 5 vị tướng, 2 ông đã phát tín hiệu muốn tấn công, 2 ông đã phát tín hiệu muốn rút lui, còn ông thứ 5 lại chơi trò 2 mang, nhắn với 2 ông muốn tấn công rằng mình muốn tấn công, còn nhắn với 2 ông muốn rút lui rằng mình sẽ rút lui. Khi đó phe tấn công nghĩ rằng tấn công là lựa chọn đa số và họ tấn công (và sẽ thất bại), phe rút lui thì nghĩ rằng rút lui là lựa chọn đa số và họ rút lui. Họ đã không đạt được sự đồng thuận (về việc có cùng ý kiến).

Kịch bản của các tướng Byzantine là một sự tương tự cho vấn đề mà các hệ thống máy tính phân tán phải đối mặt: Làm thế nào để chúng ta đạt được sự đồng thuận khi phải đối mặt với các tác nhân không đáng tin cậy và gặp trục trặc đe dọa gây mất ổn định hệ sinh thái?

Byzantine Fault Tolerance là gì?

Byzantine Fault Tolerance (BFT) là hệ thống có thể giải quyết được vấn đề của bài toán các vị tướng quân Byzantine.

Byzantine Fault Tolerance đảm bảo cho một mạng máy tính phân tán hoạt động như mong muốn và đạt được sự đồng thuận chính xác. Điều này có nghĩa là hệ thống BFT có thể tiếp tục hoạt động ngay cả khi một số nút bị lỗi hoặc thực hiện hành động gây hại.

Các giao thức dựa trên BFT tìm cách giảm thiểu ảnh hưởng mà các nút độc hại có thể gây ra trên mạng lưới nhằm đảm bảo cho các nút trung thực vẫn duy trì được hoạt động đúng và đạt được sự đồng thuận. Có rất nhiều các giao thức đồng thuận khác được thiết kế dựa trên nguyên tắc này.

Byzantine Generals Problem & Blockchain & Consensus

Blockchain là một cuốn sổ cái được chia sẻ cho mọi thành viên trong một mạng lưới phi tập trung (decentralized). Ở đó, không hề có một bên thứ 3 được tin tưởng để quản lý sự vận hành của nó, mà tự các thành viên của hệ thống phải tương tác với nhau để đi đến một sự đồng thuận (consensus). Hay nói cách khác, một hệ thống Blockchain cần có cách để chịu lỗi Byzantine.

Khi Bitcoin, blockchain đầu tiên ra đời, cha đẻ của nó, Satoshi Nakamoto cũng đã giới thiệu một một phương pháp để giải quyết bài toán các vị tướng quân, được gọi dưới cái tên Proof-of-Work (PoW).

Satoshi Nakamoto cũng từng trực tiếp giải thích về cách Bitcoin dùng PoW để giải quyết bài toán các vị tướng Byzantine trong một email gửi đi ngày 14/11/2008, các bạn có thể xem qua tại đây

Cũng cần phải nhắc đến rằng, bài toán Byzantine trên mạng lưới Blockchain đã được đơn giản hơn, nhờ vào việc sử dụng chữ ký điện tử (Digital Signature). Với những đặc tính mà nó mang lại như:

• Authentication (tính xác thực): chữ ký điện tử có thể dùng để xác thực xem ai là người đã gửi message. Chỉ có người quyền sở hữu với private key mới có thể tạo ra chữ ký điện tử cho một message.
• Integrity (tính toàn vẹn): message không thể bị sửa đổi trong quá trình truyền đi. Nếu điều đó xảy ra, chữ ký điện tử sẽ trở nên không hợp lệ nữa.
• Non-repudiation (không thể chối cãi): một message cùng chữ ký điện tử đã được gửi đi, thì người đã ký nó không thể phủ nhận việc mình đã tạo và ký message

Bên cạnh PoW, ngày nay các blockchain còn có sử dụng nhiều thuật toán đồng thuận khác. Ví dụ như NEO dùng Delegated Byzantine Fault Tolerance, hay nền tảng Hyperledge Fabric của Linux Foundation dùng Practical Byzantine Fault Tolerance (PBFT), gần giống với giải pháp consensus mà Tendermint cung cấp.

CẢNH BÁO: Đầu tư vào các sản phẩm tài chính tiềm ẩn rất nhiều rủi ro mà có thể không phù hợp với một số nhà đầu tư. Do đó hãy cân nhắc kỹ lưỡng và làm chủ bản thân trước khi đưa ra bất kỳ quyết định nào cấu thành từ những nội dung tham khảo tại GiaiMaCoin.Com.