Resumo

Um livro-razão público é uma sequência de dados inviolável que pode ser lida e aumentada por qualquer pessoa. Os livros-razão públicos têm usos inúmeros e atraentes. Eles podem proteger, à vista de todos, todos os tipos de transações —como títulos, vendas e pagamentos— na ordem exata em que ocorrem. Os livros-razão públicos não apenas reduzem a corrupção, mas também permitem aplicações muito sofisticadas — como criptomoedas e smart contracts. Eles irão revolucionar a forma como uma sociedade democrática opera. No entanto, tal como estão actualmente implementados, eles têm uma fraca escalabilidade e não conseguem atingir o seu potencial. Algorand é uma forma verdadeiramente democrática e eficiente de implementar um livro-razão público. Ao contrário do anterior implementações baseadas em prova de trabalho, requer uma quantidade insignificante de computação e gera um histórico de transações que não será “fork” com probabilidade extremamente alta. Algorand é baseado em um acordo bizantino de transmissão de mensagens (novo e super rápido). Para ser mais concreto, descreveremos Algorand apenas como uma plataforma monetária.

Introdução

O dinheiro está se tornando cada vez mais virtual. Estima-se que cerca de 80% dos Estados Unidos dólares hoje existem apenas como entradas contábeis [5]. Outros instrumentos financeiros estão a seguir o exemplo. Num mundo ideal, em que pudéssemos contar com uma entidade central de confiança universal, imunes a todos os ataques cibernéticos possíveis, o dinheiro e outras transações financeiras poderiam ser exclusivamente eletrónicas. Infelizmente, não vivemos num mundo assim. Conseqüentemente, criptomoedas descentralizadas, como como Bitcoin [29], e sistemas “smart contract”, como Ethereum, foram propostos [4]. Em o coração desses sistemas é um livro-razão compartilhado que registra de forma confiável uma sequência de transações, ∗Esta é a versão mais formal (e assíncrona) do artigo ArXiv do segundo autor [24], um artigo em si baseado no de Gorbunov e Micali [18]. As tecnologias de Algorand são objeto do seguinte pedidos de patente: US62/117.138 US62/120.916 US62/142.318 US62/218.817 US62/314.601 PCT/US2016/018300 US62/326.865 62/331.654 US62/333.340 US62/343.369 US62/344.667 US62/346.775 US62/351.011 US62/653.482 US62/352.195 US62/363.970 US62/369.447 US62/378.753 US62/383.299 US62/394.091 US62/400.361 US62/403.403 US62/410.721 US62/416.959 US62/422.883 US62/455.444 US62/458.746 US62/459.652 US62/460.928 US62/465.931tão variados quanto pagamentos e contratos, de forma inviolável. A tecnologia escolhida para garantir tal inviolabilidade é o blockchain. Blockchains estão por trás de aplicativos como criptomoedas [29], aplicações financeiras [4] e Internet das Coisas [3]. Várias técnicas para gerenciar livros contábeis baseados em blockchain foram propostos: prova de trabalho [29], prova de aposta [2], tolerância prática a falhas bizantinas [8], ou alguma combinação. Atualmente, no entanto, os livros contábeis podem ser ineficientes de gerenciar. Por exemplo, Bitcoin de proof-of-work abordagem (baseada no conceito original de [14]) requer uma grande quantidade de computação, é um desperdício e escala mal [1]. Além disso, concentra de facto o poder em muito poucas mãos. Desejamos, portanto, propor um novo método para implementar um livro público que ofereça a conveniência e eficiência de um sistema centralizado administrado por uma autoridade confiável e inviolável, sem as ineficiências e fraquezas das atuais implementações descentralizadas. Chamamos nossa abordagem Algorand, porque usamos aleatoriedade algorítmica para selecionar, com base no livro-razão construído até agora, um conjunto de verificadores encarregados de construir o próximo bloco de transações válidas. Naturalmente, garantimos que tais seleções sejam comprovadamente imunes a manipulações e imprevisíveis até no último minuto, mas também que, em última análise, sejam universalmente claros. A abordagem de Algorand é bastante democrática, no sentido de que nem em princípio nem de facto cria diferentes classes de usuários (como “mineradores” e “usuários comuns” em Bitcoin). Em Algorand “todos o poder reside no conjunto de todos os usuários”. Uma propriedade notável de Algorand é que seu histórico de transações pode bifurcar-se apenas com valores muito pequenos probabilidade (por exemplo, um em um trilhão, isto é, ou mesmo 10-18). Algorand também pode abordar algumas questões legais e preocupações políticas. A abordagem Algorand aplica-se a blockchains e, mais geralmente, a qualquer método de geração uma sequência de blocos inviolável. Na verdade, propusemos um novo método - alternativo e mais eficiente do que blockchains— que pode ser de interesse independente. 1.1 Suposição e problemas técnicos de Bitcoin Bitcoin é um sistema muito engenhoso e inspirou muitas pesquisas subsequentes. Ainda assim, também é problemático. Vamos resumir a sua suposição subjacente e os problemas técnicos - que na verdade, são compartilhados por essencialmente todas as criptomoedas que, como Bitcoin, são baseadas em proof-of-work. Para este resumo, basta lembrar que, em Bitcoin, um usuário pode possuir múltiplas chaves públicas de um esquema de assinatura digital, que o dinheiro está associado a chaves públicas e que um pagamento é um assinatura digital que transfere alguma quantia de dinheiro de uma chave pública para outra. Essencialmente, Bitcoin organiza todos os pagamentos processados em uma cadeia de blocos, B1, B2, . . ., cada um consistindo de múltiplos pagamentos, de modo que todos os pagamentos de B1, efetuados em qualquer ordem, seguidos pelos de B2, em qualquer ordem, etc., constituem uma sequência de pagamentos válidos. Cada bloco é gerado, em média, a cada 10 minutos. Esta sequência de blocos é uma cadeia, pois está estruturada de forma a garantir que qualquer alteração, mesmo em um único bloco, se infiltra em todos os blocos subsequentes, facilitando a detecção de qualquer alteração de o histórico de pagamentos. (Como veremos, isto é conseguido incluindo em cada bloco um código criptográfico hash do anterior.) Essa estrutura de bloco é referida como blockchain. Suposição: Maioria Honesta do Poder Computacional Bitcoin assume que nenhum mal-intencionado entidade (nem uma coalizão de entidades maliciosas coordenadas) controla a maioria dos recursos computacionais poder dedicado à geração de blocos. Tal entidade, de fato, seria capaz de modificar o blockchain,e assim reescrever o histórico de pagamentos, como desejar. Em particular, poderia fazer um pagamento \(\wp\), obter os benefícios pagos e então “apagar” qualquer vestígio de \(\wp\). Problema Técnico 1: Resíduos Computacionais Abordagem de Bitcoin proof-of-work para bloquear a geração requer uma quantidade extraordinária de computação. Atualmente, com apenas algumas centenas milhares de chaves públicas no sistema, os 500 supercomputadores mais poderosos só conseguem reunir apenas 12,8% do poder computacional total exigido dos jogadores Bitcoin. Isto a quantidade de computação aumentaria muito, caso um número significativamente maior de usuários ingressasse no sistema. Problema Técnico 2: Concentração de Poder Hoje, devido à quantidade exorbitante de cálculo necessário, um usuário, tentando gerar um novo bloco usando um desktop comum (sem falar em um celular), espera perder dinheiro. Na verdade, para calcular um novo bloco com um computador comum, o custo esperado da eletricidade necessária para alimentar o cálculo excede a recompensa esperada. Somente usando pools de computadores especialmente construídos (que não fazem nada além de “minerar novos blocos”), pode-se pode esperar obter lucro gerando novos blocos. Assim, hoje existem, de facto, dois classes distintas de usuários: usuários comuns, que apenas fazem pagamentos, e pools de mineração especializados, que apenas procuram novos blocos. Portanto, não deveria ser surpresa que, recentemente, o poder computacional total para blocos geração está dentro de apenas cinco grupos. Nessas condições, a suposição de que a maioria dos o poder computacional é honesto torna-se menos credível. Problema Técnico 3: Ambiguidade Em Bitcoin, blockchain não é necessariamente único. Na verdade sua última parte frequentemente se bifurca: o blockchain pode ser —digamos— B1, . . . , Bk, B' k+1, B′ k+2, de acordo com um usuário e B1, . . . , Bk, B'' k+1, B'' k+2, B'' k+3 de acordo com outro usuário. Somente depois de vários blocos terem sido adicionado à cadeia, podemos ter certeza razoável de que os primeiros k + 3 blocos serão os mesmos para todos os usuários. Assim, não se pode confiar desde já nos pagamentos contidos no último bloco de a corrente. É mais prudente esperar e ver se o bloco se torna suficientemente profundo no blockchain e, portanto, suficientemente estável. Separadamente, também foram levantadas preocupações de aplicação da lei e de política monetária sobre Bitcoin.1 1.2 Algorand, em poucas palavras Configuração Algorand funciona em ambientes muito difíceis. Resumidamente, (a) Ambientes sem permissão e com permissão. Algorand funciona de forma eficiente e segura, mesmo em um ambiente totalmente sem permissão, onde muitos usuários podem ingressar arbitrariamente no sistema a qualquer momento, sem qualquer verificação ou permissão de qualquer tipo. Claro, Algorand funciona ainda melhor em um ambiente permitido. 1O (pseudo) anonimato oferecido pelos pagamentos Bitcoin pode ser utilizado indevidamente para lavagem de dinheiro e/ou financiamento de indivíduos criminosos ou organizações terroristas. Notas tradicionais ou barras de ouro, que em princípio oferecem perfeita anonimato, deveriam representar o mesmo desafio, mas a fisicalidade destas moedas desacelera substancialmente o fluxo de dinheiro transferências, de modo a permitir algum grau de monitorização por parte das agências de aplicação da lei. A capacidade de “imprimir dinheiro” é um dos poderes básicos de um Estado-nação. Em princípio, portanto, a enorme a adopção de uma moeda flutuante independente pode restringir este poder. Atualmente, porém, Bitcoin está longe de ser uma ameaça às políticas monetárias governamentais e, devido aos seus problemas de escalabilidade, poderá nunca o ser.(b) Ambientes muito adversários. Algorand resiste a um Adversário muito poderoso, que pode (1) corromper instantaneamente qualquer usuário que desejar, a qualquer momento que desejar, desde que, de forma ambiente sem permissão, 2/3 do dinheiro do sistema pertence ao usuário honesto. (Em um ambiente permitido, independentemente do dinheiro, basta que 2/3 dos usuários sejam honestos.) (2) controlar totalmente e coordenar perfeitamente todos os usuários corrompidos; e (3) programar a entrega de todas as mensagens, desde que cada mensagem seja enviada por um usuário honesto atinge 95% dos usuários honestos dentro de um tempo \(\lambda\)m, que depende apenas do tamanho de m. Propriedades Principais Apesar da presença do nosso poderoso adversário, em Algorand • A quantidade de cálculo necessária é mínima. Essencialmente, não importa quantos usuários estejam presente no sistema, cada um dos mil e quinhentos usuários deve realizar no máximo alguns segundos de computação. • Um novo bloco é gerado em menos de 10 minutos e, de fato, nunca sairá do blockchain. Por exemplo, na expectativa, o tempo para gerar um bloco na primeira modalidade é menor do que Λ + 12,4\(\lambda\), onde Λ é o tempo necessário para propagar um bloco, em uma fofoca ponto a ponto moda, não importa o tamanho do bloco escolhido, e \(\lambda\) é o tempo para propagar 1.500 mensagens de 200Blong. (Uma vez que num sistema verdadeiramente descentralizado, Λ é essencialmente uma latência intrínseca, em Algorand o fator limitante na geração de blocos é a velocidade da rede.) A segunda modalidade tem na verdade foi testado experimentalmente ( por ?), indicando que um bloco é gerado em menos de 40 segundos. Além disso, blockchain de Algorand pode bifurcar apenas com probabilidade insignificante (ou seja, menos de um em um trilhão), e assim os usuários podem contar com os pagamentos contidos em um novo bloco assim que o bloco aparece. • Todo o poder reside nos próprios usuários. Algorand é um sistema verdadeiramente distribuído. Em particular, não existem entidades exógenas (como os “mineradores” em Bitcoin), que podem controlar quais transações são reconhecidos. Técnicas de Algorand. 1. Um novo e rápido protocolo de acordo bizantino. Algorand gera um novo bloco via um novo protocolo de acordo bizantino (BA) binário, criptográfico e de passagem de mensagens, BA⋆. Protocolo BA⋆não apenas satisfaz algumas propriedades adicionais (que discutiremos em breve), mas também é muito rápido. Grosso modo, sua versão de entrada binária consiste em um loop de 3 etapas, no qual um jogador i envia um único mensagem mi para todos os outros jogadores. Executado em rede completa e síncrona, com mais mais de 2/3 dos jogadores sendo honestos, com probabilidade > 1/3, após cada loop o protocolo termina em acordo. (Enfatizamos que o protocolo BA⋆ satisfaz a definição original do acordo bizantino de Pease, Shostak e Lamport [31], sem quaisquer enfraquecimentos.) Algorand aproveita este protocolo BA binário para chegar a um acordo, em nossas diferentes comunicações modelo, em cada novo bloco. O bloco acordado é então certificado, através de um número prescrito de assinatura digital dos verificadores apropriados e propagada pela rede. 2. Classificação criptográfica. Embora muito rápido, o protocolo BA⋆ se beneficiaria com mais velocidade quando jogado por milhões de usuários. Assim, Algorand escolhe os jogadores da BA⋆para seremum subconjunto muito menor do conjunto de todos os usuários. Para evitar um tipo diferente de concentração de poder problema, cada novo bloco Br será construído e acordado, através de uma nova execução de BA⋆, por um conjunto separado de verificadores selecionados, SV r. Em princípio, selecionar tal conjunto pode ser tão difícil quanto selecionando Br diretamente. Atravessamos este problema potencial através de uma abordagem que denominamos, abrangendo a sugestão perspicaz de Maurice Herlihy, classificação criptográfica. Sortição é a prática de selecionar funcionários aleatoriamente de um grande conjunto de indivíduos elegíveis [6]. (A classificação foi praticada ao longo dos séculos: por exemplo, pelas repúblicas de Atenas, Florença e Veneza. No sistema judicial moderno sistemas, a seleção aleatória é frequentemente usada para escolher os júris. A amostragem aleatória também foi recentemente defendido para as eleições por David Chaum [9].) Num sistema descentralizado, é claro, escolher o moedas aleatórias necessárias para selecionar aleatoriamente os membros de cada conjunto de verificadores SV r é problemático. Recorremos assim à criptografia para selecionar cada conjunto de verificadores, da população de todos os usuários, de uma forma garantidamente automática (ou seja, sem necessidade de troca de mensagens) e aleatória. Em essência, usamos uma função criptográfica para determinar automaticamente, a partir do bloco anterior Br−1, um usuário, o líder, encarregado de propor o novo bloco Br, e o conjunto verificador SV r, em cobrar para chegar a um acordo sobre o bloco proposto pelo líder. Como usuários mal-intencionados podem afetar composição de Br−1 (por exemplo, escolhendo alguns de seus pagamentos), construímos e usamos especialmente entradas adicionais para provar que o líder do r-ésimo bloco e o conjunto verificador SV r são de fato escolhido aleatoriamente. 3. A Quantidade (Semente) Qr. Usamos o último bloco Br−1 em blockchain para determinar automaticamente o próximo conjunto de verificadores e líder responsável pela construção do novo bloco Ir. O desafio desta abordagem é que, ao escolher apenas um pagamento ligeiramente diferente no rodada anterior, nosso poderoso Adversário ganha um tremendo controle sobre o próximo líder. Mesmo que ele controlava apenas 1/1000 dos jogadores/dinheiro no sistema, ele poderia garantir que todos os líderes fossem malicioso. (Veja a Seção Intuição 4.1.) Este desafio é central para todas as abordagens proof-of-stake, e, tanto quanto sabemos, não foi, até agora, resolvido de forma satisfatória. Para enfrentar esse desafio, construímos propositalmente e atualizamos continuamente um relatório separado e cuidadosamente quantidade definida, Qr, que provavelmente é, não apenas imprevisível, mas também não influenciável, pelos nossos adversário poderoso. Podemos nos referir a Qr como a r-ésima semente, pois é de Qr que Algorand seleciona, através de triagem criptográfica secreta, todos os usuários que desempenharão um papel especial na geração do quarto bloco. 4. Classificação criptográfica secreta e credenciais secretas. Usando de forma aleatória e inequívoca o último bloco atual, Br−1, para escolher o conjunto de verificadores e o líder responsável da construção do novo bloco, Br, não é suficiente. Como Br−1 deve ser conhecido antes de gerar Br, a última quantidade não-influenciável Qr−1 contida em Br−1 também deve ser conhecida. Assim, então são os verificadores e o líder encarregados de calcular o bloco Br. Assim, nosso poderoso Adversário pode corromper imediatamente todos eles, antes que se envolvam em qualquer discussão sobre Br, de modo a obter controle total sobre o bloco que certificam. Para evitar este problema, os líderes (e também os verificadores) aprendem secretamente sobre o seu papel, mas podem computar uma credencial adequada, capaz de provar a todos que de fato desempenham esse papel. Quando um usuário percebe secretamente que ele é o líder do próximo bloco, primeiro ele monta secretamente seu próprio novo bloco proposto e, em seguida, divulga-o (para que possa ser certificado) juntamente com o seu próprio credencial. Desta forma, embora o Adversário perceba imediatamente quem é o líder do próximo bloco é, e embora ele possa corrompê-lo imediatamente, será tarde demais para o Adversário influenciar a escolha de um novo bloco. Na verdade, ele não pode mais “revogar” a mensagem do líderdo que um governo poderoso pode colocar de volta na garrafa uma mensagem espalhada de forma viral pelo WikiLeaks. Como veremos, não podemos garantir a singularidade do líder, nem que todos tenham certeza de quem é o líder. é, incluindo o próprio líder! Mas, em Algorand, um progresso inequívoco será garantido. 5. Substituibilidade do Jogador. Depois de propor um novo bloco, o líder pode muito bem “morrer” (ou ser corrompido pelo Adversário), porque seu trabalho está cumprido. Mas, para os verificadores em SV r, as coisas são menos simples. Com efeito, estando encarregado de certificar o novo bloco Br com um número suficiente de assinaturas, eles devem primeiro conseguir um acordo bizantino sobre o bloco proposto pelo líder. O problema é que, não importa quão eficiente seja, BA⋆requer múltiplas etapas e a honestidade de > 2/3 de seus jogadores. Isto é um problema porque, por razões de eficiência, o conjunto de jogadores de BA⋆consiste no pequeno conjunto SV r selecionado aleatoriamente entre o conjunto de todos os usuários. Assim, o nosso poderoso Adversário, embora incapaz de corromper 1/3 de todos os usuários, certamente pode corromper todos os membros do SV r! Felizmente provaremos que o protocolo BA⋆, executado pela propagação de mensagens ponto a ponto, é substituível pelo jogador. Este novo requisito significa que o protocolo corretamente e atinge consenso de forma eficiente, mesmo que cada uma de suas etapas seja executada por um método totalmente novo e aleatório. e conjunto de jogadores selecionados independentemente. Assim, com milhões de usuários, cada pequeno conjunto de jogadores associado a um passo de BA⋆provavelmente possui interseção vazia com o próximo conjunto. Além disso, os conjuntos de jogadores de diferentes etapas do BA⋆provavelmente terão cardinalidades. Além disso, os membros de cada conjunto não sabem quem será o próximo conjunto de jogadores. ser, e não passar secretamente por nenhum estado interno. A propriedade do jogador substituível é realmente crucial para derrotar o dinâmico e muito poderoso Adversário que imaginamos. Acreditamos que os protocolos de jogadores substituíveis serão cruciais em muitos contextos e aplicações. Em particular, eles serão cruciais para executar pequenos subprotocolos com segurança inserido em um universo maior de jogadores com um adversário dinâmico, que, sendo capaz de corromper até mesmo uma pequena fração do total de jogadores, não tem dificuldade em corromper todos os jogadores no menor subprotocolo. Uma propriedade/técnica adicional: honestidade preguiçosa Um usuário honesto segue o que lhe foi prescrito instruções, que incluem estar online e executar o protocolo. Desde então, Algorand tem apenas modesto exigência de computação e comunicação, estar online e rodando o protocolo “no histórico” não é um grande sacrifício. Claro, algumas “ausências” entre jogadores honestos, como aqueles devido à perda repentina de conectividade ou à necessidade de reinicialização, são automaticamente tolerados (porque sempre podemos considerar esses poucos jogadores como temporariamente maliciosos). Destaquemos, porém, que Algorand pode ser simplesmente adaptado para funcionar em um novo modelo, no qual usuários honestos sejam off-line na maior parte do tempo. Nosso novo modelo pode ser apresentado informalmente da seguinte maneira. Honestidade preguiçosa. Grosso modo, um usuário i é preguiçoso, mas honesto se (1) seguir todas as instruções prescritas. instruções, quando ele for solicitado a participar do protocolo, e (2) ele for solicitado a participar ao protocolo apenas raramente e com um aviso prévio adequado. Com uma noção tão relaxada de honestidade, podemos estar ainda mais confiantes de que as pessoas honestas serão à mão quando precisarmos deles, e Algorand garantimos que, quando for o caso, O sistema funciona de forma segura mesmo que, num determinado momento, a maioria dos jogadores participantes são maliciosos.1.3 Trabalho intimamente relacionado As abordagens de prova de trabalho (como as citadas [29] e [4]) são bastante ortogonais às nossas. Assim são os abordagens baseadas no acordo bizantino de passagem de mensagens ou na tolerância prática a falhas bizantinas (como o citado [8]). Na verdade, estes protocolos não podem ser executados entre o conjunto de todos os utilizadores e não podem, em nosso modelo, fique restrito a um conjunto adequadamente pequeno de usuários. Na verdade, nosso poderoso adversário, meu corromper imediatamente todos os usuários envolvidos em um pequeno conjunto encarregado de realmente executar um protocolo BA. Nossa abordagem poderia ser considerada relacionada à prova de aposta [2], no sentido de que o “poder” dos usuários na construção de blocos é proporcional ao dinheiro que possuem no sistema (em oposição a —digamos— para o dinheiro que colocaram em “escrow”). O artigo mais próximo do nosso é o Sleepy Consensus Model of Pass e Shi [30]. Para evitar o computação pesada necessária na abordagem proof-of-work, seu artigo se baseia (e gentilmente créditos) Classificação criptográfica secreta de Algorand. Com este aspecto crucial em comum, vários existem diferenças significativas entre nossos artigos. Em particular, (1) Sua configuração é apenas permitida. Por outro lado, Algorand também é um sistema sem permissão. (2) Eles usam um protocolo estilo Nakamoto e, portanto, seus blockchain se bifurcam com frequência. Embora dispensando proof-of-work, em seu protocolo um líder selecionado secretamente é solicitado a alongar o válido mais longo (em um sentido mais rico) blockchain. Assim, os garfos são inevitáveis e é preciso esperar que o bloco está suficientemente “profundo” na cadeia. Na verdade, para atingir seus objetivos com um adversário capazes de corrupções adaptativas, eles exigem que um bloco seja poli(N) profundo, onde N representa o número total de usuários no sistema. Observe que, mesmo assumindo que um bloco poderia ser produzido em um minuto, se houvesse N = 1 milhão de usuários, seria necessário esperar cerca de 2 milhões de anos para um bloco para se tornar N 2 de profundidade, e por cerca de 2 anos para um bloco se tornar N-profundo. Em contraste, O blockchain de Algorand bifurca-se apenas com probabilidade insignificante, mesmo que o Adversário corrompa usuários imediatamente e de forma adaptativa, e seus novos blocos podem ser imediatamente confiáveis. (3) Eles não tratam de acordos bizantinos individuais. De certa forma, eles apenas garantem “eventual consenso sobre uma sequência crescente de valores”. O protocolo deles é de replicação de estado, em vez do que um BA, e não pode ser usado para chegar a um acordo bizantino sobre um valor individual de juros. Por outro lado, Algorand também pode ser usado apenas uma vez, se desejado, para permitir que milhões de usuários acessem rapidamente chegar a um acordo bizantino sobre um valor específico de juros. (4) Eles exigem relógios fracamente sincronizados. Ou seja, todos os relógios dos usuários são adiantados por um pequeno intervalo de tempo δ. Por outro lado, em Algorand, os relógios precisam apenas ter (essencialmente) a mesma “velocidade”. (5) Seu protocolo funciona com usuários preguiçosos, mas honestos, ou com a maioria honesta dos usuários online. Eles gentilmente creditam Algorand por levantar a questão de usuários honestos ficarem off-line em massa e por apresentando o modelo de honestidade preguiçosa em resposta. O protocolo deles não funciona apenas nos preguiçosos modelo de honestidade, mas também em seu modelo adversário sonolento, onde um adversário escolhe quais usuários estão on-line e quais estão off-line, desde que, em todos os momentos, a maioria dos usuários on-line seja honesta.2 2A versão original do seu artigo, na verdade, considerava apenas a segurança no seu modelo adversário sonolento. O versão original de Algorand, que precede a deles, também explicitamente prevista assumindo que uma determinada maioria do os jogadores online são sempre honestos, mas excluíram-no explicitamente de consideração, em favor do modelo de honestidade preguiçosa. (Por exemplo, se em algum momento metade dos usuários honestos optar por ficar off-line, então a maioria dos usuários on-line pode muito bem ser malicioso. Assim, para evitar que isso aconteça, o Adversário deveria forçar a maior parte de seus jogadores corrompidos também fiquem off-line, o que claramente vai contra o seu próprio interesse.) Observe que um protocolo com maioria de jogadores preguiçosos, mas honestos, funciona muito bem se a maioria dos usuários on-line for sempre mal-intencionada. Isto é assim, porque um número suficiente de jogadores honestos, sabendo que serão cruciais em algum momento raro, elegerá não ficar off-line nesses momentos, nem podem ser forçados a ficar off-line pelo Adversário, já que ele não sabe quem é o jogadores honestos e cruciais podem ser.(6) Eles exigem uma maioria simples e honesta. Por outro lado, a versão atual de Algorand requer uma maioria honesta de 2/3. Outro artigo próximo de nós é Ouroboros: um protocolo Blockchain de prova de participação comprovadamente seguro, por Kiayias, Russell, David e Oliynykov [20]. Além disso, o sistema deles apareceu depois do nosso. Também usa classificação criptográfica para dispensar prova de trabalho de maneira comprovável. No entanto, seus O sistema é, novamente, um protocolo do estilo Nakamoto, no qual as bifurcações são inevitáveis e frequentes. (No entanto, em seu modelo, os bloqueios não precisam ser tão profundos quanto o modelo de consenso sonolento.) Além disso, seu sistema baseia-se nas seguintes suposições: nas palavras dos próprios autores, “(1) o a rede é altamente síncrona, (2) a maioria das partes interessadas selecionadas está disponível conforme necessário para participar em cada época, (3) as partes interessadas não permanecem off-line por longos períodos de tempo, (4) a adaptabilidade das corrupções está sujeita a um pequeno atraso que é medido em rodadas lineares em o parâmetro de segurança.” Por outro lado, Algorand é, com grande probabilidade, livre de bifurcação e não se baseia em nenhuma dessas quatro suposições. Em particular, em Algorand, o Adversário é capaz de corromper instantaneamente os usuários que ele deseja controlar.

Preliminares

