2020/03/06
Blockchain

Byzantine Generals’ Problem là gì? Vấn đề nan giải của khoa học máy tính khi xử lý bitcoin

Bạn có biết đến vấn đề nan giải trong khoa học máy tính “Byzantine Generals Problem” không?

Byzantine Generals Problem là vấn đề về mặt xây dựng sự đồng thuận trong hệ thống dữ liệu.

Để lý giải được các vấn đề trong việc xây dựng sự đồng thuận thì việc hiểu rõ về Blockchain là điều vô cùng quan trọng.

Tổng quan về Byzantine Generals Problem

Byzantine Generals Problem là “Vấn đề liên quan đến mức độ tin cậy trên các hệ thống phân tán” được phát minh bởi nhà toán học Leslie Lamport.

Byzantine Generals Problem có thể được giải thích như sau, “thông qua Mạng P2P giao tiếp với nhau, trong trường hợp các thông tin đó và các Node riêng lẻ gặp sự cố hoặc cố ý truyền thông tin sai lệch thì câu hỏi cần đặt ra đó là sự đồng thuận chính xác có thể hình thành được hay không”

Hệ thống của P2PNetwork mà có chức năng giúp cho hệ thống vận hành bình thường và giải quyết vấn đề này nắm giữ Byzantine Fault Tolerance (BFT)

Nguồn gốc của từ 「Byzantine Generals Problem」bắt nguồn từ vấn đề của các vị tướng trong Đế quốc Byzantine.

Bạn hãy tưởng tượng tình trạng mà trong đó mỗi vị tướng đang dẫn dắt một đội quân và bao vây quân đội địch.

Các vị tướng đang xem xét về kế hoạch tấn công quân đội địch và phải quyết định “tấn công” hoặc “rút lui”.

Tuy nhiên, mỗi vị tướng ở những khoảng cách xa nên không thể nói chuyện trực tiếp với nhau mà chỉ có thể liên lạc được bằng cách gửi Message.

Do đó, tuy rằng các vị tướng sẽ có thể giành chiến thắng nếu họ ra chỉ thị và khởi động cuộc tấn công cùng một lúc, nhưng nếu họ chỉ tấn công với một phần của đội quân thì họ sẽ thua cuộc. Tóm lại, tất cả các vị tướng cần phải đồng ý thống nhất về việc nên tấn công hay rút lui.

Tuy nhiên, trong các vị tướng sẽ có thể có vị tướng phản bội.

Nếu vị tướng phản bội nhận được lời đề nghị tấn công từ một vị tướng, họ có thể chuyển sang đề nghị rút quân và truyền lại cho vị tướng khác. Nếu như vậy, một vài các vị tướng được giả lập rằng họ có thể nhận được cả đề nghị tấn công lẫn đề nghị rút lui.

Trong trường hợp tệ nhất, các bên không thể đạt được sự đồng thuận và các ý kiến bị phân chia làm đôi giữa tấn công hoặc rút lui, dẫn đến chỉ có một vài đội quân bắt đầu tấn công và sẽ bị thua cuộc.

 

Byzantine Generals Problem này áp dụng cho vấn đề xây dựng sự đồng thuận bằng mạng Internet.

Trong P2PNetwork, mỗi Node không sở hữu cơ sở dữ liệu liên quan đến toàn bộ các Node khác. Hơn nữa, việc thực hiện hòa giải không thể đạt được giữa các Node mà chỉ có thể giao tiếp gửi Message qua lại lẫn nhau.

Byzantine Generals Problem cũng tương tự như việc các vị tướng không biết ý đồ của tất cả các vị tướng mà chỉ có thể gửi Message cho nhau. Trong tình trạng như vậy, vấn đề là làm thế nào để đạt được sự đồng thuận giữa tất cả các thành viên.

Byzantine Generals Problem là vấn đề nổi tiếng thường được đề xuất trong sách giáo khoa Hệ thống phân tán.

Ngoài ra, sự xuất hiện của kết quả bại trận, vấn đề bất thường không thể dự đoán trước được gọi là sự thất bại Byzantine. Đây được gọi là sự thất bại rắc rối nhất trong toàn bộ các sự cố của máy tính.

Ví dụ cụ thể của Byzantine Generals Problem

Bởi vì rất khó để hiểu được chỉ bằng thông tin tổng quan, nên bạn hãy xem xét ví dụ cụ thể.

