1. Introdução

function getAbsolutelyRandomNumer() { return 4; // returns absolutely random number! } 

Como no caso do conceito de uma cifra de criptografia absolutamente segura, os verdadeiros protocolos publicamente verificáveis ​​de sinal aleatório publicamente verificável (daqui em diante PVRB) apenas tentam chegar o mais próximo possível do esquema ideal. em redes reais em sua forma pura, não é aplicável: é necessário concordar estritamente em um bit, deve haver muitas rodadas e todas as mensagens devem ser perfeitamente rápidas e sempre entregues. Obviamente, em redes reais isso não é verdade. Portanto, ao projetar o PVRB para tarefas específicas em cadeias de blocos modernas, além da incapacidade de controlar a aleatoriedade e a força criptográfica resultantes, surgem muitos problemas puramente arquitetônicos e técnicos.

O próprio blockchain é para o PVRB essencialmente um meio de comunicação no qual mensagens = transações. Isso permite que você ignore parcialmente problemas de rede, entrega de mensagens, problemas de middleware - todos esses riscos são suportados por uma rede descentralizada e seu principal valor para o PVRB é a incapacidade de retirar ou arruinar uma transação já enviada - isso não permite que os participantes se recusem a participar do protocolo, a menos que eles tenham tido um ataque de consenso bem-sucedido. Esse nível de segurança é aceitável, portanto, o PVRB deve ser resistente a conluio entre os participantes exatamente da mesma maneira que a principal cadeia de blockchain. Além disso, isso sugere que o PVRB deve fazer parte do consenso, se a rede concordar com a cadeia principal de blocos, permita que ela concorde ao mesmo tempo no único aleatório resultante honesto. Ou, o PVRB é apenas um protocolo independente implementado por um contrato inteligente que funciona de forma assíncrona em relação a blockchain e blocos. Ambos os métodos têm suas vantagens e desvantagens, e a escolha entre eles é extremamente não trivial.

Duas maneiras de implementar o PVRB

Vamos descrever mais detalhadamente duas opções para implementar o PVRB: a versão autônoma, que funciona usando um contrato inteligente independente da blockchain, e integrada por consenso, incorporada ao protocolo segundo o qual a rede concorda em uma cadeia de blocos e inclui transações. Em todos os casos, lembrarei dos populares mecanismos de blockchain: Ethereum, EOS e todos semelhantes a eles na maneira de estabelecer e processar contratos inteligentes.

Contrato autônomo

Nesta modalidade, o PVRB é um contrato inteligente que aceita transações aleatórias do produtor (daqui em diante RP), as processa, combina os resultados e, como resultado, tem algum valor que qualquer usuário deste contrato pode obter. Esse valor não pode ser armazenado diretamente no contrato, mas ser representado apenas por dados dos quais um e apenas um valor da aleatoriedade resultante pode ser obtido de forma determinística. Nesse esquema, os RPs são usuários de blockchain e qualquer pessoa pode participar do processo de geração.

A opção de contrato autônomo é boa:

• portabilidade (os contratos podem ser arrastados de blockchain para blockchain)
• simplicidade na implementação e teste (os contratos são convenientes para escrever e testar)
• conveniência na implementação de esquemas econômicos (é fácil criar seu próprio token, cuja lógica serve aos objetivos do PVRB)
• a capacidade de executar em blockchains existentes

Também tem desvantagens:

• fortes limitações de recursos em cálculos, volume de transações e armazenamento (em outras palavras, cpu / mem / io)
• restrições às operações dentro do contrato (nem todas as instruções estão disponíveis, é difícil conectar bibliotecas externas)
• a incapacidade de organizar as mensagens mais rapidamente do que as transações estão incluídas no blockchain

Essa opção é adequada para implementar o PVRB, que deve ser executado em uma rede existente que não contém criptografia complexa e não requer um grande número de interações.

Integrado por consenso

Nesta modalidade, o PVRB é implementado no código do nó da blockchain, é incorporado ou trabalha em paralelo com a troca de mensagens entre os nós da blockchain. Os resultados do protocolo são gravados diretamente nos blocos produzidos e as mensagens do protocolo são enviadas pela rede p2p entre os nós. Como o protocolo resulta nos números a serem gravados em blocos, a rede deve chegar a um consenso sobre eles. Isso significa que as mensagens PVRB, bem como as transações, devem ser validadas por nós e incluídas em blocos para que qualquer participante da rede possa verificar a conformidade com o protocolo PVRB. Isso nos leva automaticamente à decisão óbvia - se a rede negociar consenso sobre o bloco e as transações nele, o PVRB deve fazer parte do consenso, não um protocolo independente. Caso contrário, é possível uma situação em que o bloco é válido do ponto de vista de consenso, mas o protocolo PVRB não é respeitado e, do ponto de vista do PVRB, o bloco não pode ser aceito. Portanto, se a opção “integrada por consenso” for escolhida, o PVRB se tornará uma parte importante do consenso.

Descrevendo a implementação do PVRB no nível de consenso na rede, em nenhum caso você pode ignorar os problemas de finalidade. Finalidade é um mecanismo usado no consenso determinístico, um bloqueio (e uma corrente que leva a ele) que é final e nunca será jogado fora, mesmo que um garfo paralelo apareça. Por exemplo, não existe esse mecanismo no Bitcoin - se você publicar uma cadeia de maior complexidade, ela substituirá outra menos complexa, independentemente do tamanho da cadeia. E na EOS, por exemplo, os finais são os chamados Últimos Blocos Irreversíveis, que aparecem em média a cada 432 blocos (12 * 21 + 12 * 15, pré-votação + pré-confirmação). Esse processo está aguardando essencialmente 2/3 das assinaturas dos produtores de bloco (doravante, BP). Quando os garfos mais antigos que o último LIB aparecem, eles são simplesmente descartados. Esse mecanismo permite garantir que a transação seja incluída no blockchain e nunca seja bombeada, independentemente dos recursos que o invasor possui. Além disso, os blocos finais são blocos assinados por 2/3 da BP em Hyperledger, Tendermint e outros consensos baseados em pBFT. Além disso, um protocolo para garantir a finalidade faz sentido para obter um consenso adicional, pois pode funcionar de forma assíncrona com a produção e publicação de blocos. Aqui está um bom artigo sobre a finalização do Ethereum.

A finalização é extremamente importante para usuários que, sem ela, podem ser vítimas do ataque de "gasto duplo" quando a BP "retém" os blocos e os publica depois que a rede "vê" uma boa transação. Se não houver finalização, a bifurcação publicada substitui o bloco pela transação "boa" por outra, da bifurcação "ruim", na qual os mesmos fundos são transferidos para o endereço do atacante. No caso do PVRB, os requisitos de finalidade ainda estão sendo rigorosos, pois a construção de garfos para o PVRB significa que um invasor pode preparar várias opções para uma casa aleatória, a fim de publicar o mais lucrativo para ele e limitar o tempo de um possível ataque é uma boa solução.

Portanto, a melhor opção é combinar PVRB e finalidade em um protocolo - então o bloco finalizado = finalizado aleatoriamente, e é exatamente isso que você precisa obter. Agora, os jogadores receberão aleatoriedade garantida em N segundos e podem ter certeza de que é impossível reverter ou repeti-la.

A opção integrada por consenso é boa:

• a possibilidade de implementação assíncrona com relação à produção de blocos - os blocos são produzidos como de costume, mas, paralelamente, o protocolo PVRB pode funcionar, o que não torna aleatório qualquer bloco
• a capacidade de implementar até criptografia pesada, sem as restrições impostas a contratos inteligentes
• a capacidade de organizar as mensagens mais rapidamente do que as transações estão incluídas no blockchain, por exemplo, parte do protocolo pode funcionar entre nós sem espalhar mensagens pela rede

Também tem desvantagens:

• dificuldades no teste e desenvolvimento - você precisa emular erros de rede, nós ausentes, garfos rígidos de rede
• erros de implementação requerem uma rede de hard fork

Ambos os métodos de implementação do PVRB têm direito à vida, mas a implementação inteligente de contratos em cadeias de blocos modernas ainda é bastante limitada em recursos de computação, e qualquer transição para criptografia séria geralmente é simplesmente impossível. Vamos precisar de criptografia séria, como será demonstrado mais adiante. Embora esse problema seja claramente temporário, é necessária criptografia séria nos contratos para resolver muitos problemas, e ela aparece gradualmente (por exemplo, contratos de sistema para zkSNARKs no Ethereum)

O blockchain, que fornece um canal de mensagens de protocolo transparente e confiável, faz isso por um motivo. Qualquer protocolo descentralizado deve levar em conta a possibilidade de um ataque Sybil; qualquer ação pode ser realizada pelas forças coordenadas de muitas contas; portanto, ao projetar, é necessário levar em conta as capacidades dos invasores para criar um número arbitrário de participantes do protocolo que atuam em conluio.

PVRB e variáveis ​​de bloco.

Eu não menti quando disse que até agora ninguém implementou um bom PVRB, verificado por muitos aplicativos de jogo, em blockchains. Onde, então, existem tantas aplicações de jogo no Ethereum e EOS? Surpreende-me tanto quanto você, bem, de onde você tirou tantos números aleatórios "persistentes" de um ambiente completamente determinístico?

A maneira favorita de se tornar aleatório na blockchain é pegar algum tipo de informação "imprevisível" do bloco, e com base nela para fazer aleatoriamente - apenas armazene em cache um ou mais valores. Um bom artigo sobre os problemas de tais esquemas aqui . Você pode usar alguns dos valores "imprevisíveis" do bloco, por exemplo, o hash do bloco, o número de transações, a complexidade da rede e outros valores desconhecidos antecipadamente. Em seguida, armazene-os em cache, um ou mais e, em teoria, você deve obter um aleatório real. Você pode até adicionar ao wihitepaper que seu esquema é "pós-quantum secure" (já que existem funções hash à prova de quantum :)).

