Protocolul de consens Stellar a fost descris pentru prima dată în 2015 de David Mazieș. Este un „sistem federativ de acord bizantin”, care permite rețelelor de calcul descentralizate fără lideri să ajungă eficient la consens cu privire la o decizie anume. Rețeaua de plăți Stellar folosește Protocolul de Consens Stellar (SCP) pentru a menține o istorie consensuală a tranzacțiilor, pe care toate părțile o pot vedea.
Se consideră că protocoalele de consens sunt dificile de înțeles. SCP este mai simplu decât majoritatea dintre ele, dar totuși împărtășește această reputație — parțial din cauza ideii greșite că „votul federativ”, despre care se discută în prima jumătate a articolului, este SCP. Dar nu este așa! Este doar un bloc de construcție important, care în a doua jumătate a articolului este utilizat pentru a crea protocolul efectiv de consens Stellar.
În acest articol, vom explica pe scurt ce este un „sistem de acord”, ce poate face acesta „bizantin” și de ce trebuie să facem ca un sistem bizantin să fie „federativ”. Apoi, vom explica procedura de votare federativă descrisă în articolul despre SCP și, în final, vom explica protocolul SCP în sine.
Sistemele de acord
Sistemul de acord permite unui grup de participanți să ajungă la consens cu privire la un anumit subiect, de exemplu, ce să comandăm la prânz.
Noi, la compania Interstellar, am implementat propriul nostru sistem de acord pentru prânz: comandăm ceea ce spune managerul nostru operațional John. Este un sistem simplu și eficient de acord. Toți avem încredere în John și credem că el va găsi în fiecare zi ceva interesant și hrănitor.
Dar ce se întâmplă dacă John abuzează de încrederea noastră? El ar putea decide singur că toți trebuie să devenim vegani. După o săptămână sau două, probabil că îl vom răsturna și vom încredința puterea Elizabetei. Dar, dintr-o dată, ea adoră avocado cu anșoa și crede că toți ar trebui să devină la fel. Puterea corupe. De aceea, este mai bine să găsim o metodă mai democratică: un mod de a ne asigura că diferitele preferințe sunt luate în considerare, asigurând în același timp un rezultat clar și în timp util, astfel încât să nu se ajungă în situația în care nimeni nu comandă prânzul sau cinci persoane fac comenzi diferite, sau discuția se întinde până seara.
Părea simplu: să facem un vot! Dar aceasta este o impresie înșelătoare. Cine va colecta buletinele și va anunța rezultatele? Și de ce ceilalți ar trebui să aibă încredere în ceea ce va spune el? Poate că putem mai întâi să votăm pentru un lider în care avem încredere să conducă votul - dar cine va conduce acest în primul rând vot? Ce se întâmplă dacă nu ne putem înțelege asupra unui lider? Sau dacă ne înțelegem, iar acest lider este blocat la o întâlnire sau se îmbolnăvește?
Probleme similare apar în rețelele informatice distribuite. Toți participanții sau nodurile trebuie să ajungă la un consens cu privire la o anumită decizie, cum ar fi cine este responsabil pentru actualizarea unui fișier comun sau pentru preluarea unei sarcini dintr-o coadă de procesare. Într-o rețea de criptomonede, nodurile trebuie să aleagă de mai multe ori cum arată istoricul complet dintre mai multe versiuni posibile, care uneori pot intra în conflict. Acest consimțământ în rețea oferă destinatarului asigurarea că moneda este (a) validă (nu contrafăcută) și (b) nu a fost cheltuită în altă parte. Aceasta garantează, de asemenea, că el va putea să cheltuie monedele în viitor, deoarece noul destinatar va avea aceleași garanții din aceleași motive.
Orice sistem de consens într-o rețea de calcul distribuită trebuie să fie tolerat la defecte: acesta trebuie să ofere rezultate consistente, în ciuda erorilor, cum ar fi linii de comunicație lente, noduri care nu răspund și ordinea greșită a mesajelor. Sistemul de consens bizantin este suplimentar rezistent la erorile „bizantine”: noduri care oferă informații false, fie din cauza unei erori, fie în încercarea deliberată de a submina sistemul sau de a obține un avantaj. Reziliența „bizantină” - capacitatea de a avea încredere în deciziile grupului, chiar și atunci când unii membri ai grupului pot minți sau să nu urmeze regulile de luare a deciziilor - își are numele în , care încercau să coordoneze un atac. la Anthony Stevens.
Să ne imaginăm că proprietarul de criptomonedă, Alice, trebuie să aleagă între a cumpăra înghețată delicioasă de la Bob și a plăti o datorie lui Carol. Poate că Alice vrea să plătească amândurora în același timp, cheltuind fraudulos aceeași monedă. Pentru aceasta, 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. Un sistem bizantin de acorduri face acest lucru practic imposibil, utilizând o formă de regulă a majorității, numită cvorum. Un nod dintr-o astfel de rețea refuză să treacă la o anumită versiune a istoriei până nu vede că un număr suficient de noduri de egală putere — cvorum — sunt de acord cu această tranziție. Odată ce acest lucru se întâmplă, ele formează un bloc electoral suficient de mare pentru a determina nodurile rămase din rețea să fie de acord cu decizia lor. Alice poate determina unele noduri să mintă în numele ei, dar, dacă rețeaua este suficient de mare, încercarea ei va fi supresată de vocile nodurilor oneste.
Câte noduri sunt necesare pentru un cvorum? Cel puțin, majoritatea, sau mai precis, o majoritate calificată pentru a combate erorile și fraudele. Dar pentru a calcula majoritatea, este necesar să se cunoască numărul total de participanți. La biroul Interstellar sau la alegerile locale, aceste cifre sunt ușor de aflat. Însă dacă grupul dvs. este o rețea slab definită, în care nodurile pot intra și ieși după bunul plac fără a se coordona cu un centru, atunci este nevoie de un sistem federativ de acord bizantin, capabil să determine cvorumuri nu dintr-o listă prestabilită de noduri, ci dintr-un instantaneu dinamic, mereu schimbător și inevitabil incomplet de noduri într-un anumit moment.
Poate părea imposibil să se creeze un cvorum din perspectiva unui nod într-o rețea vastă, dar este posibil. Un astfel de cvorum poate chiar garanta rezultatele votului descentralizat. Documentul tehnic SCP arată cum se poate face acest lucru printr-o procedură denumită votare federativă.
Pentru cei nerăbdători
Restul articolului descrie mai detaliat votarea federativă și protocolul de consens Stellar. Dacă nu vă interesează detaliile, iată o prezentare generală a procesului.
- Nodurile desfășoară runde de vot federal pentru «nominați». Runda de votare federală înseamnă:
- Un nod votează pentru o anumită afirmație, de exemplu, «Propun valoarea V»;
- Un nod ascultă vocile părților implicate, până când găsește pe cineva care poate «accepta»;
- Un nod caută «cvorumul» pentru această afirmație. Cvorumul «confirmă» nominalizatul.
- Odată ce nodul poate confirma unul sau mai mulți nominalizați, el încearcă să «pregătească» «buletinul» prin câteva runde de votare federală.
- Odată ce nodul este capabil să verifice pregătirea buletinului, el încearcă să-l angajeze cu ajutorul unor runde suplimentare de votare federală.
- Odată ce nodul poate confirma angajamentul buletinului, el poate «externaliza» valoarea acestui buletin, folosindu-l ca rezultat al consensului.
Acești pași includ mai multe runde de votare federală, care împreună formează o rundă SCP. Să vedem în detaliu ce se întâmplă la fiecare pas.
Votare federală
Votarea federală este o procedură care determină dacă rețeaua poate concilia o propunere. În runda de votare, fiecare nod trebuie să aleagă una dintre numeroasele valori posibile. Nu poate face acest lucru până când nu este sigur că celelalte noduri din rețea nu vor alege un alt rezultat. Pentru a fi sigure de acest lucru, nodurile schimbă un flux de mesaje în ambele sensuri, astfel încât fiecare a confirmat, ceea ce cvorum nod acceptă aceeași soluție. Restul acestei secțiuni explică termenii din această afirmație și cum se desfășoară întreaga procedură.
Cvorumuri și „cortege de cvorum”
Să începem cu definiția unui cvorum. Așa cum am discutat mai devreme, în cadrul unei rețele descentralizate cu membri dinamici, nu este posibil să se cunoască dinainte numărul de noduri și, prin urmare, câte sunt necesare pentru o majoritate. Votarea federală rezolvă această problemă, introducând o nouă idee a „cortegei de cvorum” (quorum slice): un set mic de noduri de egali care sunt de încredere pentru a transmite informații despre starea votului în restul rețelei. Fiecare nod își definește propriul corteg de cvorum (de care devine membru prin simpla existență).
Formarea cvorumului începe cu cortegul de cvorum. Pentru fiecare nod, se adaugă nodurile din cortegul său. Apoi, se adaugă membrii cortegelor. aceste noduri şi aşa mai departe. Pe măsură ce continuăm, găsim tot mai multe noduri pe care nu le puteţi adăuga, deoarece sunt deja incluse în secţiune. Când nu mai există noduri noi de adăugat, procesul se încheie: am format un cvorum prin „închidere tranzitivă” a secţiunii cvorumului nodului iniţial.
Pentru a găsi un cvorum din nodul dat…
… adăugăm membri ai secţiunii sale…
… apoi adăugăm membri ai secţiunilor acestor noduri.
Continuăm până nu mai rămân noduri de adăugat.
Nu mai sunt noduri de adăugat. Acesta este cvorumul.
În realitate, fiecare nod poate face parte din mai multe secţiuni. Pentru a forma un cvorum, alegeţi doar una dintre secţiuni şi adăugaţi membri; apoi alegeţi orice secţiune pentru fiecare dintre membri şi adăugaţi membri aceasta secţiunii şi aşa mai departe. Aceasta înseamnă că fiecare nod este membru al unui număr de cvorumuri posibile.
Alegeţi doar o secţiune de cvorum la fiecare pas.
Un cvorum posibil. Sau o alternativă…
… alegem alte secţiuni…
… (când este posibil)…
… creează un alt cvorum.
Cum află un nod în ce secţiuni se află celelalte noduri? La fel ca şi celelalte informaţii despre celelalte noduri: din transmisiile pe care fiecare nod le transmite în reţea, atunci când starea sa de votare se schimbă. Fiecare transmisiune conţine informaţii despre secţiunile nodului emitent. În documentul tehnic SCP nu este specificat un mecanism de comunicaţie. Implementările folosesc de obicei pentru a garanta transmiterea mesajelor în întreaga reţea.
Reamintim că în sistemul de acorduri bizantine nefederaționiste, cvorumul este definit ca majoritatea tuturor nodurilor. Sistemul bizantin de acorduri a fost dezvoltat din perspectiva întrebării: câte noduri necorecte poate suporta sistemul? Într-un sistem format din N noduri, proiectat să supraviețuiască la f eșecuri (înșelăciuni), un nod trebuie să fie capabil să realizeze progresul obținând un răspuns de la N−f perechi, deoarece f dintre ele nu funcționează poate. Dar, obținând un răspuns de la N−f perechi, se poate presupune că toate f perechile (de la care nodul nu a primit răspuns) sunt, de fapt, corecte. Astfel, malefice sunt f din N−f perechi (de la care s-a primit un răspuns). Pentru ca nodurile să ajungă la un consens comun, majoritatea celorlalte noduri trebuie să fie corecte, adică avem nevoie ca N−f să fie mai mare decât 2f sau N > 3f. Așadar, în mod obișnuit, un sistem proiectat să supraviețuiască la f eșecuri va avea în total N=3f+1 noduri și o dimensiune a cvorumului de 2f+1. Odată ce propunerea depășește pragul cvorumului, ceilalți membri ai rețelei sunt convinși că orice propuneri concurente vor eșua. Astfel, rețeaua converge spre un rezultat.
Dar în sistemul de acorduri bizantine federative nu numai că nu poate exista o majoritate (deoarece nimeni nu cunoaște 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 așa-numita atac Sivil: adunându-se repetat la rețea prin mai multe noduri. Atunci, de ce se poate numi închiderea tranzitivă a tăieturii cvorum, și cum poate suprima propunerile concurente?
Tehnic, deloc! Imaginează-ți o rețea formată din șase noduri, unde două grupuri de câte trei sunt izolate în tăieturile cvorumului unul de celălalt. Prima subgrupă poate lua o decizie despre care a doua nu va auzi niciodată și viceversa. Pentru această rețea nu există nicio modalitate de a atinge consensul (în afară de cazurile întâmplătoare).
De aceea, SCP necesită ca pentru votul federativ (și pentru aplicarea teoremelor importante ale articolului), rețeaua să aibă o proprietate numită intersecția cvorumurilor. Într-o rețea cu această proprietate, orice două cvorumuri care pot fi construite se suprapun întotdeauna în cel puțin un nod. Pentru a determina tendințele predominante ale rețelei, acest lucru este la fel de bun ca a avea majoritatea. Intuitiv, aceasta înseamnă că, dacă un cvorum este de acord cu afirmația X, niciun alt cvorum nu va putea niciodată să fie de acord cu ceva diferit, pentru că va include cu siguranță un anumit nod din primul cvorum, care a votat deja pentru X.
Dacă în rețea există intersecții între cvorumuri…
…atunci orice două cvorumuri pe care le poți construi…
…se vor suprapune întotdeauna.
(Desigur, nodurile suprapuse pot fi vizante, mincinoase sau defectuoase în alte privințe. În acest caz, intersecțiile între cvorumuri nu ajută rețeaua să ajungă la un consens. Din acest motiv, multe rezultate în documentul tehnic SCP se bazează pe presupuneri expresse, cum ar fi că rețeaua a păstrat intersecții între cvorumuri, chiar și după eliminarea nodurilor defectuoase.. Pentru simplificare, să lăsăm aceste presupuneri neexplicite în restul articolului).
Poate părea nerezonabil să aștepți că într-o rețea de noduri independente este posibil un intersecție fiabilă între cvorumuri. Dar există două motive pentru care este așa.
Primul motiv este existența însăși a internetului. Internetul este un exemplu ideal de rețea de noduri independente cu intersecții între cvorumuri. Cele mai multe noduri din internet se conectează doar cu câteva alte noduri locale, dar aceste seturi mici se suprapun suficient pentru ca fiecare nod să fie accesibil din fiecare alt nod printr-o rută oarecare.
A doua cauză este specifică rețelei de plăți Stellar (cea mai frecventă aplicare a SCP). Fiecare activ din rețeaua Stellar are un emitent, iar recomandările Stellar cer ca fiecare emitent să desemneze unul sau mai multe noduri din rețea pentru a gestiona cererile de răscumpărare. Este în interesul vostru să includeți direct sau indirect aceste noduri în cotele de quorum pentru fiecare activ de interes. Astfel, cotele pentru toate nodurile interesate de acest activ se vor suprapune cel puțin în aceste noduri de răscumpărare. Nodurile interesate de mai multe active vor include în cotele lor de quorum toate nodurile de răscumpărare ale emitentelor corespunzătoare și vor căuta să adune toate activele împreună. În plus, orice active care nu sunt legate în acest mod de altele din rețea și nu trebuie să fie legate — a fost gândit astfel încât să nu existe suprapuneri de quorumuri în această rețea (de exemplu, băncile din zona dolarului vor să facă uneori tranzacții cu băncile din zona euro și cu băncile din zona peso, deci se află în aceeași rețea, dar nimănui nu-i pasă de rețeaua separată a copiilor care tranzacționează cărți de baseball).
Desigur, așteptarea suprapunerilor de quorumuri nu este o garanție. Alte sisteme de acorduri bizantine își datorează în mare parte complexitatea garanției quorumurilor. O inovație importantă a SCP este că aceasta transferă responsabilitatea pentru crearea quorumurilor de la algoritmul de consens la nivelul aplicației. Astfel, deși votul federativ este suficient de obișnuit pentru votarea pe orice subiect, în realitate fiabilitatea sa depinde critic de sensul mai larg al acestor valori. Unele utilizări ipotetice s-ar putea să nu fie la fel de convenabile pentru crearea de rețele bine legate ca altele.
Votul, acceptarea și confirmarea
În runda de votare federativă, un nod opțional începe să voteze pentru o anumită valoare V. Aceasta înseamnă transmiterea în rețea a unui mesaj: „Eu sunt nodul N, cotele mele de quorum Q și votez pentru V”. Când un nod votează în acest mod, promite că nu a votat niciodată împotriva lui V și nu va face acest lucru niciodată.
În transmisiile de la noduri peer-to-peer, fiecare nod poate vedea cum votează celelalte. Odată ce un nod strânge un număr suficient de astfel de mesaje, poate urmări subgrupele de quorum și încerca să găsească quorumul. Dacă vede un quorum de noduri care votează pentru V, poate trece la acceptarea V și transmite acest nou mesaj în rețea: „Eu sunt nodul N, subgrupurile mele de quorum Q, și accept V”. Acceptarea oferă o garanție mai puternică decât votul simplu. Atunci când un nod votează pentru V, nu poate vota niciodată pentru alte opțiuni. Dar dacă un nod acceptă V, niciun alt nod din rețea nu va accepta o altă opțiune (teorema 8 din documentul tehnic SCP dovedește acest lucru).
Desigur, este foarte probabil ca nu imediat să se găsească un quorum de noduri care să fie de acord cu V. Alte noduri pot vota pentru alte valori. Dar pentru nod există încă o modalitate de a trece de la votul simplu la acceptare. N poate accepta o altă valoare W, chiar dacă nu a votat pentru ea și chiar dacă nu vede un quorum pentru aceasta. Pentru a schimba votul său, este suficient să vadă un set de blocare de noduri care au acceptat W. Setul de blocare este format din câte un nod din fiecare subgrup de quorum N. Așa cum denumirea sugerează, acesta este capabil să blocheze orice altă valoare. Dacă toate nodurile dintr-un astfel de set acceptă W, atunci, conform teoremei 8, nu va fi niciodată posibil să se formeze un quorum care să accepte o altă valoare și astfel, pentru N, este de asemenea sigur să accepte W.
Nodul N cu trei subgrupuri de quorum.
B-D-F este setul de blocare pentru N: acesta include câte un nod din fiecare subgrup N.
B-E este de asemenea un set de blocare pentru N, deoarece E apare în două subgrupuri din N.
Dar setul de blocare nu este un quorum. Ar fi prea ușor să păcălești nodul N să accepte valoarea dorită dacă ar fi suficient să compromiți un singur nod din fiecare subgrup din N. De aceea, acceptarea unei valori nu este finalul votului. În schimb, N trebuie să confirme valoarea, adică să vadă un quorum de noduri care o acceptă. Dacă a ajuns atât de departe, așa cum dovedește documentul tehnic SCP (în teorema 11), restul rețelei va confirma, de asemenea, aceeași valoare, astfel încât N va finaliza votul federal cu o valoare specifică ca rezultat.
Votul federal.
Procesul de votare, adoptare și confirmare constituie un ciclu complet de votare federativă. Protocolul de consens Stellar reunește multe astfel de cicluri pentru a crea un sistem complet de consens.
Protocolul de consens Stellar
Cele două cele mai importante proprietăți ale unui sistem de consens sunt securitate și reziliența. Un algoritm de consens este „sigur” dacă nu poate niciodată oferi rezultate diferite diferitelor părți (o copie a istoricului lui Bob nu va contrazice niciodată pe cea a lui Carol). „Resiliența” înseamnă că algoritmul va oferi mereu un rezultat, adică nu va rămâne blocat.
Procedura descrisă a votului federativ este sigură în sensul că, dacă un nod confirmă valoarea V, niciun alt nod nu va confirma o altă valoare. Dar „nu va confirma o altă valoare” nu înseamnă că trebuie să confirme neapărat ceva. Participanții pot vota pentru un număr atât de mare de valori diferite încât nimic nu va atinge pragul de acceptare. Aceasta înseamnă că în votul federativ lipsește reziliența.
Protocolul de consens Stellar utilizează votul federativ într-un mod care garantează atât siguranța, cât și reziliența. (Garanțiile de siguranță și reziliență ale SCP au o limită teoretică. Construcția alege o garanție de siguranță foarte puternică, sacrificând o ușoară slăbire a rezilienței, dar având în vedere un termen suficient, consensul va fi atins cu o mare probabilitate). În câteva cuvinte, ideea este de a desfășura mai multe voturi federative asupra mai multor valori, până când una dintre ele va trece complet prin toate fazele de vot SCP, descrise mai jos.
Valorile pentru care SCP caută consens pot fi istorii de tranzacții sau comenzi de prânz, sau altele, dar este important de menționat că acestea nu sunt valorile care sunt acceptate sau confirmate. În schimb, votul federativ are loc asupra declarațiilor referitoare la aceste valori.
Primele runde de vot federativ au loc în faza de nominalizare (nomination phase), pe un set de declarații de tip „Îi propun V”, posibil pentru multe valori diferite V. Scopul nominalizării este de a găsi una sau mai multe declarații care să treacă prin acceptare și confirmare.
După identificarea candidaților confirmabili, SCP trece la etapa de votare, unde scopul este de a găsi o buletină (adică un container pentru valoarea propusă) și un cvorum capabil să declare commit pentru acesta (commit). Dacă cvorumul face commit-ul buletinei, valoarea sa este acceptată ca fiind consens. Dar înainte ca un nod să poată vota pentru commit-ul buletinei, acesta trebuie mai întâi să confirme anularea tuturor buletinelor cu un număr de contor mai mic. Acești pași — anularea buletinelor pentru a găsi pe cel pentru care se poate confirma commit-ul — implică mai multe runde de votare federativă pe mai multe declarații de buletine.
În secțiunile următoare se discută mai în detaliu despre propunere și votare.
Propunere
La începutul etapei de propunere, fiecare nod poate alege spontan o valoare V și poate vota pentru aprobarea „Propun V”. Scopul în această etapă este de a confirma propunerea unei anumite valori prin votare federativă.
Poate că un număr suficient de noduri votează pentru declarații îndeajuns de diferite, și nicio propunere nu poate atinge pragul de acceptare. De aceea, în afară de transmiterea propriilor voturi de propunere, nodurile „reflectă” propunerile vecinilor lor. Reflecția (echo) înseamnă că, dacă un nod votează pentru propunerea V, dar vede un mesaj de la un vecin care votează pentru propunerea W, atunci acum va vota atât pentru propunerea V, cât și pentru W. (Nu toate voturile vecinilor sunt reflectate în timpul propunerii, deoarece acest lucru poate duce la o explozie de propuneri diferite. SCP include un mecanism de reglementare a acestor voturi. Pe scurt, există o formulă pentru a determina „prioritatea” unui vecin din perspectiva nodului, și sunt reflectate voturile doar ale nodurilor de înaltă prioritate. Cu cât propunerea durează mai mult, cu atât pragul este mai mic, astfel încât nodul extinde setul de vecini ale căror voturi le va reflecta. Formula de prioritate, ca unul dintre datele de intrare, include numărul slotului, astfel încât un nod peer de înaltă prioritate pentru un slot poate fi de prioritate scăzută pentru altul, și invers).
Conceptual, the advancement of both V and W in parallel means separate federative votes, each capable of achieving adoption or confirmation independently. In practice, SCP protocol messages package these individual votes together.
Although voting for the advancement of V is a promise never to vote against it, at the application level — in this case, SCP — it is determined what 'against' means. SCP does not recognize a statement that contradicts the vote 'I nominate X'; that is, there is no message 'I am against the nomination of X', so the node can vote for the advancement of any values. Many of these nominations may lead nowhere, but eventually, the node can accept or confirm one or several values. Once the nominee is confirmed, they become candidate.
Nomination in SCP using federative voting. There can be many 'B' values nominated by peer nodes and 'reflected' by the node.
Nominating candidates may result in multiple confirmable candidates. Therefore, SCP requires that the application layer provide some method of merging candidates into one composite (composite). The merging method can be anything. The main point is that if this method is deterministic, each node will merge the same candidates. In a lunch voting system, 'merging' may simply mean dropping one of the two candidates. (But deterministically: each node must choose the same value to drop. For example, by earlier alphabetical order). In the Stellar payment network, where voting on transaction history occurs, merging two proposed nominees implies combining the transactions they contain and the latest of their two timestamps.
The technical description of SCP proves (theorem 12) that by the end of the nomination phase, the network eventually converges to one composite. But there is a problem: federative voting is an asynchronous protocol (just like SCP). In other words, nodes are not time-coordinated but only coordinated through the messages they send. From the node's perspective, it is unclear when has completed faza de propunere. Și, deși toate nodurile vor ajunge în cele din urmă la același compus, ele pot alege trasee diferite în acest parcurs, creând în drumul lor diferiți candidați compuși, fără a putea spune vreodată care dintre ei este final.
Dar este în regulă. Propunerea este doar o pregătire. Principalul este să restrângem numărul de candidați pentru a ajunge la un consens, care are loc în procesul votării (votare).
Votarea
Un buletin de vot este o pereche , unde counter este un număr întreg care începe de la 1, iar value este candidatul din etapa de propunere. Acesta poate fi candidatul propriu al nodului sau candidatul unui nod vecin, acceptat de acest nod. În termeni simpli, în timpul votării se fac multiple încercări pentru a face rețeaua să ajungă la un consens asupra unui anumit candidat într-un anumit buletin, prin desfășurarea potențial a multor voturi federative pe declarațiile privind buletinele. Contoarele din buletinele de vot urmăresc încercările efectuate, iar buletinele cu contoare mai mari au prioritate față de cele cu contoare mai mici. Dacă buletinul se blochează, începe o nouă votare acum pe buletinul .
Este important să distingi valorile (de exemplu, ce ar trebui să conțină comanda de prânz: pizza sau salate), buletinele de vot (perechea counter-value) și declarații despre buletinele de vot. Runda SCP include mai multe runde de votare federativă, în special, pe declarații precum:
- „Sunt pregătit să angajez buletinul de vot B” și
- „Anunț angajamentul buletinului de vot B”
Din perspectiva acestui nod, consensul este atins când găsește buletinul B, pentru care poate confirma (adică găsi un cvorum care acceptă) declarația „Anunț angajamentul buletinului de vot B”. De acum încolo, se poate acționa în siguranță pe baza valorii indicate în B – de exemplu, să se plaseze această comandă de prânz. Aceasta se numește externalizarea valorii. Odată ce a fost confirmată acceptarea buletinului, nodul poate fi sigur că orice alt nod a realizat externalizarea acelei valori sau o va face cu siguranță în viitor.
Deși conceptual, multe voturi federative sunt efectuate pe baza declarațiilor referitoare la multe buletine diferite, ele nu schimbă atât de multe mesaje, deoarece fiecare mesaj încorporează un număr de buletine. Astfel, un singur mesaj promovează starea simultan a multor voturi federative, de exemplu: „Accept comiterea buletinelor în intervalul de la la .”
Ce înseamnă termenii „preparat” (prepared) și „comite” (commit)?
Nodul votează pentru comiterea buletinului atunci când este convins că celelalte noduri nu vor comite buletine cu alte valori. Convincerea în acest sens este scopul pregătirii declarației. Votul care spune: „Sunt gata să comit buletinul B” reprezintă o promisiune de a nu comite niciodată buletine mai mici decât B, adică cu un contor mai mic (SCP necesită ca valorile din buletine să aibă un anumit ordonare. Astfel, buletinul este mai mic decât , dacă N1<N2, și de asemenea, dacă N1=N2 și V1<V2). Aceste buletine mai mici sunt „abandonate” (aborted) în timpul votului de pregătire, în timp ce B este considerat „pregătit”.
De ce „Sunt gata să comit buletinul B” înseamnă „Promit să nu permit niciodată comiterea buletinelor mai mici decât B”? Pentru că SCP definește abort ca fiind opusul lui commit. Votul pentru pregătirea buletinului implică de asemenea votul pentru anularea unor alte buletine, și, așa cum am discutat anterior, votul pentru ceva anume este o promisiune de a nu vota niciodată împotriva acestuia.
Înainte de a transmite comiterea, nodul trebuie mai întâi să găsească un buletin pe care îl poate confirma ca fiind pregătit. Cu alte cuvinte, el realizează un vot federativ pe tema „Sunt gata să comit buletinul B”, posibil pentru multe buletine diferite, până găsește pe acela care acceptă cvorumul.
De unde provin buletinele pentru pregătirea votului? Mai întâi, nodul transmite pregătirea pentru votul pentru , unde C este candidatul-compozit, creat în etapa de propunere. Cu toate acestea, chiar și după începutul pregătirii pentru vot, propunerea poate duce la apariția unor candidați suplimentari, care vor deveni noile buletine. Între timp, părțile pot avea candidați diferiți și pot forma un set blocant, care acceptă „Sunt pregătit pentru a comite buletinul B2”, ceea ce va convinge nodul să-l accepte și el. În cele din urmă, există un mecanism de timeout care generează noi runde de votare federativă pe noi buletine cu numere de contor mai mari, dacă buletinele curente sunt blocate.
Odată ce nodul găsește buletinul V, care poate fi confirmat ca pregătit, transmite un nou mesaj „Comite buletinul V”. Această votare îi spune părților că nodul nu va renunța niciodată la V. De fapt, dacă V reprezintă un buletin , atunci „Comite buletinul ” înseamnă acordul necondiționat de a vota pentru pregătirea fiecărui buletin de la până la . Această valoare suplimentară îi ajută pe alții noduri să ajungă din urmă cu comiterea, dacă aceștia se află încă în etape anterioare ale protocolului.
În această etapă, este important să subliniem din nou că acestea sunt protocoale asincrone. Numai pentru că un nod trimite voturi pentru comitere, nu înseamnă că colegii săi fac la fel. Unii dintre ei ar putea încă vota pe declarații pentru pregătirea votului, alții ar putea că deja au externalizat valoarea. SCP explică cum un nod trebuie să proceseze fiecare tip de mesaj peer-to-peer independent de faza sa.
Dacă mesajul „Anunț commit <N,C>” nu poate fi acceptat sau confirmat, există șansa ca mesajul <N+1, C> sau <N+2, C> să fie acceptat sau confirmat — sau, în orice caz, orice buletin cu valoarea C, și nu orice altceva, deoarece nodul a promis deja să nu anuleze niciodată <N,C>. Până când nodul transmite voturile pentru commit, acesta va fi C sau nimic, în funcție de cât de departe va merge consensul. Cu toate acestea, aceasta nu este încă suficient pentru ca nodul să externalizeze C. Anumiți participanți bizantini (constituind mai puțin de un cvorum, bazându-se pe presupunerile noastre de securitate) pot minți nodul. Acceptarea și apoi confirmarea unui anumit buletin (sau a unui interval de buletine) este ceea ce oferă nodului încrederea de a externaliza, în sfârșit, C.
Votarea SCP prin vot federal. Nu este afișat: la orice moment, un temporizator poate fi activat, crescând contorul din buletin (și, posibil, creând un nou compus din candidați suplimentari propusi).
Și asta e tot! Odată ce rețeaua a ajuns la un consens, este pregătită să facă asta din nou și din nou. În rețeaua de plăți Stellar, acest lucru se întâmplă aproximativ la fiecare 5 secunde: o realizare care necesită atât securitate, cât și reziliență, garantate de SCP.
SCP poate realiza acest lucru, bazându-se pe mai multe runde de votare federală. Votarea federală a devenit posibilă datorită conceptului de tăieturi de cvorum: seturi de noduri de același nivel, î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 consens chiar și într-o rețea cu membri deschiși și înșelăciuni bizantine.
Citiți mai departe
- Documentul tehnic original SCP se poate găsi , iar proiectul specificațiilor pentru implementarea sa.
- Autorul original al protocolului SCP, David Mazier, explică simplificat (dar totuși tehnic) acesta .
- Poate că ați fost surprinși că nu ați găsit în acest articol termenii „mining” sau „proof of work”. SCP nu folosește aceste metode, dar alte algoritme de consens le folosesc. Zane Wiserpoon a scris un accesibil .
- a unei rețele simple care ajunge la consens în cadrul unei runde complete de SCP.
- Pentru cititorii interesați de implementările SCP: verificați , utilizat de rețeaua de plăți Stellar, sau , pe care l-am scris pentru o mai bună înțelegere a SCP.
Sursa: habr.com
