Protokol konsensus Stellar pertama kali diterangkan dalam artikel ilmiah David Mazier pada tahun 2015. Ini ialah "sistem perjanjian Byzantine persekutuan" yang membolehkan rangkaian pengkomputeran tanpa pemimpin dan terdesentralisasi mencapai kata sepakat dengan cekap dalam sesuatu keputusan. Rangkaian pembayaran Stellar menggunakan Protokol Konsensus Stellar (SCP) untuk mengekalkan sejarah transaksi yang konsisten yang boleh dilihat oleh semua peserta.

Protokol konsensus dianggap sukar untuk difahami. SCP adalah lebih mudah daripada kebanyakan mereka, tetapi masih berkongsi reputasi ini - sebahagiannya disebabkan oleh idea yang salah bahawa "pengundian bersekutu", yang merupakan subjek separuh pertama artikel saintifik, adalah SCP. Tetapi itu tidak benar! Ini hanyalah blok binaan penting yang digunakan oleh separuh kedua artikel untuk dibuat sebenar Protokol konsensus bintang.

Dalam artikel ini kami akan menerangkan secara ringkas apa itu "sistem perjanjian", apakah yang boleh menjadikannya "Byzantine" dan mengapa menjadikan sistem Byzantine "persekutuan". Kami kemudiannya akan menerangkan prosedur pengundian bersekutu yang diterangkan dalam artikel SCP, dan akhirnya kami akan menerangkan protokol SCP itu sendiri.

Sistem perjanjian

Sistem perjanjian membolehkan sekumpulan peserta mencapai kata sepakat tentang sesuatu topik, seperti apa yang hendak dipesan untuk makan tengah hari.

Di Interstellar, kami telah melaksanakan sistem perjanjian makan kami sendiri: kami memesan apa yang dikatakan oleh pengurus operasi kami, John. Ini adalah sistem perjanjian yang mudah dan berkesan. Kami semua mempercayai John dan percaya bahawa dia akan menemui sesuatu yang menarik dan berkhasiat setiap hari.

Tetapi bagaimana jika John menyalahgunakan kepercayaan kita? Dia boleh membuat keputusan sendirian bahawa kita semua harus menjadi vegan. Dalam seminggu atau dua minggu, kita mungkin akan menggulingkannya dan menyerahkan kuasa kepada Elizabeth. Tetapi tiba-tiba dia suka avokado dengan ikan bilis dan fikir semua orang harus begitu. Kuasa merosakkan. Oleh itu, adalah lebih baik untuk mencari kaedah yang lebih demokratik: beberapa cara untuk memastikan pilihan yang berbeza diambil kira, sambil memastikan hasil yang tepat pada masanya dan tidak jelas, supaya tiada siapa yang akhirnya memesan makan tengah hari, atau lima orang membuat pesanan yang berbeza, atau perbincangan berlarutan hingga ke petang.

Nampaknya penyelesaiannya mudah: adakan undi! Tetapi ini adalah tanggapan yang mengelirukan. Siapa yang akan mengutip undi dan melaporkan keputusannya? Dan mengapa orang lain harus mempercayai apa yang dia katakan? Mungkin kita boleh pada mulanya undilah pemimpin yang kami percayai untuk mengetuai pengundian - tetapi siapa yang akan memimpinnya первым dengan mengundi? Bagaimana jika kita tidak bersetuju dengan pemimpin? Atau bagaimana jika kita mencapai kata sepakat, tetapi pemimpin ini terperangkap dalam mesyuarat atau bercuti sakit?

Masalah yang sama berlaku dalam rangkaian komputer teragih. Semua peserta atau nod mesti bersetuju dengan beberapa keputusan, seperti giliran siapa untuk mengemas kini fail kongsi atau mengalih keluar tugas daripada baris gilir pemprosesan. Dalam rangkaian mata wang kripto, nod berulang kali perlu memilih rupa cerita penuh daripada beberapa versi yang mungkin, yang kadangkala bercanggah. Perjanjian rangkaian ini memberi jaminan kepada penerima bahawa syiling itu (a) sah (bukan tiruan) dan (b) belum dibelanjakan di tempat lain. Ini juga memastikan bahawa dia akan dapat membelanjakan syiling pada masa hadapan kerana penerima baharu akan mempunyai jaminan yang sama atas sebab yang sama.

Mana-mana sistem konsensus dalam rangkaian pengkomputeran teragih mestilah bertolak ansur dengan kesalahan: ia mesti menghasilkan hasil yang konsisten walaupun terdapat ralat seperti pautan perlahan, nod tidak responsif dan pesanan mesej yang salah. Byzantine Sistem perjanjian juga tahan terhadap ralat "Byzantine": nod yang memberikan maklumat palsu, sama ada disebabkan ralat atau dalam percubaan sengaja untuk melemahkan sistem atau mendapat beberapa kelebihan. Toleransi kesalahan "Byzantine" - keupayaan untuk mempercayai keputusan kumpulan walaupun sesetengah ahli kumpulan mungkin berbohong atau sebaliknya tidak mengikut peraturan membuat keputusan - dipanggil perumpamaan tentang jeneral Empayar Byzantineyang cuba menyelaraskan serangan. Penerangan yang baik di Anthony Stevens.

