O protocolo de consenso Stellar foi descrito pela primeira vez em de David Mazières em 2015. Trata-se de um "sistema federal de consenso bizantino" que permite que redes computacionais descentralizadas, sem líderes, alcancem efetivamente um consenso sobre qualquer decisão. A rede de pagamentos Stellar utiliza o Stellar Consensus Protocol (SCP) para manter um histórico consistente de transações, visível a todos os participantes.
Acredita-se que os protocolos de consenso sejam difíceis de entender. O SCP é mais simples que a maioria deles, mas ainda assim carrega essa reputação — em parte devido à ideia equivocada de que a "votação federativa", discutida na primeira metade do artigo científico, é o SCP. Mas não é! É apenas um bloco de construção importante que, na segunda metade do artigo, é utilizado para formar o real protocolo de consenso Stellar.
Neste artigo, apresentaremos brevemente o que é um "sistema de acordos", o que pode torná-lo "bizantino" e por que tornar um sistema bizantino "federal". Em seguida, explicaremos o processo de votação federativa, descrito no artigo sobre o SCP, e, finalmente, explicaremos o próprio protocolo SCP.
Sistemas de acordos
Um sistema de acordos permite que um grupo de participantes chegue a um consenso sobre algum tópico, como o que pedir para o almoço.
Na empresa Interstellar, implementamos nosso próprio sistema de acordos para o almoço: pedimos o que nosso gerente operacional, John, diz. É um sistema simples e eficaz. Todos confiamos em John e acreditamos que ele encontrará algo interessante e nutritivo todos os dias.
Mas e se John abusar de nossa confiança? Ele pode decidir unilateralmente que todos devemos nos tornar veganos. Em uma ou duas semanas, provavelmente o deporemos e passaremos o poder para Elizabeth. Mas, de repente, ela adora abacate com anchovas e acha que todos devem ser assim. O poder corrompe. Por isso, é melhor encontrar um método um pouco mais democrático: uma maneira de garantir que diferentes preferências sejam consideradas, ao mesmo tempo em que se assegura um resultado claro e atempado, para que não aconteça que ninguém peça almoço ou que cinco pessoas façam pedidos diferentes, ou que a discussão se arraste até a noite.
À primeira vista, a solução parece simples: realizar uma votação! Mas essa é uma impressão enganadora. Quem irá coletar os votos e informar os resultados? E por que os outros deveriam acreditar no que ele diz? Talvez possamos primeiro votar em um líder que confiamos para conduzir a votação — mas quem irá liderar este primeiro votação? E se não conseguirmos concordar com um líder? Ou se chegarmos a um acordo, mas esse líder ficar preso em uma reunião ou sair doente?
Problemas semelhantes ocorrem em redes computacionais distribuídas. Todos os participantes ou nós devem concordar com alguma decisão, como quem deve atualizar um arquivo compartilhado ou retirar uma tarefa da fila de processamento. Em uma rede de criptomoedas, os nós frequentemente precisam escolher como se parece a história completa, a partir de várias versões possíveis que podem entrar em conflito. Esse consenso de rede garante ao destinatário que a moeda é (a) válida (não falsificada) e (b) ainda não foi gasta em outro lugar. Também garante que ele poderá gastar as moedas no futuro, porque o novo destinatário terá as mesmas garantias pelos mesmos motivos.
Qualquer sistema de consenso em uma rede computacional distribuída deve ser tolerante a falhas: ele 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 consenso bizantino é adicionalmente resistente a erros 'bizantinos': nós que fornecem informações falsas, seja por erro ou em uma tentativa deliberada de sabotar o sistema ou obter alguma vantagem. A resistência 'bizantina' — a capacidade de confiar na decisão de um grupo, mesmo quando alguns membros do grupo podem mentir ou de outra forma não seguir as regras de tomada de decisão — recebeu esse nome da , que tentavam coordenar um ataque. pode ser encontrada em Anthony Stevens.
Vamos considerar a proprietária da criptomoeda, Alice, que deve escolher entre comprar um delicioso sorvete com Bob e pagar a dívida com Carol. É possível que Alice queira pagar ambos ao mesmo tempo, gastando fraudulentamente a mesma moeda. Para isso, ela deve convencer o computador de Bob de que a moeda nunca foi paga a Carol e convencer o computador de Carol de que a moeda nunca foi paga a Bob. Um sistema de acordos bizantino torna isso praticamente impossível, utilizando uma forma de regra da maioria, chamada quórum. Um nó em tal rede recusa mudar para uma determinada versão da história até ver que um número suficiente de nós homogêneos — o quórum — concorda com essa mudança. Assim que isso acontecer, eles formarão um bloco eleitoral suficiente para forçar os nós restantes da rede a concordar com sua decisão. Alice pode fazer alguns nós mentirem em seu nome, mas se a rede for grande o suficiente, sua tentativa será dominada pelas vozes dos nós honestos.
Quantos nós são necessários para um quórum? No mínimo, a maioria, ou mais precisamente, a maioria qualificada para combater erros e fraudes. Mas para contar a maioria, é necessário saber o número total de participantes. Em um escritório da Interstellar ou em eleições de distrito, esses números são fáceis de obter. Mas se seu grupo é uma rede vagamente definida, onde os nós podem entrar e sair à vontade sem coordenação com um centro, então é necessário um sistema federativo de acordo bizantino, capaz de determinar quóruns não a partir de uma lista previamente definida de nós, mas dinamicamente, de uma imagem constantemente mutável e inevitavelmente incompleta dos nós em um determinado momento.
Pode parecer impossível criar um quórum do ponto de vista de um único nó em uma vasta rede, mas isso é possível. Esse quórum pode até garantir resultados em votações descentralizadas. O documento técnico SCP mostra como fazer isso através de um procedimento chamado votação federativa.
Para os impacientes
O restante do artigo descreve em mais detalhes a votação federativa e o protocolo de consenso Stellar. Se você não está interessado nos detalhes, aqui está uma visão geral do processo.
- Os nós realizam rodadas de votação federal sobre "nomeações". Uma rodada de votação federativa significa:
- O nó vota em alguma proposta, como "Eu sugiro o valor V";
- O nó ouve os votos dos pares até encontrar um que possa "aceitar";
- O nó busca um "quorum" para essa proposta. O quorum "confirma" o nomeado.
- Assim que o nó pode confirmar um ou mais nomeados, ele tenta "preparar" o "boleto" através de várias rodadas de votação federativa.
- Assim que o nó é capaz de verificar a prontidão do boleto, ele tenta confirmá-lo com ainda mais rodadas de votação federativa.
- Assim que o nó pode confirmar o compromisso do boleto, ele pode "externalizar" o valor desse boleto, usando-o como resultado de consenso.
Essas etapas incluem várias rodadas de votação federativa que em conjunto formam uma rodada SCP. Vamos analisar mais detalhadamente o que acontece em cada etapa.
Votação federativa
A votação federativa é um procedimento para determinar se a rede pode concordar com uma proposta. Na rodada de votação, cada nó deve escolher um entre muitos valores potenciais. Ele não pode fazer isso até ter certeza de que outros nós na rede não escolherão um resultado diferente. Para garantir isso, os nós trocam uma enxurrada de mensagens de ida e volta para que cada confirmou, mesmo sem otimização para essas tarefas, tem sucesso em outra área: . nó aceita o mesmo uma solução. O restante desta seção explica os termos nesta proposta e como o processo inteiro ocorre.
Quorums e cortes de quorum
Vamos começar definindo quorum. Como discutimos acima, em uma rede descentralizada com adesão dinâmica, é impossível saber de antemão quantos nós existem e, consequentemente, quantos são necessários para a maioria. A votação federativa resolve esse problema apresentando uma nova ideia de corte de quorum quorum slice: um pequeno conjunto de nós iguais que o nó confia para transmitir informações sobre o estado da votação ao restante da rede. Cada nó define seu próprio corte de quorum (do qual se torna membro por fato).
A formação do quorum começa com o corte de quorum. Para cada nó, os nós de seu corte são adicionados. Em seguida, são adicionados os membros dos cortes desses nós E assim por diante. À medida que avançamos, encontramos cada vez mais nós que não podemos adicionar, pois já estão incluídos no corte. Quando não houver mais nós novos para adicionar, o processo termina: formamos um quórum por meio do "fechamento transitivo" do corte do nó inicial.
Para encontrar um quórum a partir de um dado nó...
… adicionamos membros do seu corte...
… em seguida, adicionamos membros dos cortes desses nós.
Continuamos até que não haja mais nós para adicionar.
Não restam mais nós para adicionar. Este é o quórum.
Na verdade, cada nó pode fazer parte de mais de um corte. Para formar um quórum, escolha apenas um dos cortes e adicione os membros; em seguida, escolha qualquer corte para cada um dos membros e adicione os membros disso do corte e assim por diante. Isso significa que cada nó é membro de um conjunto de possíveis quóruns.
Escolha apenas um corte de quórum a cada passo.
Um possível quórum. Ou uma alternativa...
… escolhemos outros cortes...
… (quando possível)…
… cria um outro quórum.
Como um nó descobre em quais cortes outros nós estão? Exatamente como outras informações sobre outros nós: das transmissões que cada nó transmite pela rede quando seu estado de votação muda. Cada transmissão inclui informações sobre os cortes do nó que está enviando. O documento técnico SCP não especifica o mecanismo de comunicação. Implementações geralmente usam para garantir a transmissão de mensagens por toda a rede.
Lembre-se de que, no sistema de acordos bizantinos não federativos, o quórum é definido como a maioria de todos os nós. O sistema de acordos bizantinos foi desenvolvido sob a perspectiva da questão: quantos nós desonestos o sistema pode suportar? Em um sistema de N nós projetado para sobreviver a f falhas (trapaças), um nó deve ser capaz de progredir ao receber respostas de N−f pares, uma vez que f deles podem não estar funcionando. Contudo, ao receber respostas de N−f pares, pode-se supor que todos os f pares (dos quais o nó não recebeu resposta) são, na verdade, honestos. Assim, os f de N−f pares (dos quais foi recebida resposta) são os maliciosos. Para que os nós cheguem a um consenso, a maioria dos demais nós deve ser honesta, ou seja, precisamos que N−f seja maior que 2f ou N > 3f. Portanto, geralmente um sistema projetado para sobreviver a f falhas terá um total de N=3f+1 nós e um tamanho de quórum de 2f+1. Assim que a proposta ultrapassa o limite do quórum, os demais membros da rede estão convencidos de que quaisquer propostas concorrentes falharão. Assim, a rede converge para um resultado.
Mas, no sistema de acordos bizantinos federativos, não pode haver uma maioria (uma vez que ninguém conhece o tamanho total da rede), e o conceito de maioria é, de fato, inútil! Se a adesão ao sistema for aberta, alguém pode obter a maioria simplesmente realizando o que é chamado de ataque de Sybil: unindo-se repetidamente à rede através de vários nós. Então, por que o fechamento transitivo do corte pode ser chamado quórum, e como ele é capaz de suprimir propostas concorrentes?
Tecnicamente, não! Imagine uma rede de seis nós, onde dois grupos de três estão isolados dentro dos seus próprios cortes de quórum. O primeiro subgrupo pode tomar uma decisão da qual o segundo nunca ouvirá, e vice-versa. Para essa rede, não há como alcançar um consenso (exceto por acaso).
Por isso, o SCP requer que, para a votação federativa (e para a aplicação de teoremas importantes do artigo), a rede deve possuir uma propriedade chamada interseção de quóruns. Na rede com essa propriedade, quaisquer dois quóruns que possam ser formados sempre se sobrepõem em pelo menos um nó. Para determinar os sentimentos predominantes da rede, isso é quase tão bom quanto ter a maioria. Intuitivamente, isso significa que se algum quórum concorda com a afirmação X, nenhum outro quórum poderá concordar com algo diferente, pois necessariamente incluirá algum nó do primeiro quórum que já votou em X.
Se houver interseções de quóruns na rede…
… então quaisquer dois quóruns que você puder formar…
… sempre se sobreporão.
(Claro, os nós sobrepostos podem ser bizantinos, enganadores ou ruins de outras maneiras. Nesse caso, a interseção dos quóruns não ajuda a rede a concordar de forma alguma. Por essa razão, muitos resultados no documento técnico SCP se baseiam em suposições claramente expressas, como a de que a rede ainda possui interseções de quóruns mesmo após a remoção de nós problemáticos. Para simplificar, deixaremos essas suposições não explícitas no restante do artigo).
Pode parecer irrazoável esperar que uma rede de nós independentes possa ter uma interseção de quóruns confiável. Mas há duas razões pelas quais isso acontece.
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ções de quóruns. A maioria dos nós na internet se conecta apenas a alguns outros nós locais, mas esses pequenos conjuntos se sobrepõem o suficiente para que cada nó seja acessível a partir de qualquer outro nó de uma forma ou de outra.
A segunda razão é específica para a rede de pagamento Stellar (a aplicação mais comum do SCP). Cada ativo na rede Stellar tem um emissor, e as recomendações do Stellar exigem que cada emissor nomeie um ou mais nós na rede para processar os pedidos de resgate. É do seu interesse incluir esses nós diretamente ou indiretamente nos cortes de quórum para cada ativo que lhe interessar. Assim, os quóruns para todos os nós interessados neste ativo se sobreporão pelo menos nesses nós de resgate. Nós interessados em vários ativos incluirão em seus cortes de quórum todos os nós de resgate dos respectivos emissores, e eles buscarão unir todos os ativos juntos. Além disso, quaisquer ativos que não estejam assim relacionados a outros na rede e não devem estar relacionados — foram projetados para que não haja sobreposição de quóruns nesta rede (por exemplo, bancos na área do dólar às vezes querem negociar com bancos da área do euro e bancos da área do peso, portanto estão na mesma rede, mas nenhum deles se importa com uma rede separada de crianças negociando cartões de beisebol).
Claro, a expectativa de sobreposição de quóruns não é uma garantia. Outras системы de acordo bizantino, com sua complexidade, devem muito à garantia de quóruns. Uma inovação importante do SCP é que ele remove a responsabilidade pela criação de quóruns do próprio algoritmo de consenso e o passa para o nível de aplicação. Assim, embora a votação federativa seja bastante geral para a votação sobre quaisquer questões, na verdade sua confiabilidade depende criticamente do significado mais amplo desses valores. Alguns tipos de uso hipotéticos podem não ser tão convenientes para a criação de redes bem conectadas quanto outros.
Votação, aceitação e confirmação
Na rodada de votação federativa, um nó opcionalmente começa a votar em algum valor V. Isso significa transmitir na rede a mensagem: 'Eu sou o nó N, meus cortes de quórum Q, e eu voto em V'. Quando um nó vota dessa forma, ele promete que nunca votou contra V e nunca o fará.
Nas transmissões a partir de nós pareados, cada nó vê como os outros votam. Assim que um nó coleta um número suficiente de mensagens desse tipo, ele pode rastrear os cortes de quóruns e tentar encontrar quóruns. Se ele vê um quórum de pares que também votam em V, ele pode passar para a aceitação de V e transmitir essa nova mensagem pela rede: "Eu sou o nó N, meus cortes de quórum Q, e eu aceito V". A aceitação fornece uma garantia mais forte do que uma simples votação. Quando um nó vota em V, ele nunca pode votar em outras opções. Mas se um nó aceita V, nenhum nó na Rede nunca aceitará outra opção (teorema 8 no documento técnico SCP prova isso).
Claro, há uma alta probabilidade de que um quórum de nós que concordem com V não seja encontrado imediatamente. Outros nós podem votar em outros valores. Mas para o nó, há outra maneira de passar da simples votação para a aceitação. N pode aceitar outro valor W, mesmo que não tenha votado nele e mesmo que não veja um quórum para ele. Para decidir mudar seu voto, basta ver um conjunto bloqueador de nós que aceitaram W. Um conjunto bloqueador é composto por um nó de cada um dos cortes de quórum de N. Como o nome sugere, ele é capaz de bloquear qualquer outro valor. Se todos os nós nesse conjunto aceitarem W, então (de acordo com o teorema 8) nunca será possível formar um quórum que aceite um valor diferente, e portanto, para N também é seguro aceitar W.
O nó N com três cortes de quórum.
B-D-F é um conjunto bloqueador para N: inclui um nó de cada um dos cortes de N.
B-E também é um conjunto bloqueador para N, porque E aparece em dois cortes de N.
Mas um conjunto bloqueador não é um quórum. Seria muito fácil enganar o nó N para aceitar o valor desejado, se bastasse comprometer apenas um nó em cada um dos cortes de N. Portanto, aceitar um valor não é o fim da votação. Em vez disso, N deve confirmar o valor, ou seja, ver um quórum de nós que o aceitam. Se ele chegar tão longe, então, como o documento técnico SCP prova (no teorema 11), o restante da rede também acabará confirmando o mesmo valor, assim N encerrará a votação federativa com um valor específico como resultado.
Votação federativa.
O processo de votação, aceitação e confirmação consiste em uma rodada completa de votação federativa. O protocolo de consenso Stellar combina muitas dessas rodadas para criar um sistema de consenso completo.
Protocolo de Consenso Stellar
As duas propriedades mais importantes de um sistema de consenso são segurança e resiliência. Um algoritmo de consenso é considerado "seguro" se nunca pode fornecer resultados diferentes para participantes diferentes (a cópia da história de Bob nunca contradirá a de Carol). "Resiliência" significa que o algoritmo sempre produzirá um resultado, ou seja, não ficará preso.
O procedimento descrito de votação federativa é seguro no sentido de que se um nó confirma o valor V, nenhum outro nó confirmará um valor diferente. Mas "não confirmar um valor diferente" não significa que ele necessariamente confirmará algo. Os participantes podem votar em uma quantidade tão grande de valores diferentes que nenhum alcance o limiar de aceitação. Isso significa que na votação federativa não existe resiliência.
O protocolo de consenso Stellar utiliza a votação federativa de tal forma que garante tanto a segurança quanto a resiliência. (As garantias de segurança e resiliência do SCP têm um limite teórico. O desenho opta por uma garantia de segurança muito forte, sacrificando uma leve redução da resiliência, mas dado um tempo suficiente, o consenso será alcançado com alta probabilidade). Em suma, a ideia é realizar várias votações federativas sobre vários valores até que um deles passe completamente por todas as fases de votação do SCP, descritas abaixo.
Os valores pelos quais o SCP busca consenso podem ser o histórico de transações ou um pedido de almoço, ou qualquer outra coisa, mas é importante notar que esses não são os valores que são aceitos ou confirmados. Em vez disso, a votação federativa ocorre sobre declarações sobre esses valores.
As primeiras rodadas da votação federativa ocorrem na fase de nomeação (nomination phase), em um conjunto de declarações do tipo "Eu nomeio V", possivelmente para muitos valores diferentes de V. O objetivo da nomeação é encontrar uma ou mais declarações que possam passar pela aceitação e confirmação.
Após encontrar candidatos confirmados, o SCP avança para a etapa de votação, onde o objetivo é encontrar um boletim (ou seja, um contêiner para o valor proposto) e um quórum que pode declarar o commit para ele (commit). Se o quórum fizer o commit do boletim, seu valor é aceito como consenso. Mas antes que um nó possa votar para o commit do boletim, ele deve primeiro confirmar o cancelamento de todos os boletins com um valor menor de contador. Esses passos — o cancelamento de boletins para encontrar aquele para o qual pode ser confirmado o commit — envolvem várias rodadas de votação federativa sobre várias declarações de boletins.
As próximas seções detalham mais sobre a indicação e votação.
Indicação
No início da etapa de indicação, cada nó pode escolher espontaneamente um valor V e votar para a afirmação "Eu indico V". O objetivo nesta etapa é confirmar a indicação de algum valor por meio de votação federativa.
É possível que um número suficiente de nós vote por declarações suficientemente diferentes, e nenhuma indicação possa alcançar o limite de aceitação. Portanto, além de transmitir seus próprios votos de nomeação, os nós "refletem" as indicações de seus pares. Refletir (echo) significa que, se um nó votar por uma indicação V, mas vê uma mensagem de um vizinho votando por uma indicação W, agora votará tanto por V quanto por W. (Nem todos os votos dos pares são refletidos durante a indicação, pois isso pode levar a uma explosão de diferentes nomeados. O SCP inclui um mecanismo para regular esses votos. Em resumo, existe uma fórmula para determinar a "prioridade" de um par do ponto de vista do nó, e apenas os votos de nós de alta prioridade são refletidos. Quanto mais longa a indicação, mais baixo o limite, portanto, o nó amplia o conjunto de pares cujos votos refletirá. A fórmula de prioridade, como uma das variáveis de entrada, inclui o número do slot, portanto um nó de par de alta prioridade para um slot pode ser de baixa prioridade para outro, e vice-versa).
O conceito de apresentar tanto V quanto W paralelamente são vozes federativas distintas, cada uma capaz de alcançar aprovação ou confirmação separadamente. Na prática, as mensagens do protocolo SCP empacotam essas vozes separadas juntas.
Embora votar para apresentar V seja uma promessa de nunca votar contra a apresentação de V, no nível da aplicação — neste caso, SCP — é definido o que significa "contra". O SCP não reconhece uma afirmação que contradiga o voto "Eu apresento X", ou seja, não há mensagem "Eu sou contra a apresentação de X", portanto, o nó pode votar na apresentação de quaisquer valores. Muitas dessas nomeações não levarão a nada, mas, em última análise, o nó poderá aceitar ou confirmar um ou mais valores. Assim que o indicado for confirmado, ele se torna um candidato.
A apresentação SCP usando votação federativa. Pode haver muitos valores "B" apresentados por nós de igual nível e "refletidos" por um nó.
A apresentação de candidatos pode resultar em vários candidatos confirmáveis. Portanto, o SCP requer que o nível de aplicação forneça algum método para combinar candidatos em um único composto (composite). O método de combinação pode ser qualquer um. A principal questão é que se esse método for determinado, então cada nó combinará os mesmos candidatos. Em um sistema de votação para o almoço, “combinar” pode simplesmente significar descartar um dos dois candidatos. (Mas de forma determinada: cada nó deve escolher o mesmo valor para descartar. Por exemplo, uma escolha anterior em ordem alfabética). Na rede de pagamento Stellar, onde ocorrem votações sobre o histórico de transações, combinar dois candidatos propostos implica unir as transações que eles contêm, e os últimos de seus dois timestamps.
A descrição técnica do SCP prova (teorema 12) que ao final da fase de apresentação a rede, em última análise, converge para um único composto. Mas há um problema: a votação federativa é um protocolo assíncrono (assim como o SCP). Em outras palavras, os nós não são coordenados no tempo, mas apenas nas mensagens que enviam. Do ponto de vista de um nó, não está claro quando terminou fase de proposição. E embora todos os nós acabem chegando ao mesmo composto, eles podem escolher diferentes rotas nesse caminho, criando ao longo do percurso diferentes candidatos compostos, e nunca podem dizer qual deles é o final.
Mas isso é normal. A proposição é apenas uma preparação. O principal é limitar o número de candidatos para alcançar o consenso, que ocorre no processo de votação (balloting).
Votação
Um boletim é um par , onde counter é um número inteiro que começa em 1, e value é um candidato da fase de proposição. Isso pode ser um próprio candidato do nó ou um candidato de um nó vizinho, aceito por esse nó. Simplificando, ao votar, são feitas tentativas repetidas para fazer a rede alcançar um consenso sobre algum candidato em algum boletim, por meio da realização de múltivas votações federativas sobre declarações de boletins. Os contadores nos boletins rastreiam as tentativas feitas, e boletins com contadores mais altos têm prioridade sobre boletins com contadores mais baixos. Se o boletim travar, uma nova votação começa, agora sobre o boletim .
É importante diferenciar valores (por exemplo, o que deve ser o pedido do almoço: pizza ou saladas), boletins (par counter-value) e declarações sobre boletins. A rodada SCP inclui várias rodadas de votação federativa, em particular, sobre declarações como:
- "Estou pronto para o commit do boletim B" e
- "Eu declaro o commit do boletim B"
Do ponto de vista desse nó, o consenso é alcançado quando ele encontra o boletim B, para o qual pode confirmar (ou seja, encontrar quórum que aceite) a declaração "Eu declaro o commit do boletim B". A partir desse momento, é seguro agir com base no valor indicado em B — por exemplo, fazer esse pedido de almoço. Isso é chamado de externalização do valor. Uma vez confirmado o aceitação do boletim, o nó pode ter certeza de que qualquer outro nó terá externado esse mesmo valor ou certamente o fará no futuro.
Embora conceitualmente muitos votos federativos sejam realizados com base em declarações sobre muitos diferentes boletins, eles trocam não tantas mensagens, pois cada mensagem encapsula uma série de boletins. Assim, uma mensagem promove o estado de muitos votos federativos simultaneamente, por exemplo: "Aceito o commit dos boletins no intervalo de até ."
O que significam os termos "preparado" (prepared) e "commit" (commit)?
Um nó vota pelo commit do boletim quando está convencido de que outros nós não farão commit de boletins com outros valores. Convencer-se disso é o objetivo da preparação da declaração. Um voto que diz: "Estou pronto para o commit do boletim B" é uma promessa de nunca fazer commit de um boletim menor que B, ou seja, com um contador menor (o SCP requer que os valores nos boletins tenham uma ordem específica. Assim, o boletim é menor que , se N1<N2, e também se N1=N2 e V1<V2). Esses boletins menores são "abandonados" (aborted) durante a votação preparatória, enquanto B é considerado "preparado".
Por que "Estou pronto para o commit do boletim B" significa "Prometo nunca permitir commit de boletins menores que B"? Porque o SCP define abort como oposto de commit. O voto sobre a preparação do boletim implica também a votação para cancelar alguns outros boletins, e, como discutimos anteriormente, votar por algo é uma promessa de nunca votar contra isso.
Antes de transmitir o commit, o nó deve primeiro encontrar um boletim que possa confirmar como preparado. Em outras palavras, ele realiza uma votação federativa sobre a questão "Estou pronto para o commit do boletim B", possivelmente para muitos boletins diferentes, até encontrar aquele que aceita o quórum.
De onde vêm os boletins para a preparação da votação? Primeiro, o nó transmite a preparação para a votação por <1,C>, onde C é o candidato composto gerado na fase de nomeação. No entanto, mesmo após o início da preparação para a votação, a nomeação pode resultar em novos candidatos que se tornarão novos boletins. Enquanto isso, os pares podem ter diferentes candidatos e podem formar um conjunto bloqueador que aceita "Estou pronto para o commit do boletim B2", o que convencerá o nó a aceitá-lo também. Por fim, há um mecanismo de timeout que gera novas rodadas de votação federativa em novos boletins com contadores mais altos se os boletins atuais ficarem parados.
Assim que o nó encontra o boletim B, que pode confirmar como preparado, ele transmite uma nova mensagem "Commit do boletim B". Essa votação informa aos pares que o nó nunca desistirá de B. Na verdade, se B for um boletim <N,C>, então "Commit do boletim <N,C>" significa um consentimento incondicional para votar pela prontidão de cada boletim de <N,C> até <∞,s>. Esse valor adicional ajuda outros nós a alcançar o par com o commit, caso ainda estejam em etapas mais iniciais do protocolo.
Neste ponto, vale a pena ressaltar mais uma vez que esses são protocolos assíncronos. Apenas porque um nó envia votos para o commit, não significa que seus pares também o façam. Alguns ainda podem estar votando em declarações para a preparação da votação, enquanto outros talvez já tenham externalizado o valor. O SCP explica como um nó deve processar cada tipo de mensagem par-a-par independentemente de sua fase.
Se a mensagem "Eu declaro o commit " não pode ser aceita ou confirmada, há uma probabilidade de aceitação ou confirmação da mensagem ou — ou, de qualquer forma, de qualquer boletim com o valor C, e não qualquer outro, uma vez que o nó já prometeu nunca reverter . Quando o nó transmite os votos para o commit, isso será C ou nada, dependendo de quão longe o consenso irá. No entanto, isso ainda não é suficiente para o nó externalizar C. Alguns bytes bizantinos (compostos por menos do que o quórum, com base em nossas suposições sobre segurança) podem mentir para o nó. Aceitar e, em seguida, confirmar algum boletim (ou intervalo de boletins) é o que dá ao nó a certeza de finalmente externalizar C.
Votação SCP por meio de votação federativa. Não mostrado: a qualquer momento, um cronômetro pode ser ativado, aumentando o contador no boletim (e, possivelmente, gerando um novo composto a partir de candidatos adicionais propostos).
E é isso! Assim que a rede chega a um consenso, ela está pronta para fazer isso novamente e novamente. Na rede de pagamentos Stellar, isso acontece a cada 5 segundos: um feito que exige tanto segurança quanto resiliência, garantidas pelo SCP.
O SCP pode alcançar isso confiando em várias rodadas de votação federativa. A votação federativa é possibilitada pelo conceito de cortes de quórum: conjuntos de nós pares nos quais cada nó decidiu confiar como parte de seu quórum (subjetivo). Essa configuração significa que é possível chegar a um consenso mesmo em uma rede de adesão aberta e com fraudes bizantinas.
Leitura adicional
- O documento técnico original do SCP pode ser encontrado , e projeto de especificações para sua implementação.
- O autor original do protocolo SCP, David Mazieres, explica de forma simplificada (mas ainda técnica) como ele funciona .
- Você pode ter se surpreendido ao não encontrar nesta matéria os termos "mineração" ou "prova de trabalho". O SCP não utiliza esses métodos, mas alguns outros algoritmos de consenso o fazem. Zane Weiszspun escreveu uma acessível .
- de uma rede simples alcançando consenso em uma única rodada completa do SCP.
- Para leitores interessados nas implementações do SCP: veja , utilizado pela rede de pagamento Stellar, ou , que escrevi para uma melhor compreensão do SCP.
Fonte: habr.com
