Stellar konsensüs protokolü ilk olarak 2015 yılında David Mazier. Bu, merkezi olmayan, lidersiz bilgi işlem ağlarının bir karar üzerinde verimli bir şekilde fikir birliğine varmasına olanak tanıyan bir "federal Bizans anlaşma sistemidir". Stellar ödeme ağı, tüm katılımcılar tarafından görülebilen tutarlı bir işlem geçmişini sürdürmek için Stellar Consensus Protokolünü (SCP) kullanır.
Konsensüs protokollerinin anlaşılmasının zor olduğu düşünülmektedir. SCP çoğundan daha basittir ancak kısmen bilimsel makalenin ilk yarısının konusu olan "federe oylamanın" SCP olduğu yönündeki yanlış düşünceden dolayı hala bu itibarı paylaşmaktadır. Ama bu doğru değil! Bu, makalenin ikinci yarısının oluşturmak için kullandığı önemli bir yapı taşıdır. gerçek Yıldız konsensüs protokolü.
Bu yazımızda “anlaşmalar sistemi”nin ne olduğunu, onu neyin “Bizans” yapabileceğini ve Bizans sistemini neden “federal” yaptığını kısaca anlatacağız. Daha sonra SCP makalesinde açıklanan birleşik oylama prosedürünü açıklayacağız ve son olarak SCP protokolünün kendisini açıklayacağız.
Anlaşma sistemleri
Anlaşma sistemi, bir grup katılımcının öğle yemeği için ne sipariş edileceği gibi bir konu üzerinde fikir birliğine varmasına olanak tanır.
Interstellar'da kendi yemek anlaşması sistemimizi uyguladık: Operasyon yöneticimiz John ne derse onu sipariş ediyoruz. Bu basit ve etkili bir anlaşma sistemidir. Hepimiz John'a güveniyoruz ve onun her gün ilginç ve besleyici bir şeyler bulacağına inanıyoruz.
Peki ya John güvenimizi kötüye kullanırsa? Hepimizin vegan olmamız gerektiğine tek başına karar verebilir. Bir iki hafta içinde muhtemelen onu devirip iktidarı Elizabeth'e devredeceğiz. Ama birdenbire hamsili avokadoyu seviyor ve herkesin böyle olması gerektiğini düşünüyor. Güç yozlaştırır. Bu nedenle, daha demokratik bir yöntem bulmak daha iyidir: Zamanında ve kesin bir sonuç sağlarken, farklı tercihlerin dikkate alındığından emin olmanın bir yolu, böylece hiç kimse öğle yemeği sipariş etmesin veya beş kişi farklı siparişler versin veya tartışsın. akşama doğru sürüyor.
Görünüşe göre çözüm basit: oy verin! Ancak bu yanıltıcı bir izlenimdir. Oy pusulalarını kim toplayacak ve sonuçları kim rapor edecek? Peki neden başkaları onun söylediklerine inansın ki? Belki yapabiliriz ilk Oylamayı yöneteceğine güvendiğimiz ama oylamaya liderlik edecek bir lidere oy verin ilk oy vererek mi? Peki ya bir lider üzerinde anlaşamazsak? Peki ya bir anlaşmaya varırsak ama bu lider bir toplantıda takılıp kalırsa ya da hastalık iznine çıkarsa?
Benzer sorunlar dağıtılmış bilgisayar ağlarında da ortaya çıkar. Tüm katılımcılar veya düğümler, paylaşılan bir dosyayı güncelleme sırasının kimde olduğu veya bir görevi işlem kuyruğundan kaldırma sırasının kimde olduğu gibi bazı kararlar üzerinde anlaşmaya varmalıdır. Bir kripto para birimi ağında düğümler, bazen çatışan birkaç olası versiyon arasından hikayenin tamamının nasıl görüneceğini tekrar tekrar seçmek zorunda kalır. Bu ağ sözleşmesi, alıcıya madalyonun (a) geçerli (sahte olmadığı) ve (b) henüz başka bir yerde harcanmadığına dair güvence sağlar. Bu aynı zamanda gelecekte de paraları harcayabilmesini sağlar çünkü yeni alıcı aynı nedenlerden dolayı aynı garantilere sahip olacaktır.
Dağıtılmış bir bilgi işlem ağındaki herhangi bir fikir birliği sistemi hataya dayanıklı olmalıdır: yavaş bağlantılar, yanıt vermeyen düğümler ve yanlış mesaj sıralaması gibi hatalara rağmen tutarlı sonuçlar üretmelidir. Bizans Anlaşma sistemi ayrıca "Bizans" hatalarına karşı da dayanıklıdır: ister bir hata nedeniyle ister sistemi baltalamak veya bir avantaj elde etmek için kasıtlı bir girişim nedeniyle yanlış bilgi veren düğümler. "Bizans" hata toleransı - bazı grup üyeleri yalan söylese veya karar verme kurallarına uymasa bile grup kararına güvenme yeteneği - denir Saldırıyı koordine etmeye çalışan kişi. Anthony Stevens'ta.
Bob'tan lezzetli dondurma almakla Carol'ın borcunu ödemek arasında seçim yapmak zorunda kalan kripto para sahibi Alice'i düşünün. Belki Alice aynı parayı sahtekarlıkla harcayarak ikisine de aynı anda ödeme yapmak istiyor olabilir. Bunu yapmak için Bob'un bilgisayarını paranın Carol'a asla ödenmediğine ve Carol'ın bilgisayarını da paranın Bob'a asla ödenmediğine ikna etmesi gerekir. Bizans anlaşma sistemi, çoğunluk kuralı adı verilen bir biçimi kullanarak bunu neredeyse imkansız hale getiriyor. çoğunluk. Böyle bir ağdaki bir düğüm, yeterli sayıda eşin (yesayı) böyle bir geçişi kabul ettiğini görene kadar tarihin belirli bir sürümüne geçmeyi reddeder. Bu gerçekleştiğinde, geri kalan ağ düğümlerini kendi kararlarına katılmaya zorlayacak kadar büyük bir oylama bloğu oluşturacaklar. Alice, bazı düğümleri kendi adına yalan söylemeye zorlayabilir, ancak ağ yeterince büyükse, girişimi dürüst düğümlerin oyları karşısında ezilecektir.
Çekirdek için kaç düğüm gereklidir? Hatalarla ve dolandırıcılıkla mücadele için en azından çoğunluk, daha doğrusu nitelikli çoğunluk. Ancak çoğunluğu saymak için toplam katılımcı sayısını bilmeniz gerekir. Interstellar ofisinde veya bölge seçimlerinde bu sayıları bulmak kolaydır. Ancak grubunuz, düğümlerin merkezin onayı olmadan istediği gibi girip çıkabildiği gevşek tanımlanmış bir ağsa, o zaman şunlara ihtiyacınız vardır: federal Yeter sayılarını önceden belirlenmiş bir düğüm listesinden değil, dinamik olarak, belirli bir zaman noktasındaki düğümlerin sürekli değişen ve kaçınılmaz olarak tamamlanmamış bir anlık görüntüsünden yola çıkarak belirleme yeteneğine sahip bir Bizans anlaşma sistemi.
Geniş bir ağda tek bir düğüm açısından bakıldığında yeterli çoğunluk oluşturmak imkansız gibi görünebilir ancak mümkündür. Böyle bir yeter sayı, merkezi olmayan oylamanın sonuçlarını bile garanti edebilir. SCP teknik incelemesi, adı verilen bir prosedür kullanılarak bunun nasıl yapılacağını gösterir. federal oylamayla.
Sabırsız için
Makalenin geri kalanında birleşik oylama ve Stellar konsensüs protokolü daha ayrıntılı olarak açıklanmaktadır. Ayrıntılarla ilgilenmiyorsanız burada sürecin genel bir özetini bulabilirsiniz.
- Düğümler “adaylar” üzerinde federal oylama turları düzenliyor. Federal oylama turu şu anlama gelir:
- Düğüm bazı ifadelere oy verir, örneğin, "V'nin değerini öneriyorum";
- Düğüm, "alabilen" bir ses bulana kadar eşlerin sesini dinler;
- Düğüm bu iddia için bir "yesayı" arar. Yeterli çoğunluk adayı “onaylar”.
- Bir düğüm bir veya daha fazla adayı onayladığında, birkaç turlu birleşik oylama yoluyla "oy pusulasını" "hazırlamaya" çalışır.
- Bir düğüm oylamanın hazır olduğunu doğrulayabildiğinde, daha fazla birleşik oylama turu yoluyla oylamayı gerçekleştirmeye çalışır.
- Bir düğüm bir oylamanın taahhüdünü onayladığında, oylamanın değerini bir fikir birliği sonucu olarak kullanarak "dışsallaştırabilir".
Bu adımlar, topluca bir SCP turu oluşturan birden fazla birleşik oylama turunu içerir. Her adımda neler olduğuna daha yakından bakalım.
Federe oylama
Birleşik oylama, ağın bir teklif üzerinde anlaşıp anlaşamayacağını belirlemeye yönelik bir prosedürdür. Oylama turunda her düğüm potansiyel olarak birçok olası değerden birini seçmelidir. Ağdaki diğer düğümlerin farklı bir sonuç seçmeyeceğinden emin olmadığı sürece bunu yapamaz. Bundan emin olmak için, düğümler bir dizi mesaj alışverişinde bulunur, böylece herkes onaylıO nisap knot alır aynı karar. Bu bölümün geri kalanında bu cümledeki terimler ve tüm prosedürün nasıl gerçekleştiği açıklanmaktadır.
Yeterli çoğunluk ve çekirdek dilimleri
Yeter sayıyı tanımlayarak başlayalım. Yukarıda tartıştığımız gibi, dinamik üyeliğe sahip merkezi olmayan bir ağda, düğüm sayısını ve dolayısıyla çoğunluk için kaç taneye ihtiyaç duyulduğunu önceden bilmek imkansızdır. Federe oylama yeni bir fikir sunarak bu sorunu çözüyor çoğunluk kesintisi (çekirdek dilimi): Bir düğümün, oylama durumu bilgilerini ağın geri kalanına iletmek için güvendiği küçük bir eş kümesi. Her düğüm kendi çekirdek dilimini tanımlar (bunun fiilen üyesi olur).
Yeter sayının oluşumu yetersayı kesimiyle başlar. Her düğüm için kesilen düğümler eklenir. Daha sonra dilim terimleri eklenir bu düğümler ve benzeri. Devam ettikçe dilime zaten dahil oldukları için ekleyemediğiniz düğümlerin sayısı artar. Eklenecek yeni düğüm kalmadığında süreç durur: İlk düğümün çekirdek diliminin "geçişli kapatılması" yoluyla bir çekirdek oluşturduk.
Belirli bir düğümden yeter sayıyı bulmak için...
... kendi diliminin üyelerini ekle...
...daha sonra bu düğümlerin dilim üyelerini ekliyoruz.
Eklenecek düğüm kalmayıncaya kadar devam ediyoruz.
Eklenecek düğüm kalmadı. Bu bir yeter sayıdır.
Aslında her düğüm birden fazla dilimde görünebilir. Yeterli çoğunluk oluşturmak için dilimlerden yalnızca birini seçin ve üyeleri ekleyin; daha sonra üyelerin her biri için herhangi bir dilimi seçin ve üyeleri ekleyin o kes vb. Bu, her düğümün birçok olası yeter çoğunluğun üyesi olduğu anlamına gelir.
Her adımda yalnızca bir çekirdek dilimi seçin.
Olası bir yeter çoğunluk. Veya bir alternatif...
...diğer dilimleri seç...
…(mümkün olduğunda)…
... başka bir çoğunluk oluşturur.
Bir düğüm diğer düğümlerin hangi dilimlerde olduğunu nasıl bilir? Diğer düğümlerle ilgili diğer bilgilerle aynı şekilde: her bir düğümün, oylama durumu değiştiğinde ağa yayınladığı iletimlerden. Her yayın, gönderen düğümün dilimleri hakkında bilgi içerir. SCP teknik incelemesi bir iletişim mekanizması belirtmez. Uygulamalar genellikle şunları kullanır: mesajların ağ genelinde garantili yayınlanması için.
Federal olmayan Bizans anlaşma sisteminde yeter sayının tüm düğümlerin çoğunluğu olarak tanımlandığını hatırlayın. Bizans anlaşma sistemi şu soru bakış açısına göre tasarlanmıştır: Sistem kaç tane dürüst olmayan düğüme tahammül edebilir? N sayıda düğümden oluşan ve f arızadan kurtulacak şekilde tasarlanmış bir sistemde, bir düğüm, f tanesi kapalı olabileceğinden N−f eşlerinden geri bildirim alarak ilerleme kaydedebilmelidir. Ancak N−f eşlerinden bir yanıt aldığımıza göre, (düğümün yanıt almadığı) tüm f eşlerinin aslında dürüst olduğunu varsayabiliriz. Bu nedenle, N−f eşlerinden f tanesi (yanıtın alındığı) kötü niyetlidir. Düğümlerin aynı fikir birliğine varması için geri kalan düğümlerin çoğunluğunun dürüst olması gerekir, yani N−f'nin 2f'den büyük veya N > 3f olmasına ihtiyacımız var. Yani tipik olarak f arızalarına dayanacak şekilde tasarlanmış bir sistem toplam N=3f+1 düğüme ve 2f+1 çekirdek boyutuna sahip olacaktır. Bir teklif yeterli çoğunluk eşiğini geçtiğinde, ağın geri kalanı rakip tekliflerin başarısız olacağına ikna olur. Ağ bu şekilde sonuca yakınsar.
Ancak federal Bizans anlaşma sisteminde çoğunluk olamayacağı gibi (çünkü kimse ağın toplam boyutunu bilmiyor), çoğunluk kavramı da tamamen işe yaramaz! Sistemdeki üyelik açıksa, birisi Sybil saldırısı adı verilen saldırıyı gerçekleştirerek çoğunluğu elde edebilir: birden fazla düğüm üzerinden tekrar tekrar ağa katılarak. Peki neden geçişli dilim kapatma denilebilir? çoğunlukve rakip teklifleri nasıl bastırabiliyor?
Teknik olarak mümkün değil! İki üçlünün birbirinin çekirdek dilimlerinde izole edildiği altı düğümden oluşan bir ağ düşünün. İlk alt grup, ikincinin asla duymayacağı bir karar verebilir veya bunun tersi de geçerlidir. Bu ağın fikir birliğine varmasının (şans eseri hariç) hiçbir yolu yoktur.
Bu nedenle SCP, birleşik oylama için (ve makalenin önemli teoremlerinin uygulanması için) ağın şu şekilde adlandırılan bir özelliğe sahip olmasını gerektirir: yetersayıların kesişimi. Bu özelliğe sahip bir ağda, oluşturulabilecek herhangi iki çekirdek her zaman en az bir düğümde çakışır. Ağın hakim duyarlılığını belirlemek için bu çoğunluğa sahip olmak kadar iyidir. Sezgisel olarak bu, herhangi bir yeter kurulun X beyanını kabul etmesi halinde, başka hiçbir yeter kurulun asla başka bir şeyi kabul edemeyeceği anlamına gelir, çünkü bu yetersayı zaten X'e oy vermiş olan ilk yeter kurulun bazı düğümlerini içerecektir.
Ağda yetersayıların kesişmesi varsa...
...sonra oluşturabileceğiniz herhangi iki yeter çoğunluk...
...her zaman kesişecek.
(Elbette, örtüşen düğümlerin Bizans yalanı olduğu veya başka bir şekilde kötü olduğu ortaya çıkabilir. Bu durumda çekirdek kesişimi ağın anlaşmaya varmasına hiçbir şekilde yardımcı olmaz. Bu nedenle, SCP teknik incelemesindeki sonuçların çoğu, ağ çekirdek geçişinde kalanlar gibi açık varsayımlar Kötü düğümleri çıkardıktan sonra bile. Basit olması açısından bu varsayımları bir kenara bırakalım örtülü makalenin geri kalanında).
Bağımsız düğümlerden oluşan bir ağda güvenilir bir çekirdek geçişin mümkün olmasını beklemek mantıksız görünebilir. Fakat bunun böyle olmasının iki nedeni var.
Birinci sebep internetin kendisinin varlığıdır. İnternet, kesişen çekirdeklere sahip bağımsız düğümlerden oluşan bir ağın mükemmel bir örneğidir. İnternet'teki çoğu düğüm yalnızca birkaç yerel düğüme bağlanır, ancak bu küçük kümeler, her düğüme bir rota boyunca diğer düğümlerden ulaşılabilecek kadar örtüşür.
İkinci neden ise Stellar ödeme ağına (SCP'nin en yaygın kullanımı) özeldir. Stellar ağındaki her varlığın bir ihraççısı vardır ve Stellar'ın yönergeleri, her ihraççının geri ödeme taleplerini işlemek için ağda bir veya daha fazla düğüm belirlemesini gerektirir. İlgilendiğiniz her varlık için bu düğümleri doğrudan veya dolaylı olarak çekirdek dilimlerine dahil etmek sizin yararınıza olacaktır. Belirli bir varlıkla ilgilenen tüm düğümler için yeterli çoğunluk, en azından bu satın alma düğümlerinde örtüşecektir. Birden fazla varlıkla ilgilenen düğümler, ilgili ihraççıların tüm geri ödeme düğümlerini çekirdek dilimlerine dahil edecek ve tüm varlıkları bir araya toplamaya çalışacaklar. Ayrıca ağdaki diğer varlıklara bu şekilde bağlı olmayan varlıklar ve bağlanmamalı - bu, bu ağ için çekirdek çakışması olmayacak şekilde tasarlanmıştır (örneğin, dolar bölgesindeki bankalar bazen euro bölgesindeki bankalarla ve peso bölgesindeki bankalarla ticaret yapmak isterler, dolayısıyla aynı ağ üzerindedirler, ancak hiçbiri (bunların çoğu beyzbol kartları satan çocukların oluşturduğu ayrı bir ağla ilgilenmektedir).
Tabii ki, beklenti çoğunluk geçişi değil garanti. Diğer Bizans anlaşma sistemleri karmaşıklıklarının çoğunu yeterli çoğunluk garantisine borçludur. SCP'nin önemli bir yeniliği, yetersayı oluşturma sorumluluğunu mutabakat algoritmasının kendisinden kaldırıp uygulama düzeyine getirmesidir. Bu nedenle, her ne kadar birleştirilmiş oylama herhangi bir konuda oy kullanmaya yetecek kadar genel olsa da, güvenilirliği aslında bu anlamların daha geniş anlamına önemli ölçüde bağlıdır. Bazı varsayımsal kullanımlar, diğerleri kadar iyi bağlantılı ağlar oluşturmaya yardımcı olmayabilir.
Oylama, kabul ve onay
Birleşik oylama turunda, bir düğüm isteğe bağlı olarak bir V değeri için oy vermeye başlar. Bu, ağa bir mesaj yayınlamak anlamına gelir: "Ben N düğümüm, çekirdek dilimlerim Q ve V'ye oy veriyorum." Bir düğüm bu şekilde oy verdiğinde, asla V'ye karşı oy kullanmadığını ve asla vermeyeceğini taahhüt eder.
Eşler arası yayınlarda her düğüm diğerlerinin nasıl oy verdiğini görür. Bir düğüm bu mesajlardan yeterince topladıktan sonra çekirdek dilimlerini izleyebilir ve çekirdekleri bulmaya çalışabilir. Eğer aynı zamanda V'ye oy verecek yeterli sayıda meslektaşı görürse, devam edebilir. Benimseme V ve şu yeni mesajı ağa yayınlayın: "Ben N düğümüm, çekirdek dilimlerim Q ve V'yi kabul ediyorum." Kabul, basit oylamadan daha güçlü bir garanti sağlar. Bir düğüm V'ye oy verdiğinde asla diğer seçeneklere oy veremez. Ancak bir düğüm V'yi kabul ederse, Ağdaki hiçbir düğüm diğer seçeneği asla kabul etmeyecektir (SCP teknik incelemesindeki Teorem 8 bunu kanıtlamaktadır).
Elbette, V ile aynı fikirde olan düğüm yeter sayısının hemen oluşmaması ihtimali yüksektir. Diğer düğümler başka değerlere oy verebilir. Ancak bir düğümün basit oylamadan kabule geçmesinin başka bir yolu daha var. N, oy vermemiş olsa ve yeterli çoğunluğu görmese bile W için farklı bir değeri kabul edebilir. Oyunuzu değiştirmeye karar vermek için bkz. engelleme seti W'yi kabul eden düğümler. Bir engelleme kümesi, N çekirdek dilimlerinin her birinden bir düğümdür. Adından da anlaşılacağı gibi, engellemek başka bir anlam. Böyle bir kümedeki tüm düğümler W'yi kabul ederse, o zaman (Teorem 8'e göre) farklı bir değer alan bir çoğunluk oluşturmak asla mümkün olmayacaktır ve bu nedenle N'nin W'yi kabul etmesi de güvenlidir.
Üç çekirdek dilimli N düğümü.
BDF, N için bir engelleme kümesidir: N'nin her diliminden bir düğüm içerir.
BE ayrıca N için bir engelleme kümesidir çünkü E, N'nin iki diliminde görünür.
Ancak engelleme kümesi bir yeter sayı değildir. N'nin dilimlerinin her birinde yalnızca bir düğümün hacklenmesi yeterli olsaydı, N düğümünü istenen değeri kabul etmesi için kandırmak çok kolay olurdu. Bu nedenle, değeri kabul etmek oylamanın sonu değildir. Bunun yerine N'nin değeri onaylaması, yani onu kabul eden düğümlerin yeterli çoğunluğunu görmesi gerekir. Eğer bu kadar ileri giderse, SCP teknik incelemesinin (Teorem 11'de) kanıtladığı gibi, ağın geri kalanı da eninde sonunda aynı değeri onaylayacaktır, dolayısıyla N, birleşik oylamayı sonuç olarak belirli bir değerle sonlandıracaktır.
Federasyon oylaması.
Oylama, kabul ve onay süreci, birleşik oylamanın tam bir turunu oluşturur. Stellar mutabakat protokolü, eksiksiz bir mutabakat sistemi oluşturmak için bu turların çoğunu birleştirir.
Yıldız Konsensüs Protokolü
Bir fikir birliği sisteminin en önemli iki özelliği şunlardır: güvenlik и hayatta kalma. Bir fikir birliği algoritması, farklı katılımcılara hiçbir zaman farklı sonuçlar veremiyorsa "güvenlidir" (Bob'un tarih kopyası hiçbir zaman Carol ile çelişmeyecektir). “Yaşanabilirlik”, algoritmanın her zaman bir sonuç üreteceği, yani takılıp kalmayacağı anlamına gelir.
Açıklanan federal oylama prosedürü zararsız yani bir düğüm V'nin değerini doğrularsa, başka hiçbir düğüm diğer değeri onaylamayacaktır. Ancak “başka bir manayı teyit etmeyecek” demek mutlaka bir şeyi teyit edeceği anlamına gelmez. Katılımcılar o kadar çok farklı değere oy verebilir ki hiçbir şey kabul eşiğine ulaşamaz. Bu, federal oylamada hiçbir şeyin olmadığı anlamına gelir. hayatta kalma.
Stellar fikir birliği protokolü, hem güvenliği hem de hayatta kalmayı sağlayacak şekilde birleşik oylamayı kullanır. (SCP'nin güvenlik ve hayatta kalma garantilerinin teorik bir sınırı vardır. Tasarım çok güçlü bir güvenlik garantisi seçiyor ve hayatta kalma konusundaki küçük bir hafifletmeden fedakarlık ediyor, ancak yeterli zaman verildiğinde fikir birliğine varılması oldukça muhtemel.) Özetle, fikir, birden fazla değer üzerinde birden fazla birleşik oya sahip olmak ve bunlardan biri aşağıda açıklanan SCP oylama aşamalarının tamamını tamamlayıncaya kadar.
SCP'nin fikir birliği istediği değerler işlem geçmişi, öğle yemeği siparişi veya başka bir şey olabilir, ancak bunların kabul edilen veya onaylanan değerler olmadığını belirtmek önemlidir. Bunun yerine, federal oylama şu şekilde gerçekleşir: Bu değerlerle ilgili ifadeler.
Federal oylamanın ilk turu bugün yapılacak adaylık aşaması (adaylık aşaması), belki de V'nin birçok farklı değeri için "V'yi aday gösteriyorum" gibi bir dizi ifade üzerinde. Aday göstermenin amacı, kabul ve onaydan geçen bir veya daha fazla ifadeyi bulmaktır.
Doğrulanabilir adaylar bulduktan sonra SCP, amacın belirli bir adayı bulmak olduğu oylama aşamasına geçer. бюллетень (yani önerilen değer için bir kapsayıcı) ve bildirebilecek bir yeter sayı işlemek bunun için (taahhüt). Yeter sayı ile oylama yapılırsa değeri oy birliği olarak kabul edilir. Ancak bir düğümün oy pusulası taahhüdüne oy verebilmesi için önce onaylaması gerekir iptal tüm oy pusulaları daha düşük sayaç değerine sahip. Bu adımlar (onaylanabilecek bir oy pusulası bulmak için oy pusulalarının iptal edilmesi), birden fazla oy pusulası talebine ilişkin birden fazla turlu birleşik oylamayı içerir.
Aşağıdaki bölümlerde aday gösterme ve oylama daha ayrıntılı olarak açıklanmaktadır.
Adaylık
Aday gösterme aşamasının başlangıcında, her düğüm kendiliğinden V için bir değer seçebilir ve "V'yi aday gösteriyorum" ifadesine oy verebilir. Bu aşamadaki amaç, federal bir oylama yoluyla bazı değerlerin aday gösterilmesini onaylamaktır.
Belki yeterli sayıda düğüm, hiçbir adaylığın kabul eşiğine ulaşamayacağı kadar farklı tekliflere oy verir. Bu nedenle, düğümler kendi adaylık oylarını yayınlamanın yanı sıra, akranlarının adaylıklarını da "yansıtır". Yankı, eğer bir düğüm V adaylığına oy verirse ancak W adaylığına oy veren bir komşudan gelen bir mesaj görürse, artık hem V hem de W'ye oy vereceği anlamına gelir. farklı adaylar.SCP, bu oyları düzenleyecek bir mekanizma içerir.Kısacası, bir düğümün bakış açısından bir eşin "önceliğini" belirleyen bir formül vardır ve yalnızca yüksek öncelikli düğümlerin oyları yansıtılır.Adaylık süresi ne kadar uzun olursa eşik ne kadar düşük olursa düğüm, oylarını yansıtacağı eş kümesini genişletir.Öncelik formülü, girdilerinden biri olarak yuva numarasını içerir, dolayısıyla bir yuva için yüksek öncelikli bir eş, diğer yuva için düşük öncelikli bir eş olabilir. diğeri ve tam tersi).
Kavramsal olarak adaylık paraleldir; hem V hem de W ayrı federal oylardır ve her biri bireysel olarak kabul veya onay elde etme kapasitesine sahiptir. Uygulamada, SCP protokol mesajları bu bireysel oyları bir arada paketler.
Her ne kadar V'nin adaylığına oy vermek, V'nin adaylığına asla karşı oy kullanmama sözü olsa da, "karşı"nın ne anlama geldiği uygulama düzeyinde - bu durumda SCP - belirlenir. SCP, "X'i aday gösteriyorum" oyu ile çelişen bir ifade görmüyor, yani "X'i aday gösteriyorum" mesajı yok, dolayısıyla düğüm herhangi bir değeri aday göstermek için oy kullanabilir. Bu adaylıkların çoğu hiçbir yere varmayacak, ancak sonunda düğüm bir veya daha fazla değeri kabul edebilecek veya onaylayabilecektir. Bir aday onaylandıktan sonra, o olur aday.
Birleşik oylama kullanılarak SCP adaylığı. Eşler tarafından öne sürülen ve düğüm tarafından “yansıyan” birçok “B” değeri olabilir.
Aday gösterme birden fazla onaylanmış adayla sonuçlanabilir. Bu nedenle SCP, uygulama katmanının adayları tek bir grupta birleştirmeye yönelik bir yöntem sağlamasını gerektirir. bileşik (bileşik). Birleştirme yöntemi herhangi bir şey olabilir. Önemli olan şu ki, eğer bu yöntem deterministikse, o zaman her düğüm aynı adayları birleştirecektir. Öğle yemeği oylama sisteminde "birleşme" basitçe iki adaydan birinin reddedilmesi anlamına gelebilir. (Ancak deterministik bir şekilde: her düğümün sıfırlamak için aynı değeri seçmesi gerekir. Örneğin, alfabetik sırayla önceki seçim). İşlem geçmişinin oylandığı Stellar ödeme ağında, önerilen iki adayın birleştirilmesi, içerdikleri işlemlerin ve iki zaman damgasından en sonuncusunun birleştirilmesini içerir.
SCP teknik incelemesi (Teorem 12), uzatma aşamasının sonunda ağın en sonunda tek bir bileşik halinde birleştiğini kanıtlar. Ancak bir sorun var: Birleşik oylama eşzamansız bir protokoldür (SCP gibi). Başka bir deyişle, düğümler zamana göre değil, yalnızca gönderdikleri mesajlara göre koordine edilir. Düğümün bakış açısından, ne zaman olacağı belli değil Bitti uzatma aşaması. Her ne kadar tüm düğümler eninde sonunda aynı bileşiğe ulaşsa da, yol boyunca farklı rotalar izleyebilir, yol boyunca farklı bileşik adaylar yaratabilirler ve hangisinin son olduğunu asla bilemezler.
Ama bu normal. Adaylık sadece hazırlıktır. Önemli olan, süreçte ortaya çıkan fikir birliğine varmak için aday sayısını sınırlamaktır. koşma (oylama).
Koşma
Bülten bir çift burada sayaç 1'den başlayan bir tam sayıdır ve değer aday gösterme aşamasındaki bir adaydır. Bu, bir düğümün kendi adayı veya o düğüm tarafından kabul edilen komşu düğümün adayı olabilir. Kabaca söylemek gerekirse, bir oylama, oy pusulalarında potansiyel olarak çok sayıda federal oy bulundurarak ağı bazı oy pusulalarında bazı adaylar üzerinde fikir birliğine varmaya zorlamak için tekrarlanan girişimleri içerir. Oy pusulalarındaki sayaçlar yapılan girişimleri takip ediyor ve daha yüksek sayımlı oy pusulaları, daha düşük sayımlı oy pusulalarına göre öncelikli. Eğer bülten takılıp kalıyor, yeni bir oylama başlıyor, şimdi oy pusulasında .
Ayırt etmek önemlidir anlam (Örneğin öğle yemeği sırası ne olmalı: pizza mı yoksa salata mı), bültenler (karşı-değer çifti) ve açıklama oy pusulaları hakkında. SCP turu, özellikle aşağıdaki ifadelere ilişkin çeşitli federal oylama turlarını içerir:
- "B oylamasını yapmaya hazırım" ve
- "B oy pusulasının taahhüdünü duyuruyorum"
Belirli bir düğümün perspektifinden, "B oy pusulasını veriyorum" ifadesini onaylayabileceği (yani kabul eden bir yeter çoğunluk bulduğunda) bir B oy pusulası bulduğunda fikir birliğine varılır. Bu noktadan itibaren B'de belirtilen değere göre hareket etmek güvenlidir; örneğin öğle yemeği için bu siparişi vermek. denir dışsallaştırma anlamlar. Oylamanın kabulü onaylandıktan sonra bir düğüm, başka herhangi bir düğümün aynı değeri dışsallaştırdığından veya gelecekte bunu yapacağından emin olabilir.
Her ne kadar birçok federal oylama kavramsal olarak birçok farklı oy pusulasına ilişkin talepler üzerinden gerçekleştirilse de, her mesaj bir dizi oy pusulasını kapsadığı için çok fazla mesaj alışverişinde bulunmuyorlar. Dolayısıyla bir mesaj aynı anda birçok federal oyun durumunu teşvik ediyor, örneğin: "Oyların kesinleştirilmesini kabul ediyorum: önce "
"Hazırlanmak" ve "taahhüt etmek" terimleri ne anlama geliyor?
Bir düğüm, diğer düğümlerin farklı değerlere sahip oy pusulaları kullanmayacağından emin olduğunda oylama yapmak için oy kullanır. Başvuruyu hazırlamanın amacı buna ikna etmektir. "B oy pusulasını vermeye hazırım" şeklinde bir oylama, asla B'den küçük yani daha küçük sayımlı bir oylama yapılmayacağına dair bir sözdür (SCP, oy pusulalarındaki değerlerin belirli bir sırada olmasını gerektirir. Bu nedenle haber bülteni) az , eğer N1 ise
"B oy pusulasını vermeye hazırım" neden "B'den küçük oy pusulaları vermeyeceğime söz veriyorum" anlamına geliyor? Çünkü SCP, iptali taahhüt etmenin zıttı olarak tanımlar. Bir oy pusulasının hazırlanmasına yönelik bir oylama aynı zamanda diğer bazı oyların geçersiz sayılmasına yönelik bir oyu da içerir ve daha önce tartıştığımız gibi, bir şeye oy vermek, ona asla karşı oy kullanmama sözü vermektir.
Bir taahhüt yayınlamadan önce, bir düğüm ilk olarak hazırlandığını onaylayabileceği bir bülten bulmalıdır. Başka bir deyişle, yeterli çoğunluğu kabul eden bir oylama bulana kadar, muhtemelen birçok farklı oylamada “B oy pusulasını vermeye hazırım” konulu federal bir oylama gerçekleştirir.
Oylamayı hazırlamak için oy pusulaları nereden geliyor? İlk olarak düğüm, C'nin aday gösterme aşamasında üretilen bileşik aday olduğu <1,C>'ye oy vermek için hazırlıkları yayınlar. Ancak, oylama hazırlıkları başladıktan sonra bile aday göstermeler, yeni oy pusulalarında başka adayların görünmesine neden olabilir. Bu arada, eşlerin farklı adayları olabilir ve düğümü de bunu kabul etmeye ikna edecek "B2 oylamasını yapmaya hazırım" ifadesini kabul eden bir engelleme seti oluşturabilirler. Son olarak, mevcut oy pusulalarının takılıp kalması durumunda daha yüksek sayımlarla yeni oy pusulalarında yeni federal oylama turları üreten bir zaman aşımı mekanizması bulunmaktadır.
Düğüm, hazırlandığını onaylayabileceği bir B oy pusulası bulur bulmaz yeni bir "B oy pusulasını onayla" mesajını yayınlar. Bu oy, eşlere düğümün B'den asla vazgeçmeyeceğini söyler. Aslında, eğer B bir oy pusulasıysa , ardından “Oylamayı onayla " her oylamanın hazır olması yönünde oy kullanmaya koşulsuz onay anlamına gelir <∞, s>'ye. Bu ekstra değer, diğer eşlerin henüz protokolün erken aşamalarında olmaları durumunda taahhüt eşlerine yetişmelerine yardımcı olur.
Bu aşamada bunların asenkron protokoller olduğunu bir kez daha vurgulamakta fayda var. Bir düğümün bir taahhüt için olumlu oy göndermesi, eşlerinin de olumlu oy gönderdiği anlamına gelmez. Bazıları hala oylamaya hazırlık amacıyla ifadelere oy veriyor olabilir, diğerleri ise anlamı zaten dışsallaştırmış olabilir. SCP, bir düğümün, aşamasına bakılmaksızın her tür eş mesajını nasıl işlemesi gerektiğini açıklar.
"Bir taahhütte bulunduğumu duyurdum" mesajı görüntülenirse » alınamıyor veya onaylanamıyor, yani mesajın kabul edilme veya onaylanma olasılığı veya - veya her durumda, düğüm hiçbir zaman iptal etmeyeceğine söz verdiği için başkası değil, C değeri olan herhangi bir oylama . Bir düğüm bir taahhüt için oy yayınladığında, fikir birliğinin ne kadar ileri gittiğine bağlı olarak C olacak ya da hiçbir şey olmayacak. Ancak bu, düğümün C'yi dışsallaştırması için henüz yeterli değildir. Bazı Bizans eşleri (güvenlik varsayımlarımıza göre yeterli çoğunluktan daha azını oluşturan) düğüme yalan söyleyebilir. Bazı oylamaların (veya oylamaların aralığının) kabul edilmesi ve ardından onaylanması, düğüme sonunda C'yi dışsallaştırma güvenini veren şeydir.
SCP, federal oylama yoluyla oy kullanıyor. Gösterilmiyor: Zamanlayıcı herhangi bir zamanda kapanarak oy pusulasındaki sayıyı artırabilir (ve muhtemelen ek aday adaylarından oluşan yeni bir bileşik oluşturabilir).
Ve hepsi bu! Ağ bir kez fikir birliğine vardığında bunu tekrar tekrar yapmaya hazırdır. Stellar ödeme ağında bu durum yaklaşık olarak her 5 saniyede bir gerçekleşir: SCP tarafından garanti edilen hem güvenlik hem de hayatta kalma gerektiren bir başarı.
SCP bunu birden fazla federal oylama turuna güvenerek başarabilir. Birleşik oylama, yetersayı dilimleri kavramıyla mümkün olur: her düğümün (öznel) yetersayısının bir parçası olarak güvenmeye karar verdiği eş kümeleri. Bu yapılanma, açık üyeliğin ve Bizans aldatmacalarının olduğu bir ağda bile fikir birliğine varılabileceği anlamına geliyor.
daha fazla okuma
- Orijinal SCP teknik incelemesini şu adreste bulabilirsiniz: Ve uygulanmasına ilişkin taslak şartname.
- SCP protokolünün orijinal yazarı David Mazier, bunu basitleştirilmiş (ama yine de teknik) bir şekilde açıklıyor. .
- Bu makalede “madencilik” veya “çalışma kanıtı” terimlerini bulamadığınıza şaşırmış olabilirsiniz. SCP bu yöntemleri kullanmaz ancak diğer bazı fikir birliği algoritmaları kullanır. Zane Witherspoon erişilebilir yazdı .
- SCP'nin tam turunda fikir birliğine varan basit bir ağ.
- SCP uygulamalarıyla ilgilenen okuyucular için: bkz. Stellar ödeme ağı tarafından kullanılan veya SCP'nin daha iyi anlaşılması için yazdım.
Kaynak: habr.com