Pertimbangkan pemilik syiling crypto Alice, yang mesti memilih antara membeli ais krim yang lazat daripada Bob dan membayar hutang Carol. Mungkin Alice mahu membayar kedua-duanya sekali gus dengan menipu membelanjakan syiling yang sama. Untuk melakukan ini, dia mesti meyakinkan komputer Bob bahawa syiling itu tidak pernah dibayar kepada Carol, dan meyakinkan komputer Carol bahawa syiling itu tidak pernah dibayar kepada Bob. Sistem perjanjian Byzantine menjadikan ini hampir mustahil, menggunakan satu bentuk peraturan majoriti yang dipanggil kuorum. Nod dalam rangkaian sedemikian enggan berpindah ke versi sejarah tertentu sehingga ia melihat bahawa bilangan rakan sebaya yang mencukupi - kuorum - bersetuju dengan peralihan sedemikian. Sebaik sahaja ini berlaku, mereka akan membentuk blok pengundian yang cukup besar untuk memaksa nod rangkaian yang tinggal bersetuju dengan keputusan mereka. Alice boleh memaksa beberapa nod untuk berbohong bagi pihaknya, tetapi jika rangkaian itu cukup besar, percubaannya akan ditenggelami oleh undian nod yang jujur.

Berapakah bilangan nod yang diperlukan untuk korum? Sekurang-kurangnya, majoriti, atau lebih tepat, majoriti yang layak untuk memerangi kesilapan dan penipuan. Tetapi untuk mengira majoriti, anda perlu mengetahui jumlah peserta. Di pejabat Interstellar atau pada pilihan raya daerah, nombor ini mudah diketahui. Tetapi jika kumpulan anda ialah rangkaian yang ditakrifkan secara longgar di mana nod boleh masuk dan keluar sesuka hati tanpa kelulusan daripada pusat, maka anda perlu persekutuan sistem perjanjian Byzantine yang mampu menentukan kuorum bukan daripada senarai nod yang telah ditetapkan, tetapi secara dinamik, daripada petikan nod yang sentiasa berubah dan tidak dapat dielakkan tidak lengkap pada masa tertentu.

Ia mungkin kelihatan mustahil untuk mencipta kuorum dari perspektif satu nod dalam rangkaian yang luas, tetapi ia mungkin. Kuorum sebegini malah boleh menjamin keputusan pengundian terpencar. Kertas putih SCP menunjukkan cara melakukan ini menggunakan prosedur yang dipanggil melalui undi persekutuan.

Untuk tidak sabar

Selebihnya artikel menerangkan pengundian bersekutu dan protokol konsensus Stellar dengan lebih terperinci. Jika anda tidak berminat dengan butirannya, berikut ialah gambaran keseluruhan proses tersebut.

1. Nod menjalankan pusingan pengundian persekutuan mengenai "penama". Pusingan pengundian persekutuan bermaksud:
   • Nod mengundi untuk beberapa pernyataan, sebagai contoh, "Saya mencadangkan nilai V";
   • Nod mendengar suara rakan sebaya sehingga ia menemui satu yang boleh "menerima";
   • Nod mencari "kuorum" untuk pernyataan ini. Satu kuorum "mengesahkan" penama.
2. Sebaik sahaja nod boleh mengesahkan satu atau lebih penama, ia cuba "menyediakan" "undi" melalui beberapa pusingan pengundian bersekutu.
3. Sebaik sahaja nod dapat mengesahkan undian itu sudah sedia, ia cuba melaksanakannya melalui lebih banyak pusingan pengundian bersekutu.
4. Sebaik sahaja nod boleh mengesahkan komitmen undi, ia boleh "mengeluarkan" nilai undi itu dengan menggunakannya sebagai keputusan konsensus.

Langkah-langkah ini melibatkan beberapa pusingan pengundian bersekutu, yang secara kolektif membentuk satu pusingan SCP. Mari kita lihat dengan lebih dekat apa yang berlaku pada setiap langkah.

Pengundian bersekutu

Pengundian bersekutu ialah prosedur untuk menentukan sama ada rangkaian boleh bersetuju dengan cadangan. Dalam pusingan pengundian, setiap nod mesti memilih salah satu daripada banyak kemungkinan nilai. Ia tidak boleh melakukan ini melainkan ia yakin bahawa nod lain dalam rangkaian tidak akan memilih hasil yang berbeza. Untuk memastikan ini, nod bertukar-tukar mesej berulang-alik supaya semua orang disahkanItu kuorum knot menerima perkara yang sama keputusan. Bahagian selebihnya menerangkan istilah dalam ayat ini dan cara keseluruhan prosedur berlaku.

