Byzantine Generals Problem

Lamport, Shostak, dan Pease menerbitkan alegori ini di ACM TOPLAS pada Juli 1982 untuk menjelaskan konsistensi interaktif sistem tereplikasi. Para jenderal terpisah harus memilih satu rencana meski pengkhianat dapat mengirim klaim berbeda. Kegagalan Bizantium lebih luas dari berhentinya proses: komponen dapat berbohong, berkontradiksi, menghilangkan pesan, atau tampak benar hanya bagi sebagian sistem. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

Makalah memisahkan IC1: semua letnan setia mengikuti perintah sama, dan IC2: jika komandan setia mereka mengikuti perintahnya. Istilah modern terkait ialah kesepakatan atau keamanan, validitas, serta penyelesaian atau kemajuan. Jaminan hanya bermakna bersama model jaringan, autentikasi, dan batas maksimum kegagalan. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Pease, Shostak & Lamport — Reaching Agreement in the Presence of Faults (1980)]

Dalam model pesan lisan, pengirim langsung diketahui, ketidakhadiran terdeteksi, dan setiap pasangan berkomunikasi, tetapi pengkhianat dapat mengirim nilai berbeda. OM(m) meneruskan nilai secara rekursif lalu memakai mayoritas deterministik. Menoleransi m proses Bizantium memerlukan sedikitnya 3m+1 peserta, lebih dari dua pertiga setia. Tiga proses tak dapat menoleransi satu pengkhianat karena perannya tak bisa dibedakan. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)]

Tanda tangan tak-terpalsukan menyingkap pesan kontradiktif dan mencegah perubahan perintah yang ditandatangani peserta setia. Algoritme meneruskan nilai bertanda tangan baru lalu memilih secara deterministik. Dengan asumsi ideal, jumlah pengkhianat tak dibatasi. Namun tanda tangan membuktikan asal, bukan kebenaran, pengiriman tepat waktu, atau kejujuran kunci yang bocor; Dolev–Strong kemudian memperketat batas putaran. [Lamport, Shostak & Pease — The Byzantine Generals Problem (1982)] [Dolev & Strong — Authenticated Algorithms for Byzantine Agreement (1983)]

Kemampuan menjamin kemajuan bergantung pada kondisi waktu. Hasil Fischer–Lynch–Paterson tahun 1985 menunjukkan bahwa dalam sistem pesan deterministik yang sepenuhnya asinkron, satu proses yang boleh berhenti saja sudah memungkinkan eksekusi sah yang tidak menuntaskan konsensus. FLP tidak menyatakan bahwa sistem nyata tidak pernah bersepakat. Jaminan kemajuan memerlukan asumsi tambahan, misalnya batas waktu yang akhirnya berlaku atau pendeteksi kegagalan dengan sifat tertentu, atau perubahan ke protokol teracak. Penunjukan pemimpin saja tidak cukup. Saat jaringan terpisah lama, protokol yang aman dapat berhenti menuntaskan operasi. [Fischer, Lynch & Paterson — Impossibility of Distributed Consensus with One Faulty Process (1985)] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]

PBFT karya Miguel Castro dan Barbara Liskov pada 1999 menerapkan kesepakatan Bizantium pada mesin keadaan yang direplikasi. Konfigurasi dasar n = 3f+1 menoleransi f replika Bizantium. Keadaan siap mencakup pre-prepare dari replika utama dan 2f pesan prepare yang cocok; pengesahan lokal memerlukan keadaan siap dan 2f+1 pesan commit yang cocok. Irisan kuorum dan aturan pergantian pandangan mencegah pengesahan yang bertentangan. Autentikasi, nomor urut, titik pemeriksaan, dan pergantian pandangan menangani pemalsuan, pengulangan pesan, pertumbuhan catatan, dan pemimpin bermasalah. Kumpulan replika yang dikenal serta finalitas deterministik berbeda dari jaringan Proof of Work terbuka. [Castro & Liskov — Practical Byzantine Fault Tolerance (1999)]

Bitcoin tidak menjalankan OM atau PBFT dan tidak menghitung simpul bernama. Proof of Work yang tahan serangan Sybil membobot riwayat yang bersaing berdasarkan kerja terkumpul; setiap Full Node secara mandiri menolak blok yang melanggar aturan konsensus dan mengikuti rantai valid dengan kerja kumulatif terbesar. Percabangan sementara memang diharapkan. Dengan asumsi keunggulan kerja jujur dan kondisi komunikasi, peluang penulisan ulang menurun seiring kedalaman konfirmasi, tetapi bukan berarti mustahil dibalik secara matematis. Model Bitcoin Backbone merumuskan awalan bersama, pertumbuhan, dan kualitas rantai dengan proporsi kerja penyerang serta kondisi jaringan yang ditetapkan secara eksplisit. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol]

Pernyataan bahwa Bitcoin menyelesaikan masalah jenderal Bizantium menyembunyikan perubahan model. Kesepakatan klasik dimulai dari kelompok tetap dengan identitas dikenal dan batas f; Bitcoin mengizinkan peserta bernama samaran yang berubah serta sumber daya langka eksternal. Jaminannya tetap membutuhkan asumsi khusus tentang pengiriman pesan. Proof of Work membatasi pengaruh identitas Sybil, tetapi tidak mencegah serangan isolasi eclipse, penyensoran, penambangan egois, kesalahan perangkat lunak, atau reorganisasi oleh mayoritas laju hash. Model ancaman harus menentukan penyerang, waktu, keanggotaan, dan finalitas; label BFT saja tidak cukup. [Nakamoto — Bitcoin: A Peer-to-Peer Electronic Cash System] [Garay, Kiayias & Leonardos — The Bitcoin Backbone Protocol] [NIST IR 8460 Initial Public Draft — State Machine Replication and Consensus with Byzantine Adversaries]