Eleição de Líder de Randomness Beacons e Outras Estratégias

A eleição de líder em uma configuração de blockchain visa selecionar o participante que determinará o próximo bloco a ser anexado ao blockchain. Normalmente, um validador é escolhido por slot do conjunto de validadores e obtém o direito de estender a cadeia com um novo bloco nesse slot. (Presumimos que os validadores mantêm o tempo preciso e concordam com o número do slot atual.) Neste artigo, exploramos estratégias para eleição de líder aleatória em protocolos de consenso. (Para saber mais sobre aleatoriedade em geral, consulte nosso artigo anterior, Aleatoriedade pública e sinalizadores de aleatoriedade, Onde examinamos protocolos independentes para gerar aleatoriedade publicamente verificável e imprevisível.) 

Por que a eleição do líder é importante

Eleger líderes honestos e atuantes é fundamental para o crescimento saudável da cadeia. Os validadores mal-intencionados não devem ser capazes de influenciar o processo de eleição de líderes para se tornarem líderes com mais frequência. Caso contrário, a produção de blocos pode cair nas mãos de partes que podem censurar transações ou interromper completamente o blockchain. Em protocolos de consenso de estilo de cadeia mais longa, um líder produzindo um bloco inválido (ou nenhum bloco) pode fazer com que a cadeia se bifurque temporariamente. Nos protocolos de consenso do estilo BFT, um líder ruim aciona um subprotocolo de alteração de visualização que incorrerá em uma sobrecarga de comunicação. 

A alternativa eleitoral do comitê

A eleição do comitê é um problema relacionado, onde o objetivo é selecionar um subconjunto uniformemente aleatório dos validadores de algum tamanho fixo k. Essa funcionalidade é útil por si só porque os subcomitês geralmente são necessários nas configurações de blockchain para reduzir o tamanho do conjunto de validadores para tornar o consenso mais rápido (entre muitos exemplos estão classificação de Algorand e Seleção do comitê da Ethereum). Mas a eleição do comitê também é útil para a eleição do líder, permitindo que os validadores evitem executar novamente um protocolo de eleição do líder se o líder eleito não comparecer. Se, em vez de um líder, for eleito um comitê com ordem fixa, o segundo membro do comitê pode se tornar líder se o primeiro não estiver disponível. 

As propriedades de um bom protocolo eleitoral

Em um protocolo de eleição de líderes, os líderes devem ser imprevisíveis. Se um invasor descobrir quem é o próximo líder, poderá lançar um ataque de negação de serviço (DoS) contra ele para impedi-lo de publicar um bloco. O invasor poderia então derrubar o próximo líder e assim por diante, parando o blockchain. A imprevisibilidade também pode ser fortalecida para garantir que o próprio validador não saiba quando vai liderar, o que pode ser importante para a prevenção de suborno.

O processo de eleição do líder deve ter as três propriedades a seguir:

• justiça: cada validador honesto tem uma probabilidade de 1/N ser eleito de um conjunto de N validadores (uma noção relaxada de a justiça da teoria dos jogos permite construindo a eleição do líder mesmo na presença de uma maioria maliciosa, embora com um limite inferior não constante no número de rodadas).
• Imprevisibilidade: o adversário não aprende o próximo líder até algum tempo T antes do líder anunciar o próximo bloco.
• Singularidade: exatamente um líder é escolhido em cada slot.

Eleição do líder secreto

A eleição do líder secreto é uma eleição imprevisível com T = 0. Neste processo, o líder não é conhecido por ninguém até que publique o bloco. Isso elimina completamente a janela para um ataque DoS: antes que o líder se revele, o invasor não sabe a quem atacar, tornando sua melhor estratégia um palpite aleatório. E depois que o líder publica seu bloco, é tarde demais para atacar porque o líder já cumpriu sua responsabilidade com o protocolo. 

A noção de “depois que o líder publica seu bloco” é na verdade uma simplificação, porque não temos transmissão instantânea no mundo real. Um invasor com uma posição de rede forte pode perceber um líder transmitindo um bloco primeiro e ser capaz de corromper rapidamente o líder, criar um bloco diferente e executar a transmissão original. 

