É possível gerar números aleatórios se não confiarmos uns nos outros? Parte 1

Oi, Habr!

Neste artigo falarei sobre a geração de números pseudoaleatórios por participantes que não confiam uns nos outros. Como veremos a seguir, implementar um gerador “quase” bom é bastante simples, mas um gerador muito bom é difícil.

Por que seria necessário gerar números aleatórios entre participantes que não confiam uns nos outros? Uma área de aplicação são as aplicações descentralizadas. Por exemplo, um aplicativo que aceita uma aposta de um participante e dobra o valor com 49% de probabilidade ou retira com 51% de probabilidade só funcionará se puder receber um número aleatório de forma imparcial. Se um invasor puder influenciar o resultado do gerador de números aleatórios e até mesmo aumentar ligeiramente sua chance de receber um pagamento no aplicativo, ele o destruirá facilmente.

Quando projetamos um protocolo distribuído de geração de números aleatórios, queremos que ele tenha três propriedades:

1. Ele deve ser imparcial. Em outras palavras, nenhum participante deve de forma alguma influenciar o resultado do gerador de números aleatórios.

2. Ele deve ser imprevisível. Em outras palavras, nenhum participante deve ser capaz de prever qual número será gerado (ou inferir qualquer uma de suas propriedades) antes de ser gerado.

3. O protocolo deve ser viável, ou seja, resistente ao fato de um determinado percentual de participantes se desconectar da rede ou tentar interromper deliberadamente o protocolo.

Neste artigo veremos duas abordagens: RANDAO + VDF e a abordagem dos códigos de eliminação. Na próxima parte, examinaremos detalhadamente a abordagem baseada em assinaturas de limite.

Mas primeiro, vejamos um algoritmo simples e comumente usado que é viável, imprevisível, mas tendencioso.

RANDO

RANDAO é uma abordagem muito simples e, portanto, bastante usada para gerar aleatoriedade. Todos os participantes da rede primeiro selecionam localmente um número pseudoaleatório e, em seguida, cada participante envia um hash do número selecionado. Em seguida, os participantes se revezam revelando os números escolhidos e realizando uma operação XOR nos números revelados, e o resultado dessa operação passa a ser o resultado do protocolo.

A etapa de publicar os hashes antes de revelar os números é necessária para que o invasor não possa escolher o seu número após ter visto os números dos demais participantes. Isso permitiria que ele determinasse praticamente sozinho a saída do gerador de números aleatórios.

Durante o curso do protocolo, os participantes precisam chegar a uma decisão comum (o chamado consenso) duas vezes: quando começar a revelar os números selecionados e, portanto, parar de aceitar hashes, e quando parar de aceitar os números selecionados e calcular o resultado aleatório número. Tomar tais decisões entre participantes que não confiam uns nos outros não é uma tarefa fácil por si só, e voltaremos a isso em artigos futuros; neste artigo assumiremos que tal algoritmo de consenso está disponível para nós.

Quais das propriedades descritas acima o RANDAO possui? É imprevisível, tem a mesma vitalidade que o protocolo de consenso subjacente, mas é tendencioso. Especificamente, um invasor pode observar a rede e, após outros participantes revelarem seus números, ele pode calcular seu XOR e decidir se revela ou não seu número para influenciar o resultado. Embora isso impeça o invasor de determinar sozinho a saída do gerador de números aleatórios, ainda lhe dá 1 bit de influência. E se os invasores controlarem vários participantes, o número de bits que eles controlam será igual ao número de participantes sob seu controle.

A influência dos atacantes pode ser bastante reduzida exigindo que os participantes revelem os números em ordem. Então o invasor só poderá influenciar o resultado se for aberto por último. Embora a influência seja significativamente menor, o algoritmo ainda é tendencioso.

RANDAO+VDF

Uma maneira de tornar RANDAO imparcial é esta: depois que todos os números são revelados e o XOR é calculado, seu resultado é inserido na entrada de uma função, que leva muito tempo para ser calculada, mas permite verificar a exatidão do cálculo muito rapidamente.

(vdf_output, vdf_proof) = VDF_compute(input) // это очень медленно
correct = VDF_verify(input, vdf_output, vdf_proof) // это очень быстро

Esta função é chamada de Função de Atraso Verificável ou VDF. Se o cálculo do resultado final demorar mais do que a etapa de divulgação do número, o invasor não será capaz de prever o efeito de mostrar ou ocultar seu número e, portanto, perderá a oportunidade de influenciar o resultado.

