Byzantine Generals Problem

Bayangkan pasukan ditempatkan mengelilingi sebuah kota. Mereka harus menyerang bersama atau mundur bersama; tindakan yang terpecah bisa berakibat fatal. Komandan mengirim perintah, tetapi seseorang mungkin berkhianat dan menyampaikan versi berbeda. Bagaimana peserta yang dapat diandalkan akhirnya bertindak sama? Ini bukan kisah pertempuran nyata, melainkan eksperimen pikiran tentang komputer yang perlu memiliki catatan selaras. Misalnya, beberapa server, yaitu komputer yang menjalankan layanan bersama, harus sepakat apakah pembayaran sudah diproses. Menerima sembarang jawaban belum cukup: jawaban itu harus mendukung keputusan bersama. [1] [9]

Leslie Lamport, Robert Shostak, dan Marshall Pease memperkenalkan rumusan terkenal ini pada Juli 1982, setelah karya mereka tahun 1980 tentang kesepakatan saat terjadi kegagalan. Pengkhianat mewakili komponen yang perilakunya tidak lagi dapat diprediksi. Komputer tidak harus sekadar berhenti. Ia dapat menjawab satu tetangga dengan benar dan yang lain dengan keliru, menghilangkan pesan, atau mengaku melihat hal berbeda. Penyebabnya bisa berupa serangan maupun kesalahan program. Kegagalan Bizantium menggambarkan perilaku yang diamati peserta lain, bukan niat perangkat. BFT (Byzantine Fault Tolerance) berarti kemampuan menghadapi perilaku tersebut dengan syarat-syarat tertentu. [1] [2]

Masalah awal menetapkan dua syarat. IC1 menuntut semua bawahan yang dapat diandalkan menerima perintah yang sama. IC2 menambahkan bahwa jika komandannya juga dapat diandalkan, mereka harus menerima perintah yang benar-benar dikirimnya. Tanpa syarat kedua, aturan ‘selalu mundur’ tampak menyelesaikan masalah, padahal mengabaikan komandan yang jujur. Sistem komputer membedakan keselamatan, yaitu tidak menghasilkan keputusan bertentangan, dari kelangsungan kemajuan, yaitu kemampuan mencapai hasil. Aturan lain menentukan hasil yang sah. Catatan yang selaras tidak dengan sendirinya membuktikan bahwa pernyataan masukan benar di dunia luar. [1] [9]

Sebut komandan A, dan bawahannya B serta C. C menerima perintah menyerang dari A, tetapi B mengatakan komandan menyuruh mundur. Apakah B berbohong, atau A mengirim perintah berbeda? Tanpa tanda tangan yang dapat diverifikasi setelah diteruskan, C mungkin tak dapat membedakan kedua keadaan. B bisa menghadapi ketidakpastian yang sama. Selalu mengikuti komandan memungkinkan A yang curang memecah mereka; selalu mengabaikannya melanggar syarat untuk komandan jujur. Jadi, dalam masalah tiga peserta dengan satu kemungkinan pengkhianat ini, tidak ada prosedur tanpa tanda tangan yang selalu berhasil. Hambatannya adalah kurangnya informasi pembeda, bukan komputer yang lambat. [1] [9]

Dalam model klasik tanpa tanda tangan, menghadapi m kemungkinan pengkhianat memerlukan setidaknya n ≥ 3m+1 peserta: empat untuk satu pengkhianat. Di sini n adalah jumlah seluruh peserta, sedangkan m adalah jumlah maksimum pengkhianat yang harus dapat ditoleransi sistem. Bukan sekadar menambah satu suara lalu menghitung mayoritas sekali. OM(m) membuat peserta berulang kali meneruskan apa yang didengar dan menilai pesan dengan aturan bersama; kasus dasar OM(0) memakai nilai komandan atau nilai bawaan yang disepakati. Model mengasumsikan peserta dikenal, hubungan langsung, pesan terkirim diterima dengan benar, identitas pengirim langsung diketahui, dan pesan yang tidak ada dapat dideteksi. Jadi, ‘tanpa tanda tangan’ bukan berarti ‘tanpa autentikasi asal apa pun’. Tanpa asumsi itu, angka empat tidak menjamin apa-apa. [1] [9]

Dengan tanda tangan digital yang dapat diverifikasi, Digital Signature, B dapat menunjukkan kepada C apa yang benar-benar ditandatangani komandan. Program membuat tanda tangan ini dengan kunci privat, yaitu nilai angka rahasia. Pihak lain memeriksanya dengan kunci publik yang sesuai, tanpa perlu mengetahui kunci privatnya. Pengkhianat tidak dapat diam-diam mengubah perintah peserta tepercaya atau meniru tanda tangannya. Algoritme pesan bertanda tangan menyebarkan nilai bertanda tangan dan menerapkan aturan pemilihan bersama. Dalam model ini, tuntutan mayoritas jujur tadi hilang, tetapi asumsi tentang tanda tangan yang tidak dapat dipalsukan, pengiriman, dan waktu putaran tetap diperlukan. Karya Dolev dan Strong tahun 1983 meneliti lebih lanjut jumlah putaran yang dibutuhkan. Tanda tangan sah pun tidak menjamin kebenaran isi atau pengiriman tepat waktu, dan tidak membuktikan bahwa kunci privat belum dicuri. Ia membuktikan asal pesan tertentu, bukan kejujuran pengirim dalam segala hal. [1] [3]