Embora este seja um modelo de atacante muito forte, foram propostas defesas contra ele. Algorand propôs o modelo de rasuras, em que o líder é realmente capaz de apagar a chave necessária para assinar o bloco em seu slot antes transmitindo-o, então é tarde demais para atacar no momento em que o líder realiza qualquer ação pública. Thaddeus Dryja, Quanquan C. Liu e Neha Narula, três pesquisadores do MIT Media Lab, proposto que o líder calcule um VDF em seu bloco antes da transmissão, garantindo que um invasor adaptativo não possa construir um bloco alternativo válido a tempo de aceitá-lo para o slot desejado.

Outros métodos eleitorais 

O processo de eleição de líder mais simples é rodízio, onde os líderes são eleitos em ordem determinística. Apesar desta abordagem ser previsível e, portanto, propensa a ataques DoS, ela é adequada para sistemas permissionados onde os validadores têm boa proteção DoS.

Um líder também pode ser eleito usando uma saída de um farol de aleatoriedade, se houver um disponível e confiável para ser seguro. Infelizmente, é complicado para os participantes do consenso executarem eles mesmos um protocolo de randomness beacon distribuído (DRB), uma vez que eles normalmente assumem uma noção de transmissão ou consenso confiável, o que, por sua vez, requer a eleição do líder novamente, introduzindo uma dependência circular.

Atual eleição de líder em Ethereum é um bom estudo de caso. Cada novo líder calcula uma saída da função de aleatoriedade verificável (VRF) (uma assinatura BLS no número da época) e XORs o valor na mistura. O valor da mistura no final da época i define os líderes e os subcomitês durante o período i+2. Os líderes e sua programação são previsíveis com uma época de antecedência (atualmente ~6.4 min). O protocolo está sujeito a ataques de imparcialidade, já que o último líder pode optar por publicar ou reter sua contribuição para a mistura e, assim, influenciar o resultado das próximas eleições em um bit. Se o último  k líderes conspiram, eles podem introduzir k  bits de viés e tornar mais provável a eleição de usuários mal-intencionados. A Fundação Ethereum está trabalhando ativamente em técnicas mais avançadas para a eleição de líderes que discutimos abaixo.

Eleição de líder baseada em VRF

Outra abordagem, iniciada por Algorand, É um Eleição de líder baseada em VRF, que envolve cada validador calculando privadamente uma saída VRF e verificando se a saída cai abaixo de um limite. Este procedimento já filtra a maioria dos validadores, pois o limite é escolhido de forma que cair abaixo dele é improvável. Os poucos validadores restantes revelam suas saídas VRF, e aquele com o menor valor VRF é eleito. Essa abordagem atinge a imprevisibilidade perfeita (ou sigilo), mas não garante exclusividade. Alguns dos validadores podem não receber mensagens de todos os líderes em potencial e podem presumir que o líder errado venceu a eleição, fazendo com que esses validadores se desviem da cadeia principal. 

A avaliação VRF é periodicamente semeada com a saída de um beacon de aleatoriedade para torná-lo menos previsível para os próprios validadores verem quais slots eles vão liderar. Essa propriedade impede que um invasor que comprometa silenciosamente o validador aprenda o slot quando o validador se tornar um líder e lance um ataque quando o validador estiver prestes a anunciar um bloqueio. Essa abordagem também ajuda a evitar ataques de suborno, em que um validador prova para partes externas que será um líder em um determinado slot e colhe subornos em troca de concluir alguma tarefa como líder (por exemplo, bloquear uma transação).

Tais abordagens, onde o número de líderes eleitos é uma variável aleatória, são chamadas de Eleição Probabilística do Líder (PLE). O PLE pode resultar na não eleição de dirigentes para determinado cargo. Isso equivale a eleger um líder malicioso ou offline em que o slot acabará sendo ignorado, reduzindo a eficiência do protocolo de consenso.