Kuorum dan hirisan kuorum

Mari kita mulakan dengan menentukan kuorum. Seperti yang kita bincangkan di atas, dalam rangkaian terdesentralisasi dengan keahlian dinamik, adalah mustahil untuk mengetahui terlebih dahulu bilangan nod dan oleh itu berapa banyak yang diperlukan untuk majoriti. Pengundian bersekutu menyelesaikan masalah ini dengan memperkenalkan idea baharu potong korum (potongan kuorum): Satu set kecil rakan sebaya yang dipercayai oleh nod untuk menyampaikan maklumat status pengundian kepada seluruh rangkaian. Setiap nod mentakrifkan kepingan kuorumnya sendiri (yang mana ia menjadi ahli de facto).

Pembentukan kuorum bermula dengan pemotongan kuorum. Untuk setiap nod, nod potongnya ditambah. Kemudian istilah hirisan ditambah nod ini dan sebagainya. Semasa anda meneruskan, semakin banyak nod yang anda tidak boleh tambah kerana ia sudah disertakan dalam kepingan. Apabila tiada lagi nod baharu untuk ditambah, proses akan berhenti: kami telah membentuk kuorum dengan "penutupan transitif" kepingan kuorum nod awal.

Untuk mencari kuorum dari nod tertentu...

... tambahkan ahli hirisannya...

...kemudian kami menambah ahli hirisan nod ini.

Kami meneruskan sehingga tiada nod lagi untuk ditambah.

Tiada nod lagi untuk ditambah. Ini adalah korum.

Malah, setiap nod boleh muncul dalam lebih daripada satu kepingan. Untuk membentuk kuorum, pilih hanya satu daripada kepingan dan tambah ahli; kemudian pilih mana-mana bahagian untuk setiap ahli dan tambah ahli ia potong dan sebagainya. Ini bermakna setiap nod adalah ahli kepada banyak kuorum yang mungkin.

Pilih hanya satu kepingan kuorum pada setiap langkah.

Satu korum yang mungkin. Atau alternatif...

...pilih kepingan lain...

…(bila boleh)…

... mewujudkan kuorum lain.

Bagaimanakah nod mengetahui bahagian mana nod lain berada? Dengan cara yang sama seperti maklumat lain tentang nod lain: daripada penghantaran yang setiap nod disiarkan ke rangkaian apabila keadaan pengundiannya berubah. Setiap siaran termasuk maklumat tentang kepingan nod penghantaran. Kertas putih SCP tidak menyatakan mekanisme komunikasi. Pelaksanaan biasanya menggunakan protokol gosip untuk jaminan penyiaran mesej ke seluruh rangkaian.

Ingat bahawa dalam sistem perjanjian Byzantine bukan persekutuan, kuorum ditakrifkan sebagai majoriti semua nod. Sistem perjanjian Byzantine direka dari sudut pandangan soalan: berapa banyak nod yang tidak jujur ​​yang boleh diterima oleh sistem? Dalam sistem N-nod yang direka untuk bertahan f kegagalan, nod seharusnya boleh membuat kemajuan dengan menerima maklum balas daripada N−f rakan sebaya kerana f daripada mereka mungkin menurun. Tetapi setelah menerima respons daripada rakan N−f, kita boleh mengandaikan bahawa semua rakan f (yang mana nod tidak menerima respons) sebenarnya jujur. Oleh itu, f daripada N−f rakan sebaya (yang mana maklum balas diterima) adalah berniat jahat. Untuk nod mendapat konsensus yang sama, majoriti nod yang tinggal mestilah jujur, iaitu, kita memerlukan N−f lebih besar daripada 2f atau N > 3f. Jadi lazimnya sistem yang direka untuk bertahan dalam kegagalan f akan mempunyai sejumlah N=3f+1 nod dan saiz kuorum 2f+1. Sebaik sahaja cadangan melepasi ambang kuorum, seluruh rangkaian yakin bahawa sebarang cadangan yang bersaing akan gagal. Ini adalah bagaimana rangkaian menumpu kepada hasilnya.

Tetapi dalam sistem perjanjian Byzantine persekutuan, bukan sahaja tidak boleh ada majoriti (kerana tiada siapa yang tahu jumlah saiz rangkaian), tetapi konsep majoriti sama sekali tidak berguna! Jika keahlian dalam sistem terbuka, maka seseorang boleh memperoleh majoriti hanya dengan melakukan serangan Sybil yang dipanggil: berulang kali menyertai rangkaian merentas berbilang nod. Jadi mengapa penutupan kepingan transitif boleh dipanggil kuorum, dan bagaimanakah ia dapat menyekat cadangan bersaing?

