Protokol konsensus Stellar pertama kali dijelaskan dalam artikel ilmiah 2015 oleh David Mazier. Ini adalah "sistem federal perjanjian Bizantium", yang memungkinkan jaringan komputasi terdesentralisasi tanpa pemimpin untuk secara efektif mencapai konsensus tentang keputusan apa pun. Jaringan penagihan Stellar menggunakan Stellar Consensus Protocol (SCP) untuk menjaga riwayat transaksi yang konsisten yang dilihat semua anggota.

Protokol konsensus dianggap sulit dipahami. SCP lebih sederhana daripada kebanyakan dari mereka, tetapi masih berbagi reputasi ini - sebagian karena gagasan keliru bahwa "suara federal," yang mana bagian pertama dari artikel ilmiah dikhususkan, adalah SCP. Tapi ini tidak benar! Ini hanya blok bangunan penting, yang pada paruh kedua artikel digunakan untuk membuat protokol konsensus Stellar yang sebenarnya .

Dalam artikel ini, kami menjelaskan secara singkat apa itu "sistem perjanjian", apa yang bisa membuatnya "Bizantium," dan mengapa membuat sistem Bizantium "federal." Kemudian kami menjelaskan prosedur pemberian suara gabungan yang dijelaskan dalam artikel SCP, dan akhirnya menjelaskan protokol SCP itu sendiri.

Sistem perjanjian

Sistem perjanjian memungkinkan sekelompok peserta untuk mencapai konsensus tentang suatu topik, misalnya, apa yang harus dipesan untuk makan siang.

Kami di Interstellar telah menerapkan sistem pengaturan makan kami sendiri: kami memesan apa yang dikatakan manajer operasi kami John. Ini adalah sistem perjanjian yang sederhana dan efektif. Kita semua percaya kepada John dan percaya bahwa setiap hari dia akan menemukan sesuatu yang menarik dan bergizi.

Tetapi bagaimana jika John menyalahgunakan kepercayaan kita? Dia dapat memutuskan sendiri bahwa kita semua harus menjadi vegan. Dalam satu atau dua minggu, kita mungkin akan menggulingkannya dan menyerahkan wewenang kepada Elizabeth. Tapi tiba-tiba dia menyukai alpukat dengan ikan teri dan berpikir bahwa semua orang harus menjadi seperti itu. Kekuasaan rusak. Oleh karena itu, lebih baik untuk menemukan beberapa metode yang lebih demokratis: beberapa cara untuk memastikan bahwa preferensi yang berbeda dipertimbangkan, sambil memastikan hasil yang tepat waktu dan tidak ambigu sehingga tidak ada yang memesan makan siang atau lima orang melakukan pesanan yang berbeda, atau diskusi berlangsung hingga malam hari.

Tampaknya solusinya sederhana: untuk memilih! Tapi ini kesan yang menyesatkan. Siapa yang akan mengumpulkan surat suara dan melaporkan hasilnya? Dan mengapa sisanya harus percaya dengan apa yang dia katakan? Mungkin kita pertama - tama dapat memilih pemimpin yang kita percayai untuk memimpin pemilihan - tetapi siapa yang akan memimpin pemilihan pertama ini? Bagaimana jika kita tidak bisa menyetujui seorang pemimpin? Atau jika kita setuju, dan pemimpin ini terjebak dalam rapat atau cuti sakit?

Masalah serupa ditemukan di jaringan komputer terdistribusi. Semua peserta atau node harus menyetujui beberapa solusi, misalnya, yang giliran untuk memperbarui file bersama atau mengambil tugas dari antrian pemrosesan. Dalam jaringan cryptocurrency, node berulang kali harus memilih bagaimana cerita lengkap terlihat dari beberapa versi yang mungkin terkadang bertentangan. Perjanjian jaringan ini memberi penerima jaminan bahwa koin itu (a) valid (bukan palsu) dan (b) belum dihabiskan di tempat lain. Ini juga memastikan bahwa dia dapat menghabiskan koin di masa depan karena penerima baru akan memiliki jaminan yang sama untuk alasan yang sama.

