O protocolo de consenso estelar foi descrito pela primeira vez em um artigo científico de 2015 de David Mazier. Este é um "sistema federal do acordo bizantino", que permite que redes de computação descentralizadas sem líderes cheguem a um consenso sobre qualquer decisão. A rede de cobrança Stellar usa o Stellar Consensus Protocol (SCP) para manter um histórico de transações consistente que todos os participantes veem.

Protocolos de consenso são considerados difíceis de entender. O SCP é mais simples do que a maioria deles, mas ainda compartilha essa reputação - em parte devido à idéia errônea de que o “voto federal”, ao qual é dedicada a primeira metade do artigo científico, é o SCP. Mas isso não é verdade! Esse é apenas um componente importante, que na segunda metade do artigo é usado para criar o atual protocolo de consenso estelar.

Neste artigo, descrevemos brevemente o que é um "sistema de acordos", o que pode torná-lo "bizantino" e por que tornar o sistema bizantino "federal". Depois, explicamos o procedimento de votação federada descrito no artigo do SCP e, finalmente, o próprio protocolo do SCP.

Sistemas de acordo

O sistema de acordos permite que um grupo de participantes chegue a um consenso sobre um tópico, por exemplo, o que pedir para o almoço.

Nós da Interstellar implementamos nosso próprio sistema de organização de refeições: pedimos o que John, nosso gerente de operações, diz. Este é um sistema de contrato simples e eficaz. Todos nós confiamos em John e acreditamos que todos os dias ele encontrará algo interessante e nutritivo.

Mas e se João abusar de nossa confiança? Ele pode decidir sozinho que todos devemos nos tornar veganos. Em uma ou duas semanas, é provável que o derrubemos e o entregemos a Elizabeth. Mas de repente ela adora abacates com anchovas e acha que todo mundo deveria ficar assim. O poder corrompe. Portanto, é melhor encontrar um método mais democrático: alguma maneira de garantir que diferentes preferências sejam levadas em conta, garantindo um resultado oportuno e inequívoco, para que ninguém faça pedidos de almoço ou cinco pessoas façam pedidos diferentes, ou a discussão se prolongará até a noite.

Parece que a solução é simples: vote! Mas essa é uma impressão enganosa. Quem coletará as cédulas e reportará os resultados? E por que o resto deveria acreditar no que ele diz? Talvez possamos votar primeiro no líder em quem confiamos para liderar a votação - mas quem liderará essa primeira votação? E se não pudermos concordar com um líder? Ou, se concordarmos, e esse líder ficar preso em uma reunião ou sair para licença médica?

Problemas semelhantes são encontrados em redes de computadores distribuídas. Todos os participantes ou nós devem concordar com alguma solução, por exemplo, de quem é a vez de atualizar o arquivo compartilhado ou executar a tarefa da fila de processamento. Em uma rede de criptomoedas, os nós precisam escolher repetidamente como a história completa se parece entre várias versões possíveis que às vezes entram em conflito. Este contrato de rede dá ao destinatário a garantia de que a moeda é (a) válida (não falsificada) e (b) ainda não foi gasta em outro lugar. Também garante que ele possa gastar moedas no futuro porque o novo destinatário terá as mesmas garantias pelos mesmos motivos.

Qualquer sistema correspondente em uma rede de computadores distribuída deve ser tolerante a falhas: deve fornecer resultados consistentes, apesar de erros, como linhas de comunicação lentas, nós não responsivos e ordem incorreta de mensagens. O sistema de acordos bizantino é adicionalmente resistente a erros “bizantinos”: nós que fornecem informações falsas, devido a um erro ou em uma tentativa deliberada de prejudicar o sistema ou obter alguma vantagem. A resiliência “bizantina” - a capacidade de confiar em uma decisão do grupo, mesmo quando alguns membros do grupo podem mentir ou não seguir as regras da tomada de decisão - é chamada de parábola dos generais do Império Bizantino que tentaram coordenar o ataque. Anthony Stevens tem uma boa descrição .