Secara teknikal, tidak mungkin! Bayangkan rangkaian enam nod, di mana dua kembar tiga diasingkan dalam kepingan kuorum masing-masing. Subkumpulan pertama mungkin membuat keputusan yang tidak akan didengari oleh kumpulan kedua, dan begitu juga sebaliknya. Tiada cara untuk rangkaian ini mencapai kata sepakat (kecuali secara kebetulan).

Oleh itu, SCP memerlukan bahawa untuk pengundian bersekutu (dan untuk teorem penting kertas untuk digunakan), rangkaian mesti mempunyai sifat yang dipanggil persimpangan kuorum. Dalam rangkaian dengan sifat ini, mana-mana dua kuorum yang boleh dibina sentiasa bertindih dalam sekurang-kurangnya satu nod. Untuk menentukan sentimen semasa rangkaian, ini sama baiknya dengan mempunyai majoriti. Secara intuitif, ini bermakna jika mana-mana kuorum bersetuju dengan pernyataan X, tiada kuorum lain boleh bersetuju dengan apa-apa lagi, kerana ia semestinya akan memasukkan beberapa nod daripada kuorum pertama yang telah mengundi untuk X.

Jika terdapat persimpangan kuorum dalam rangkaian...

... maka mana-mana dua kuorum yang anda boleh bina...

... akan sentiasa bersilang.

(Sudah tentu, nod bertindih mungkin bertukar menjadi pembohongan Byzantine atau sebaliknya buruk. Dalam kes ini, persimpangan kuorum tidak membantu rangkaian bersetuju sama sekali. Atas sebab ini, banyak keputusan dalam kertas putih SCP adalah berdasarkan andaian eksplisit, seperti apa yang tinggal dalam persimpangan kuorum rangkaian walaupun selepas mengeluarkan nod buruk. Untuk kesederhanaan, mari kita tinggalkan andaian ini tersirat dalam artikel yang lain).

Ia mungkin kelihatan tidak munasabah untuk menjangkakan bahawa persimpangan kuorum yang boleh dipercayai adalah mungkin dalam rangkaian nod bebas. Tetapi ada dua sebab mengapa ini berlaku.

Sebab pertama ialah kewujudan Internet itu sendiri. Internet ialah contoh sempurna rangkaian nod bebas dengan kuorum bersilang. Kebanyakan nod di Internet bersambung kepada hanya beberapa nod tempatan lain, tetapi set kecil ini cukup bertindih sehingga setiap nod boleh dicapai dari setiap nod lain di sepanjang laluan tertentu.

Sebab kedua adalah khusus untuk rangkaian pembayaran Stellar (penggunaan SCP yang paling biasa). Setiap aset pada rangkaian Stellar mempunyai pengeluar dan garis panduan Stellar memerlukan setiap pengeluar untuk menetapkan satu atau lebih nod pada rangkaian untuk memproses permintaan penebusan. Adalah menjadi kepentingan terbaik anda untuk memasukkan nod ini secara langsung atau tidak dalam kepingan kuorum untuk setiap aset yang anda minati. Kuorum untuk semua nod yang berminat dalam aset tertentu kemudiannya akan bertindih sekurang-kurangnya pada nod penebusan tersebut. Nod yang berminat dalam berbilang aset akan memasukkan semua nod penebusan pengeluar masing-masing dalam kepingan kuorum mereka dan mereka akan berusaha untuk mengumpulkan semua aset bersama-sama. Selain itu, sebarang aset yang tidak dipautkan dengan cara ini kepada orang lain dalam rangkaian, dan tidak sepatutnya disambungkan - ini direka bentuk supaya tiada pertindihan kuorum untuk rangkaian ini (contohnya, bank dari zon dolar kadangkala ingin berdagang dengan bank dari zon euro dan bank dari zon peso, jadi mereka berada dalam rangkaian yang sama, tetapi tiada daripada mereka mengambil berat tentang rangkaian berasingan kanak-kanak, menjual kad besbol).

Sudah tentu, menunggu lintasan kuorum tidak jaminan. Sistem perjanjian Byzantine yang lain berhutang banyak kerumitannya kepada jaminan kuorum. Inovasi penting SCP ialah ia menghapuskan tanggungjawab untuk mencipta kuorum daripada algoritma konsensus itu sendiri dan membawanya ke peringkat aplikasi. Oleh itu, walaupun pengundian bersekutu cukup umum untuk mengundi sebarang isu, kebolehpercayaannya sebenarnya bergantung secara kritikal pada makna yang lebih luas bagi maksud ini. Sesetengah penggunaan hipotetikal mungkin tidak kondusif untuk mencipta rangkaian yang bersambung dengan baik seperti yang lain.

Undian, penerimaan dan pengesahan