Setiap sistem yang cocok dalam jaringan komputer terdistribusi harus toleran terhadap kesalahan: ia harus memberikan hasil yang konsisten, terlepas dari kesalahan, seperti jalur komunikasi yang lambat, node yang tidak responsif, dan urutan pesan yang salah. Sistem perjanjian Bizantium juga tahan terhadap kesalahan "Bizantium": node yang memberikan informasi palsu, apakah karena kesalahan atau dalam upaya yang disengaja untuk merusak sistem atau mendapatkan beberapa keuntungan. Ketahanan "Bizantium" - kemampuan untuk mempercayai keputusan kelompok, bahkan ketika beberapa anggota kelompok mungkin berbohong atau tidak mengikuti aturan pengambilan keputusan - disebut perumpamaan para jenderal Kekaisaran Bizantium yang mencoba mengoordinasikan serangan. Anthony Stevens memiliki deskripsi yang bagus .

Pertimbangkan pemilik koin crypto Alice, yang harus memilih antara membeli es krim lezat dari Bob dan membayar hutang Carol. Mungkin Alice ingin membayar keduanya sekaligus, dengan curang membelanjakan koin yang sama. Untuk melakukan ini, ia harus meyakinkan komputer Bob bahwa koin itu tidak pernah dibayarkan kepada Carol, dan meyakinkan komputer Carol bahwa koin itu tidak pernah dibayarkan kepada Bob. Sistem konvensi Bizantium membuat ini hampir tidak mungkin menggunakan bentuk aturan mayoritas yang disebut kuorum . Suatu simpul dalam jaringan semacam itu menolak untuk beralih ke versi sejarah tertentu sampai ia melihat bahwa jumlah yang cukup dari rekan-rekan node - suatu kuorum - menyetujui transisi semacam itu. Begitu ini terjadi, mereka akan membentuk blok pemilihan yang cukup besar untuk memaksa node jaringan yang tersisa untuk setuju dengan keputusan mereka. Alice mungkin membuat beberapa node berbohong atas namanya, tetapi jika jaringannya cukup besar, maka upayanya akan ditekan oleh suara-suara dari node yang jujur.

Berapa simpul yang diperlukan untuk kuorum? Minimal, mayoritas, atau lebih tepatnya, mayoritas yang memenuhi syarat, untuk memerangi kesalahan dan penipuan. Tetapi untuk menghitung mayoritas, Anda perlu mengetahui jumlah total peserta. Di kantor Interstellar atau di pemilihan distrik, angka-angka ini mudah dikenali. Tetapi jika grup Anda adalah jaringan yang tidak didefinisikan dengan baik di mana node dapat masuk dan keluar seperti yang diinginkan tanpa koordinasi dengan pusat, maka Anda memerlukan sistem perjanjian Bizantium federal yang dapat menentukan kuorum bukan dari daftar node yang telah ditentukan, tetapi secara dinamis, dari yang terus berubah dan pasti tidak lengkap snapshot node pada titik waktu tertentu.

Tampaknya tidak mungkin untuk membuat kuorum dalam hal satu simpul dalam jaringan yang luas, tetapi itu mungkin. Kuorum semacam itu bahkan dapat menjamin hasil pemungutan suara terdesentralisasi. Buku putih SCP menunjukkan bagaimana melakukan ini menggunakan prosedur yang disebut pemilihan gabungan .

Untuk yang tidak sabar

Sisa artikel merinci pemungutan suara federal dan protokol konsensus Stellar. Jika Anda tidak tertarik dengan detailnya, berikut adalah gambaran umum prosesnya.

1. Node melakukan putaran pemungutan suara federal pada "nominasi". Putaran pemungutan suara federal berarti:
   
   • Node memilih pernyataan apa pun, misalnya, "Saya mengusulkan nilai V";
     
   • Node mendengarkan suara-suara pesta sampai menemukan yang bisa "menerima";
     
   • Node sedang mencari "kuorum" untuk pernyataan ini. Kuorum “menegaskan” calon tersebut.