Mas mesmo hashes seguros pós-quantum não são suficientes, infelizmente. O segredo está nos requisitos do PVRB, lembro-os de um artigo anterior:

1. O resultado deve ter uma distribuição comprovadamente uniforme, isto é, com base em criptografia comprovadamente forte.
2. Não foi possível controlar nenhum dos bits do resultado. Como resultado, o resultado não pode ser previsto com antecedência.
3. Você não pode sabotar o protocolo de geração não participando do protocolo ou sobrecarregando a rede com mensagens de ataque
4. Todos os itens acima devem ser resistentes ao conluio do número permitido de participantes desonestos no protocolo (por exemplo, 1/3 dos participantes).

Nesse caso, apenas o requisito 1 é atendido e 2. não é atendido.Com valores imprevisíveis do bloco, obtemos uma distribuição uniforme e uma boa aleatoriedade. Mas a BP tem pelo menos a capacidade de "publicar um bloco ou não". Assim, a BP pode pelo menos escolher entre DUAS opções de aleatoriedade: “nossa” e uma que resultará se alguém fizer o bloqueio. A BP pode "espionar" antecipadamente o que acontece se publicar um bloco e apenas decide fazê-lo ou não. Assim, jogando, por exemplo, "ímpar-par" ou "vermelho / preto" na roleta, ele pode publicar um bloco apenas se vir uma vitória. Também cria uma estratégia inoperante para usar, por exemplo, um hash de um bloco do futuro. Nesse caso, eles dizem que “será utilizado um aleatório, obtido por hash dos dados atuais e do hash do bloco futuro com uma altura, por exemplo, N + 42, onde N é a altura atual do bloco. Isso fortalece um pouco o esquema, mas ainda permite que a BP, ainda que no futuro, escolha, mantenha o bloco ou publique.

