Byzantium, ibu kota Kekaisaran Romawi Timur kuno, pernah menjadi salah satu kota terkuat dan paling kaya di dunia. Namun, karena wilayahnya yang luas, Byzantium sering menghadapi invasi eksternal dan pemberontakan internal. Untuk mempertahankan perbatasannya, Byzantium mengirimkan beberapa pasukan, masing-masing diperintah oleh jenderal yang berbeda. Mencapai konsensus di antara para jenderal ini menjadi tantangan yang signifikan.
Masalah Jenderal Byzantium memiliki hubungan dekat dengan blockchain. Jaringan blockchain adalah jaringan terdistribusi di mana node, seperti jenderal Byzantium, harus mencapai konsensus tentang transaksi dan data dalam lingkungan jaringan yang tidak dapat diandalkan.

Masalah Dua Jenderal

Masalah Dua Jenderal adalah kasus khusus dari Masalah Jenderal Byzantine. Masalah ini dan bukti ketidakdapatannya pertama kali diusulkan oleh E.A. Akkoyunlu, K.Ekanadham, dan R.V. Huber dalam makalah mereka tahun 1975 “Some Constraints and Trade-offs In The Design of Network Communications.” Pada tahun 1978, Jim Gray secara resmi menamai masalah ini sebagai “Masalah Dua Jenderal” dalam bukunya “Notes on Data Base Operating Systems.” Awalnya, masalah ini digunakan untuk menganalisis masalah mencapai konsensus melalui komunikasi melalui tautan komunikasi yang tidak dapat diandalkan. Sekarang ini biasanya digunakan untuk mengilustrasikan masalah konsistensi dan konsensus dalam sistem terdistribusi.

Definisi Masalah:
Dua pasukan negara A, masing-masing dipimpin oleh seorang jenderal, bersiap untuk menyerang pasukan negara B. Pasukan negara B dikelilingi di lembah, dengan dua pasukan A yang ditempatkan di bukit di kedua sisi lembah. Namun, satu-satunya jalan di antara dua pasukan A melewati lembah. Pasukan B lebih kuat daripada masing-masing pasukan A, tetapi jika kedua pasukan A menyerang bersama, mereka dapat mengalahkan pasukan B.
Masalah: Bisakah sebuah algoritma dirancang yang memungkinkan dua jenderal pasukan A untuk setuju untuk menyerang secara bersamaan? Algoritma tersebut mungkin melibatkan pengiriman dan penerimaan pesan.
Solusi: Masalah Dua Jenderal klasik tidak dapat diselesaikan. Tidak ada protokol yang dapat menjamin dua pasukan dari A akan berhasil mengkoordinasikan serangan mereka. Namun, dalam sistem praktis, masalah dapat diatasi dengan cukup dapat diandalkan, seperti dengan mekanisme 'tiga jalan salaman' dalam protokol TCP.

Byzantine Generals Problem

Masalah Jenderal Byzantium pertama kali diusulkan oleh Leslie Lamport, pemenang Penghargaan Turing 2013, dalam makalahnya tahun 1982 “The Byzantine Generals Problem.” Masalah ini menggambarkan bagaimana mencapai konsistensi dalam sistem terdistribusi dalam kehadiran perilaku jahat, seperti penyusupan pesan.
Beberapa pasukan Kekaisaran Byzantium mengepung sebuah kota musuh, masing-masing dipimpin oleh seorang jenderal. Pasukan Byzantium hanya dapat berkomunikasi melalui utusan. Setelah mengamati kekuatan musuh, para jenderal Byzantium harus mencapai kesimpulan yang sama: hanya jika lebih dari setengah pasukan Byzantium menyerang bersama-sama dapat mereka menaklukkan kota dan mencapai kemenangan.

Solusi: Jika jumlah jenderal (node) dalam sistem Byzantine adalah Z dan jumlah jenderal yang tidak dapat diandalkan (pengkhianat) adalah X, maka hanya ketika Z ≥ 3X + 1, protokol Toleransi Kesalahan Byzantine (BFT) dapat menjamin konsistensi sistem.
Dalam sistem praktis, kegagalan yang menyebabkan node menjadi tidak responsif diklasifikasikan sebagai "Fault Crash," sementara node yang memalsukan atau merusak pesan diklasifikasikan sebagai "Fault Byzantine."

Klasifikasi Algoritma Konsensus

Sistem blockchain adalah jenis sistem terdistribusi, terutama rantai publik seperti Bitcoin dan Ethereum, yang terdiri dari banyak node jaringan yang sangat terdesentralisasi dan saling tidak percaya. Mekanisme konsensus blockchain memastikan bahwa sistem blockchain secara konsisten mencapai konsistensi data tanpa fork.
Berdasarkan jenis ketahanan kesalahan, algoritma konsensus dapat diklasifikasikan menjadi algoritma Non-Byzantine Fault Tolerance (CFT) dan algoritma Byzantine Fault Tolerance (BFT).

Algoritma Toleransi Kesalahan Non-Byzantine

Dalam sistem terdistribusi, algoritma Toleransi Kesalahan Non-Byzantine memastikan kehandalan seluruh sistem terdistribusi ketika node mengalami kegagalan sistem atau gangguan tidak terencana (kesalahan non-Byzantine). Namun, ketika node jahat memalsukan atau merusak data, algoritma Toleransi Kesalahan Non-Byzantine tidak dapat menjamin kehandalan sistem. Algoritma-algoritma ini terutama digunakan dalam sistem terdistribusi perusahaan yang tertutup dan terkendali. Algoritma Toleransi Kesalahan Non-Byzantine yang paling representatif termasuk algoritma Paxos dan algoritma Raft.

Algoritma Toleransi Kesalahan Byzantine

Algoritma Toleransi Kesalahan Byzantine memungkinkan sistem terdistribusi untuk memastikan kehandalan bahkan jika node mengalami jenis kesalahan apa pun, selama jumlah node yang rusak tidak melebihi proporsi tertentu. Secara sederhana, selama jumlah node yang rusak (karena kesalahan non-Byzantine atau Byzantine) kurang dari proporsi tertentu dari total node, algoritma Toleransi Kesalahan Byzantine dapat menjamin kehandalan sistem. Karena adanya banyak node jaringan yang tidak terpercaya dalam sistem blockchain seperti Bitcoin dan Ethereum, algoritma Toleransi Kesalahan Byzantine terutama digunakan dalam mekanisme konsensus blockchain. Algoritma Toleransi Kesalahan Byzantine yang paling representatif termasuk PBFT (Practical Byzantine Fault Tolerance), PoW (Proof of Work), dan PoS (Proof of Stake).