2. Segera setelah sebuah simpul dapat mengkonfirmasi satu atau lebih calon, ia mencoba untuk "menyiapkan" sebuah "surat suara" melalui beberapa putaran pemungutan suara federal.
   
3. Segera setelah simpul tersebut dapat memverifikasi kesiapan surat suara, ia mencoba memberi makan dengan lebih banyak putaran pemberian suara gabungan.
   
4. Setelah situs dapat mengkonfirmasi komitmen buletin, ia dapat “mengeksternalkan” nilai buletin ini, menggunakannya sebagai hasil konsensus.

Langkah-langkah ini mencakup beberapa putaran pemungutan suara gabungan, yang bersama-sama membentuk satu putaran SCP. Kami akan memeriksa secara lebih rinci apa yang terjadi pada setiap langkah.

Pemungutan suara gabungan

Pemungutan suara Federasi adalah proses menentukan apakah suatu jaringan dapat menyetujui suatu proposal. Dalam putaran pemungutan suara, setiap node harus memilih salah satu dari nilai yang berpotensi banyak kemungkinan. Dia tidak dapat melakukan ini sampai dia yakin bahwa node lain di jaringan tidak akan memilih hasil yang berbeda. Untuk memastikan hal ini, node bertukar kebingungan pesan bolak-balik sehingga semua orang mengkonfirmasi bahwa kuorum node membuat keputusan yang sama. Sisa dari bagian ini menjelaskan istilah-istilah dalam kalimat ini dan bagaimana keseluruhan prosedur berjalan.

Kuorum dan Irisan Kuorum

Mari kita mulai dengan mendefinisikan kuorum. Seperti yang kita diskusikan di atas, dalam jaringan terdesentralisasi dengan keanggotaan dinamis, tidak mungkin untuk mengetahui terlebih dahulu jumlah node dan, oleh karena itu, berapa yang paling dibutuhkan. Pemungutan suara Federated memecahkan masalah ini dengan memperkenalkan ide baru untuk kuorum slice: satu set kecil node peer yang dipercaya oleh node untuk mengirimkan informasi status voting di seluruh jaringan. Setiap node mendefinisikan irisan kuorumnya sendiri (yang sebenarnya menjadi anggota).

Pembentukan kuorum dimulai dengan potongan kuorum. Untuk setiap node, node dari slice-nya ditambahkan. Kemudian, anggota alat pengiris dari node-node ini ditambahkan , dan seterusnya. Saat Anda melanjutkan, semakin banyak node menemukan bahwa Anda tidak dapat menambahkan, karena mereka sudah termasuk dalam slice. Ketika tidak ada lagi node baru untuk ditambahkan, proses berhenti: kami membentuk kuorum dengan "penutupan transitif" dengan memotong kuorum dari simpul awal.


Untuk menemukan kuorum dari simpul ini ...


... tambahkan anggota ke slice-nya ...


... lalu tambahkan anggota alat pengiris ke simpul-simpul ini.


Lanjutkan sampai tidak ada simpul untuk ditambahkan.




Tidak ada simpul untuk ditambahkan ke kiri. Ini adalah kuorum.

Bahkan, setiap node dapat masuk ke lebih dari satu slice. Untuk membentuk kuorum, pilih hanya satu dari irisan dan tambahkan anggota; kemudian pilih potongan apa pun untuk setiap anggota dan tambahkan anggota ke potongan itu dan seterusnya. Ini berarti bahwa setiap simpul adalah anggota dari banyak kuorum yang mungkin.


Pilih hanya satu irisan kuorum di setiap langkah.






Satu kuorum yang mungkin. Atau alternatif ...


... pilih irisan lain ...




... (bila mungkin) ...


... menciptakan kuorum lain.

Bagaimana cara sebuah node mengetahui irisan apa yang dimiliki node lain? Dengan cara yang sama seperti informasi lainnya tentang node lain: dari transmisi yang disiarkan setiap node ke jaringan ketika status pemilihannya berubah. Setiap siaran menyertakan informasi tentang irisan node pengirim. Dokumen teknis SCP tidak menentukan mekanisme komunikasi. Implementasi biasanya menggunakan protokol gosip untuk menjamin pesan siaran di seluruh jaringan.

