Sự thật thú vị về hệ thống chịu lỗi Byzantine mà bạn chưa biết

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

Lịch sử bài toán các vị tướng Byzantine

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

Trước đó, vấn đề đạt được sự đồng thuận của Byzantine được Robert Shostak gọi với cái tên “Vấn đề nhất quán tương tác”. Dự án bắt đầu từ năm 1978, khi tiến hành nghiên cứu, họ chưa rõ là cần đến bao nhiêu máy tính để chứng minh giả sử có n máy tính bị lỗi cũng không thể cản trở nỗ lực đạt được sự đồng thuận của những máy tính vận hành chính xác. Shostak sau quá trình nghiên cứu đã ước lược được con số đó là 3n + 1. Đồng nghiệp của ông, Marshell Pease sau đó khái quát thuật toán bằng cách cho n > 0 bất kỳ rồi chứng minh con số 3n + 1 là vừa đủ.

Để làm cho vấn đề dễ hiểu hơn, một cộng sự khác là Leslie Lamport nghĩ ra một câu chuyện ngụ ngôn thú vị để truyền đạt ý tưởng. Câu chuyện đó ngày nay được biết đến với tên gọi bài toán các vị tướng Byzantine.

Nội dung bài toán các vị tướng Byzantine

Bài toán các vị tướng Byzantine là một bài toán khoa học máy tính giả định về đường truyền tin cậy, mô tả việc một nhóm các vị tướng quân đội đế quốc Đông La Mã gặp phải các vấn đề khi không đạt được sự thống nhất giữa các bên trong quá trình tiến hành vây hãm 1 thành phố. 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.

Cụ thể, có nhiều nhóm quân đội được lãnh đạo bởi các vị tướng. Mỗi tướng đóng quân ở các địa điểm khác nhau xung quanh thành phố mà họ có ý định xâm chiếm. Việc của họ là lựa chọn giữa tấn công và rút lui sao cho quyết định hai bên đồng thuận. Một số quy tắc các tướng phải tuân theo đó là:

+ Mỗi tướng quân bắt buộc phải lựa chọn một trong hai phương án: tấn công hoặc rút lui.

+ Không thể thay đổi quyết định sau khi đưa ra.

+ Tất cả tướng quân phải đồng thuận với quyết định được đưa ra đồng thời tiến hành chúng cùng một thời điểm.

+ Các vị tướng chỉ có thể trao đổi thông qua việc gửi thư cho nhau. Thông điệp được truyền đi bởi lính đưa tin. 

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 của mình. Tất cả đề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. Từ đó, các tình huống xấu có thể xảy ra cũng được liệt kê:

+ Người đưa tin bị bắt giữa đường, không thể chuyển thông điệp đến người nhận.

+ Người đưa tin bị quân địch bắt giữ, sau đó chúng làm giả thông tin theo hướng ngược lại.

+ Các tướng còn lại nhận được tin nhưng vẫn không thể tin tưởng 100%.

+ Trong số các tướng lĩnh có nội gián, sau khi nhận được tin thì thay đổi nội dung và cố ý tung ra các tin giả.

Hệ thống chịu lỗi Byzantine ra đời nhằm giải quyết tất cả những tình huống vừa kể trên.

Hệ thống chịu lỗi Byzantine

Khái niệm hệ thống chịu lỗi Byzantine

Như đã đề cập ở trên, hệ thống chịu lỗi Byzantine là một thuật toán được phát minh ra nhằm giải quyết các vấn đề trong bài toàn các vị tướng. Cụ thể hơn, Byzantine đả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 nhất.

Khả năng chịu lỗi của Byzantine chỉ quan tâm đến tính đúng đắn của chương trình phát sóng, tức là thuộc tính mà khi một thành phần phát một giá trị nhất quán duy nhất cho các thành phần khác, tất cả chúng đều nhận được chính xác cùng một giá trị, hoặc trong trường hợp đài phát không nhất quán, các thành phần khác đồng ý về một giá trị chung. Loại khả năng chịu lỗi này không bao hàm tính đúng đắn của bản thân giá trị.