Giả sử có tổng số 3 vị tướng, trong đó có 1 kẻ phản bội và 2 vị tướng chân thành.

Tại đây, nếu giả sử rằng vị tướng chân thành A đề xuất “tấn công” thì câu hỏi Byzantine Generals Problem được đặt ra là liệu 2 vị tướng chân thành có thể thống nhất cùng tấn công hay không.

Vị tướng A đề xuất tấn công sẽ gửi một đề nghị tấn công cho các tướng khác.

Vị tướng B người đã nhận được đề nghị đó và sẽ chuyển sang cho tướng C khác.

Tuy nhiên, trong trường hợp vị tướng B là kẻ phản bội, đề nghị rút lui có thể được gửi đến vị tướng C thay vì tấn công.

Lúc này, bởi vì vị tướng C sẽ không biết được liệu đề xuất ban đầu vốn dĩ là cuộc tấn công hay rút lui, dẫn đến không thể tạo thành sự đồng thuận chính xác.

Nếu vị tướng C vô tình lựa chọn đề xuất rút quân do vị tướng B đã đưa ra, đề xuất tấn công mà tướng A lựa chọn sẽ bị phân chia ra, và vị tướng A và vị tướng C sẽ thua trận.

Tuy nhiên, nếu số lượng tướng quân trung thực tăng lên ba thì sẽ như thế nào?

Trong trường hợp vị tướng B là kẻ phản bội thì 3 vị tướng trung thực vẫn có thể đưa ra phán đoán chính xác để tấn công,dù cho vị tướng kia gửi thông tin sai lệch cho tướng C và tướng D để ra lệnh “Rút quân”.

Tóm lại, khi vị tướng của bên phản bội là N người, nếu các tướng trung thực là 2N + 1 người trở lên thì phán đoán của các vị tướng trung thực có thể sẽ thống nhất.

Nói theo cách khác, nếu “kẻ phản bội = Node chướng ngại vật” nhỏ hơn 1/3 tổng toàn bộ các Node, thì có thể sẽ hình thành sự đồng thuận một cách chính xác.

Byzantine Generals Problem và Bitcoin

Ví dụ điển hình cho sản phẩm sử dụng Blockchain chính là Bitcoin.

Vậy thì mối quan hệ giữa Byzantine Generals Problem và Bitcoin là như thế nào?

Trong Bitcoin, việc can thiệp vào giao dịch sẽ tương ứng với vị tướng phản bội trong Byzantine Generals Problem. Nếu bạn không giải quyết được Byzantine Generals Problem, Bitcoin sẽ không thể được hình thành dưới dạng tiền tệ.

Vì vậy, Bitcoin đã giới thiệu cơ chế phát hiện và ngăn chặn hành vi gian lận như thế này. Đó là Proof of Work.

Proof of Work gây khó khăn trong việc lưu lại dữ liệu giả mạo trong Block dựa vào Mining.

Hơn thế nữa, thông qua việc trao phần thưởng đối với việc khai thác, Minor sẽ hình thành cơ chế hành động trung thực và hợp lý về kinh tế.

Tức là, bằng hệ thống gọi là khai thác và chi trả phần tiền thưởng thành công cho việc khai thác, kẻ phản bội trong Byzantine Generals Problem đã được loại trừ.

Byzantine Generals Problem và Blockchain

Byzantine Generals Problem không chỉ với Bitcoin mà cũng có liên quan đến toàn bộ Blockchain.

Ethereum và NEM sử dụng blockchain giải quyết Byzantine Generals Problem bằng việc sử dụng các phương pháp thay thế như Proof of Stake và Proof of Importance.

 


Tổng kết

Byzantine Generals’ Problem đặt ra vấn đề liệu một thỏa thuận chính xác có thể được hình thành hay không khi có khả năng sự truyền đạt thông tin, các Node riêng lẻ có thể bị hỏng hoặc cố tình truyền thông tin sai lệch trên Mạng P2P. .

Byzantine Generals’ Problem bắt nguồn từ các vấn đề của các vị tướng quân Đế quốc Byzantine.

Vấn đề về Byzantine Generals’ Problem lần đầu tiên được giải quyết bằng Bitcoin.

Đồng tiền ảo giải quyết Byzantine Generals’ Problem dựa vào việc sử dụng các thuật toán được phê duyệt như Proof of Work, Proof of Stake và Proof of Importance, v.v…