Dalam pusingan pengundian bersekutu, nod secara pilihan mula mengundi untuk beberapa nilai V. Ini bermakna menyiarkan mesej ke rangkaian: "Saya nod N, potongan korum saya ialah Q, dan saya mengundi untuk V." Apabila nod mengundi dengan cara ini, ia menjanjikan bahawa ia tidak pernah mengundi menentang V dan tidak akan pernah mengundi.

Dalam siaran peer-to-peer, setiap nod melihat cara yang lain mengundi. Apabila nod telah mengumpulkan cukup mesej ini, ia boleh menjejaki kepingan kuorum dan cuba mencari kuorum. Jika dia melihat korum rakan sebaya yang turut mengundi V, dia boleh meneruskan ke pengangkatan V dan siarkan mesej baharu ini ke rangkaian: “Saya nod N, kepingan kuorum saya ialah Q, dan saya menerima V.” Penerimaan memberikan jaminan yang lebih kuat daripada pengundian mudah. Apabila nod mengundi untuk V, ia tidak boleh mengundi untuk pilihan lain. Tetapi jika nod menerima V, tiada nod pada Rangkaian akan menerima pilihan lain (Teorem 8 dalam kertas putih SCP membuktikannya).

Sudah tentu, terdapat kebarangkalian tinggi bahawa tidak akan ada kuorum nod yang bersetuju dengan V. Nod lain boleh mengundi untuk nilai lain. Tetapi ada cara lain untuk nod beralih daripada pengundian mudah kepada penerimaan. N mungkin menerima nilai yang berbeza untuk W, walaupun dia tidak mengundinya, dan walaupun dia tidak melihat kuorum untuknya. Untuk memutuskan untuk menukar undi anda, lihat sahaja set menyekat nod yang telah menerima W. Set penyekat ialah satu nod daripada setiap kepingan kuorum N. Seperti namanya, ia boleh sekatan apa-apa makna lain. Jika semua nod dalam set sedemikian menerima W, maka (oleh Teorem 8) ia tidak akan mungkin membentuk kuorum yang mengambil nilai yang berbeza, dan oleh itu ia juga selamat untuk N menerima W.

Nod N dengan tiga keping korum.

BDF ialah set penyekat untuk N: ia termasuk satu nod daripada setiap kepingan N.

BE juga merupakan set penyekat untuk N kerana E muncul dalam dua keping N.

Tetapi set menyekat bukan korum. Terlalu mudah untuk menipu nod N supaya menerima nilai yang diingini jika sudah cukup untuk menggodam hanya satu nod dalam setiap kepingan N. Oleh itu, menerima nilai itu bukanlah pengakhiran pengundian. Sebaliknya, N mesti mengesahkan nilai, iaitu, melihat kuorum nod yang menerimanya. Jika ia sampai sejauh itu, maka, seperti yang dibuktikan oleh kertas putih SCP (dalam Teorem 11), seluruh rangkaian juga akhirnya akan mengesahkan nilai yang sama, jadi N akan menamatkan undian bersekutu dengan nilai tertentu sebagai hasilnya.

Pengundian bersekutu.

Proses pengundian, penerimaan dan pengesahan merupakan satu pusingan penuh pengundian bersekutu. Protokol konsensus Stellar menggabungkan banyak pusingan ini untuk mencipta sistem konsensus yang lengkap.

Protokol Konsensus Bintang

Dua sifat terpenting bagi sistem konsensus ialah − keselamatan и kebolehmandirian. Algoritma konsensus adalah "selamat" jika ia tidak boleh memberikan hasil yang berbeza kepada peserta yang berbeza (salinan sejarah Bob tidak akan pernah bercanggah dengan Carol). "Kebolehhidupan" bermaksud bahawa algoritma akan sentiasa menghasilkan hasil, iaitu, ia tidak akan tersekat.

Diterangkan prosedur pengundian persekutuan selamat dalam erti kata bahawa jika nod mengesahkan nilai V, tiada nod lain akan mengesahkan nilai lain. Tetapi "tidak akan mengesahkan makna lain" tidak bermakna bahawa ia semestinya akan mengesahkan sesuatu. Peserta boleh mengundi pada begitu banyak nilai yang berbeza sehingga tiada apa yang akan mencapai ambang penerimaan. Ini bermakna dalam pengundian persekutuan tidak ada kebolehmandirian.

Protokol konsensus Stellar menggunakan pengundian bersekutu dengan cara yang memastikan keselamatan dan kemandirian. (Jaminan keselamatan dan kemandirian SCP mempunyai had teori. Reka bentuk memilih jaminan keselamatan yang sangat kukuh, mengorbankan pengurangan kebolehmandirian yang kecil, tetapi dengan masa yang mencukupi, konsensus berkemungkinan besar dapat dicapai.) Secara ringkasnya, ideanya adalah untuk mempunyai berbilang undian bersekutu pada berbilang nilai sehingga salah satu daripadanya berjaya melalui semua fasa pengundian SCP yang diterangkan di bawah.