2.1 Primitivos criptográficos Hashing ideal. Contaremos com uma função criptográfica hash eficientemente computável, H, que mapeia cadeias arbitrariamente longas em cadeias binárias de comprimento fixo. Seguindo uma longa tradição, modelamos H como um oracle aleatório, essencialmente uma função que mapeia cada string s possível para um aleatório e string binária selecionada independentemente (e então fixa), H(s), do comprimento escolhido. Neste artigo, H tem saídas longas de 256 bits. Na verdade, esse comprimento é curto o suficiente para tornar o sistema eficiente e longo o suficiente para torná-lo seguro. Por exemplo, queremos que H seja resistente a colisões. Ou seja, deveria ser difícil encontrar duas strings diferentes x e y tais que H(x) = H(y). Quando H é um oracle aleatório com saídas longas de 256 bits, encontrar qualquer par de strings é de fato difícil. (Tentar aleatoriamente e confiar no paradoxo do aniversário exigiria 2.256/2 = 2.128 testes.) Assinatura digital. As assinaturas digitais permitem que os usuários autentiquem informações entre si sem compartilhar nenhuma chave secreta. Um esquema de assinatura digital consiste em três algoritmos: um gerador de chave probabilística G, um algoritmo de assinatura S e um algoritmo de verificação V. Dado um parâmetro de segurança k, um número inteiro suficientemente alto, um usuário i usa G para produzir um par de Chaves de k bits (ou seja, strings): uma chave “pública” pki e uma chave de assinatura “secreta” correspondente ski. Crucialmente, um a chave pública não “trai” sua chave secreta correspondente. Ou seja, mesmo com conhecimento de pki, não outro além de mim é capaz de calcular esqui em menos de um tempo astronômico. O usuário i usa ski para assinar mensagens digitalmente. Para cada mensagem possível (string binária) m, primeiro hashes m e então executa o algoritmo S nas entradas H(m) e ski para produzir a string de k bits sigpki(m) \(\triangleq\)S(H(m), esqui) .3 3Como H é resistente a colisões, é praticamente impossível que, ao assinar m, alguém “assine acidentalmente” uma mensagem diferente mensagem m'.A string binária sigpki(m) é chamada de assinatura digital de i de m (relativa a pki) e pode ser denotado mais simplesmente por sigi(m), quando a chave pública pki está clara no contexto. Qualquer pessoa que conheça o pki pode usá-lo para verificar as assinaturas digitais produzidas pelo i. Especificamente, em insere (a) a chave pública pki de um jogador i, (b) uma mensagem m e (c) uma string s, ou seja, i é alegado assinatura digital da mensagem m, o algoritmo de verificação V produz SIM ou NÃO. As propriedades que exigimos de um esquema de assinatura digital são: 1. Assinaturas legítimas são sempre verificadas: Se s = sigi(m), então V (pki, m, s) = Y ES; e 2. Assinaturas digitais são difíceis de falsificar: sem conhecimento de esqui, é hora de encontrar uma string como essa. que V (pki, m, s) = Y ES, para uma mensagem m nunca assinada por i, é astronomicamente longo. (Seguindo os fortes requisitos de segurança de Goldwasser, Micali e Rivest [17], isso é verdade mesmo que se possa obter a assinatura de qualquer outra mensagem.) Assim, para evitar que qualquer outra pessoa assine mensagens em seu nome, um jogador deve manter o seu assinando a chave secreta de esqui (daí o termo “chave secreta”) e para permitir que qualquer pessoa verifique as mensagens ele assina, tenho interesse em divulgar sua chave pki (daí o termo “chave pública”). Em geral, uma mensagem m não é recuperável a partir da sua assinatura sigi(m). Para negociar virtualmente com assinaturas digitais que satisfaçam a propriedade de “recuperabilidade” conceitualmente conveniente (ou seja, para garantir que o signatário e a mensagem sejam facilmente computáveis a partir de uma assinatura, definimos SIGpki(m) = (i, m, sigpki(m)) e SIGi(m) = (i, m, sigi(m)), se pki estiver claro. Assinatura digital exclusiva. Consideramos também esquemas de assinatura digital (G, S, V ) que satisfazem a seguinte propriedade adicional. 3. Singularidade. É difícil encontrar strings pk′, m, s e s′ tais que ̸= s′ e V (pk′, m, s) = V (pk′, m, s′) = 1. (Observe que a propriedade de exclusividade também é válida para strings pk′ que não são geradas legitimamente chaves públicas. Em particular, porém, a propriedade de unicidade implica que, se alguém usasse a propriedade gerador de chave especificado G para calcular uma chave pública pk junto com uma chave secreta correspondente sk, e, portanto, sabia que sk, seria essencialmente impossível também para ele encontrar dois dispositivos digitais diferentes. assinaturas de uma mesma mensagem relativa a pk.) Observações • De assinaturas exclusivas a funções aleatórias verificáveis. Em relação a um digital esquema de assinatura com a propriedade de exclusividade, o mapeamento m \(\to\) H(sigi(m)) associa-se a cada string m possível, uma string única de 256 bits selecionada aleatoriamente e a exatidão disso o mapeamento pode ser provado dada a assinatura sigi(m). Ou seja, esquema ideal de hashing e assinatura digital que satisfaz a propriedade de exclusividade essencialmente fornecer uma implementação elementar de uma função aleatória verificável, conforme introduzida e por Micali, Rabin e Vadhan [27]. (Sua implementação original era necessariamente mais complexa, já que eles não dependiam do hashing ideal.)• Três necessidades diferentes para assinaturas digitais. Em Algorand, um usuário depende de recursos digitais assinaturas para (1) Autenticação dos próprios pagamentos do i. Nesta aplicação, as chaves podem ser de “longo prazo” (ou seja, usadas para assinar muitas mensagens durante um longo período de tempo) e vêm de um esquema de assinatura comum. (2) Gerar credenciais provando que i tem o direito de agir em alguma etapa s de uma rodada r. Aqui, as chaves podem ser de longo prazo, mas devem vir de um esquema que satisfaça a propriedade de exclusividade. (3) Autenticar a mensagem que envio em cada etapa em que atua. Aqui, as chaves devem ser efêmero (ou seja, destruído após seu primeiro uso), mas pode vir de um esquema de assinatura comum. • Uma simplificação de pequeno custo. Para simplificar, imaginamos que cada usuário i tenha uma única chave de longo prazo. Conseqüentemente, tal chave deve vir de um esquema de assinatura com a exclusividade propriedade. Essa simplicidade tem um pequeno custo computacional. Normalmente, na verdade, digital único as assinaturas são um pouco mais caras para produzir e verificar do que as assinaturas comuns. 2.2 O livro-razão público idealizado Algorand tenta imitar o seguinte sistema de pagamento, baseado em um livro-razão público idealizado. 1. O Status Inicial. O dinheiro está associado a chaves públicas individuais (geradas de forma privada e propriedade dos usuários). Deixando pk1, . . . , pkj são as chaves públicas iniciais e a1, . . . , e seus respectivos quantias iniciais de unidades monetárias, então o status inicial é S0 = (pk1, a1), . . . , (pkj, aj) , que é assumido como conhecimento comum no sistema. 2. Pagamentos. Seja pk uma chave pública atualmente com \(\geq\)0 unidades monetárias, pk′ outra chave pública chave, e a′ um número não negativo não maior que a. Então, um pagamento (válido) \(\wp\)é um pagamento digital assinatura, relativa a pk, especificando a transferência de a′ unidades monetárias de pk para pk′, juntamente com algumas informações adicionais. Em símbolos, \(\wp\)= SIGpk(pk, pk′, a′, I, H(I)), onde I representa qualquer informação adicional considerada útil, mas não sensível (por exemplo, tempo informações e um identificador de pagamento) e qualquer informação adicional considerada sensível (por exemplo, o motivo do pagamento, possivelmente as identidades dos proprietários do pk e do pk′, e assim por diante). Referimo-nos a pk (ou seu proprietário) como pagador, a cada pk′ (ou seu proprietário) como beneficiário e a a′ como o valor do pagamento \(\wp\). Adesão gratuita por meio de pagamentos. Observe que os usuários podem ingressar no sistema quando quiserem, gerando seus próprios pares de chaves pública/secreta. Assim, a chave pública pk′ que aparece em o pagamento \(\wp\)acima pode ser uma chave pública recém-gerada que nunca “possuíu” nenhum dinheiro antes. 3. O Livro Mágico. No Sistema Idealizado, todos os pagamentos são válidos e aparecem em formato inviolável lista L de conjuntos de pagamentos “postados no céu” para que todos possam ver: L = PAGUE 1, PAGUE 2, . . . ,Cada bloco PAY r+1 consiste no conjunto de todos os pagamentos efetuados desde o aparecimento do bloco PAGAR R. No sistema ideal, um novo bloco aparece após um período de tempo fixo (ou finito). Discussão. • Pagamentos mais gerais e resultados de transações não gastas. De forma mais geral, se uma chave pública pk possui um valor a, então um pagamento válido \(\wp\)of pk pode transferir os valores a′ 1, uma' 2, . . ., respectivamente às chaves pk′ 1, pk' 2, . . ., desde que P eu' j \(\leq\)a. Em Bitcoin e sistemas similares, o dinheiro pertencente a um pacote de chave pública é segregado em valores, e um pagamento \(\wp\)feito por pk deve transferir esse valor segregado em sua totalidade. Se pk deseja transferir apenas uma fração a′ < a de a para outra chave, então ele também deve transferir a fração saldo, a saída da transação não gasta, para outra chave, possivelmente o próprio pk. Algorand também funciona com chaves com valores segregados. Contudo, para focar no aspectos novos de Algorand, é conceitualmente mais simples manter nossas formas de pagamento mais simples e chaves com um único valor associado a elas. • Status atual. O Esquema Idealizado não fornece diretamente informações sobre o atual status do sistema (ou seja, sobre quantas unidades monetárias cada chave pública possui). Esta informação é dedutível do Magic Ledger. No sistema ideal, um usuário ativo armazena e atualiza continuamente as informações de status mais recentes, ou ele teria que reconstruí-lo, seja do zero, ou desde a última vez que ele calculou. (Na próxima versão deste artigo, aumentaremos Algorand para permitir seu usuários reconstruam o status atual de maneira eficiente.) • Segurança e “Privacidade”. As assinaturas digitais garantem que ninguém pode falsificar um pagamento outro usuário. Em um \(\wp\) de pagamento, as chaves públicas e o valor não ficam ocultos, mas sim o sensível informação que eu sou. Na verdade, apenas H(I) aparece em \(\wp\), e como H é uma função hash ideal, H(I) é um valor aleatório de 256 bits e, portanto, não há como descobrir o que eu era melhor do que simplesmente adivinhando. No entanto, para provar o que eu era (por exemplo, para provar o motivo do pagamento), o o pagador pode apenas revelar I. A exatidão do I revelado pode ser verificada calculando H(I) e comparando o valor resultante com o último item de \(\wp\). Na verdade, como H é resiliente a colisões, é difícil encontrar um segundo valor I′ tal que H(I) = H(I′). 2.3 Noções e notações básicas Chaves, usuários e proprietários A menos que especificado de outra forma, cada chave pública (“chave” para abreviar) é de longo prazo e relativa a um esquema de assinatura digital com a propriedade de exclusividade. Uma chave pública que eu juntei o sistema quando outra chave pública j já no sistema faz um pagamento para i. Para a cor, personificamos as chaves. Referimo-nos a uma chave i como “ele”, dizemos que sou honesto, que envio e recebe mensagens, etc. Usuário é sinônimo de chave. Quando queremos distinguir uma chave de a quem pertence, utilizamos respectivamente os termos “chave digital” e “proprietário”. Sistemas sem permissão e com permissão. Um sistema não tem permissão se uma chave digital for gratuita aderir a qualquer momento e um proprietário pode possuir várias chaves digitais; e é permitido, caso contrário.Representação Única Cada objeto em Algorand possui uma representação única. Em particular, cada conjunto {(x, y, z, . . .) : x \(\in\)X, y \(\in\)Y, z \(\in\)Z, . . .} é ordenado de uma maneira pré-especificada: por exemplo, primeiro lexicograficamente em x, depois em y, etc. Relógios da mesma velocidade Não existe um relógio global: cada usuário tem seu próprio relógio. Relógios do usuário não precisa ser sincronizado de forma alguma. Assumimos, no entanto, que todos eles têm a mesma velocidade. Por exemplo, quando são 12h de acordo com o relógio de um usuário i, podem ser 14h30 de acordo com o relógio de outro usuário j, mas quando for 12h01 de acordo com o relógio de i, serão 2h31 de acordo para o relógio de j. Ou seja, “um minuto é igual (suficientemente, essencialmente igual) para todos os usuários”. Rodadas Algorand está organizado em unidades lógicas, r = 0, 1, . . ., chamadas rodadas. Usamos consistentemente sobrescritos para indicar rodadas. Para indicar que uma quantidade não numérica Q (por exemplo, uma string, uma chave pública, um conjunto, uma assinatura digital, etc.) refere-se a uma rodada r, simplesmente escrevemos Qr. Somente quando Q for um número genuíno (em oposição a uma sequência binária interpretável como um número), faça escrevemos Q(r), de modo que o símbolo r não possa ser interpretado como o expoente de Q. No (início de uma) rodada r > 0, o conjunto de todas as chaves públicas é PKr e o status do sistema é Sr = n eu, um (r) eu,. . .  : eu \(\in\)PKro , onde um(r) eu é a quantidade de dinheiro disponível para a chave pública i. Observe que PKr é dedutível de Sr, e esse Sr também pode especificar outros componentes para cada chave pública i. Para a rodada 0, PK0 é o conjunto de chaves públicas iniciais e S0 é o status inicial. Tanto PK0 quanto S0 são considerados de conhecimento comum no sistema. Para simplificar, no início da rodada r, então são PK1, . . . , PKr e S1, . . . , Sr. Numa rodada r, o status do sistema transita de Sr para Sr+1: simbolicamente, Rodada r: Sr −→Sr+1. Pagamentos Em Algorand, os usuários realizam pagamentos continuamente (e os divulgam na forma descrito na subseção 2.7). Um pagamento \(\wp\)de um usuário i \(\in\)PKr tem o mesmo formato e semântica como no Sistema Ideal. Ou seja, \(\wp\)= SIGi(i, i′, a, I, H(I)) . O pagamento \(\wp\)é individualmente válido em uma rodada r (é um pagamento redondo, para abreviar) se (1) seu valor a é menor ou igual a a(r) i, e (2) não aparece em nenhum conjunto de pagamentos oficial PAY r′ para r′ < r. (Conforme explicado abaixo, a segunda condição significa que \(\wp\) ainda não entrou em vigor. Um conjunto de pagamentos redondos de i é coletivamente válido se a soma de seus valores for no máximo a(r) eu. Conjuntos de pagamentos Um conjunto de pagamentos redondo P é um conjunto de pagamentos redondos tais que, para cada usuário i, os pagamentos de i em P (possivelmente nenhum) são coletivamente válidos. O conjunto de todos os conjuntos de pagamentos da rodada r é PAY(r). Um round-r payset P é máximo se nenhum superconjunto de P for um payset round-r. Na verdade, sugerimos que um pagamento \(\wp\)também especifica uma rodada \(\rho\), \(\wp\)= SIGi(\(\rho\), i, i′, a, I, H(I)) , e não pode ser válido em qualquer rodada fora de [\(\rho\), \(\rho\) + k], para algum inteiro não negativo fixo k.4 4Isso simplifica a verificação se \(\wp\)se tornou “eficaz” (ou seja, simplifica a determinação se algum conjunto de salários PAGAR r contém \(\wp\). Quando k = 0, se \(\wp\)= SIGi(r, i, i′, a, I, H(I)) e \(\wp\)/\(\in\)PAY r, então devo reenviar \(\wp\).Pagamentos oficiais Para cada rodada r, Algorand seleciona publicamente (da maneira descrita mais adiante) um único conjunto de pagamentos (possivelmente vazio), PAY r, o conjunto de pagamentos oficial da rodada. (Essencialmente, PAY r representa os pagamentos redondos que “realmente” aconteceram.) Assim como no Sistema Ideal (e Bitcoin), (1) a única maneira de um novo usuário j entrar no sistema deve ser o destinatário de um pagamento pertencente ao conjunto de pagamentos oficial PAY r de uma determinada rodada r; e (2) PAY r determina o status da próxima rodada, Sr+1, daquele da rodada atual, Sr. Simbolicamente, PAGAR r: Sr −→Sr+1. Especificamente, 1. o conjunto de chaves públicas da rodada r + 1, PKr+1, consiste na união de PKr e no conjunto de todos chaves de beneficiário que aparecem, pela primeira vez, nos pagamentos de PAY r; e 2. a quantidade de dinheiro a(r+1) eu que um usuário i possui na rodada r + 1 é a soma de ai(r) - ou seja, o quantidade de dinheiro que possuo na rodada anterior (0 se i̸\(\in\)PKr) - e a soma das quantias pago a i de acordo com os pagamentos de PAY r. Em suma, tal como no Sistema Ideal, cada estado Sr+1 é dedutível do histórico de pagamentos anteriores: PAGUE 0, . . . , PAGUE R. 2.4 Blocos e Blocos Comprovados Em Algorand0, o bloco Br correspondente a uma rodada r especifica: o próprio r; o conjunto de pagamentos de rodada r, PAGAR r; uma quantidade Qr, a ser explicada, e o hash do bloco anterior, H(Br−1). Assim, partindo de algum bloco fixo B0, temos um blockchain tradicional: B1 = (1, PAGUE 1, Q0, H(B0)), B2 = (2, PAGUE 2, Q1, H(B1)), B3 = (3, PAGUE 3, Q2, H(B2)), . . . Em Algorand, a autenticidade de um bloco é na verdade comprovada por uma informação separada, um “certificado de bloco” CERT r, que transforma Br em um bloco comprovado, Br. O livro mágico, portanto, é implementado pela sequência dos blocos comprovados, B1, B2, . . . Discussão Como veremos, o CERT r consiste em um conjunto de assinaturas digitais para H(Br), aquelas de um maioria dos membros do SV r, juntamente com uma prova de que cada um desses membros pertence efectivamente para SV r. Poderíamos, é claro, incluir os certificados CERT r nos próprios blocos, mas conceitualmente mais limpo para mantê-lo separado.) Em Bitcoin cada bloco deve satisfazer uma propriedade especial, ou seja, deve “conter uma solução de um crypto puzzle”, o que torna a geração de blocos computacionalmente intensiva e bifurcações inevitáveis e não raro. Por outro lado, blockchain de Algorand tem duas vantagens principais: é gerado com cálculo mínimo e não será bifurcado com probabilidade extremamente alta. Cada bloco Bi é final com segurança assim que entrar em blockchain.2,5 Probabilidade de falha aceitável Para analisar a segurança de Algorand especificamos a probabilidade, F, com a qual estamos dispostos a aceitar que algo dê errado (por exemplo, que um conjunto verificador SV r não tenha uma maioria honesta). Como no caso do comprimento de saída da função criptográfica hash H, também F é um parâmetro. Mas, como nesse caso, achamos útil definir F para um valor concreto, de modo a obter uma estimativa mais intuitiva. compreensão do fato de que é de fato possível, em Algorand, desfrutar simultaneamente de segurança suficiente e eficiência suficiente. Para enfatizar que F é um parâmetro que pode ser definido conforme desejado, na primeira e segundas modalidades, definimos respectivamente F = 10−12 e F = 10−18 . Discussão Observe que 10-12 é, na verdade, menos que um em um trilhão, e acreditamos que tal a escolha de F é adequada em nossa aplicação. Vamos enfatizar que 10−12 não é a probabilidade com o qual o Adversário pode falsificar os pagamentos de um usuário honesto. Todos os pagamentos são digitalmente assinado e, portanto, se as assinaturas digitais adequadas forem usadas, a probabilidade de falsificar um pagamento é muito inferior a 10-12 e é, na verdade, essencialmente 0. O evento ruim que estamos dispostos a tolerar com probabilidade F é que as bifurcações de Algorand blockchain. Observe que, com nossa configuração de F e rodadas de um minuto, espera-se que uma bifurcação ocorra no blockchain de Algorand tão raramente quanto (aproximadamente) uma vez em 1,9 milhões de anos. Por outro lado, em Bitcoin, bifurcações ocorrem com bastante frequência. Uma pessoa mais exigente pode definir F para um valor mais baixo. Para este fim, em nossa segunda modalidade consideramos definir F como 10−18. Observe que, supondo que um bloco seja gerado a cada segundo, 1018 é o número estimado de segundos que o Universo levou até agora: desde o Big Bang até o presente tempo. Assim, com F = 10−18, se um bloco for gerado em um segundo, deve-se esperar para a idade de o Universo para ver uma bifurcação. 2.6 O modelo adversário Algorand foi projetado para ser seguro em um modelo muito adversário. Deixe-nos explicar. Usuários honestos e maliciosos Um usuário é honesto se seguir todas as instruções do protocolo e é perfeitamente capaz de enviar e receber mensagens. Um usuário é malicioso (ou seja, bizantino, no linguagem da computação distribuída) se ele puder desviar-se arbitrariamente de suas instruções prescritas. O Adversário O Adversário é um algoritmo eficiente (tecnicamente em tempo polinomial), personificado pela cor, que pode imediatamente tornar malicioso qualquer usuário que ele quiser, a qualquer hora que ele quiser (sujeito apenas para um limite superior ao número de usuários que ele pode corromper). O Adversário controla totalmente e coordena perfeitamente todos os usuários maliciosos. Ele realiza todas as ações em seu nome, incluindo receber e enviar todas as suas mensagens, e pode permitir que eles se desviem de suas instruções prescritas de maneira arbitrária. Ou ele pode simplesmente isolar um usuário corrompido enviando e recebimento de mensagens. Deixe-nos esclarecer que ninguém mais fica sabendo automaticamente que um usuário i é malicioso, embora a maldade de i possa transparecer nas ações que o Adversário o faz tomar. Este poderoso adversário, no entanto, • Não possui poder computacional ilimitado e não consegue forjar com sucesso o digital assinatura de um usuário honesto, exceto com probabilidade insignificante; e• Não poderá interferir de forma alguma nas trocas de mensagens entre usuários honestos. Além disso, sua capacidade de atacar usuários honestos é limitada por uma das seguintes suposições. Honestidade Maioria do Dinheiro Consideramos um continuum de Maioria Honesta de Dinheiro (HMM) suposições: ou seja, para cada inteiro não negativo k e h real > 1/2, HHMk > h: os usuários honestos em cada rodada r possuíam uma fração maior que h de todo o dinheiro em o sistema na rodada r −k. Discussão. Supondo que todos os usuários mal-intencionados coordenem perfeitamente suas ações (como se fossem controlados por uma única entidade, o Adversário) é uma hipótese bastante pessimista. Coordenação perfeita entre também muitos indivíduos é difícil de alcançar. Talvez a coordenação só ocorra dentro de grupos separados de jogadores maliciosos. Mas, como não se pode ter certeza sobre o nível de coordenação dos usuários mal-intencionados podemos aproveitar, é melhor prevenir do que remediar. Presumir que o Adversário possa corromper secreta, dinâmica e imediatamente os usuários também é pessimista. Afinal, de forma realista, assumir o controle total das operações de um usuário deve levar algum tempo. A suposição HMMk > h implica, por exemplo, que, se uma rodada (em média) for implementada em um minuto, então, a maior parte do dinheiro em uma determinada rodada permanecerá em mãos honestas por pelo menos duas horas, se k = 120, e pelo menos uma semana, se k = 10.000. Observe que as suposições do HMM e a maioria honesta anterior do poder de computação suposições estão relacionadas no sentido de que, uma vez que o poder computacional pode ser comprado com dinheiro, se usuários mal-intencionados possuírem a maior parte do dinheiro, eles poderão obter a maior parte do poder de computação. 2.7 O modelo de comunicação Prevemos que a propagação de mensagens — isto é, “fofoca entre pares”5 — seja o único meio de comunicação. Suposição temporária: entrega oportuna de mensagens em toda a rede. Para na maior parte deste artigo assumimos que toda mensagem propagada atinge quase todos os usuários honestos em tempo hábil. Removeremos essa suposição na Seção 10, onde tratamos de redes partições, sejam de ocorrência natural ou induzidas adversamente. (Como veremos, apenas assumimos entrega oportuna de mensagens dentro de cada componente conectado da rede.) Uma maneira concreta de capturar a entrega oportuna de mensagens propagadas (em toda a rede) é o seguinte: Para toda alcançabilidade \(\rho\) > 95% e tamanho de mensagem \(\mu\) \(\in\)Z+, existe \(\lambda\) \(\rho\),\(\mu\) tal que, se um usuário honesto propagar uma mensagem m de \(\mu\) bytes no tempo t, então m atinge, no tempo t + \(\lambda\) \(\rho\),\(\mu\), pelo menos uma fração \(\rho\) dos usuários honestos. 5Essencialmente, como em Bitcoin, quando um usuário propaga uma mensagem m, todo usuário ativo recebe m pela primeira vez, seleciona aleatoriamente e de forma independente um número adequadamente pequeno de usuários ativos, seus “vizinhos”, para os quais ele encaminha m, possivelmente até que ele receba um reconhecimento deles. A propagação de m termina quando nenhum usuário recebe m pela primeira vez.A propriedade acima, no entanto, não pode suportar nosso protocolo Algorand, sem prever explícita e separadamente um mecanismo para obter o blockchain mais recente - por outro usuário/depositório/etc. Na verdade, para construir um novo bloco Br, não apenas um conjunto adequado de verificadores deve receber atempadamente rodadas-r mensagens, mas também as mensagens das rodadas anteriores, para conhecer o Br−1 e todos os outros blocos, o que é necessário para determinar se os pagamentos em Br são válidos. O seguinte suposição, em vez disso, é suficiente. Suposição de propagação de mensagens (MP): Para todo \(\rho\) > 95% e \(\mu\) \(\in\)Z+, existe \(\lambda\) \(\rho\),\(\mu\) tal que, para todos os tempos t e todas as mensagens de \(\mu\) bytes m propagadas por um usuário honesto antes de t −\(\lambda\) \(\rho\), \(\mu\), m é recebido, no tempo t, por pelo menos uma fração \(\rho\) dos usuários honestos. O protocolo Algorand ′ na verdade instrui cada um de um pequeno número de usuários (ou seja, os verificadores de um dada etapa de uma rodada em Algorand ′, para propagar uma mensagem separada de tamanho (pequeno) prescrito, e precisamos limitar o tempo necessário para cumprir essas instruções. Fazemo-lo enriquecendo o MP suposição da seguinte forma. Para todo n, \(\rho\) > 95% e \(\mu\) \(\in\)Z+, existe \(\lambda\)n,\(\rho\),\(\mu\) tal que, para todos os tempos t e todos \(\mu\)-byte mensagens m1, . . . , mn, cada um propagado por um usuário honesto antes de t −\(\lambda\)n,\(\rho\),\(\mu\), m1, . . . , mn são recebidos, no tempo t, por pelo menos uma fração \(\rho\) dos usuários honestos. Nota • A suposição acima é deliberadamente simples, mas também mais forte do que o necessário em nosso artigo.6 • Para simplificar, assumimos \(\rho\) = 1 e, portanto, deixamos de mencionar \(\rho\). • Presumimos pessimistamente que, desde que não viole a suposição do MP, o Adversário controla totalmente a entrega de todas as mensagens. Em particular, sem ser notado pelos honestos usuários, o Adversário pode decidir arbitrariamente qual jogador honesto recebe qual mensagem quando, e acelerar arbitrariamente a entrega de qualquer mensagem que desejar.7

O protocolo BA BA⋆ em um ambiente tradicional

Como já enfatizado, o acordo bizantino é um ingrediente chave de Algorand. Na verdade, é através o uso de um protocolo BA que Algorand não seja afetado por bifurcações. No entanto, para estarmos seguros contra os nossos Adversário poderoso, Algorand deve contar com um protocolo BA que satisfaça a nova capacidade de substituição do jogador restrição. Além disso, para que Algorand seja eficiente, tal protocolo BA deve ser muito eficiente. Os protocolos BA foram definidos pela primeira vez para um modelo de comunicação idealizado, síncrono completo redes (redes SC). Tal modelo permite um projeto e análise mais simples de protocolos BA. 6Dada a porcentagem honesta h e a probabilidade de falha aceitável F, Algorand calcula um limite superior, N, ao número máximo de membros dos verificadores em uma etapa. Assim, a suposição de MP só precisa ser válida para n \(\leq\)N. Além disso, como afirmado, a suposição de MP é válida, não importa quantas outras mensagens possam ser propagadas ao lado o mj. Como veremos, entretanto, em Algorand as mensagens são propagadas em tempo essencialmente não sobreposto intervalos, durante os quais um único bloco é propagado, ou no máximo N verificadores propagam um pequeno (por exemplo, 200B) mensagem. Assim, poderíamos reafirmar o pressuposto do MP de uma forma mais fraca, mas também mais complexa. 7Por exemplo, ele pode aprender imediatamente as mensagens enviadas por jogadores honestos. Assim, um usuário malicioso i′, que é solicitado a propagar uma mensagem simultaneamente com um usuário honesto i, pode sempre escolher sua própria mensagem m′ com base em a mensagem m realmente propagada por i. Essa habilidade está relacionada à pressa, no jargão da computação distribuída literatura.Assim, nesta seção, apresentamos um novo protocolo BA, BA⋆, para redes SC e ignorando a questão da substituibilidade do jogador. O protocolo BA⋆é uma contribuição de valor separado. Na verdade, é o protocolo BA criptográfico mais eficiente para redes SC conhecido até agora. Para usá-lo em nosso protocolo Algorand, modificamos BA⋆ um pouco, de modo a levar em conta nossos diferentes modelo de comunicação e contexto, mas certifique-se, na seção X, de destacar como BA⋆é usado dentro do nosso protocolo real Algorand ′. Começamos por relembrar o modelo em que BA⋆opera e a noção de acordo bizantino. 3.1 Redes Síncronas Completas e Adversários Correspondentes Em uma rede SC, existe um relógio comum, marcando a cada tempo integral r = 1, 2, . . . A cada clique par em r, cada jogador i envia instantânea e simultaneamente um único mensagem senhor i,j (possivelmente a mensagem vazia) para cada jogador j, incluindo ele mesmo. Cada senhor i,j é recebido naquele momento clique em r + 1 do jogador j, junto com a identidade do remetente i. Novamente, num protocolo de comunicação, um jogador é honesto se seguir todas as instruções prescritas. instruções e malicioso de outra forma. Todos os jogadores maliciosos são totalmente controlados e perfeitamente coordenado pelo Adversário, que, em particular, recebe imediatamente todas as mensagens dirigidas a jogadores maliciosos e escolhe as mensagens que eles enviam. O Adversário pode imediatamente tornar malicioso qualquer usuário honesto que ele quiser, a qualquer momento, clicar ele deseja, sujeito apenas a um possível limite máximo para o número de jogadores mal-intencionados. Isto é, o Adversário “não pode interferir nas mensagens já enviadas por um usuário honesto i”, o que será entregue normalmente. O Adversário também tem a capacidade adicional de ver instantaneamente, em cada rodada par, o mensagens que os jogadores atualmente honestos enviam e usam instantaneamente essas informações para escolher as mensagens que os jogadores maliciosos enviam ao mesmo tempo são marcadas. Observações • Poder Adversário. A configuração acima é muito contraditória. Na verdade, no acordo bizantino literatura, muitos ambientes são menos antagônicos. No entanto, algumas configurações mais adversárias também foi considerado, onde o Adversário, após ver as mensagens enviadas por um jogador honesto, em um determinado momento clique em r, tem a capacidade de apagar todas essas mensagens da rede, imediatamente corrupto i, escolha a mensagem que o agora malicioso i envia na hora clique em r, e faça com que eles entregue normalmente. O poder previsto do Adversário corresponde ao que ele tem em nosso cenário. • Abstração Física. O modelo de comunicação previsto abstrai um modelo mais físico, em que cada par de jogadores (i, j) está ligado por uma linha de comunicação separada e privada li,j. Ou seja, ninguém mais pode injetar, interferir ou obter informações sobre as mensagens enviadas. li, j. A única maneira de o Adversário ter acesso a li,j é corromper i ou j. • Privacidade e Autenticação. Nas redes SC a privacidade e a autenticação das mensagens são garantidas por suposição. Por outro lado, na nossa rede de comunicação, onde as mensagens são propagadas ponto a ponto, a autenticação é garantida por assinaturas digitais e a privacidade é inexistente. Assim, para adotar o protocolo BA⋆ ao nosso cenário, cada mensagem trocada deverá ser assinada digitalmente (identificando ainda o estado para o qual foi enviado). Felizmente, os protocolos BA que usamos considere usar em Algorand não requer privacidade de mensagem.3.2 A noção de um acordo bizantino A noção de acordo bizantino foi introduzida por Pease Shostak e Lamport [31] para o caso binário, isto é, quando todo valor inicial consiste em um bit. No entanto, foi rapidamente prorrogado para valores iniciais arbitrários. (Veja as pesquisas de Fischer [16] e Chor e Dwork [10].) Por um BA protocolo, queremos dizer um de valor arbitrário. Definição 3.1. Em uma rede síncrona, seja P um protocolo de n jogadores, cujo conjunto de jogadores é comum conhecimento entre os jogadores, t um número inteiro positivo tal que n \(\geq\)2t + 1. Dizemos que P é um valor arbitrário (respectivamente, binário) (n, t) - Protocolo de acordo bizantino com solidez \(\sigma\) \(\in\) (0, 1) se, para cada conjunto de valores V que não contém o símbolo especial \(\bot\) (respectivamente, para V = {0, 1}), em um execução em que no máximo t dos jogadores são maliciosos e em que cada jogador i começa com um valor inicial vi \(\in\)V , todo jogador honesto j para com probabilidade 1, gerando um valor outi \(\in\)V \(\cup\){\(\bot\)} de modo a satisfazer, com probabilidade pelo menos \(\sigma\), as duas condições seguintes: 1. Acordo: Existe out \(\in\)V \(\cup\){\(\bot\)} tal que outi = out para todos os jogadores honestos i. 2. Consistência: se, para algum valor v \(\in\)V , vi = v para todos os jogadores honestos, então out = v. Referimo-nos a out como saída de P e a cada outi como saída do jogador i. 3.3 A notação BA # Em nossos protocolos BA, um jogador é obrigado a contar quantos jogadores lhe enviaram uma determinada mensagem em um determinado passo. Assim, para cada valor possível v que possa ser enviado,

s

eu(v) (ou apenas #i(v) quando s estiver limpo) é o número de jogadores j dos quais i recebeu v na etapa s. Lembrando que um jogador i recebe exatamente uma mensagem de cada jogador j, se o número de jogadores é n, então, para todos i e s, P v#s eu(v) = n. 3.4 O Protocolo Binário BA BBA⋆ Nesta seção apresentamos um novo protocolo BA binário, BBA⋆, que depende da honestidade de mais mais de dois terços dos jogadores e é muito rápido: não importa o que os jogadores maliciosos possam fazer, cada execução de seu loop principal faz com que os jogadores concordem com a probabilidade 1/3. Cada jogador tem sua própria chave pública de um esquema de assinatura digital que satisfaz a assinatura única. propriedade. Como este protocolo se destina a ser executado em rede completa síncrona, não há necessidade de um jogador assinar cada uma de suas mensagens. Assinaturas digitais são usadas para gerar um bit aleatório suficientemente comum na Etapa 3. (Em Algorand, assinaturas digitais também são usadas para autenticar todas as outras mensagens.) O protocolo requer uma configuração mínima: uma string aleatória comum r, independente da posição dos jogadores. chaves. (Em Algorand, r é na verdade substituído pela quantidade Qr.) O protocolo BBA⋆é um loop de 3 etapas, onde os jogadores trocam repetidamente valores booleanos e diferentes jogadores podem sair deste ciclo em momentos diferentes. Um jogador i sai deste loop propagando, em alguma etapa, um valor especial 0∗ou um valor especial 1∗, instruindo assim todos os jogadores a “fingir” que recebem respectivamente 0 e 1 de i em todas as etapas futuras. (Alternativamente dito: assumirque a última mensagem recebida por um jogador j de outro jogador i foi um pouco b. Então, em qualquer passo em que ele não recebe nenhuma mensagem de i, j age como se eu tivesse enviado a ele o bit b.) O protocolo utiliza um contador \(\gamma\), representando quantas vezes seu loop de 3 etapas foi executado. No início do BBA⋆, \(\gamma\) = 0. (Pode-se pensar em \(\gamma\) como um contador global, mas na verdade é aumentado por cada jogador individual toda vez que o loop é executado.) Existem n \(\geq\)3t + 1, onde t é o número máximo possível de jogadores maliciosos. Um binário a string x é identificada com o inteiro cuja representação binária (com possíveis 0s iniciais) é x; e lsb(x) denota o bit menos significativo de x. Protocolo BBA⋆ (Comunicação) Etapa 1. [Coin-Fixed-To-0 Step] Cada jogador envia bi. 1.1 Se #1 i (0) \(\geq\)2t + 1, então i define bi = 0, envia 0∗, gera outi = 0, e PARA. 1.2 Se #1 i (1) \(\geq\)2t + 1, então, então i define bi = 1. 1.3 Caso contrário, i define bi = 0. (Comunicação) Etapa 2. [Coin-Fixed-To-1 Step] Cada jogador envia bi. 2.1 Se #2 i (1) \(\geq\)2t + 1, então i define bi = 1, envia 1∗, saídas outi = 1, e PARA. 2.2 Se #2 i (0) \(\geq\)2t + 1, então defino bi = 0. 2.3 Caso contrário, i define bi = 1. (Comunicação) Etapa 3. [Etapa da Moeda Genuinamente Invertida] Cada jogador i envia bi e SIGi(r, \(\gamma\)). 3.1 Se #3 i (0) \(\geq\)2t + 1, então i define bi = 0. 3.2 Se #3 i (1) \(\geq\)2t + 1, então i define bi = 1. 3.3 Caso contrário, deixando Si = {j \(\in\)N que enviou i uma mensagem adequada nesta etapa 3}, i define bi = c \(\triangleq\)lsb(minj\(\in\)Si H(SIGi(r, \(\gamma\)))); aumenta \(\gamma\)i em 1; e retorna ao Passo 1. Teorema 3.1. Sempre que n \(\geq\)3t + 1, BBA⋆é um protocolo binário (n, t)-BA com solidez 1. Uma prova do Teorema 3.1 é dada em [26]. Sua adaptação ao nosso ambiente e sua capacidade de substituição do jogador propriedade são novos. Observação histórica Protocolos BA binários probabilísticos foram propostos pela primeira vez por Ben-Or em configurações assíncronas [7]. O protocolo BBA⋆é uma nova adaptação, para nossa configuração de chave pública, do protocolo BA binário de Feldman e Micali [15]. Seu protocolo foi o primeiro a funcionar da maneira esperada. número constante de etapas. Funcionou fazendo com que os próprios jogadores implementassem uma moeda comum, uma noção proposta por Rabin, que a implementou por meio de uma parte externa confiável [32].3.5 Consenso Graduado e Protocolo GC Recordemos, para valores arbitrários, uma noção de consenso muito mais fraca do que o acordo bizantino. Definição 3.2. Seja P um protocolo no qual o conjunto de todos os jogadores é de conhecimento comum, e cada jogador i conhece em particular um valor inicial arbitrário v′ eu. Dizemos que P é um protocolo de consenso com classificação (n, t) se, em cada execução com n jogadores, em a maioria dos quais são maliciosos, todo jogador honesto pára de produzir um par de valor-grau (vi, gi), onde gi \(\in\){0, 1, 2}, de modo a satisfazer as três condições a seguir: 1. Para todos os jogadores honestos i e j, |gi −gj| \(\leq\)1. 2. Para todos os jogadores honestos i e j, gi, gj > 0 ⇒vi = vj. 3. Se v′ 1 = \(\cdots\) =v′ n = v para algum valor v, então vi = v e gi = 2 para todos os jogadores honestos i. Nota Histórica A noção de consenso graduado é simplesmente derivada daquela de consenso graduado. transmitido, apresentado por Feldman e Micali em [15], ao fortalecer a noção de um cruzado acordo, conforme introduzido por Dolev [12], e refinado por Turpin e Coan [33].8 Em [15], os autores também forneceram um protocolo de transmissão graduado em 3 etapas (n, t), gradecast, para n \(\geq\)3t+1. Um protocolo de transmissão graduado (n, t) mais complexo para n> 2t + 1 foi encontrado posteriormente por Katz e Koo [19]. O seguinte protocolo GC de duas etapas consiste nas duas últimas etapas do gradecast, expressas em nosso notação. Para enfatizar este fato, e para corresponder às etapas do protocolo Algorand ′ da seção 4.1, nós nomeie respectivamente 2 e 3 as etapas do GC. Protocolo GC Passo 2. Cada jogador envia v′ eu para todos os jogadores. Etapa 3. Cada jogador i envia a todos os jogadores a string x se e somente se #2 eu(x) \(\geq\)2t + 1. Determinação de saída. Cada jogador i gera o par (vi, gi) calculado da seguinte forma: • Se, para algum x, #3 i (x) \(\geq\)2t + 1, então vi = x e gi = 2. • Se, para algum x, #3 eu (x) \(\geq\)t + 1, então vi = x e gi = 1. • Caso contrário, vi = \(\bot\) e gi = 0. Teorema 3.2. Se n \(\geq\)3t + 1, então GC é um protocolo de transmissão com classificação (n, t). A prova segue imediatamente aquela da classificação do protocolo em [15] e, portanto, é omitida.9 8Em essência, num protocolo de transmissão gradual, (a) a entrada de cada jogador é a identidade de um distinto jogador, o remetente, que tem um valor arbitrário v como uma entrada privada adicional, e (b) as saídas devem satisfazer o mesmas propriedades 1 e 2 do consenso graduado, mais a seguinte propriedade 3′: se o remetente for honesto, então vi = v e gi = 2 para todos os jogadores honestos i. 9Na verdade, no protocolo deles, na etapa 1, o remetente envia seu próprio valor privado v para todos os jogadores, e cada jogador i deixa v' consisto no valor que ele realmente recebeu do remetente na etapa 1.3.6 O Protocolo BA⋆ Descrevemos agora o protocolo BA de valor arbitrário BA⋆por meio do protocolo BA binário BBA⋆e o protocolo de consenso graduado GC. Abaixo, o valor inicial de cada jogador i é v′ eu. Protocolo BA⋆ Etapas 1 e 2. Cada jogador i executa GC, na entrada v′ i, para calcular um par (vi, gi). Etapa 3, . . . Cada jogador i executa BBA⋆ - com entrada inicial 0, se gi = 2, e 1 caso contrário - então como calcular o bit outi. Determinação de saída. Cada jogador i gera vi, se outi = 0, e \(\bot\)caso contrário. Teorema 3.3. Sempre que n \(\geq\)3t + 1, BA⋆é um protocolo (n, t)-BA com solidez 1. Prova. Primeiro provamos a consistência e depois a concordância. Prova de consistência. Suponha que, para algum valor v \(\in\)V , v′ i = v. Então, pela propriedade 3 de consenso graduado, após a execução do GC, todos os jogadores honestos produzem (v, 2). Assim, 0 é a parte inicial de todos os jogadores honestos no final da execução do BBA⋆. Assim, pelo Acordo propriedade do acordo bizantino binário, ao final da execução de BA⋆, outi = 0 para todos os honestos jogadores. Isto implica que a saída de cada jogador honesto i em BA⋆é vi = v. ✷ Prova de acordo. Como BBA⋆é um protocolo BA binário, (A) outi = 1 para todo jogador honesto i, ou (B) outi = 0 para todos os jogadores honestos i. No caso A, todos os jogadores honestos produzem \(\bot\)em BA⋆ e, portanto, o acordo é válido. Considere agora o caso B. Em neste caso, na execução de BBA⋆, o bit inicial de pelo menos um jogador honesto i é 0. (Na verdade, se inicial de todos os jogadores honestos fosse 1, então, pela propriedade Consistência do BBA⋆, teríamos outj = 1 para todos os j honestos.) Assim, após a execução do GC, i gera o par (v, 2) para alguns valor v. Assim, pela propriedade 1 do consenso graduado, gj > 0 para todos os jogadores honestos j. Assim, por propriedade 2 do consenso graduado, vj = v para todos os jogadores honestos j. Isto implica que, no final do BA⋆, todo jogador honesto j produz v. Assim, o acordo também é válido no caso B. ✷ Como tanto a Consistência quanto o Acordo são válidos, BA⋆é um protocolo BA de valor arbitrário. Nota Histórica Turpin e Coan foram os primeiros a mostrar que, para n \(\geq\)3t+1, qualquer binário (n, t)-BA O protocolo pode ser convertido em um protocolo de valor arbitrário (n, t)-BA. O valor arbitrário de redução O acordo bizantino para o acordo bizantino binário via consenso gradual é mais modular e mais limpo e simplifica a análise do nosso protocolo Algorand Algorand ′. Generalizando BA⋆para uso em Algorand Algorand funciona mesmo quando toda a comunicação é via fofocando. Contudo, embora apresentado numa rede de comunicação tradicional e familiar, por assim dizer para permitir uma melhor comparação com o estado da técnica e uma compreensão mais fácil, o protocolo BA⋆works também em redes de fofoca. Na verdade, em nossas concretizações detalhadas de Algorand, iremos apresentá-lo diretamente para redes de fofocas. Devemos também salientar que satisfaz a substituibilidade do jogador propriedade que é crucial para que Algorand esteja seguro no modelo muito adversário previsto.

Qualquer protocolo substituível por jogador BA trabalhando em uma rede de comunicação de fofoca pode ser empregado com segurança dentro do sistema inventivo Algorand. Em particular, Micali e Vaikunthanatan estenderam o BA⋆ para trabalhar de forma muito eficiente também com uma maioria simples de jogadores honestos. Isso o protocolo também pode ser usado em Algorand.

Duas Modalidades de Algorand

Conforme discutido, em um nível muito alto, uma rodada de Algorand idealmente procede da seguinte forma. Primeiro, aleatoriamente o usuário selecionado, o líder, propõe e circula um novo bloco. (Este processo inclui inicialmente selecionando alguns líderes potenciais e depois garantindo que, pelo menos uma boa fração do tempo, um surge um único líder comum.) Em segundo lugar, um comitê de usuários selecionado aleatoriamente é selecionado e chega a um acordo bizantino sobre o bloco proposto pelo líder. (Este processo inclui que cada etapa do protocolo BA é executada por um comitê selecionado separadamente.) O bloco acordado é então assinado digitalmente por um determinado limite (TH) de membros do comitê. Essas assinaturas digitais são circulados para que todos tenham certeza de qual é o novo bloco. (Isto inclui a circulação do credencial dos signatários, e autenticando apenas o hash do novo bloco, garantindo que todos tem a garantia de aprender o bloco, uma vez que seu hash seja esclarecido.) Nas próximas duas seções, apresentamos duas modalidades de Algorand, Algorand ′ 1 e Algorand ′ 2, que funcionam sob a suposição da maioria dos usuários honestos. Na Seção 8 mostramos como adotar essas incorporações para trabalhar sob uma suposição de maioria honesta de dinheiro. Algorand ′ 1 prevê apenas que > 2/3 dos membros do comitê sejam honestos. Além disso, em Algorand ′ 1, o número de passos para chegar a um acordo bizantino é limitado a um nível adequadamente elevado número, de modo que é garantido que o acordo será alcançado com probabilidade esmagadora dentro de um número fixo de etapas (mas potencialmente exigindo mais tempo do que as etapas de Algorand ′ 2). No caso remoto em que o acordo ainda não foi alcançado na última etapa, a comissão concorda com a bloco vazio, que é sempre válido. Algorand ′ 2 prevê que o número de membros honestos em uma comissão seja sempre maior do que ou igual a um limite fixo tH (o que garante que, com probabilidade esmagadora, pelo menos 2/3 dos membros do comitê são honestos). Além disso, Algorand ′ 2 permite que o acordo bizantino ser alcançado em um número arbitrário de etapas (mas potencialmente em um tempo menor que Algorand ′ 1). É fácil derivar muitas variantes destas modalidades básicas. Em particular, é fácil, dado Algorand ′ 2, para modificar Algorand ′ 1, de modo a permitir chegar a um acordo bizantino de forma arbitrária número de etapas. Ambas as modalidades compartilham o seguinte núcleo, notações, noções e parâmetros comuns. 4.1 Um núcleo comum Objetivos Idealmente, para cada rodada r, Algorand satisfaria as seguintes propriedades: 1. Correção Perfeita. Todos os usuários honestos concordam com o mesmo bloco Br. 2. Completude 1. Com probabilidade 1, o conjunto de pagamentos de Br, PAY r, é máximo.10 10Como os conjuntos de pagamentos são definidos para conter pagamentos válidos e os usuários honestos para fazer apenas pagamentos válidos, um valor máximo PAY r contém os pagamentos “atualmente pendentes” de todos os usuários honestos.É claro que garantir a correção perfeita por si só é trivial: todo mundo sempre escolhe o modelo oficial. payset PAY r fique vazio. Mas neste caso, o sistema teria completude 0. Infelizmente, garantir tanto a correção perfeita quanto a integridade 1 não é fácil na presença de malware usuários. Algorand adota assim um objetivo mais realista. Informalmente, deixando h denotar a porcentagem de usuários honestos, h > 2/3, o objetivo de Algorand é Garantindo, com probabilidade esmagadora, correção perfeita e completude próxima de h. Privilegiar a correcção em detrimento da integralidade parece ser uma escolha razoável: os pagamentos não processados em uma rodada pode ser processada na próxima, mas deve-se evitar garfos, se possível. Acordo Bizantino Liderado A correção perfeita pode ser garantida da seguinte forma. No início da rodada r, cada usuário i constrói seu próprio bloco candidato Br i , e então todos os usuários alcançam o Byzantine acordo sobre um bloco candidato. De acordo com nossa introdução, o protocolo BA empregado requer uma maioria honesta de 2/3 e é substituível pelo jogador. Cada uma de suas etapas pode ser executada por um pequeno e conjunto de verificadores selecionados aleatoriamente, que não compartilham nenhuma variável interna. Infelizmente, esta abordagem não tem garantias de integridade. Isso ocorre porque o candidato blocos de usuários honestos são provavelmente totalmente diferentes uns dos outros. Assim, em última análise O bloco acordado pode sempre ser aquele com um conjunto de pagamentos não máximo. Na verdade, pode ser sempre o bloco vazio, B\(\varepsilon\), ou seja, o bloco cujo payset está vazio. bem, será o padrão, vazio. Algorand ′ evita esse problema de completude da seguinte maneira. Primeiro, um líder para a rodada r, \(\ell\)r, é selecionado. Então, \(\ell\)r propaga seu próprio bloco candidato, Br \(\ell\)r. Finalmente, os usuários chegam a um acordo sobre o bloqueio eles realmente recebem de \(\ell\)r. Porque, sempre que \(\ell\)r for honesto, perfeita correção e integridade 1 ambos são válidos, Algorand ′ garante que \(\ell\)r é honesto com probabilidade próxima de h. (Quando o líder é malicioso, não nos importamos se o bloco acordado é aquele com um conjunto de pagamentos vazio. Afinal, um o líder malicioso \(\ell\)r pode sempre escolher Br de forma maliciosa \(\ell\)r para ser o bloco vazio e, honestamente propagá-lo, forçando assim os usuários honestos a concordar com o bloco vazio.) Seleção de Líder Em Algorand's, o r-ésimo bloco tem a forma Br = (r, PAY r, Qr, H(Br−1). Como já mencionado na introdução, a quantidade Qr−1 é cuidadosamente construída de modo a ser essencialmente não manipulável pelo nosso poderoso Adversário. (Mais adiante nesta seção, iremos fornecer alguma intuição sobre por que isso acontece.) No início de uma rodada r, todos os usuários sabem o blockchain até agora, B0, . . . , Br−1, a partir do qual eles deduzem o conjunto de usuários de cada rodada anterior: que é, PK1, . . . , PKr−1. Um potencial líder da rodada r é um usuário i tal que .H SIGi r, 1, Qr−1 \(\leq\)p. Deixe-nos explicar. Observe que, como a quantidade Qr−1 faz parte do bloco Br−1, e o subjacente esquema de assinatura satisfaz a propriedade de exclusividade, SIGi r, 1, Qr−1 é uma string binária exclusivamente associado a i e r. Assim, como H é um oracle aleatório, H SIGi r, 1, Qr−1 é um aleatório de 256 bits string longa associada exclusivamente a i e r. O símbolo “.” na frente de H SIGi r, 1, Qr−1 é o ponto decimal (no nosso caso, binário), de modo que ri \(\triangleq\).H SIGi r, 1, Qr−1 é a expansão binária de um número aleatório de 256 bits entre 0 e 1 associado exclusivamente a i e r. Assim a probabilidade de que ri é menor ou igual a p é essencialmente p. (Nosso mecanismo de seleção de líderes potenciais tem sido inspirado no esquema de micropagamento de Micali e Rivest [28].) A probabilidade p é escolhida de modo que, com probabilidade esmagadora (ou seja, 1 −F), pelo menos um o verificador potencial é honesto. (Se for verdade, p é escolhido como a menor probabilidade.)Observe que, como i é o único capaz de calcular suas próprias assinaturas, só ele pode determinar se ele é um verificador potencial da primeira rodada. No entanto, ao revelar sua própria credencial, \(\sigma\)r eu \(\triangleq\)SIGi r, 1, Qr−1 , posso provar a qualquer um que sou um verificador potencial da rodada r. O líder \(\ell\)r é definido como o líder potencial cuja credencial hashed é menor que a hashed credencial de todos os outros líderes potenciais j: isto é, H(\(\sigma\)r,s \(\ell\)r ) \(\leq\)H(\(\sigma\)r,s j). Observe que, como um \(\ell\)r malicioso pode não revelar sua credencial, o líder correto da rodada r pode nunca será conhecido, e que, salvo laços improváveis, \(\ell\)r é de fato o único líder da rodada r. Vamos finalmente trazer um último mas importante detalhe: um usuário pode ser um líder em potencial (e, portanto, o líder) de uma rodada r somente se ele pertencer ao sistema por pelo menos k rodadas. Isso garante a não manipulabilidade de Qr e de todas as quantidades Q futuras. Na verdade, um dos potenciais líderes irá realmente determinar Qr. Seleção do Verificador Cada passo s > 1 da rodada r é executado por um pequeno conjunto de verificadores, SV r,s. Novamente, cada verificador i \(\in\)SV r,s é selecionado aleatoriamente entre os usuários já presentes no sistema k rodadas. antes de r, e novamente através da quantidade especial Qr−1. Especificamente, i \(\in\)PKr−k é um verificador em SV r,s, se .H SIGi r, s, Qr−1 \(\leq\)p′. Mais uma vez, só eu sei se ele pertence a SV r,s, mas, se for esse o caso, ele poderia provar isso exibindo sua credencial \(\sigma\)r,s eu \(\triangleq\)H(SIGi r, s, Qr−1 ). Um verificador i \(\in\)SV r,s envia uma mensagem, mr,s eu, em etapa s da rodada r, e esta mensagem inclui sua credencial \(\sigma\)r,s i , de modo a permitir que os verificadores do passo para reconhecer que o senhor,s eu é uma mensagem legítima de etapas. A probabilidade p′ é escolhida de modo a garantir que, em SV r,s, sendo #good o número de usuários honestos e #bad o número de usuários mal-intencionados, com grande probabilidade o seguinte duas condições são válidas. Para concretização Algorand ′ 1: (1) #bom > 2 \(\cdot\) #ruim e (2) #bom + 4 \(\cdot\) #ruim < 2n, onde n é a cardinalidade esperada de SV r,s. Para concretização Algorand ′ 2: (1) #bom > tH e (2) #bom + 2#ruim < 2tH, onde tH é um limite especificado. Estas condições implicam que, com probabilidade suficientemente alta, (a) na última etapa do BA protocolo, haverá pelo menos um determinado número de jogadores honestos para assinar digitalmente o novo bloco Br, (b) apenas um bloco por rodada poderá ter o número necessário de assinaturas, e (c) o BA utilizado o protocolo tem (em cada etapa) a maioria honesta necessária de 2/3. Esclarecendo a geração de blocos Se o líder da rodada r for honesto, então o bloco correspondente é da forma Br = r, PAGAR r, SIG\(\ell\)r Qr−1 , H Br−1 , onde o payset PAY r é máximo. (lembre-se de que todos os conjuntos de pagamentos são, por definição, válidos coletivamente.) Caso contrário (ou seja, se \(\ell\)r for malicioso), Br terá uma das duas formas possíveis a seguir: Br = r, PAGAR r, SIGi Qr-1 , H Br−1 e Br = Br \(\varepsilon\) \(\triangleq\) r, \(\emptyset\), Qr−1, H Br−1 .Na primeira forma, PAY r é um conjunto de pagamentos (não necessariamente máximo) e pode ser PAY r = \(\emptyset\); e eu sou um potencial líder da rodada r. (No entanto, posso não ser o líder \(\ell\)r. Isso pode realmente acontecer se \(\ell\)r mantém em segredo sua credencial e não se revela.) A segunda forma surge quando, na execução da rodada R do protocolo BA, todos os jogadores honestos produza o valor padrão, que é o bloco vazio Br \(\varepsilon\) em nossa aplicação. (Por definição, o possível as saídas de um protocolo BA incluem um valor padrão, genericamente denotado por \(\bot\). Consulte a seção 3.2.) Observe que, embora os paysets estejam vazios em ambos os casos, Br = r, \(\emptyset\), SIGi Qr-1 , H Br−1 e irmão \(\varepsilon\) são blocos sintaticamente diferentes e surgem em duas situações diferentes: respectivamente, “todos correu bem na execução do protocolo BA” e “algo deu errado no Protocolo BA, e o valor padrão foi gerado”. Vamos agora descrever intuitivamente como ocorre a geração do bloco Br na rodada r de Algorand ′. Na primeira etapa, cada jogador elegível, ou seja, cada jogador i \(\in\)PKr−k, verifica se é um potencial líder. Se for esse o caso, então me perguntam, usando todos os pagamentos que ele viu até agora, e o atual blockchain, B0, . . . , Br−1, para preparar secretamente um conjunto de pagamento máximo, PAY r eu, e secretamente monta seu bloco candidato, Br = r, PAGUE r eu, SIGi Qr-1 , H Br−1 . Isto é, ele não apenas incluir no Br i, como segundo componente o conjunto de pagamentos recém-preparado, mas também, como terceiro componente, sua própria assinatura de Qr−1, a terceira componente do último bloco, Br−1. Finalmente, ele propagou seu mensagem round-r-step-1, senhor,1 i , que inclui (a) seu bloco candidato Br eu, (b) sua assinatura adequada de seu bloco candidato (ou seja, sua assinatura do hash do Br i , e (c) sua própria credencial \(\sigma\)r,1 eu, provando que ele é de fato um verificador potencial da rodada r. (Observe que, até que um i honesto produza sua mensagem mr,1 i, o Adversário não tem ideia de que i é um verificador potencial. Se ele quiser corromper potenciais líderes honestos, o Adversário poderia muito bem jogadores honestos aleatórios corruptos. No entanto, uma vez que ele vê o Sr.,1 i , uma vez que contém a credencial de i, o O adversário sabe e pode corromper-me, mas não pode impedir o senhor,1 i , que é propagado viralmente, de atingindo todos os usuários do sistema.) Na segunda etapa, cada verificador selecionado j \(\in\)SV r,2 tenta identificar o líder da rodada. Especificamente, j usa as credenciais da etapa 1, \(\sigma\)r,1 i1 , . . . , \(\sigma\)r,1 in , contido na mensagem apropriada da etapa 1 mr,1 eu ele recebeu; hashes todos eles, ou seja, calcula H  \(\sigma\)r,1 e1  , . . . , H  \(\sigma\)r,1 em  ; encontra a credencial, \(\sigma\)r,1 \(\ell\)j , cujo hash é lexicograficamente mínimo; e considera \(\ell\)r j para ser o líder da rodada r. Lembre-se que cada credencial considerada é uma assinatura digital de Qr−1, que o SIGi r, 1, Qr−1 é determinado exclusivamente por i e Qr−1, que H é aleatório oracle e, portanto, cada H(SIGi r, 1, Qr−1 é uma longa string aleatória de 256 bits exclusiva para cada líder potencial i da rodada r. Disto podemos concluir que, se a string de 256 bits Qr-1 fosse ela mesma aleatória e independentemente selecionados, então seriam as credenciais hashed de todos os líderes potenciais da rodada r. Na verdade, todos líderes potenciais são bem definidos, assim como suas credenciais (sejam realmente computadas ou não). Além disso, o conjunto de líderes potenciais da rodada r é um subconjunto aleatório dos usuários da rodada r −k, e um líder potencial honesto eu sempre constrói e propaga adequadamente sua mensagem, Sr. eu, que contém a credencial de i. Assim, como o percentual de usuários honestos é h, não importa qual seja o potenciais líderes mal-intencionados possam fazer (por exemplo, revelar ou ocultar suas próprias credenciais), o mínimo A credencial de líder potencial hashed pertence a um usuário honesto, que é necessariamente identificado por todos ser o líder \(\ell\)r da rodada r. Conseqüentemente, se a string de 256 bits Qr-1 fosse ela mesma aleatória e selecionado independentemente, com probabilidade exatamente h (a) o líder \(\ell\)r é honesto e (b) \(\ell\)j = \(\ell\)r para todos verificadores honestos da etapa 2 j. Na realidade, as credenciais hashed são, sim, selecionadas aleatoriamente, mas dependem de Qr−1, que énão selecionados de forma aleatória e independente. Provaremos em nossa análise, entretanto, que Qr−1 é suficientemente não manipulável para garantir que o líder de uma rodada seja honesto com a probabilidade h′ suficientemente próximo de h: ou seja, h′ > h2(1 + h −h2). Por exemplo, se h = 80%, então h′ > 0,7424. Tendo identificado o líder da rodada (o que eles fazem corretamente quando o líder \(\ell\)r é honesto), a tarefa dos verificadores da etapa 2 é começar a executar o BA usando como valores iniciais o que eles acreditam ser o bloco do líder. Na verdade, para minimizar a quantidade de comunicação necessária, um verificador j \(\in\)SV r,2 não usa, como seu valor de entrada v′ j para o protocolo bizantino, o bloco Bj que ele realmente recebeu de \(\ell\)j (o usuário j acredita ser o líder), mas o líder, mas o hash desse bloco, ou seja, v′ j = H(Bi). Assim, após o término do protocolo BA, os verificadores da última etapa não calcula o bloco round-r desejado Br, mas calcula (autentica e propagar) H(Br). Assim, uma vez que H(Br) é assinado digitalmente por um número suficiente de verificadores do última etapa do protocolo BA, os usuários do sistema perceberão que H(Br) é o hash do novo bloco. Entretanto, eles também devem recuperar (ou esperar, já que a execução é bastante assíncrona) o próprio bloco Br, que o protocolo garante que está realmente disponível, não importa o que o Adversário poderia fazer. Assincronia e Tempo Algorand ′ 1 e Algorand ′ 2 têm um grau significativo de assincronia. Isso ocorre porque o Adversário tem grande liberdade para programar a entrega das mensagens que estão sendo enviadas. propagado. Além disso, quer o número total de passos numa ronda seja limitado ou não, há a variância contribui com o número de passos realmente dados. Assim que ele souber dos certificados de B0, . . . , Br−1, um usuário i calcula Qr−1 e começa a trabalhar na rodada r, verificando se ele é um líder em potencial ou um verificador em algumas etapas da rodada r. Supondo que devo agir na etapa s, à luz da assincronia discutida, baseio-me em vários estratégias para garantir que ele tenha informações suficientes antes de agir. Por exemplo, ele pode esperar para receber pelo menos um determinado número de mensagens dos verificadores de passo anterior, ou esperar um tempo suficiente para garantir que ele receba as mensagens de pessoas suficientemente muitos verificadores da etapa anterior. O Seed Qr e o Parâmetro Look-Back k Lembre-se que, idealmente, as quantidades Qr deveriam aleatórios e independentes, embora seja suficiente que sejam suficientemente não manipuláveis por o Adversário. À primeira vista, poderíamos escolher Qr−1 para coincidir com H PAGUE r−1 , e assim evitar especifique Qr−1 explicitamente em Br−1. Uma análise elementar revela, contudo, que utilizadores maliciosos podem aproveitar esse mecanismo de seleção.11 Alguns esforços adicionais mostram que miríades de outros 11Estamos no início da rodada r −1. Assim, Qr−2 = PAY r−2 é conhecido publicamente, e o Adversário é privado sabe quem são os líderes potenciais que ele controla. Suponha que o Adversário controle 10% dos usuários, e que, com probabilidade muito alta, um usuário malicioso w é o líder potencial da rodada r −1. Ou seja, suponha que H SIGw r −2, 1, Qr −2 é tão pequeno que é altamente improvável que um líder potencial honesto seja realmente o líder da rodada r −1. (Lembre-se que, uma vez que escolhemos líderes potenciais através de um mecanismo secreto de classificação criptográfica, o Adversário não sabe quem são os líderes potenciais honestos.) O Adversário, portanto, está na invejável posição de escolher o conjunto de pagamentos PAY ′ que ele deseja, e torná-lo o conjunto de pagamentos oficial da rodada r −1. No entanto, ele pode fazer mais. Ele também pode garantir que, com alta probabilidade, () um de seus usuários maliciosos será o líder também da rodada r, para que ele possa escolher livremente qual será o PAY r. (E assim por diante. Pelo menos por um longo tempo, isto é, contanto que esses eventos de alta probabilidade realmente ocorram.) Para garantir (), o Adversário age da seguinte forma. Vamos PAGAR' seja o conjunto de pagamentos que o Adversário prefere para a rodada r −1. Então, ele calcula H(PAY ′) e verifica se, para algum o jogador já malicioso z, SIGz(r, 1, H(PAY ′)) é particularmente pequeno, ou seja, pequeno o suficiente para que com valores muito altos probabilidade z será o líder da rodada r. Se for esse o caso, então ele instrui w a escolher seu bloco candidato a seralternativas, baseadas em quantidades de blocos tradicionais, são facilmente exploráveis pelo Adversário para garantir que líderes maliciosos são muito frequentes. Em vez disso, definimos específica e indutivamente nossa marca nova quantidade Qr para poder provar que ela não é manipulável pelo Adversário. Ou seja, Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), se Br não for o bloco vazio, e Qr \(\triangleq\)H(Qr−1, r) caso contrário. A intuição de por que esta construção de Qr funciona é a seguinte. Suponha por um momento que Qr−1 é verdadeiramente selecionado de forma aleatória e independente. Então, será assim Qr? Quando \(\ell\)r é honesto, o a resposta é (grosso modo) sim. Isto é assim porque H(SIG\(\ell\)r( \(\cdot\) ), r) : {0, 1}256 −→{0, 1}256 é uma função aleatória. Quando \(\ell\)r é malicioso, entretanto, Qr não é mais definido univocamente a partir de Qr−1 e \(\ell\)r. Existem pelo menos dois valores separados para Qr. Um continua a ser Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), e o outro é H(Qr−1, r). Vamos primeiro argumentar que, embora a segunda escolha seja um tanto arbitrária, uma segunda escolha é absolutamente obrigatória. A razão para isso é que um \(\ell\)r malicioso sempre pode causar blocos candidatos totalmente diferentes a serem recebidos pelos verificadores honestos da segunda etapa.12 Uma vez for esse o caso, é fácil garantir que o bloco finalmente acordado através do protocolo BA de round r será o padrão e, portanto, não conterá a assinatura digital de Qr-1 de ninguém. Mas o sistema deve continuar e, para isso, precisa de um líder para a rodada r. Se este líder for automaticamente e selecionado abertamente, então o Adversário irá corrompê-lo trivialmente. Se for selecionado pelo anterior Qr−1 através do mesmo processo, então \(\ell\)r será novamente o líder na rodada r+1. Propomos especificamente usam o mesmo mecanismo secreto de classificação criptográfica, mas aplicado a uma nova quantidade Q: a saber, H(Qr−1, r). Ter essa quantidade como a saída de H garante que a saída seja aleatória, e incluindo r como a segunda entrada de H, enquanto todos os outros usos de H têm uma ou mais de 3 entradas, “garante” que tal Qr seja selecionado de forma independente. Novamente, nossa escolha específica da alternativa Qr não importa, o que importa é que \(\ell\)r tem duas opções para Qr e, portanto, ele pode dobrar suas chances ter outro usuário mal-intencionado como o próximo líder. As opções para Qr podem ser ainda mais numerosas para o Adversário que controla um \(\ell\)r malicioso. Por exemplo, sejam x, y e z três líderes potenciais maliciosos da rodada r, tais que H \(\sigma\)r,1 x
< H \(\sigma\)r,1 sim
< H \(\sigma\)r,1 z
e H  \(\sigma\)r,1 z  é particularmente pequeno. Isto é, tão pequeno que há uma boa chance de que H  \(\sigma\)r,1 z  é menor da credencial hashed de todo líder potencial honesto. Então, pedindo a x para esconder seu credencial, o Adversário tem uma boa chance de fazer com que y se torne o líder da rodada r −1. Isto implica que ele tem outra opção para Qr: a saber, SIGy Qr-1 . Da mesma forma, o Adversário pode peça a x e y que retenham suas credenciais, de modo que z se torne o líder da rodada r −1 e ganhando outra opção para Qr: a saber, SIGz Qr-1 . É claro, porém, que cada uma dessas e outras opções tem uma chance diferente de zero de falhar, porque o O adversário não pode prever o hash das assinaturas digitais dos usuários potenciais honestos. Br−1 eu = (r −1, PAY ′, H(Br−2). Caso contrário, ele tem dois outros usuários maliciosos x e y para continuar gerando um novo pagamento \(\wp\)′, de um para outro, até que, para algum usuário malicioso z (ou mesmo para algum usuário fixo z) H (SIGz (PAY ′ \(\cup\){\(\wp\)})) é particularmente pequeno também. Esta experiência irá parar rapidamente. E quando isso acontece, o Adversário pede que você proponha o bloco candidato Br−1 eu = (r −1, PAGUE ′ \(\cup\){\(\wp\)}, H(Br−2). 12Por exemplo, para simplificar (mas extremo), “quando o tempo da segunda etapa estiver prestes a expirar”, \(\ell\)r poderia enviar por e-mail diretamente um bloco candidato Bi diferente para cada usuário i. Dessa forma, sejam quem forem os verificadores da etapa 2, eles terá recebido blocos totalmente diferentes.Uma análise cuidadosa, semelhante à cadeia de Markov, mostra que, independentemente das opções que o Adversário escolha fazer na rodada r −1, desde que ele não possa injetar novos usuários no sistema, ele não poderá diminuir o probabilidade de um usuário honesto ser o líder da rodada r + 40 muito abaixo de h. Esta é a razão que exigimos que os potenciais líderes da rodada r sejam usuários já existentes na rodada r −k. É uma forma de garantir que, na rodada r −k, o Adversário não possa alterar muito a probabilidade de que um usuário honesto se torna o líder da rodada r. Na verdade, não importa quais usuários ele adicione ao sistema nas rodadas r −k até r, eles são inelegíveis para se tornarem líderes em potencial (e a fortiori o líder) da rodada r. Assim, o parâmetro de lookback k é, em última análise, um parâmetro de segurança. (Embora, como veremos na seção 7, também pode ser uma espécie de “parâmetro de conveniência”.) Chaves Efêmeras Embora a execução do nosso protocolo não possa gerar um fork, exceto com probabilidade desprezível, o Adversário poderia gerar uma bifurcação, no bloco r, após o legítimo o bloco r foi gerado. Grosso modo, uma vez gerado Br, o Adversário sabe quem são os verificadores de cada etapa. da rodada r são. Assim, ele poderia corromper todos eles e obrigá-los a certificar um novo bloco f Ir. Como esse bloco falso pode ser propagado somente após o bloco legítimo, os usuários que foram prestar atenção não seria enganado.13 No entanto, f Br estaria sintaticamente correto e nós deseja evitar que seja fabricado. Fazemos isso por meio de uma nova regra. Essencialmente, os membros do conjunto verificador SV r,s de uma etapa s da rodada r use chaves públicas efêmeras pkr,s eu para assinar digitalmente suas mensagens. Essas chaves são de uso único e suas chaves secretas correspondentes skr,s eu são destruídos uma vez usados. Dessa forma, se um verificador for corrompido mais tarde, o Adversário não pode forçá-lo a assinar qualquer outra coisa que ele não tenha assinado originalmente. Naturalmente, devemos garantir que seja impossível para o Adversário calcular uma nova chave g pr,s eu e convencer um usuário honesto de que é a chave efêmera correta do verificador i \(\in\)SV r,s para usar na etapa s. 4.2 Resumo comum de notações, noções e parâmetros Notações • r \(\geq\)0: o número da rodada atual. • s \(\geq\)1: o número do passo atual na rodada r. • Br: bloco gerado na rodada r. • PKr: o conjunto de chaves públicas no final da rodada r −1 e no início da rodada r. • Sr: o status do sistema no final da rodada r −1 e no início da rodada r.14 • PAY r: o payset contido no Br. • \(\ell\)r: líder da rodada r. \(\ell\)r escolhe o payset PAY r da rodada r (e determina o próximo Qr). • Qr: a semente da rodada r, uma quantidade (ou seja, string binária) que é gerada no final da rodada r e é usado para escolher verificadores para a rodada r + 1. Qr é independente dos paysets nos blocos e não pode ser manipulado por \(\ell\)r. 13Considere corromper o âncora de uma grande rede de TV e produzir e transmitir hoje um noticiário mostrando a secretária Clinton vencendo a última eleição presidencial. A maioria de nós reconheceria isso como uma farsa. Mas alguém que sai do coma pode ser enganado. 14Num sistema que não é síncrono, a noção de “fim da ronda r −1” e “início da ronda r” precisam ser cuidadosamente definidos. Matematicamente, PKr e Sr são calculados a partir do status inicial S0 e dos blocos B1, . . . , Br−1.• SV r,s: o conjunto de verificadores escolhidos para a etapa s da rodada r. • SV r: o conjunto de verificadores escolhidos para a rodada r, SV r = \(\cup\)s\(\geq\)1SV r,s. • MSV r,s e HSV r,s: respectivamente, o conjunto de verificadores maliciosos e o conjunto de verificadores honestos em SV r,s. MSV r,s \(\cup\)HSV r,s = SV r,s e MSV r,s ∩HSV r,s = \(\emptyset\). • n1 \(\in\)Z+ e n \(\in\)Z+: respectivamente, os números esperados de potenciais líderes em cada SV r,1, e os números esperados de verificadores em cada SV r,s, para s > 1. Observe que n1 << n, já que precisamos de pelo menos um membro honesto e honesto em SV r,1, mas pelo menos uma maioria de membros honestos em cada SV r,s para s > 1. • h \(\in\)(0, 1): uma constante maior que 2/3. h é o índice de honestidade no sistema. Ou seja, o fração de usuários honestos ou dinheiro honesto, dependendo da suposição utilizada, em cada PKr é pelo menos h. • H: uma função criptográfica hash, modelada como uma oracle aleatória. • \(\bot\): Uma string especial do mesmo comprimento que a saída de H. • F \(\in\)(0, 1): parâmetro que especifica a probabilidade de erro permitida. Uma probabilidade \(\leq\)F é considerada “desprezível”, e uma probabilidade \(\geq\)1 −F é considerada “esmagadora”. • ph \(\in\)(0, 1): a probabilidade de o líder de uma rodada r, \(\ell\)r, ser honesto. Idealmente ph = h. Com a existência do Adversário, o valor de ph será determinado na análise. • k \(\in\)Z+: o parâmetro de retrospectiva. Ou seja, a rodada r −k é onde os verificadores da rodada r estão escolhido entre —ou seja, SV r \(\subseteq\)PKr−k.15 • p1 \(\in\)(0, 1): para o primeiro passo da rodada r, um usuário da rodada r −k é escolhido para estar em SV r,1 com probabilidade p1 \(\triangleq\) n1 |P Kr−k|. • p \(\in\)(0, 1): para cada passo s > 1 da rodada r, um usuário da rodada r −k é escolhido para estar em SV r,s com probabilidade p \(\triangleq\) n |P Kr−k|. • CERT r: o certificado para Br. É um conjunto de assinaturas tH de H(Br) de verificadores apropriados em rodada R. • Br \(\triangleq\)(Br, CERT r) é um bloco comprovado. Um usuário i conhece Br se possuir (e verificar com sucesso) ambas as partes do bloco provado. Observe que o CERT visto por diferentes usuários pode ser diferente. • τr i: a hora (local) em que um usuário i conhece Br. No protocolo Algorand cada usuário tem seu próprio relógio. Os relógios de diferentes usuários não precisam ser sincronizados, mas devem ter a mesma velocidade. Apenas para efeitos de análise, consideramos um relógio de referência e medimos a velocidade dos jogadores. tempos relacionados em relação a ele. • \(\alpha\)r,s eu e \(\beta\)r,s i : respectivamente o horário (local) em que um usuário i inicia e termina sua execução da Etapa s de rodada R. • Λ e \(\lambda\): essencialmente, os limites superiores para, respectivamente, o tempo necessário para executar a Etapa 1 e o tempo necessário para qualquer outra etapa do protocolo Algorand. O parâmetro Λ limita superiormente o tempo para propagar um único bloco de 1 MB. (Em nossa notação, Λ = \(\lambda\) \(\rho\),1MB. Lembrando nossa notação, que definimos \(\rho\) = 1 para simplificar, e que os blocos são escolhido para ter no máximo 1 MB, temos Λ = \(\lambda\)1,1,1MB.) 15A rigor, “r −k” deveria ser “max{0, r −k}”.O parâmetro \(\lambda\) limita o tempo para propagar uma pequena mensagem por verificador em uma Etapa s > 1. (Usando, como em Bitcoin, assinaturas de curvas elípticas com chaves de 32B, uma mensagem do verificador tem 200B de comprimento. Assim, em nossa notação, \(\lambda\) = \(\lambda\)n,\(\rho\),200B.) Assumimos que Λ = O(\(\lambda\)). Noções • Seleção do verificador. Para cada rodada r e etapa s > 1, SV r,s \(\triangleq\){i \(\in\)PKr−k : .H(SIGi(r, s, Qr−1)) \(\leq\)p}. Cada o usuário i \(\in\)PKr−k calcula privadamente sua assinatura usando sua chave de longo prazo e decide se i \(\in\)SV r,s ou não. Se i \(\in\)SV r,s, então SIGi(r, s, Qr−1) é a credencial de i(r, s), denotada de forma compacta por \(\sigma\)r,s eu. Para a primeira etapa da rodada r, SV r,1 e \(\sigma\)r,1 eu são definidos de forma semelhante, com p substituído por p1. O verificadores em SV r,1 são líderes em potencial. • Seleção de líderes. O usuário i \(\in\)SV r,1 é o líder da rodada r, denotado por \(\ell\)r, se H(\(\sigma\)r,1 eu) \(\leq\)H(\(\sigma\)r,1 j) para todo potencial líderes j \(\in\)SV r,1. Sempre que os hashes das credenciais de dois jogadores são comparados, no improvável Em caso de empate, o protocolo sempre rompe o vínculo lexicograficamente de acordo com o (público de longo prazo chaves dos) líderes potenciais. Por definição, o valor hash da credencial do jogador \(\ell\)r também é o menor entre todos os usuários em PKr-k. Observe que um líder potencial não pode decidir privadamente se ele é o líder ou não, sem ver as credenciais dos outros líderes potenciais. Como os valores de hash são uniformes aleatoriamente, quando SV r,1 não é vazio, \(\ell\)r sempre existe e é honesto com probabilidade pelo menos h. O parâmetro n1 é grande o suficiente para garantir que cada SV r,1 não é vazio com probabilidade esmagadora. • Estrutura de bloco. Um bloco não vazio tem a forma Br = (r, PAY r, SIG\(\ell\)r(Qr−1), H(Br−1)), e um bloco vazio é da forma Br ǫ = (r, \(\emptyset\), Qr−1, H(Br−1)). Observe que um bloco não vazio ainda pode conter um conjunto de pagamentos PAY r vazio, se nenhum pagamento ocorrer em nesta rodada ou se o líder for malicioso. No entanto, um bloco não vazio implica que a identidade de \(\ell\)r, sua credencial \(\sigma\)r,1 \(\ell\)r e SIG\(\ell\)r(Qr−1) foram todos revelados em tempo hábil. O protocolo garante que, se o líder for honesto, então o bloco não estará vazio com uma probabilidade esmagadora. • Semente Qr. Se Br não for vazio, então Qr \(\triangleq\)H(SIG\(\ell\)r(Qr−1), r), caso contrário Qr \(\triangleq\)H(Qr−1, r). Parâmetros • Relações entre vários parâmetros. — Os verificadores e potenciais líderes da rodada r são selecionados entre os usuários do PKr−k, onde k é escolhido de modo que o Adversário não possa prever Qr−1 na rodada r −k −1 com probabilidade melhor que F: caso contrário, ele poderá introduzir usuários maliciosos para a rodada r −k, todos os quais serão potenciais líderes/verificadores na rodada r, tendo sucesso em

ter um líder malicioso ou uma maioria maliciosa em SV r,s para algumas etapas desejadas por ele. — Para a Etapa 1 de cada rodada r, n1 é escolhido de modo que com probabilidade esmagadora, SV r,1 ̸= \(\emptyset\). • Exemplos de escolhas de parâmetros importantes. — As saídas de H têm 256 bits. — h = 80%, n1 = 35. — Λ = 1 minuto e \(\lambda\) = 10 segundos. • Inicialização do protocolo. O protocolo começa no tempo 0 com r = 0. Como não existe “B−1” ou “CERT −1”, sintaticamente B−1 é um parâmetro público com seu terceiro componente especificando Q−1, e todos os usuários conheça B−1 no tempo 0.

Algorand ′

1 Nesta seção, construímos uma versão de Algorand ′ trabalhando sob a seguinte suposição. Suposição da maioria honesta dos usuários: Mais de 2/3 dos usuários em cada PKr são honestos. Na Seção 8, mostramos como substituir a suposição acima pela desejada Maioria Honesta de Suposição de dinheiro. 5.1 Notações e parâmetros adicionais Notações • m \(\in\)Z+: número máximo de passos no protocolo BA binário, múltiplo de 3. • Lr \(\leq\)m/3: uma variável aleatória que representa o número de tentativas de Bernoulli necessárias para ver um 1, quando cada tentativa é 1 com probabilidade ph 2 e há no máximo m/3 tentativas. Se todas as tentativas falharem então Lr\(\triangleq\)m/3. Lr será usado para limitar o tempo necessário para gerar o bloco Br. • tH = 2n 3 + 1: o número de assinaturas necessárias nas condições finais do protocolo. • CERT r: o certificado para Br. É um conjunto de assinaturas tH de H(Br) de verificadores apropriados em rodada R. Parâmetros • Relações entre vários parâmetros. — Para cada passo s > 1 da rodada r, n é escolhido de modo que, com probabilidade esmagadora, |HSV r,s| > 2|MSV r,s| e |HSV r,s| + 4|MSV r,s| <2n. Quanto mais próximo de 1 for o valor de h, menor será n. Em particular, usamos (variantes de) Chernoffbounds para garantir que as condições desejadas se mantenham com uma probabilidade esmagadora. — m é escolhido de modo que Lr < m/3 com probabilidade esmagadora. • Exemplos de escolhas de parâmetros importantes. — F = 10−12. — n \(\approx\)1500, k = 40 e m = 180.5.2 Implementando chaves efêmeras em Algorand ′ 1 Como já mencionado, desejamos que um verificador i \(\in\)SV r,s assine digitalmente sua mensagem mr,s eu de passo s na rodada r, relativo a uma chave pública efêmera pkr,s i , usando uma chave secreta efêmera skr,s eu isso ele destrói prontamente após o uso. Portanto, precisamos de um método eficiente para garantir que cada usuário possa verifique se pkr,s eu é de fato a chave a ser usada para verificar a assinatura do senhor,s eu. Fazemo-lo através de um (da melhor forma do nosso conhecimento) novo uso de esquemas de assinatura baseados em identidade. Em um nível elevado, em tal esquema, uma autoridade central A gera uma chave mestra pública, PMK, e uma chave mestra secreta correspondente, SMK. Dada a identidade, U, de um jogador U, A calcula, via SMK, um skU de chave de assinatura secreta relativo à chave pública U, e fornece skU de forma privada para U. (Na verdade, em um esquema de assinatura digital baseado em identidade, a chave pública de um usuário U é o próprio U!) Desta forma, se A destruir o SMK após calcular as chaves secretas dos usuários que ele deseja habilitar para produz assinaturas digitais e não mantém nenhuma chave secreta computada, então U é o único que pode assinar digitalmente mensagens relativas à chave pública U. Assim, qualquer pessoa que saiba o “nome de U”, conhece automaticamente a chave pública de U e, portanto, pode verificar as assinaturas de U (possivelmente usando também o chave mestra pública PMK). Em nossa aplicação, a autoridade A é o usuário i, e o conjunto de todos os usuários possíveis U coincide com o par de passos redondos (r, s) em —digamos— S = {i}\(\times\){r′, . . . , r′ +106}\(\times\){1, . . . , m+3}, onde r′ é um dado rodada e m + 3 o limite superior para o número de etapas que podem ocorrer dentro de uma rodada. Isto caminho, pkr,s eu \(\triangleq\)(i, r, s), para que todos vejam a assinatura de i SIGr,s pkr,s eu (sr.,s i) pode, com esmagadora probabilidade, verifique-a imediatamente para o primeiro milhão de rodadas r após r′. Em outras palavras, primeiro gero PMK e SMK. Em seguida, ele divulga que PMK é o mestre do i chave pública para qualquer rodada r \(\in\)[r′, r′ + 106], e usa SMK para produzir e armazenar o segredo de forma privada chave skr,s eu para cada triplo (i, r, s) \(\in\)S. Feito isso, ele destrói SMK. Se ele determinar que não está parte de SV r,s, então posso deixar skr,s eu sozinho (já que o protocolo não exige que ele autentique qualquer mensagem na Etapa s da rodada r). Caso contrário, primeiro uso skr,s eu para assinar digitalmente sua mensagem, Sr. eu, e então destrói skr,s eu. Observe que posso divulgar sua primeira chave mestra pública quando ele entrar no sistema pela primeira vez. Isto é, o mesmo pagamento \(\wp\)que traz i para o sistema (em uma rodada r′ ou em uma rodada próxima de r′), também pode especifique, a pedido de i, que a chave mestra pública de i para qualquer rodada r \(\in\)[r′, r′ + 106] é PMK - por exemplo, por incluindo um par da forma (PMK, [r′, r′ + 106]). Observe também que, como m + 3 é o número máximo de passos em uma rodada, assumindo que uma rodada leva um minuto, o estoque de chaves efêmeras assim produzido durará quase dois anos. Ao mesmo tempo, essas chaves secretas efêmeras não levarão muito tempo para serem produzidas. Usando uma curva elíptica baseada sistema com chaves de 32B, cada chave secreta é computada em alguns microssegundos. Assim, se m + 3 = 180, então, todas as 180 milhões de chaves secretas podem ser computadas em menos de uma hora. Quando a rodada atual estiver se aproximando de r′ + 106, para lidar com o próximo milhão de rodadas, i gera um novo par (PMK′, SMK′) e informa qual é seu próximo estoque de chaves efêmeras —por exemplo— fazer com que SIGi(PMK′, [r′ + 106 + 1, r′ + 2 \(\cdot\) 106 + 1]) insira um novo bloco, seja como um “transação” separada ou como alguma informação adicional que faz parte de um pagamento. Ao fazer isso, i informa a todos que devem usar PMK′ para verificar as assinaturas efêmeras de i no próximo milhões de rodadas. E assim por diante. (Observe que, seguindo esta abordagem básica, outras formas de implementar chaves efêmeras sem o uso de assinaturas baseadas em identidade é certamente possível. Por exemplo, via Merkle trees.16) 16Neste método, i gera um par de chaves públicas-secretas (pkr,s eu, skr,s eu ) para cada par de etapas redondas (r, s) em —digamos—Outras maneiras de implementar chaves efêmeras são certamente possíveis — por exemplo, via Merkle trees. 5.3 Correspondendo às etapas de Algorand ′ 1 com os de BA⋆ Como dissemos, uma rodada em Algorand ′ 1 tem no máximo m + 3 passos. Passo 1. Nesta etapa, cada líder potencial i calcula e propaga seu bloco candidato Br eu, juntamente com sua própria credencial, \(\sigma\)r,1 eu. Lembre-se de que esta credencial identifica explicitamente i. Isto é assim porque \(\sigma\)r,1 eu \(\triangleq\)SIGi(r, 1, Qr−1). O verificador potencial i também propaga, como parte de sua mensagem, sua assinatura digital própria de H(Br eu). Não se tratando de um pagamento ou de uma credencial, esta assinatura de i é relativa ao seu efêmero público chave pkr,1 i: isto é, ele propaga sigpkr,1 eu (H(Br eu)). Dadas as nossas convenções, em vez de propagar o Br eu e sigpkr,1 eu (H(Br i)), ele poderia ter SIGpkr propagado,1 eu (H(Br eu)). No entanto, na nossa análise, precisamos de ter acesso explícito a sigpkr,1 eu (H(Br eu)). Etapa 2. Nesta etapa, cada verificador i define \(\ell\)r eu serei o líder em potencial cuja credencial hashed é o menor e Br i será o bloco proposto por \(\ell\)r eu. Como, por uma questão de eficiência, desejar concordar com H(Br), em vez de diretamente com Br, i propaga a mensagem que ele teria propagado na primeira etapa de BA⋆com valor inicial v′ eu = H(Br eu). Ou seja, ele propaga v′ eu, depois de assiná-lo efêmeramente, é claro. (Nomeadamente, depois de assiná-lo relativamente ao direito efémero chave pública, que neste caso é pkr,2 i.) Claro, também transmito sua própria credencial. Como a primeira etapa de BA⋆consiste na primeira etapa do protocolo de consenso graduado GC, Etapa 2 de Algorand ′ corresponde ao primeiro passo do GC. Passo 3. Neste passo, cada verificador i \(\in\)SV r,2 executa o segundo passo de BA⋆. Ou seja, ele envia o mesma mensagem que ele teria enviado na segunda etapa do GC. Novamente, a mensagem de i é efêmera assinado e acompanhado da credencial do i. (De agora em diante, deixaremos de dizer que um verificador assina efêmeramente sua mensagem e também propaga sua credencial.) Etapa 4. Nesta etapa, cada verificador i \(\in\)SV r,4 calcula a saída de GC, (vi, gi), e efêmeramente assina e envia a mesma mensagem que teria enviado na terceira etapa do BA⋆, ou seja, no primeiro passo do BBA⋆, com bit inicial 0 se gi = 2, e 1 caso contrário. Etapa s = 5, . . . , m + 2. Tal passo, se alguma vez alcançado, corresponde ao passo s −1 de BA⋆ e, portanto, a etapa s −3 do BBA⋆. Como nosso modelo de propagação é suficientemente assíncrono, devemos levar em conta a possibilidade que, no meio de tal passo s, um verificador i \(\in\)SV r,s é alcançado por informações que o comprovam aquele bloco Br já foi escolhido. Neste caso, i interrompe sua própria execução da rodada r de Algorand ′ e começa a executar suas instruções round-(r + 1). {r', . . . , r′ + 106} \(\times\) {1, . . . , m + 3}. Então ele ordena essas chaves públicas de forma canônica, armazena a j-ésima chave pública digita a j-ésima folha de um Merkle tree e calcula o valor da raiz Ri, que ele divulga. Quando ele quer assinar uma mensagem relativa à chave pkr,s eu , não apenas forneço a assinatura real, mas também o caminho de autenticação para pkr,s eu em relação a Ri. Observe que este caminho de autenticação também prova que pkr,s eu é armazenado na j-ésima folha. O resto do detalhes podem ser facilmente preenchidos.Assim, as instruções de um verificador i \(\in\)SV r,s, além das instruções correspondentes para a Etapa s −3 do BBA⋆, inclui a verificação se a execução do BBA⋆ foi interrompida em um momento anterior Passo s′. Como o BBA⋆ só pode parar em uma etapa fixada em moeda em 0 ou em uma etapa fixada em moeda em 1, o instruções distinguem se A (Condição Final 0): s′ −2 ≡0 mod 3, ou B (Condição Final 1): s′ −2 ≡1 mod 3. Na verdade, no caso A, o bloco Br não está vazio e, portanto, são necessárias instruções adicionais para garantir que i reconstrói Br adequadamente, juntamente com seu certificado adequado CERT r. No caso B, o bloco Br está vazio e, portanto, i é instruído a definir Br = Br \(\varepsilon\) = (r, \(\emptyset\), H(Qr−1, r), H(Br−1)), e para calcular CERT r. Se, durante a execução do passo s, i não vir nenhuma evidência de que o bloco Br já tenha foi gerado, então ele envia a mesma mensagem que teria enviado na etapa s −3 do BBA⋆. Passo m + 3. Se, durante o passo m + 3, i \(\in\)SV r,m+3 vê que o bloco Br já foi gerado em uma etapa anterior s′, então ele prossegue conforme explicado acima. Caso contrário, em vez de enviar a mesma mensagem que ele teria enviado na etapa m do BBA⋆, i é instruído, com base nas informações em sua posse, a calcular Br e seu correspondente certificado CERT r. Lembre-se, de fato, que limitamos em m + 3 o número total de etapas de uma rodada. 5.4 O protocolo real Lembre-se que, em cada passo s de uma rodada r, um verificador i \(\in\)SV r,s usa seu par de chaves secretas públicas de longo prazo para produzir sua credencial, \(\sigma\)r,s eu \(\triangleq\)SIGi(r, s, Qr−1), bem como SIGi Qr-1 no caso s = 1. Verificador i usa sua chave secreta efêmera skr,s eu para assinar sua mensagem (r, s) mr,s eu. Por simplicidade, quando r e s são claro, escrevemos esigi(x) em vez de sigpkr,s i (x) para denotar a assinatura efêmera adequada de um valor de i x na etapa s da rodada r e escreva ESIGi(x) em vez de SIGpkr,s i (x) para denotar (i, x, esigi (x)). Etapa 1: bloquear proposta Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 1 da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir do terceiro componente de Br−1 e verifica se i \(\in\)SV r,1 ou não. • Se i /\(\in\)SV r,1, então i interrompe imediatamente a sua própria execução do Passo 1. • Se i \(\in\)SV r,1, ou seja, se i for um líder em potencial, então ele recebe os pagamentos da rodada r que foram foi propagado para ele até agora e calcula um conjunto de pagamento máximo PAY r eu deles. A seguir, ele calcula seu “bloco de candidatos” Br eu = (r, PAGAR r eu, SIGi(Qr−1), H(Br−1)). Finalmente, ele calcula a mensagem senhor,1 eu = (Br eu , esigi(H(Br eu )), \(\sigma\)r,1 i ), destrói sua chave secreta efêmera skr,1 eu, e então propaga senhor,1 eu.Observação. Na prática, para encurtar a execução global do Passo 1, é importante que o (r, 1)- as mensagens são propagadas seletivamente. Ou seja, para cada usuário i no sistema, para o primeiro (r, 1)- mensagem que ele recebe e verifica com sucesso,17 o jogador i a propaga normalmente. Para todos os outras mensagens (r, 1) que o jogador i recebe e verifica com sucesso, ele as propaga apenas se o hash o valor da credencial que contém é o menor entre os valores hash das credenciais contidas em todas as mensagens (r, 1) que ele recebeu e verificou com sucesso até agora. Além disso, como sugerido por Georgios Vlachos, é útil que cada líder potencial i também propague sua credencial \(\sigma\)r,1 eu separadamente: essas pequenas mensagens viajam mais rápido que os blocos, garantem a propagação oportuna do mr,1 j's onde as credenciais contidas têm valores hash pequenos, enquanto fazem aquelas com valores hash grandes desaparecer rapidamente. Etapa 2: A primeira etapa do GC do protocolo de consenso graduado Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 2 da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir do terceiro componente de Br−1 e verifica se i \(\in\)SV r,2 ou não. • Se i /\(\in\)SV r,2 então i interrompe imediatamente a sua própria execução do Passo 2. • Se i \(\in\)SV r,2, então depois de esperar um período de tempo t2 \(\triangleq\) \(\lambda\) + Λ, i age da seguinte forma. 1. Ele encontra o usuário \(\ell\) tal que H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j ) para todas as credenciais \(\sigma\)r,1 j que fazem parte as mensagens (r, 1) verificadas com sucesso que ele recebeu até agora.a 2. Se ele recebeu de \(\ell\) uma mensagem válida mr,1 \(\ell\) = (Br \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),b então eu defino v' eu \(\triangleq\)H(Br \(\ell\)); caso contrário, eu defino v′ eu \(\triangleq\) \(\bot\). 3. eu calculo a mensagem senhor,2 eu \(\triangleq\)(ESIGi(v′ eu), \(\sigma\)r,2 i ),c destrói sua chave secreta efêmera skr,2 i , e então propaga mr,2 eu. aEssencialmente, o usuário i decide em particular que o líder da rodada r é o usuário \(\ell\). bNovamente, as assinaturas do jogador \(\ell\) e os hashes foram todos verificados com sucesso e PAGUE r \(\ell\)no Brasil \(\ell\)é um conjunto de pagamento válido para rodada r - embora eu não verifique se PAY r \(\ell\)é máximo para \(\ell\)ou não. cA mensagem senhor,2 eu sinaliza que o jogador i considera v′ i é o hash do próximo bloco, ou considera o próximo bloco fique vazio. 17Ou seja, todas as assinaturas estão corretas e tanto o bloco quanto seu hash são válidos —embora eu não verifique se o conjunto de pagamentos incluído é máximo para o seu proponente ou não.

Etapa 3: A segunda etapa do GC Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 3 da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir do terceiro componente de Br−1 e verifica se i \(\in\)SV r,3 ou não. • Se i /\(\in\)SV r,3, então i interrompe imediatamente a sua própria execução do Passo 3. • Se i \(\in\)SV r,3, então depois de esperar um período de tempo t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ, i age da seguinte forma. 1. Se existe um valor v′ ̸= \(\bot\)tal que, entre todas as mensagens válidas mr,2 j ele recebeu, mais de 2/3 deles são da forma (ESIGj(v′), \(\sigma\)r,2 j ), sem qualquer contradição,a então ele calcula a mensagem mr,3 eu \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 eu). Caso contrário, ele calcula mr,3 eu \(\triangleq\) (ESIGi(\(\bot\)), \(\sigma\)r,3 eu). 2. eu destruo sua chave secreta efêmera skr,3 i , e então propaga mr,3 eu. aOu seja, ele não recebeu duas mensagens válidas contendo ESIGj(v′) e um ESIGj(v′′) diferente respectivamente, de um jogador j. Aqui e daqui em diante, exceto nas Condições Finais definidas posteriormente, sempre que um jogador honesto deseja mensagens de um determinado formato, mensagens contraditórias nunca são contadas ou consideradas válidas.Etapa 4: Resultado do GC e a primeira etapa do BBA⋆ Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 4 da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir do terceiro componente de Br−1 e verifica se i \(\in\)SV r,4 ou não. • Se i /\(\in\)SV r,4, então i his interrompe imediatamente a execução do Passo 4. • Se i \(\in\)SV r,4, então depois de esperar um período de tempo t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ, i age da seguinte forma. 1. Ele calcula vi e gi, a saída do GC, como segue. (a) Se existe um valor v′ ̸= \(\bot\)tal que, entre todas as mensagens válidas mr,3 j ele tem recebidos, mais de 2/3 deles são da forma (ESIGj(v′), \(\sigma\)r,3 j ), então ele define vi \(\triangleq\)v′ e gi \(\triangleq\)2. (b) Caso contrário, se existir um valor v′ ̸= \(\bot\)tal que, entre todas as mensagens válidas senhor,3 j ele recebeu, mais de 1/3 deles são da forma (ESIGj(v′), \(\sigma\)r,3 j), então ele define vi \(\triangleq\)v′ e gi \(\triangleq\)1.a (c) Caso contrário, ele define vi \(\triangleq\)H(Br ǫ ) e gi \(\triangleq\)0. 2. Ele calcula bi, a entrada de BBA⋆, como segue: bi \(\triangleq\)0 se gi = 2, e bi \(\triangleq\)1 caso contrário. 3. Ele calcula a mensagem mr,4 eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), destrói seu efêmero chave secreta skr,4 i , e então propaga mr,4 eu. aPode-se provar que v′ no caso (b), se existir, deve ser único.

Etapa s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: Uma etapa de BBA⋆ com moeda fixada em 0 Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia suas próprias etapas da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir da terceira componente de Br−1 e verifica se i \(\in\)SV r,s. • Se i /\(\in\)SV r,s, então i interrompe imediatamente a sua própria execução do Passo s. • Se i \(\in\)SV r,s então ele age da seguinte forma. – Ele espera até que um período de tempo ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ tenha passado. – Condição Final 0: Se, durante essa espera e em qualquer momento, existir uma string v ̸= \(\bot\)e um passo s′ tal que (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 - isto é, a etapa s′ é uma etapa fixada em moeda em 0, (b) recebi pelo menos tH = 2n 3 + 1 mensagens válidas mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),a e (c) recebi uma mensagem válida senhor,1 j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) com v = H(Br j ), então, eu interrompo sua própria execução do Passo s (e de fato da rodada r) imediatamente, sem propagar qualquer coisa; define Br = Br j; e define seu próprio CERT r como o conjunto de mensagens senhor,s′−1 j da subetapa (b).b – Condição Final 1: Se, durante essa espera e em qualquer momento, existir um passo s′ tal que (a') 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 - isto é, a etapa s′ é uma etapa fixada em moeda para 1, e (b') i recebeu pelo menos tH mensagens válidas mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),c então, eu interrompo sua própria execução do Passo s (e de fato da rodada r) imediatamente, sem propagar qualquer coisa; define Br = Br ǫ; e define seu próprio CERT r como o conjunto de mensagens senhor,s′−1 j da subetapa (b'). – Caso contrário, ao final da espera, o usuário i faz o seguinte. Ele define vi como o voto majoritário dos vj nos segundos componentes de todos os votos válidos. senhor,s−1 j é o que ele recebeu. Ele calcula bi da seguinte maneira. Se mais de 2/3 de todos os mr,s−1 válidos j que ele recebeu são da forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele define bi \(\triangleq\)0. Caso contrário, se mais de 2/3 de todos os mr,s−1 válidos j que ele recebeu são da forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele define bi \(\triangleq\)1. Caso contrário, ele define bi \(\triangleq\)0. Ele computa a mensagem mr,s eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), destrói seu efêmero chave secreta skr,s i e então propaga mr,s eu. aEssa mensagem do jogador j é contada mesmo que o jogador i também tenha recebido uma mensagem de j assinando por 1. Coisas semelhantes para a Condição Final 1. Conforme mostrado na análise, isso é feito para garantir que todos os usuários honestos saibam Br dentro do tempo \(\lambda\) um do outro. bO usuário i agora conhece Br e seus próprios acabamentos de rodada. Ele ainda ajuda a propagar mensagens como um usuário genérico, mas não inicia nenhuma propagação como um verificador (r, s). Em particular, ele ajudou a propagar todas as mensagens em seu CERT r, o que é suficiente para o nosso protocolo. Observe que ele também deve definir bi \(\triangleq\)0 para o protocolo BA binário, mas bi não é necessário neste caso de qualquer maneira. Coisas semelhantes para todas as instruções futuras. cNeste caso, não importa quais são os vj’s.Etapa s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: Uma etapa de BBA⋆ fixada em moeda para 1 Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia suas próprias etapas da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir do terceiro componente de Br−1 e verifica se i \(\in\)SV r,s ou não. • Se i /\(\in\)SV r,s, então i interrompe imediatamente a sua própria execução do Passo s. • Se i \(\in\)SV r,s então ele faz o seguinte. – Ele espera até que um período de tempo ts \(\triangleq\)(2s −3)\(\lambda\) + Λ tenha passado. – Condição Final 0: As mesmas instruções das etapas Coin-Fixed-To-0. – Condição Final 1: As mesmas instruções das etapas Coin-Fixed-To-0. – Caso contrário, ao final da espera, o usuário i faz o seguinte. Ele define vi como o voto majoritário dos vj nos segundos componentes de todos os votos válidos. senhor,s−1 j é o que ele recebeu. Ele calcula bi da seguinte maneira. Se mais de 2/3 de todos os mr,s−1 válidos j que ele recebeu são da forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele define bi \(\triangleq\)0. Caso contrário, se mais de 2/3 de todos os mr,s−1 válidos j que ele recebeu são da forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele define bi \(\triangleq\)1. Caso contrário, ele define bi \(\triangleq\)1. Ele computa a mensagem mr,s eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), destrói seu efêmero chave secreta skr,s i e então propaga mr,s eu.

Etapa s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Uma etapa de BBA⋆ com moeda genuinamente invertida Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia suas próprias etapas da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir do terceiro componente de Br−1 e verifica se i \(\in\)SV r,s ou não. • Se i /\(\in\)SV r,s, então i interrompe imediatamente a sua própria execução do Passo s. • Se i \(\in\)SV r,s então ele faz o seguinte. – Ele espera até que um período de tempo ts \(\triangleq\)(2s −3)\(\lambda\) + Λ tenha passado. – Condição Final 0: As mesmas instruções das etapas Coin-Fixed-To-0. – Condição Final 1: As mesmas instruções das etapas Coin-Fixed-To-0. – Caso contrário, ao final da espera, o usuário i faz o seguinte. Ele define vi como o voto majoritário dos vj nos segundos componentes de todos os votos válidos. senhor,s−1 j é o que ele recebeu. Ele calcula bi da seguinte maneira. Se mais de 2/3 de todos os mr,s−1 válidos j que ele recebeu são da forma (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele define bi \(\triangleq\)0. Caso contrário, se mais de 2/3 de todos os mr,s−1 válidos j que ele recebeu são da forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele define bi \(\triangleq\)1. Caso contrário, seja SV r,s−1 eu ser o conjunto de (r, s −1)-verificadores dos quais ele recebeu um valor válido mensagem senhor,s-1 j . Ele define bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 eu H(\(\sigma\)r,s−1 j )). Ele computa a mensagem mr,s eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i ), destrói seu efêmero chave secreta skr,s i e então propaga mr,s eu.

