BTC
$96,000
5.73%
ETH
$3,521.91
3.97%
HTX
$0.{5}2273
5.23%
SOL
$198.17
3.05%
BNB
$710
3.05%
lang
简体中文
繁體中文
English
Tiếng Việt
한국어
日本語
ภาษาไทย
Türkçe
Trang chủ
AI AI
Tin nhanh
Bài viết
Sự kiện
BlockBeats Pro
Thêm
Thông tin tài chính
Chuyên đề
Hệ sinh thái chuỗi khối
Mục nhập
Podcast
Data
OPRR
Partnered With:

Tìm hiểu vấn đề của các vị tướng Byzantine trong một bài viết

Đọc bài viết này mất 16 phút
Bài toán Byzantine Generals là mô hình chịu lỗi phức tạp nhất trong lĩnh vực hệ thống phân tán, mô tả cách đạt được sự đồng thuận trong hệ thống phân tán khi có hành vi nguy hiểm, chẳng hạn như giả mạo hoặc giả mạo tin nhắn.

Tiêu đề gốc: "Hiểu vấn đề của các vị tướng Byzantine trong một bài viết"
Nguồn gốc: Blockchain Basecamp


一文读懂拜占庭将军问题

Tác giả | Yu Liebing
Biên tập viên | Carol
Sản xuất | Blockchain Camp (ID: blockchain_camp)


Vấn đề các vị tướng Byzantine (Vấn đề các vị tướng Byzantine) cung cấp một mô tả tình huống về vấn đề đồng thuận phân tán và được xuất bản lần đầu tiên vào năm 1982 bởi Leslie Lamport và những người khác. Bài viết “Bài toán các vị tướng Byzantine” cũng đưa ra hai thuật toán giải bài toán các vị tướng Byzantine:

Giải pháp bằng miệng message);

Một giải pháp với tin nhắn đã được ký).

Giấy:

https://www -inst.eecs.berkeley.edu /~cs162/sp16/static/readings/Original_Byzantine.pdf

Bài viết này sẽ mô tả chi tiết điều này sau Hai thuật toán. Trên thực tế, Bài toán chung của Byzantine là mô hình chịu lỗi phức tạp nhất trong lĩnh vực hệ thống phân tán, mô tả cách đạt được sự đồng thuận trong hệ thống phân tán khi có hành vi nguy hiểm, chẳng hạn như giả mạo hoặc giả mạo tin nhắn. Đây là cơ sở quan trọng cho sự hiểu biết của chúng ta về các giao thức và thuật toán đồng thuận phân tán.

Mô tả bài toán của các vị tướng Byzantine

Bài toán về các vị tướng Byzantine mô tả một kịch bản như vậy:

一文读懂拜占庭将军问题

Hình 1. Vấn đề của các tướng lĩnh Byzantine

Một số sư đoàn của quân đội Đế quốc Byzantine đang đóng quân tại thành phố của kẻ thù Ngoài ra, mỗi sư đoàn đều có tướng riêng của mình chỉ huy. Các tướng chỉ có thể liên lạc với nhau thông qua người đưa tin. Sau khi quan sát tình hình của kẻ thù, họ phải xây dựng một kế hoạch hành động chung, chẳng hạn như tấn công hoặc rút lui, và chiến thắng chỉ có thể đạt được khi hơn một nửa số tướng cùng nhau phát động tấn công. Tuy nhiên, một số vị tướng này có thể là những kẻ phản bội đang cố gắng ngăn cản các tướng trung thành thống nhất một kế hoạch hành động. Tệ hơn nữa, người đưa tin chịu trách nhiệm gửi tin nhắn cũng có thể là kẻ phản bội, họ có thể giả mạo hoặc giả mạo tin nhắn hoặc có thể khiến tin nhắn bị thất lạc.