Ingatlah bahwa dalam sistem perjanjian Bizantium non-federal, kuorum didefinisikan sebagai mayoritas dari semua simpul. Sistem perjanjian Bizantium dikembangkan dari sudut pandang pertanyaan: berapa banyak node yang tidak jujur ​​yang dapat ditahan oleh sistem? Dalam sistem N node yang dirancang untuk bertahan dengan kegagalan (trik), node harus dapat membuat kemajuan dengan menerima respons dari N - f rekan, karena f dari mereka mungkin tidak berfungsi. Tetapi setelah menerima respons dari N - f rekan, kita dapat mengasumsikan bahwa semua f rekan (dari mana node tidak menerima respons) sebenarnya jujur. Jadi, f dari N - f rekan (dari mana respons diterima) berbahaya. Agar node mencapai konsensus yang sama, mayoritas node yang tersisa harus jujur, yaitu, kita perlu N - f lebih besar dari 2f atau N> 3f. Jadi biasanya sistem yang dirancang untuk bertahan dari kegagalan akan memiliki total N = 3f + 1 node dan ukuran kuorum 2f + 1. Segera setelah proposal melewati ambang kuorum, seluruh jaringan yakin bahwa setiap proposal yang bersaing akan gagal. Jadi jaringan bertemu dengan hasilnya.

Tetapi dalam sistem perjanjian Bizantium federal, tidak hanya tidak mungkin ada mayoritas (karena tidak ada yang tahu ukuran keseluruhan jaringan), tetapi konsep mayoritas umumnya tidak berguna! Jika keanggotaan dalam sistem terbuka, maka seseorang dapat memperoleh mayoritas dengan hanya melakukan apa yang disebut serangan Sibyl: dengan berulang kali bergabung dengan jaringan melalui beberapa node. Jadi mengapa penutupan transitif dari sepotong dapat disebut kuorum , dan bagaimana hal itu dapat menekan penawaran yang bersaing?

Secara teknis, tidak mungkin! Bayangkan sebuah jaringan enam simpul, di mana dua tiga kali lipat diisolasi dalam kuorum satu sama lain. Subkelompok pertama dapat membuat keputusan yang tidak akan pernah didengar oleh yang kedua, dan sebaliknya. Tidak ada cara bagi jaringan ini untuk mencapai konsensus (kecuali secara kebetulan).

Oleh karena itu, SCP mensyaratkan bahwa jaringan harus memiliki properti yang disebut quorum crossing untuk pemungutan suara gabungan (dan untuk menerapkan teorema artikel penting). Pada jaringan dengan properti ini, dua kuorum apa pun yang dapat dibangun selalu tumpang tindih di setidaknya satu simpul. Untuk menentukan suasana jaringan yang berlaku sama baiknya dengan memiliki mayoritas. Secara intuitif, ini berarti bahwa jika kuorum setuju dengan pernyataan X, tidak ada kuorum lain yang dapat setuju dengan sesuatu yang lain, karena kuorum tersebut harus mencakup beberapa simpul dari kuorum pertama yang telah memilih X.


Jika jaringan memiliki persimpangan kuorum ...


... lalu dua kuorum yang dapat Anda bangun ...


... akan selalu berpotongan.





(Tentu saja, node yang tumpang tindih dapat berubah menjadi Bizantium-berbohong atau sebaliknya buruk. Dalam hal ini, kuorum yang berpotongan tidak membantu jaringan sama sekali. Untuk alasan ini, banyak hasil dalam makalah teknis SCP didasarkan pada asumsi eksplisit, seperti apa yang tersisa di jaringan persimpangan kuorum bahkan setelah penghapusan node yang buruk .Untuk kesederhanaan, kita membiarkan asumsi ini tersirat dalam sisa artikel).