Etapa m + 3: A última etapa do BBA⋆a Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa m + 3 da rodada r assim que ele conhece Br−1. • O usuário i calcula Qr−1 a partir do terceiro componente de Br−1 e verifica se i \(\in\)SV r,m+3 ou não. • Se i /\(\in\)SV r,m+3, então i interrompe imediatamente a sua própria execução do Passo m + 3. • Se i \(\in\)SV r,m+3 então ele faz o seguinte. – Ele espera até que um período de tempo tm+3 \(\triangleq\)tm+2 + 2\(\lambda\) = (2m + 3)\(\lambda\) + Λ tenha passado. – Condição Final 0: As mesmas instruções das etapas Coin-Fixed-To-0. – Condição Final 1: As mesmas instruções das etapas Coin-Fixed-To-0. – Caso contrário, ao final da espera, o usuário i faz o seguinte. Ele definei \(\triangleq\)1 e Br \(\triangleq\)Br ǫ. Ele calcula a mensagem mr,m+3 eu = (ESIGi(outi), ESIGi(H(Br)), \(\sigma\)r,m+3 eu ), destrói seu chave secreta efêmera skr,m+3 eu , e então propaga mr,m+3 eu para certificar Br.b aCom probabilidade esmagadora, BBA⋆terminou antes desta etapa e especificamos esta etapa para completude. bUm certificado da Etapa m + 3 não precisa incluir ESIGi(outi). Nós o incluímos apenas por uniformidade: o os certificados agora têm um formato uniforme, independentemente da etapa em que são gerados.Reconstrução do Bloco Round-r por Não-Verificadores Instruções para cada usuário i no sistema: O usuário i inicia sua própria rodada r assim que souber Br−1, e espera pelas informações do bloco como segue. – Se, durante essa espera e em qualquer momento, existir uma string v e um passo s′ tal isso (a) 5 \(\leq\)s′ \(\leq\)m + 3 com s′ −2 ≡0 mod 3, (b) recebi pelo menos tH mensagens válidas mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ) e (c) recebi uma mensagem válida senhor,1 j = (Br j , esigj(H(Br j )), \(\sigma\)r,1 j ) com v = H(Br j ), então, i interrompe imediatamente sua própria execução da rodada r; define Br = Br j; e define seu próprio CERT r ser o conjunto de mensagens mr,s′−1 j do subpasso (b). – Se, durante essa espera e em qualquer momento, existir uma etapa s′ tal que (a') 6 \(\leq\)s′ \(\leq\)m + 3 com s′ −2 ≡1 mod 3, e (b') i recebeu pelo menos tH mensagens válidas mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ), então, i interrompe imediatamente sua própria execução da rodada r; define Br = Br ǫ; e define seu próprio CERT r ser o conjunto de mensagens mr,s′−1 j da subetapa (b'). – Se, durante essa espera e em qualquer momento, recebi pelo menos mensagens válidas senhor,m+3 j = (ESIGj(1), ESIGj(H(Br ǫ )), \(\sigma\)r,m+3 j ), então eu interrompo sua própria execução da rodada r imediatamente, define Br = Br ǫ , e define seu próprio CERT r como o conjunto de mensagens mr,m+3 j por 1 e H(Br ǫ). 5.5 Análise de Algorand ′ 1 Introduzimos as seguintes notações para cada rodada r \(\geq\)0, utilizada na análise. • Seja T r o momento em que o primeiro usuário honesto conhece Br−1. • Seja Ir+1 o intervalo [T r+1, T r+1 + \(\lambda\)]. Observe que T 0 = 0 pela inicialização do protocolo. Para cada s \(\geq\)1 e i \(\in\)SV r,s, lembre-se que ar,s eu e \(\beta\)r,s eu são respectivamente o horário de início e o horário de término da etapa s do jogador i. Além disso, lembre-se que ts = (2s −3)\(\lambda\) + Λ para cada 2 \(\leq\)s \(\leq\)m + 3. Além disso, sejam I0 \(\triangleq\){0} e t1 \(\triangleq\)0. Finalmente, lembre-se que Lr \(\leq\)m/3 é uma variável aleatória que representa o número de tentativas de Bernoulli precisava ver um 1, quando cada tentativa é 1 com probabilidade ph 2 e há no máximo m/3 tentativas. Se tudo as tentativas falham então Lr \(\triangleq\)m/3. Na análise ignoramos o tempo de cálculo, pois é de facto insignificante em relação ao tempo necessário para propagar mensagens. Em qualquer caso, usando \(\lambda\) e Λ ligeiramente maiores, o tempo de cálculo pode ser incorporado diretamente na análise. A maioria das declarações abaixo são sustentadas “com esmagadora probabilidade”, e não podemos enfatizar repetidamente esse fato na análise.5.6 Teorema Principal Teorema 5.1. As seguintes propriedades são válidas com probabilidade esmagadora para cada rodada r \(\geq\)0: 1. Todos os usuários honestos concordam com o mesmo bloco Br. 2. Quando o líder \(\ell\)r é honesto, o bloco Br é gerado por \(\ell\)r, Br contém um conjunto de pagamentos máximo recebido por \(\ell\)r no tempo \(\alpha\)r,1 \(\ell\)r , T r+1 \(\leq\)T r + 8\(\lambda\) + Λ e todos os usuários honestos conhecem Br na época intervalo Ir+1. 3. Quando o líder \(\ell\)r é malicioso, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ e todos os usuários honestos conhecem Br no intervalo de tempo Ir+1. 4. ph = h2(1 + h −h2) para Lr, e o líder \(\ell\)r é honesto com probabilidade pelo menos ph. Antes de provar nosso teorema principal, façamos duas observações. Observações. • Geração de blocos e latência real. O tempo para gerar o bloco Br é definido como T r+1 −T r. Ou seja, é definido como a diferença entre a primeira vez que um usuário honesto aprende Br e a primeira vez que algum usuário honesto aprende Br−1. Quando o líder da rodada é honesto, a Propriedade 2 é nossa o teorema principal garante que o tempo exato para gerar Br é 8\(\lambda\) + Λ tempo, não importa o que o valor preciso de h > 2/3 pode ser. Quando o líder é malicioso, a Propriedade 3 implica que o o tempo esperado para gerar Br é limitado por (12 ph + 10)\(\lambda\) + Λ, novamente não importa a precisão valor de h.18 Entretanto, o tempo esperado para gerar Br depende do valor preciso de h. Na verdade, pela Propriedade 4, ph = h2(1 + h −h2) e o líder é honesto com probabilidade pelo menos ph, portanto E[T r+1 −T r] \(\leq\)h2(1 + h −h2) \(\cdot\) (8\(\lambda\) + Λ) + (1 −h2(1 + h −h2))(( 12 h2(1 + h −h2) + 10)\(\lambda\) + Λ). Por exemplo, se h = 80%, então E[T r+1 −T r] \(\leq\)12,7\(\lambda\) + Λ. • \(\lambda\) versus Λ. Observe que o tamanho das mensagens enviadas pelos verificadores em uma etapa Algorand ′ é dominado pelo comprimento das chaves de assinatura digital, que podem permanecer fixas, mesmo quando o número de usuários é enorme. Observe também que, em qualquer passo s > 1, o mesmo número esperado n de verificadores pode ser usado se o número de usuários for 100 mil, 100 milhões ou 100 milhões. Isso ocorre porque n apenas depende de h e F. Em suma, portanto, salvo uma necessidade repentina de aumentar o comprimento da chave secreta, o valor de \(\lambda\) deve permanecer o mesmo, não importa quão grande seja o número de usuários no futuro previsível. Por outro lado, para qualquer taxa de transação, o número de transações cresce com o número de usuários. Portanto, para processar todas as novas transações em tempo hábil, o tamanho de um bloco deve também cresce com o número de usuários, fazendo com que Λ também cresça. Assim, no longo prazo, deveríamos ter \(\lambda\) << Λ. Conseqüentemente, é apropriado ter um coeficiente maior para \(\lambda\) e, na verdade, um coeficiente de 1 para Λ. Prova do Teorema 5.1. Provamos as Propriedades 1–3 por indução: assumindo que elas são válidas para a rodada r −1 (sem perda de generalidade, eles são válidos automaticamente para “rodada -1” quando r = 0), nós os provamos para rodada R. 18De fato, E[T r+1 −T r] \(\leq\)(6E[Lr] + 10)\(\lambda\) + Λ = (6 \(\cdot\) 2 ph + 10)\(\lambda\) + Λ = ( 12 ph + 10)\(\lambda\) + Λ.Como Br−1 é definido exclusivamente pela hipótese indutiva, o conjunto SV r,s é definido exclusivamente para cada etapa s da rodada r. Pela escolha de n1, SV r,1 ̸= \(\emptyset\)com probabilidade esmagadora. Nós agora enuncie os dois lemas a seguir, provados nas Seções 5.7 e 5.8. Durante toda a indução e em nas provas dos dois lemas, a análise para a rodada 0 é quase a mesma que a etapa indutiva, e destacaremos as diferenças quando elas ocorrerem. Lema 5.2. [Lema da completude] Assumindo que as propriedades 1–3 são válidas para a rodada r−1, quando o líder \(\ell\)r é honesto, com probabilidade esmagadora, • Todos os usuários honestos concordam com o mesmo bloco Br, que é gerado por \(\ell\)r e contém um valor máximo conjunto de pagamentos recebido por \(\ell\)r no tempo \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; e • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ e todos os usuários honestos conhecem Br no intervalo de tempo Ir+1. Lema 5.3. [Lema de Solidez] Assumindo que as Propriedades 1–3 são válidas para a rodada r −1, quando o líder \(\ell\)r é malicioso, com probabilidade esmagadora, todos os usuários honestos concordam com o mesmo bloco Br, T r+1 \(\leq\) T r + (6Lr + 10)\(\lambda\) + Λ e todos os usuários honestos conhecem Br no intervalo de tempo Ir+1. As propriedades 1–3 são válidas aplicando os Lemas 5.2 e 5.3 a r = 0 e à etapa indutiva. Finalmente, reafirmamos a Propriedade 4 como o seguinte lema, provado na Seção 5.9. Lema 5.4. Dadas as propriedades 1–3 para cada rodada antes de r, ph = h2(1 + h −h2) para Lr, e o o líder \(\ell\)r é honesto com probabilidade de pelo menos ph. Combinando os três lemas acima, o Teorema 5.1 é válido. ■ O lema abaixo afirma várias propriedades importantes sobre o round r dado o indutivo hipótese, e será usada nas provas dos três lemas acima. Lema 5.5. Suponha que as propriedades 1–3 sejam válidas para a rodada r −1. Para cada etapa s \(\geq\)1 da rodada r e cada verificador honesto i \(\in\)HSV r,s, temos que (a) \(\alpha\)r,s eu \(\in\)Ir; (b) se o jogador i esperou um período de tempo ts, então \(\beta\)r,s eu \(\in\)[T r + ts, T r + \(\lambda\) + ts] para r > 0 e \(\beta\)r,s eu = ts para r = 0; e (c) se o jogador i esperou um período de tempo ts, então no tempo \(\beta\)r,s eu, ele recebeu todas as mensagens enviado por todos os verificadores honestos j \(\in\)HSV r,s′ para todas as etapas s′ < s. Além disso, para cada passo s \(\geq\)3, temos que (d) não existem dois jogadores diferentes i, i′ \(\in\)SV r,s e dois valores diferentes v, v′ do mesmo duração, tal que ambos os jogadores esperaram um período de tempo ts, mais de 2/3 de todos os mensagens válidas senhor,s−1 j jogador que recebo assinou por v, e mais de 2/3 de todos os válidos mensagens senhor,s-1 j o jogador que i′ recebe assinou por v′. Prova. A propriedade (a) segue diretamente da hipótese indutiva, pois o jogador i conhece Br−1 no intervalo de tempo Ir e inicia seus próprios passos imediatamente. A propriedade (b) segue diretamente de (a): uma vez que jogador i esperou um certo tempo ts antes de agir, \(\beta\)r,s eu = \(\alpha\)r,s eu + ts. Observe que \(\alpha\)r,s eu = 0 para r = 0. Provamos agora a Propriedade (c). Se s = 2, então pela Propriedade (b), para todos os verificadores j \(\in\)HSV r,1 temos \(\beta\)r,s eu = \(\alpha\)r,s eu + ts \(\geq\)T r + ts = T r + \(\lambda\) + Λ \(\geq\) \(\beta\)r,1 j +Λ.Como cada verificador j \(\in\)HSV r,1 envia sua mensagem no tempo \(\beta\)r,1 j e a mensagem chega a todos os honestos usuários em no máximo Λ tempo, por tempo \(\beta\)r,s eu jogador i recebeu as mensagens enviadas por todos os verificadores em HSV r,1 conforme desejado. Se s > 2, então ts = ts−1 + 2\(\lambda\). Pela Propriedade (b), para todas as etapas s′ < s e todos os verificadores j \(\in\)HSV r,s′, \(\beta\)r,s eu = \(\alpha\)r,s eu + ts \(\geq\)T r + ts = T r + ts−1 + 2\(\lambda\) \(\geq\)T r + ts′ + 2\(\lambda\) = T r + \(\lambda\) + ts′ + \(\lambda\) \(\geq\) \(\beta\)r,s′ j +\(\lambda\). Como cada verificador j \(\in\)HSV r,s′ envia sua mensagem no tempo \(\beta\)r,s′ j e a mensagem chega a todos os honestos usuários em no máximo \(\lambda\) tempo, por tempo \(\beta\)r,s eu jogador i recebeu todas as mensagens enviadas por todos os verificadores honestos em HSV r,s′ para todo s′ < s. Assim, a Propriedade (c) é válida. Finalmente, provamos a Propriedade (d). Observe que os verificadores j \(\in\)SV r,s−1 sinalizam no máximo duas coisas em Etapa s −1 usando suas chaves secretas efêmeras: um valor vj do mesmo comprimento que a saída do Função hash, e também um bit bj \(\in\){0, 1} se s −1 \(\geq\)4. É por isso que no enunciado do lema exigimos que v e v′ tenham o mesmo comprimento: muitos verificadores podem ter assinado um valor hash v e um bit b, portanto, ambos ultrapassam o limite de 2/3. Suponha, por contradição, que existam os verificadores desejados i, i′ e os valores v, v′. Observe que alguns verificadores maliciosos no MSV r,s−1 podem ter assinado v e v′, mas cada um deles honesto O verificador em HSV r,s−1 assinou no máximo um deles. Pela propriedade (c), tanto i quanto i′ receberam todas as mensagens enviadas por todos os verificadores honestos em HSV r,s−1. Seja HSV r,s−1(v) o conjunto de verificadores honestos (r, s −1) que assinaram v, MSV r,s−1 eu o conjunto de verificadores maliciosos (r, s −1) dos quais i recebeu uma mensagem válida, e MSV r,s−1 eu (v) o subconjunto de MSV r,s−1 eu de quem recebi uma assinatura de mensagem válida v. Pelos requisitos para eu e v, temos razão \(\triangleq\)|HSV r,s−1(v)| + |MSV r,s−1 eu (v)| |HSV r,s−1| + |MSV r,s−1 eu |

2 3. (1) Nós primeiro mostramos |MSV r,s−1 eu (v)| \(\leq\)|HSV r,s−1(v)|. (2) Supondo o contrário, pelas relações entre os parâmetros, com probabilidade esmagadora |HSV r,s−1| > 2|MSV r,s−1| \(\geq\)2|MSV r,s−1 eu |, assim razão < |HSV r,s−1(v)| + |MSV r,s−1 eu (v)| 3|MSV r,s−1 eu | < 2|MSV r,s−1 eu (v)| 3|MSV r,s−1 eu | \(\leq\)2 3, contradizendo a desigualdade 1. A seguir, pela Desigualdade 1 temos 2|HSV r,s−1| + 2|MSV r,s−1 eu | < 3|HSV r,s−1(v)| + 3|MSV r,s−1 eu (v)| \(\leq\) 3|HSV r,s−1(v)| + 2|MSV r,s−1 eu | + |MSV r,s−1 eu (v)|. Combinando com a Desigualdade 2, 2|HSV r,s−1| < 3|HSV r,s−1(v)| + |MSV r,s−1 eu (v)| \(\leq\)4|HSV r,s−1(v)|, o que implica |HSV r,s−1(v)| > 1 2|HSV r,s−1|.Da mesma forma, pelos requisitos para i′ e v′, temos |HSV r,s−1(v′)| > 1 2|HSV r,s−1|. Como um verificador honesto j \(\in\)HSV r,s−1 destrói sua chave secreta efêmera skr,s−1 j antes de propagar sua mensagem, o Adversário não pode falsificar a assinatura de j para um valor que j não assinou, após aprendendo que j é um verificador. Assim, as duas desigualdades acima implicam |HSV r,s−1| \(\geq\)|HSV r,s−1(v)| + |HSV r,s−1(v′)| > |HSV r,s−1|, uma contradição. Consequentemente, os desejados i, i′, v, v′ não existem, e A propriedade (d) é válida. ■ 5.7 O lema da completude Lema 5.2. [Lema da completude, reformulado] Assumindo que as propriedades 1–3 são válidas para a rodada r−1, quando o líder \(\ell\)r é honesto, com probabilidade esmagadora, • Todos os usuários honestos concordam com o mesmo bloco Br, que é gerado por \(\ell\)r e contém um valor máximo conjunto de pagamentos recebido por \(\ell\)r no tempo \(\alpha\)r,1 \(\ell\)r \(\in\)Ir; e • T r+1 \(\leq\)T r + 8\(\lambda\) + Λ e todos os usuários honestos conhecem Br no intervalo de tempo Ir+1. Prova. Pela hipótese indutiva e Lema 5.5, para cada etapa s e verificador i \(\in\)HSV r,s, ar,s eu \(\in\)Ir. Abaixo analisamos o protocolo passo a passo. Etapa 1. Por definição, todo verificador honesto i \(\in\)HSV r,1 propaga a mensagem desejada mr,1 eu em tempo \(\beta\)r,1 eu = \(\alpha\)r,1 eu, onde senhor,1 eu = (Br eu , esigi(H(Br eu )), \(\sigma\)r,1 eu), irmão eu = (r, PAGAR r eu, SIGi(Qr−1), H(Br−1)), e PAGUE r i é um conjunto de pagamentos máximo entre todos os pagamentos que vi até o momento \(\alpha\)r,1 eu. Etapa 2. Fixe arbitrariamente um verificador honesto i \(\in\)HSV r,2. Pelo Lema 5.5, quando o jogador i termina esperando no tempo \(\beta\)r,2 eu = \(\alpha\)r,2 eu + t2, ele recebeu todas as mensagens enviadas pelos verificadores em HSV r,1, incluindo senhor,1 \(\ell\)r. Pela definição de \(\ell\)r, não existe outro jogador em PKr−k cuja credencial seja hash valor é menor que H(\(\sigma\)r,1 \(\ell\)r). Claro, o Adversário pode corromper \(\ell\)r depois de ver que H(\(\sigma\)r,1 \(\ell\)r) é muito pequeno, mas a essa altura o jogador \(\ell\)r destruiu sua chave efêmera e a mensagem mr,1 \(\ell\)r foi propagado. Assim, o verificador i define seu próprio líder como o jogador \(\ell\)r. Assim, no tempo \(\beta\)r,2 eu, verificador i propaga mr,2 eu = (ESIGi(v′ eu), \(\sigma\)r,2 eu), onde v′ eu = H(Br \(\ell\)r). Quando r = 0, a única diferença é que \(\beta\)r,2 eu = t2 em vez de estar em um intervalo. Coisas semelhantes podem ser ditas para passos futuros e não os enfatizarei novamente. Etapa 3. Fixe arbitrariamente um verificador honesto i \(\in\)HSV r,3. Pelo Lema 5.5, quando o jogador i termina esperando no tempo \(\beta\)r,3 eu = \(\alpha\)r,3 eu + t3, ele recebeu todas as mensagens enviadas pelos verificadores em HSV r,2. Pelas relações entre os parâmetros, com probabilidade esmagadora |HSV r,2| > 2|MSV r,2|. Além disso, nenhum verificador honesto assinaria mensagens contraditórias, e o Adversário não pode falsificar a assinatura de um verificador honesto depois que este último tiver destruído seu correspondente chave secreta efêmera. Assim, mais de 2/3 de todas as mensagens (r, 2) válidas que recebi são de verificadores honestos e da forma mr,2 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,2 j ), sem contradição. Assim, no tempo \(\beta\)r,3 eu jogador i propaga mr,3 eu = (ESIGi(v′), \(\sigma\)r,3 eu ), onde v′ = H(Br \(\ell\)r).Etapa 4. Fixe arbitrariamente um verificador honesto i \(\in\)HSV r,4. Pelo Lema 5.5, o jogador i recebeu todos mensagens enviadas pelos verificadores no HSV r,3 quando ele termina de esperar no tempo \(\beta\)r,4 eu = \(\alpha\)r,4 eu +t4. Semelhante a Etapa 3, mais de 2/3 de todas as mensagens (r, 3) válidas que recebi são de verificadores honestos e da forma senhor,3 j = (ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,3 j). Assim, o jogador i define vi = H(Br \(\ell\)r), gi = 2 e bi = 0. No tempo \(\beta\)r,4 eu = \(\alpha\)r,4 eu +t4 ele propaga senhor,4 eu = (ESIGi(0), ESIGi(H(Br \(\ell\)r)), \(\sigma\)r,4 eu). Etapa 5. Fixe arbitrariamente um verificador honesto i \(\in\)HSV r,5. Pelo Lema 5.5, jogador eu teria recebeu todas as mensagens enviadas pelos verificadores no HSV r,4 se ele esperou até o tempo \(\alpha\)r,5 eu + t5. Observe que |HSV r,4| \(\geq\)tH.19 Observe também que todos os verificadores em HSV r,4 assinaram para H(Br \(\ell\)r). Como |MSV r,4| < tH, não existe v′ ̸= H(Br \(\ell\)r) que poderia ter sido assinado por tH verificadores em SV r,4 (que seriam necessariamente maliciosos), então o jogador i não para antes de ter recebeu mensagens válidas mr,4 j = (ESIGj(0), ESIGj(H(Br \(\ell\)r)), \(\sigma\)r,4 j). Seja T o momento em que o último evento acontece. Algumas dessas mensagens podem ser de jogadores maliciosos, mas porque |MSV r,4| < tH, pelo menos um deles é de um verificador honesto em HSV r,4 e é enviado após o tempo Tr+t4. Assim, T \(\geq\)T r +t4 > T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\)r +Λ, e no momento T o jogador i também recebeu a mensagem senhor,1 \(\ell\)r. Pela construção do protocolo, o jogador i para no tempo \(\beta\)r,5 eu = T sem propagar qualquer coisa; define Br = Br \(\ell\)r; e define seu próprio CERT r como o conjunto de (r, 4) mensagens para 0 e H(Br \(\ell\)r) que ele recebeu. Etapa s > 5. Da mesma forma, para qualquer passo s > 5 e qualquer verificador i \(\in\)HSV r,s, o jogador i teria recebeu todas as mensagens enviadas pelos verificadores no HSV r,4 se ele esperou até o tempo \(\alpha\)r,s eu + ts. Pelo mesma análise, jogador i para sem propagar nada, configurando Br = Br \(\ell\)r (e definindo seu próprio CERT r corretamente). É claro que os verificadores maliciosos podem não parar e podem propagar mensagens, mas porque |MSV r,s| <tH, por indução nenhum outro v′ poderia ser assinado pelos verificadores tH em qualquer passo 4 \(\leq\)s′ < s, portanto, os verificadores honestos só param porque receberam o valor válido (r, 4)-mensagens para 0 e H(Br \(\ell\)r). Reconstrução do Bloco Round-r. A análise do Passo 5 aplica-se a uma abordagem honesta genérica. usuário eu quase sem nenhuma alteração. Na verdade, o jogador i inicia sua própria rodada r no intervalo Ir e só irá parar no instante T quando tiver recebido tH mensagens válidas (r, 4) para H(Br \(\ell\)r). Novamente porque pelo menos uma dessas mensagens é de verificadores honestos e é enviada após o tempo T r + t4, o jogador i tem também recebeu senhor,1 \(\ell\)r pelo tempo T. Assim, ele define Br = Br \(\ell\)r com o CERT r adequado. Resta apenas mostrar que todos os usuários honestos terminam sua rodada r dentro do intervalo de tempo Ir+1. Pela análise da Etapa 5, todo verificador honesto i \(\in\)HSV r,5 conhece Br em ou antes de \(\alpha\)r,5 eu + t5 \(\leq\) Tr + \(\lambda\) + t5 = Tr + 8\(\lambda\) + Λ. Como T r+1 é o momento em que o primeiro usuário honesto conhece Br, temos T r+1 \(\leq\)T r + 8\(\lambda\) + Λ conforme desejado. Além disso, quando o jogador conhece o Br, ele já ajudou a propagar as mensagens em seu CERT r. Observe que todas essas mensagens serão recebidas por todos os usuários honestos dentro do tempo \(\lambda\), mesmo que 19Estritamente falando, isto acontece com uma probabilidade muito elevada, mas não necessariamente esmagadora. No entanto, isso a probabilidade afeta ligeiramente o tempo de execução do protocolo, mas não afeta sua correção. Quando h = 80%, então |HSV r,4| \(\geq\)tH com probabilidade 1 −10−8. Se este evento não ocorrer, o protocolo continuará por mais um 3 etapas. Como a probabilidade de isso não ocorrer em duas etapas é insignificante, o protocolo terminará na Etapa 8. Em expectativa, então, o número de etapas necessárias é quase 5.player ir foi o primeiro player a propagá-los. Além disso, seguindo a análise acima, temos T r+1 \(\geq\)T r + t4 \(\geq\) \(\beta\)r,1 \(\ell\)r + Λ, portanto, todos os usuários honestos receberam mr,1 \(\ell\)r por tempo T r+1 + \(\lambda\). Assim, todos os usuários honestos conhecem Br no intervalo de tempo Ir+1 = [T r+1, T r+1 + \(\lambda\)]. Finalmente, para r = 0 temos na verdade T 1 \(\leq\)t4 + \(\lambda\) = 6\(\lambda\) + Λ. Combinando tudo junto, O lema 5.2 é válido. ■ 5.8 O Lema da Solidez Lema 5.3. [Lema da Solidez, reformulado] Assumindo que as Propriedades 1–3 são válidas para a rodada r −1, quando o líder \(\ell\)r é malicioso, com grande probabilidade, todos os usuários honestos concordam com o mesmo bloco Br, T r+1 \(\leq\)T r + (6Lr + 10)\(\lambda\) + Λ e todos os usuários honestos conhecem Br no intervalo de tempo Ir+1. Prova. Consideramos as duas partes do protocolo, GC e BBA⋆, separadamente. GC. Pela hipótese indutiva e pelo Lema 5.5, para qualquer passo s \(\in\){2, 3, 4} e qualquer passo honesto verificador i \(\in\)HSV r,s, quando o jogador i atua no tempo \(\beta\)r,s eu = \(\alpha\)r,s eu +ts, ele recebeu todas as mensagens enviadas por todos os verificadores honestos nas etapas s′ < s. Distinguimos dois casos possíveis para o passo 4. Caso 1. Nenhum verificador i \(\in\)HSV r,4 define gi = 2. Neste caso, por definição bi = 1 para todos os verificadores i \(\in\)HSV r,4. Ou seja, eles começam com um acordo sobre 1 no protocolo BA binário. Eles podem não ter um acordo sobre seus vis, mas isso não importa, como veremos no BA binário. Caso 2. Existe um verificador ˆi \(\in\)HSV r,4 tal que gˆi = 2. Neste caso, mostramos que (1) gi \(\geq\)1 para todo i \(\in\)HSV r,4, (2) existe um valor v′ tal que vi = v′ para todo i \(\in\)HSV r,4, e (3) existe uma mensagem válida mr,1 \(\ell\) de algum verificador \(\ell\) \(\in\)SV r,1 tal que v′ = H(Br \(\ell\)). Na verdade, como o jogador ˆi é honesto e define gˆi = 2, mais de 2/3 de todas as mensagens válidas mr,3 j ele recebeu são para o mesmo valor v′ ̸= \(\bot\), e ele definiu vˆi = v′. Pela Propriedade (d) no Lema 5.5, para qualquer outro verificador honesto (r, 4) i, não pode ser que mais de 2/3 de todas as mensagens válidas mr,3 j que i′ recebeu têm o mesmo valor v′′ ̸= v′. Conseqüentemente, se i definir gi = 2, deve ser que i tenha visto > 2/3 de maioria para v′ também e defina vi = v′, conforme desejado. Agora considere um verificador arbitrário i \(\in\)HSV r,4 com gi < 2. Semelhante à análise de Propriedade (d) no Lema 5.5, porque o jogador ˆi obteve > 2/3 de maioria para v′, mais de 1 2|HSV r,3| honesto (r, 3)-verificadores assinaram v′. Porque recebi todas as mensagens de verificadores honestos (r, 3) de tempo \(\beta\)r,4 eu = \(\alpha\)r,4 eu + t4, ele recebeu em particular mais de 1 2|HSV r,3| mensagens deles para v'. Porque |HSV r,3| > 2|MSV r,3|, i obteve > 1/3 de maioria para v′. Assim, jogador i define gi = 1 e a propriedade (1) é válida. O jogador i necessariamente define vi = v′? Suponha que exista um valor diferente v′′ ̸= \(\bot\)tal que o jogador i também obteve > 1/3 de maioria para v′′. Algumas dessas mensagens podem ser de mensagens maliciosas verificadores, mas pelo menos um deles é de algum verificador honesto j \(\in\)HSV r,3: de fato, porque |HSV r,3| > 2|MSV r,3| e recebi todas as mensagens do HSV r,3, o conjunto de malware verificadores de quem i recebeu uma mensagem válida (r, 3) conta como <1/3 de todas as mensagens válidas mensagens que recebeu.Por definição, o jogador j deve ter visto > 2/3 de maioria para v′′ entre todas as mensagens (r, 2) válidas ele recebeu. No entanto, já temos que alguns outros verificadores (r, 3) honestos viram Maioria de 2/3 para v′ (porque assinaram v′). Pela Propriedade (d) do Lema 5.5, isso não pode acontecer e tal valor v′′ não existe. Assim, o jogador i deve ter definido vi = v′ conforme desejado, e Propriedade (2) é válida. Finalmente, dado que alguns verificadores (r, 3) honestos viram uma maioria > 2/3 para v′, alguns (na verdade, mais da metade dos verificadores) honestos (r, 2) assinaram v′ e propagaram suas mensagens. Pela construção do protocolo, aqueles verificadores (r, 2) honestos devem ter recebido um valor válido. mensagem senhor,1 \(\ell\) de algum jogador \(\ell\) \(\in\)SV r,1 com v′ = H(Br \(\ell\)), portanto a Propriedade (3) é válida. BBA⋆. Novamente distinguimos dois casos. Caso 1. Todos os verificadores i \(\in\)HSV r,4 possuem bi = 1. Isso acontece seguindo o Caso 1 do GC. Como |MSV r,4| < tH, neste caso não há verificador em SV r,5 poderia coletar ou gerar mensagens válidas (r, 4) para o bit 0. Assim, nenhum verificador honesto em HSV r,5 pararia porque conhece um bloco não vazio, o Ir. Além disso, embora existam pelo menos tH mensagens (r, 4) válidas para o bit 1, s′ = 5 não satisfaz s′ −2 ≡1 mod 3, portanto, nenhum verificador honesto em HSV r,5 pararia porque sabe que Br = Br ǫ. Em vez disso, todo verificador i \(\in\)HSV r,5 atua no tempo \(\beta\)r,5 eu = \(\alpha\)r,5 eu + t5, quando ele tiver recebido todos mensagens enviadas pelo HSV r,4 seguindo o Lema 5.5. Assim, o jogador i obteve > 2/3 de maioria para 1 e define bi = 1. Na Etapa 6, que é uma etapa Coin-Fixed-To-1, embora s′ = 5 satisfaça s′ −2 ≡0 mod 3, há não existem mensagens válidas (r, 4) para o bit 0, portanto, nenhum verificador em HSV r,6 pararia porque ele conhece um bloco não vazio, Ir. No entanto, com s′ = 6, s′ −2 ≡1 mod 3 e existem |HSV r,5| \(\geq\)tH mensagens válidas (r, 5) para o bit 1 do HSV r,5. Para cada verificador i \(\in\)HSV r,6, seguindo o Lema 5.5, no tempo ou antes dele \(\alpha\)r,6 eu + jogador t6 eu recebeu todas as mensagens do HSV r,5, então paro sem propagar nada e configuro Br = Br ǫ. Seu CERT r é o conjunto de tH mensagens válidas (r, 5) mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) recebido por ele quando ele para. Em seguida, seja o jogador i um verificador honesto na etapa s > 6 ou um usuário honesto genérico (ou seja, não verificador). Semelhante à prova do Lema 5.2, o jogador i define Br = Br ǫ e define o seu próprio CERT r como o conjunto de tH mensagens válidas (r, 5) mr,5 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,5 j) ele tem recebido. Finalmente, semelhante ao Lema 5.2, Tr+1 \(\leq\) min i\(\in\)HSV r,6 \(\alpha\)r,6 eu + t6 \(\leq\)T r + \(\lambda\) + t6 = T r + 10\(\lambda\) + Λ, e todos os usuários honestos conhecem Br no intervalo de tempo Ir+1, porque o primeiro usuário honesto i que sabe que Br ajudou a propagar as mensagens (r, 5) em seu CERT r. Caso 2. Existe um verificador ˆi \(\in\)HSV r,4 com bˆi = 0. Isto acontece seguindo o Caso 2 do GC e é o caso mais complexo. Pela análise do GC, neste caso existe uma mensagem válida mr,1 \(\ell\) tal que vi = H(Br \(\ell\)) para todo i \(\in\)HSV r,4. Nota que os verificadores no HSV r,4 podem não ter um acordo sobre seus bi’s. Para qualquer passo s \(\in\){5, . . . , m + 3} e verificador i \(\in\)HSV r,s, pelo Lema 5.5 jogador eu teria recebeu todas as mensagens enviadas por todos os verificadores honestos em HSV r,4 \(\cup\) \(\cdots\) \(\cup\)HSV r,s−1 se ele esperou por tempo ts.Consideramos agora o seguinte evento E: existe um passo s∗\(\geq\)5 tal que, pela primeira vez tempo no BA binário, algum jogador i∗\(\in\)SV r,s∗(seja malicioso ou honesto) deveria parar sem propagar nada. Usamos “deveria parar” para enfatizar o fato de que, se o jogador i∗ é malicioso, então ele pode fingir que não deveria parar de acordo com o protocolo e propagar mensagens da escolha do Adversário. Além disso, pela construção do protocolo, quer (E.a) i∗é capaz de coletar ou gerar pelo menos tH mensagens válidas mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ) para os mesmos v e s′, com 5 \(\leq\)s′ \(\leq\)s∗and s′ −2 ≡0 mod 3; ou (E.b) i∗é capaz de coletar ou gerar pelo menos tH mensagens válidas mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ) para o mesmo s′, com 6 \(\leq\)s′ \(\leq\)s∗e s′ −2 ≡1 mod 3. Porque as mensagens honestas (r, s′ −1) são recebidas por todos os verificadores honestos (r, s′) antes de terminam de esperar na Etapa s′, e porque o Adversário recebe tudo o mais tardar no usuários honestos, sem perda de generalidade temos s′ = s∗e o jogador i∗é malicioso. Observe que não exigimos que o valor v em E.a fosse o hash de um bloco válido: como ficará claro na análise, v = H(Br \(\ell\)) neste subevento. Abaixo analisamos primeiro o Caso 2 após o evento E, e depois mostramos que o valor de s∗é essencialmente distribuído de acordo com Lr (portanto, o evento E acontece antes da Etapa m + 3 com esmagadora probabilidade, dadas as relações dos parâmetros). Para começar, para qualquer etapa 5 \(\leq\)s < s∗, todo verificador honesto i \(\in\)HSV r,s esperou o tempo ts e definiu vi como o voto majoritário do mensagens válidas (r, s−1) que ele recebeu. Como o jogador i recebeu todas as mensagens honestas (r, s−1) seguindo o Lema 5.5, uma vez que todos os verificadores honestos em HSV r,4 assinaram H(Br \(\ell\)) seguinte caso 2 do GC, e já que |HSV r,s−1| > 2|MSV r,s−1| para cada s, por indução temos aquele jogador i definiu vi = H(Br \(\ell\)). O mesmo vale para todo verificador honesto i \(\in\)HSV r,s∗que não para sem propagar qualquer coisa. Agora consideramos a Etapa s∗ e distinguimos quatro subcasos. Caso 2.1.a. O evento E.a acontece e existe um verificador honesto i′ \(\in\)HSV r,s∗que deveria também pare sem propagar nada. Neste caso, temos s∗−2 ≡0 mod 3 e o passo s∗ é um passo Coin-Fixed-To-0. Por definição, o jogador i′ recebeu pelo menos tH mensagens válidas (r, s∗−1) da forma (ESIGj(0), ESIGj(v), \(\sigma\)r,s∗−1 j ). Como todos os verificadores em HSV r,s∗−1 assinaram H(Br \(\ell\)) e |MSV r,s∗−1| <tH, temos v = H(Br \(\ell\)). Como pelo menos tH −|MSV r,s∗−1| \(\geq\)1 das (r, s∗−1)-mensagens recebidas por i′ para 0 e v são enviados por verificadores em HSV r,s∗−1 após o tempo T r +ts∗−1 \(\geq\)T r +t4 \(\geq\)T r +\(\lambda\)+Λ \(\geq\) \(\beta\)r,1 \(\ell\) +Λ, jogador i′ recebeu mr,1 \(\ell\) no momento em que ele recebe essas mensagens (r, s∗−1). Assim jogador i′ para sem propagar nada; define Br = Br \(\ell\); e define seu próprio CERT r para ser o conjunto de mensagens (r, s∗−1) válidas para 0 e v que ele recebeu. A seguir, mostramos que qualquer outro verificador i \(\in\)HSV r,s∗ parou com Br = Br \(\ell\), ou definiu bi = 0 e propagou (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s eu). Na verdade, porque Step s∗ é a primeira vez que algum verificador deve parar sem propagar nada, não há existe uma etapa s′ < s∗com s′ −2 ≡1 mod 3 tal que tH (r, s′ −1)-verificadores assinaram 1. Conseqüentemente, nenhum verificador em HSV r,s∗para com Br = Br ǫ.Além disso, como todos os verificadores honestos nas etapas {4, 5, . . . , s∗−1} assinaram H(Br \(\ell\)), existe não existe uma etapa s′ \(\leq\)s∗com s′ −2 ≡0 mod 3 tal que tH (r, s′ −1)-verificadores assinaram algum v′′ ̸= H(Br \(\ell\)) —de fato, |MSV r,s′−1| < tH. Conseqüentemente, nenhum verificador em HSV r,s∗stops com Br̸= Br ǫ e Br̸= Br \(\ell\). Isto é, se um jogador i \(\in\)HSV r,s∗ parou sem propagando qualquer coisa, ele deve ter definido Br = Br \(\ell\). Se um jogador i \(\in\)HSV r,s∗ esperou o tempo ts∗ e propagou uma mensagem no momento \(\beta\)r,s∗ eu = \(\alpha\)r,s∗ eu + ts∗, ele recebeu todas as mensagens do HSV r,s∗−1, incluindo pelo menos tH −|MSV r,s∗−1| deles para 0 e v. Se eu obtive uma maioria > 2/3 para 1, então ele viu mais de 2(tH −|MSV r,s∗−1|) mensagens (r, s∗−1) válidas para 1, com mais que 2tH −3|MSV r,s∗−1| deles de verificadores (r, s∗−1) honestos. No entanto, isso implica |HSV r,s∗−1| \(\geq\)tH−|MSV r,s∗−1|+2tH−3|MSV r,s∗−1| > 2n−4|MSV r,s∗−1|, contradizendo o fato de que |HSV r,s∗−1| + 4|MSV r,s∗−1| < 2n, que vem dos relacionamentos para os parâmetros. Assim, não vejo > 2/3 maioria para 1, e ele define bi = 0 porque a etapa s∗ é uma etapa com moeda fixada em 0. Como temos visto, vi = H(Br \(\ell\)). Assim i se propaga (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s i) como queríamos mostrar. Para a Etapa s∗+ 1, já que o jogador i′ ajudou a propagar as mensagens em seu CERT r no ou antes do tempo \(\alpha\)r,s∗ eu' + ts∗, todos os verificadores honestos em HSV r,s∗+1 receberam pelo menos mensagens válidas (r, s∗−1) para o bit 0 e valor H(Br \(\ell\)) antes ou antes de terminarem esperando. Além disso, os verificadores em HSV r,s∗+1 não irão parar antes de receber aqueles (r, s∗−1)- mensagens, porque não existem outras tH mensagens válidas (r, s′ −1) para o bit 1 com s′ −2 ≡1 mod 3 e 6 \(\leq\)s′ \(\leq\)s∗+ 1, pela definição do Passo s∗. Em particular, Passo s∗+ 1 em si é uma etapa Coin-Fixed-To-1, mas nenhum verificador honesto em HSV r,s∗ propagou uma mensagem para 1 e |MSV r,s∗| < tH. Assim, todos os verificadores honestos em HSV r,s∗+1 param sem propagar nada e definem Br = irmão \(\ell\): como antes, eles receberam mr,1 \(\ell\) antes de receberem as mensagens (r, s∗−1) desejadas.20 O mesmo pode ser dito de todos os verificadores honestos em etapas futuras e de todos os usuários honestos em geral. Em particular, todos eles sabem Br = Br \(\ell\)dentro do intervalo de tempo Ir+1 e T r+1 \(\leq\) \(\alpha\)r,s∗ eu' + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Caso 2.1.b. O evento E.b acontece e existe um verificador honesto i′ \(\in\)HSV r,s∗que deveria também pare sem propagar nada. Neste caso, temos s∗−2 ≡1 mod 3 e o passo s∗ é um passo Coin-Fixed-To-1. A análise é semelhante ao Caso 2.1.a e muitos detalhes foram omitidos. 20Se \(\ell\) for malicioso, ele poderá enviar mr,1 \(\ell\) tarde, esperando que alguns usuários/verificadores honestos não tenham recebido mr,1 \(\ell\) ainda quando receberem o certificado desejado por isso. No entanto, como o verificador ˆi \(\in\)HSV r,4 definiu bˆi = 0 e vˆi = H(Br \(\ell\)), como antes de termos que mais da metade dos verificadores honestos i \(\in\)HSV r,3 definiram vi = H(Br \(\ell\)). Isto implica ainda mais mais da metade dos verificadores honestos i \(\in\)HSV r,2 definiram vi = H(Br \(\ell\)), e todos os verificadores (r, 2) receberam mr,1 \(\ell\). Como o O adversário não consegue distinguir um verificador de um não-verificador, ele não pode visar a propagação de mr,1 \(\ell\) para (r, 2)-verificadores sem que os não-verificadores o vejam. Na verdade, com alta probabilidade, mais da metade (ou uma boa fração constante) de todos os usuários honestos viram mr,1 \(\ell\) depois de esperar por t2 desde o início de sua própria rodada r. A partir daqui, o tempo \(\lambda\)′ necessário para mr,1 \(\ell\) alcançar os usuários honestos restantes é muito menor que Λ e, para simplificar, não escreva na análise. Se 4\(\lambda\) \(\geq\) \(\lambda\)′ então a análise prossegue sem qualquer alteração: ao final da Etapa 4, todos usuários honestos teriam recebido mr,1 \(\ell\). Se o tamanho do bloco se tornar enorme e 4\(\lambda\) < \(\lambda\)′, então nas Etapas 3 e 4, o protocolo poderia pedir a cada verificador que esperasse por \(\lambda\)′/2 em vez de 2\(\lambda\), e a análise continua válida.Como antes, o jogador i′ deve ter recebido pelo menos tH mensagens válidas (r, s∗−1) da forma (ESIGj(1), ESIGj(vj), \(\sigma\)r,s∗−1 j ). Novamente pela definição de s∗, não existe um passo 5 \(\leq\)s′ < s∗com s′ −2 ≡0 mod 3, onde pelo menos tH (r, s′ −1)-verificadores assinaram 0 e o mesmo v. Assim o jogador i′ para sem propagar nada; define Br = Br ǫ; e conjuntos seu próprio CERT r seja o conjunto de mensagens (r, s∗−1) válidas para o bit 1 que ele recebeu. Além disso, qualquer outro verificador i \(\in\)HSV r,s∗ parou com Br = Br ǫ , ou definiu bi = 1 e propagado (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ eu ). Já que o jogador i′ ajudou a propagar as mensagens (r, s∗−1) em seu CERT r no tempo \(\alpha\)r,s∗ eu' + ts∗, novamente todos os verificadores honestos em HSV r,s∗+1 para sem propagar nada e define Br = Br ǫ . Da mesma forma, todos os honestos os usuários sabem Br = Br ǫ dentro do intervalo de tempo Ir+1 e T r+1 \(\leq\) \(\alpha\)r,s∗ eu' + ts∗\(\leq\)T r + \(\lambda\) + ts∗. Caso 2.2.a. O evento E.a acontece e não existe um verificador honesto i′ \(\in\)HSV r,s∗quem também deve parar sem propagar nada. Neste caso, observe que o jogador i∗ poderia ter um CERT válido r i∗consistindo no tH desejado (r, s∗−1)-mensagens que o Adversário é capaz de coletar ou gerar. No entanto, o malicioso verificadores podem não ajudar a propagar essas mensagens, por isso não podemos concluir que o honesto os usuários os receberão no tempo \(\lambda\). Na verdade, |MSV r,s∗−1| dessas mensagens podem ser de verificadores (r, s∗−1) maliciosos, que não propagaram suas mensagens e apenas enviaram para os verificadores maliciosos na etapa s∗. Semelhante ao Caso 2.1.a, aqui temos s∗−2 ≡0 mod 3, a etapa s∗ é uma etapa com moeda fixada em 0, e as mensagens (r, s∗−1) no CERT r i∗são para o bit 0 e v = H(Br \(\ell\)). Na verdade, todos honestos (r, s∗−1)-verificadores assinam v, portanto o Adversário não pode gerar as mensagens (r, s∗−1) válidas para um v′ diferente. Além disso, todos os verificadores (r, s∗) honestos esperaram o tempo ts∗ e não veem > 2/3 da maioria para o bit 1, novamente porque |HSV r,s∗−1| + 4|MSV r,s∗−1| <2n. Assim, todo verificador honesto i \(\in\)HSV r,s∗conjuntos bi = 0, vi = H(Br \(\ell\)) pela maioria dos votos e propaga mr,s∗ eu = (ESIGi(0), ESIGi(H(Br \(\ell\))), \(\sigma\)r,s∗ eu ) no tempo \(\alpha\)r,s∗ eu + ts∗. Agora considere os verificadores honestos na Etapa s∗+ 1 (que é uma etapa de Moeda Fixada em 1). Se o O adversário realmente envia as mensagens no CERT r i∗para alguns deles e faz com que eles pare, então semelhante ao Caso 2.1.a, todos os usuários honestos sabem Br = Br \(\ell\)dentro do intervalo de tempo Ir+1 e T r+1 \(\leq\)T r + \(\lambda\) + ts∗+1. Caso contrário, todos os verificadores honestos na Etapa s∗+1 receberam todas as mensagens (r, s∗) para 0 e H(Br \(\ell\)) do HSV r,s∗após o tempo de espera ts∗+1, o que leva a > 2/3 da maioria, porque |HSV r,s∗| > 2|MSV r,s∗|. Assim, todos os verificadores em HSV r,s∗+1 propagam suas mensagens para 0 e H(Br \(\ell\)) em conformidade. Observe que os verificadores em HSV r,s∗+1 não param em Br = Br \(\ell\), porque a etapa s∗+ 1 não é uma etapa com moeda fixada em 0. Agora considere os verificadores honestos na Etapa s∗+2 (que é uma etapa de Inversão Genuína da Moeda). Se o Adversário enviar as mensagens em CERT r i∗para alguns deles e faz com que parem, então, novamente, todos os usuários honestos sabem Br = Br \(\ell\)dentro do intervalo de tempo Ir+1 e T r+1 \(\leq\)T r + \(\lambda\) + ts∗+2.Caso contrário, todos os verificadores honestos na Etapa s∗+ 2 receberam todas as mensagens (r, s∗+ 1) para 0 e H(Br \(\ell\)) do HSV r,s∗+1 após o tempo de espera ts∗+2, o que leva a uma maioria > 2/3. Assim todos eles propagam suas mensagens para 0 e H(Br \(\ell\)) respectivamente: é isso que eles fazem não “jogue uma moeda” neste caso. Novamente, observe que eles não param sem se propagar, porque a etapa s∗+ 2 não é uma etapa com moeda fixada em 0. Finalmente, para os verificadores honestos na Etapa s∗+3 (que é outra etapa de Moeda Fixada em 0), todos deles teriam recebido pelo menos tH mensagens válidas para 0 e H(Br \(\ell\)) de HSV s∗+2, se eles realmente esperarem o tempo ts∗+3. Assim, quer o Adversário envie ou não as mensagens no CERT r i∗para qualquer um deles, todos os verificadores em HSV r,s∗+3 param com Br = Br \(\ell\), sem propagar qualquer coisa. Dependendo de como o Adversário age, alguns deles podem ter seu próprio CERT r consistindo naquelas (r, s∗−1)-mensagens em CERT r i∗, e os outros têm seu próprio CERT r consistindo nessas mensagens (r, s∗+ 2). De qualquer forma, todos os usuários honestos saiba Br = Br \(\ell\)dentro do intervalo de tempo Ir+1 e T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3. Caso 2.2.b. O evento E.b acontece e não existe um verificador honesto i′ \(\in\)HSV r,s∗quem também deve parar sem propagar nada. A análise neste caso é semelhante àquelas no Caso 2.1.b e Caso 2.2.a, portanto muitos detalhes foram omitidos. Em particular, CERT r i∗consiste nas tH mensagens desejadas (r, s∗−1) para o bit 1 que o Adversário é capaz de coletar ou gerar, s∗−2 ≡1 mod 3, Etapa s∗é um Etapa Coin-Fixed-To-1, e nenhum verificador (r, s∗) honesto poderia ter visto > 2/3 de maioria para 0. Assim, todo verificador i \(\in\)HSV r,s∗define bi = 1 e propaga mr,s∗ eu = (ESIGi(1), ESIGi(vi), \(\sigma\)r,s∗ eu ) no tempo \(\alpha\)r,s∗ eu + ts∗. Semelhante ao Caso 2.2.a, em no máximo mais 3 etapas (ou seja, o protocolo atinge a Etapa s∗+3, que é outra etapa Coin-Fixed-To-1), todos os usuários honestos sabem Br = Br ǫ dentro do intervalo de tempo Ir+1. Além disso, T r+1 pode ser \(\leq\)T r+\(\lambda\)+ts∗+1, ou \(\leq\)T r+\(\lambda\)+ts∗+2, ou \(\leq\)T r + \(\lambda\) + ts∗+3, dependendo de quando é a primeira vez que um verificador honesto é capaz de parar sem propagação. Combinando os quatro subcasos, temos que todos os usuários honestos conhecem Br dentro do intervalo de tempo Ir+1, com T r+1 \(\leq\)T r + \(\lambda\) + ts∗ nos casos 2.1.a e 2.1.b, e T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 nos Casos 2.2.a e 2.2.b. Resta limitar s∗ e, portanto, T r+1 para o Caso 2, e fazemos isso considerando como muitas vezes as etapas Coin-Genuinely-Flipped são realmente executadas no protocolo: isto é, alguns verificadores honestos realmente jogaram uma moeda ao ar. Em particular, corrija arbitrariamente uma etapa s′ de moeda genuinamente invertida (ou seja, 7 \(\leq\)s′ \(\leq\)m + 2 e s′ −2 ≡2 mod 3), e seja \(\ell\)′ \(\triangleq\)arg minj\(\in\)SV r,s′−1 H(\(\sigma\)r,s′−1 j ). Por enquanto vamos assumir s′ < s∗, porque de outra forma nenhum verificador honesto realmente joga uma moeda na Etapa s′, de acordo com discussões. Pela definição de SV r,s′−1, o valor hash da credencial de \(\ell\)′ também é o menor entre todos os usuários em PKr-k. Como a função hash é uma oracle aleatória, idealmente o jogador \(\ell\)′ é honesto com probabilidade pelo menos h. Como mostraremos mais tarde, mesmo que o Adversário tente ao máximo prever o saída do aleatório oracle e inclina a probabilidade, o jogador \(\ell\) ′ ainda é honesto com a probabilidadepelo menos ph = h2(1 + h −h2). Abaixo consideramos o caso em que isso realmente acontece: isto é, \(\ell\)′ \(\in\)HSV r,s′−1. Observe que todo verificador honesto i \(\in\)HSV r,s′ recebeu todas as mensagens do HSV r,s′−1 por tempo \(\alpha\)r,s′ eu +ts′. Se o jogador i precisar jogar uma moeda (ou seja, ele não obteve > 2/3 da maioria por o mesmo bit b \(\in\){0, 1}), então ele define bi = lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )). Se existir outro honesto verificador i′ \(\in\)HSV r,s′ que viu > 2/3 maioria para um bit b \(\in\){0, 1}, então por Propriedade (d) do Lema 5.5, nenhum verificador honesto em HSV r,s′ teria visto > 2/3 de maioria por um tempo b′̸=b. Como lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) = b com probabilidade 1/2, todos os verificadores honestos em HSV r,s′ alcançam um acordo sobre b com probabilidade 1/2. É claro que, se tal verificador i′ não existir, então todos verificadores honestos em HSV r,s′ concordam com o bit lsb(H(\(\sigma\)r,s′−1 \(\ell\)′ )) com probabilidade 1. Combinando a probabilidade para \(\ell\)′ \(\in\)HSV r,s′−1, temos que os verificadores honestos em HSV r,s′ chegar a um acordo sobre um bit b \(\in\){0, 1} com probabilidade pelo menos ph 2 = h2(1+h−h2) 2 . Além disso, por indução na votação majoritária como antes, todos os verificadores honestos em HSV r,s′ têm seus vi definidos ser H(Br \(\ell\)). Assim, uma vez alcançado um acordo sobre b na Etapa s′, T r+1 é ou \(\leq\)T r + \(\lambda\) + ts′+1 ou \(\leq\)T r + \(\lambda\) + ts′+2, dependendo se b = 0 ou b = 1, seguindo a análise dos Casos 2.1.a e 2.1.b. Em particular, nenhuma etapa adicional de Coin-Genuinely-Flipped será executada: isto é, os verificadores em tais passos ainda verificam se eles são os verificadores e, portanto, esperam, mas todos irão parar sem propagar qualquer coisa. Assim, antes do Passo s∗, o número de vezes que os passos Coin-GenuinelyFlipped são executados é distribuído de acordo com a variável aleatória Lr. Deixando o Passo s′ ser a última etapa de Coin-Genuinely-Flipped de acordo com Lr, pela construção do protocolo nós temos s′ = 4 + 3Lr. Quando o Adversário deve fazer o Step s∗ acontecer se ele quiser atrasar T r+1 tanto quanto possível? Podemos até assumir que o Adversário conhece antecipadamente a realização de Lr. Se s∗> s′ então é inútil, porque os verificadores honestos já chegaram a um acordo em Passo s′. Com certeza, neste caso s∗seria s′ +1 ou s′ +2, novamente dependendo se b = 0 ou b = 1. No entanto, na verdade estes são os Casos 2.1.a e 2.1.b, e o T r+1 resultante é exatamente o o mesmo que nesse caso. Mais precisamente, T r+1 \(\leq\)T r + \(\lambda\) + ts∗\(\leq\)T r + \(\lambda\) + ts′+2. Se s∗< s′ −3 —isto é, s∗está antes da penúltima etapa de lançamento genuíno da moeda— então por a análise dos Casos 2.2.a e 2.2.b, T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 < T r + \(\lambda\) + ts′. Ou seja, o Adversário está na verdade fazendo com que o acordo sobre o Br aconteça de forma mais rápida. Se s∗= s′ −2 ou s′ −1 - isto é, a etapa Coin-Fixed-To-0 ou a etapa Coin-Fixed-To-1 imediatamente antes da Etapa s' - então, pela análise dos quatro subcasos, os verificadores honestos em A etapa s′ não consegue mais lançar moedas, porque elas pararam sem se propagar, ou viram maioria > 2/3 para o mesmo bit b. Portanto temos T r+1 \(\leq\)T r + \(\lambda\) + ts∗+3 \(\leq\)T r + \(\lambda\) + ts′+2.Em suma, não importa qual seja s∗, temos T r+1 \(\leq\)T r + \(\lambda\) + ts′+2 = T r + \(\lambda\) + t3Lr+6 = T r + \(\lambda\) + (2(3Lr + 6) −3)\(\lambda\) + Λ = T r + (6Lr + 10)\(\lambda\) + Λ, como queríamos mostrar. O pior caso é quando s∗= s′ −1 e o Caso 2.2.b acontece. Combinando os Casos 1 e 2 do protocolo BA binário, o Lema 5.3 é válido. ■ 5.9 Segurança do Qr Semente e Probabilidade de um Líder Honesto Resta provar o Lema 5.4. Lembre-se de que os verificadores na rodada r são retirados de PKr−k e são escolhidos de acordo com a quantidade Qr−1. A razão para introduzir o parâmetro lookback k é garantir que, na rodada r −k, quando o Adversário for capaz de adicionar novos usuários mal-intencionados para PKr−k, ele não pode prever a quantidade Qr−1 exceto com probabilidade desprezível. Observe que o A função hash é uma oracle aleatória e Qr−1 é uma de suas entradas ao selecionar verificadores para a rodada r. Assim, não importa quão usuários mal-intencionados sejam adicionados ao PKr-k, do ponto de vista do Adversário, cada um deles ainda é selecionado para ser um verificador em uma etapa de rodada r com a probabilidade necessária p (ou p1 para a Etapa 1). Mais precisamente, temos o seguinte lema. Lema 5.6. Com k = O(log1/2 F), para cada rodada r, com probabilidade esmagadora o Adversário não consultou Qr−1 para o oracle aleatório na rodada r −k. Prova. Procedemos por indução. Suponha que para cada rodada \(\gamma\) < r, o Adversário não questionou Q\(\gamma\)−1 ao aleatório oracle na rodada \(\gamma\) −k.21 Considere o seguinte jogo mental jogado por o Adversário na rodada r −k, tentando prever Qr−1. Na Etapa 1 de cada rodada \(\gamma\) = r −k,. . . , r −1, dado um Q\(\gamma\)−1 específico não consultado ao aleatório oracle, ordenando os jogadores i \(\in\)PK\(\gamma\)−k de acordo com os valores hash H(SIGi(\(\gamma\), 1, Q\(\gamma\)−1)) cada vez mais, obtemos uma permutação aleatória sobre PK\(\gamma\)−k. Por definição, o líder \(\ell\) \(\gamma\) é o primeiro usuário na permutação e é honesto com probabilidade h. Além disso, quando PK\(\gamma\)−k é grande suficiente, para qualquer número inteiro x \(\geq\)1, a probabilidade de que os primeiros x usuários na permutação sejam todos malicioso, mas o (x + 1)st é honesto é (1 −h)xh. Se \(\ell\) \(\gamma\) for honesto, então Q\(\gamma\) = H(SIG\(\ell\) \(\gamma\)(Q\(\gamma\)−1), \(\gamma\)). Como o Adversário não pode falsificar a assinatura de \(\ell\) \(\gamma\), Q\(\gamma\) é distribuído uniformemente aleatoriamente do ponto de vista do Adversário e, exceto com probabilidade exponencialmente pequena,22 não foi questionado para H na rodada r −k. Desde cada Q\(\gamma\)+1, Q\(\gamma\)+2, . . . , Qr−1 respectivamente é a saída de H com Q\(\gamma\), Q\(\gamma\)+1, . . . , Qr−2 como uma das entradas, todos eles parecem aleatórios para o Adversário e o Adversário não poderia ter consultado Qr−1 para H em rodada r −k. Conseqüentemente, o único caso em que o Adversário pode prever Qr−1 com boa probabilidade na rodada r−k é quando todos os líderes \(\ell\)r−k,. . . , \(\ell\)r−1 são maliciosos. Considere novamente uma rodada \(\gamma\) \(\in\){r−k . . . , r−1} e a permutação aleatória sobre PK\(\gamma\)−k induzida pelos valores hash correspondentes. Se para alguns x \(\geq\)2, os primeiros x −1 usuários na permutação são todos maliciosos e o x-ésimo é honesto, então o O adversário tem x escolhas possíveis para Q\(\gamma\): qualquer uma da forma H(SIGi(Q\(\gamma\)−1, \(\gamma\))), onde i é um dos 21Como k é um número inteiro pequeno, sem perda de generalidade pode-se assumir que as primeiras k rodadas do protocolo são executadas sob um ambiente seguro e a hipótese indutiva é válida para essas rodadas. 22Isto é, exponencial no comprimento da saída de H. Observe que esta probabilidade é bem menor que F.os primeiros x-1 usuários mal-intencionados, ao tornar o jogador i o verdadeiro líder da rodada \(\gamma\); ou H(Q\(\gamma\)−1, \(\gamma\)), por forçando B\(\gamma\) = B\(\gamma\) ǫ . Caso contrário, o líder da rodada \(\gamma\) será o primeiro usuário honesto na permutação e Qr−1 torna-se imprevisível para o Adversário. Qual das x opções de Q\(\gamma\) acima o Adversário deve seguir? Para ajudar o adversário responder a esta pergunta, no jogo mental nós realmente o tornamos mais poderoso do que ele realmente é, como segue. Em primeiro lugar, na realidade, o Adversário não pode calcular o hash do valor de um usuário honesto. assinatura, portanto não pode decidir, para cada Q\(\gamma\), o número x(Q\(\gamma\)) de usuários mal-intencionados no início da permutação aleatória na rodada \(\gamma\) + 1 induzida por Q\(\gamma\). No jogo mental, damos a ele o números x(Q\(\gamma\)) gratuitamente. Em segundo lugar, na realidade, ter os primeiros x usuários na permutação, todos ser malicioso não significa necessariamente que todos possam ser transformados em líderes, porque o hash os valores de suas assinaturas também devem ser menores que p1. Ignoramos essa restrição na mente jogo, dando ao Adversário ainda mais vantagens. É fácil perceber que no jogo mental a opção ótima para o Adversário, denotada por ˆQ\(\gamma\), é aquele que produz a maior sequência de usuários maliciosos no início do aleatório permutação na rodada \(\gamma\) + 1. Na verdade, dado um Q\(\gamma\) específico, o protocolo não depende de Q\(\gamma\)−1 mais e o Adversário pode focar apenas na nova permutação na rodada \(\gamma\) + 1, que tem o mesma distribuição para o número de usuários mal-intencionados no início. Assim, em cada rodada \(\gamma\), o ˆQ\(\gamma\) mencionado acima dá a ele o maior número de opções para Q\(\gamma\)+1 e, portanto, maximiza a probabilidade de que os líderes consecutivos sejam todos maliciosos. Portanto, no jogo mental o Adversário segue uma Cadeia de Markov da rodada r −k para arredondar r −1, com o espaço de estados sendo {0} \(\cup\){x : x \(\geq\)2}. O estado 0 representa o fato de que o o primeiro usuário na permutação aleatória na rodada atual \(\gamma\) é honesto, portanto o Adversário falha no jogo para previsão de Qr−1; e cada estado x \(\geq\)2 representa o fato de que os primeiros x −1 usuários no permutações são maliciosas e o x-ésimo é honesto, portanto o Adversário tem x opções para Q\(\gamma\). O as probabilidades de transição P(x, y) são as seguintes. • P(0, 0) = 1 e P(0, y) = 0 para qualquer y \(\geq\)2. Ou seja, o Adversário falha no jogo assim que o primeiro o usuário na permutação torna-se honesto. • P(x, 0) = hx para qualquer x \(\geq\)2. Ou seja, com probabilidade hx, todas as x permutações aleatórias têm seus primeiros usuários são honestos, portanto o Adversário falha no jogo na próxima rodada. • Para qualquer x \(\geq\)2 e y \(\geq\)2, P(x, y) é a probabilidade de que, entre as x permutações aleatórias induzida pelas x opções de Q\(\gamma\), a sequência mais longa de usuários mal-intencionados no início de alguns deles são y −1, portanto o Adversário tem y opções para Q\(\gamma\)+1 na próxima rodada. Isto é, P(x, y) = y−1 X eu=0 (1 −h)ih !x - y−2 X eu=0 (1 −h)ih !x = (1 −(1 −h)y)x −(1 −(1 −h)y−1)x. Observe que o estado 0 é o único estado absorvente na matriz de transição P, e todos os outros estados x tem uma probabilidade positiva de ir para 0. Estamos interessados em limitar superiormente o número k de rodadas necessárias para a Cadeia de Markov convergir para 0 com probabilidade esmagadora: isto é, não Não importa em que estado a cadeia comece, com uma probabilidade esmagadora de que o Adversário perca o jogo e falha em prever Qr−1 na rodada r −k. Considere a matriz de transição P (2) \(\triangleq\)P \(\cdot\) P após duas rodadas. É fácil ver que P (2) (0, 0) = 1 e P (2)(0, x) = 0 para qualquer x \(\geq\)2. Para qualquer x \(\geq\)2 e y \(\geq\)2, como P(0, y) = 0, temos P(2)(x, y) = P(x, 0)P(0, y) + X z\(\geq\)2 P(x, z)P(z, y) = X z\(\geq\)2 P(x, z)P(z, y).Deixando ¯h \(\triangleq\)1 −h, temos P(x, y) = (1 −¯hy)x −(1 −¯hy−1)x e P(2)(x,y) = X z\(\geq\)2 [(1 −¯hz)x −(1 −¯hz−1)x][(1 −¯hy)z −(1 −¯hy−1)z]. Abaixo calculamos o limite de P (2)(x,y) P(x,y) à medida que h vai para 1 - isto é, ¯h vai para 0. Observe que o maior a ordem de ¯h em P(x, y) é ¯hy−1, com coeficiente x. Assim, limão h \(\to\) 1 P(2)(x,y) P(x, y) =lim ¯h \(\to\) 0 P(2)(x,y) P(x, y) =lim ¯h \(\to\) 0 P(2)(x,y) x¯hy−1 + O(¯hy) = limão ¯h \(\to\) 0 P z\(\geq\)2[x¯hz−1 + O(¯hz)][z¯hy−1 + O(¯hy)] x¯hy−1 + O(¯hy) =lim ¯h \(\to\) 0 2x¯hy + O(¯hy+1) x¯hy−1 + O(¯hy) = limão ¯h \(\to\) 0 2x¯h x¯hy−1 = lim ¯h \(\to\) 0 2¯h = 0. Quando h está suficientemente próximo de 1,23, temos P(2)(x,y) P(x, y) \(\leq\)1 2 para qualquer x \(\geq\)2 e y \(\geq\)2. Por indução, para qualquer k > 2, P (k) \(\triangleq\)P k é tal que • P (k)(0, 0) = 1, P (k)(0, x) = 0 para qualquer x \(\geq\)2, e • para qualquer x \(\geq\)2 e y \(\geq\)2, P(k)(x, y) = P(k−1)(x, 0)P(0, y) + X z\(\geq\)2 P(k−1)(x, z)P(z, y) = X z\(\geq\)2 P(k−1)(x, z)P(z, y) \(\leq\) X z\(\geq\)2 P(x,z) 2k−2 \(\cdot\) P(z, y) = P(2)(x, y) 2k−2 \(\leq\)P(x, y) 2k−1. Como P(x, y) \(\leq\)1, após 1−log2 F rodadas, a probabilidade de transição para qualquer estado y \(\geq\)2 é insignificante, começando com qualquer estado x \(\geq\)2. Embora existam muitos desses estados, é fácil ver que limão y→+∞ P(x, y) P(x, y + 1) = limão y→+∞ (1 −¯hy)x −(1 −¯hy−1)x (1 −¯hy+1)x −(1 −¯hy)x = limão y→+∞ ¯hy−1 −¯hy ¯hy −¯hy+1 = 1 ¯h = 1 1-h. Portanto, cada linha x da matriz de transição P diminui como uma sequência geométrica com taxa 1 1-h > 2 quando y é grande o suficiente, e o mesmo vale para P (k). Assim, quando k é grande o suficiente, mas ainda assim na ordem de log1/2 F, P y\(\geq\)2 P (k)(x, y) < F para qualquer x \(\geq\)2. Ou seja, com uma probabilidade esmagadora o Adversário perde o jogo e não consegue prever Qr−1 na rodada r −k. Para h \(\in\)(2/3, 1], mais análise complexa mostra que existe uma constante C ligeiramente maior que 1/2, tal que é suficiente tomar k = O(logC F). Assim, o Lema 5.6 é válido. ■ Lema 5.4. (reapresentado) Dadas as propriedades 1–3 para cada rodada antes de r, ph = h2(1 + h −h2) para Lr, e o líder \(\ell\)r é honesto com probabilidade de pelo menos ph. 23Por exemplo, h = 80% conforme sugerido pelas escolhas específicas de parâmetros.