Mas a maior ressalva do PLE é que vários líderes podem ser eleitos, necessitando de algum tipo de procedimento de desempate. Os empates representam um risco para o consenso, pois um validador com uma entrada vencedora pode reportá-la a apenas metade da rede, podendo causar desacordo no líder escolhido. Além disso, os processos de resolução de vínculos podem demandar mais tempo e comunicação, prejudicando a eficiência. Dfinidade, discutido com mais detalhes em a primeira postagem desta série, usa um beacon de aleatoriedade baseado em VRF para eleger um único líder; no entanto, sacrifica a imprevisibilidade para fazê-lo. Idealmente, qualquer processo de escolha de um líder deve evitar totalmente os empates e ainda assim ser imprevisível, o que nos leva ao santo graal desta área de pesquisa – Eleição do Líder Único Secreto.

Eleição de líder secreto único 

O objectivo de Eleição de líder secreto único (SSLE) é selecionar um líder exclusivo de um conjunto de validadores, mantendo a imparcialidade e a imprevisibilidade. O Protocol Labs apresentou a noção como um Problema de pesquisa, e Dan Boneh, o cientista da computação de Stanford e consultor de pesquisa de criptografia a16z, com Saba Eskandarian, Lucjan Hanzlik e Nicola Greco, mais tarde oferecido uma definição formal de SSLE. Essa propriedade de unicidade evita os riscos de consenso e os custos de eficiência decorrentes dos procedimentos de desempate. Concretamente, Sarah Azouvi, do Protocol Labs, e Danielle Cappelletti, do Politecnico di Torino, mostrar que quando o SSLE é usado em comparação com o PLE em um protocolo de cadeia mais longa, os blocos podem ser finalizados significativamente mais rápido (25% mais rápido com um adversário controlando um terço da aposta). Assim, desenvolver um protocolo SSLE prático é um problema importante.

Na abordagem mais comum, que chamaremos baseado em shuffle (usado no papel SSLE original e uma proposta Ethereum SSLE), cada validador registra um nonce que parece aleatório, mas que eles podem provar que pertence a eles. Os nonces são então compilados em uma lista. A lista é embaralhada de forma que os nonces sejam desvinculados dos validadores que os enviaram; ou seja, dada a lista embaralhada, nenhum adversário pode dizer qual validador enviou qual nonce. Um índice de lista é então escolhido de acordo com um público farol de aleatoriedade, e o líder se revela provando que o nonce naquele índice da lista embaralhada pertence a eles. 

Como apenas um índice é escolhido, o protocolo baseado em shuffle sempre gera um único líder. Como o beacon aleatório é construído para gerar valores aleatórios uniformes, o protocolo também é feira: cada validador tem chances iguais de ser eleito. Além disso, se o embaralhamento for feito corretamente (ou seja, uniformemente aleatório) e os nonces se tornarem indisponíveis às identidades dos validadores, esse protocolo também alcança imprevisibilidade.

O embaralhamento é necessário porque, embora a simples escolha de um índice da lista não embaralhada com base em um beacon aleatório já forneça exclusividade e imparcialidade, a imprevisibilidade é mais difícil de alcançar: se um adversário souber qual validador enviou qual nonce, ele saberá quem enviou o nonce no horário escolhido índice e pode identificar o líder. 

As duas abordagens a seguir embaralham a lista de maneiras diferentes. O mais simples é o Proposta Ethereum SSLE, no qual n os validadores enviam seus nonces via Tor para desvincular as identidades dos validadores de seus nonces. Uma vez que todos os validadores tenham se registrado, a lista é embaralhada usando um beacon público de aleatoriedade, e os validadores se tornam líderes na ordem da lista embaralhada. Embora este esquema seja prático - a eleição deve ser realizada apenas uma vez por n slots – essa confiança no Tor pode ser indesejável (como é o caso de confiar na segurança de qualquer protocolo externo). Além disso, não é perfeitamente imprevisível: após o primeiro n-1 líderes se revelam, o final nth líder é conhecido.

