O protocolo de consenso Stellar foi descrito pela primeira vez em David Mazier em 2015. Este é um “sistema de acordo federal bizantino” que permite que redes de computação descentralizadas e sem liderança cheguem de forma eficiente a um consenso sobre uma decisão. A rede de pagamento Stellar usa o Stellar Consensus Protocol (SCP) para manter um histórico de transações consistente que é visível para todos os participantes.
Os protocolos de consenso são considerados difíceis de compreender. O SCP é mais simples que a maioria deles, mas ainda compartilha dessa reputação - em parte devido à ideia equivocada de que a “votação federada”, que é o tema da primeira metade do artigo científico, é o SCP. Mas isso não é verdade! Este é apenas um importante alicerce que a segunda metade do artigo usa para criar real Protocolo de consenso estelar.
Neste artigo explicaremos brevemente o que é um “sistema de acordos”, o que pode torná-lo “bizantino” e por que tornar o sistema bizantino “federal”. Em seguida, explicaremos o procedimento de votação federada descrito no artigo do SCP e, por fim, explicaremos o próprio protocolo do SCP.
Sistemas de acordo
Um sistema de acordos permite que um grupo de participantes chegue a um consenso sobre um tema, como o que pedir para o almoço.
Na Interstellar, implementamos nosso próprio sistema de acordo de jantar: pedimos o que nosso gerente de operações, John, diz. Este é um sistema de acordo simples e eficaz. Todos nós confiamos em John e acreditamos que ele encontrará algo interessante e nutritivo todos os dias.
Mas e se John abusar da nossa confiança? Ele pode decidir sozinho que todos devemos nos tornar veganos. Dentro de uma ou duas semanas, provavelmente iremos derrubá-lo e entregar o poder a Elizabeth. Mas de repente ela adora abacate com anchovas e acha que todo mundo deveria ser assim. O poder corrompe. Portanto, é melhor encontrar algum método mais democrático: alguma maneira de garantir que as diferentes preferências sejam levadas em conta, garantindo ao mesmo tempo um resultado oportuno e inequívoco, para que ninguém acabe pedindo o almoço, ou cinco pessoas façam pedidos diferentes, ou a discussão se arrasta até a noite.
Parece que a solução é simples: vote! Mas esta é uma impressão enganosa. Quem recolherá as cédulas e reportará os resultados? E por que outros deveriam acreditar no que ele diz? Talvez possamos primeiro vote em um líder em quem confiamos para liderar a votação - mas que a liderará primeiro votando? E se não conseguirmos chegar a acordo sobre um líder? Ou e se chegarmos a um acordo, mas esse líder ficar preso numa reunião ou ficar de licença médica?
Problemas semelhantes ocorrem em redes de computadores distribuídas. Todos os participantes ou nós devem concordar com alguma decisão, como de quem é a vez de atualizar um arquivo compartilhado ou remover uma tarefa da fila de processamento. Em uma rede de criptomoedas, os nós precisam repetidamente escolher como será a história completa entre diversas versões possíveis, que às vezes entram em conflito. Este acordo 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. Isto também garante que ele poderá gastar as moedas no futuro, pois o novo destinatário terá as mesmas garantias pelos mesmos motivos.
Qualquer sistema de consenso em uma rede de computação distribuída deve ser tolerante a falhas: deve produzir resultados consistentes apesar de erros como links lentos, nós que não respondem e ordem incorreta de mensagens. bizantino O sistema de acordo é adicionalmente resistente a erros “bizantinos”: nós que fornecem informações falsas, seja por erro ou numa tentativa deliberada de minar o sistema ou obter alguma vantagem. A tolerância a falhas "bizantina" - a capacidade de confiar em uma decisão de grupo mesmo quando alguns membros do grupo podem mentir ou não seguir as regras de tomada de decisão - é chamada que tentou coordenar o ataque. em Anthony Stevens.
Considere a dona da criptomoeda Alice, que deve escolher entre comprar um delicioso sorvete de Bob ou 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 de que a moeda nunca foi paga a Carol e convencer o computador de Carol de que a moeda nunca foi paga a Bob. O sistema bizantino de acordos torna isso praticamente impossível, utilizando uma forma de regra da maioria chamada quorum. Um nó em tal rede recusa-se a passar para uma versão específica do histórico até que veja que um número suficiente de pares – um quorum – concorda com tal transição. Quando isso acontecer, eles formarão um bloco de votação grande o suficiente para forçar os nós restantes da rede a concordarem com sua decisão. Alice pode forçar alguns nós a mentirem em seu nome, mas se a rede for grande o suficiente, sua tentativa será esmagada pelos votos dos nós honestos.
Quantos nós são necessários para o quorum? No mínimo, uma maioria, ou melhor, uma maioria qualificada para combater os erros e a fraude. Mas para contar a maioria, é preciso saber o número total de participantes. No escritório interestelar ou nas eleições distritais, estes números são fáceis de descobrir. Mas se o seu grupo for uma rede vagamente definida na qual os nós podem entrar e sair à vontade sem a aprovação do centro, então você precisa Federal um sistema de acordo bizantino capaz de determinar quóruns não a partir de uma lista predeterminada de nós, mas dinamicamente, a partir de um instantâneo de nós em constante mudança e inevitavelmente incompleto em um determinado momento.
Pode parecer impossível criar um quorum da perspectiva de um único nó numa vasta rede, mas é possível. Tal quórum pode até garantir os resultados da votação descentralizada. O white paper do SCP mostra como fazer isso usando um procedimento chamado por voto federal.
Para os impacientes
O restante do artigo descreve a votação federada e o protocolo de consenso Stellar com mais detalhes. Se você não estiver interessado nos detalhes, aqui está uma visão geral do processo.
- Os nós conduzem rodadas de votação federal sobre os “indicados”. Uma rodada de votação federal significa:
- O nó vota em alguma afirmação, por exemplo, “Proponho o valor de V”;
- O nó escuta as vozes dos pares até encontrar uma que possa “receber”;
- O nó procura um “quórum” para esta afirmação. Um quórum “confirma” o indicado.
- Uma vez que um nó pode confirmar um ou mais indicados, ele tenta “preparar” a “cédula” através de várias rodadas de votação federada.
- Depois que um nó consegue verificar se a cédula está pronta, ele tenta confirmá-la por meio de ainda mais rodadas de votação federada.
- Uma vez que um nó pode confirmar o commit de uma votação, ele pode “externalizar” o valor dessa votação usando-o como um resultado de consenso.
Estas etapas envolvem múltiplas rodadas de votação federada, que coletivamente formam uma rodada de SCP. Vamos dar uma olhada mais de perto no que acontece em cada etapa.
Votação federada
A votação federada é 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 possíveis. Ela não pode fazer isso a menos que esteja confiante de que outros nós da rede não escolherão um resultado diferente. Para garantir isso, os nós trocam uma enxurrada de mensagens para que todos confirmadoQue quorum nós toma a mesma coisa decisão. O restante desta seção explica os termos desta frase e como ocorre todo o procedimento.
Quóruns e fatias de quórum
Vamos começar definindo um quórum. Como discutimos acima, numa rede descentralizada com adesão dinâmica, é impossível saber antecipadamente o número de nós e, portanto, quantos são necessários para a maioria. A votação federada resolve este problema introduzindo uma nova ideia corte de quórum (fatia de quorum): Um pequeno conjunto de pares nos quais um nó confia para comunicar informações de status de votação ao restante da rede. Cada nó define sua própria fatia de quorum (da qual se torna um membro de fato).
A formação do quórum começa com uma redução do quórum. Para cada nó, seus nós cortados são adicionados. Em seguida, os termos da fatia são adicionados esses nós e assim por diante. À medida que você continua, há cada vez mais nós que não podem ser adicionados porque já estão incluídos na fatia. Quando não há mais nós para adicionar, o processo para: formamos um quorum por “fechamento transitivo” da fatia de quorum do nó inicial.
Para encontrar o quorum de um determinado nó...
... adicione membros de sua fatia...
...então adicionamos membros de fatia desses nós.
Continuamos até que não haja mais nós para adicionar.
Não há mais nós para adicionar. Este é um quórum.
Na verdade, cada nó pode aparecer em mais de uma fatia. Para formar um quorum, selecione apenas uma das fatias e adicione membros; em seguida, selecione qualquer fatia para cada um dos membros e adicione membros ele cortar e assim por diante. Isso significa que cada nó é membro de muitos quóruns possíveis.
Selecione apenas uma fatia do quórum em cada etapa.
Um quórum possível. Ou uma alternativa...
...selecione outras fatias...
…(quando for possível)…
... cria outro quórum.
Como um nó sabe em quais fatias os outros nós estão? Da mesma forma que outras informações sobre outros nós: desde as transmissões que cada nó transmite para a rede quando seu estado de votação muda. Cada transmissão inclui informações sobre as fatias do nó remetente. O white paper SCP não especifica um mecanismo de comunicação. Implementações normalmente usam para transmissão garantida de mensagens em toda a rede.
Lembre-se de que no sistema de acordos bizantino não federal, um quórum é definido como a maioria de todos os nós. O sistema de acordo bizantino é concebido do ponto de vista da questão: quantos nós desonestos o sistema pode tolerar? Em um sistema de N nós projetados para sobreviver a f falhas, um nó deve ser capaz de progredir recebendo feedback de N-f pares, uma vez que f deles podem estar inativos. Mas tendo recebido uma resposta de N-f pares, podemos assumir que todos os f pares (dos quais o nó não recebeu uma resposta) são na verdade honestos. Assim, f dos N-f pares (dos quais a resposta foi 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. Então, normalmente, um sistema projetado para sobreviver a f falhas terá um total de N=3f+1 nós e um tamanho de quorum de 2f+1. Quando uma proposta ultrapassa o limite de quórum, o resto da rede está convencido de que quaisquer propostas concorrentes serão rejeitadas. É assim que a rede converge para o resultado.
Mas num sistema de acordo bizantino federal, não só não pode haver maioria (porque ninguém conhece o tamanho total da rede), mas o conceito de maioria é completamente inútil! Se a adesão ao sistema estiver aberta, então alguém pode obter a maioria simplesmente realizando o chamado ataque Sybil: juntando-se repetidamente à rede através de vários nós. Então, por que o fechamento transitivo de fatia pode ser chamado quorum, e como é capaz de suprimir propostas concorrentes?
Tecnicamente, de jeito nenhum! Imagine uma rede de seis nós, onde dois trigêmeos são isolados nas fatias de quorum um do outro. O primeiro subgrupo pode tomar uma decisão da qual o segundo nunca ouvirá falar e vice-versa. Não há como esta rede chegar a um consenso (a não ser por acaso).
Portanto, o SCP exige que para a votação federada (e para que os importantes teoremas do artigo sejam aplicados), a rede deve ter uma propriedade chamada interseção de quóruns. Numa rede com esta propriedade, quaisquer dois quóruns que possam ser construídos sempre se sobrepõem em pelo menos um nó. Para determinar o sentimento predominante da rede, isto é tão bom quanto ter uma maioria. Intuitivamente, isso significa que se qualquer quórum concordar com a afirmação X, nenhum outro quórum poderá concordar com qualquer outra coisa, porque incluirá necessariamente algum nó do primeiro quórum que já votou em X.
Se houver uma interseção de quóruns na rede...
...então quaisquer dois quóruns que você possa construir...
... sempre se cruzará.
(É claro que nós sobrepostos podem acabar sendo bizantinos ou ruins. Nesse caso, a interseção de quorum não ajuda em nada a rede a concordar. Por esse motivo, muitos dos resultados no white paper SCP são baseados em suposições explícitas, como o que resta no cruzamento do quorum da rede mesmo depois de remover nós ruins. Para simplificar, vamos deixar essas suposições implícito no resto do artigo).
Pode parecer irracional esperar que um cruzamento de quorum confiável seja possível em uma rede de nós independentes. Mas há duas razões pelas quais isso acontece.
A primeira razão é a própria existência da Internet. A Internet é um exemplo perfeito de rede de nós independentes com quóruns que se cruzam. A maioria dos nós na Internet conecta-se apenas a alguns outros nós locais, mas esses pequenos conjuntos se sobrepõem o suficiente para que cada nó possa ser alcançado a partir de todos os outros nós ao longo de alguma rota.
A segunda razão é específica da rede de pagamento Stellar (o uso mais comum do SCP). Cada ativo na rede Stellar tem um emissor, e as diretrizes da Stellar exigem que cada emissor designe um ou mais nós na rede para processar solicitações de resgate. É de seu interesse incluir direta ou indiretamente esses nós em fatias de quorum para cada ativo no qual você está interessado. Os quóruns para todos os nós interessados em um determinado ativo se sobreporão pelo menos nesses nós de resgate. Os nós interessados em múltiplos ativos incluirão todos os nós de resgate dos respectivos emissores em suas fatias de quórum e procurarão agrupar todos os ativos. Além disso, quaisquer ativos que não estejam vinculados desta forma a outros na rede, e não deveria estar conectado - isto foi concebido para que não haja sobreposição de quórum para esta rede (por exemplo, os bancos da zona do dólar por vezes querem negociar com bancos da zona euro e bancos da zona do peso, por isso estão na mesma rede, mas nenhum deles se preocupam com a rede separada de crianças que vendem cartões de beisebol).
Naturalmente, ожидание a passagem do quórum não é garantia. Outros sistemas de acordos bizantinos devem grande parte da sua complexidade à 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 traz para o nível da aplicação. Assim, embora a votação federada seja suficientemente geral para votar sobre qualquer questão, a sua fiabilidade depende, na verdade, criticamente do significado mais amplo desses significados. Alguns usos hipotéticos podem não ser tão propícios à criação de redes bem conectadas como outros.
Votação, aceitação e confirmação
Em uma rodada de votação federada, um nó opcionalmente começa a votar em algum valor V. Isso significa transmitir uma mensagem para a rede: “Eu sou o nó N, minhas fatias de quórum são Q e estou votando em V”. Quando um nó vota desta forma, ele promete que nunca votou contra V e nunca votará.
Nas transmissões peer-to-peer, cada nó vê como os outros votam. Depois que um nó tiver coletado um número suficiente dessas mensagens, ele poderá rastrear fatias de quorum e tentar encontrar quóruns. Se ele vir um quórum de pares que também votam em V, ele poderá prosseguir para adoção V e transmita esta nova mensagem para a rede: “Eu sou o nó N, minhas fatias de quorum são Q e aceito V.” A aceitação oferece uma garantia mais forte do que a simples votação. Quando um nó vota em V, ele nunca poderá votar em outras opções. Mas se um nó aceitar V, nenhum nó na Rede aceitará a outra opção (o Teorema 8 no white paper SCP prova isso).
É claro que há uma grande probabilidade de que não haja imediatamente um quorum de nós que concordem com V. Outros nós podem votar em outros valores. Mas há outra maneira de um nó passar da simples votação para a aceitação. N pode aceitar um valor diferente para W, mesmo que não tenha votado a favor e mesmo que não veja quórum para isso. Para decidir mudar seu voto, basta ver conjunto de bloqueio nós que aceitaram W. Um conjunto de bloqueio é um nó de cada uma das fatias de quorum N. Como o nome sugere, ele pode quadra qualquer outro significado. Se todos os nós de tal conjunto aceitarem W, então (pelo Teorema 8) nunca será possível formar um quorum que assuma um valor diferente e, portanto, também é seguro para N aceitar W.
Nó N com três fatias de quorum.
BDF é um conjunto de bloqueio para N: inclui um nó de cada uma das fatias de N.
BE também é um conjunto bloqueador para N porque E aparece em duas fatias de N.
Mas o conjunto de bloqueios não é um quórum. Seria muito fácil enganar o nó N para que aceitasse o valor desejado se bastasse hackear apenas um nó em cada uma das fatias de N. Portanto, aceitar o valor não é o fim da votação. Em vez disso, N deve confirmar o valor, ou seja, ver um quorum de nós aceitando-o. Se chegar a esse ponto, então, como prova o white paper do SCP (no Teorema 11), o resto da rede também acabará por confirmar o mesmo valor, então N encerrará o voto federado com um determinado valor como resultado.
Votação federada.
O processo de votação, aceitação e confirmação constitui uma rodada completa de votação federada. O protocolo de consenso Stellar combina muitas dessas rodadas para criar um sistema de consenso completo.
Protocolo de Consenso Estelar
As duas propriedades mais importantes de um sistema de consenso são - Segurança и capacidade de sobrevivência. Um algoritmo de consenso é "seguro" se nunca puder fornecer resultados diferentes para participantes diferentes (a cópia da história de Bob nunca contradiz Carol). “Habitabilidade” significa que o algoritmo sempre produzirá um resultado, ou seja, não ficará preso.
Procedimento de votação federal descrito seguro no sentido de que se um nó confirmar o valor de V, nenhum outro nó confirmará o outro valor. Mas “não confirmará outro significado” não significa que confirmará necessariamente algo. Os participantes podem votar em tantos valores diferentes que nada atingirá o limite de aceitação. Isso significa que na votação federal não há capacidade de sobrevivência.
O protocolo de consenso Stellar usa votação federada de uma forma que garante segurança e capacidade de sobrevivência. (As garantias de segurança e capacidade de sobrevivência do SCP têm um limite teórico. O projeto escolhe uma garantia de segurança muito forte, sacrificando uma pequena mitigação da capacidade de sobrevivência, mas com tempo suficiente, é altamente provável que o consenso seja alcançado.) Em suma, a ideia é ter vários votos federados em vários valores até que um deles passe por todas as fases de votação do SCP descritas abaixo.
Os valores sobre os 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 ressaltar que esses não são os valores aceitos ou confirmados. Em vez disso, a votação federal ocorre de acordo com declarações sobre esses valores.
O primeiro turno da votação federal ocorre em fase de nomeação (fase de nomeação), em um conjunto de afirmações como “Eu nomeio V”, talvez para muitos valores diferentes de V. O objetivo da nomeação é encontrar uma ou mais afirmações que passem por aceitação e confirmação.
Depois de encontrar candidatos verificáveis, o SCP passa para a fase de votação, onde o objetivo é encontrar um determinado бюллетень (ou seja, um contêiner para o valor proposto) e um quorum que pode declarar comprometer-se para isso (comprometer). Se um quórum realizar uma votação, seu valor será aceito como consenso. Mas antes que um nó possa votar em um commit de votação, ele deve primeiro confirmar cancelamento todas as cédulas com valor de contador menor. Essas etapas – cancelar cédulas para encontrar uma que possa ser comprometida – envolvem múltiplas rodadas de votação federada em múltiplas reivindicações de cédula.
As seções a seguir descrevem a nomeação e a votação com mais detalhes.
Nomeação
No início da fase de nomeação, cada nó pode escolher espontaneamente um valor para V e votar na afirmação “Eu nomeio V”. O objetivo nesta fase é confirmar a indicação de algum valor através de votação federada.
Talvez um número suficiente de nós vote em proposições suficientemente diferentes para que nenhuma nomeação possa atingir o limite de aceitação. Portanto, além de transmitirem seus próprios votos de nomeação, os nós “refletem” as nomeações de seus pares. Eco significa que se um nó votar na nomeação V, mas vir uma mensagem de um vizinho votando na nomeação W, ele agora votará em V e W. (Nem todos os votos dos pares são ecoados durante a nomeação porque isso pode levar a uma explosão de diferentes indicados. O SCP inclui um mecanismo para regular esses votos. Em suma, existe uma fórmula para determinar a "prioridade" de um par do ponto de vista de um nó, e apenas os votos dos nós de alta prioridade são refletidos. Quanto mais longa a nomeação leva,quanto mais baixo for o limite,de modo que o nó expande o conjunto de pares cujos votos irá reflectir.A fórmula de prioridade inclui o número do slot como uma das suas entradas,de modo que um par de alta prioridade para um slot pode ser um par de baixa prioridade para outro e vice-versa).
Conceitualmente, a nomeação é paralela, tanto V quanto W são votos federais separados, cada um individualmente capaz de obter aceitação ou confirmação. Na prática, as mensagens do protocolo SCP agrupam esses votos individuais.
Embora votar a favor da nomeação de V seja uma promessa de nunca votar contra a nomeação de V, é no nível da aplicação - neste caso SCP - que é determinado o que significa “contra”. SCP não vê afirmação que contradiga o voto “Eu indico X”, ou seja, não há mensagem “Sou contra a indicação X”, então o nodo pode votar para indicar quaisquer valores. Muitas dessas nomeações não levarão a lugar nenhum, mas eventualmente o nó será capaz de aceitar ou confirmar um ou mais valores. Uma vez confirmado o candidato, ele se torna candidato.
Nomeação de SCP usando votação federada. Pode haver muitos valores “B” apresentados pelos pares e “refletidos” pelo nó.
As nomeações podem resultar em vários candidatos confirmados. Portanto, o SCP exige que a camada de aplicação forneça algum método de combinar os candidatos em um só. composto (composto). O método de união pode ser qualquer coisa. O principal é que se este método for determinístico, cada nó combinará os mesmos candidatos. Num sistema de votação no almoço, “unificação” pode significar simplesmente a rejeição de um de dois candidatos. (Mas de forma determinística: cada nó deve selecionar o mesmo valor para redefinir. Por exemplo, a seleção anterior em ordem alfabética). Na rede de pagamentos Stellar, onde o histórico de transações é votado, a fusão de dois indicados propostos envolve a fusão das transações que eles contêm e o mais recente de seus dois carimbos de data/hora.
O whitepaper SCP prova (Teorema 12) que ao final da fase de extensão, a rede eventualmente converge para um único composto. Mas há um problema: a votação federada é um protocolo assíncrono (como o SCP). Em outras palavras, os nós não são coordenados pelo tempo, mas apenas pelas mensagens que enviam. Do ponto de vista do nó, não está claro quando terminou fase de extensão. E embora todos os nós acabem por chegar ao mesmo composto, eles podem seguir rotas diferentes ao longo do caminho, criando diferentes candidatos compostos ao longo do caminho, e nunca poderão dizer qual deles é o final.
Mas é normal. A nomeação é apenas uma preparação. O principal é limitar o número de candidatos para chegar ao consenso, o que ocorre no processo corrida (votação).
Correndo
Boletim é um casal , onde contador é um número inteiro que começa em 1 e valor é um candidato da fase de nomeação. Este pode ser o candidato do próprio nó ou o candidato de um nó vizinho aceito por esse nó. Grosso modo, uma votação envolve repetidas tentativas de forçar a rede a chegar a um consenso sobre algum candidato em alguma votação, mantendo potencialmente muitos votos federados nas declarações eleitorais. Os contadores nas cédulas registram as tentativas feitas, e as cédulas com contagens mais altas têm precedência sobre as cédulas com contagens mais baixas. Se o boletim informativo fica preso, uma nova votação começa, agora na cédula .
É importante distinguir significados (por exemplo, qual deve ser o pedido do almoço: pizza ou saladas), boletins informativos (par contra-valor) e declarações sobre votos. A rodada do SCP inclui várias rodadas de votação federal, em particular nas seguintes declarações:
- "Estou pronto para cometer o voto B" e
- "Eu anuncio o commit da votação B"
Da perspectiva de um determinado nó, o consenso é alcançado quando ele encontra uma cédula B para a qual pode confirmar (ou seja, encontrar um quorum que aceite) a declaração “Eu comprometo a cédula B”. A partir deste ponto, é seguro atuar no valor especificado em B – por exemplo, fazer esse pedido de almoço. É chamado externalização significados. Uma vez confirmada a aceitação da votação, um nó pode ter certeza de que qualquer outro nó externalizou o mesmo valor ou o fará no futuro.
Embora muitas votações federadas sejam conceitualmente conduzidas em reivindicações para muitas cédulas diferentes, elas não trocam tantas mensagens porque cada mensagem encapsula um número de cédulas. Uma mensagem promove assim o estado de muitos votos federados de uma só vez, por exemplo: “Aceito submeter votos que vão desde antes "
O que significam os termos “preparado” e “comprometido”?
Um nó vota para confirmar uma cédula quando está confiante de que outros nós não cometerão cédulas com valores diferentes. Convencer isso é o objetivo da preparação da aplicação. Uma votação que diz “Estou pronto para submeter a cédula B” é uma promessa de nunca submeter uma cédula menor que B, ou seja, com uma contagem menor (o SCP exige que os valores nas cédulas estejam em uma determinada ordem. Assim, o boletim informativo menos , se N1
Por que “Estou pronto para submeter a cédula B” significa “Prometo nunca submeter cédulas menores que B”? Porque o SCP define abortar como o oposto de confirmar. Uma votação para preparar uma votação também envolve uma votação para desqualificar algumas outras cédulas e, como discutimos anteriormente, votar a favor de uma coisa é uma promessa de nunca votar contra ela.
Antes de transmitir um commit, um nó deve primeiro encontrar um boletim que possa confirmar como preparado. Em outras palavras, realiza uma votação federada sobre o tema “Estou pronto para submeter a votação B”, possivelmente em muitas votações diferentes, até encontrar uma que aceite quórum.
De onde vêm as cédulas para preparar a votação? Primeiro, o nó transmite os preparativos para votar em <1,C>, onde C é o candidato composto produzido na fase de nomeação. No entanto, mesmo após o início dos preparativos para a votação, as nomeações podem resultar no aparecimento de candidatos adicionais para se tornarem novas cédulas. Enquanto isso, os pares podem ter candidatos diferentes e podem formar um conjunto de bloqueio que aceita “Estou pronto para confirmar a votação B2”, o que convencerá o nó a aceitá-la também. Finalmente, existe um mecanismo de tempo limite que gera novas rodadas de votação federada em novas cédulas com contagens mais altas se as cédulas atuais ficarem presas.
Assim que o nó encontra uma cédula B que pode confirmar como preparada, ele transmite uma nova mensagem “Confirmar cédula B”. Esta votação diz aos pares que o nó nunca desistirá de B. Na verdade, se B for uma cédula e, em seguida, “Confirmar votação "significa o consentimento incondicional para votar pela prontidão de cada cédula de para <∞, s>. Este valor extra ajuda outros peers a alcançar o peer commit se ainda estiverem em estágios anteriores do protocolo.
Nesta fase, vale ressaltar mais uma vez que se trata de protocolos assíncronos. Só porque um nó envia votos positivos para um commit não significa que seus pares também o façam. Alguns deles podem ainda estar a votar declarações em preparação para a votação, outros podem já ter externalizado o significado. SCP explica como um nó deve processar cada tipo de mensagem peer independentemente de sua fase.
Se a mensagem "Eu anunciei um commit » não pode ser recebida ou confirmada, ou seja, a probabilidade da mensagem ser aceita ou confirmada ou - ou, em qualquer caso, qualquer cédula com valor C, e não qualquer outra, pois o nó já prometeu nunca cancelar . No momento em que um nó transmite votos para um commit, será C ou nada, dependendo de até onde vai o consenso. No entanto, isto ainda não é suficiente para o nó externalizar C. Alguns pares bizantinos (que constituem menos que um quorum, com base nas nossas suposições de segurança) podem mentir para o nó. Aceitar e depois confirmar alguma cédula (ou série de cédulas) é o que dá ao nó a confiança para finalmente externalizar C.
Votação SCP através de votação federada. Não mostrado: O cronômetro pode disparar a qualquer momento, aumentando a contagem na cédula (e possivelmente produzindo uma nova composição de candidatos indicados adicionais).
E é tudo! Uma vez que a rede tenha alcançado um consenso, ela estará pronta para fazê-lo repetidas vezes. Na rede de pagamento Stellar, isso acontece aproximadamente uma vez a cada 5 segundos: um feito que exige segurança e capacidade de sobrevivência garantidas pelo SCP.
O SCP pode conseguir isso contando com múltiplas rodadas de votação federada. A votação federada é possível graças ao conceito de fatias de quorum: conjuntos de pares nos quais cada nó decidiu confiar como parte de seu quorum (subjetivo). Esta configuração significa que o consenso pode ser alcançado mesmo numa rede com adesão aberta e enganos bizantinos.
Leitura adicional
- O white paper original do SCP pode ser encontrado E elaborar especificações para a sua implementação.
- O autor original do protocolo SCP, David Mazier, explica-o de forma simplificada (mas ainda técnica). .
- Você pode ter ficado surpreso 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 usam. Zane Witherspoon escreveu acessível .
- uma rede simples que chega a consenso em uma rodada completa de SCP.
- Para leitores interessados em implementações de SCP: veja , usado pela rede de pagamento Stellar, ou , que escrevi para uma melhor compreensão do SCP.
Fonte: habr.com