Prova. Seguindo o Lema 5.6, o Adversário não pode prever Qr−1 na rodada r −k, exceto com probabilidade desprezível. Observe que isso não significa que a probabilidade de um líder honesto seja h para cada rodada. Na verdade, dado o Qr-1, dependendo de quantos usuários mal-intencionados existem no início do a permutação aleatória de PKr−k, o Adversário pode ter mais de uma opção para Qr e portanto, pode aumentar a probabilidade de um líder malicioso na rodada r + 1 - mais uma vez estamos dando a ele algumas vantagens irrealistas como no Lema 5.6, de modo a simplificar a análise. No entanto, para cada Qr−1 que não foi questionado a H pelo Adversário na rodada r −k, por qualquer x \(\geq\)1, com probabilidade (1 −h)x−1h o primeiro usuário honesto ocorre na posição x no resultado permutação aleatória de PKr−k. Quando x = 1, a probabilidade de um líder honesto na rodada r + 1 é na verdade h; enquanto quando x = 2, o Adversário tem duas opções para Qr e a probabilidade resultante é h2. Somente considerando estes dois casos, temos que a probabilidade de um líder honesto na rodada r + 1 é pelo menos h \(\cdot\) h + (1 −h)h \(\cdot\) h2 = h2(1 + h −h2) conforme desejado. Observe que a probabilidade acima considera apenas a aleatoriedade no protocolo da rodada r −k para arredondar r. Quando toda a aleatoriedade da rodada 0 à rodada r é levada em consideração, Qr−1 é ainda menos previsível para o Adversário e a probabilidade de um líder honesto na rodada r + 1 é de pelo menos h2(1 + h −h2). Substituindo r + 1 por r e retrocedendo tudo em uma rodada, o líder \(\ell\)r é honesto com probabilidade de pelo menos h2(1 + h −h2), conforme desejado. Da mesma forma, em cada etapa s de inversão genuína da moeda, o “líder” dessa etapa - que é o verificador em SV r,s cuja credencial tem o menor valor hash, é honesto com probabilidade de pelo menos h2(1 + h-h2). Assim ph = h2(1 + h −h2) para Lr e o Lema 5.4 é válido. ■