BP suave neste caso é complicado, mas não muito. Só que, ao validar e incluir uma transação no bloco, é feita uma verificação rápida para verificar se haverá um ganho e, possivelmente, a seleção de um dos parâmetros da transação para obter uma alta probabilidade de vitória. Ao mesmo tempo, capturar um BP inteligente, para tais manipulações, é quase impossível, toda vez que você pode usar novos endereços e ganhar um pouco, sem causar suspeitas.

Portanto, os métodos que usam informações do bloco não são adequados para o papel de implementação universal do PVRB. Em uma versão limitada, com restrições no tamanho das apostas, restrições no número de jogadores e / ou registro KYC (para impedir que um jogador use vários endereços), esses esquemas podem funcionar para jogos pequenos, mas nada mais.

PVRB e confirmação de confirmação.

Ok, graças ao hash e, pelo menos, à relativa imprevisibilidade do hash do bloco e outras variáveis. Se você resolver o problema dos mineiros de frente, deve obter algo mais adequado. Vamos adicionar usuários a esse esquema - embora eles também afetem a aleatoriedade: qualquer pessoa de suporte técnico dirá que a coisa mais aleatória nos sistemas de TI são as ações dos usuários :)

O esquema ingênuo, quando os usuários simplesmente enviam números aleatórios, e o resultado é calculado como, por exemplo, um hash de sua soma, não é adequado. Nesse caso, o último jogador pode escolher seu próprio controle aleatório sobre qual será o resultado. Portanto, o padrão de confirmação e divulgação muito usado é usado. Os participantes primeiro enviam hashes de seus aleatórios (commit) se abrem os aleatórios eles mesmos. A fase de "revelação" começa somente depois que a confirmação necessária foi coletada, para que os participantes possam enviar exatamente o aleatório do qual enviaram um hash anteriormente. Agora, cegamos tudo isso com os parâmetros do bloco, e é melhor do que o obtido no futuro (você pode descobrir a aleatoriedade apenas em um dos futuros blocos) e pronto - o aleatório está pronto! Agora, qualquer jogador influencia a aleatoriedade resultante e pode "derrotar" o BP malicioso bloqueando-o com o seu próprio, anteriormente desconhecido, aleatório ... Você também pode adicionar proteção contra sabotagem do protocolo, não abrindo-o no estágio de revelação - apenas exigindo a aplicação de uma certa quantia na transação. - depósito de seguro, que será devolvido apenas durante o procedimento de revelação. Nesse caso, fazer commit e não revelar será uma desvantagem.