Em vez de usar o Tor, o papel SSLE original tem cada registro de validador para eleição em sequência, anexando seu nonce à lista, embaralhando a lista e re-randomizando os nonces. Essa re-randomização significa que cada nonce é mapeado para uma nova string não vinculável, de modo que o validador a quem ele pertence ainda possa provar a propriedade do nonce re-randomizado. A re-randomização faz com que um adversário não possa dizer em qual posição qualquer nonce em particular acabou após o embaralhamento, assumindo que pelo menos um embaralhador é honesto.

Embora essa abordagem de embaralhamento sequencial do documento SSLE original evite a dependência do Tor e alcance as propriedades formais do SSLE, ela é cara: sempre que um novo validador se registra, ele deve postar toda a lista embaralhada no blockchain, randomizar novamente todos os nonces e fornecem uma prova de que o fizeram honestamente, o que resulta em uma quantidade linear de comunicação por validador. Com um conjunto imutável de validadores, isso deve ser feito (amortizado) uma vez por eleição, pois o líder se registra novamente depois de revelar a prova do nonce. O artigo oferece uma compensação ajustável de eficiência e previsibilidade: em vez disso, podemos embaralhar apenas um subconjunto menor da lista, reduzindo o custo, se estivermos dispostos a permitir uma pequena quantidade de previsibilidade. Alcançar um bom equilíbrio entre eficiência e segurança é um desafio e, como resultado, os protocolos SSLE ainda precisam ser amplamente utilizados na prática. 

Convenientemente, essa abordagem de embaralhamento sequencial também pode ser usada para resolver o problema de eleição do comitê, usando o beacon aleatório para escolher k índices distintos da lista como membros do comitê. Esta é uma boa conquista, pois o problema não é resolvido trivialmente por abordagens baseadas em VRF, pois a execução de um protocolo probabilístico baseado em VRF k vezes pode eleger um tamanho de comitê variável dependendo da aleatoriedade. 

Outras abordagens para SSLE

Outra abordagem baseada em shuffle é SSLE de segurança adaptativa de DDH. Esta construção é um pouco mais complicada, mas alcança uma noção mais forte de segurança, protegendo contra uma adversário adaptável no modelo de apagamentos de Algorand. Esse adversário é adaptável, pois pode escolher quais validadores corromper durante o protocolo, em vez de antes do início do protocolo. 

Um outro desafio no SSLE é eleger cada validador com probabilidade proporcional à sua aposta, em vez de uniformemente ao acaso. Os protocolos baseados em embaralhamento podem alcançar isso de forma ingênua, permitindo que cada validador registre vários nonces: um nonce para cada unidade de participação que eles possuem. No entanto, o custo de embaralhar aumenta linearmente com o número de unidades de participação S, tornando-se muito caro mesmo para distribuições de apostas realistas. um elegante SSLE baseado em MPC abordagem tem complexidade aumentando apenas com log S, e também evita a necessidade de uma configuração confiável ou beacon de aleatoriedade. No entanto, em comparação com as abordagens baseadas em embaralhamento, requer mais rodadas de comunicação (logarítmica no número de participantes) por líder eleito

***

Resumimos nossa análise nesta tabela útil.

	justiça	Imprevisibilidade/ Segredo*	Singularidade
Rodada	✓	✗	✓
Farol de aleatoriedade ideal	✓	✗	✓
Eleição do líder da Ethereum (atual)	✗	✗	✓
Eleição de líder baseada em VRF (Algorand)	✓	✓	✗
SSLE	✓	✓	✓

* O farol round-robin é totalmente previsível, mas no restante dos faróis ✗ significa que a noção é alcançada até um certo grau limitado: o farol de aleatoriedade ideal é imprevisível, mas o adversário aprende a saída ao mesmo tempo que o líder eleito; portanto, o líder eleito pode ser atacado antes de anunciar um bloqueio; O farol do Etherum é imprevisível até ~ 6 min e pode ser ligeiramente tendencioso para prejudicar a justiça; A Algorand elege vários líderes com uma pequena probabilidade.