Algorand ′

2 Nesta seção, construímos uma versão de Algorand ′ trabalhando sob a seguinte suposição. Suposição da maioria honesta dos usuários: Mais de 2/3 dos usuários em cada PKr são honestos. Na Seção 8, mostramos como substituir a suposição acima pela desejada Maioria Honesta de Suposição de dinheiro. 6.1 Notações e parâmetros adicionais para Algorand ′ 2 Notações • \(\mu\) \(\in\)Z+: um limite superior pragmático para o número de etapas que, com probabilidade esmagadora, será realmente obtido em uma rodada. (Como veremos, o parâmetro \(\mu\) controla quantos eventos efêmeros chaves que um usuário prepara antecipadamente para cada rodada.) • Lr: uma variável aleatória que representa o número de tentativas de Bernoulli necessárias para obter 1, quando cada tentativa é 1 com probabilidade ph 2. Lr será usado para limitar o tempo necessário para gerar bloco Ir. • tH: um limite inferior para o número de verificadores honestos em uma etapa s > 1 da rodada r, tal que com probabilidade esmagadora (dados n e p), existem > tH verificadores honestos em SV r,s. Parâmetros • Relações entre vários parâmetros. — Para cada passo s > 1 da rodada r, n é escolhido de modo que, com probabilidade esmagadora,