Desenvolver bons VDFs é extremamente difícil. Houve vários avanços recentemente, por ex. este и este aqui o que tornou o VDF mais prático na prática, e o Ethereum 2.0 planeja usar RANDAO com VDF como fonte de números aleatórios no longo prazo. Além do facto de esta abordagem ser imprevisível e imparcial, tem a vantagem adicional de ser viável se pelo menos dois participantes estiverem disponíveis na rede (assumindo que o protocolo de consenso utilizado é viável quando se trata de um número tão pequeno de participantes).

O maior desafio desta abordagem é configurar o VDF de tal forma que mesmo um participante com hardware especializado muito caro não será capaz de calcular o VDF antes do final da fase de descoberta. Idealmente, o algoritmo deveria ter uma margem de segurança significativa, digamos 10x. A figura abaixo mostra um ataque de um ator que possui um ASIC especializado que lhe permite executar um VDF mais rápido que o tempo alocado para revelar a confirmação RANDAO. Tal participante ainda pode calcular o resultado final utilizando ou não seu número, e então, com base no cálculo, escolher se deseja mostrá-lo ou não.

Para a família VDF mencionada acima, o desempenho de um ASIC dedicado pode ser 100 vezes superior ao do hardware convencional. Portanto, se a fase de implantação durar 10 segundos, o VDF calculado em tal ASIC deverá levar mais de 100 segundos para ter uma margem de segurança de 10x e, portanto, o mesmo VDF calculado em hardware comum deverá levar 100x 100 segundos = aproximadamente 3 horas.

A Fundação Ethereum planeja resolver esse problema criando seus próprios ASICs gratuitos e disponíveis publicamente. Quando isso acontecer, todos os outros protocolos também poderão tirar proveito desta tecnologia, mas até então a abordagem RANDAO+VDF não será tão viável para protocolos que não podem investir no desenvolvimento de seus próprios ASICs.

Muitos artigos, vídeos e outras informações sobre VDF foram coletados em este site.

Usamos códigos de apagamento

Nesta seção, veremos um protocolo de geração de números aleatórios que usa apagando códigos. Ele pode tolerar até ⅓ dos invasores enquanto permanece viável e permite que até ⅔ dos invasores existam antes que possam prever ou influenciar o resultado.

A ideia principal do protocolo é a seguinte. Para simplificar, vamos supor que haja exatamente 100 participantes. Suponhamos também que todos os participantes localmente possuam alguma chave privada e que as chaves públicas de todos os participantes sejam conhecidas por todos os participantes:

1. Cada participante cria localmente uma longa sequência, divide-a em 67 partes, cria códigos de apagamento para obter 100 compartilhamentos de modo que quaisquer 67 sejam suficientes para recuperar a sequência, atribui cada um dos 100 compartilhamentos a um dos participantes e os criptografa com a chave pública do mesmo participante. Todos os compartilhamentos codificados são então publicados.

2. Os participantes usam algum tipo de consenso para chegar a um acordo sobre conjuntos codificados de 67 participantes específicos.

3. Uma vez alcançado o consenso, cada participante pega os compartilhamentos codificados em cada um dos 67 conjuntos criptografados com sua chave pública, descriptografa todos esses compartilhamentos e publica todos os compartilhamentos descriptografados.

4. Depois que 67 participantes concluírem a etapa (3), todos os conjuntos acordados podem ser completamente decodificados e reconstruídos devido às propriedades dos códigos de apagamento, e o número final pode ser obtido como um XOR das linhas iniciais com as quais os participantes começaram em (1) .

Este protocolo pode ser demonstrado como imparcial e imprevisível. O número aleatório resultante é determinado após o consenso ser alcançado, mas não é conhecido por ninguém até que ⅔ dos participantes decodifiquem as partes criptografadas com sua chave pública. Assim, o número aleatório é determinado antes que informações suficientes para reconstruí-lo sejam publicadas.

O que acontece se na etapa (1) um dos participantes enviou aos outros participantes compartilhamentos codificados que não são o código de apagamento correto para alguma string? Sem alterações adicionais, diferentes participantes não conseguirão recuperar a sequência ou recuperarão sequências diferentes, o que fará com que diferentes participantes recebam um número aleatório diferente. Para evitar isso, você pode fazer o seguinte: cada participante, além das ações codificadas, também calcula Árvore Merkla todos esses compartilhamentos e envia a cada participante o próprio compartilhamento codificado e a raiz da árvore merkle, além da prova da inclusão do compartilhamento na árvore merkle. No consenso da etapa (2), os participantes concordam não apenas com um conjunto de conjuntos, mas com um conjunto de raízes específicas de tais árvores (se algum participante se desviar do protocolo e enviar diferentes raízes de árvores Merkle para diferentes participantes, e duas dessas raízes são mostradas durante o consenso, sua linha não está incluída no conjunto de resultados). Como resultado do consenso, teremos 67 linhas codificadas e as raízes correspondentes da árvore merkle de modo que haja pelo menos 67 participantes (não necessariamente os mesmos que propuseram as linhas correspondentes), que para cada uma das 67 linhas têm uma mensagem com um compartilhamento do código de apagamento e uma prova da ocorrência de seu compartilhamento na árvore correspondente desbotada.

