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

Oi, Habr!

В a primeira parte Neste artigo, discutimos por que pode ser necessário gerar números aleatórios para participantes que não confiam uns nos outros, quais requisitos são apresentados para tais geradores de números aleatórios e consideramos duas abordagens para sua implementação.

Nesta parte do artigo, examinaremos mais de perto outra abordagem que usa assinaturas de limite.

Um pouco de criptografia

Para entender como funcionam as assinaturas de limite, você precisa entender um pouco de criptografia básica. Usaremos dois conceitos: escalares, ou simplesmente números, que denotaremos por letras minúsculas (x, y) e pontos na curva elíptica, que denotaremos por letras maiúsculas.

Para entender o básico das assinaturas de limite, você não precisa entender como funcionam as curvas elípticas, além de algumas coisas básicas:

1. Os pontos em uma curva elíptica podem ser somados e multiplicados por um escalar (denotaremos a multiplicação por um escalar como xG, embora a notação Gx também frequentemente usado na literatura). O resultado da adição e multiplicação por um escalar é um ponto em uma curva elíptica.

2. Sabendo apenas o ponto G e seu produto com um escalar xG não pode ser calculado x.

Também usaremos o conceito de polinômio p (x) graus k-1. Em particular, usaremos a seguinte propriedade dos polinômios: se conhecermos o valor p (x) para qualquer k diferente x (e não temos mais informações sobre p (x)), podemos calcular p (x) para qualquer outra pessoa x.

É interessante que para qualquer polinômio p (x) e algum ponto na curva Gsabendo o significado p(x)G para qualquer k Significados diferentes x, também podemos calcular p(x)G para qualquer x.

Essas informações são suficientes para aprofundar os detalhes de como funcionam as assinaturas de limite e como usá-las para gerar números aleatórios.

Gerador de números aleatórios em assinaturas de limite

Digamos que n os participantes querem gerar um número aleatório e queremos que qualquer pessoa participe k eram suficientes para gerar um número, mas para que os atacantes que controlam k-1 ou menos participantes não puderam prever ou influenciar o número gerado.

Suponha que exista tal polinômio p (x) graus k-1 o que o primeiro participante sabe p (1), o segundo sabe p(2), e assim por diante (n-você sabe p(n)). Também assumimos que para algum ponto predeterminado G todo mundo sabe p(x)G para todos os valores x. Nós vamos ligar p(eu) “componente privado” io participante (porque apenas io décimo participante a conhece), e porco “componente público” i-º participante (porque todos os participantes a conhecem). Como você se lembra, o conhecimento porco não é suficiente para restaurar p(eu).

Criando tal polinômio de modo que apenas i-O primeiro participante e mais ninguém conhecia seu componente privado - esta é a parte mais complexa e interessante do protocolo, e iremos analisá-la a seguir. Por enquanto, vamos supor que temos esse polinômio e todos os participantes conhecem seus componentes privados.

Como podemos usar esse polinômio para gerar um número aleatório? Para começar, precisamos de alguma string que não tenha sido usada anteriormente como entrada para o gerador. No caso de uma blockchain, o hash do último bloco h é um bom candidato para tal linha. Deixe os participantes quererem criar um número aleatório usando h como semente. Os participantes convertem primeiro h para um ponto na curva usando qualquer função predefinida:

H = escalarToPoint(h)

Então cada participante i calcula e publica Oi = p(i)H, o que eles podem fazer porque sabem p(i) e H. Divulgação Hnão permito que outros participantes restaurem o componente privado io participante e, portanto, um conjunto de componentes privados pode ser usado de bloco para bloco. Assim, o caro algoritmo de geração de polinômios descrito abaixo só precisa ser executado uma vez.

Quando k participantes foram autopsiados Oi = p(i)H, todos podem calcular Hx = p(x)H para todos x graças à propriedade dos polinômios que discutimos na última seção. Neste momento, todos os participantes calculam H0 = p(0)H, e este é o número aleatório resultante. Observe que ninguém sabe p(0), e, portanto, a única maneira de calcular p(0)H – isso é interpolação p(x)H, o que só é possível quando k valores p(i)H conhecido. Abrindo qualquer quantidade menor p(i)H não fornece nenhuma informação sobre p(0)H.

O gerador acima possui todas as propriedades que desejamos: invasores controlando apenas k-1 participante ou menos não tem informação ou influência na conclusão, enquanto qualquer k os participantes podem calcular o número resultante e qualquer subconjunto de k os participantes sempre chegarão ao mesmo resultado para a mesma semente.

Há um problema que evitamos cuidadosamente acima. Para que a interpolação funcione, é importante que o valor Hi que foi publicado por cada participante i realmente era o mesmo p(i)H. Já que ninguém exceto i-º participante não sabe p(eu), ninguém exceto i-o participante não pode verificar se Hi realmente calculado corretamente e sem qualquer prova criptográfica de correção Hum invasor pode publicar qualquer valor como Oi, e influenciar arbitrariamente a saída do gerador de números aleatórios:

Diferentes valores de H_1 enviados pelo primeiro participante levam a resultados diferentes de H_0

Existem pelo menos duas maneiras de provar a correção Hi, iremos considerá-los após analisarmos a geração do polinômio.

Geração polinomial

Na última seção, assumimos que temos tal polinômio p (x) graus k-1 que o participante i sabe p(eu), e ninguém mais tem informações sobre esse valor. Na próxima seção também precisaremos disso para algum ponto predeterminado G todos sabiam p(x)G para todos x.

Nesta seção, assumiremos que cada participante localmente possui alguma chave privada XI, tal que todos conheçam a chave pública correspondente Xi.

Um possível protocolo de geração de polinômios é o seguinte:

1. Cada participante i cria localmente um polinômio arbitrário pi(x) grau k-1. Eles então enviam a cada participante j valor pi(j), criptografado com chave pública Xj. Assim apenas i-th и j-th participante sabe peu j). Participante i também anuncia publicamente pi(j)G para todos j de 1 para k inclusivo.

2. Todos os participantes usam algum consenso para escolher k participantes cujos polinômios serão usados. Como alguns participantes podem estar offline, não podemos esperar até que todos n os participantes publicarão polinômios. O resultado desta etapa é um conjunto Z consistindo de pelo menos k polinômios criados na etapa (1).

3. Os participantes certificam-se de que os valores que conhecem pi(j) correspondem a anunciados publicamente pi(j)G. Após esta etapa Z apenas polinômios para os quais transmitidos de forma privada pi(j) correspondem a anunciados publicamente pi(j)G.

4. Cada participante j calcula seu componente privado p(j) como uma soma peu(j) para todos i в Z. Cada participante também calcula todos os valores p(x)G como uma soma pi(x)G para todo i в Z.

Note-se que p(x) – é realmente um polinômio k-1, porque é a soma do indivíduo pi(x), cada um dos quais é um polinômio de grau k-1. Então, observe que enquanto cada participante j sabe p(j), eles não têm informações sobre p (x) para x ≠ j. Na verdade, para calcular esse valor, eles precisam saber tudo pi(x), e desde que o participante j não conhece pelo menos um dos polinômios selecionados, eles não têm informações suficientes sobre p(x).

Este é todo o processo de geração de polinômios necessário na última seção. As etapas 1, 2 e 4 acima têm uma implementação bastante óbvia. Mas o passo 3 não é tão trivial.

Especificamente, precisamos ser capazes de provar que dados criptografados pi(j) realmente correspondem aos publicados pi(j)G. Se não pudermos provar isso, o atacante i pode enviar lixo em vez disso pi(j) para participante je participante j não será capaz de obter o valor real pi(j), e não será capaz de calcular seu componente privado.

Existe um protocolo criptográfico que permite criar uma mensagem adicional provai(j), tal que qualquer participante, tendo algum valor e, bem como prova (j) и pi(j)G, pode verificar localmente que e - é realmente pi(j), criptografado com a chave do participante j. Infelizmente, o tamanho dessas evidências é incrivelmente grande, e dado que é necessário publicar O (nk) Tais provas não podem ser utilizadas para este fim.

Em vez de provar isso pi(j) соответствует pi(j)G podemos alocar um período de tempo muito longo no protocolo de geração de polinômios, durante o qual todos os participantes verificam os dados criptografados recebidos. pi(j), e se a mensagem descriptografada não corresponder ao público pi(j)G, eles publicam uma prova criptográfica de que a mensagem criptografada que receberam está incorreta. Prove que a mensagem não соответствует porco) muito mais fácil do que provar que corresponde. Deve-se notar que isso exige que cada participante apareça on-line pelo menos uma vez durante o tempo alocado para criar tal prova, e se baseia na suposição de que se publicarem tal prova, ela chegará a todos os outros participantes no mesmo tempo alocado.

Se um participante não aparecer on-line durante esse período e tiver pelo menos um componente incorreto, esse participante específico não poderá participar da geração posterior de números. O protocolo, no entanto, ainda funcionará se houver pelo menos k participantes que acabaram de receber os componentes corretos ou conseguiram deixar prova de incorreção dentro do prazo estipulado.

Provas de correção de H_i

A última parte que resta a ser discutida é como provar a exatidão dos dados publicados Heu, ou seja, que Oi = p(i)H, sem abrir p(eu).

Lembremos que os valores H, G, p(i)G pública e conhecida por todos. Operação de recebimento p(eu) sabendo porco и G chamado logaritmo discreto, ou dlog, e queremos provar que:

dlog(p(i)G, G) = dlog(Hi, H)

sem divulgação p(eu). Existem construções para tais provas, por exemplo Protocolo Schnorr.

Com este design, cada participante, juntamente com Hi envia uma prova de correção de acordo com o projeto.

Depois que um número aleatório é gerado, muitas vezes ele precisa ser usado por outros participantes além daqueles que o geraram. Tais participantes, juntamente com o número, deverão enviar todos Hi e evidências relacionadas.

Um leitor curioso pode perguntar: como o número aleatório final é H0, e p(0)G – Esta é uma informação pública, por que precisamos de provas para cada indivíduo Heu, por que não enviar uma prova disso

dlog(p(0)G, G) = dlog(H0, H)

O problema é que tal prova não pode ser criada usando o Protocolo Schnorr porque ninguém sabe o valor p (0), necessário para criar a prova e, além do mais, todo o gerador de números aleatórios se baseia no fato de que ninguém conhece esse valor. Portanto é necessário ter todos os valores Hi e suas evidências individuais para provar a correção H0.

No entanto, se houvesse alguma operação em pontos de curvas elípticas que fosse semanticamente semelhante à multiplicação, a prova de correção H0 seria trivial, simplesmente teríamos certeza de que

H0 × G = p(0)G × H

Se a curva selecionada suportar pares de curvas elípticas, esta prova funciona. Nesse caso H0 não é apenas a saída de um gerador de números aleatórios, que pode ser verificado por qualquer participante que conheça G, H и p(0)G. H0 também é uma assinatura na mensagem que foi usada como semente, confirmando que k и n participantes assinaram esta mensagem. Assim, se semente - é o hash do bloco no protocolo blockchain, então H0 é uma assinatura múltipla em um bloco e um número aleatório muito bom.

Em conclusão

Este artigo faz parte de uma série de blogs técnicos 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