|HSV r,s| >tH e |HSV r,s| + 2|MSV r,s| < 2tH. Observe que as duas desigualdades acima juntas implicam |HSV r,s| > 2|MSV r,s|: isto é, há é uma maioria honesta de 2/3 entre os verificadores selecionados. Quanto mais próximo de 1 for o valor de h, menor será n. Em particular, usamos (variantes de) Chernoffbounds para garantir que as condições desejadas se mantenham com uma probabilidade esmagadora. • Exemplos de escolhas de parâmetros importantes. — F = 10−18. — n \(\approx\)4000, tH \(\approx\)0,69n, k = 70. 6.2 Implementando chaves efêmeras em Algorand ′ 2 Lembre-se que um verificador i \(\in\)SV r,s assina digitalmente sua mensagem mr,s eu da etapa s na rodada r, em relação a uma chave pública efêmera pkr,s i , usando uma chave secreta efêmera skr,s eu que ele destrua prontamente depois de usar. Quando o número de passos possíveis que uma rodada pode dar é limitado por um determinado inteiro \(\mu\), já vimos como lidar de forma prática com chaves efêmeras. Por exemplo, como nós explicaram em Algorand ′ 1 (onde \(\mu\) = m + 3), para lidar com todas as suas possíveis chaves efêmeras, de uma rodada r′ para uma rodada r′ + 106, i gera um par (PMK, SMK), onde PMK mestre público chave de um esquema de assinatura baseado em identidade e SMK sua chave mestra secreta correspondente. Usuário eu divulga PMK e usa SMK para gerar a chave secreta de cada chave pública efêmera possível (e destrói SMK depois de fazer isso). O conjunto de chaves públicas efêmeras de i para o relevante rodadas é S = {i} \(\times\) {r′,. . . , r′ + 106} \(\times\) {1, . . . , \(\mu\)}. (Conforme discutido, à medida que a rodada r′ + 106 se aproxima, eu “atualizo” seu par (PMK, SMK).) Na prática, se \(\mu\) for grande o suficiente, uma rodada de Algorand ′ 2 não levará mais do que \(\mu\) passos. Em princípio, no entanto, existe a possibilidade remota de que, para alguma rodada r, o número de etapas realmente tomadas excederá \(\mu\). Quando isso acontecer, eu não conseguirei assinar a mensagem dele, Sr. eu para qualquer passo s > \(\mu\), porque ele preparou antecipadamente apenas \(\mu\) chaves secretas para a rodada r. Além disso, ele não poderia preparar e divulgar um novo estoque de chaves efêmeras, conforme discutido anteriormente. Na verdade, fazer então, ele precisaria inserir uma nova chave mestra pública PMK′ em um novo bloco. Mas, deveria arredondar r Se você desse mais e mais passos, nenhum novo bloco seria gerado. No entanto, existem soluções. Por exemplo, posso usar a última chave efêmera da rodada r, pkr,\(\mu\) eu , como segue. Ele gera outro estoque de pares de chaves para a rodada r - por exemplo, (1) gerando outro par de chaves mestras (PMK, SMK); (2) usar este par para gerar outras, digamos, 106 chaves efêmeras, sk r,\(\mu\)+1 eu , . . . , sk r,\(\mu\)+106 eu , correspondendo às etapas \(\mu\)+1, ..., \(\mu\)+106 da rodada r; (3) usando skr,\(\mu\) eu para digitalmente assine PMK (e qualquer mensagem (r, \(\mu\)) se i \(\in\)SV r,\(\mu\)), relativa a pkr,\(\mu\) eu ; e (4) apagar SMK e skr,\(\mu\) eu . Devo me tornar um verificador em uma etapa \(\mu\) + s com s \(\in\){1, . . . , 106}, então eu assino digitalmente seu (r, \(\mu\) + s)- mensagem senhor,\(\mu\)+s eu em relação à sua nova chave pk r,\(\mu\)+s eu = (eu, r, \(\mu\) + s). Claro, para verificar esta assinatura de i, outros precisam ter certeza de que esta chave pública corresponde à nova chave mestra pública PMK de i. Assim, além desta assinatura, i transmite sua assinatura digital de PMK relativa a pkr,\(\mu\) eu . É claro que esta abordagem pode ser repetida quantas vezes forem necessárias, caso a rodada r continue para mais e mais passos! A última chave secreta efêmera é usada para autenticar um novo público mestre chave e, portanto, outro estoque de chaves efêmeras para a rodada r. E assim por diante.6.3 O protocolo real Algorand ′ 2 Lembre-se novamente que, em cada etapa s de uma rodada r, um verificador i \(\in\)SV r,s usa seu segredo público de longo prazo par de chaves para produzir sua credencial, \(\sigma\)r,s eu \(\triangleq\)SIGi(r, s, Qr−1), bem como SIGi Qr-1 no caso s = 1. O verificador i usa seu par de chaves efêmeras, (pkr,s eu, skr,s i ), para assinar qualquer outra mensagem m que possa ser necessário. Para simplificar, escrevemos esigi(m), em vez de sigpkr,s i (m), para denotar o efêmero próprio de i assinatura de m nesta etapa e escreva ESIGi(m) em vez de SIGpkr,s eu (m) \(\triangleq\)(eu, m, esigi(m)). Etapa 1: bloquear proposta Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 1 da rodada r assim que tiver CERT r−1, que permite que i calcule H(Br−1) e Qr−1 de forma inequívoca. • O usuário i usa Qr−1 para verificar se i \(\in\)SV r,1 ou não. Se i /\(\in\)SV r,1, ele não faz nada na Etapa 1. • Se i \(\in\)SV r,1, ou seja, se i for um líder potencial, então ele faz o seguinte. (a) Se eu vi B0, . . . , o próprio Br−1 (qualquer Bj = Bj ǫ pode ser facilmente derivado de seu valor hash no CERT j e, portanto, é assumido como “visto”), então ele coleta os pagamentos da rodada r que foram foi propagado para ele até agora e calcula um conjunto de pagamento máximo PAY r eu deles. (b) Se eu não vi todo B0,. . . , Br−1 ainda, então ele define PAY r eu = \(\emptyset\). (c) Em seguida, i calcula seu “bloco de candidatos” Br eu = (r, PAGAR r eu, SIGi(Qr−1), H(Br−1)). (c) Finalmente, i calcula a mensagem mr,1 eu = (Br eu , esigi(H(Br eu )), \(\sigma\)r,1 i ), destrói seu efêmero chave secreta skr,1 i , e então propaga duas mensagens, mr,1 eu e (SIGi(Qr−1), \(\sigma\)r,1 eu), separadamente, mas simultaneamente.a aQuando i é o líder, SIGi(Qr−1) permite que outros calculem Qr = H(SIGi(Qr−1), r).

