Bài toán các vị tướng Byzantine là gì? Ứng dụng?

Làm thế nào một mạng lưới phân tán gồm các nút máy tính đạt được sự đồng thuận khi xử lý một quyết định, nếu một số các nút trong đó có khả năng là sẽ thất bại hoặc không đáng tin?

Đây là câu hỏi cơ bản của vấn đề được đặt tên là bài toán các vị tướng Byzantine, từ đó làm khai sinh ra khái niệm về hệ thống chịu lỗi Byzantine.

Byzantine là tên của một vị tướng quân

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.

Chuyện kể rằng cách đây hàng nghìn năm về trước, đế quốc Byzantine (được biết đến là một đế quốc La Mã Phương Đông hùng mạnh) quyết định chiếm đánh bao vây một thành phố. Thành phố này được bao quanh bởi quân đội và mỗi tiểu đoàn đều do một vị tướng đứng đầu. Để chiến thắng, các đạo quân đều phải hợp lực tấn công (hoặc rút lui) cùng một thời điểm. Nếu không, họ sẽ không đủ sức mạnh và dẫn đến thất bại.

Thời bấy giờ, chưa có bộ đàm hay điện thoại, mọi thông tin đều phải liên lạc thông qua người đưa tin bằng ngựa. Người này sẽ đưa tin từ người chỉ huy đến các đạo quân. Lúc này, một bài toán được đặt ra như sau:

Người đưa tin bị bắt và không thể tiếp tục truyền tin.
Quân địch tóm được người đưa tin, sau đó thay đổi tin nhắn gửi đến các vị tướng tiếp theo.
Một trong các tướng phản bội. Họ sẽ ngăn những người khác đạt được đồng thuận hay làm tổn hại quân ta bằng việc thay đổi nội dung tin nhắn.

Câu hỏi được đặt ra là làm cách nào để các vị tướng có thể phối hợp với nhau để giành được chiến thắng?

Blockchain và vấn đề phi tập trung

Bài toán vị tướng Byzantine chỉ xảy ra trong một hệ thống phi tập trung do không có nguồn thông tin “đáng tin cậy”. Ngược lại, ở hệ thống tập trung, một cơ quan sẽ đứng ra đảm bảo rằng thông tin được phân phối cho các cấp dưới là “chính xác”, điều này giúp ngăn ngừa gian lận và phổ biến thông tin sai lệch trên toàn mạng. Dẫu vậy, không thể phủ nhận rằng một hệ thống tập trung cũng có thể bị “tham nhũng” bởi cơ quan quản lý của nó.

Để khắc phục những vấn đề được đưa ra trong Bài toán vị tướng Byzantine, từ trước đến nay, con người đã tìm đến một số cách như sử dụng dịch vụ của bên thứ ba uy tín. Cụ thể trong bài toán này, một vài giải pháp có thể xem xét là yêu cầu các vị tướng phải ký hiệp ước với nhau nếu phát hiện một ai đó cố tình giả mạo thông tin sẽ bị trừng phạt trước toà án, hoặc thuê một bên đưa tin uy tín, có nhiều kinh nghiệm.

Vậy có cách nào để một cá nhân (hay tổ chức) có thể “tin tưởng tuyệt đối” mà không cần phải phụ thuộc vào bên thứ ba hay không?

Môi quan hệ của bài toán Byzantine và Blockchain

Trên mạng lưới Blockchain, thay vì các vị tướng, chúng ta sẽ có các máy tính hoặc các node. Tất cả node này đều phải đạt được “sự đồng thuận” về trạng thái hiện tại của hệ thống, tức là những người tham gia phải đều đồng ý và thực hiện các hành động một cách “đồng bộ” để tránh thất bại.

Như chúng ta đã biết, Blockchain là một cuốn sổ cái điện tử có thể chia sẻ tới mọi thành viên trong một mạng lưới phi tập trung (Decentralized). Ở đó, không hề có sự xuất hiện của một bên thứ 3 nào khác 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).

Đây cũng là lý do ra đời của Hệ thống chịu lỗi Byzantine. Hệ thống được thiết kế nhằm chống lại các loại lỗi có thể phát sinh từ vấn đề chung của Byzantine. Một số trường hợp có thể kể đến là Double Spending (gian lận lập chi) hoặc các node độc hại gửi thông tin sai lệch tới toàn mạng.

Ngoài ra, hệ thống này còn đảm bảo rằng một chuỗi khối có thể tiếp tục hoạt động ngay cả khi một số node bị hại hoặc không giao tiếp được. Một số thuật toán đồng thuận mà Blockchain sử dụng để tăng tính bảo mật mạng như bằng chứng cổ phần, bằng chứng công việc hay bằng chứng cổ phần được uỷ quyền.

Cha đẻ của Bitcoin, Nakamoto Satoshi, cũng từng trực tiếp giải thích về cách Bitcoin dùng “bằng chứng công việc” – 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:

Satoshi's Previously Unpublished Emails Present New Puzzle - CoinDesk

Ngoài ra, bài toán Byzantine trên mạng lưới Blockchain cũng được “đơn giản hoá” hơn rất nhiều 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