Khả năng chịu lỗi Byzantine

Khả năng chịu lỗi Byzantine là nghiên cứu về việc đạt được sự đồng thuận khi một số tiến trình có thể thất bại một cách tùy tiện, bao gồm cả việc gửi các thông điệp xung đột hoặc độc hại.

Definition

Lỗi Byzantine là một sự sai lệch tùy ý so với đặc tả của một thành phần, bao gồm cả hành vi độc hại; khả năng chịu lỗi Byzantine là khả năng của một giao thức phân tán để thỏa mãn các điều kiện đúng đắn của nó mặc dù có một số lượng giới hạn các thành phần lỗi như vậy.

Scope

Chủ đề này bao gồm vấn đề các tướng lĩnh Byzantine và các giới hạn khả năng phục hồi chặt chẽ mà nó thiết lập (ít nhất 3f+1 tiến trình, hoặc các thông điệp đã ký, để chịu đựng f lỗi tùy ý), các thuật toán đồng thuận thông điệp truyền miệng và thông điệp đã ký đồng bộ, và các giao thức chịu lỗi Byzantine không đồng bộ thực tế như PBFT và các hậu duệ của chúng. Nó làm nền tảng cho các mô hình tin cậy của các blockchain có quyền hạn và các dịch vụ sao chép có tính toàn vẹn cao.

Core questions

• Cần bao nhiêu tiến trình đúng để chịu đựng một số lượng lỗi tùy ý nhất định?
• Chữ ký số thay đổi giới hạn khả năng phục hồi đối với sự đồng thuận Byzantine như thế nào?
• Làm thế nào để sự đồng thuận Byzantine đủ hiệu quả cho các hệ thống không đồng bộ thực tế?

Key theories

Giới hạn các tướng lĩnh Byzantine

Với các thông điệp không được xác thực (truyền miệng), sự đồng thuận Byzantine có thể giải quyết được nếu và chỉ nếu hơn hai phần ba các tiến trình là đúng (n > 3f); các thông điệp được xác thực với chữ ký không thể giả mạo làm giảm yêu cầu này.

Sao chép BFT thực tế

PBFT cho thấy rằng sự đồng thuận Byzantine có thể chạy trong một hệ thống bán đồng bộ với sao chép máy trạng thái sử dụng một máy chủ chính và một giao thức ba pha, đạt được hiệu suất thực tế trong khi chịu đựng tới một phần ba các bản sao bị lỗi.

Thuật toán đồng thuận đồng bộ

Trong mô hình đồng bộ, các thuật toán thông điệp truyền miệng và thông điệp đã ký đệ quy đạt được sự đồng thuận trong f+1 vòng, minh họa chi phí phức tạp về vòng để chịu đựng các lỗi tùy ý.

Clinical relevance

Khả năng chịu lỗi Byzantine là nền tảng của các hệ thống phải chịu đựng không chỉ sự cố mà còn cả sự xâm nhập hoặc hành vi độc hại, bao gồm các blockchain có quyền hạn, các dịch vụ sao chép có độ tin cậy cao, và hệ thống điều khiển hàng không và vũ trụ nơi không thể loại trừ khả năng hỏng hóc thành phần tùy ý.

History

Pease, Shostak và Lamport đã thiết lập các giới hạn đồng thuận vào năm 1980 và kịch tính hóa chúng thành vấn đề các tướng lĩnh Byzantine vào năm 1982; trong gần hai thập kỷ, sự đồng thuận Byzantine được coi là quá tốn kém để áp dụng vào thực tế cho đến khi PBFT của Castro và Liskov năm 1999 chứng minh khả năng sao chép Byzantine không đồng bộ hiệu quả, làm sống lại lĩnh vực này và sau đó cung cấp thông tin cho sự đồng thuận blockchain.

Key figures

• Leslie Lamport
• Robert Shostak
• Marshall Pease
• Miguel Castro
• Barbara Liskov

Seminal works

• lamport1982byz
• castro1999
• pease1980

Frequently asked questions

Tại sao việc chịu đựng f lỗi Byzantine yêu cầu 3f+1 tiến trình?

Các tiến trình đúng phải đạt được quyết định đa số ngay cả khi f tiến trình lỗi nói dối và f tiến trình khác có thể chậm hoặc không thể truy cập; chỉ với số lượng tiến trình gấp hơn ba lần số tiến trình lỗi thì đa số đúng mới luôn có thể bỏ phiếu áp đảo sự kết hợp của các thành phần lỗi và chậm trễ.