Propagação Seletiva Para encurtar a execução global do Passo 1 e de toda a rodada, é importante que o (r, 1)- as mensagens são propagadas seletivamente. Ou seja, para cada usuário j no sistema, • Para a primeira mensagem (r, 1) que ele recebe e verifica com sucesso, se ela contém um bloco ou é apenas uma credencial e uma assinatura de Qr−1, o jogador j o propaga normalmente. • Para todas as outras mensagens (r, 1) que o jogador j recebe e verifica com sucesso, ele propaga somente se o valor hash da credencial que ela contém for o menor entre os valores hash das credenciais contidas em todas as mensagens (r, 1) que ele recebeu e verificou com sucesso para longe. • Entretanto, se j receber duas mensagens diferentes no formato mr,1 eu do mesmo jogador i,b ele descarta o segundo, não importa qual seja o valor hash da credencial de i. Observe que, na propagação seletiva, é útil que cada líder potencial i propague seu credencial \(\sigma\)r,1 eu separadamente do senhor,1 i:c essas pequenas mensagens viajam mais rápido que os blocos, certifique-se propagação oportuna do mr,1 i é onde as credenciais contidas têm valores hash pequenos, enquanto fazer com que aqueles com valores hash grandes desapareçam rapidamente. aOu seja, todas as assinaturas estão corretas e, se for no formato mr,1 i , tanto o bloco quanto seu hash são válidos —embora j não verifique se o conjunto de pagamentos incluído é máximo para i ou não. bO que significa que eu sou malicioso. cAgradecemos a Georgios Vlachos por sugerir isso.Etapa 2: A primeira etapa do GC do protocolo de consenso graduado Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 2 da rodada r assim que tiver CERT r-1. • O usuário i espera um tempo máximo t2 \(\triangleq\) \(\lambda\) + Λ. Enquanto espero, ajo da seguinte maneira. 1. Depois de esperar pelo tempo 2\(\lambda\), ele encontra o usuário \(\ell\) tal que H(\(\sigma\)r,1 \(\ell\)) \(\leq\)H(\(\sigma\)r,1 j) para todos credenciais \(\sigma\)r,1 j que fazem parte das mensagens (r, 1) verificadas com sucesso que ele recebeu até agora.a 2. Se ele tem recebido um bloquear Br−1, qual partidas o hash valor H(Br−1) contido no CERT r−1,b e se ele recebeu de \(\ell\)uma mensagem válida mr,1 \(\ell\) = (Irmão \(\ell\), esig\(\ell\)(H(Br \(\ell\))), \(\sigma\)r,1 \(\ell\)),c então eu paro de esperar e defino v′ eu \(\triangleq\)(H(Br \(\ell\)), \(\ell\)). 3. Caso contrário, quando o tempo t2 acabar, i define v′ eu \(\triangleq\) \(\bot\). 4. Quando o valor de v′ i foi definido, eu calcula Qr−1 a partir do CERT r−1 e verifica se i \(\in\)SV r,2 ou não. 5. Se i \(\in\)SV r,2, i calcula a mensagem mr,2 eu \(\triangleq\)(ESIGi(v′ eu), \(\sigma\)r,2 i),d destrói seu efêmero chave secreta skr,2 i , e então propaga mr,2 eu. Caso contrário, eu para sem propagar qualquer coisa. aEssencialmente, o usuário i decide em particular que o líder da rodada r é o usuário \(\ell\). bClaro, se CERT r−1 indicar que Br−1 = Br−1 ǫ , então eu já “recebi” Br−1 no momento em que ele recebeu CERT r-1. cNovamente, as assinaturas do jogador \(\ell\) e os hashes foram todos verificados com sucesso e PAGUE r \(\ell\)no Brasil \(\ell\)é um conjunto de pagamento válido para rodada r - embora eu não verifique se PAY r \(\ell\)é máximo para \(\ell\)ou não. Se irmão \(\ell\) contém um conjunto de pagamentos vazio, então na verdade, não há necessidade de ver Br−1 antes de verificar se Br \(\ell\)é válido ou não. dA mensagem senhor,2 eu sinaliza que o jogador i considera o primeiro componente de v′ i será o hash do próximo bloco, ou considera o próximo bloco vazio.

Etapa 3: A segunda etapa do GC Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 3 da rodada r assim que tiver CERT r-1. • O usuário i espera um tempo máximo t3 \(\triangleq\)t2 + 2\(\lambda\) = 3\(\lambda\) + Λ. Enquanto espero, eu ajo como segue. 1. Se existe um valor v tal que ele recebeu pelo menos mensagens válidas mr,2 j de a forma (ESIGj(v), \(\sigma\)r,2 j ), sem qualquer contradição,a então ele para de esperar e define v' = v. 2. Caso contrário, quando o tempo t3 acabar, ele define v′ = \(\bot\). 3. Quando o valor de v′ for definido, i calcula Qr−1 a partir do CERT r−1 e verifica se i \(\in\)SV r,3 ou não. 4. Se i \(\in\)SV r,3, então i calcula a mensagem mr,3 eu \(\triangleq\)(ESIGi(v′), \(\sigma\)r,3 i ), destrói seu chave secreta efêmera skr,3 i , e então propaga mr,3 eu. Caso contrário, eu paro sem propagar qualquer coisa. aOu seja, ele não recebeu duas mensagens válidas contendo ESIGj(v) e um ESIGj(ˆv) diferente respectivamente, de um jogador j. Aqui e daqui em diante, exceto nas Condições Finais definidas posteriormente, sempre que um jogador honesto deseja mensagens de um determinado formato, mensagens contraditórias nunca são contadas ou consideradas válidas.