Để hiểu sâu hơn về Bài toán các vị tướng Byzantine, chúng tôi lấy Bài toán ba vị tướng làm ví dụ. Khi ba vị tướng trung thành, họ có thể quyết định đường lối hành động nhất quán thông qua biểu quyết, Hình 2 cho thấy kịch bản trong đó Tướng A và B có thể phát động tấn công bằng cách quan sát tình hình quân sự của địch và phán đoán tình hình của mình, trong khi Tướng C có thể phát động một cuộc tấn công. tấn công bằng cách quan sát tình hình quân sự của kẻ thù và đánh giá tình hình của chính mình, dựa trên tình hình quân sự và tình hình của chính mình, có thể phán đoán nên rút lui. Cuối cùng ba tướng biểu quyết và kết quả là tấn công:rút lui = 2:1 nên sẽ cùng nhau tấn công để giành chiến thắng. Đối với 3 tướng, khi mỗi tướng có thể thi hành 2 quyết định (tấn công hoặc rút lui) sẽ có 6 kịch bản khác nhau, Hình 2 là một trong số đó, 5 kịch bản còn lại có thể suy luận đơn giản là 1 lá phiếu sẽ dẫn cả 3 tướng đến nhất trí về một kế hoạch hành động.

一文读懂拜占庭将军问题
Hình 2. Ba vị tướng trung thành Kịch bản

Khi có kẻ phản bội trong số ba vị tướng, điều đó có thể làm gián đoạn kế hoạch tác chiến thông thường. Hình 3 thể hiện kịch bản Tướng C là kẻ phản bội, gửi các tin nhắn khác nhau đến Tướng A và Tướng B. Trong kịch bản này, Tướng A bị tấn công bằng cách biểu quyết: rút lui = 1:2 và cuối cùng sẽ thực hiện hành động rút lui. ; Tướng B nhận được Tấn công: Rút lui=2:1 bằng cách bỏ phiếu và cuối cùng sẽ lập kế hoạch hành động cho cuộc tấn công. Kết quả chỉ có tướng B tấn công và bị đánh bại.

一文读懂拜占庭将军问题
Hình 3. Cảnh hai người chung thủy và một nổi loạn

一文读懂拜占庭将军问题 span>

Trên thực tế, đối với kịch bản có kẻ phản bội trong số ba vị tướng, không thể luôn luôn đạt được một đường lối hành động nhất quán. Bằng chứng chi tiết có thể được tìm thấy trong bài báo của Leslie Lamport. Ngoài ra, bài viết còn đưa ra một kết luận tổng quát hơn: nếu có m tướng nổi dậy thì cần ít nhất 3m+1 tướng để cuối cùng đạt được kế hoạch hành động nhất quán.

Giải pháp

Leslie Lamport đã đưa ra hai giải pháp cho Bài toán các vị tướng Byzantine trong bài báo, đó là giải pháp bằng tin nhắn bằng miệng (A giải pháp bằng tin nhắn bằng miệng) và một giải pháp bằng tin nhắn đã ký (A giải pháp bằng tin nhắn đã ký).

1. Giải pháp nhắn tin bằng lời nói

Trước hết, định nghĩa về tin nhắn bằng miệng (Oral message) như sau:

A1. Bất kỳ tin nhắn nào đã được gửi đi sẽ truyền tải chính xác;

A2. Người nhận tin nhắn biết ai đã gửi tin nhắn;

A3. Có thể phát hiện sự vắng mặt của tin nhắn.