Considere o dono da moeda criptográfica Alice, que deve escolher entre comprar um sorvete delicioso de Bob e pagar a dívida de Carol. Talvez Alice queira pagar os dois ao mesmo tempo, gastando fraudulentamente a mesma moeda. Para fazer isso, ela deve convencer o computador de Bob que a moeda nunca foi paga a Carol e convencer o computador de Carol que a moeda nunca foi paga a Bob. O sistema bizantino de convenções torna isso praticamente impossível usando uma forma de regra majoritária chamada quorum . Um nó dessa rede se recusa a mudar para uma determinada versão do histórico até ver que um número suficiente de nós de mesmo nível - um quorum - concorda com essa transição. Assim que isso acontecer, eles formarão um bloco eleitoral suficientemente grande para forçar os demais nós da rede a concordar com sua decisão. Alice pode fazer com que alguns nós fiquem em seu nome, mas se a rede for grande o suficiente, sua tentativa será reprimida pelas vozes de nós honestos.

Quantos nós são necessários para um quorum? No mínimo, uma maioria, ou melhor, uma maioria qualificada, para combater erros e fraudes. Mas, para calcular a maioria, você precisa saber o número total de participantes. No escritório da Interstellar ou nas eleições distritais, esses números são fáceis de reconhecer. Mas se o seu grupo é uma rede mal definida na qual os nós podem entrar e sair como desejado sem coordenação com o centro, você precisa de um sistema federal de acordos bizantinos que possa determinar quóruns não a partir de uma lista predeterminada de nós, mas dinamicamente, a partir de uma constante mudança e inevitavelmente incompleta instantâneo de nós em um determinado ponto no tempo.

Pode não parecer possível criar um quorum em termos de um único nó em uma rede extensa, mas é possível. Esse quorum pode até garantir os resultados de uma votação descentralizada. O white paper do SCP mostra como fazer isso usando um procedimento chamado votação federada .

Para os impacientes

O restante do artigo detalha a votação federal e o protocolo de consenso estelar. Se você não está interessado nos detalhes, aqui está uma visão geral do processo.

1. Os nós conduzem rodadas de votação federal sobre os "nomeados". Uma rodada de votação federal significa:
   
   • O nó vota em qualquer declaração, por exemplo, "proponho o valor de V";
     
   • O nó ouve as vozes das festas até encontrar uma que possa "receber";
     
   • O nó está procurando um "quorum" para esta declaração. O quorum "confirma" o candidato.
2. Assim que um nó pode confirmar um ou mais candidatos, ele tenta "preparar" uma "votação" através de várias rodadas de votação federal.
   
3. Assim que o nó é capaz de verificar a prontidão da votação, ele tenta alimentá-lo com ainda mais rodadas de votação federada.
   
4. Quando um site pode confirmar a confirmação de um boletim, ele pode "externalizar" o valor desse boletim, usando-o como resultado de consenso.

Essas etapas incluem várias rodadas de votação federada, que juntas formam uma rodada do SCP. Examinaremos mais detalhadamente o que acontece a cada passo.

Voto Federado

A votação federada é o processo de determinar se uma rede pode concordar com uma proposta. Em uma rodada de votação, cada nó deve selecionar um dos muitos valores possíveis. Ele não pode fazer isso até ter certeza de que outros nós na rede não escolherão um resultado diferente. Para ter certeza disso, os nós trocam uma enxurrada de mensagens para frente e para trás, para que todos confirmem que o quorum de nós toma a mesma decisão . O restante desta seção explica os termos desta sentença e como todo o procedimento ocorre.

Quóruns e fatias de quórum

Vamos começar definindo um quorum. Como discutimos acima, em uma rede descentralizada com associação dinâmica, é impossível saber antecipadamente o número de nós e, portanto, quanto é necessário para a maioria. A votação federada resolve esse problema, introduzindo uma nova idéia para a fatia de quorum: um pequeno conjunto de nós de pares nos quais o nó confia para transmitir informações de status de votação no restante da rede. Cada nó define sua própria fatia de quorum (da qual ele se torna um membro de fato).

