Protocolul de consens Stellar a fost descris pentru prima dată în David Mazier în 2015. Acesta este un „sistem de acord federal bizantin” care permite rețelelor de calcul descentralizate, fără lider, să ajungă eficient la un consens asupra unei decizii. Rețeaua de plăți Stellar folosește Stellar Consensus Protocol (SCP) pentru a menține un istoric consecvent al tranzacțiilor, care este vizibil pentru toți participanții.
Protocoalele de consens sunt considerate greu de înțeles. SCP este mai simplu decât majoritatea dintre ei, dar încă împărtășește această reputație - parțial datorită ideii greșite că „votul federal”, care face obiectul primei jumătate a articolului științific, este SCP. Dar asta nu este adevărat! Acesta este doar un bloc important pe care îl folosește a doua jumătate a articolului real Protocolul de consens stelar.
În acest articol vom explica pe scurt ce este un „sistem de acorduri”, ce îl poate face „bizantin” și de ce să facă sistemul bizantin „federal”. Vom explica apoi procedura de vot federal descrisă în articolul SCP și, în final, vom explica protocolul SCP în sine.
Sisteme de acorduri
Un sistem de acorduri permite unui grup de participanți să ajungă la un consens asupra unui subiect, cum ar fi ce să comande pentru prânz.
La Interstellar, am implementat propriul nostru sistem de acorduri de mese: comandăm ceea ce spune managerul nostru de operațiuni, John. Acesta este un sistem de acord simplu și eficient. Cu toții avem încredere în John și credem că va găsi ceva interesant și hrănitor în fiecare zi.
Dar dacă John abuzează de încrederea noastră? El poate decide de unul singur că ar trebui să devenim cu toții vegani. Peste o săptămână sau două, probabil îl vom răsturna și vom preda puterea lui Elizabeth. Dar deodată iubește avocado cu hamsii și crede că toată lumea ar trebui să fie așa. Puterea corupe. Așa că e mai bine să găsești o metodă mai democratică: o modalitate de a te asigura că sunt luate în considerare diferite preferințe, asigurând în același timp un rezultat în timp util și fără ambiguități, astfel încât nimeni să nu ajungă să comande prânzul, sau cinci persoane să plaseze comenzi diferite, sau discuția. se prelungește până seara.
S-ar părea că soluția este simplă: ține un vot! Dar aceasta este o impresie înșelătoare. Cine va strânge buletinele de vot și va raporta rezultatele? Și de ce ar trebui alții să creadă ce spune el? Poate că putem la început votează un lider în care avem încredere să conducă votul - dar care îl va conduce în primul rând prin vot? Dacă nu putem fi de acord cu un lider? Sau ce se întâmplă dacă ajungem la o înțelegere, dar acest lider rămâne blocat într-o întâlnire sau merge în concediu medical?
Probleme similare apar în rețelele de calculatoare distribuite. Toți participanții sau nodurile trebuie să cadă de acord asupra unei decizii, cum ar fi al cui este rândul să actualizeze un fișier partajat sau să elimine o sarcină din coada de procesare. Într-o rețea de criptomonede, nodurile trebuie să aleagă în mod repetat cum arată povestea completă din mai multe versiuni posibile, care uneori sunt în conflict. Acest acord de rețea asigură destinatarului că moneda este (a) valabilă (nu este contrafăcută) și (b) nu a fost încă cheltuită în altă parte. Acest lucru asigură, de asemenea, că va putea cheltui monedele în viitor, deoarece noul destinatar va avea aceleași garanții din aceleași motive.
Orice sistem de consens dintr-o rețea de calcul distribuită trebuie să fie tolerant la erori: trebuie să producă rezultate consistente în ciuda erorilor, cum ar fi legăturile lente, nodurile care nu răspund și ordonarea incorectă a mesajelor. bizantin Sistemul de acorduri este în plus rezistent la erorile „bizantine”: noduri care oferă informații false, fie din cauza unei erori, fie într-o încercare deliberată de a submina sistemul sau de a obține un avantaj. Toleranța „bizantină” la greșeală - abilitatea de a avea încredere într-o decizie de grup chiar și atunci când unii membri ai grupului pot minți sau nu respectă în alt mod regulile de luare a deciziilor - se numește care a încercat să coordoneze atacul. la Anthony Stevens.
Luați în considerare proprietarul de monede criptografice Alice, care trebuie să aleagă între să cumpere înghețată delicioasă de la Bob și să plătească datoria lui Carol. Poate că Alice vrea să-i plătească pe amândoi deodată, cheltuind în mod fraudulos aceeași monedă. Pentru a face acest lucru, ea trebuie să convingă computerul lui Bob că moneda nu a fost niciodată plătită lui Carol și să convingă computerul lui Carol că moneda nu a fost niciodată plătită lui Bob. Sistemul bizantin de acorduri face acest lucru practic imposibil, folosind o formă de regulă majoritară numită cvorum. Un nod dintr-o astfel de rețea refuză să treacă la o anumită versiune a istoriei până când vede că un număr suficient de colegi - un cvorum - sunt de acord cu o astfel de tranziție. Odată ce se întâmplă acest lucru, ei vor forma un bloc de vot suficient de mare pentru a forța nodurile de rețea rămase să fie de acord cu decizia lor. Alice poate forța unele noduri să mintă în numele ei, dar dacă rețeaua este suficient de mare, încercarea ei va fi depășită de voturile nodurilor cinstite.
Câte noduri sunt necesare pentru cvorum? Cel puțin, o majoritate, sau mai bine zis, o majoritate calificată pentru combaterea erorilor și fraudelor. Dar pentru a număra majoritatea, trebuie să știți numărul total de participanți. La biroul Interstellar sau la alegerile raionale, aceste cifre sunt ușor de aflat. Dar dacă grupul dvs. este o rețea puțin definită în care nodurile pot intra și ieși după bunul plac fără aprobarea centrului, atunci aveți nevoie federal un sistem de acord bizantin capabil să determine cvorumurile nu dintr-o listă predeterminată de noduri, ci în mod dinamic, dintr-un instantaneu în continuă schimbare și inevitabil incomplet al nodurilor la un moment dat în timp.
Poate părea imposibil de a crea un cvorum din perspectiva unui singur nod într-o rețea vastă, dar este posibil. Un astfel de cvorum poate garanta chiar rezultatele votului descentralizat. Cartea albă SCP arată cum se face acest lucru folosind o procedură numită prin vot federal.
Pentru nerăbdători
Restul articolului descrie votul federat și protocolul de consens Stellar mai detaliat. Dacă nu sunteți interesat de detalii, iată o prezentare generală a procesului.
- Nodurile desfășoară runde de vot federal asupra „candidaților”. O rundă de vot federal înseamnă:
- Nodul votează pentru o afirmație, de exemplu, „propun valoarea lui V”;
- Nodul ascultă vocile colegilor până găsește una care poate „primi”;
- Nodul caută un „cvorum” pentru această afirmație. Un cvorum „confirmă” candidatul.
- Odată ce un nod poate confirma unul sau mai mulți nominalizați, încearcă să „pregătească” „buletinul” prin mai multe runde de vot federal.
- Odată ce un nod este capabil să verifice că buletinul de vot este gata, încearcă să îl angajeze prin și mai multe runde de vot federal.
- Odată ce un nod poate confirma o angajare a unui buletin de vot, poate „externa” valoarea acelui buletin de vot folosindu-l ca rezultat de consens.
Acești pași implică mai multe runde de vot federat, care formează colectiv o rundă SCP. Să aruncăm o privire mai atentă la ceea ce se întâmplă la fiecare pas.
Votul federat
Votul federal este o procedură pentru a determina dacă rețeaua poate conveni asupra unei propuneri. În runda de vot, fiecare nod trebuie să aleagă una dintre cele mai multe valori posibile. Nu poate face acest lucru decât dacă are încredere că alte noduri din rețea nu vor alege un rezultat diferit. Pentru a se asigura de acest lucru, nodurile schimbă un val de mesaje înainte și înapoi, astfel încât toată lumea confirmatCă cvorum noduri ia acelasi lucru decizie. Restul acestei secțiuni explică termenii din această propoziție și modul în care are loc întreaga procedură.
Cvorumuri și segmente de cvorum
Să începem prin a defini un cvorum. După cum am discutat mai sus, într-o rețea descentralizată cu apartenență dinamică, este imposibil să știm în avans numărul de noduri și, prin urmare, de câte sunt necesare pentru majoritatea. Votul federat rezolvă această problemă prin introducerea unei noi idei reducere a cvorumului (porțiune de cvorum): un set mic de colegi în care un nod are încredere pentru a comunica informațiile despre starea votului către restul rețelei. Fiecare nod își definește propria secțiune de cvorum (din care devine membru de facto).
Formarea cvorumului începe cu o reducere a cvorumului. Pentru fiecare nod, se adaugă nodurile tăiate. Apoi se adaugă termenii felii aceste noduri și așa mai departe. Pe măsură ce continuați, există tot mai multe noduri pe care nu le puteți adăuga, deoarece sunt deja incluse în felie. Când nu mai există noduri noi de adăugat, procesul se oprește: am format un cvorum prin „închiderea tranzitivă” a secțiunii de cvorum a nodului inițial.
Pentru a găsi cvorum de la un nod dat...
... adăugați membri ai feliei sale...
... apoi adăugăm membrii slice ai acestor noduri.
Continuăm până când nu mai există noduri de adăugat.
Nu mai sunt noduri de adăugat. Acesta este un cvorum.
De fapt, fiecare nod poate apărea în mai multe felii. Pentru a forma un cvorum, selectați doar una dintre felii și adăugați membri; apoi selectați orice felie pentru fiecare dintre membri și adăugați membri ea tăiat și așa mai departe. Aceasta înseamnă că fiecare nod este membru al mai multor cvorumuri posibile.
Selectați o singură porțiune de cvorum la fiecare pas.
Un cvorum posibil. Sau o alternativa...
...selectați alte felii...
…(când este posibil)…
... creează un alt cvorum.
Cum știe un nod în ce felii se află alte noduri? La fel ca și alte informații despre alte noduri: de la transmisiile pe care fiecare nod le transmite în rețea atunci când starea sa de vot se schimbă. Fiecare difuzare include informații despre feliile nodului expeditor. Cartea albă SCP nu specifică un mecanism de comunicare. Implementările folosesc de obicei pentru difuzarea garantată a mesajelor în întreaga rețea.
Amintiți-vă că în sistemul de acorduri bizantin non-federal, un cvorum este definit ca majoritatea tuturor nodurilor. Sistemul de acord bizantin este conceput din punctul de vedere al întrebării: câte noduri necinstite poate tolera sistemul? Într-un sistem de N noduri concepute pentru a supraviețui f defecțiuni, un nod ar trebui să poată face progrese primind feedback de la N-f colegi, deoarece f dintre ei ar putea fi opriți. Dar, după ce a primit un răspuns de la N−f peers, putem presupune că toți f peers (de la care nodul nu a primit un răspuns) sunt de fapt sinceri. Astfel, f din N−f colegi (de la care a fost primit răspunsul) sunt rău intenționați. Pentru ca nodurile să ajungă la același consens, majoritatea nodurilor rămase trebuie să fie sincere, adică avem nevoie ca N−f să fie mai mare decât 2f sau N > 3f. Deci, de obicei, un sistem proiectat să supraviețuiască f defecțiuni va avea un total de N=3f+1 noduri și o dimensiune a cvorumului de 2f+1. Odată ce o propunere depășește pragul de cvorum, restul rețelei este convins că orice propuneri concurente vor eșua. Acesta este modul în care rețeaua converge către rezultat.
Dar într-un sistem federal de acord bizantin, nu numai că nu poate exista o majoritate (pentru că nimeni nu știe dimensiunea totală a rețelei), dar conceptul de majoritate este complet inutil! Dacă apartenența la sistem este deschisă, atunci cineva poate obține o majoritate pur și simplu efectuând un așa-numit atac Sybil: alăturarea în mod repetat la rețea prin mai multe noduri. Deci, de ce poate fi numită închiderea tranzitivă a feliei cvorum, și cum este capabil să suprime propunerile concurente?
Tehnic, în niciun caz! Imaginați-vă o rețea de șase noduri, în care două triplete sunt izolate unul în secțiunile de cvorum ale celuilalt. Primul subgrup poate lua o decizie despre care al doilea nu va auzi niciodată și invers. Nu există nicio modalitate ca această rețea să ajungă la un consens (decât din întâmplare).
Prin urmare, SCP cere ca pentru votul federat (și pentru ca teoremele importante ale lucrării să se aplice), rețeaua trebuie să aibă o proprietate numită intersecția cvorumurilor. Într-o rețea cu această proprietate, oricare două cvorumuri care pot fi construite se suprapun întotdeauna în cel puțin un nod. Pentru a determina sentimentul predominant al rețelei, acest lucru este la fel de bun ca și a avea o majoritate. Intuitiv, aceasta înseamnă că, dacă vreun cvorum este de acord cu declarația X, niciun alt cvorum nu poate fi de acord cu nimic altceva, deoarece va include în mod necesar un nod din primul cvorum care a votat deja pentru X.
Dacă există o intersecție de cvorumuri în rețea...
...atunci oricare două cvorumuri pe care le puteți construi...
...se vor intersecta întotdeauna.
(Desigur, nodurile care se suprapun se pot dovedi a fi bizantine sau altfel rele. În acest caz, intersecția cvorumului nu ajută deloc rețeaua să fie de acord. Din acest motiv, multe dintre rezultatele din cartea albă SCP se bazează pe ipoteze explicite, cum ar fi ceea ce rămâne în trecerea cvorumului rețelei chiar și după îndepărtarea nodurilor dăunătoare. Pentru simplitate, să lăsăm aceste presupuneri implicit în restul articolului).
Poate părea nerezonabil să ne așteptăm că o trecere sigură a cvorumului este posibilă într-o rețea de noduri independente. Dar există două motive pentru care este așa.
Primul motiv este existența internetului în sine. Internetul este un exemplu perfect de rețea de noduri independente cu cvorumuri care se intersectează. Majoritatea nodurilor de pe Internet se conectează doar la câteva alte noduri locale, dar aceste seturi mici se suprapun suficient de mult încât fiecare nod poate fi atins de la orice alt nod de-a lungul unei rute.
Al doilea motiv este specific rețelei de plată Stellar (cea mai comună utilizare a SCP). Fiecare activ din rețeaua Stellar are un emitent, iar ghidurile Stellar impun fiecărui emitent să desemneze unul sau mai multe noduri din rețea pentru a procesa cererile de răscumpărare. Este în interesul dvs. să includeți direct sau indirect aceste noduri în secțiunile de cvorum pentru fiecare activ care vă interesează. Cvorumurile pentru toate nodurile interesate de un anumit activ se vor suprapune apoi cel puțin la acele noduri de răscumpărare. Nodurile interesate de mai multe active vor include toate nodurile de răscumpărare ale emitenților respectivi în secțiunile lor de cvorum și vor căuta să pună în comun toate activele. În plus, orice bunuri care nu sunt conectate în acest fel la alții din rețea și nu trebuie conectat - acest lucru este conceput astfel încât să nu existe o suprapunere de cvorum pentru această rețea (de exemplu, băncile din zona dolarului doresc uneori să tranzacționeze cu bănci din zona euro și bănci din zona peso, deci sunt în aceeași rețea, dar nici una dintre ei le pasă de rețeaua separată de copii care vând cărți de baseball).
Desigur, așteptare trecerea cvorumului nu este garanție. Alte sisteme de acorduri bizantine datorează o mare parte din complexitatea lor garanției cvorumurilor. O inovație importantă a SCP este că înlătură responsabilitatea creării de cvorumuri din algoritmul de consens în sine și o aduce la nivelul aplicației. Astfel, deși votul federat este suficient de general pentru a vota orice problemă, fiabilitatea sa depinde de fapt în mod critic de sensul mai larg al acestor semnificații. Unele utilizări ipotetice pot să nu fie la fel de favorabile pentru crearea de rețele bine conectate ca altele.
Vot, acceptare și confirmare
Într-o rundă de vot federată, un nod începe opțional să voteze pentru o valoare V. Aceasta înseamnă difuzarea unui mesaj către rețea: „Sunt nodul N, secțiunile mele de cvorum sunt Q și votez pentru V”. Când un nod votează în acest fel, promite că nu a votat niciodată împotriva lui V și nu va vota niciodată.
În emisiunile peer-to-peer, fiecare nod vede cum votează ceilalți. Odată ce un nod a strâns suficient din aceste mesaje, poate urmări segmentele de cvorum și poate încerca să găsească cvorumuri. Dacă vede un cvorum de colegi care votează și pentru V, poate continua adopţie V și a difuzat acest nou mesaj în rețea: „Sunt nodul N, secțiunile mele de cvorum sunt Q și accept V”. Acceptarea oferă o garanție mai puternică decât votul simplu. Când un nod votează pentru V, nu poate vota niciodată pentru alte opțiuni. Dar dacă un nod acceptă V, niciun nod din rețea nu va accepta vreodată cealaltă opțiune (Teorema 8 din documentul SCP demonstrează acest lucru).
Desigur, există o probabilitate mare ca să nu existe imediat un cvorum de noduri care să fie de acord cu V. Alte noduri pot vota pentru alte valori. Dar există o altă modalitate prin care un nod poate trece de la votul simplu la acceptare. N poate accepta o valoare diferită pentru W, chiar dacă nu a votat pentru aceasta și chiar dacă nu vede un cvorum pentru aceasta. Pentru a decide să vă schimbați votul, vedeți set de blocare noduri care au acceptat W. Un set de blocare este un nod din fiecare dintre secțiunile de cvorum N. După cum sugerează și numele, poate bloc orice alt sens. Dacă toate nodurile dintr-o astfel de mulțime acceptă W, atunci (prin teorema 8) nu va fi niciodată posibil să se formeze un cvorum care să ia o valoare diferită și, prin urmare, este, de asemenea, sigur ca N să accepte W.
Nodul N cu trei felii de cvorum.
BDF este un set de blocare pentru N: include un nod din fiecare dintre feliile de N.
BE este, de asemenea, un set de blocare pentru N, deoarece E apare în două felii de N.
Dar setul de blocare nu este un cvorum. Ar fi prea ușor să păcăliți nodul N să accepte valoarea dorită dacă ar fi suficient să piratați doar un nod în fiecare dintre feliile de N. Prin urmare, acceptarea valorii nu este sfârșitul votării. În schimb, N trebuie să confirme valoarea, adică să vadă un cvorum de noduri care o acceptă. Dacă se ajunge atât de departe, atunci, așa cum demonstrează documentul SCP (în Teorema 11), restul rețelei va confirma în cele din urmă aceeași valoare, așa că N va încheia votul federat cu o anumită valoare ca rezultat.
Votul federat.
Procesul de vot, acceptare și confirmare constituie o rundă completă de vot federal. Protocolul de consens Stellar combină multe dintre aceste runde pentru a crea un sistem de consens complet.
Protocolul de consens stelar
Cele mai importante două proprietăți ale unui sistem de consens sunt − siguranță и supraviețuirea. Un algoritm de consens este „sigur” dacă nu poate da niciodată rezultate diferite diferiților participanți (copia istoriei lui Bob nu o va contrazice niciodată pe Carol). „Livability” înseamnă că algoritmul va produce întotdeauna un rezultat, adică nu se va bloca.
Procedura de vot federală descrisă sigur în sensul că dacă un nod confirmă valoarea lui V, niciun alt nod nu va confirma cealaltă valoare. Dar „nu va confirma un alt sens” nu înseamnă că va confirma neapărat ceva. Participanții pot vota atât de multe valori diferite încât nimic nu va atinge pragul de acceptare. Aceasta înseamnă că în votul federal nu există supraviețuirea.
Protocolul de consens Stellar folosește votul federat într-un mod care asigură atât securitatea, cât și supraviețuirea. (Garanțiile de securitate și supraviețuire ale SCP au o limită teoretică. Designul alege o garanție de securitate foarte puternică, sacrificând o mică atenuare a capacității de supraviețuire, dar având suficient timp, este foarte probabil să se ajungă la un consens.) Pe scurt, ideea este de a avea mai multe voturi federate pe mai multe valori până când una dintre ele trece prin toate fazele de vot SCP descrise mai jos.
Valorile asupra cărora SCP caută consens ar putea fi istoricul tranzacțiilor sau o comandă de prânz sau altceva, dar este important de menționat că acestea nu sunt valorile care sunt acceptate sau confirmate. În schimb, votul federal are loc conform afirmații despre aceste valori.
Primele tururi de scrutin federal au loc etapa de nominalizare (faza de nominalizare), pe un set de afirmații precum „Eu nominalizez V”, poate pentru multe valori diferite ale lui V. Scopul nominalizării este de a găsi una sau mai multe declarații care trec prin acceptare și confirmare.
După ce a găsit candidați verificabili, SCP trece la faza de vot, unde scopul este de a găsi un anumit buletin (adică un container pentru valoarea propusă) și un cvorum care poate declara comite pentru ea (comite). Dacă un cvorum angajează un vot, valoarea acestuia este acceptată ca consens. Dar, înainte ca un nod să poată vota un vot de vot, trebuie mai întâi să confirme anulare toate buletinele de vot cu o valoare de contor mai mică. Acești pași – anularea buletinelor de vot pentru a găsi unul care poate fi angajat – implică mai multe runde de vot federal pentru mai multe cereri de vot.
Următoarele secțiuni descriu nominalizarea și votul mai detaliat.
Numire
La începutul fazei de nominalizare, fiecare nod poate alege spontan o valoare pentru V și poate vota pentru afirmația „Eu nominalizez V”. Scopul în această etapă este de a confirma nominalizarea unei anumite valori printr-un vot federal.
Poate că suficiente noduri votează propuneri suficient de diferite încât nicio nominalizare nu poate atinge pragul de acceptare. Prin urmare, pe lângă difuzarea propriilor voturi de nominalizare, nodurile „reflectează” nominalizările colegilor lor. Eco înseamnă că, dacă un nod votează pentru nominalizarea V, dar vede un mesaj de la un vecin care votează pentru nominalizarea W, acum va vota atât pentru V, cât și pentru W. (Nu toate voturile colegilor sunt reluate în timpul nominalizării, deoarece acest lucru poate duce la o explozie de diferiți nominalizați. SCP include un mecanism de reglementare a acestor voturi. Pe scurt, există o formulă de determinare a „priorității” unui egal din punctul de vedere al unui nod și se reflectă doar voturile nodurilor cu prioritate ridicată. Cu cât nominalizarea este mai lungă. are, cu atât pragul este mai mic, astfel încât nodul extinde setul de colegi ale căror voturi le va reflecta. Formula de prioritate include numărul de slot ca una dintre intrările sale, astfel încât un peer cu prioritate mare pentru un slot poate fi un peer cu prioritate scăzută pentru alta, și invers).
Conceptual, nominalizarea este paralelă, atât V cât și W sunt voturi federale separate, fiecare individual capabil să obțină acceptare sau confirmare. În practică, mesajele protocolului SCP împachetează aceste voturi individuale.
Deși votul pentru nominalizarea lui V este o promisiune de a nu vota niciodată împotriva nominalizării lui V, la nivelul aplicației - în acest caz SCP - se stabilește ce înseamnă „împotrivă”. SCP nu vede o declarație care să contrazică votul „I nominalize X”, adică nu există niciun mesaj „Sunt împotriva nominalizării X”, așa că nodul poate vota pentru nominalizarea oricăror valori. Multe dintre aceste nominalizări nu vor ajunge nicăieri, dar în cele din urmă nodul va putea accepta sau confirma una sau mai multe valori. Odată ce un nominalizat este confirmat, el devine candidat.
Nominalizarea SCP folosind votul federat. Pot exista multe valori „B” prezentate de colegi și „reflectate” de nod.
Nominalizările pot avea ca rezultat mai mulți candidați confirmați. Prin urmare, SCP solicită stratului de aplicație să ofere o metodă de combinare a candidaților într-una singură compozit (compozit). Metoda de îmbinare poate fi orice. Principalul lucru este că, dacă această metodă este deterministă, atunci fiecare nod va combina aceiași candidați. Într-un sistem de vot la prânz, „unificarea” poate însemna pur și simplu respingerea unuia dintre cei doi candidați. (Dar într-un mod determinist: fiecare nod trebuie să selecteze aceeași valoare pentru a reseta. De exemplu, selecția anterioară în ordine alfabetică). În rețeaua de plăți Stellar, unde se votează istoricul tranzacțiilor, fuzionarea a doi nominalizați propuși implică fuziunea tranzacțiilor pe care le conțin și a celei mai recente dintre cele două marcaje temporale ale acestora.
Cartea albă SCP demonstrează (Teorema 12) că până la sfârșitul fazei de extindere, rețeaua converge în cele din urmă către un singur compozit. Dar există o problemă: votul federat este un protocol asincron (cum ar fi SCP). Cu alte cuvinte, nodurile nu sunt coordonate de timp, ci doar de mesajele pe care le transmit. Din punctul de vedere al nodului, nu este clar când încheiat faza de extindere. Și, deși toate nodurile vor ajunge în cele din urmă la același compozit, ele pot lua rute diferite pe parcurs, creând diferiți candidați compozit pe parcurs și nu pot spune niciodată care dintre ele este finalul.
Dar e normal. Nominalizarea este doar o pregătire. Principalul lucru este să limitați numărul de candidați pentru a obține un consens, care are loc în proces votul (votare).
Alergare
Buletinul este un cuplu , unde counter este un număr întreg care începe la 1 și value este un candidat din etapa de nominalizare. Acesta poate fi candidatul propriu al unui nod sau candidatul unui nod vecin acceptat de acel nod. În linii mari, un buletin de vot implică încercări repetate de a forța rețeaua să ajungă la un consens cu privire la un candidat la un buletin de vot prin deținerea potențial de multe voturi federate pe declarațiile de vot. Numărătoarele de pe buletinele de vot țin evidența încercărilor făcute, iar buletinele de vot cu un număr mai mare au prioritate față de buletinele de vot cu un număr mai mic. Dacă buletinul informativ se blochează, începe un nou vot, acum pe buletinul de vot .
Este important să se facă distincția sens (de exemplu, care ar trebui să fie comanda de prânz: pizza sau salate), buletine informative (perechea contravaloare) și declarații despre buletine de vot. Runda SCP include mai multe runde de vot federal, în special pentru următoarele declarații:
- „Sunt gata să comite buletinul B” și
- „Anunț comiterea buletinului de vot B”
Din perspectiva unui nod dat, se ajunge la consens atunci când găsește un buletin de vot B pentru care poate confirma (adică să găsească un cvorum care acceptă) afirmația „Angajez buletinul B”. Din acest moment, este sigur să acționați asupra valorii specificate în B - de exemplu, plasarea acestei comenzi pentru prânz. Se numeste externalizare sensuri. Odată ce acceptarea buletinului de vot este confirmată, un nod poate fi sigur că orice alt nod a exteriorizat aceeași valoare sau o va face în viitor.
Deși multe voturi federate se desfășoară conceptual pe baza revendicărilor pentru multe buletine de vot diferite, ele nu schimbă atât de multe mesaje, deoarece fiecare mesaj încapsulează un număr de buletine de vot. Un mesaj promovează astfel starea multor voturi federate simultan, de exemplu: „Accept buletine de vot de la inainte de "
Ce înseamnă termenii „pregătit” și „angajați”?
Un nod votează pentru comiterea unui buletin de vot atunci când are încredere că alte noduri nu vor comite buletine de vot cu valori diferite. Convingerea acestui lucru este scopul pregătirii cererii. Un vot care spune „Sunt gata să comite buletinul B” este o promisiune de a nu angaja niciodată un buletin mai mic decât B, adică cu un număr mai mic (SCP cere ca valorile din buletine de vot să fie într-o anumită ordine. Astfel, buletinul informativ Mai puțin , dacă N1
De ce „Sunt pregătit să comite buletinul B” înseamnă „Promit să nu commit niciodată buletine de vot mai mici decât B”? Deoarece SCP definește abort ca opusul commit-ului. Un vot pentru pregătirea unui buletin de vot implică, de asemenea, un vot pentru descalificarea altor buletine de vot și, așa cum am discutat mai devreme, votul pentru un singur lucru este o promisiune de a nu vota niciodată împotrivă.
Înainte de a difuza un commit, un nod trebuie să găsească mai întâi un buletin pe care îl poate confirma ca fiind pregătit. Cu alte cuvinte, efectuează un vot federal pe tema „Sunt gata să angajez buletinul B”, eventual pe mai multe buletine de vot diferite, până când găsește unul care acceptă cvorumul.
De unde vin buletinele de vot pentru pregătirea votului? În primul rând, nodul difuzează pregătirile pentru votul pentru <1,C>, unde C este candidatul compus produs în etapa de nominalizare. Cu toate acestea, chiar și după începerea pregătirilor pentru vot, nominalizările pot avea ca rezultat candidați suplimentari care par să devină noi buletine de vot. Între timp, colegii pot avea diferiți candidați și pot forma un set de blocare care acceptă „Sunt gata să commit buletinul de vot B2”, ceea ce va convinge și nodul să-l accepte. În cele din urmă, există un mecanism de timeout care generează noi runde de vot federal pentru buletinele noi cu un număr mai mare dacă buletinele actuale sunt blocate.
De îndată ce nodul găsește un buletin de vot B pe care îl poate confirma ca fiind pregătit, difuzează un nou mesaj „Commit buletinul B”. Acest vot le spune colegilor că nodul nu va renunța niciodată la B. De fapt, dacă B este un buletin de vot , apoi „Angajați votul „ înseamnă consimțământul necondiționat de a vota pentru pregătirea fiecărui buletin de vot de la la <∞, s>. Această valoare suplimentară îi ajută pe ceilalți colegi să ajungă din urmă cu peer-ul de comitere, dacă se află încă în stadiile anterioare ale protocolului.
În această etapă, merită să subliniem încă o dată că acestea sunt protocoale asincrone. Doar pentru că un nod trimite voturi pozitive pentru un commit, nu înseamnă că și colegii săi o fac. Unii dintre ei s-ar putea să voteze în continuare declarații în pregătirea votului, alții ar putea să fi exteriorizat deja sensul. SCP explică modul în care un nod ar trebui să proceseze fiecare tip de mesaj peer, indiferent de faza acestuia.
Dacă mesajul „Am anunțat un commit » nu poate fi primit sau confirmat, adică probabilitatea ca mesajul să fie acceptat sau confirmat sau - sau, în orice caz, orice buletin de vot cu valoarea C, și nu oricare altul, deoarece nodul a promis deja că nu va anula niciodată . În momentul în care un nod transmite voturi pentru un comit, acesta va fi C sau nimic, în funcție de cât de departe ajunge consensul. Cu toate acestea, acest lucru nu este încă suficient pentru ca nodul să exteriorizeze C. Unii colegi bizantini (care constituie mai puțin decât un cvorum, pe baza ipotezelor noastre de securitate) pot minți nodul. Acceptarea și apoi confirmarea unui buletin de vot (sau a unei game de buletine de vot) este ceea ce oferă nodului încrederea de a exterioriza în cele din urmă C.
Votarea SCP prin vot federal. Nu este afișat: cronometrul se poate opri în orice moment, crescând numărul de pe buletinul de vot (și posibil producând un nou compus de candidați nominalizați suplimentari).
Și e tot! Odată ce rețeaua a ajuns la un consens, este gata să o facă din nou și din nou. În rețeaua de plată Stellar, acest lucru se întâmplă aproximativ o dată la 5 secunde: o performanță care necesită atât securitatea, cât și capacitatea de supraviețuire garantate de SCP.
SCP poate realiza acest lucru bazându-se pe mai multe runde de vot federal. Votul federal este posibil prin conceptul de segmente de cvorum: seturi de egali în care fiecare nod a decis să aibă încredere ca parte a cvorumului său (subiectiv). Această configurație înseamnă că se poate ajunge la un consens chiar și într-o rețea cu apartenență deschisă și înșelăciuni bizantine.
Lecturi suplimentare
- Cartea albă SCP originală poate fi găsită Și proiect de caiete de sarcini pentru implementarea acestuia.
- Autorul original al protocolului SCP, David Mazier, îl explică într-un mod simplificat (dar totuși tehnic). .
- S-ar putea să fi fost surprins să nu găsiți termenii „exploatare” sau „dovada muncii” în acest articol. SCP nu folosește aceste metode, dar alți algoritmi de consens o fac. Zane Witherspoon a scris accesibil .
- o rețea simplă care ajunge la un consens într-o rundă completă de SCP.
- Pentru cititorii interesați de implementările SCP: vezi , utilizat de rețeaua de plată Stellar sau , pe care l-am scris pentru o mai bună înțelegere a SCP.
Sursa: www.habr.com