Foi uma boa tentativa, e esses esquemas também estão em DApps de jogos, mas, infelizmente, isso novamente não é suficiente. Agora, não apenas o mineiro, mas qualquer participante do protocolo pode influenciar o resultado. Ainda é possível controlar o valor em si, com um menor grau de variabilidade e por dinheiro, mas, como no caso do mineiro, se os resultados do sorteio forem mais valiosos do que a taxa de participação no protocolo PVRB, o produtor aleatório (RP) pode decidir se deve revelar e ainda pode escolher entre pelo menos duas opções aleatórias.
Mas houve uma oportunidade de punir aqueles que cometem e não revelam, e esse esquema ainda é útil. Sua simplicidade é uma grande vantagem - protocolos mais sérios requerem computação muito mais poderosa.

PVRB e assinaturas determinísticas.

Há outra maneira de obter um RP para fornecer um número pseudo-aleatório que ele não pode afetar se for fornecido com um "protótipo" - essa é uma assinatura determinística. Essa assinatura é, por exemplo, RSA e não é ECS. Se o RP tiver um par de chaves: RSA e ECC, e ele assinar algum valor com sua chave privada, no caso do RSA, ele receberá uma e apenas uma assinatura, e no caso do ECS, ele poderá gerar qualquer número de assinaturas válidas diferentes. Isso se deve ao fato de que, ao criar uma assinatura ECS, um número aleatório é usado, escolhido pelos assinantes, e pode ser escolhido conforme desejado, dando ao signatário a oportunidade de escolher uma das várias assinaturas. No caso do RSA: “um valor de entrada” + “um par de chaves” = “uma assinatura”. É impossível prever qual será a assinatura do outro RP, para que o PVRB com assinaturas determinísticas possa ser organizado combinando assinaturas RSA de vários participantes que assinaram o mesmo valor. Por exemplo - o aleatório anterior. Nesse esquema, muitos recursos são economizados, porque as assinaturas são uma confirmação da correção do comportamento do protocolo e uma fonte de aleatoriedade.