Ketika server tidak menjawab, yang lain tidak tahu apakah ia berhenti atau koneksinya hanya sangat lambat. Hasil FLP, diterbitkan pada 1985 oleh Michael Fischer, Nancy Lynch, dan Michael Paterson, merumuskan ketidakpastian ini secara tepat. Proses di sini berarti program yang sedang berjalan. Prosedur deterministik mengambil langkah berikutnya yang sama untuk keadaan dan masukan yang sama, bukan memilihnya secara acak. Dalam sistem sepenuhnya asinkron tanpa batas atas penundaan yang diketahui, prosedur deterministik tidak dapat menjamin penyelesaian kesepakatan pada setiap eksekusi yang diizinkan apabila bahkan satu proses boleh berhenti karena gagal. Ini berlaku meski pengiriman andal tetapi penundaannya tidak dibatasi. Bukan berarti kesepakatan tidak pernah tercapai. Sistem praktis menambahkan asumsi waktu, pendeteksi kegagalan yang sesuai, atau keacakan. Saat jaringan terpisah, menunggu mungkin lebih aman daripada mengesahkan hasil yang bertentangan. [4] [13] [8]

Miguel Castro dan Barbara Liskov menjelaskan Practical Byzantine Fault Tolerance, PBFT, pada 1999 untuk layanan pada beberapa replika yang dikenal. Replika adalah salinan layanan yang berjalan di server berbeda dan terus memproses permintaan yang sama. Ini bukan berkas cadangan yang disimpan untuk dipakai nanti. Konfigurasi dasar n = 3f+1 menoleransi f replika gagal. Dari empat server, satu dapat bersifat Bizantium; dua kelompok berisi tiga server beririsan pada setidaknya dua server, dan minimal satu pasti dapat diandalkan. Kumpulan persetujuan yang diperlukan disebut kuorum. Irisan saja tidak cukup: aturan fase dan pergantian pemimpin juga menentukan. Secara lebih rinci, keadaan prepared membutuhkan permintaan, pesan pre-prepare, dan 2f pesan prepare yang cocok dari replika berbeda selain replika utama. Pengesahan lokal juga memerlukan 2f+1 pesan commit, mungkin termasuk miliknya sendiri. Autentikasi, nomor urut, dan titik pemeriksaan menangani pemalsuan, pengulangan, dan pertumbuhan log tanpa batas. Keselamatan tidak bergantung pada batas waktu, tetapi kemajuan memerlukan syarat tambahan tentang penundaan. [5] [10] [11] [12]

Bitcoin tidak memiliki daftar server tertutup yang ditetapkan sebelumnya. Jika setiap akun baru mendapat satu suara, penyerang dapat menciptakan mayoritas: inilah Sybil Attack. Karena itu Proof of Work mengaitkan pembuatan blok dengan kerja komputasi. Blok adalah sekumpulan transaksi yang ditambahkan ke riwayat bersama. Full Node, komputer yang menjalankan perangkat lunak untuk memeriksa aturan secara mandiri, terlebih dahulu menolak blok tak sah lalu mengikuti cabang sah dengan kerja terkumpul terbesar. Bitcoin tidak menjalankan OM atau PBFT; percabangan sementara merupakan bagian operasinya. Dengan porsi daya jujur yang memadai dan kondisi komunikasi yang sesuai, konfirmasi tambahan menurunkan risiko penulisan ulang sejarah, tetapi tidak memberi ketidakberubahan mutlak. Penelitian Bitcoin Backbone memeriksa syarat-syarat ini: keselarasan riwayat, pertumbuhan rantai, dan porsi blok yang dapat dibuat peserta jujur. [6] [7]

Saat mendengar ‘jaringan mencapai konsensus’, cari jawaban konkret: siapa boleh ikut, apa yang dapat dikuasai penyerang, berapa lama pesan boleh tertunda, dan kapan keputusan bisa berubah? Proof of Work pun tidak menghapus semua masalah. Eclipse Attack mengisolasi simpul dari rekan jujur, penyensoran mengecualikan transaksi, dan Selfish Mining melibatkan penahanan blok yang telah ditambang. Kesalahan perangkat lunak serta kemungkinan menulis ulang sebagian riwayat dengan kekuatan serangan yang cukup tetap ada. Namun mayoritas daya komputasi pun tidak dapat memaksa Full Node yang berfungsi benar menerima blok yang melanggar aturannya. Kisah para jenderal mengajarkan kita memeriksa syarat kesepakatan, bukan hanya mempercayai nama teknologi. [6] [7] [8]