A formação de quorum começa com um corte de quorum. Para cada nó, nós da sua fatia são adicionados. Em seguida, membros slicer desses nós são adicionados e assim por diante. À medida que você continua, mais e mais nós aparecem e não podem ser adicionados, porque eles já estão incluídos na fatia. Quando não há mais novos nós a serem adicionados, o processo é interrompido: formamos um quorum por "fechamento transitivo" cortando o quorum do nó inicial.


Para encontrar o quorum desse nó ...


... adicione membros à sua fatia ...


... adicione membros slicer a esses nós.


Continue até que não haja nós a serem adicionados.




Nenhum nó a ser adicionado à esquerda. Este é um quorum.

De fato, cada nó pode entrar em mais de uma fatia. Para formar um quorum, selecione apenas uma das fatias e adicione membros; selecione qualquer fatia para cada membro e adicione membros a essa fatia e assim por diante. Isso significa que cada nó é membro de muitos quóruns possíveis.


Selecione apenas uma fatia de quorum em cada etapa.






Um quorum possível. Ou uma alternativa ...


... selecione outras fatias ...




... (quando possível) ...


... cria outro quorum.

Como um nó sabe em quais fatias os outros nós estão? Da mesma maneira que outras informações sobre outros nós: das transmissões que cada nó transmite para a rede quando seu status de votação é alterado. Cada transmissão inclui informações sobre fatias do nó de envio. O documento técnico do SCP não especifica um mecanismo de comunicação. As implementações geralmente usam o protocolo de fofocas para garantir a transmissão de mensagens pela rede.

Lembre-se de que em um sistema bizantino não federal de acordos, um quorum é definido como a maioria de todos os nós. O sistema bizantino de acordos foi desenvolvido do ponto de vista da pergunta: quantos nós desonestos o sistema pode suportar? Em um sistema de N nós projetado para sobreviver com falhas de f (truques), o nó deve poder progredir recebendo uma resposta dos pares de N - f, pois f deles pode não funcionar. Porém, tendo recebido uma resposta de N - f pares, podemos assumir que todos os pares (dos quais o nó não recebeu uma resposta) são realmente honestos. Assim, f de N - f pares (dos quais uma resposta é recebida) são maliciosos. Para que os nós cheguem ao mesmo consenso, a maioria dos nós restantes deve ser honesta, ou seja, precisamos que N - f seja maior que 2f ou N> 3f. Portanto, geralmente um sistema projetado para sobreviver a falhas f terá um total de N = 3f + 1 nós e um tamanho de quorum de 2f + 1. Assim que a proposta ultrapassa o limiar do quorum, o restante da rede está convencido de que qualquer proposta concorrente falhará. Então a rede converge para o resultado.

Mas em um sistema bizantino federal de acordos, não só não pode haver uma maioria (porque ninguém sabe o tamanho total da rede), mas o conceito de maioria é geralmente inútil! Se a associação ao sistema estiver aberta, alguém poderá obter a maioria simplesmente conduzindo o chamado ataque Sibyl: ingressando na rede repetidamente através de vários nós. Então, por que o fechamento transitivo de uma fatia pode ser chamado de quorum e como é capaz de suprimir ofertas concorrentes?

Tecnicamente, de jeito nenhum! Imagine uma rede de seis nós, onde dois triplos são isolados em fatias do quorum um do outro. O primeiro subgrupo pode tomar uma decisão sobre a qual o segundo nunca ouvirá e vice-versa. Não há como esta rede alcançar consenso (exceto por acaso).

Portanto, o SCP exige que a rede tenha uma propriedade chamada cruzamento de quorum para votação federada (e para aplicar importantes teoremas de artigos). Em uma rede com essa propriedade, quaisquer dois quóruns que podem ser criados sempre se sobrepõem em pelo menos um nó. Determinar o clima predominante da rede é tão bom quanto ter a maioria. Intuitivamente, isso significa que, se um quorum concordar com a afirmação X, nenhum outro quorum poderá concordar com outra coisa, porque incluirá necessariamente algum nó do primeiro quorum que já votou em X.


Se a rede tiver uma interseção de quóruns ...


