Terjemahan artikel ini disiapkan khusus untuk siswa kursus
"Arsitek Beban Tinggi" , yang dimulai bulan ini.
Blockchain adalah sistem terdesentralisasi yang terdiri dari berbagai entitas yang beroperasi tergantung pada insentif mereka dan informasi yang mereka miliki.
Setiap kali transaksi baru disiarkan melalui jaringan, node dapat memasukkan transaksi ini dalam salinan buku besar mereka atau mengabaikannya. Ketika sebagian besar peserta jaringan memutuskan untuk menerima keadaan tertentu, konsensus tercapai.
Masalah mendasar dalam
komputasi terdistribusi dan
sistem multi-agen adalah untuk mencapai keandalan sistem secara keseluruhan di hadapan sejumlah proses tidak beroperasi.
Seringkali, ini mensyaratkan bahwa proses mengoordinasikan di antara mereka sendiri beberapa nilai yang akan dibutuhkan selama perhitungan.Proses-proses ini digambarkan sebagai konsensus.
- Apa yang terjadi ketika seorang peserta memutuskan untuk tidak mengikuti aturan dan campur tangan dalam keadaan buku besarnya?
- Apa yang terjadi ketika ada banyak peserta seperti itu dalam jaringan, tetapi tidak mayoritas?
Agar protokol konsensus aman, protokol harus toleran terhadap kesalahan.
Untuk memulainya, kita akan berbicara secara singkat tentang masalah dua jendral yang tak terpecahkan. Kemudian, pertimbangkan Masalah Jenderal Bizantium dan bahas toleransi kesalahan Bizantium dalam sistem terdistribusi dan terdesentralisasi. Dan pada akhirnya, mari kita bicara tentang bagaimana semua ini berhubungan dengan teknologi blockchain.
Tugas dua jenderal
Tugas ini
, pertama kali diterbitkan pada tahun 1975 dan dinamai pada tahun 1978, menggambarkan sebuah skenario di mana dua jenderal menyerang musuh bersama. Jenderal pertama dianggap sebagai pemimpin, dan yang kedua adalah pengikut. Tentara masing-masing jenderal saja tidak cukup untuk mengalahkan pasukan musuh, sehingga mereka perlu bekerja sama dan menyerang pada saat yang sama. Skenario ini terlihat sederhana, tetapi ada satu peringatan:
Agar mereka dapat berkomunikasi dan menyetujui suatu waktu, jenderal pertama harus mengirim utusan melalui kamp musuh, ia harus menyampaikan pesan dengan waktu dimulainya serangan ke jenderal kedua. Namun, kemungkinan utusan tersebut akan ditangkap oleh lawan, dan pesan tersebut tidak terkirim. Ini akan mengarah pada fakta bahwa tentara jenderal pertama akan melakukan serangan, dan yang kedua akan tetap di tempatnya.
Bahkan jika pesan pertama dikirim, jenderal kedua harus mengkonfirmasi (ACK (mengakui), perhatikan kesamaan dengan jabat tangan tiga arah dalam
TCP ) bahwa ia menerima pesan, jadi ia mengirim kembali kurir, sehingga mereproduksi skenario sebelumnya di mana kurir dapat ditangkap . Ini mengalir ke ACK tanpa akhir, dan karena ini, para jenderal tidak dapat mencapai kesepakatan.
Tidak ada cara untuk menjamin kondisi kedua, yaitu, bahwa masing-masing jenderal sepenuhnya yakin bahwa yang lain setuju dengan rencana serangan. Kedua jenderal akan selalu tidak tahu apakah utusan itu telah mencapai kawannya.
Terbukti bahwa tugas dua jenderal tidak dapat diselesaikan.
Tugas para Jenderal Bizantium
Digambarkan pada tahun 1982 oleh Lamport, Shostak dan Piz, versi masalah ini ternyata menjadi sorotan. Dia menggambarkan skenario yang sama, di mana alih-alih dua jenderal, lebih banyak jenderal harus menyetujui waktu serangan. Komplikasi tambahan adalah bahwa satu atau lebih jenderal dapat menjadi pengkhianat, yaitu, mereka dapat berbohong tentang niat mereka (misalnya, jenderal mengatakan bahwa ia setuju untuk menyerang pada pukul 09:00, tetapi tidak).
Paradigma pemimpin-pengikut yang dijelaskan dalam tugas dua jenderal diubah menjadi instalasi komandan-bawahan. Untuk mencapai konsensus di sini, komandan dan setiap bawahan harus menyetujui solusi yang sama (serangan atau mundur).
Terjemahan gambar:
Tugas para Jenderal Bizantium. Komandan jenderal harus mengirim pesanan kepada bawahan n-1-nya, sehingga:
- Semua jenderal bawahan yang setia mematuhi satu perintah.
- Jika komandan jenderal setia, maka semua bawahannya yang setia mematuhi perintahnya.
Selain poin kedua, fakta menarik harus ditunjukkan: jika komandan adalah pengkhianat, maka konsensus masih harus dicapai. Akibatnya, semua letnan memiliki suara terbanyak.
Algoritma konsensus dalam kasus ini didasarkan pada arti dari sebagian besar keputusan yang dilihat bawahan.
Teorema: Untuk setiap
m , algoritma
OM (m) mencapai konsensus dengan lebih dari
3 juta jenderal dan maksimum
m pengkhianat.
Ini berarti bahwa algoritma dapat mencapai konsensus sementara 2/3 dari peserta jujur. Jika pengkhianat lebih dari 1/3, konsensus tidak tercapai, pasukan tidak dapat mengoordinasikan serangan mereka, dan musuh menang.
Algoritma OM (0)
- Komandan mengirimkan nilainya kepada masing-masing bawahan.
- Setiap bawahan menggunakan nilai yang ia terima dari komandan, atau menggunakan nilai DELAY jika ia tidak menerima nilai apa pun.
Algoritma OM (m), m> 0
- Komandan mengirim dengan kepentingannya kepada masing-masing bawahan.
- Untuk setiap i, misalkan vi adalah nilai yang diterima bawahan ith dari komandan, atau nilai RESET akan digunakan jika bawahan tidak menerima nilai apa pun. Bawahan ke-i bertindak sebagai komandan dalam Algoritma OM (m-1) dan mengirimkan nilai ke masing-masing bawahan yang tersisa n-2.
- Untuk setiap i, asalkan ji itu, biarkan vj menjadi nilai yang diterima bawahan h dari bawahan j pada langkah (2) (menggunakan Algoritma OM (m-1)), atau menggunakan nilai PUTUSKAN jika tidak mengerti artinya. Budak ith menggunakan nilai mayoritas (v1, ..., vn-1).
Ketika m = 0 tidak ada pengkhianat, setiap bawahan mengikuti urutan. Untuk m> 0, setiap pilihan akhir dari bawahan berasal dari bagian utama pemilihan semua bawahan.Akan lebih jelas jika Anda melihat situasi dari sudut pandang bawahan kedua - biarkan C menjadi Panglima, dan L {i} adalah bawahan ke-i.
OM (1): Bawahan 3 adalah pengkhianat. Situasi dari sudut pandang bawahan kedua.Langkah-langkah:
- Komandan mengirimkan v ke semua bawahan.
- L1 mengirimkan L2 nilai v atau L3 mengirimkan L2 nilai x.
- L2 ← mayoritas (v, v, x) == v
Keputusan akhir dibuat dari mayoritas suara L1, L2 dan L3 dan sebagai hasilnya konsensus tercapai.
Penting untuk diingat bahwa tujuannya adalah bagi sebagian besar bawahan untuk memilih solusi yang sama, bukan yang spesifik.
Mari kita lihat kasus ketika komandan adalah pengkhianat.
OM (1): Komandan adalah pengkhianat.Langkah-langkah:
- Komandan mengirimkan L1, L2, L3 masing-masing nilai x, y, z;
- L1 mengirimkan nilai x ke budak L2, L3 | L2 mengirimkan L1, L3 nilai y | L3 mengirimkan L1, L2 nilai z;
- L1 ← mayoritas (x, y, z) | L2 ← sebagian besar (x, y, z) | L3 ← mayoritas (x, y, z)
Mereka semua memiliki nilai yang sama, sehingga tercapai konsensus. Perhatikan bahwa meskipun nilai x, y, z semuanya berbeda, nilai
mayoritas (x, y, z) adalah sama untuk ketiga bawahan. Jika x, y, z adalah pesanan yang sama sekali berbeda, kita dapat mengasumsikan bahwa mereka akan bertindak sesuai dengan rencana default - RESET.
Untuk melihat pendekatan praktis pada contoh yang lebih kompleks dengan 7 jenderal dan 3 pengkhianat, saya sarankan Anda membaca
artikel ini.
Toleransi kesalahan Bizantium
Toleransi kesalahan Bizantium adalah karakteristik yang mendefinisikan sistem yang memungkinkan kelas kegagalan yang termasuk dalam Tugas Jenderal Bizantium. Kegagalan Bizantium adalah kelas
jenis kegagalan yang paling kompleks. Itu tidak menyiratkan pembatasan dan tidak membuat asumsi tentang perilaku seperti apa yang bisa dimiliki suatu simpul (misalnya, sebuah simpul dapat menghasilkan data apa pun yang sewenang-wenang, menyamar sebagai peserta yang jujur).
Kesalahan Bizantium adalah yang paling sulit untuk diperbaiki. Toleransi kesalahan Bizantium diperlukan dalam sistem mesin pesawat terbang, di pembangkit listrik tenaga nuklir, dan di hampir semua sistem yang tindakannya bergantung pada hasil sejumlah besar sensor. Bahkan SpaceX melihatnya sebagai
persyaratan potensial untuk sistemnya.
Algoritma yang disebutkan di bagian sebelumnya sesuai dengan toleransi kesalahan Bizantium sampai jumlah pengkhianat melebihi sepertiga dari semua jenderal. Ada opsi lain untuk memfasilitasi tugas ini, termasuk penggunaan tanda tangan digital atau pengenalan pembatasan komunikasi antar teman.
Bagaimana semua ini berhubungan dengan blockchain?
Blockchain adalah buku besar yang terdesentralisasi yang, menurut definisi, tidak dikendalikan oleh otoritas pusat. Karena nilai yang tersimpan di dalamnya, penyerang memiliki insentif ekonomi yang baik untuk mencoba dan melakukan kesalahan. Namun demikian, toleransi kesalahan Bizantium dan, oleh karena itu, solusi dari masalah umum Bizantium untuk blockchain sangat diperlukan.
Dengan tidak adanya Toleransi Kesalahan Bizantium, rekan dapat mengirimkan dan mempublikasikan transaksi palsu, benar-benar membatalkan keandalan blockchain. Untuk memperburuk keadaan, tidak ada otoritas pusat yang dapat mengambil tanggung jawab dan memperbaiki kerusakan.
Ketika
Bitcoin ditemukan, terobosan besar adalah penggunaan bukti
dari solusi probabilistik dari masalah Jenderal Bizantium. Sudah dijelaskan secara rinci oleh Satoshi Nakamoto di
email ini.
Kesimpulan
Dalam artikel ini, kami menguji beberapa konsep dasar konsensus dalam sistem terdistribusi.