Quando na etapa (4) o participante decifra 67 batidas para uma determinada corda e tenta reconstruir a partir delas a corda original, uma das opções é possível:

1. A string é restaurada e, se for novamente codificada para eliminação, e a árvore Merkle for calculada para os compartilhamentos calculados localmente, a raiz coincide com aquela sobre a qual o consenso foi alcançado.

2. A linha é restaurada, mas a raiz calculada localmente não corresponde àquela na qual o consenso foi alcançado.

3. A linha não é restaurada.

É fácil mostrar que se a opção (1) aconteceu para pelo menos um participante acima, então a opção (1) aconteceu para todos os participantes, e vice-versa, se a opção (2) ou (3) aconteceu para pelo menos um participante, então para todos os participantes a opção (2) ou (3) acontecerá. Assim, para cada linha do conjunto, ou todos os participantes irão recuperá-la com sucesso ou todos os participantes não conseguirão recuperá-la. O número aleatório resultante é então um XOR apenas das linhas que os participantes conseguiram recuperar.

Assinaturas de limite

Outra abordagem para a aleatoriedade é usar o que chamamos de assinaturas de limite BLS. Um gerador de números aleatórios baseado em assinaturas de limite tem exatamente as mesmas garantias que o algoritmo baseado em código de apagamento descrito acima, mas tem um número assintótico significativamente menor de mensagens enviadas pela rede para cada número gerado.

As assinaturas BLS são um design que permite que vários participantes criem uma assinatura comum para uma mensagem. Essas assinaturas são frequentemente usadas para economizar espaço e largura de banda, não exigindo o envio de várias assinaturas. 

Uma aplicação comum para assinaturas BLS em protocolos blockchain, além de gerar números aleatórios, é a assinatura em bloco em protocolos BFT. Digamos que 100 participantes criem blocos e um bloco seja considerado final se 67 deles o assinarem. Todos eles podem enviar suas partes da assinatura BLS e usar algum algoritmo de consenso para concordar com 67 delas e então mesclá-las em uma assinatura BLS. Quaisquer 67 (ou mais) partes podem ser usadas para criar a assinatura final, o que dependerá de quais 67 assinaturas foram combinadas e, portanto, pode variar, embora diferentes escolhas dos 67 participantes criem uma assinatura diferente, qualquer assinatura será válida. assinatura do bloco. Os demais participantes só precisam receber e verificar apenas uma assinatura por bloco, em vez de 67, na rede, o que reduz significativamente a carga na rede.

Acontece que se as chaves privadas usadas pelos participantes forem geradas de uma determinada maneira, não importa quais 67 assinaturas (ou mais, mas não menos) sejam agregadas, a assinatura resultante será a mesma. Isto pode ser usado como uma fonte de aleatoriedade: os participantes primeiro concordam com alguma mensagem que irão assinar (esta pode ser a saída de RANDAO ou apenas o hash do último bloco, isso realmente não importa, desde que mude a cada vez e é consistente) e crie uma assinatura BLS para ele. O resultado da geração será imprevisível até que 67 participantes forneçam suas peças, e a partir daí a saída já está pré-determinada e não pode depender da ação de nenhum participante.

Esta abordagem à aleatoriedade é viável desde que pelo menos ⅔ dos participantes online sigam o protocolo, e é imparcial e imprevisível desde que pelo menos ⅓ dos participantes sigam o protocolo. É importante observar que um invasor que controla mais de ⅓ mas menos de ⅔ dos participantes pode interromper o protocolo, mas não pode prever ou influenciar sua saída.

As próprias assinaturas de limite são um tópico muito interessante. Na segunda parte do artigo analisaremos detalhadamente como funcionam e como exatamente é necessário gerar chaves de participantes para que as assinaturas de limite possam ser utilizadas como gerador de números aleatórios.

Em conclusão

Este artigo é o primeiro de uma série de artigos técnicos de blog NEAR. NEAR é um protocolo e plataforma blockchain para desenvolvimento de aplicativos descentralizados com ênfase na facilidade de desenvolvimento e uso para usuários finais.

O código do protocolo é aberto, nossa implementação está escrita em Rust, pode ser encontrada aqui.

Você pode ver como é o desenvolvimento para NEAR e experimentar no IDE online aqui.

Você pode acompanhar todas as notícias em russo em grupo de telegramas e grupo no VKontakte, e em inglês no oficial twitter.

Até breve!

Fonte: habr.com