Kelihatannya tidak masuk akal untuk berharap bahwa dalam jaringan node independen persimpangan Kuorum yang andal adalah mungkin. Tetapi ada dua alasan mengapa demikian.

Alasan pertama adalah keberadaan Internet itu sendiri. Internet adalah contoh ideal dari jaringan node independen dengan persimpangan kuorum. Sebagian besar situs di Internet terhubung hanya dengan beberapa situs lokal lainnya, tetapi set kecil ini cukup tumpang tindih untuk membuat setiap situs dapat diakses dari setiap situs lain pada rute tertentu.

Alasan kedua khusus untuk jaringan pembayaran Stellar (penggunaan SCP paling umum). Setiap aset dalam jaringan Stellar memiliki penerbit, dan rekomendasi Stellar mengharuskan setiap penerbit menunjuk satu atau lebih simpul dalam jaringan untuk memproses permintaan pembayaran kembali. Adalah kepentingan Anda untuk secara langsung atau tidak langsung memasukkan simpul-simpul ini dalam irisan kuorum untuk setiap aset yang Anda minati. Maka kuorum untuk semua simpul yang tertarik pada aset ini akan tumpang tindih setidaknya dalam simpul pembayaran ini. Node yang tertarik pada beberapa aset akan termasuk dalam kuorum irisan semua node pembayaran dari masing-masing emiten, dan mereka akan berusaha untuk menggabungkan semua aset bersama-sama. Selain itu, setiap aset yang tidak terhubung sedemikian rupa dengan orang lain di jaringan dan tidak boleh terhubung - ini dimaksudkan agar tidak ada kuorum yang melintasi untuk jaringan ini (misalnya, bank dari zona dolar terkadang ingin berdagang dengan bank dari zona euro dan bank dari zona peso, jadi mereka berada di jaringan yang sama, tetapi tidak ada yang peduli tentang jaringan terpisah anak-anak yang menjual kartu baseball).

Tentu saja, menunggu persimpangan kuorum bukan jaminan . Sistem perjanjian Bizantium lainnya berutang banyak kompleksitas mereka untuk menjamin kuorum. Inovasi penting SCP adalah menghilangkan tanggung jawab untuk membuat kuorum dari algoritma konsensus itu sendiri dan membawanya ke tingkat aplikasi. Dengan demikian, meskipun pemungutan suara gabungan cukup umum untuk pemungutan suara tentang masalah apa pun, pada kenyataannya keandalannya tergantung pada makna yang lebih luas dari nilai-nilai ini. Beberapa penggunaan hipotesis mungkin tidak nyaman untuk membangun jaringan yang terhubung dengan baik seperti yang lain.

Voting, penerimaan dan konfirmasi

Dalam putaran pemungutan suara gabungan, simpul secara opsional mulai memilih beberapa nilai V. Ini berarti pesan dikirim ke jaringan: "Saya simpul N, irisan kuorum saya adalah Q, dan saya memilih V". Ketika sebuah node memilih dengan cara ini, dia berjanji bahwa dia tidak pernah memilih melawan V dan tidak akan pernah.

Dalam siaran dari node peer-to-peer, setiap node melihat bagaimana orang lain memilih. Segera setelah simpul mengumpulkan cukup banyak pesan seperti itu, ia dapat melacak irisan kuorum dan mencoba menemukan kuorum. Jika dia melihat kuorum rekan yang juga memilih V, maka dia dapat melanjutkan untuk menerima V dan menyiarkan pesan baru ini ke jaringan: "Saya adalah simpul N, irisan saya adalah kuorum Q, dan saya menerima V". Penerimaan memberikan jaminan yang lebih kuat dari pada pemungutan suara sederhana. Ketika sebuah node memberikan suara untuk V, itu tidak akan pernah bisa memilih opsi lain. Tetapi jika sebuah simpul menerima V, tidak ada simpul di Web yang akan menerima opsi lain (Teorema 8 dalam kertas putih teknis SCP membuktikan ini).