Nilai yang SCP mencari konsensus boleh menjadi sejarah transaksi atau pesanan makan tengah hari atau sesuatu yang lain, tetapi adalah penting untuk ambil perhatian bahawa ini bukan nilai yang diterima atau disahkan. Sebaliknya, pengundian persekutuan berlaku mengikut pernyataan tentang nilai-nilai ini.

Pusingan pertama pengundian persekutuan berlangsung pada peringkat pencalonan (fasa pencalonan), pada set pernyataan seperti "Saya mencalonkan V," mungkin untuk banyak nilai V yang berbeza. Tujuan pencalonan adalah untuk mencari satu atau lebih pernyataan yang melalui penerimaan dan pengesahan.

Selepas mencari calon yang boleh disahkan, SCP bergerak ke fasa pengundian, di mana matlamatnya adalah untuk mencari buletin (iaitu, bekas untuk nilai yang dicadangkan) dan kuorum yang boleh mengisytiharkan komited untuknya (komit). Jika korum membuat undian, nilainya diterima sebagai konsensus. Tetapi sebelum nod boleh mengundi pada komitmen undi, ia mesti mengesahkan terlebih dahulu pembatalan semua undi dengan nilai kaunter yang lebih rendah. Langkah-langkah ini—membatalkan undi untuk mencari yang boleh dilakukan—melibatkan berbilang pusingan pengundian bersekutu bagi berbilang tuntutan undi.

Bahagian berikut menerangkan pencalonan dan pengundian dengan lebih terperinci.

Pencalonan

Pada permulaan fasa pencalonan, setiap nod boleh secara spontan memilih nilai untuk V dan mengundi untuk pernyataan "Saya mencalonkan V." Matlamat pada peringkat ini adalah untuk mengesahkan pencalonan beberapa nilai melalui undian bersekutu.

Mungkin nod yang mencukupi mengundi pada cadangan yang cukup berbeza sehingga tiada pencalonan boleh mencapai ambang penerimaan. Oleh itu, selain menyiarkan undi pencalonan mereka sendiri, nod "mencerminkan" pencalonan rakan sebaya mereka. Gema bermakna jika nod mengundi untuk pencalonan V, tetapi melihat mesej daripada jiran mengundi untuk pencalonan W, ia kini akan mengundi untuk kedua-dua V dan W. (Tidak semua undian rakan sebaya bergema semasa penamaan calon kerana ini boleh membawa kepada letupan penama yang berbeza. SCP termasuk mekanisme untuk mengawal selia undi ini. Ringkasnya, terdapat formula untuk menentukan "keutamaan" rakan sebaya dari sudut pandangan nod, dan hanya undian nod keutamaan tinggi yang ditunjukkan. Semakin lama pencalonan mengambil masa, lebih rendah ambang, jadi nod mengembangkan set rakan yang undiannya akan dicerminkan. Formula keutamaan termasuk nombor slot sebagai salah satu inputnya, jadi rakan setara keutamaan tinggi untuk satu slot mungkin rakan setara keutamaan rendah untuk lain, begitu juga sebaliknya).

Dari segi konsep, pencalonan adalah selari, kedua-dua V dan W adalah undi persekutuan yang berasingan, setiap individu mampu mencapai penerimaan atau pengesahan. Dalam amalan, mesej protokol SCP membungkus undian individu ini bersama-sama.

Walaupun mengundi untuk pencalonan V adalah janji untuk tidak sekali-kali mengundi terhadap pencalonan V, ia adalah pada peringkat permohonan - dalam kes ini SCP - ia ditentukan apa yang dimaksudkan dengan "menentang". SCP tidak melihat kenyataan yang bercanggah dengan undian "Saya mencalonkan X", iaitu, tiada mesej "Saya menentang pencalonan X", jadi nod boleh mengundi untuk mencalonkan sebarang nilai. Kebanyakan pencalonan ini tidak akan ke mana-mana, tetapi akhirnya nod akan dapat menerima atau mengesahkan satu atau lebih nilai. Sebaik sahaja penama disahkan, dia menjadi calon.

Pencalonan SCP menggunakan undian bersekutu. Terdapat banyak nilai "B" yang dikemukakan oleh rakan sebaya dan "dicerminkan" oleh nod.

Pencalonan boleh menyebabkan berbilang calon yang disahkan. Oleh itu, SCP memerlukan lapisan aplikasi untuk menyediakan beberapa kaedah untuk menggabungkan calon menjadi satu komposit (komposit). Kaedah menyertai boleh apa sahaja. Perkara utama ialah jika kaedah ini bersifat deterministik, maka setiap nod akan menggabungkan calon yang sama. Dalam sistem pengundian makan tengah hari, "penyatuan" mungkin bermaksud menolak satu daripada dua calon. (Tetapi dengan cara yang menentukan: setiap nod mesti memilih nilai yang sama untuk ditetapkan semula. Contohnya, pemilihan awal dalam susunan abjad). Dalam rangkaian pembayaran Stellar, di mana sejarah urus niaga diundi, penggabungan dua penama yang dicadangkan melibatkan penggabungan urus niaga yang terkandung di dalamnya dan yang terbaru daripada dua cap masa mereka.

