Mphuong_luu28
🐋Cá Voi Phake🐋
1. “Byzantine generals problem" theo cách diễn giải của Lamport
Trong một bài báo của Lamport và cộng sự đã chỉ ra một vấn đề lớn của sự đồng thuận qua câu chuyện sau: Hãy tưởng tượng vài sư đoàn của quân đội Byzantine đang bên ngoài thành phố của địch. Mỗi sư đoàn có một tướng chỉ huy riêng, các vị tướng giao tiếp thông tin với nhau bằng một hộp thư. Sau khi quan sát kẻ địch họ phải thống nhất với nhau một kế hoạch hành động chung. Tuy nhiên một vài vị tướng trong đó có thể là kẻ phản bội, đang cố chống lại sự thống nhất hành động của các vị tướng trung thành.
Giả sử có n vị tướng và một trong số họ là tướng chỉ huy. Tướng chỉ huy muốn đưa ra một mệnh lệnh là ATTACT hoặc RETREAT sao cho:
Giả sử có n vị tướng và một trong số họ là tướng chỉ huy. Tướng chỉ huy muốn đưa ra một mệnh lệnh là ATTACT hoặc RETREAT sao cho:
- Một là tất cả các vị tướng trung thành đạt được cùng một quyết định (nhất quán với nhau)
- Hai là nếu tướng chỉ huy trung thành thì tất cả các tướng trung thành sẽ tuân theo mệnh lệnh của tướng chỉ huy (Xác thực được người trung thực)
Lamport và cộng sự đặt tên cho vấn đề này là "Byzantine generals problem" và mọi người cũng hay gọi Byzantine Broadcast (BB).
Lưu ý, nếu trường hợp số 2 ở trên xảy ra thì chẳng có gì được gọi là vấn đề cả. Giả sử các tướng khác có thể xác minh lệnh của tướng chỉ huy thì vị tướng chỉ huy đó có thể gửi lệnh của mình cho các tướng khác và họ chỉ việc ngoan ngoãn làm theo.
Tất nhiên, ngay cả tướng chỉ huy cũng có thể là kẻ phản bội và trong trường hợp này có thể đề xuất khác nhau. Nếu không có giải pháp nào thì sẽ dẫn đến các quyết định không nhất quán. Và kế hoạch tấn công vào thành phố của địch sẽ không hiệu quả.
Vậy, liệu có thể thống nhất với một kế hoạch tấn công bằng cách giao tiếp với nhau bất chấp sự ảnh hưởng của các vị tướng hư hỏng (corrupted)?
Lưu ý, nếu trường hợp số 2 ở trên xảy ra thì chẳng có gì được gọi là vấn đề cả. Giả sử các tướng khác có thể xác minh lệnh của tướng chỉ huy thì vị tướng chỉ huy đó có thể gửi lệnh của mình cho các tướng khác và họ chỉ việc ngoan ngoãn làm theo.
Tất nhiên, ngay cả tướng chỉ huy cũng có thể là kẻ phản bội và trong trường hợp này có thể đề xuất khác nhau. Nếu không có giải pháp nào thì sẽ dẫn đến các quyết định không nhất quán. Và kế hoạch tấn công vào thành phố của địch sẽ không hiệu quả.
Vậy, liệu có thể thống nhất với một kế hoạch tấn công bằng cách giao tiếp với nhau bất chấp sự ảnh hưởng của các vị tướng hư hỏng (corrupted)?
2. Một biến thể khác của Byzantine generals problem
Sau đây là một biến thể khác của BB gần với bối cảnh của chúng ta hơn. Giả sử trong đại dịch covid-19 Ủy ban chương trình của hội nghị blockchain'20 cố gắng quyết định xem Hội nghị năm tới tổ chức trực tuyến hay trực tiếp.
Trưởng ban của chương trình - Chủ tọa muốn gửi một đề nghị đến toàn thể ban chương trình đó là "virtual" hoặc "physical" (tổ chức trên không gian ảo hoặc thực).
Vì ban tổ chức chương trình đều đang trong quá trình cách ly, họ quyết định đạt được thỏa thuận qua Internet bằng cách gửi email qua lại cho nhau. Chúng ta có thể cho rằng một email đã được gửi một lúc nào đó hôm nay và người nhận sẽ nhận và đọc nó lúc đầu ngày mai.
Tình huống giả định ở trên tương tự như một hệ thống máy tính trong đó một hoặc nhiều thành phần có thể bị lỗi.
Chính xác hơn, đây là vấn đề đồng thuận phân tán trong một hệ thống phân tán, một số nốt (nodes) hoạt động tùy tiện trong khi các nốt hoạt động chính xác vẫn phải đồng ý về một giá trị chung giữa chúng.
Điều này cũng tương tự như trong các tướng của Byzantine có một số tướng hoạt động tùy tiện dẫn đến sự không nhất quán trong việc thực hiện mệnh lệnh chung.
Trưởng ban của chương trình - Chủ tọa muốn gửi một đề nghị đến toàn thể ban chương trình đó là "virtual" hoặc "physical" (tổ chức trên không gian ảo hoặc thực).
Vì ban tổ chức chương trình đều đang trong quá trình cách ly, họ quyết định đạt được thỏa thuận qua Internet bằng cách gửi email qua lại cho nhau. Chúng ta có thể cho rằng một email đã được gửi một lúc nào đó hôm nay và người nhận sẽ nhận và đọc nó lúc đầu ngày mai.
Tình huống giả định ở trên tương tự như một hệ thống máy tính trong đó một hoặc nhiều thành phần có thể bị lỗi.
Chính xác hơn, đây là vấn đề đồng thuận phân tán trong một hệ thống phân tán, một số nốt (nodes) hoạt động tùy tiện trong khi các nốt hoạt động chính xác vẫn phải đồng ý về một giá trị chung giữa chúng.
Điều này cũng tương tự như trong các tướng của Byzantine có một số tướng hoạt động tùy tiện dẫn đến sự không nhất quán trong việc thực hiện mệnh lệnh chung.
3. Định nghĩa Byzantine Broadcast
Ở thời điểm bắt đầu một giao thức, người gửi được chỉ định sẽ nhận giao thức đầu vào b Є {0,1}. Sau đó các nốt chạy vài giao thức, ở cuối giao thức các nốt trung thực sẽ xuất ra một bit.
Giao thức Byzantine Broadcast (BB) phải đáp ứng hai yêu cầu sau:
Giao thức Byzantine Broadcast (BB) phải đáp ứng hai yêu cầu sau:
- Tính nhất quán (Consistency): Nếu hai nốt trung thực xuất ra b và b' tương ứng, thì b=b'
- Tính hợp lệ (Validity): Nếu người gửi trung thực và nhận được bit đầu vào b, thì tất cả các nốt trung thực xuất ra b.
Chú ý: Chỉ riêng tính nhất quán sẽ rất khó đạt được nếu không có tính hợp lệ, do đó định nghĩa về BB chỉ có nghĩa khi đạt được đồng thời cả 2 thuộc tính.
Cảm ơn anh em đã theo dõi bài viết nhé!