Tentu saja, sangat mungkin bahwa tidak akan segera ada kuorum node yang setuju dengan V. node lain dapat memilih nilai-nilai lain. Tetapi untuk situs ada cara lain untuk beralih dari pemungutan suara sederhana ke penerimaan. N dapat mengambil nilai W yang berbeda, bahkan jika itu tidak memilihnya, dan bahkan jika itu tidak melihat kuorum untuk itu. Untuk memutuskan untuk mengubah suara Anda, cukup untuk melihat sekumpulan node pemblokiran yang telah menerima W. Satu set pemblokiran adalah satu node di setiap irisan kuorum N. Seperti namanya, ia dapat memblokir nilai lainnya. Jika semua node dalam himpunan seperti mengambil W, maka (dengan Teorema 8) tidak akan mungkin untuk membentuk kuorum dengan asumsi nilai yang berbeda, dan karena itu juga aman untuk menerima W.


Simpul N dengan tiga irisan kuorum.


BDF adalah set pemblokiran untuk N: itu termasuk satu simpul dari setiap irisan N.


BE N, E N.

— . N, , N. — . N , , . , , SCP ( 11), , N .


.

Proses pemungutan suara, penerimaan dan konfirmasi adalah satu putaran penuh pemungutan suara gabungan. Protokol Konsensus Stellar menyatukan banyak babak ini untuk menciptakan sistem konsensus yang lengkap.

Protokol Konsensus Stellar

Dua fitur terpenting dari sistem konsensus adalah keselamatan dan kemampuan bertahan . Algoritma konsensus adalah "aman" jika tidak pernah dapat memberikan hasil yang berbeda kepada peserta yang berbeda (salinan cerita Bob tidak akan pernah bertentangan dengan Carol). "Vitalitas" berarti algoritme akan selalu membuahkan hasil, artinya, ia tidak akan macet.

Prosedur pemungutan suara yang dijelaskan di atas aman dalam arti bahwa jika sebuah simpul mengonfirmasi nilai V, tidak ada simpul lain yang mengonfirmasi nilai lainnya. Tetapi “tidak mengkonfirmasi arti lain” - ini tidak berarti bahwa ia perlu mengkonfirmasi sesuatu. Peserta dapat memilih begitu banyak nilai yang berbeda sehingga tidak ada yang mencapai ambang penerimaan. Ini berarti bahwa tidak ada suara federal. .

Stellar , , . ( SCP . , , , ). , , , SCP, .

, SCP , , - , , , . .

(nomination phase), « V», , V. — , .

SCP , , (mis. sebuah wadah untuk nilai yang diusulkan) dan kuorum yang dapat mendeklarasikan komit untuknya (komit). Jika kuorum melakukan pemungutan suara, nilainya diambil sebagai konsensus. Tetapi sebelum simpul dapat memilih komit suara, ia harus terlebih dahulu mengkonfirmasi pembatalan semua surat suara dengan nilai penghitung yang lebih rendah. Langkah-langkah ini - membatalkan surat suara untuk menemukan satu yang dapat Anda konfirmasi komitnya - mencakup beberapa putaran pemberian suara gabungan pada beberapa pernyataan surat suara.

Bagian berikut menjelaskan secara lebih rinci pencalonan dan pemungutan suara.

Nominasi

Pada awal tahap nominasi, setiap node dapat secara spontan memilih nilai V dan memilih pernyataan "Saya mencalonkan V". Tujuan pada tahap ini adalah untuk mengkonfirmasi pencalonan nilai tertentu melalui pemungutan suara federal.

, , . , «» . (echo) , V, , W, V, W. ( , . SCP . , «» , . , , , . , , ).

V, W — , . SCP .

V — V, — SCP — , «». SCP , « X», « X», . , . , .


Menominasikan SCP menggunakan pemungutan suara gabungan. Mungkin ada banyak nilai "B" yang didorong oleh teman sebaya dan "tercermin" oleh rekan.

Nominasi kandidat dapat menghasilkan beberapa kandidat yang dikonfirmasi. Oleh karena itu, SCP membutuhkan lapisan aplikasi untuk menyediakan beberapa metode menggabungkan kandidat menjadi satu komposit. (composite). . , , . «» . ( : . , ). Stellar, , , , .