... então quaisquer dois quóruns que você possa construir ...


... sempre se cruzam.





(É claro que os nós sobrepostos podem se tornar mentirosos bizantinos ou ruins em outros aspectos. Nesse caso, a interseção de quóruns não ajuda a rede a concordar. Por esse motivo, muitos dos resultados no documento técnico do SCP são baseados em suposições explícitas, como o que permanece na rede interseção de quóruns, mesmo após a remoção de nós ruins . Para simplificar, deixamos essas suposições implícitas no restante do artigo).

Pode parecer irracional esperar que em uma rede de nós independentes seja possível uma interseção confiável de quóruns. Mas há duas razões pelas quais isso é verdade.

A primeira razão é a existência da própria Internet. A Internet é um exemplo ideal de uma rede de nós independentes com interseção de quóruns. A maioria dos sites na Internet se conecta a apenas alguns outros sites locais, mas esses pequenos conjuntos se sobrepõem o suficiente para tornar cada site acessível a partir de qualquer outro site em uma rota específica.

O segundo motivo é específico da rede de pagamento estelar (o uso mais comum do SCP). Cada ativo na rede Stellar possui um emissor, e as recomendações Stellar exigem que cada emissor designe um ou mais nós na rede para processar solicitações de pagamento. É do seu interesse incluir direta ou indiretamente esses nós nas fatias de quorum para cada ativo no qual você está interessado. Em seguida, os quóruns de todos os nós interessados ​​neste ativo se sobreporão pelo menos nesses nós de reembolso. Os nós interessados ​​em vários ativos incluirão em suas fatias de quorum todos os nós de pagamento dos respectivos emissores e procurarão combinar todos os ativos. Além disso, todos os ativos que não estão conectados de maneira a outros na rede e não devem estar conectados - ele se destina a que não haja cruzamento de quorum para essa rede (por exemplo, bancos da zona do dólar às vezes desejam negociar com bancos da zona do euro e bancos da zona do peso, para que estejam na mesma rede, mas nenhum deles se preocupa com uma rede separada de crianças que vendem cartões de beisebol).

Obviamente, esperar pela interseção de quóruns não é uma garantia . Outros sistemas de acordos bizantinos devem grande parte de sua complexidade à garantia de quóruns. Uma inovação importante do SCP é que ele remove a responsabilidade de criar quóruns do próprio algoritmo de consenso e o leva ao nível do aplicativo. Assim, embora uma votação federada seja suficientemente geral para votar em qualquer questão, de fato sua confiabilidade depende criticamente do significado mais amplo desses valores. Alguns usos hipotéticos podem não ser tão convenientes para a construção de redes bem conectadas quanto outros.

Votação, aceitação e confirmação

Na rodada de votação federal, o nó opcionalmente começa a votar por algum valor de V. Isso significa que a mensagem é enviada à rede: "Eu sou o nó N, minhas fatias de quorum são Q e eu voto em V". Quando um nó vota dessa maneira, ele promete que nunca votou contra V e nunca votará.

Nas transmissões de nós ponto a ponto, cada nó vê como os outros votam. Assim que o nó coleta um número suficiente dessas mensagens, ele pode rastrear fatias de quorum e tentar encontrar quorums. Se ele vir um quorum de colegas que também votam em V, ele poderá aceitar V e transmitir esta nova mensagem para a rede: “Eu sou o nó N, minhas fatias são o quorum Q e eu aceito V”. A aceitação oferece uma garantia mais forte do que uma simples votação. Quando um nó vota em V, nunca pode votar em outras opções. Mas se um nó aceitar V, nenhum nó na Web aceitará outra opção (o Teorema 8 no white paper técnico SCP prova isso).

Obviamente, é altamente provável que não exista imediatamente um quorum de nós que concordem com V. Outros nós podem votar em outros valores. Mas, para o site, existe outra maneira de passar da votação simples à aceitação. N pode assumir um valor diferente de W, mesmo que não tenha votado nele e mesmo que não veja um quorum para ele. Para decidir mudar sua voz, basta ver um conjunto de nós de bloqueio que aceitaram W. Um conjunto de bloqueio é um nó em cada uma das fatias dos quóruns de N. Como o nome indica, ele pode bloquear qualquer outro valor. Se todos os nós nesse conjunto adotarem W, então (pelo Teorema 8) nunca será possível formar um quorum assumindo um valor diferente e, portanto, também é seguro aceitar W.