Etapa 4: Resultado do GC e a primeira etapa do BBA⋆ Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia sua própria Etapa 4 da rodada r assim que ele termina seu próprio Passo 3. • O usuário i espera um tempo máximo 2\(\lambda\).a Enquanto espera, i age da seguinte forma. 1. Ele calcula vi e gi, a saída do GC, como segue. (a) Se existe um valor v′ ̸= \(\bot\)tal que ele recebeu pelo menos tH mensagens válidas senhor,3 j = (ESIGj(v′), \(\sigma\)r,3 j ), então ele para de esperar e define vi \(\triangleq\)v′ e gi \(\triangleq\)2. (b) Se ele recebeu pelo menos as mensagens válidas mr,3 j = (ESIGj(\(\bot\)), \(\sigma\)r,3 j ), então ele para esperando e define vi \(\triangleq\) \(\bot\) e gi \(\triangleq\)0.b (c) Caso contrário, quando o tempo 2\(\lambda\) acabar, se existir um valor v′ ̸= \(\bot\)tal que ele tenha recebeu pelo menos ⌈tH 2 ⌉mensagens válidas senhor,j j = (ESIGj(v′), \(\sigma\)r,3 j ), então ele define vi \(\triangleq\)v′ e gi \(\triangleq\)1.c (d) Caso contrário, quando o tempo 2\(\lambda\) acabar, ele define vi \(\triangleq\) \(\bot\) e gi \(\triangleq\)0. 2. Quando os valores vi e gi forem definidos, i calcula bi, a entrada de BBA⋆, como segue: bi \(\triangleq\)0 se gi = 2, e bi \(\triangleq\)1 caso contrário. 3. i calcula Qr−1 a partir do CERT r−1 e verifica se i \(\in\)SV r,4 ou não. 4. Se i \(\in\)SV r,4, ele calcula a mensagem mr,4 eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,4 i ), destrói seu chave secreta efêmera skr,4 i , e propaga mr,4 eu. Caso contrário, eu para sem propagar qualquer coisa. aAssim, o tempo total máximo desde que i inicia sua Etapa 1 da rodada r poderia ser t4 \(\triangleq\)t3 + 2\(\lambda\) = 5\(\lambda\) + Λ. bSe a Etapa (b) estiver ou não no protocolo, isso não afeta sua correção. No entanto, a presença da Etapa (b) permite que a Etapa 4 termine em menos de 2\(\lambda\) se um número suficiente de verificadores da Etapa 3 tiver “assinado \(\bot\)”. cPode-se provar que v′ neste caso, se existir, deve ser único.Etapa s, 5 \(\leq\)s \(\leq\)m + 2, s −2 ≡0 mod 3: Uma etapa de BBA⋆ com moeda fixada em 0 Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia suas próprias etapas da rodada r assim que ele termina seu próprio Passo s −1. • O usuário i espera um tempo máximo 2\(\lambda\).a Enquanto espera, i age da seguinte forma. – Condição Final 0: Se em algum ponto existe uma string v ̸= \(\bot\) e um passo s′ tal que (a) 5 \(\leq\)s′ \(\leq\)s, s′ −2 ≡0 mod 3 - isto é, a etapa s′ é uma etapa fixada em moeda em 0, (b) recebi pelo menos tH mensagens válidas mr,s′−1 j = (ESIGj(0), ESIGj(v), \(\sigma\)r,s′−1 j ),b e (c) i recebeu uma mensagem válida (SIGj(Qr−1), \(\sigma\)r,1 j) com j sendo o segundo componente de v, então, eu para de esperar e termina sua própria execução do Passo s (e de fato da rodada r) imediatamente, sem propagar nada como um verificador (r, s); define H(Br) como o primeiro componente de v; e define seu próprio CERT r como o conjunto de mensagens mr,s′−1 j da etapa (b) junto com (SIGj(Qr−1), \(\sigma\)r,1 j ).c – Condição Final 1: Se em algum ponto existir um passo s′ tal que (a') 6 \(\leq\)s′ \(\leq\)s, s′ −2 ≡1 mod 3 - isto é, a etapa s′ é uma etapa fixada em moeda para 1, e (b') i recebeu pelo menos tH mensagens válidas mr,s′−1 j = (ESIGj(1), ESIGj(vj), \(\sigma\)r,s′−1 j ),d então, eu para de esperar e termina sua própria execução do Passo s (e de fato da rodada r) certo afastado sem propagar nada como um verificador (r, s); define Br = Br ǫ; e define o seu próprio CERT r será o conjunto de mensagens mr,s′−1 j da subetapa (b'). – Se em qualquer ponto ele tem recebido em menos o válido senhor,s−1 j é de o formulário (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele para de esperar e define bi \(\triangleq\)1. – Se em qualquer ponto ele tem recebido em menos o válido senhor,s−1 j é de o formulário (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), mas eles não concordam sobre o mesmo v, então ele para esperando e define bi \(\triangleq\)0. – Caso contrário, quando o tempo 2\(\lambda\) acabar, i define bi \(\triangleq\)0. – Quando o valor bi for definido, i calcula Qr−1 a partir do CERT r−1 e verifica se eu \(\in\)SV r,s. – Se i \(\in\)SV r,s, i calcula a mensagem mr,s eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) com vi sendo o valor que ele calculou na Etapa 4, destrói sua chave secreta efêmera skr,s eu, e então propaga senhor,s eu. Caso contrário, paro sem propagar nada. aAssim, o tempo total máximo desde que i inicia sua Etapa 1 da rodada r poderia ser ts \(\triangleq\)ts−1 + 2\(\lambda\) = (2s −3)\(\lambda\) + Λ. bEssa mensagem do jogador j é contada mesmo que o jogador i também tenha recebido uma mensagem de j assinando por 1. Coisas semelhantes para a Condição Final 1. Conforme mostrado na análise, isso é para garantir que todos os usuários honestos saibam CERT r dentro do tempo \(\lambda\) um do outro. cO usuário i agora conhece H(Br) e sua própria rodada termina. Ele só precisa esperar até que o bloco Br esteja propagado para ele, o que pode levar algum tempo adicional. Ele ainda ajuda a propagar mensagens como um usuário genérico, mas não inicia nenhuma propagação como um verificador (r, s). Em particular, ele ajudou a propagar todas as mensagens em seu CERT r, que é suficiente para o nosso protocolo. Observe que ele também deve definir bi \(\triangleq\)0 para o protocolo BA binário, mas bi não é necessário neste caso de qualquer maneira. Coisas semelhantes para todas as instruções futuras. dNeste caso, não importa quais são os vj’s. 65Etapa s, 6 \(\leq\)s \(\leq\)m + 2, s −2 ≡1 mod 3: Uma etapa de BBA⋆ fixada em moeda para 1 Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia suas próprias etapas da rodada r assim que ele termina seu próprio Passo s −1. • O usuário i espera um tempo máximo de 2\(\lambda\). Enquanto espero, ajo da seguinte maneira. – Condição Final 0: As mesmas instruções da etapa Coin-Fixed-To-0. – Condição Final 1: As mesmas instruções da etapa Coin-Fixed-To-0. – Se em qualquer ponto ele tem recebido em menos o válido senhor,s−1 j é de o formulário (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele para de esperar e define bi \(\triangleq\)0.a – Caso contrário, quando o tempo 2\(\lambda\) acabar, i define bi \(\triangleq\)1. – Quando o valor bi for definido, i calcula Qr−1 a partir do CERT r−1 e verifica se eu \(\in\)SV r,s. – Se i \(\in\)SV r,s, i calcula a mensagem mr,s eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) com vi sendo o valor que ele calculou na Etapa 4, destrói sua chave secreta efêmera skr,s eu, e então propaga senhor,s eu. Caso contrário, paro sem propagar nada. aObserve que receber mensagens válidas (r, s −1) assinadas para 1 significaria a Condição Final 1. Etapa s, 7 \(\leq\)s \(\leq\)m + 2, s −2 ≡2 mod 3: Uma etapa de BBA⋆ com moeda genuinamente invertida Instruções para cada usuário i \(\in\)PKr−k: O usuário i inicia suas próprias etapas da rodada r assim que ele termina seu próprio passo s −1. • O usuário i espera um tempo máximo de 2\(\lambda\). Enquanto espero, ajo da seguinte maneira. – Condição Final 0: As mesmas instruções da etapa Coin-Fixed-To-0. – Condição Final 1: As mesmas instruções da etapa Coin-Fixed-To-0. – Se em qualquer ponto ele tem recebido em menos o válido senhor,s−1 j é de o formulário (ESIGj(0), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele para de esperar e define bi \(\triangleq\)0. – Se em qualquer ponto ele tem recebido em menos o válido senhor,s−1 j é de o formulário (ESIGj(1), ESIGj(vj), \(\sigma\)r,s−1 j ), então ele para de esperar e define bi \(\triangleq\)1. – Caso contrário, quando o tempo 2\(\lambda\) acabar, deixando SV r,s−1 eu seja o conjunto de (r, s −1)-verificadores de a quem ele recebeu uma mensagem válida mr,s−1 j , i define bi \(\triangleq\)lsb(minj\(\in\)SV r,s−1 eu H(\(\sigma\)r,s−1 j )). – Quando o valor bi for definido, i calcula Qr−1 a partir do CERT r−1 e verifica se eu \(\in\)SV r,s. – Se i \(\in\)SV r,s, i calcula a mensagem mr,s eu \(\triangleq\)(ESIGi(bi), ESIGi(vi), \(\sigma\)r,s i) com vi sendo o valor que ele calculou na Etapa 4, destrói sua chave secreta efêmera skr,s eu, e então propaga senhor,s eu. Caso contrário, paro sem propagar nada. Observação. Em princípio, conforme considerado na subseção 6.2, o protocolo pode levar arbitrariamente muitas passos em alguma rodada. Caso isso aconteça, conforme discutido, um usuário i \(\in\)SV r,s com s > \(\mu\) esgotou

seu estoque de chaves efêmeras pré-geradas e precisa autenticar sua mensagem (r, s) mr,s eu por um “cascata” de chaves efêmeras. Assim, a mensagem de i torna-se um pouco mais longa e a transmissão é mais longa as mensagens levarão um pouco mais de tempo. Assim, depois de tantas etapas de uma determinada rodada, o valor de o parâmetro \(\lambda\) aumentará ligeiramente automaticamente. (Mas ele reverte para o \(\lambda\) original uma vez que um novo bloco é produzido e uma nova rodada começa.) Reconstrução do Bloco Round-r por Não-Verificadores Instruções para cada usuário i no sistema: O usuário i inicia sua própria rodada r assim que tiver CERT r-1. • sigo as instruções de cada etapa do protocolo, participa da propagação de todos mensagens, mas não inicia nenhuma propagação em uma etapa se ele não for um verificador nela. • i termina sua própria rodada r inserindo a Condição Final 0 ou a Condição Final 1 em alguma etapa, com o CERT r correspondente. • A partir daí, ele inicia sua rodada r + 1 enquanto espera para receber o bloco real Br (a menos que ele já recebeu), cujo hash H(Br) foi definido pelo CERT r. Novamente, se CERT r indica que Br = Br ǫ, o i conhece Br no momento em que possui CERT r. 6.4 Análise de Algorand ′ 2 A análise de Algorand ′ 2 é facilmente derivado daquele de Algorand ′ 1. Essencialmente, em Algorand ′ 2, com probabilidade esmagadora, (a) todos os usuários honestos concordam com o mesmo bloco Br; o líder de um novo O bloco é honesto com probabilidade de pelo menos ph = h2(1 + h −h2).

Lidando com usuários honestos off-line

Como dissemos, um usuário honesto segue todas as instruções prescritas, que incluem a de estar online e executando o protocolo. Este não é um grande fardo em Algorand, uma vez que o cálculo e a largura de banda exigida de um usuário honesto é bastante modesta. No entanto, vamos salientar que Algorand pode ser facilmente modificável para funcionar em dois modelos, nos quais usuários honestos podem ficar off-line em grandes números. Antes de discutir estes dois modelos, salientamos que, se a percentagem de jogadores honestos eram 95%, Algorand ainda poderia ser executado definindo todos os parâmetros assumindo que h = 80%. Conseqüentemente, Algorand continuaria a funcionar corretamente mesmo que no máximo metade dos jogadores honestos optaram por ficar off-line (na verdade, um caso importante de “absenteísmo”). Na verdade, em qualquer momento, pelo menos 80% dos jogadores online seriam honestos. Da participação contínua à honestidade preguiçosa Como vimos, Algorand ′ 1 e Algorand ′ 2 escolha o parâmetro de retrospectiva k. Vamos agora mostrar que escolher k adequadamente grande permite remover o requisito de participação contínua. Este requisito garante uma propriedade crucial: a saber, que o protocolo BA subjacente BBA⋆tem uma maioria honesta adequada. Vamos agora explicar o quão preguiçoso a honestidade fornece uma maneira alternativa e atraente de satisfazer essa propriedade.

Lembre-se de que um usuário i é preguiçoso, mas honesto se (1) seguir todas as instruções prescritas, quando ele é convidado a participar do protocolo e (2) ele é convidado a participar apenas do protocolo muito raramente - por exemplo, uma vez por semana - com aviso prévio adequado e potencialmente recebendo recompensas quando ele participa. Para permitir que Algorand trabalhe com tais players, basta “escolher os verificadores do rodada atual entre os usuários que já estão no sistema em uma rodada muito anterior.” Na verdade, lembre-se que os verificadores para uma rodada r são escolhidos entre os usuários da rodada r −k, e as seleções são feitas com base na quantidade Qr−1. Observe que uma semana consiste em aproximadamente 10.000 minutos e suponha que um rodada leva aproximadamente (por exemplo, em média) 5 minutos, então uma semana tem cerca de 2.000 rodadas. Suponha que, em algum momento, um usuário deseja planejar seu tempo e saber se ele estará um verificador na próxima semana. O protocolo agora escolhe os verificadores para uma rodada r entre os usuários em arredondar r −k −2.000, e as seleções são baseadas em Qr−2.001. Na rodada r, jogador que eu já conheço os valores Qr −2.000, . . . , Qr−1, uma vez que na verdade fazem parte do blockchain. Então, para cada M entre 1 e 2.000, i é um verificador em uma etapa s da rodada r + M se e somente se .H SIGi r + M, s, Qr+M−2.001 \(\leq\)p. Assim, para verificar se ele será chamado para atuar como verificador nas próximas 2.000 rodadas, devo calcular \(\sigma\)M,s eu =SIGi r + M, s, Qr+M−2.001 para M = 1 a 2.000 e para cada etapa s, e verifique se .H(\(\sigma\)M,s eu ) \(\leq\)p para alguns deles. Se o cálculo de uma assinatura digital levar um milissegundo, então toda esta operação levará cerca de 1 minuto de cálculo. Se ele não for selecionado como verificador em qualquer uma dessas rodadas, ele poderá ficar off-line com uma “consciência honesta”. Se ele tivesse continuamente participou, ele teria essencialmente dado 0 passos nas próximas 2.000 rodadas de qualquer maneira! Se, em vez disso, ele é selecionado para ser um verificador em uma dessas rodadas, então ele se prepara (por exemplo, obtendo todos as informações necessárias) para atuar como um verificador honesto na rodada apropriada. Ao agir assim, um verificador de potencial preguiçoso, mas honesto, apenas deixa de participar da propagação. de mensagens. Mas a propagação de mensagens é normalmente robusta. Além disso, os pagadores e os beneficiários de espera-se que os pagamentos propagados recentemente estejam on-line para observar o que acontece com seus pagamentos, e assim participarão da propagação da mensagem, se forem honestos.

Protocolo Algorand ′ com maioria honesta de dinheiro

Agora, finalmente, mostramos como substituir a suposição da maioria honesta dos usuários pela hipótese muito mais suposição significativa da Maioria Honesta do Dinheiro. A ideia básica é (em um sabor proof-of-stake) “selecionar um usuário i \(\in\)PKr−k para pertencer a SV r,s com um peso (ou seja, poder de decisão) proporcional a a quantidade de dinheiro possuída por i.”24 Pela nossa suposição HMM, podemos escolher se essa quantia deve ser detida na rodada r −k ou no (início da) rodada r. Supondo que não nos importamos com a participação contínua, optamos por a última escolha. (Para eliminar a participação contínua, teríamos optado pela primeira opção. Melhor dizendo, pela quantidade de dinheiro possuída na rodada r −k −2.000.) Existem muitas maneiras de implementar essa ideia. A maneira mais simples seria manter cada tecla pressionada no máximo 1 unidade de dinheiro e então selecione aleatoriamente n usuários i de PKr−k tal que a(r) eu = 1. 24Deveríamos dizer PKr−k−2.000 para substituir a participação contínua. Por simplicidade, uma vez que se pode querer exigir de qualquer forma, com participação contínua, usamos PKr-k como antes, para carregar um parâmetro a menos.

A próxima implementação mais simples A próxima implementação mais simples pode ser exigir que cada chave pública possua uma quantidade máxima de dinheiro M, para algum M fixo. O valor M é pequeno o suficiente comparado com a quantidade total de dinheiro dinheiro no sistema, de modo que a probabilidade de uma chave pertencer ao conjunto verificador de mais de um intervir —digamos— k rodadas é insignificante. Então, uma chave i \(\in\)PKr−k, possuindo uma quantia de dinheiro a(r) eu na rodada r, é escolhido para pertencer a SV r,s se .H SIGi r, s, Qr−1 \(\leq\)p \(\cdot\) uma(r) eu M . E tudo continua como antes. Uma implementação mais complexa A última implementação “forçou um participante rico no sistema a possuir muitas chaves”. Uma implementação alternativa, descrita abaixo, generaliza a noção de status e considera cada usuário i consiste em K + 1 cópias (i, v), cada uma das quais é selecionada independentemente para ser um verificador, e possuirá sua própria chave efêmera (pkr,s eu,v, skr,s i,v) em uma etapa s de uma rodada r. O valor K depende sobre a quantidade de dinheiro a(r) eu propriedade de i na rodada r. Vejamos agora como esse sistema funciona com mais detalhes. Número de cópias Seja n a cardinalidade esperada desejada de cada conjunto de verificadores e seja a(r) eu seja a quantidade de dinheiro pertencente a um usuário i na rodada r. Seja Ar a quantidade total de dinheiro possuído pelos usuários em PKr−k na rodada r, ou seja, Ar = X i\(\in\)P Kr−k um(r) eu. Se i for um usuário em PKr−k, então as cópias de i são (i, 1), . . . , (i, K + 1), onde K = $ n \(\cdot\) uma(r) eu Ar % . Exemplo. Seja n = 1.000, Ar = 109 e a(r) eu = 3,7 milhões. Então, K = 103 \(\cdot\) (3,7 \(\cdot\) 106) 109  = ⌊3,7⌋= 3 . Verificadores e credenciais Seja eu um usuário em PKr−k com K + 1 cópias. Para cada v = 1,. . . , K, copy (i, v) pertence a SV r,s automaticamente. Ou seja, a credencial de i é \(\sigma\)r,s i,v \(\triangleq\)SIGi((i, v), r, s, Qr−1), mas a condição correspondente torna-se .H(\(\sigma\)r,s i,v) \(\leq\)1, que é sempre verdadeiro. Para cópia (i, K + 1), para cada etapa s da rodada r, i verifica se .H SIGi (eu, K + 1), r, s, Qr−1 \(\leq\)a(r) eu n Ar-K.

Se sim, a cópia (i, K + 1) pertence a SV r,s. Para provar isso, i propaga a credencial \(\sigma\)r,1 i,K+1 = SIGi (eu, K + 1), r, s, Qr−1 . Exemplo. Como no exemplo anterior, seja n = 1K, a(r) eu = 3,7M, Ar = 1B e i tem 4 cópias: (i, 1), . . . , (eu, 4). Então, as primeiras 3 cópias pertencem a SV r,s automaticamente. Para o 4º, conceitualmente, Algorand ′ lança independentemente uma moeda viciada, cuja probabilidade de cara é 0,7. Copiar (i, 4) é selecionado se e somente se o lançamento da moeda for Cara. (É claro que esse lançamento de moeda tendencioso é implementado hashing, assinando e comparando - como fazemos fiz o tempo todo neste artigo - para me permitir provar seu resultado.) Negócios como sempre Tendo explicado como os verificadores são selecionados e como suas credenciais são calculada a cada etapa de uma rodada r, a execução de uma rodada é semelhante à já explicada.

Tratamento de forks

Tendo reduzido a probabilidade de bifurcações para 10-12 ou 10-18, é praticamente desnecessário lidar com na remota chance de ocorrerem. Algorand, no entanto, também pode empregar vários fork procedimentos de resolução, com ou sem comprovação de trabalho. Uma forma possível de instruir os usuários a resolver bifurcações é a seguinte: • Siga a cadeia mais longa se um usuário vir várias cadeias. • Se houver mais de uma cadeia mais longa, siga aquela com um bloco não vazio no final. Se todos eles têm blocos vazios no final, considere seus penúltimos blocos. • Se houver mais de uma cadeia mais longa com blocos não vazios no final, digamos que as cadeias sejam de comprimento r, siga aquele cujo líder do bloco r possui a menor credencial. Se houver laços, siga aquele cujo bloco r tem o menor valor hash. Se ainda houver empates, siga o aquele cujo bloco r é ordenado lexicograficamente em primeiro lugar.

Lidando com partições de rede

Como dito, assumimos que os tempos de propagação das mensagens entre todos os usuários da rede são limitados por \(\lambda\) e Λ. Esta não é uma suposição forte, já que a Internet de hoje é rápida e robusta, e os valores reais desses parâmetros são bastante razoáveis. Aqui, vamos ressaltar que Algorand ′ 2 continua a funcionar mesmo que a Internet ocasionalmente seja dividida em duas partes. O caso quando a Internet é dividida em mais de duas partes de maneira semelhante. 10.1 Partições Físicas Em primeiro lugar, a partição pode ser causada por motivos físicos. Por exemplo, um grande terremoto pode acabarão por quebrar completamente a ligação entre a Europa e a América. Neste caso, o usuários mal-intencionados também são particionados e não há comunicação entre as duas partes. Assim

haverá dois Adversários, um para a parte 1 e outro para a parte 2. Cada Adversário ainda tenta quebrar o protocolo em sua própria parte. Suponha que a partição aconteça no meio da rodada r. Então cada usuário ainda é selecionado como um verificador baseado em PKr−k, com a mesma probabilidade de antes. Deixe HSV r,s eu e MSV r,s eu respectivamente seja o conjunto de verificadores honestos e maliciosos em uma etapa s da parte i \(\in\){1, 2}. Nós temos |HSV r,s 1 | + |MSV r,s 1 | + |HSV r,s 2 | + |MSV r,s 2 | = |HSV r,s| + |MSV r,s|. Observe que |HSV r,s| + |MSV r,s| < |HSV r,s| + 2|MSV r,s| < 2tH com probabilidade esmagadora. Se alguma parte i tiver |HSV r,s eu | + |MSV r,s eu | \(\geq\)tH com probabilidade não desprezível, por exemplo, 1%, então o probabilidade de que |HSV r,s 3−eu| + |MSV r,s 3−eu| \(\geq\)tH é muito baixo, por exemplo, 10−16 quando F = 10−18. Neste caso, podemos muito bem tratar a parte menor como estando off-line, porque não haverá verificadores suficientes em esta parte para gerar as assinaturas para certificar um bloco. Consideremos a parte maior, digamos a parte 1, sem perda de generalidade. Embora |HSV r,s| < tH com probabilidade desprezível em cada passo s, quando a rede é particionada, |HSV r,s 1 | pode ser menor que tH com alguma probabilidade não desprezível. Neste caso o Adversário pode, com alguma outra probabilidade não desprezível, forçar o protocolo BA binário em uma bifurcação na rodada r, com um bloco não vazio Br e o bloco vazio Br ǫ ambos com assinaturas válidas.25 Por exemplo, em um Coin-Fixed-To-0 step s, todos os verificadores em HSV r,s 1 assinado para o bit 0 e H(Br), e propagou seus mensagens. Todos os verificadores em MSV r,s 1 também assinaram 0 e H(Br), mas retiveram suas mensagens. Porque |HSV r,s 1 | + |MSV r,s 1 | \(\geq\)tH, o sistema possui assinaturas suficientes para certificar o Br. No entanto, desde o verificadores maliciosos retiveram suas assinaturas, os usuários entram na etapa s + 1, que é uma etapa Coin-Fixed-To1. Porque |HSV r,s 1 | < tH devido à partição, os verificadores em HSV r,s+1 1 não vi assinaturas para o bit 0 e todas assinadas para o bit 1. Todos os verificadores em MSV r,s+1 1 fez o mesmo. Porque |HSV r,s+1 1 | + |MSV r,s+1 1 | \(\geq\)tH, o sistema possui assinaturas suficientes para certificar Br ǫ. O Adversário em seguida, cria uma bifurcação liberando as assinaturas do MSV r,s 1 para 0 e H(Br). Assim, haverá dois Qr’s, definidos pelos blocos correspondentes da rodada r. No entanto, a bifurcação não continuará e apenas um dos dois ramos poderá crescer na rodada r + 1. Instruções adicionais para Algorand ′ 2. Ao ver um bloco não vazio Br e o bloco vazio bloco BR ǫ , segue o não vazio (e o Qr definido por ele). Na verdade, ao instruir os usuários a usarem o bloco não vazio no protocolo, se um grande quantidade de usuários honestos em PKr+1−k percebem que há uma bifurcação no início da rodada r +1, então o o bloco vazio não terá seguidores suficientes e não crescerá. Suponha que o adversário consiga particionar os usuários honestos para que alguns usuários honestos vejam Br (e talvez Br ǫ), e alguns só veem irmão ǫ. Porque o Adversário não pode dizer qual deles será um verificador seguindo Br e qual será um verificador seguindo o Ir. ǫ , os usuários honestos são particionados aleatoriamente e cada um deles ainda torna-se um verificador (seja em relação a Br ou em relação a Br ǫ) em uma etapa s > 1 com probabilidade pág. Para os usuários mal-intencionados, cada um deles pode ter duas chances de se tornar um verificador, uma com Br e outro com Br ǫ, cada um com probabilidade p independentemente. Seja HSV r+1,s 1;Br seja o conjunto de verificadores honestos nas etapas s da rodada r+1 após Br. Outras notações como HSV r+1,s 1;Brǫ , MSV r+1,s 1;Br e MSV r+1,s 1;Brǫ são definidos de forma semelhante. Por Chernoffbound, é fácil 25Ter uma bifurcação com dois blocos não vazios não é possível com ou sem partições, exceto com partições insignificantes probabilidade.ver isso com uma probabilidade esmagadora, |HSV r+1,s 1;Br | + |HSV r+1,s 1;Brǫ | + |MSV r+1,s 1;Br | + |MSV r+1,s 1;Brǫ | < 2tH. Conseqüentemente, as duas filiais não podem ter ambas as assinaturas adequadas certificando um bloco para rodada r + 1 na mesma etapa s. Além disso, uma vez que as probabilidades de seleção para duas etapas s e s′ são as iguais e as seleções são independentes, também com probabilidade esmagadora |HSV r+1,s 1;Br | + |MSV r+1,s 1;Br | + |HSV r+1,s′ 1;Brǫ | + |MSV r+1,s′ 1;Brǫ | < 2tH, para quaisquer duas etapas s e s′. Quando F = 10−18, pelo sindicato, desde que o Adversário não possa particionar os usuários honestos por um longo tempo (digamos 104 etapas, o que equivale a mais de 55 horas com \(\lambda\) = 10 segundos26), com alta probabilidade (digamos 1−10−10) no máximo uma ramificação terá as assinaturas adequadas para certificar um bloco na rodada r + 1. Finalmente, se a partição física criou duas partes com aproximadamente o mesmo tamanho, então o probabilidade de que |HSV r,s eu | + |MSV r,s eu | \(\geq\)tH é pequeno para cada parte i. Seguindo uma análise semelhante, mesmo que o Adversário consiga criar uma bifurcação com alguma probabilidade não desprezível em cada parte para a rodada r, no máximo um dos quatro ramos pode crescer na rodada r + 1. 10.2 Partição Adversária Em segundo lugar, a partição pode ser causada pelo Adversário, de modo que as mensagens propagadas pelos usuários honestos de uma parte não alcançará diretamente os usuários honestos da outra parte, mas o Adversário é capaz de encaminhar mensagens entre as duas partes. Ainda assim, uma vez que uma mensagem de um parte chega a um usuário honesto na outra parte, será propagada nesta última como de costume. Se o O adversário está disposto a gastar muito dinheiro, é concebível que ele consiga hackear o Internet e particione-o assim por um tempo. A análise é semelhante à da parte maior da partição física acima (a parte menor parte pode ser considerada como tendo população 0): o Adversário pode ser capaz de criar uma bifurcação e cada usuário honesto vê apenas um dos ramos, mas no máximo um ramo pode crescer. 10.3 Partições de rede em soma Embora possam ocorrer partições de rede e uma bifurcação em uma rodada possa ocorrer nas partições, não há ambigüidade persistente: um garfo dura muito pouco e, na verdade, dura no máximo uma única rodada. Em todas as partes da partição, exceto no máximo uma, os usuários não podem gerar um novo bloco e, portanto, (a) perceber que há uma partição na rede e (b) nunca confiar em blocos que irão “desaparecer”. Agradecimentos Gostaríamos de agradecer primeiro a Sergey Gorbunov, co-autor do citado sistema Democoin. Os mais sinceros agradecimentos a Maurice Herlihy, pelas muitas discussões esclarecedoras, por apontar que o pipelining melhorará o desempenho da taxa de transferência de Algorand e melhorará muito o 26Observe que um usuário termina uma etapa s sem esperar pelo tempo 2\(\lambda\) somente se ele tiver visto pelo menos as assinaturas para o mesma mensagem. Quando não há assinaturas suficientes, cada etapa durará 2\(\lambda\).

exposição de uma versão anterior deste artigo. Muito obrigado a Sergio Rajsbaum, pelos seus comentários sobre uma versão anterior deste artigo. Muito obrigado a Vinod Vaikuntanathan, por várias discussões profundas e percepções. Muito obrigado a Yossi Gilad, Rotem Hamo, Georgios Vlachos e Nickolai Zeldovich por começar a testar essas ideias e por muitos comentários e discussões úteis. Silvio Micali gostaria de agradecer pessoalmente a Ron Rivest pelas inúmeras discussões e orientações em pesquisa criptográfica ao longo de mais de 3 décadas, pela coautoria do sistema de micropagamento citado que inspirou um dos mecanismos de seleção de verificadores de Algorand. Esperamos levar esta tecnologia para o próximo nível. Enquanto isso a viagem e o companheirismo são muito divertidos, pelos quais estamos muito gratos.