No entanto, mesmo com assinaturas determinísticas, o esquema ainda é vulnerável ao problema do "último ator". O último participante ainda pode decidir se deseja publicar sua assinatura ou não, controlando o resultado. Você pode refinar o esquema, adicionar hashes de bloco a ele, fazer rodadas para que o resultado não possa ser previsto com antecedência, mas todos esses métodos, mesmo levando em conta muitas melhorias, ainda deixam por resolver o problema da influência de um participante no resultado coletivo em um ambiente não confiável e só podem funcionar em condições de restrições econômicas e de tempo. Além disso, o tamanho das chaves RSA (1024 e 2048 bits) é bastante grande, e o tamanho das transações de blockchain é um parâmetro extremamente importante. Aparentemente, de uma maneira simples, não vai funcionar, vamos mais longe.

Esquemas de compartilhamento secreto e PVRB

Na criptografia, existem esquemas que permitem à rede concordar com um e apenas um valor do PVRB, enquanto esses esquemas são resistentes a qualquer ação maliciosa de parte dos participantes. Um protocolo útil para conhecer é o esquema de compartilhamento secreto de Shamir. Serve para dividir um segredo (por exemplo, uma chave secreta) em várias partes e distribuir essas partes para N participantes. O segredo é distribuído de maneira que M partes de N sejam suficientes para sua restauração, enquanto pode ser qualquer parte M. Se nos dedos, com um gráfico de uma função desconhecida, os participantes trocam pontos no gráfico e, depois de receber os pontos M, toda a função pode ser restaurada.
Uma boa explicação é dada no wiki e brincar com ele praticamente para perder o protocolo em sua cabeça é útil na página de demonstração .

Se o esquema FSSS (Fiat-Shamir Secret Sharing) fosse aplicável em sua forma pura, seria um PVRB inabalável. Na versão mais simples, o protocolo pode ser assim:

• Cada participante gera seu próprio aleatório e distribui ações para os outros participantes
• M shares, , ,
• random- PVRB

, , threshold- . , RP , , “last actor”.

, PVRB secret sharing - , , . , , , . - EOS — share : . , proof- , . , verify , block-producer , , verify . , (0.5 ).

— - . proof-, — off-chain , — PVRB.

PVRB threshold signatures

secret sharing, , “threshold”. M N, N, “threshold” . “last actor”, , , . , .

threshold- PVRB — threshold-. threshold-, longread Dash.

BLS (BLS Boneh-Lynn-Shacham, ), — , , BLS , , . . , BLS , , M N , , publicly verifiable, , M- .

threshold BLS signatures BLS - ( ), threshold- . BLS , threshold- “last-actor”, , , , .

, PVRB , BLS threshold signatures, . , DFinity ( , , verifiable secret sharing), Keep.network ( random beacon yellowpaper , -, ).

PVRB

, , PVRB , . , , . PVRB , : CPU, memory, storage, I/O. PVRB — , , . , RP, , proof- , .

, PVRB:

• . PVRB unbiasable, . ,
• “last actor” . PVRB , , RP .
• . PVRB , , RP , ,
• . RP “ , ”. p2p , ,
• . PVRB on-chain , . -,
• liveness . PVRB , RP
• trusted setup . PVRB setup , . . - — ,
• . , , , ..

threshold BLS — , , , threshold. , , , , , , , realtime, , , threshold . , threshold-, , (slashing) , . , BLS , , EOS Ethereum — . — WebAssembly EVM, . (), . , 1024 2048 bit RSA, 4-8 , Bitcoin Ethereum.

— , . , Go geth, Rust Parity, C++ EOS. JavaScript , JavaScript , WebAssembly, -.

Conclusão

, , , , , . , , setup- , whitepaper- , - “ , ”.

, PVRB Haya , threshold BLS signatures, PVRB , - . , : secret sharing random_seed, threshold BLS , . , , , , , , — , , . — , , governance .

PVRB, , , , , , , , , , - . , , .

, , , , :)