Nó N com três fatias de quorums.


BDF é um conjunto de bloqueio para N: inclui um nó de cada uma das N fatias.


BE N, E N.

— . N, , N. — . N , , . , , SCP ( 11), , N .


.

, . Stellar .

Stellar

— . «», ( ). «» , , .

, V, . « » — , - . , . , .

Stellar , , . ( SCP . , , , ). , , , SCP, .

, SCP , , - , , , . .

(nomination phase), « V», , V. — , .

SCP , , ( ) , (commit). , . , . — , , — .

.

No início do estágio de nomeação, cada nó pode selecionar espontaneamente o valor V e votar na declaração "Estou nomeando V". O objetivo nesta fase é confirmar a nomeação de um determinado valor através de uma votação federal.

, , . , «» . (echo) , V, , W, V, W. ( , . SCP . , «» , . , , , . , , ).

V, W — , . SCP .

V — V, — SCP — , «». SCP , « X», « X», . , . , .


Nomeando SCP usando votação federada. Pode haver muitos valores "B" pressionados pelos pares e "refletidos" pelo par.

A nomeação de candidatos pode resultar em vários candidatos confirmados. Portanto, o SCP exige que a camada de aplicativo forneça algum método de combinação de candidatos em um composto. (composite). . , , . «» . ( : . , ). Stellar, , , , .

SCP ( 12), . : — ( SCP). , , , . , . , , , , .

. — . , (balloting).

— <counter,value>, counter — , 1, value — . , . , - - . , . <counter, value> , , <counter+1, value>.

(, : ), ( counter-value) . SCP , , :

• « B»
  
• « B»

Do ponto de vista desse nó, é alcançado um consenso ao encontrar o Boletim B para o qual ele pode confirmar (ou seja, encontrar um quorum que aceite) a declaração "Declaro compromisso com o Boletim B". A partir de agora, você poderá agir com segurança no valor especificado em B - por exemplo, faça esse pedido para o almoço. Isso é chamado de externalização do valor. Depois de confirmada a aceitação da votação, o nó pode ter certeza de que qualquer outro nó externalizou o mesmo valor ou o comprometerá definitivamente no futuro.

Embora conceitualmente muitas cédulas federadas sejam mantidas em aplicativos para muitas cédulas diferentes, elas não trocam tantas mensagens porque cada mensagem encapsula várias cédulas. Uma mensagem, portanto, promove o estado de muitos votos federados de uma só vez, por exemplo: "Aceito comissões de cédula no intervalo de <min, V> a <max, V>".

O que significam os termos "preparado" e "confirmar"?

Um nó vota para cometer uma votação quando está convencido de que outros nós não irão cometer valores com valores diferentes. Convencer este é o objetivo de preparar a declaração. Uma votação que diz "Estou pronto para enviar o boletim B" é uma promessa de nunca enviar um boletim menor que B, ou seja, com um contador mais baixo (o SCP exige que os valores nos boletins tenham uma certa ordem.) O boletim <N1, V1> é menor que <N2, V2> se N1 <N2 e também se N1 = N2 e V1 <V2). Essas cédulas menores são "abortadas" durante a votação preparatória, enquanto B é considerado "preparado".

Por que "estou pronto para cometer o boletim B" significa "prometo nunca cometer menos do que B"? Porque o SCP define abortar como o oposto de confirmar. Votar na preparação da cédula também implica votar para cancelar outras cédulas e, como discutimos anteriormente, votar em uma coisa é uma promessa de nunca votar contra.

Antes de transmitir o commit, o site deve primeiro encontrar o boletim, que pode ser confirmado conforme preparado. Em outras palavras, ele realiza uma votação federada sobre "Estou pronto para me comprometer com o Boletim B", talvez para muitas cédulas diferentes, até encontrar uma que aceite o quorum.