Cũng giống như một bài toán sẽ có nhiều cách giải, có nhiều phương pháp để giải quyết vấn đề của các vị tướng, từ đó có nhiều cách để xây dựng một hệ thống chịu lỗi Byzantine.

Cơ chế hoạt động của hệ thống chịu lỗi Byzantine

Mục tiêu của hệ thống chịu lỗi Byzantine đó là bảo vệ toàn bộ mạng lưới khỏi các thành phần lỗi để đạt được sự đồng thuận nhất quán nhất. Có thể hình dung, Byzantine sẽ giúp hệ thống chống lại các lỗi phát sinh khi hai nhà giao dịch chưa đưa ra được thỏa thuận cuối cùng, giúp các nút hoạt động trong mạng không bị ảnh hưởng cũng như hệ thống không bị phá vỡ khi các nút khác bị mất kết nối.

Một số ứng dụng của hệ thống chịu lỗi Byzantine vào Blockchain

Chữ ký điện tử

Chữ ký điện tử là một trong những ứng dụng đơn giản của hệ thống chịu lỗi Byzantine vào Blockchain. Nó có thể dùng để xác thực xem ai là người gửi thông điệp, và thông điệp này chỉ có người sở hữu Private Key có quyền tạo. Thông điệp không thể bị sửa đổi trong quá trình truyền đi. Bạn hoàn toàn có thể thấy cơ chế này có nhiều điểm tương đồng với bài toán các vị tướng mà chúng ta đã đề cập ở trên đúng không nào?

Proof of Work (PoW)

Mặc dù khái niệm Proof of Work đã có từ trước khi tiền mã hóa ra đời. Tuy nhiên, Satoshi Nakamoto đã phát triển nó thành một thuật toán cho phép tạo ra Bitcoin như là một hệ thống chịu lỗi Byzantine. Cách thức hoạt động của phương pháp trên hiểu đơn giản là các Miner phải giải một bài toán để thêm một khối vào Blockchain. Mục đích của việc này đó là người dùng phải sử dụng tài nguyên của chính mình như điện, đầu tư phần cứng,…để đóng góp công sức. Nếu cố gắng gian lận những tài nguyên này coi như lãng phí, do đó cũng tự làm hại chính mình. Hệ thống sẽ an toàn nếu như có hơn 50% Miner không gian lận trong mạng.

Thuật toán PoW không đảm bảo 100% chịu lỗi Byzantine, nhưng nhờ vào quá trình đào tốn kém chi phí và các kỹ thuật mã hóa đằng sau, PoW đã chứng tỏ là một trong những thuật toán triển khai an toàn và đáng tin cậy nhất cho các mạng Blockchain. Theo nghĩa đó, thuật toán đồng thuận Proof of Work, được thiết kế bởi Satoshi Nakamoto, được coi là một trong những giải pháp thiên tài nhất cho vấn đề lỗi Byzantine.

Kết luận

Tìm hiểu rồi mới thấy hệ thống chịu lỗi Byzantine được ứng dụng vô cùng hiệu quả trong hệ sinh thái Blockchain. Ngoài ra, thuật toán này còn được sử dụng trong các ngành nghề tiên tiến như công nghiệp hàng không, không gian và điện hạt nhân. 

Trong bối cảnh tiền mã hóa, việc có một giao tiếp mạng hiệu quả cùng với một cơ chế đồng thuận tốt là rất quan trọng đối với bất kỳ hệ sinh thái Blockchain nào.  Chắc chắn hệ thống Byzantine sẽ còn nhiều tiềm năng phát triển ở tương lai nữa.

Đọc thêm: Tìm hiều về thuật toán đồng thuận Proof of Burn là gì?