Dựa trên định nghĩa về tin nhắn miệng, chúng ta có thể biết rằng tin nhắn miệng không thể bị giả mạo nhưng có thể bị giả mạo. Dựa vào diễn biến của kịch bản ở hình 3, chúng ta biết khi có tướng phản bội thì phải bổ sung thêm ba tướng trung thành nữa để đạt được thống nhất hành động cuối cùng. Để hiểu sâu hơn, chúng ta sẽ sử dụng kịch bản 3 vị tướng trung thành và 1 vị tướng phản bội để rút ra giải pháp truyền miệng. Trong giải pháp truyền miệng, tướng gửi tin trước được gọi là chỉ huy, các tướng còn lại gọi là trung úy. Đối với kịch bản 3 người trung thành và 1 kẻ phản loạn, cần có hai vòng đàm phán thông tin chiến đấu, nếu không nhận được thông tin chiến đấu, hệ thống sẽ mặc định rút lui. Hình 4 là cảnh người chỉ huy là một vị tướng trung thành. Ở vòng đàm phán thông tin chiến đấu đầu tiên, người chỉ huy đã gửi tin nhắn tấn công cho ba phụ tá. Ở vòng thứ hai, ba phụ tá lại tiến hành đàm phán thông tin chiến đấu. Kể từ Tướng A , B là một vị tướng trung thành nên họ đã gửi tin tấn công cho hai phụ tá còn lại dựa trên tin nhắn của chỉ huy, trong khi tướng C là một tên tướng phản bội, nhằm phá vỡ kế hoạch tác chiến, ông ta đã gửi tin rút lui về phía hai phụ tá khác. Cuối cùng, Tướng chỉ huy, Tướng A và B đồng ý về kế hoạch tấn công dẫn đến chiến thắng.

一文读懂拜占庭将军问题
Hình 4. Cảnh người chỉ huy trung thành tướng

Hình 5 là cảnh người chỉ huy là kẻ phản bội. Vòng đàm phán thông tin chiến đấu đầu tiên, người chỉ huy hỏi Đại tướng A, B gửi tin rút lui, nhưng nhằm phá rối quyết định của tướng C đã gửi tin tấn công. Ở vòng thứ hai, vì tất cả các phụ tá đều là tướng trung thành nên thông điệp từ người chỉ huy được gửi chính xác đến hai phụ tá còn lại. Cuối cùng tất cả các tướng trung thành đã có thể đồng ý về kế hoạch rút lui.

一文读懂拜占庭将军问题
Hình 5. Cảnh người chỉ huy là kẻ phản bội

Như đã đề cập ở trên, đối với bài toán truyền miệng về tướng Byzantine, nếu số lượng tướng nổi dậy là m thì số lượng tướng không được nhỏ hơn 3m+1 thì cuối cùng mới có thể đạt được kế hoạch hành động đã thống nhất. Điều đáng chú ý là trong thuật toán này, số lượng tướng nổi dậy m được biết và số lượng tướng nổi dậy m xác định số lần đệ quy, tức là số lượng tướng nổi dậy m xác định số vòng đàm phán thông tin chiến đấu. Nếu có m Nếu tướng nổi loạn thì cần m+1 vòng đàm phán thông tin chiến đấu. Đây cũng chính là lý do cần phải có hai vòng đàm phán thông tin chiến đấu khi có tướng nổi loạn kể trên.

2. Giải pháp tin nhắn bằng chữ ký

Tương tự, định nghĩa tin nhắn chữ ký cũng dựa trên định nghĩa tin nhắn miệng có bổ sung thêm 2 mục sau:

A4. Chữ ký của một vị tướng trung thành không thể bị giả mạo và mọi thay đổi đối với nội dung thông điệp đã ký của ông ta sẽ bị phát hiện;

A5 . Bất cứ ai cũng có thể xác minh tính xác thực của chữ ký của tướng quân.

Dựa trên định nghĩa về tin nhắn đã ký, chúng ta có thể biết rằng tin nhắn đã ký không thể bị giả mạo hoặc giả mạo. Để hiểu sâu hơn về giải pháp tin nhắn đã ký, chúng tôi cũng lấy bài toán ba tổng quát làm ví dụ để rút ra. Hình 6 là kịch bản một vị tướng trung thành đứng ra chủ trì đàm phán tác chiến, tướng A đứng đầu gửi tin nhắn tấn công tới tướng B và C. Một khi tướng phản bội C giả mạo tin nhắn của tướng A, tướng B sẽ phát hiện ra rằng thông tin chiến đấu đã bị giả mạo bởi Tướng C., Tướng B sẽ thực hiện tin nhắn của Tướng A.

一文读懂拜占庭将军问题
Hình 6. Vị tướng trung thành dẫn đầu bắt đầu đàm phán chiến đấu

