Introdução
“A geração de números aleatórios é importante demais para ser deixada ao acaso.”
Robert Cavue, 1970
Este artigo é dedicado à aplicação prática de soluções que utilizam geração coletiva de números aleatórios em um ambiente não confiável. Resumindo, como e por que o aleatório é usado em blockchains, e um pouco sobre como distinguir o aleatório “bom” do “ruim”. Gerar um número verdadeiramente aleatório é um problema extremamente difícil, mesmo em um único computador, e tem sido estudado há muito tempo por criptógrafos. Pois bem, em redes descentralizadas a geração de números aleatórios é ainda mais complexa e importante.
É em redes onde os participantes não confiam uns nos outros que a capacidade de gerar um número aleatório indiscutível nos permite resolver eficazmente muitos problemas críticos e melhorar significativamente os esquemas existentes. Além disso, jogos de azar e loterias não são o objetivo número um aqui, como pode parecer à primeira vista ao leitor inexperiente.
Geração de números aleatórios
Os computadores não podem gerar números aleatórios sozinhos; eles precisam de ajuda externa para fazê-lo. O computador pode obter algum valor aleatório, por exemplo, dos movimentos do mouse, da quantidade de memória usada, das correntes parasitas nos pinos do processador e de muitas outras fontes chamadas fontes de entropia. Esses valores em si não são completamente aleatórios, pois estão em uma determinada faixa ou possuem um padrão previsível de mudanças. Para transformar esses números em um número verdadeiramente aleatório dentro de um determinado intervalo, criptotransformações são aplicadas a eles para produzir valores pseudo-aleatórios distribuídos uniformemente a partir dos valores distribuídos desigualmente da fonte de entropia. Os valores resultantes são chamados de pseudoaleatórios porque não são verdadeiramente aleatórios, mas são derivados deterministicamente da entropia. Qualquer bom algoritmo criptográfico, ao criptografar dados, produz textos cifrados que deveriam ser estatisticamente indistinguíveis de uma sequência aleatória, portanto para produzir aleatoriedade pode-se pegar uma fonte de entropia, que fornece apenas boa repetibilidade e imprevisibilidade de valores mesmo em intervalos pequenos, o o resto do trabalho é dispersar e misturar bits. O valor resultante será assumido pelo algoritmo de criptografia.
Para completar um breve programa educacional, acrescentarei que gerar números aleatórios mesmo em um dispositivo é um dos pilares para garantir a segurança de nossos dados. Os números pseudo-aleatórios gerados são usados para estabelecer conexões seguras em várias redes, para gerar chaves criptográficas, para balanceamento de carga, monitoramento de integridade e para muitos outros aplicativos. A segurança de muitos protocolos depende da capacidade de gerar um aleatório confiável e externamente imprevisível, armazená-lo e não revelá-lo até a próxima etapa do protocolo, caso contrário a segurança será comprometida. Um ataque a um gerador de valores pseudoaleatórios é extremamente perigoso e ameaça imediatamente todos os softwares que utilizam geração aleatória.
Você deve saber de tudo isso se fez um curso básico de criptografia, então vamos continuar sobre redes descentralizadas.
Aleatório em blockchains
Em primeiro lugar, falarei sobre blockchains com suporte a contratos inteligentes; são eles que podem aproveitar plenamente as oportunidades oferecidas pela aleatoriedade inegável e de alta qualidade. Além disso, para ser breve, chamarei essa tecnologia de “Beacons aleatórios publicamente verificáveis”Ou PVRB. Como blockchains são redes nas quais as informações podem ser verificadas por qualquer participante, a parte principal do nome é “Publicamente Verificável”, ou seja, Qualquer pessoa pode usar cálculos para obter provas de que o número resultante postado na blockchain possui as seguintes propriedades:
- O resultado deve ter uma distribuição comprovadamente uniforme, ou seja, ser baseado em criptografia comprovadamente forte.
- Não é possível controlar nenhum dos bits do resultado. Como consequência, o resultado não pode ser previsto antecipadamente.
- Você não pode sabotar o protocolo de geração não participando do protocolo ou sobrecarregando a rede com mensagens de ataque
- Todos os itens acima devem ser resistentes ao conluio de um número permitido de participantes desonestos do protocolo (por exemplo, 1/3 dos participantes).
Qualquer possibilidade de um grupo menor de participantes em conluio produzir até mesmo um aleatório par/ímpar controlado é uma falha de segurança. Qualquer capacidade do grupo de impedir a emissão de informações aleatórias é uma falha de segurança. Em geral os problemas são muitos e esta tarefa não é fácil...
Parece que a aplicação mais importante do PVRB são vários jogos, loterias e, geralmente, qualquer tipo de jogo no blockchain. Na verdade, esta é uma direção importante, mas a aleatoriedade nas blockchains tem aplicações ainda mais importantes. Vamos dar uma olhada neles.
Algoritmos de consenso
O PVRB desempenha um papel importante na organização do consenso da rede. As transações em blockchains são protegidas por uma assinatura eletrônica, portanto um “ataque a uma transação” é sempre a inclusão/exclusão de uma transação em um bloco (ou vários blocos). E a principal tarefa do algoritmo de consenso é chegar a um acordo sobre a ordem dessas transações e a ordem dos blocos que incluem essas transações. Além disso, uma propriedade necessária para blockchains reais é a finalidade – a capacidade da rede de concordar que a cadeia até o bloco finalizado é final e nunca será excluída devido ao aparecimento de uma nova bifurcação. Normalmente, para concordar que um bloco é válido e, mais importante, final, é necessário coletar assinaturas da maioria dos produtores de blocos (doravante denominados BP - produtores de blocos), o que requer pelo menos a entrega da cadeia de blocos para todos os BPs e distribuindo assinaturas entre todos os BPs. À medida que o número de BPs cresce, o número de mensagens necessárias na rede cresce exponencialmente, portanto, algoritmos de consenso que exigem finalidade, usados por exemplo no consenso Hyperledger pBFT, não funcionam na velocidade necessária, partindo de várias dezenas de BPs, exigindo um grande número de conexões.
Se houver um PVRB inegável e honesto na rede, então, mesmo na aproximação mais simples, pode-se escolher um dos produtores de blocos com base nele e nomeá-lo como “líder” durante uma rodada do protocolo. Se tiver-mos N produtores de blocos, dos quais M: M > 1/2 N são honestos, não censuram transações e não bifurcam a cadeia para realizar um ataque de “gasto duplo”, então usar um PVRB incontestado uniformemente distribuído permitirá escolher um líder honesto com probabilidade M / N (M / N > 1/2). Se cada líder receber seu próprio intervalo de tempo durante o qual ele pode produzir um bloco e validar a cadeia, e esses intervalos forem iguais no tempo, então a cadeia de blocos de BPs honestos será mais longa do que a cadeia formada por BPs maliciosos, e o consenso algoritmo depende do comprimento da cadeia. simplesmente descartará o “ruim”. Este princípio de alocar fatias iguais de tempo para cada BP foi aplicado pela primeira vez no Graphene (o antecessor do EOS), e permite que a maioria dos blocos sejam fechados com uma única assinatura, o que reduz bastante a carga da rede e permite que esse consenso funcione de forma extremamente rápida e de forma constante. Porém, a rede EOS agora passa a utilizar blocos especiais (Último Bloco Irreversível), que são confirmados pelas assinaturas de 2/3 BP. Esses blocos servem para garantir a finalidade (impossibilidade de uma bifurcação da cadeia começar antes do último último bloco irreversível).
Além disso, em implementações reais, o esquema do protocolo é mais complicado - a votação nos blocos propostos é realizada em várias etapas para manter a rede em caso de falta de blocos e problemas com a rede, mas mesmo levando isso em consideração, algoritmos de consenso usando PVRB exigem significativamente menos mensagens entre BPs, o que permite torná-las mais rápidas que o PVFT tradicional, ou suas diversas modificações.
O representante mais proeminente de tais algoritmos: da equipe Cardano, que é considerada matematicamente demonstrável contra o conluio da BP.
No Ouroboros, o PVRB é usado para definir o chamado “agendamento BP” - um cronograma segundo o qual cada BP recebe seu próprio horário para publicação de um bloco. A grande vantagem da utilização do PVRB é a completa “igualdade” dos BPs (de acordo com o tamanho dos seus balanços). A integridade do PVRB garante que BPs maliciosos não possam controlar o agendamento de intervalos de tempo e, portanto, não possam manipular a cadeia preparando e analisando os forks da cadeia com antecedência, e para selecionar um fork basta simplesmente confiar no comprimento do cadeia, sem usar métodos complicados para calcular a “utilidade” do BP e o “peso” de seus blocos.
Em geral, em todos os casos em que é necessário escolher um participante aleatório numa rede descentralizada, o PVRB é quase sempre a melhor escolha, em vez de uma opção determinística baseada, por exemplo, num hash de bloco. Sem o PVRB, a capacidade de influenciar a escolha de um participante leva a ataques nos quais o atacante pode escolher entre vários futuros para escolher o próximo participante corrupto ou vários de uma vez para garantir uma participação maior na decisão. O uso do PVRB desacredita esses tipos de ataques.
Dimensionamento e balanceamento de carga
O PVRB também pode ser de grande benefício em tarefas como redução de carga e escalonamento de pagamentos. Para começar, faz sentido se familiarizar com Rivesta “Bilhetes de Loteria Eletrônica como Micropagamentos”. A idéia geral é que, em vez de fazer pagamentos de 100 1c do pagador para o beneficiário, você pode jogar em uma loteria honesta com um prêmio de 1$ = 100c, onde o pagador dá ao banco um de 1 de seus “bilhetes de loteria” para cada Pagamento 100c. Um desses ingressos ganha um pote de US$ 1, e é esse ingresso que o destinatário pode registrar no blockchain. O mais importante é que os restantes 99 bilhetes sejam transferidos entre o destinatário e o pagador sem qualquer participação externa, através de um canal privado e na velocidade desejada. Uma boa descrição do protocolo baseado neste esquema na rede Emercoin pode ser lida .
Este esquema tem alguns problemas, tais como o destinatário pode deixar de servir o pagador imediatamente após receber um bilhete premiado, mas para muitas aplicações especiais, tais como facturação por minuto ou assinaturas electrónicas de serviços, estes podem ser negligenciados. O principal requisito, claro, é a imparcialidade da loteria, e para sua implementação um PVRB é absolutamente necessário.
A escolha de um participante aleatório também é extremamente importante para protocolos de sharding, cujo objetivo é escalar horizontalmente a cadeia de blocos, permitindo que diferentes BPs processem apenas o seu escopo de transações. Esta é uma tarefa extremamente difícil, especialmente em termos de segurança ao mesclar fragmentos. A seleção justa de um BP aleatório com o propósito de atribuir os responsáveis por um fragmento específico, como em algoritmos de consenso, também é tarefa do PVRB. Em sistemas centralizados, os shards são atribuídos por um balanceador; ele simplesmente calcula o hash da solicitação e o envia ao executor necessário. Nas blockchains, a capacidade de influenciar esta atribuição pode levar a um ataque ao consenso. Por exemplo, o conteúdo das transações pode ser controlado por um invasor, ele pode controlar quais transações vão para o fragmento que ele controla e manipular a cadeia de blocos nele contida. Você pode ler uma discussão sobre o problema do uso de números aleatórios para tarefas de fragmentação no Ethereum
Sharding é um dos problemas mais ambiciosos e sérios no campo do blockchain; sua solução permitirá construir redes descentralizadas de desempenho e volume fantásticos. O PVRB é apenas um dos blocos importantes para resolvê-lo.
Jogos, protocolos econômicos, arbitragem
É difícil superestimar o papel dos números aleatórios na indústria de jogos. O uso explícito em casinos online e o uso implícito no cálculo dos efeitos da ação de um jogador são problemas extremamente difíceis para redes descentralizadas, onde não há como confiar numa fonte central de aleatoriedade. Mas a selecção aleatória também pode resolver muitos problemas económicos e ajudar a construir protocolos mais simples e eficientes. Suponha que em nosso protocolo haja disputas sobre o pagamento de alguns serviços baratos, e essas disputas ocorrem muito raramente. Neste caso, se houver um PVRB indiscutível, clientes e vendedores podem concordar em resolver disputas aleatoriamente, mas com uma determinada probabilidade. Por exemplo, com 60% de probabilidade o cliente ganha e com 40% de probabilidade o vendedor ganha. Esta abordagem, que é absurda do primeiro ponto de vista, permite resolver litígios automaticamente com uma proporção de ganhos/perdas precisamente previsível, o que é adequado para ambas as partes, sem qualquer participação de terceiros e perda de tempo desnecessária. Além disso, a razão de probabilidade pode ser dinâmica e depender de algumas variáveis globais. Por exemplo, se uma empresa está a ir bem, tem um baixo número de disputas e uma elevada rentabilidade, a empresa pode automaticamente mudar a probabilidade de resolução de uma disputa para a centralização no cliente, por exemplo 70/30 ou 80/20, e vice-versa, se as disputas exigirem muito dinheiro e forem fraudulentas ou inadequadas, você poderá mudar a probabilidade na outra direção.
Um grande número de protocolos descentralizados interessantes, tais como registos com curadoria de tokens, mercados de previsão, curvas de títulos e muitos outros, são jogos económicos em que o bom comportamento é recompensado e o mau comportamento é penalizado. Freqüentemente, eles contêm problemas de segurança para os quais as proteções entram em conflito entre si. O que está protegido de um ataque de “baleias” com bilhões de tokens (“big stake”) fica vulnerável a ataques de milhares de contas com saldos pequenos (“sybil stake”), e medidas tomadas contra um único ataque, como não- taxas lineares criadas para tornar não lucrativo trabalhar com uma grande participação são geralmente desacreditadas por outro ataque. Como se trata de um jogo económico, os pesos estatísticos correspondentes podem ser calculados antecipadamente, bastando substituir as comissões por aleatórias com a distribuição adequada. Essas comissões probabilísticas são implementadas de forma extremamente simples se o blockchain tiver uma fonte confiável de aleatoriedade e não exigir cálculos complexos, dificultando a vida tanto das baleias quanto das sibilas.
Ao mesmo tempo, é preciso lembrar ainda que o controle de um único bit nessa aleatoriedade permite trapacear, reduzindo e aumentando as probabilidades pela metade, portanto, um PVRB honesto é o componente mais importante de tais protocolos.
Onde encontrar o aleatório certo?
Em teoria, a seleção aleatória justa em redes descentralizadas torna quase todos os protocolos comprovadamente seguros contra conluio. A lógica é bastante simples: se a rede concordar com um único bit 0 ou 1 e menos da metade dos participantes forem desonestos, então, dadas iterações suficientes, a rede terá a garantia de chegar a um consenso sobre esse bit com uma probabilidade fixa. Simplesmente porque um aleatório honesto escolherá 51 entre 100 participantes em 51% das vezes. Mas isso é em teoria, porque... em redes reais, para garantir o nível de segurança dos artigos, são necessárias muitas mensagens entre hosts, criptografia complexa de múltiplas passagens e qualquer complicação do protocolo adiciona imediatamente novos vetores de ataque.
É por isso que ainda não vemos um PVRB comprovadamente resistente em blockchains, que teria sido usado por tempo suficiente para ser testado por aplicações reais, múltiplas auditorias, cargas e, claro, ataques reais, sem os quais é difícil chamar um produto verdadeiramente seguro.
No entanto, existem várias abordagens promissoras, diferem em muitos detalhes e uma delas certamente resolverá o problema. Com recursos de computação modernos, a teoria criptográfica pode ser traduzida de forma bastante inteligente em aplicações práticas. No futuro, teremos prazer em falar sobre implementações de PVRB: agora existem várias delas, cada uma com seu próprio conjunto de propriedades e recursos de implementação importantes, e por trás de cada uma há uma boa ideia. Não há muitas equipes envolvidas na randomização e a experiência de cada uma delas é extremamente importante para todas as demais. Esperamos que a nossa informação permita que outras equipas avancem mais rapidamente, tendo em conta a experiência dos seus antecessores.
Fonte: habr.com