Kertas putih SCP membuktikan (Teorem 12) bahawa pada akhir fasa lanjutan, rangkaian akhirnya menumpu kepada komposit tunggal. Tetapi ada masalah: pengundian bersekutu ialah protokol tak segerak (seperti SCP). Dalam erti kata lain, nod tidak diselaraskan mengikut masa, tetapi hanya oleh mesej yang dihantar. Dari sudut pandangan nod, tidak jelas bila tamat fasa lanjutan. Dan walaupun semua nod akhirnya akan tiba di komposit yang sama, mereka mungkin mengambil laluan yang berbeza di sepanjang jalan, mencipta calon komposit yang berbeza di sepanjang jalan, dan tidak boleh membezakan yang mana satu yang terakhir.

Tapi biasalah. Pencalonan hanyalah persediaan. Perkara utama ialah mengehadkan bilangan calon untuk mencapai konsensus, yang berlaku dalam proses itu bertanding jawatan (mengundi).

Berlari

Buletin adalah pasangan , dengan pembilang ialah integer yang bermula pada 1 dan nilai ialah calon dari peringkat pencalonan. Ini boleh menjadi calon nod sendiri atau calon nod jiran yang diterima oleh nod itu. Secara kasarnya, undi melibatkan percubaan berulang kali untuk memaksa rangkaian mencapai kata sepakat mengenai beberapa calon dalam beberapa undi dengan memegang berpotensi banyak undi bersekutu pada penyata undi. Pembilang pada undi menjejaki percubaan yang dibuat, dan undi dengan kiraan yang lebih tinggi diutamakan daripada undi dengan kiraan yang lebih rendah. Jika surat berita tersekat, undi baru bermula, kini dalam undian .

Adalah penting untuk membezakannya makna (contohnya, apakah pesanan makan tengah hari: piza atau salad), surat berita (pasangan nilai balas) dan pernyataan tentang undi. Pusingan SCP termasuk beberapa pusingan pengundian persekutuan, khususnya pada kenyataan berikut:

• "Saya bersedia untuk melakukan undi B" dan
• "Saya mengumumkan komitmen undi B"

Dari perspektif nod tertentu, konsensus dicapai apabila ia menemui undi B yang mana ia boleh mengakui (iaitu, mencari kuorum yang menerima) pernyataan "Saya melakukan undi B." Mulai saat ini, adalah selamat untuk bertindak atas nilai yang dinyatakan dalam B - contohnya, membuat pesanan ini untuk makan tengah hari. Ia dikenali sebagai eksternalisasi makna. Sebaik sahaja penerimaan undi disahkan, nod boleh memastikan bahawa mana-mana nod lain telah mengeluarkan nilai yang sama atau akan melakukannya pada masa hadapan.

Walaupun banyak undi persekutuan secara konseptual dijalankan ke atas tuntutan untuk banyak undi yang berbeza, mereka tidak bertukar-tukar banyak mesej kerana setiap mesej merangkumi beberapa undi. Satu mesej dengan itu mempromosikan keadaan banyak undi bersekutu sekaligus, sebagai contoh: “Saya menerima undi komit mulai dari sebelum ini "

Apakah maksud istilah "bersedia" dan "komit"?

