1. Introdução
“A geração aleatória de números é importante demais para ser deixada ao acaso”
Robert Cavyu, 1970
Este artigo é dedicado à aplicação prática de soluções usando a geração coletiva de números aleatórios em um ambiente não confiável. Em resumo - como e por que o aleatório é usado em cadeias de blocos 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 computador separado, e há muito tempo é estudado por criptografadores. Bem, em redes descentralizadas, a geração aleatória de números é ainda mais complexa e importante.
É nas redes em que os participantes não confiam um no outro que a capacidade de gerar um número aleatório inegável pode efetivamente resolver muitos problemas importantes e melhorar significativamente os esquemas existentes. Além disso, jogos de azar e loterias aqui não são o objetivo número um, como um leitor inexperiente pode parecer a princípio.
Geração de números aleatórios
Os computadores não sabem como produzir números aleatórios, pois precisam de ajuda externa. Um computador pode obter algum valor aleatório usando, por exemplo, movimentos do mouse, quantidade de memória usada, correntes espúrias nos contatos do processador e muitas outras fontes chamadas fontes de entropia. Esses valores em si não são inteiramente aleatórios, pois estão em um determinado intervalo ou têm uma natureza previsível de mudanças. Para transformar esses números em um número verdadeiramente aleatório em um determinado intervalo, transformações criptográficas são aplicadas a eles para obter valores pseudo-aleatórios uniformemente distribuídos a partir dos valores desigualmente distribuídos da fonte de entropia. Os valores obtidos são chamados de pseudo-aleatórios, pois não são verdadeiramente aleatórios, mas são determinados de forma determinística a partir da entropia. Qualquer bom algoritmo criptográfico, criptografando os dados, produz textos cifrados que não devem ser estatisticamente indistinguíveis de uma sequência aleatória; portanto, para a produção de randomização, você pode usar uma fonte de entropia que fornece apenas boa repetibilidade e imprevisibilidade de valores, mesmo em pequenos intervalos, o restante do trabalho de espalhar e misturar bits. o valor resultante será assumido pelo algoritmo de criptografia.
Para concluir o breve programa educacional, acrescentarei que a geração de 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, gerar chaves criptográficas, equilibrar a carga, controlar a integridade, e para muitos outros usos. A segurança de muitos protocolos depende da capacidade de gerar dados aleatórios confiáveis e imprevisíveis de fora, salvá-los e não abri-los até a próxima etapa do protocolo; caso contrário, a segurança será comprometida. Um ataque a um gerador de valor pseudo-aleatório é extremamente perigoso e ameaça todos os softwares que usam geração aleatória de uma só vez.
Você deve saber tudo isso se tiver feito um curso básico de criptografia, então vamos continuar com redes descentralizadas.
Blockchain Random
Antes de tudo, vou falar sobre blockchains com suporte a contratos inteligentes, são eles que podem aproveitar plenamente as oportunidades oferecidas por uma aleatoriedade inegável de alta qualidade. Além disso, por questões de brevidade, chamarei essa tecnologia de " Sinalizadores aleatórios publicamente verificáveis " ou PVRB. Como blockchains são redes nas quais qualquer participante pode verificar informações, a parte principal do nome é "Publicamente verificável", ou seja, qualquer pessoa com a ajuda de cálculos pode obter prova de que o número resultante, colocado na blockchain, tem as seguintes propriedades:
- O resultado deve ter uma distribuição comprovadamente uniforme, isto é, com base em criptografia comprovadamente forte.
- Não é possível controlar nenhum dos bits do resultado. Como resultado, o resultado não pode ser previsto com antecedência.
- 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 do número permitido de participantes desonestos no protocolo (por exemplo, 1/3 dos participantes).
Qualquer oportunidade para um grupo menor de participantes conspirar para produzir até mesmo um aleatório par / ímpar controlado é uma brecha na segurança. Qualquer oportunidade para o grupo parar de emitir uma casa aleatória é uma falha de segurança. Em geral, existem muitos problemas, e essa tarefa não é fácil ...
Parece que a aplicação mais importante para o PVRB são vários jogos, loterias e geralmente qualquer tipo de jogo na blockchain. De fato, essa é uma direção importante, mas a casa aleatória em cadeias de blocos tem aplicações e mais importantes. Considere-os.
Algoritmos de consenso
O PVRB é crucial para o consenso em rede. As transações em cadeias de bloco 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 em vários blocos). E a principal tarefa do algoritmo de consenso é concordar com a ordem dessas transações e com 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 para o bloco finalizado é final e nunca será excluída devido ao aparecimento de um novo fork. Geralmente, para concordar que um bloco é válido e, o mais importante, final, você precisa coletar assinaturas da maioria dos produtores de blocos (doravante BP - produtores de blocos), o que exige pelo menos entregar uma cadeia de blocos a todos os BPs e distribuir assinaturas entre todos os BPs . À medida que o número de BPs aumenta, o número de mensagens necessárias na rede aumenta exponencialmente; portanto, algoritmos de consenso que exigem finalidade, como os usados no consenso de pBFT da Hyperledger, não funcionam na velocidade certa, a partir de várias dezenas de BPs, exigindo um grande número de conexões.
Se a rede possui um PVRB inegável e honesto, então, mesmo na aproximação mais simples, é possível selecionar um dos produtores de blocos com base nele e designá-lo como "líder" para uma rodada do protocolo. Se temos produtores de bloco N , dos quais M: M > 1/2 N são honestos, não censuram transações e não constroem cadeias de forquilhas para realizar um ataque de "gasto duplo", então usar um PVRB indisputável uniformemente distribuído permitirá que você escolha um líder honesto com probabilidade M / N (M / N > 1/2) . Se cada líder tiver 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, a cadeia de blocos honestos da BP será mais longa que a cadeia formada pela BP mal-intencionada e o algoritmo de consenso que depende do comprimento da cadeia, simplesmente descarte o "mau". Esse princípio de alocar intervalos de tempo iguais para cada BP foi aplicado pela primeira vez no Graphene (o antecessor do EOS) e permite que a maioria dos blocos seja fechada com uma única assinatura, o que reduz bastante a carga da rede e permite que esse consenso funcione de maneira extremamente rápida e constante. No entanto, as redes EOS agora precisam usar blocos especiais (Último bloco irreversível), confirmados por 2/3 de assinaturas BP. Esses blocos são usados para garantir a finalidade (a impossibilidade de uma cadeia de garfos começar antes do último bloco irreversível).
Além disso, em implementações reais, o esquema do protocolo é mais complicado - a votação dos blocos propostos é realizada em várias etapas para manter a rede em caso de falta de blocos e problemas de rede, mas mesmo com isso em mente, os algoritmos de consenso do PVRB exigem significativamente menos mensagens entre os BPs, o que permite torná-los mais rápidos que o PBFT tradicional ou suas várias modificações.
O representante mais impressionante de tais algoritmos: Ouroboros, da equipe de Cardano, que, como anunciado, tem resistência matematicamente comprovável ao conluio entre a BP.
Em Ouroboros, o PVRB é usado para definir o chamado "cronograma BP" - um cronograma segundo o qual cada BP recebe seu próprio horário para publicar um bloco. A grande vantagem do uso do PVRB são os “direitos iguais” completos da BP (de acordo com o tamanho de seus saldos). Honestidade O PVRB garante que os BPs mal-intencionados não possam controlar o cronograma de horários e, portanto, não podem manipular a cadeia preparando e analisando os garfos da cadeia com antecedência. Para selecionar um garfo, você pode simplesmente confiar no comprimento da cadeia sem usar maneiras complicadas de calcular a "utilidade" da BP e "Pesos" de seus blocos.
Em geral, em todos os casos em que um participante aleatório precisa ser selecionado em uma rede descentralizada, o PVRB é quase sempre a melhor opção, em vez de uma opção determinística baseada, por exemplo, em um hash de bloco. Sem o PVRB, a capacidade de influenciar a escolha do participante leva ao aparecimento de ataques nos quais o atacante pode, escolhendo entre várias opções para o futuro, escolher o próximo participante corrupto ou vários ao mesmo tempo, a fim de fornecer uma participação mais significativa 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 para reduzir a carga de trabalho e escalar os pagamentos. Para iniciantes, faz sentido ler o artigo da Rivest "Bilhetes de loteria eletrônicos como micropagamentos". A essência geral é que, em vez de fazer 100 pagamentos de 1c do pagador para o destinatário, você pode jogar em uma loteria honesta com um prêmio de $ 1 = 100c, onde o pagador transfere um de seus 100 "bilhetes de loteria" para o banco por cada pagamento em 1c. Um desses tickets ganha o banco $ 1, e é esse ticket que o destinatário pode fixar na blockchain. Mais importante, os 99 tickets restantes são transferidos entre o destinatário e o pagador sem nenhuma participação externa, por meio de um canal privado e na velocidade desejada. Uma boa descrição do protocolo baseado neste esquema na rede Emercoin pode ser encontrada aqui .
Esse esquema tem vários problemas, por exemplo, o destinatário pode parar de atender o pagador imediatamente após receber um bilhete premiado, mas para muitos aplicativos especiais, como cobrança por minuto ou assinaturas eletrônicas de serviços, eles podem ser negligenciados. O principal requisito, é claro, é a honestidade da loteria, e o PVRB é absolutamente necessário para a sua realização.
A escolha de um participante aleatório também é extremamente importante para protocolos de sharding, cujo objetivo é dimensionar horizontalmente a cadeia de blocos, permitindo que diferentes BPs processem apenas seu escopo de transações. Essa é uma tarefa extremamente difícil, especialmente quando se trata de segurança ao mesclar shards. A escolha honesta de um BP aleatório para atribuí-lo aos responsáveis por um fragmento específico, como em algoritmos de consenso, também é uma tarefa do PVRB. Em sistemas centralizados, os shards são atribuídos pelo balanceador, ele simplesmente calcula o hash da solicitação e o envia ao executor necessário. Nas cadeias de blocos, a capacidade de influenciar essa atribuição pode levar a um ataque ao consenso. Por exemplo, o conteúdo das transações pode ser controlado pelo invasor, ele pode controlar quais transações se enquadram no fragmento que ele controla e manipular a cadeia de blocos nele. Uma discussão sobre o problema do uso de números aleatórios para problemas de fragmentação no Ethereum pode ser encontrada aqui.
O sharding é uma das tarefas mais ambiciosas e sérias no campo da blockchain; sua solução permitirá que você construa 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 cassinos online e 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 em uma fonte central de aleatoriedade. Porém, uma escolha aleatória pode resolver muitos problemas econômicos e ajudar a criar protocolos mais simples e eficientes. Suponha que, em nosso protocolo, haja disputas sobre o pagamento de alguns serviços baratos, e essas disputas sejam bastante raras. Nesse caso, se houver um PVRB inegável, clientes e vendedores podem concordar com uma resolução aleatória de disputas, mas com uma determinada probabilidade. Por exemplo, com uma probabilidade de 60%, o cliente vence e, com uma probabilidade de 40%, o vendedor vence. Uma abordagem tão absurda, do primeiro ponto de vista, permite resolver automaticamente disputas com uma parcela precisamente previsível de ganhos / perdas, que se adapta a ambas as partes sem nenhum envolvimento de terceiros e perda desnecessária de tempo. 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á indo bem, há um número baixo de disputas e alta rentabilidade, a empresa pode mudar automaticamente a probabilidade de uma disputa ser resolvida em direção à orientação para o cliente, por exemplo, 70/30 ou 80/20 e vice-versa, se as disputas custarem muito dinheiro e são fraudulentos ou inadequados, você pode mudar a probabilidade na outra direção.
Um grande número de protocolos descentralizados interessantes, como registros com token, mercados de previsão, curvas de vínculo e muitos outros, são jogos econômicos que recompensam o bom comportamento e os maus. Eles geralmente encontram problemas de segurança, cuja proteção se contradizem. O que é protegido contra um ataque de “baleias” com bilhões de tokens (“grande participação”) é vulnerável a ataques de milhares de contas com pequenos saldos (“participação de sybil”) e medidas tomadas contra um ataque, por exemplo, comissões não lineares criadas para para fazer um bife grande funcionar desvantajoso, eles geralmente são desacreditados por outro ataque. Por se tratar de um jogo econômico, os pesos estatísticos correspondentes podem ser calculados com antecedência e simplesmente substituir as comissões por aleatórias, com a distribuição apropriada. Essas comissões probabilísticas são implementadas de maneira extremamente simples se o blockchain tiver uma fonte confiável de aleatoriedade e não exigir cálculos complexos, dificultando a vida de baleias e sibilos.
É necessário continuar lembrando que o controle de um único bit nessa aleatorização permite trapacear, reduzir e duplicar as probabilidades, para que o PVRB honesto seja o componente mais importante de tais protocolos.
Onde encontrar o aleatório correto?
Em teoria, escolhas aleatórias honestas em redes descentralizadas fornecem a segurança comprovável de quase qualquer protocolo contra conluio. A lógica é bastante simples - se a rede concordar com um bit 0 ou 1, e entre os participantes menos da metade for desonesta, então, com um número suficiente de iterações, é garantido que a rede chegue a um consenso nesse bit com uma probabilidade fixa. Só porque um acaso honesto escolherá 51 de 100 participantes em 51% dos casos. Mas isso é em teoria, porque em redes reais, para garantir um nível de segurança como nos artigos, são necessárias muitas mensagens entre hosts, criptografia complexa de várias passagens e qualquer complicação do protocolo adiciona imediatamente novos vetores de ataque.
É por isso que ainda não vemos nas cadeias de blocos um PVRB comprovado que teria sido usado tempo suficiente para ser testado por aplicativos reais, várias auditorias, cargas e, claro, ataques reais, sem os quais é difícil chamar o produto como verdadeiramente seguro.
No entanto, existem várias abordagens promissoras ao mesmo tempo, elas diferem em muitos detalhes e algumas delas definitivamente resolverão o problema. Com os recursos computacionais modernos, a teoria criptográfica é capaz de se transformar habilmente em aplicações práticas. No futuro, teremos o maior prazer em falar sobre a implementação do PVRB: agora existem vários, cada um com seu próprio conjunto de propriedades e recursos importantes na implementação e cada um com uma boa ideia. Não há muitas equipes envolvidas aleatoriamente, e a experiência de cada uma delas é extremamente importante para todos os outros. Esperamos que nossas informações permitam que outras equipes se movam mais rapidamente, levando em consideração a experiência de seus antecessores.