De onde vêm os boletins de voto para votar? Primeiro, o nó transmite os preparativos para votar em <1, C>, onde C é o candidato composto produzido no estágio de nomeação. No entanto, mesmo após o início dos preparativos para a votação, a indicação pode levar ao aparecimento de candidatos adicionais que se tornarão novas cédulas. Enquanto isso, os pares podem ter candidatos diferentes e podem formar um conjunto de bloqueio que aceita "Estou pronto para confirmar o boletim B2", o que convencerá o nó a aceitá-lo também. Finalmente, existe um mecanismo de tempo limite que gera novas rodadas de votação federada em novas cédulas com contadores mais altos se as cédulas atuais estiverem emperradas.

Assim que o nó encontra o Boletim B, que pode ser confirmado como preparado, ele transmite uma nova mensagem, "Boletim B Confirmar". Essa votação diz aos colegas que o nó nunca desistirá de B. Na verdade, se B for uma votação <N, C>, então "Commit Bulletin <N, C>" significa consentimento incondicional para votar na prontidão de cada votação de <N, C> a <∞, s>. Esse valor adicional ajuda outros nós a acompanhar uma consolidação, se eles ainda estiverem nos estágios anteriores do protocolo.

Nesse estágio, vale ressaltar mais uma vez que estes são protocolos assíncronos. Só porque um nó envia votos para uma consolidação não significa que seus pares também o façam. Alguns deles ainda podem votar em pedidos de preparação para votação, outros já podem ter externalizado o significado. O SCP explica como um nó deve processar cada tipo de mensagem de pares, independentemente de sua fase.

Se a mensagem "Declaro um commit <N, C>" não puder ser aceita ou confirmada, ou seja, a probabilidade de aceitação ou confirmação da mensagem <N + 1, C> ou <N + 2, C> - ou, em qualquer caso, qualquer boletim com um valor de C, e nenhum outro, pois o nó já prometeu nunca cancelar <N, C>. Quando o nó transmitir os votos para o commit, ele será C ou nada, dependendo da extensão do consenso. No entanto, isso não é suficiente para o nó externalizar C. Algumas festas bizantinas (menos de um quorum, com base em nossas suposições sobre segurança) podem estar no nó. A adoção e a confirmação de uma determinada cédula (ou variedade de cédulas) é o que dá ao nó a confiança para finalmente externalizar C.


SCP em execução através da votação federada. Não mostrado: a qualquer momento um cronômetro pode funcionar, aumentando o contador na votação (e, possivelmente, produzindo um novo composto a partir de candidatos nomeados adicionais).

E isso é tudo! Uma vez que a rede alcançou consenso, ela está pronta para fazê-lo novamente e novamente. Na rede de cobrança Stellar, isso acontece aproximadamente a cada 5 segundos: um feito que requer segurança e capacidade de sobrevivência, garantido pelo SCP.

O SCP pode conseguir isso confiando em várias rodadas de votação federada. A votação federada foi possível graças ao conceito de fatias de quorum: conjuntos de nós de pares nos quais cada nó decidiu confiar como parte de seu quorum (subjetivo). Essa configuração significa que você pode obter consenso mesmo em uma rede com associação aberta e engano bizantino.

Leitura adicional

• O documento técnico original do SCP pode ser encontrado aqui , e aqui está o rascunho das especificações para sua implementação.
  
• O autor original do protocolo SCP, David Mazier, simplifica (mas ainda tecnicamente) explica aqui .
  
• Você pode se surpreender ao não encontrar os termos "mineração" ou "prova de trabalho" neste artigo. O SCP não usa esses métodos, mas alguns outros algoritmos de consenso o fazem. Zane Witherspoon escreveu uma revisão acessível de algoritmos de consenso .
  
• Uma descrição passo a passo de uma rede simples que alcança consenso em uma rodada completa de SCP.
  
• Para leitores interessados ​​em implementações de SCP: consulte o código C ++ usado pela rede de pagamentos Stellar ou o código Go que escrevi para entender melhor o SCP.