O protocolo de consenso Stellar foi descrito por primeira vez en David Mazier en 2015. Este é un "sistema de acordo bizantino federal" que permite que redes informáticas descentralizadas e sen líderes alcancen un consenso sobre unha decisión de forma eficiente. A rede de pago Stellar usa o Stellar Consensus Protocol (SCP) para manter un historial de transaccións consistente que sexa visible para todos os participantes.
Os protocolos de consenso considéranse difíciles de entender. SCP é máis sinxelo que a maioría deles, pero aínda comparte esta reputación, en parte debido á idea equivocada de que a "votación federada", que é o tema da primeira metade do artigo científico, é SCP. Pero iso non é certo! Este é só un bloque de construción importante que a segunda metade do artigo usa para crear real Protocolo de consenso estelar.
Neste artigo explicaremos brevemente que é un "sistema de acordos", que pode facelo "bizantino" e por que facer o sistema bizantino "federal". Despois explicaremos o procedemento de votación federada descrito no artigo SCP e, finalmente, explicaremos o propio protocolo SCP.
Sistemas de convenio
Un sistema de acordos permite a un grupo de participantes chegar a un consenso sobre un tema, como que pedir para o xantar.
En Interstellar, implementamos o noso propio sistema de acordo de comedor: pedimos o que di o noso director de operacións, John. Este é un sistema de acordo sinxelo e eficaz. Todos confiamos en John e cremos que atopará algo interesante e nutritivo todos os días.
Pero e se Xoán abusa da nosa confianza? Pode decidir por si só que todos debemos facernos veganos. Dentro dunha ou dúas semanas, probablemente o derroquemos e lle entreguemos o poder a Elizabeth. Pero de súpeto encántanlle os aguacates con anchoas e pensa que todo o mundo debería ser así. O poder corrompe. Así que é mellor buscar algún método máis democrático: algún xeito de asegurarse de que se teñan en conta as diferentes preferencias, ao tempo que se garante un resultado oportuno e inequívoco, para que ninguén acabe pedindo o xantar, ou cinco persoas fagan pedidos diferentes, ou a discusión. prolonga ata a noite.
Parece que a solución é sinxela: vota! Pero esta é unha impresión enganosa. Quen recollerá as papeletas e informará dos resultados? E por que os demais deberían crer o que el di? Quizais poidamos ao principio votar por un líder en quen confiamos que dirixa a votación, pero quen a dirixa первым por votación? E se non podemos poñernos de acordo sobre un líder? Ou que pasa se chegamos a un acordo, pero este líder queda atrapado nunha reunión ou vai de baixa?
Problemas similares ocorren nas redes de ordenadores distribuídas. Todos os participantes ou nodos deben poñerse de acordo nalgunha decisión, como a quenda de actualizar un ficheiro compartido ou eliminar unha tarefa da cola de procesamento. Nunha rede de criptografía, os nodos teñen que escoller repetidamente como se ve a historia completa entre varias versións posibles, que ás veces entran en conflito. Este acordo de rede garante ao destinatario que a moeda é (a) válida (non falsificada) e (b) aínda non se gastou noutro lugar. Isto tamén garante que poderá gastar as moedas no futuro porque o novo destinatario terá as mesmas garantías polos mesmos motivos.
Calquera sistema de consenso nunha rede de computación distribuída debe ser tolerante a fallos: debe producir resultados consistentes a pesar de erros como ligazóns lentas, nós que non responden e orde de mensaxes incorrecta. bizantino O sistema de acordo é ademais resistente aos erros "bizantinos": nodos que dan información falsa, xa sexa por un erro ou nun intento deliberado de socavar o sistema ou obter algunha vantaxe. Denomínase tolerancia "bizantina" ás fallas: a capacidade de confiar nunha decisión do grupo aínda que algúns membros do grupo poidan mentir ou non seguir as regras de toma de decisións. que intentou coordinar o ataque. en Anthony Stevens.
Considere a propietaria da moeda criptográfica Alice, que debe escoller entre mercar un delicioso xeado a Bob e pagar a débeda de Carol. Quizais Alicia queira pagar os dous á vez gastando fraudulentamente a mesma moeda. Para iso, debe convencer ao ordenador de Bob de que a moeda nunca se lle pagou a Carol e convencer ao ordenador de Carol de que a moeda nunca se lle pagou. O sistema bizantino de acordos fai que isto sexa practicamente imposible, utilizando unha forma de regra maioritaria chamada quórum. Un nodo desta rede négase a pasar a unha versión particular do historial ata que vexa que un número suficiente de pares -un quórum- aceptan tal transición. Unha vez que isto suceda, formarán un bloque de votación o suficientemente grande como para forzar aos restantes nodos da rede a que estean de acordo coa súa decisión. Alicia pode forzar algúns nodos a mentir no seu nome, pero se a rede é o suficientemente grande, o seu intento será superado polos votos dos nodos honestos.
Cantos nodos son necesarios para o quórum? Como mínimo, unha maioría, ou mellor dito, unha maioría cualificada para combater erros e fraudes. Pero para contar coa maioría, cómpre coñecer o número total de participantes. Na oficina Interestellar ou nas eleccións de distrito, estes números son fáciles de descubrir. Pero se o teu grupo é unha rede pouco definida na que os nodos poden entrar e saír sen a aprobación do centro, entón necesitas federal un sistema de acordo bizantino capaz de determinar quórums non a partir dunha lista predeterminada de nós, senón de forma dinámica, a partir dunha instantánea de nodos en constante cambio e inevitablemente incompleta nun momento dado.
Pode parecer imposible crear un quórum desde a perspectiva dun só nodo nunha ampla rede, pero é posible. Tal quórum pode incluso garantir os resultados da votación descentralizada. O libro branco de SCP mostra como facelo usando un procedemento chamado por voto federal.
Para impaciente
O resto do artigo describe a votación federada e o protocolo de consenso de Stellar con máis detalle. Se non estás interesado nos detalles, aquí tes unha visión xeral do proceso.
- Os nodos realizan roldas de votación federal sobre os "nominados". Unha rolda de votación federal significa:
- O nodo vota por algunha afirmación, por exemplo, "Propoño o valor de V";
- O nodo escoita as voces dos compañeiros ata que atopa unha que poida "recibir";
- O nodo busca un "quórum" para esta afirmación. Un quórum "confirma" o nomeado.
- Unha vez que un nodo pode confirmar un ou máis candidatos, tenta "preparar" a "papeleta" mediante varias roldas de votación federada.
- Unha vez que un nodo pode verificar que a papeleta está lista, tenta comprometela mediante aínda máis quendas de votación federada.
- Unha vez que un nodo pode confirmar a confirmación dunha papeleta, pode "externalizar" o valor desa papeleta usándoa como resultado de consenso.
Estes pasos implican varias roldas de votación federada, que forman colectivamente unha rolda SCP. Vexamos máis de cerca o que acontece en cada paso.
Votación federada
A votación federada é un procedemento para determinar se a rede pode acordar unha proposta. Na rolda de votación, cada nodo debe escoller un dos moitos valores posibles. Non pode facelo a menos que confíe en que outros nodos da rede non escollerán un resultado diferente. Para asegurarse diso, os nodos intercambian un aluvión de mensaxes de ida e volta para que todos confirmadoQue quórum nós acepta mesmo decisión. O resto desta sección explica os termos desta frase e como se produce todo o procedemento.
Quórums e porcións de quórum
Comecemos por definir un quórum. Como comentamos anteriormente, nunha rede descentralizada con pertenza dinámica, é imposible saber de antemán o número de nodos e, polo tanto, cantos son necesarios para a maioría. O voto federado resolve este problema introducindo unha nova idea corte de quórum (porción de quórum): un pequeno conxunto de pares nos que un nodo confía para comunicar a información do estado da votación ao resto da rede. Cada nodo define o seu propio segmento de quórum (do que pasa a ser membro de facto).
A formación do quórum comeza cun corte de quórum. Para cada nodo, engádense os seus nodos de corte. A continuación, engádense os termos da porción estes nodos etcétera. A medida que continúas, hai cada vez máis nodos que non podes engadir porque xa están incluídos no segmento. Cando non hai máis nodos novos que engadir, o proceso detense: formamos un quórum por "peche transitivo" do segmento de quórum do nodo inicial.
Para atopar quórum dun nodo determinado...
... engade membros da súa porción...
...a continuación engadimos membros de corte destes nós.
Continuamos ata que non queden nodos que engadir.
Non quedan nodos que engadir. Este é un quórum.
De feito, cada nodo pode aparecer en máis dunha porción. Para formar quórum, seleccione só unha das porcións e engada membros; a continuación, seleccione calquera porción para cada un dos membros e engada membros el cortar e así por diante. Isto significa que cada nodo é membro de moitos quórums posibles.
Seleccione só unha porción de quórum en cada paso.
Un quórum posible. Ou unha alternativa...
...selecciona outras porcións...
…(cando sexa posible)…
... crea outro quórum.
Como sabe un nodo en que franxas están os outros nodos? Do mesmo xeito que outra información sobre outros nodos: dende as transmisións que cada nodo emite á rede cando cambia o seu estado de votación. Cada transmisión inclúe información sobre os segmentos do nodo emisor. O libro branco de SCP non especifica un mecanismo de comunicación. As implementacións adoitan utilizarse para garantir a difusión de mensaxes en toda a rede.
Lembre que no sistema bizantino non federal de acordos, un quórum defínese como a maioría de todos os nodos. O sistema de acordo bizantino está deseñado dende o punto de vista da pregunta: cantos nodos deshonestos pode tolerar o sistema? Nun sistema de N nodos deseñado para sobrevivir a f fallos, un nodo debería poder progresar recibindo feedback de N−f pares xa que f deles pode estar caído. Pero ao recibir unha resposta de N−f pares, podemos supoñer que todos os f pares (dos que o nodo non recibiu resposta) son realmente honestos. Así, f de N−f pares (dos que se recibiu a resposta) son maliciosos. Para que os nodos cheguen ao mesmo consenso, a maioría dos nodos restantes deben ser honestos, é dicir, necesitamos que N−f sexa maior que 2f ou N > 3f. Polo que normalmente un sistema deseñado para sobrevivir a fallos f terá un total de N=3f+1 nodos e un tamaño de quórum de 2f+1. Unha vez que unha proposta supera o limiar de quórum, o resto da rede está convencido de que todas as propostas en competencia fracasarán. Así é como a rede converxe ao resultado.
Pero nun sistema federal de acordos bizantinos, non só non pode haber maioría (porque ninguén sabe o tamaño total da rede), senón que o concepto de maioría é completamente inútil! Se a pertenza ao sistema está aberta, entón alguén pode obter a maioría simplemente realizando un chamado ataque Sybil: unirse repetidamente á rede a través de varios nodos. Entón, por que se pode chamar o peche transitivo de porcións quórum, e como é capaz de suprimir propostas en competencia?
Tecnicamente, de ningún xeito! Imaxina unha rede de seis nodos, onde dous trillizos están illados nos segmentos de quórum do outro. O primeiro subgrupo pode tomar unha decisión da que o segundo nunca escoitará falar, e viceversa. Non hai xeito de que esta rede chegue a consenso (salvo por casualidade).
Polo tanto, SCP esixe que para a votación federada (e para que se apliquen os teoremas importantes do documento), a rede debe ter unha propiedade chamada intersección de quórums. Nunha rede con esta propiedade, dous quórums que se poidan construír sempre se solapan en polo menos un nodo. Para determinar o sentimento predominante da rede, é tan bo como ter unha maioría. Intuitivamente, isto significa que se algún quórum acepta a afirmación X, ningún outro quórum poderá aceptar outra cousa, porque necesariamente incluirá algún nodo do primeiro quórum que xa votou por X.
Se hai unha intersección de quórums na rede...
...entón podes construír dous quórums...
... sempre cruzarase.
(Por suposto, os nodos superpostos poden resultar ser bizantinos ou malos. Neste caso, a intersección do quórum non axuda en absoluto a que a rede estea de acordo. Por este motivo, moitos dos resultados do libro branco de SCP baséanse en presupostos explícitos, como o que queda no cruzamento de quórum da rede mesmo despois de eliminar nodos defectuosos. Por simplicidade, deixemos estas suposicións implícito no resto do artigo).
Pode parecer pouco razoable esperar que sexa posible un cruce de quórum fiable nunha rede de nodos independentes. Pero hai dúas razóns polas que isto é así.
O primeiro motivo é a propia existencia de Internet. Internet é un exemplo perfecto de rede de nodos independentes con quórums que se cruzan. A maioría dos nodos de Internet conéctanse só a algúns outros nodos locais, pero estes pequenos conxuntos se solapan o suficiente como para que se poida chegar a todos os nodos desde calquera outro nodo ao longo dalgunha ruta.
O segundo motivo é específico para a rede de pago Stellar (o uso máis común de SCP). Cada activo da rede Stellar ten un emisor e as directrices de Stellar esixen que cada emisor designe un ou máis nodos da rede para procesar as solicitudes de rescate. É do teu mellor interese incluír directa ou indirectamente estes nós nos segmentos de quórum para cada activo que che interese. Os quórums de todos os nodos interesados nun activo dado se solaparán polo menos neses nodos de rescate. Os nós interesados en varios activos incluirán todos os nodos de rescate dos respectivos emisores nos seus segmentos de quórum e procurarán agrupar todos os activos. Ademais, calquera activo que non estea vinculado deste xeito a outros da rede, e non debe estar conectado - está deseñado para que non haxa quórum para esta rede (por exemplo, os bancos da zona do dólar ás veces queren comerciar con bancos da zona euro e bancos da zona do peso, polo que están na mesma rede, pero ningún deles preocúpanse pola rede separada de nenos que venden tarxetas de béisbol).
Por suposto, expectativa o paso de quórum non é Garantía. Outros sistemas de acordos bizantinos deben gran parte da súa complexidade á garantía de quórums. Unha innovación importante de SCP é que elimina a responsabilidade de crear quórums do propio algoritmo de consenso e lévao ao nivel de aplicación. Así, aínda que o voto federado é o suficientemente xeral como para votar sobre calquera cuestión, a súa fiabilidade depende en realidade críticamente do significado máis amplo destes significados. Algúns usos hipotéticos poden non ser tan propicios para crear redes ben conectadas como outros.
Votación, aceptación e confirmación
Nunha rolda de votación federada, un nodo comeza opcionalmente a votar por algún valor V. Isto significa transmitir unha mensaxe á rede: "Son o nodo N, os meus segmentos de quórum son Q e estou votando por V". Cando un nodo vota deste xeito, promete que nunca votou en contra de V e nunca o fará.
Nas emisións peer-to-peer, cada nodo ve como votan os outros. Unha vez que un nodo recolleu suficientes destas mensaxes, pode rastrexar partes de quórum e tentar atopar quórums. Se ve quórum de compañeiros que tamén votan por V, pode proceder adopción V e transmitiu esta nova mensaxe á rede: "Son o nodo N, os meus segmentos de quórum son Q e acepto V". A aceptación proporciona unha garantía máis forte que a simple votación. Cando un nodo vota por V, nunca poderá votar por outras opcións. Pero se un nodo acepta V, ningún nodo da Rede aceptará a outra opción (o teorema 8 do libro branco de SCP así o demostra).
Por suposto, hai unha alta probabilidade de que non haxa inmediatamente un quórum de nós que concorden con V. Outros nodos poden votar por outros valores. Pero hai outra forma de que un nodo pase da simple votación á aceptación. N pode aceptar un valor diferente para W, aínda que non o votou, e aínda que non vexa quórum para iso. Para decidir cambiar o teu voto, só tes que ver conxunto de bloqueo nodos que aceptaron W. Un conxunto de bloqueo é un nodo de cada un dos segmentos de quórum N. Como o nome indica, pode bloque calquera outro significado. Se todos os nodos dese conxunto aceptan W, entón (polo Teorema 8) nunca será posible formar un quórum que tome un valor diferente e, polo tanto, tamén é seguro que N acepte W.
Nodo N con tres sectores de quórum.
BDF é un conxunto de bloqueo para N: inclúe un nodo de cada unha das porcións de N.
BE tamén é un conxunto de bloqueo para N porque E aparece en dúas porcións de N.
Pero o conxunto de bloqueo non é un quórum. Sería moi doado enganar ao nodo N para que aceptase o valor desexado se fose suficiente con cortar só un nodo en cada unha das porcións de N. Polo tanto, aceptar o valor non é o final da votación. En cambio, N debe confirmar o valor, é dicir, ver un quórum de nós que o aceptan. Se chega tan lonxe, entón, como demostra o libro branco de SCP (no Teorema 11), o resto da rede tamén acabará por confirmar o mesmo valor, polo que N finalizará o voto federado cun determinado valor como resultado.
Votación federada.
O proceso de votación, aceptación e confirmación constitúe unha rolda completa de votación federada. O protocolo de consenso Stellar combina moitas destas roldas para crear un sistema de consenso completo.
Protocolo de consenso estelar
As dúas propiedades máis importantes dun sistema de consenso son − seguridade и supervivencia. Un algoritmo de consenso é "seguro" se nunca pode dar resultados diferentes a diferentes participantes (a copia da historia de Bob nunca contradirá a Carol). "Livability" significa que o algoritmo sempre producirá un resultado, é dicir, non se atascará.
Procedemento de votación federal descrito seguro no sentido de que se un nodo confirma o valor de V, ningún outro nodo confirmará o outro valor. Pero "non confirmará outro significado" non significa que necesariamente confirmará algo. Os participantes poden votar tantos valores diferentes que nada chegará ao limiar de aceptación. Isto significa que na votación federal non hai supervivencia.
O protocolo de consenso de Stellar usa o voto federado dun xeito que garante tanto a seguridade como a supervivencia. (As garantías de seguridade e supervivencia de SCP teñen un límite teórico. O deseño escolle unha garantía de seguridade moi forte, sacrificando unha pequena mitigación de supervivencia, pero se se dá tempo suficiente, é moi probable que se chegue a un consenso). En poucas palabras, a idea é ter varios votos federados sobre varios valores ata que un deles supere todas as fases de votación SCP descritas a continuación.
Os valores sobre os que SCP busca consenso poderían ser o historial de transaccións ou unha orde de xantar ou outra cousa, pero é importante ter en conta que estes non son os valores que se aceptan ou confirman. Pola contra, a votación federal prodúcese segundo afirmacións sobre estes valores.
As primeiras roldas de votacións federais teñen lugar fase de nominación (fase de nominación), nun conxunto de afirmacións como "Nomino V", quizais para moitos valores diferentes de V. O propósito da nominación é atopar unha ou máis declaracións que pasan por aceptación e confirmación.
Despois de atopar candidatos verificables, SCP pasa á fase de votación, onde o obxectivo é atopar un determinado boletín (é dicir, un contedor para o valor proposto) e un quórum que poida declarar comprometerse por iso (comprometer). Se un quórum compromete unha votación, o seu valor é aceptado como o consenso. Pero antes de que un nodo poida votar unha comisión de votación, primeiro debe confirmar cancelación todas as papeletas cun valor de contador inferior. Estes pasos (cancelación de papeletas para atopar unha que se poida comprometer) implican varias roldas de votación federada sobre varias solicitudes de papeletas.
As seguintes seccións describen o nomeamento e a votación con máis detalle.
Nomeamento
Ao comezo da fase de nomeamento, cada nodo pode escoller espontaneamente un valor para V e votar pola declaración "Eu nomeo V". O obxectivo nesta fase é confirmar a nominación dalgún valor mediante unha votación federada.
Quizais bastantes nodos voten propostas suficientemente diferentes como para que ningunha candidatura poida alcanzar o limiar de aceptación. Por iso, ademais de emitir os seus propios votos de candidatura, os nodos "reflicten" as candidaturas dos seus compañeiros. Echo significa que se un nodo vota pola nominación V, pero ve unha mensaxe dun veciño votando pola nominación W, agora votará tanto por V como por W. (Non todos os votos dos pares se repiten durante a nominación porque isto pode provocar unha explosión de diferentes candidatos. SCP inclúe un mecanismo para regular estes votos. En resumo, existe unha fórmula para determinar a "prioridade" dun par desde o punto de vista dun nodo, e só se reflicten os votos dos nodos de alta prioridade. Canto máis longa sexa a nominación. toma, canto máis baixo sexa o limiar, polo que o nodo expande o conxunto de pares cuxos votos reflectirá. A fórmula de prioridade inclúe o número de slot como unha das súas entradas, polo que un par de alta prioridade para un espazo pode ser un par de baixa prioridade para outro, e viceversa).
Conceptualmente, a nominación é paralela, tanto V como W son votos federais separados, cada un deles capaz de acadar a aceptación ou confirmación. Na práctica, as mensaxes do protocolo SCP agrupan estes votos individuais.
Aínda que votar pola nominación de V é unha promesa de non votar nunca en contra da nominación de V, é a nivel de aplicación -neste caso SCP- onde se determina o que significa "en contra". SCP non ve unha declaración que contradiga o voto "Eu nomeo X", é dicir, non hai ningunha mensaxe "Estou en contra de nomear X", polo que o nodo pode votar para nomear calquera valor. Moitas destas candidaturas non irán a ningún lado, pero finalmente o nodo poderá aceptar ou confirmar un ou máis valores. Unha vez que se confirma un nomeado, pasa a ser candidato.
Nomeamento SCP mediante votación federada. Pode haber moitos valores "B" presentados polos compañeiros e "reflexionados" polo nodo.
As candidaturas poden dar lugar a varios candidatos confirmados. Polo tanto, SCP require que a capa de aplicación proporcione algún método para combinar os candidatos nun só composto (composto). O método de unión pode ser calquera cousa. O principal é que se este método é determinista, cada nodo combinará os mesmos candidatos. Nun sistema de votación de xantar, a "unificación" pode significar simplemente rexeitar a un dos dous candidatos. (Pero dun xeito determinista: cada nodo debe seleccionar o mesmo valor para restablecer. Por exemplo, a selección anterior por orde alfabética). Na rede de pago Stellar, onde se vota o historial de transaccións, a fusión de dous candidatos propostos implica a fusión das transaccións que conteñen e a máis recente das súas dúas marcas de tempo.
O libro branco de SCP demostra (Teorema 12) que ao final da fase de extensión, a rede finalmente converxe nun único composto. Pero hai un problema: o voto federado é un protocolo asíncrono (como SCP). Noutras palabras, os nodos non están coordinados polo tempo, senón só polas mensaxes que envían. Desde o punto de vista do nodo, non está claro cando rematou fase de ampliación. E aínda que todos os nodos chegarán finalmente ao mesmo composto, poden tomar diferentes rutas ao longo do camiño, creando diferentes candidatos compostos ao longo do camiño, e nunca poden dicir cal é o final.
Pero é normal. A nominación é só preparación. O principal é limitar o número de candidatos para lograr o consenso, que se produce no proceso postulándose para o cargo (votación).
Correndo
Boletín é unha parella , onde contador é un número enteiro que comeza en 1 e valor é un candidato da fase de candidatura. Este pode ser o propio candidato dun nodo ou o candidato dun nodo veciño aceptado por ese nodo. En liñas xerais, unha votación implica repetidos intentos de obrigar á rede a chegar a un consenso nalgún candidato nalgunha papeleta mediante a celebración de moitos votos federados nas declaracións das papeletas. Os contadores das papeletas fan un seguimento dos intentos realizados, e as papeletas con recuentos máis altos teñen prioridade sobre as papeletas con recuentos inferiores. Se o boletín queda atascado, comeza unha nova votación, agora na papeleta .
É importante distinguir valores (por exemplo, cal debe ser o pedido do xantar: pizza ou ensaladas), boletíns informativos (par de contravalor) e declaracións sobre papeletas. A rolda SCP inclúe varias roldas de votación federal, en particular nas seguintes declaracións:
- "Estou preparado para cometer a papeleta B" e
- "Anuncio a realización da papeleta B"
Desde a perspectiva dun determinado nodo, chégase ao consenso cando atopa unha papeleta B para a que pode confirmar (é dicir, atopar un quórum que acepte) a afirmación "Comprometo a papeleta B". A partir deste momento, é seguro actuar co valor especificado en B, por exemplo, facendo este pedido para o xantar. Chámase exteriorización significados. Unha vez confirmada a aceptación da papeleta, un nodo pode estar seguro de que calquera outro nodo exteriorizou o mesmo valor ou o fará no futuro.
Aínda que moitas votacións federadas realízanse conceptualmente sobre reclamacións para moitas papeletas diferentes, non intercambian tantas mensaxes porque cada mensaxe encapsula un número de papeletas. Unha mensaxe promove así o estado de moitos votos federados á vez, por exemplo: "Acepto votos de compromiso que van desde antes "
Que significan os termos "preparado" e "compromiso"?
Un nodo vota para comprometer unha papeleta cando está seguro de que outros nodos non comprometerán papeletas con valores diferentes. Convencer deste é o propósito de preparar a solicitude. Unha votación que di "Estou preparado para comprometer a papeleta B" é unha promesa de non comprometer nunca unha papeleta menor que B, é dicir, cun reconto menor (SCP require que os valores das papeletas estean nunha determinada orde. Así, o boletín informativo menos , se N1
Por que "Estou preparado para comprometer a papeleta B" significa "Prometo nunca comprometer papeletas máis pequenas que B"? Porque SCP define abortar como o contrario de commit. Unha votación para preparar unha papeleta tamén implica unha votación para descualificar outras papeletas e, como comentamos anteriormente, votar por unha cousa é unha promesa de nunca votar en contra.
Antes de emitir un commit, un nodo debe atopar primeiro un boletín que poida confirmar como está preparado. Noutras palabras, realiza unha votación federada sobre o tema "Estou preparado para comprometer a papeleta B", posiblemente en moitas papeletas diferentes, ata atopar unha que acepte quórum.
De onde saen as papeletas para preparar a votación? En primeiro lugar, o nodo transmite os preparativos para votar por <1,C>, onde C é o candidato composto producido na fase de candidatura. Non obstante, mesmo despois de que comecen os preparativos para a votación, as candidaturas poden dar lugar a que aparezan candidatos adicionais para converterse en novas papeletas. Mentres tanto, os compañeiros poden ter candidatos diferentes e poden formar un conxunto de bloqueo que acepte "Estou preparado para cometer a papeleta B2", o que convencerá ao nodo de que o acepte tamén. Por último, existe un mecanismo de tempo de espera que xera novas quendas de votación federada en novas papeletas con maior reconto se as papeletas actuais están atascadas.
En canto o nodo atopa unha papeleta B que pode confirmar como está preparada, emite unha nova mensaxe "Commit voto B". Este voto indica aos seus compañeiros que o nodo nunca renunciará a B. De feito, se B é unha papeleta , a continuación, “Compromete a papeleta " significa o consentimento incondicional para votar pola preparación de cada papeleta a <∞, s>. Este valor adicional axuda a outros pares a poñerse ao día co peer de commit se aínda están en fases anteriores do protocolo.
Nesta fase, cómpre subliñar unha vez máis que se trata de protocolos asíncronos. Só porque un nodo envíe votos positivos para un compromiso non significa que os seus compañeiros tamén o fagan. Algúns deles aínda poden estar votando declaracións en preparación para a votación, outros poden ter xa exteriorizado o significado. SCP explica como un nodo debe procesar cada tipo de mensaxe de pares independentemente da súa fase.
Se a mensaxe "Anunciei un compromiso » non se pode recibir nin confirmar, é dicir, a probabilidade de que a mensaxe sexa aceptada ou confirmada ou - ou, en todo caso, calquera papeleta co valor C, e non ningunha outra, xa que o nodo xa prometeu non cancelar nunca . Cando un nodo emita votos para un compromiso, será C ou nada, dependendo de ata onde chegue o consenso. Non obstante, isto aínda non é suficiente para que o nodo exteriorice C. Algúns pares bizantinos (que constitúen menos dun quórum, segundo os nosos supostos de seguridade) poden mentir ao nodo. Aceptar e despois confirmar algunha papeleta (ou rango de papeletas) é o que dá ao nodo a confianza para finalmente externalizar C.
Votación SCP mediante votación federada. Non se mostra: o temporizador pode apagarse en calquera momento, aumentando o reconto na papeleta (e posiblemente producindo un novo conxunto de candidatos nomeados adicionais).
E é todo! Unha vez que a rede chegou a un consenso, está lista para facelo unha e outra vez. Na rede de pago Stellar, isto ocorre aproximadamente unha vez cada 5 segundos: unha fazaña que require tanto a seguridade como a supervivencia garantidas por SCP.
SCP pode logralo confiando en varias roldas de votación federada. A votación federada é posible grazas ao concepto de segmentos de quórum: conxuntos de pares nos que cada nodo decidiu confiar como parte do seu quórum (subxectivo). Esta configuración significa que se pode alcanzar consenso incluso nunha rede con pertenza aberta e enganos bizantinos.
Máis lectura
- Pódese atopar o libro branco orixinal de SCP E borrador de especificacións para a súa execución.
- O autor orixinal do protocolo SCP, David Mazier, explícao dun xeito simplificado (pero aínda técnico). .
- Quizais se sorprendeu ao non atopar os termos "minería" ou "proba de traballo" neste artigo. SCP non usa estes métodos, pero algúns outros algoritmos de consenso si. Zane Witherspoon escribiu accesible .
- unha rede sinxela que alcanza un consenso nunha rolda completa de SCP.
- Para os lectores interesados nas implementacións de SCP: consulte , utilizado pola rede de pago Stellar ou , que escribín para unha mellor comprensión de SCP.
Fonte: www.habr.com