SCP ( 12), . : — ( SCP). , , , . , . , , , , .

. — . , (balloting).

— <counter,value>, counter — , 1, value — . , . , - - . , . <counter, value> , , <counter+1, value>.

(, : ), ( counter-value) . SCP , , :

• « B»
  
• « B»

Dari sudut pandang simpul ini, konsensus tercapai ketika menemukan Buletin B yang dapat dikonfirmasikan (yaitu, menemukan kuorum yang menerima) pernyataan "Saya menyatakan komit buletin B." Mulai sekarang, Anda dapat dengan aman bertindak berdasarkan nilai yang ditentukan dalam B - misalnya, pesan pesanan ini untuk makan siang. Ini disebut nilai eksternalisasi . Setelah penerimaan surat suara telah dikonfirmasi, node dapat yakin bahwa node lain telah mengeksternalisasi nilai yang sama atau pasti akan melakukan itu di masa depan.

Meskipun secara konseptual banyak suara gabungan diadakan pada aplikasi untuk banyak surat suara yang berbeda, mereka tidak bertukar banyak pesan karena setiap pesan merangkum sejumlah surat suara. Satu pesan, dengan demikian, mempromosikan keadaan banyak suara gabungan sekaligus, misalnya: "Saya menerima komisi pemungutan suara dalam rentang dari <min, V> hingga <max, V>".

Apa arti istilah "siap" dan "berkomitmen"?

Sebuah simpul memberikan suara untuk melakukan pemungutan suara ketika diyakinkan bahwa node lain tidak akan melakukan pemungutan suara dengan nilai yang berbeda. Meyakinkan ini adalah tujuan mempersiapkan pernyataan. Pemungutan suara yang mengatakan "Saya siap untuk melakukan buletin B" adalah janji untuk tidak pernah melakukan buletin kurang dari B, yaitu, dengan penghitung yang lebih rendah (SCP mensyaratkan bahwa nilai dalam buletin memiliki urutan tertentu. Dengan demikian, Buletin <N1, V1> kurang dari <N2, V2> jika N1 <N2, dan juga jika N1 = N2 dan V1 <V2). Surat suara yang lebih kecil ini "dibatalkan" selama pemungutan suara persiapan, sementara B dianggap "disiapkan".

Mengapa "Saya siap untuk melakukan buletin B" berarti "Saya berjanji untuk tidak melakukan pemungutan suara kurang dari B"? Karena SCP mendefinisikan abort sebagai kebalikan dari commit. Memilih persiapan surat suara juga menyiratkan pemilihan untuk membatalkan beberapa surat suara lainnya, dan, seperti yang kita bahas sebelumnya, memilih satu hal adalah janji untuk tidak pernah memilih menentangnya.

Sebelum menyiarkan komit, situs harus terlebih dahulu menemukan buletin, yang dapat dikonfirmasikan sebagai disiapkan. Dengan kata lain, dia memegang suara federal tentang "Saya siap berkomitmen untuk Bulletin B," mungkin untuk banyak surat suara yang berbeda, sampai dia menemukan satu yang menerima kuorum.

Dari mana surat suara untuk pemungutan suara berasal? Pertama, simpul menyiarkan persiapan pemungutan suara untuk <1, C>, di mana C adalah kandidat gabungan yang diproduksi pada tahap nominasi. Namun, bahkan setelah dimulainya persiapan pemungutan suara, nominasi dapat menyebabkan munculnya kandidat tambahan yang akan menjadi surat suara baru. Sementara itu, teman sebaya mungkin memiliki kandidat yang berbeda, dan mereka dapat membentuk set pemblokiran yang menerima “Saya siap untuk melakukan buletin B2”, yang akan meyakinkan simpul untuk menerimanya juga. Akhirnya, ada mekanisme batas waktu yang menghasilkan putaran baru pemungutan suara gabungan pada surat suara baru dengan penghitung lebih tinggi jika surat suara saat ini macet.