SSLE é uma direção promissora, alcançando justiça, imprevisibilidade e singularidade. Dois desafios proeminentes enfrentados por sua adoção são a eficiência e a capacidade de acomodar distribuições de participação não uniformes. Além disso, as abordagens SSLE baseadas em shuffle que destacamos assumem a existência de um beacon aleatório imparcial, o que não é fácil de alcançar na prática. Como o SSLE foi formalmente definido apenas recentemente, é provável que vejamos protocolos aprimorados abordando seus desafios em um futuro próximo. 

***

Miranda cristo é doutoranda em Ciência da Computação na Columbia University, onde é membro do Theory Group e Presidential Fellow. Ela também é estagiária de pesquisa na cripto a16z.

José Bonneau é um parceiro de pesquisa na criptomoeda a16z. Sua pesquisa se concentra em criptografia aplicada e segurança blockchain. Ele ministrou cursos de criptomoeda na Universidade de Melbourne, NYU, Stanford e Princeton, e recebeu um doutorado em ciência da computação pela Universidade de Cambridge e bacharelado em Stanford.

Valéria Nikolaenko é um parceiro de pesquisa na criptomoeda a16z. Sua pesquisa se concentra em criptografia e segurança blockchain. Ela também trabalhou em tópicos como ataques de longo alcance em protocolos de consenso PoS, esquemas de assinatura, segurança pós-quântica e computação multipartidária. Ela é PhD em Criptografia pela Universidade de Stanford sob a orientação do professor Dan Boneh e trabalhou na blockchain Diem como parte da equipe de pesquisa principal.

***

Editor: Tim Sullivan

***

As opiniões expressas aqui são as do pessoal individual da AH Capital Management, LLC (“a16z”) citadas e não são as opiniões da a16z ou de suas afiliadas. Certas informações aqui contidas foram obtidas de fontes de terceiros, inclusive de empresas do portfólio de fundos administrados pela a16z. Embora retiradas de fontes consideradas confiáveis, a16z não verificou essas informações de forma independente e não faz representações sobre a precisão duradoura das informações ou sua adequação a uma determinada situação. Além disso, esse conteúdo pode incluir anúncios de terceiros; a16z não revisou tais anúncios e não endossa nenhum conteúdo de publicidade neles contido.

Este conteúdo é fornecido apenas para fins informativos e não deve ser considerado como aconselhamento jurídico, comercial, de investimento ou fiscal. Você deve consultar seus próprios conselheiros sobre esses assuntos. As referências a quaisquer valores mobiliários ou ativos digitais são apenas para fins ilustrativos e não constituem uma recomendação de investimento ou oferta para fornecer serviços de consultoria de investimento. Além disso, este conteúdo não é direcionado nem destinado ao uso por quaisquer investidores ou potenciais investidores, e não pode, em nenhuma circunstância, ser invocado ao tomar uma decisão de investir em qualquer fundo administrado pela a16z. (Uma oferta para investir em um fundo a16z será feita apenas pelo memorando de colocação privada, contrato de subscrição e outra documentação relevante de tal fundo e deve ser lida na íntegra.) Quaisquer investimentos ou empresas de portfólio mencionados, referidos ou descritos não são representativos de todos os investimentos em veículos administrados pela a16z, e não pode haver garantia de que os investimentos serão rentáveis ​​ou que outros investimentos realizados no futuro terão características ou resultados semelhantes. Uma lista de investimentos feitos por fundos administrados por Andreessen Horowitz (excluindo investimentos para os quais o emissor não deu permissão para a a16z divulgar publicamente, bem como investimentos não anunciados em ativos digitais negociados publicamente) está disponível em https://a16z.com/investments /.

Os gráficos e gráficos fornecidos são apenas para fins informativos e não devem ser considerados ao tomar qualquer decisão de investimento. O desempenho passado não é indicativo de resultados futuros. O conteúdo fala apenas a partir da data indicada. Quaisquer projeções, estimativas, previsões, metas, perspectivas e/ou opiniões expressas nestes materiais estão sujeitas a alterações sem aviso prévio e podem diferir ou ser contrárias às opiniões expressas por outros. Consulte https://a16z.com/disclosures para obter informações adicionais importantes.