Nod mengundi untuk membuat undian apabila ia yakin bahawa nod lain tidak akan membuat undian dengan nilai yang berbeza. Meyakinkan ini adalah tujuan penyediaan permohonan. Undian yang menyatakan "Saya bersedia untuk membuat undian B" ialah janji untuk tidak sekali-kali membuat undian yang lebih kecil daripada B, iaitu dengan kiraan yang lebih kecil (SCP memerlukan nilai dalam kertas undi dalam susunan tertentu. Oleh itu, surat berita kurang , jika N1

Mengapakah "Saya bersedia untuk membuat undian B" bermaksud "Saya berjanji tidak akan membuat undian yang lebih kecil daripada B"? Kerana SCP mentakrifkan pengguguran sebagai bertentangan dengan komit. Undi untuk menyediakan undi juga melibatkan undi untuk membatalkan kelayakan beberapa undi lain, dan, seperti yang kita bincangkan sebelum ini, mengundi untuk satu perkara adalah janji untuk tidak sekali-kali mengundi menentangnya.

Sebelum menyiarkan komit, nod mesti terlebih dahulu mencari buletin yang boleh disahkan sebagai disediakan. Dalam erti kata lain, ia melakukan undian bersekutu mengenai topik "Saya bersedia untuk membuat undian B," mungkin pada banyak undi yang berbeza, sehingga ia mendapati satu yang menerima kuorum.

Dari mana datangnya undi untuk menyediakan undi? Pertama, nod menyiarkan persediaan untuk mengundi <1,C>, di mana C ialah calon komposit yang dihasilkan pada peringkat pencalonan. Walau bagaimanapun, walaupun selepas persiapan untuk pengundian bermula, pencalonan mungkin menyebabkan calon tambahan muncul sebagai undi baru. Sementara itu, rakan sebaya boleh mempunyai calon yang berbeza dan mereka boleh membentuk set sekatan yang menerima "Saya bersedia untuk melakukan undian B2" yang akan meyakinkan nod untuk menerimanya juga. Akhir sekali, terdapat mekanisme tamat masa yang menjana pusingan baharu pengundian bersekutu pada undi baharu dengan kiraan yang lebih tinggi jika undi semasa tersekat.

Sebaik sahaja nod menemui undi B yang boleh disahkan sebagai disediakan, ia menyiarkan mesej baharu "Komit undi B." Undian ini memberitahu rakan sebaya bahawa nod tidak akan berputus asa B. Malah, jika B ialah undi , kemudian “Komit undi " ertinya persetujuan tanpa syarat untuk mengundi bagi kesediaan setiap undi daripada kepada <∞, s>. Nilai tambahan ini membantu rakan sebaya lain mengejar rakan sebaya komit jika mereka masih dalam peringkat awal protokol.

Pada peringkat ini, perlu ditekankan sekali lagi bahawa ini adalah protokol tak segerak. Hanya kerana satu nod menghantar undian naik untuk komit tidak bermakna rakan sebayanya juga berbuat demikian. Sesetengah daripada mereka mungkin masih mengundi pada kenyataan sebagai persediaan untuk mengundi, yang lain mungkin telah menyuarakan maksudnya. SCP menerangkan cara nod harus memproses setiap jenis mesej rakan sebaya tanpa mengira fasanya.

Jika mesej "Saya telah mengumumkan komitmen » tidak boleh diterima atau disahkan, iaitu kebarangkalian mesej diterima atau disahkan atau - atau, dalam apa jua keadaan, sebarang undian dengan nilai C, dan bukan yang lain, kerana nod telah berjanji tidak akan membatalkan . Pada masa nod menyiarkan undian untuk komit, ia akan menjadi C atau tiada apa-apa, bergantung pada sejauh mana konsensus berjalan. Walau bagaimanapun, ini masih belum mencukupi untuk nod menyuarakan C. Sesetengah rakan sebaya Byzantine (yang membentuk kurang daripada kuorum, berdasarkan andaian keselamatan kami) mungkin berbohong kepada nod. Menerima dan kemudian mengesahkan beberapa undi (atau julat undi) adalah perkara yang memberi keyakinan kepada nod untuk akhirnya menyuarakan C.

Pengundian SCP melalui pengundian bersekutu. Tidak ditunjukkan: Pemasa boleh dimatikan pada bila-bila masa, meningkatkan kiraan pada undi (dan mungkin menghasilkan komposit baharu calon tambahan yang dicalonkan).

Dan itu sahaja! Apabila rangkaian telah mencapai kata sepakat, ia bersedia untuk melakukannya lagi dan lagi. Pada rangkaian pembayaran Stellar, ini berlaku kira-kira sekali setiap 5 saat: satu pencapaian yang memerlukan kedua-dua keselamatan dan kemandirian yang dijamin oleh SCP.

SCP boleh mencapai ini dengan bergantung pada beberapa pusingan pengundian bersekutu. Pengundian bersekutu dimungkinkan dengan konsep potongan kuorum: set rakan sebaya yang setiap nod telah memutuskan untuk dipercayai sebagai sebahagian daripada kuorum (subjektif). Konfigurasi ini bermakna konsensus boleh dicapai walaupun dalam rangkaian dengan keahlian terbuka dan penipuan Byzantine.

Bacaan lanjut

• Kertas putih SCP asal boleh didapati di siniDan di sini draf spesifikasi untuk pelaksanaannya.
• Pengarang asal protokol SCP, David Mazier, menerangkannya dengan cara yang dipermudahkan (tetapi masih teknikal). di sini.
• Anda mungkin terkejut kerana tidak menemui istilah "perlombongan" atau "bukti kerja" dalam artikel ini. SCP tidak menggunakan kaedah ini, tetapi beberapa algoritma konsensus lain melakukannya. Zane Witherspoon menulis boleh diakses gambaran keseluruhan algoritma konsensus.
• Huraian Langkah demi Langkah rangkaian mudah yang mencapai konsensus dalam satu pusingan penuh SCP.
• Bagi pembaca yang berminat dengan pelaksanaan SCP: lihat Kod C++, digunakan oleh rangkaian pembayaran Stellar, atau Pergi kod, yang saya tulis untuk pemahaman yang lebih baik tentang SCP.

Sumber: www.habr.com