Hình 7 là cảnh tướng nổi dậy đi đầu trong việc bắt đầu đàm phán chiến đấu. Tướng nổi dậy là tướng C là người đầu tiên gửi thông tin chiến đấu sai lệch thì tướng A, B sẽ thấy thông tin chiến đấu do tướng C gửi không nhất quán nên bị phán là kẻ phản bội. Nó có thể được xử lý trước khi tiến hành tư vấn thông tin chiến đấu.

一文读懂拜占庭将军问题
Hình 7. Tướng nổi dậy dẫn đầu bắt đầu đàm phán chiến đấu

Giải pháp tin nhắn chữ ký có thể xử lý bất kỳ tình huống phản bội nào.

Tóm tắt

Trong lĩnh vực hệ thống phân tán, sự tương ứng giữa các vai trò trong Bài toán tổng quát Byzantine và thế giới máy tính như sau:

Chung, tương ứng với Nút máy tính;

Tướng trung thành, tương ứng với nút máy tính hoạt động tốt;

Nút máy tính nổi loạn, bị kiểm soát bất hợp pháp;

Người đưa tin đã bị giết và lỗi liên lạc khiến Tin nhắn bị mất;

Người đưa tin bị thay thế bởi gián điệp, thông tin liên lạc bị tấn công và những kẻ tấn công giả mạo hoặc làm sai lệch thông tin.

Như đã đề cập ở trên, Bài toán tổng quát Byzantine cung cấp một mô tả tình huống về vấn đề đồng thuận phân tán và là một phần quan trọng của lĩnh vực phân tán hệ thống.Mô hình phức tạp nhất. Ngoài ra, nó cũng cung cấp một khuôn khổ để chúng tôi hiểu và phân loại nhiều giao thức và thuật toán đồng thuận phân tán hiện có. Các giao thức và thuật toán nhất quán phân tán hiện tại có thể được chia chủ yếu thành hai loại:

Một là thuật toán chịu lỗi (Crash Fault Tolerance ) , CFT), một thuật toán có khả năng chịu lỗi không phải của Byzantine, giải quyết vấn đề đồng thuận trong các tình huống có lỗi trong hệ thống phân tán nhưng không có cuộc tấn công độc hại. Nói cách khác, trong trường hợp này, có thể xảy ra hiện tượng mất tin nhắn và sao chép tin nhắn, nhưng không có trường hợp nào tin nhắn bị giả mạo hoặc giả mạo. Thường được sử dụng trong các hệ thống phân tán trong các tình huống mạng cục bộ, chẳng hạn như cơ sở dữ liệu phân tán. Các thuật toán phổ biến thuộc loại này bao gồm thuật toán Paxos, thuật toán Raft, giao thức ZAB, v.v.

Một loại là thuật toán chịu lỗi Byzantine, có thể giải quyết vấn đề đồng thuận trong các hệ thống phân tán, nơi có cả lỗi và các cuộc tấn công độc hại. Thường được sử dụng trong các hệ thống phân tán trong các tình huống Internet, chẳng hạn như trong công nghệ chuỗi khối của tiền kỹ thuật số. Các thuật toán phổ biến thuộc loại này bao gồm thuật toán PBFT và thuật toán PoW.


一文读懂拜占庭将军问题

Sau khi đọc bài viết này, bạn nghĩ sao về 2 giải pháp này? Chào mừng bạn đến thảo luận với chúng tôi trong khu vực bình luận!

Liên kết nguồn: weixin.qq.com



Chào mừng bạn tham gia cộng đồng chính thức của BlockBeats:

Nhóm Telegram đăng ký: https://t.me/theblockbeats

Nhóm Telegram thảo luận: https://t.me/BlockBeats_App

Tài khoản Twitter chính thức: https://twitter.com/BlockBeatsAsia

举报 Báo lỗi/Báo cáo
Chọn thư viện
Thêm mới thư viện
Hủy
Hoàn thành
Thêm mới thư viện
Chỉ mình tôi có thể nhìn thấy
Công khai
Lưu
Báo lỗi/Báo cáo
Gửi