Segera setelah node menemukan Bulletin B, yang dapat dikonfirmasikannya sebagai siap, ia menyiarkan pesan baru, "Bulletin B Commit". Suara ini memberi tahu rekan-rekan bahwa simpul tidak akan pernah menyerah B. Faktanya, jika B adalah surat suara <N, C>, maka "Buletin Komit <N, C>" berarti persetujuan tanpa syarat untuk memilih kesiapan setiap surat suara dari <N, C> ke <∞, s>. Nilai tambahan ini membantu node lain untuk mengejar komit, jika masih dalam tahap awal protokol.

Pada tahap ini, perlu ditekankan sekali lagi bahwa ini adalah protokol asinkron. Hanya karena satu node mengirimkan suara untuk komit tidak berarti rekan-rekannya juga melakukannya. Beberapa dari mereka masih dapat memberikan suara pada aplikasi dalam persiapan untuk pemungutan suara, yang lain mungkin sudah mengeksternalisasi maknanya. SCP menjelaskan bagaimana sebuah simpul harus memproses setiap jenis pesan rekan terlepas dari fase-nya.

Jika pesan "Saya menyatakan komit <N, C>" tidak dapat diterima atau dikonfirmasi, yaitu, probabilitas penerimaan atau konfirmasi pesan <N + 1, C> atau <N + 2, C> - atau, dalam hal apa pun, buletin apa pun dengan nilai C, dan bukan yang lain, karena node sudah berjanji untuk tidak membatalkan <N, C>. Pada saat node menyiarkan suara untuk komit, itu akan menjadi C atau tidak sama sekali, tergantung pada sejauh mana konsensus berjalan. Namun, ini tidak cukup bagi node untuk mengeksternalkan C. Beberapa pesta Bizantium (kurang dari kuorum, berdasarkan asumsi kami tentang keamanan) mungkin terletak pada node. Menerima dan kemudian mengkonfirmasikan surat suara tertentu (atau kisaran surat suara) adalah apa yang memberi simpul kepercayaan diri untuk akhirnya mengeksternalisasi C.


SCP dijalankan melalui pemungutan suara gabungan. Tidak ditampilkan: kapan saja timer dapat bekerja, menambah penghitung dalam pemungutan suara (dan, mungkin, menghasilkan komposit baru dari kandidat yang dinominasikan tambahan).

Dan itu saja! Setelah jaringan mencapai konsensus, jaringan siap melakukannya berulang kali. Di jaringan penagihan Stellar, ini terjadi kira-kira setiap 5 detik: suatu prestasi yang membutuhkan keamanan dan kemampuan bertahan, dijamin oleh SCP.

SCP dapat mencapainya dengan mengandalkan beberapa putaran pemungutan suara gabungan. Pemungutan suara Federated dimungkinkan berkat konsep slice kuorum: set node peer yang setiap node memutuskan untuk percaya sebagai bagian dari kuorum (subyektif). Konfigurasi ini berarti Anda dapat mencapai konsensus bahkan di jaringan dengan keanggotaan terbuka dan penipuan Bizantium.

Bacaan lebih lanjut

• Dokumen teknis SCP asli dapat ditemukan di sini , dan inilah rancangan spesifikasi untuk implementasinya.
  
• Penulis asli protokol SCP, David Mazier, menyederhanakan (tetapi masih secara teknis) menjelaskannya di sini .
  
• Anda mungkin terkejut tidak menemukan istilah "penambangan" atau "bukti kerja" dalam artikel ini. SCP tidak menggunakan metode ini, tetapi beberapa algoritma konsensus lainnya melakukannya. Zane Witherspoon menulis ulasan yang dapat diakses tentang algoritma konsensus .
  
• Deskripsi langkah-demi-langkah dari jaringan sederhana yang mencapai konsensus dalam satu putaran penuh SCP.
  
• Untuk pembaca yang tertarik dengan implementasi SCP: lihat kode C ++ yang digunakan oleh jaringan pembayaran Stellar, atau kode Go yang saya tulis untuk pemahaman yang lebih baik tentang SCP.