Ola Habr!
В Neste artigo, discutimos por que pode ser necesario xerar números aleatorios para os participantes que non confían uns nos outros, cales son os requisitos que se presentan para estes xeradores de números aleatorios e consideramos dous enfoques para a súa implementación.
Nesta parte do artigo, analizaremos con máis detalle outro enfoque que utiliza sinaturas de limiar.
Un pouco de criptografía
Para comprender como funcionan as sinaturas de limiar, cómpre comprender un pouco de criptografía básica. Empregaremos dous conceptos: escalares, ou simplemente números, que denotaremos con minúsculas (x, y) e puntos da curva elíptica, que denotaremos con maiúsculas.
Para comprender os conceptos básicos das sinaturas de limiar, non é necesario comprender como funcionan as curvas elípticas, agás algunhas cousas básicas:
-
Os puntos dunha curva elíptica pódense sumar e multiplicar por un escalar (denotaremos a multiplicación por un escalar como xG, aínda que a notación Gx tamén se usa a miúdo na literatura). O resultado da suma e multiplicación por un escalar é un punto nunha curva elíptica.
-
Coñecendo só o punto G e o seu produto cun escalar xG non se pode calcular x.
Tamén utilizaremos o concepto de polinomio p (x) grao k-1. En particular, utilizaremos a seguinte propiedade dos polinomios: se coñecemos o valor p (x) para calquera k diferente x (e non temos máis información sobre p (x)), podemos calcular p (x) para calquera outra persoa x.
É interesante que para calquera polinomio p (x) e algún punto da curva Gcoñecendo o significado p(x)G para calquera k diferentes significados x, tamén podemos calcular p(x)G para calquera x.
Esta é información suficiente para explorar os detalles de como funcionan as sinaturas de limiar e como usalas para xerar números aleatorios.
Xerador de números aleatorios en sinaturas de limiar
Digamos iso n os participantes queren xerar un número aleatorio e queremos que todos participen k había suficientes deles para xerar un número, pero para que os atacantes que controlan k-1 ou menos participantes non puideron predicir nin influír no número xerado.
Supoñamos que existe tal polinomio p (x) grao k-1 o que sabe o primeiro participante p (1), o segundo sabe p(2), etcétera (n-o sabe p(n)). Tamén asumimos que para algún punto predeterminado G todo o mundo sabe p(x)G para todos os valores x. Chamaremos p(i) "compoñente privado" iº participante (porque só io participante o coñécea), e p(i)G "compoñente público" i-ésimo participante (porque todos os participantes a coñecen). Como lembras, coñecemento p(i)G non é suficiente para restaurar p(i).
Creando tal polinomio para que só i-O primeiro participante e ninguén máis coñecía o seu compoñente privado: esta é a parte máis complexa e interesante do protocolo, e analizarémola a continuación. Polo momento, supoñamos que temos un polinomio deste tipo e que todos os participantes coñecen os seus compoñentes privados.
Como podemos usar tal polinomio para xerar un número aleatorio? Para comezar, necesitamos algunha cadea que non se utilizase previamente como entrada para o xerador. No caso dunha cadea de bloques, o hash do último bloque h é un bo candidato para tal liña. Permite que os participantes queiran crear un número aleatorio usando h como semente. Os participantes converten primeiro h a un punto da curva usando calquera función predefinida:
H = escalarToPoint(h)
Despois cada participante i calcula e publica Hi = p(i)H, que poden facer porque saben p(i) e H. Divulgación Hnon permito que outros participantes restauren o compoñente privado ith participante e, polo tanto, pódese usar un conxunto de compoñentes privados de bloque en bloque. Así, o caro algoritmo de xeración de polinomios que se describe a continuación só precisa ser executado unha vez.
Cando k os participantes foron autopsiados Hi = p(i)H, todo o mundo pode calcular Hx = p(x)H para todos x grazas á propiedade dos polinomios que comentamos no último apartado. Neste momento, todos os participantes calculan H0 = p(0)H, e este é o número aleatorio resultante. Teña en conta que ninguén o sabe p(0), e polo tanto a única forma de calcular p(0)H – esta é a interpolación p(x)H, que só é posible cando k valores p(i)H coñecido. Abrindo calquera cantidade menor p(i)H non proporciona información sobre p(0)H.
O xerador de arriba ten todas as propiedades que queremos: atacantes só controlando k-1 participantes ou menos non teñen información nin influencia na conclusión, mentres que ningún k os participantes poden calcular o número resultante e calquera subconxunto de k os participantes sempre chegarán ao mesmo resultado para a mesma semente.
Hai un problema que evitamos coidadosamente anteriormente. Para que a interpolación funcione, é importante que o valor Hi que foi publicado por cada participante i realmente foi o mesmo p(i)H. Xa que ninguén excepto i-o participante non sabe p(i), ninguén excepto i-O participante non pode verificalo Hi realmente calculado correctamente, e sen ningunha proba criptográfica de corrección Heu un atacante pode publicar calquera valor como Ola, e inflúen arbitrariamente na saída do xerador de números aleatorios:
Os diferentes valores de H_1 enviados polo primeiro participante dan lugar a un H_0 resultante diferente
Hai polo menos dúas formas de demostrar a corrección Hi, considerarémolos despois de analizar a xeración do polinomio.
Xeración de polinomios
Na última sección asumimos que temos tal polinomio p (x) grao k-1 que o participante i sabe p(i), e ninguén máis ten información sobre este valor. Na seguinte sección tamén necesitaremos iso para algún punto predeterminado G todos sabían p(x)G para todos x.
Nesta sección asumiremos que cada participante ten localmente algunha clave privada xi, de tal xeito que todos coñezan a chave pública correspondente Xi.
Un posible protocolo de xeración de polinomios é o seguinte:
-
Cada participante i localmente crea un polinomio arbitrario pi(x) grao k-1. Despois envían a cada participante j significado pi(j), cifrado con clave pública Xj. Só así i-th и j-th o participante sabe pi(j). Participante i tamén anuncia publicamente pi(j)G para todos j de 1 para k inclusive.
-
Todos os participantes usan algún consenso para escoller k participantes cuxos polinomios se utilizarán. Dado que algúns participantes poden estar sen conexión, non podemos esperar ata que todos estean n os participantes publicarán polinomios. O resultado deste paso é un conxunto Z composto polo menos por k polinomios creados no paso (1).
-
Os participantes asegúranse de que os valores que coñecen pi(j) corresponden a anunciados publicamente pi(j)G. Despois deste paso Z só polinomios para os que se transmiten de forma privada pi(j) corresponden a anunciados publicamente pi(j)G.
-
Cada participante j calcula a súa compoñente privada p(j) como unha suma pi(j) para todos i в Z. Cada participante tamén calcula todos os valores p(x)G como unha suma pi(x)G para todo i в Z.
Nótese que p(x) – é realmente un polinomio k-1, porque é a suma do individuo pi(x), cada un dos cales é un polinomio de grao k-1. A continuación, teña en conta que mentres cada participante j sabe p(j), non teñen información sobre p (x) para x ≠ j. De feito, para calcular este valor, necesitan saber todo pi(x), e sempre que o participante j non coñece polo menos un dos polinomios seleccionados, non teñen información suficiente sobre p(x).
Este é todo o proceso de xeración de polinomios que foi necesario na última sección. Os pasos 1, 2 e 4 anteriores teñen unha implementación bastante obvia. Pero o paso 3 non é tan trivial.
En concreto, temos que ser capaces de probar iso cifrado pi(j) corresponden realmente ás publicadas pi(j)G. Se non podemos demostralo, o atacante i pode enviar lixo no seu lugar pi(j) ao participante j, e participante j non poderá obter o valor real pi(j), e non poderá calcular a súa compoñente privada.
Existe un protocolo criptográfico que permite crear unha mensaxe adicional probai(j), tal que calquera participante, teña algún valor e, así como proba (j) и pi(j)G, pode verificar localmente que e - é realmente pi(j), cifrado coa clave do participante j. Desafortunadamente, o tamaño destas probas é incriblemente grande, e dado que é necesario publicalas O(nk) Tales probas non se poden utilizar para este fin.
En vez de demostralo pi(j) corresponde a pi(j)G podemos asignar un período de tempo moi grande no protocolo de xeración de polinomios, durante o cal todos os participantes verifican o cifrado recibido. pi(j), e se a mensaxe descifrada non corresponde ao público pi(j)G, publican unha proba criptográfica de que a mensaxe cifrada que recibiron é incorrecta. Demostra que a mensaxe non corresponde a pi(G) moito máis doado que demostrar que coincide. Cómpre sinalar que isto require que cada participante apareza en liña polo menos unha vez durante o tempo asignado para crear tales probas, e baséase na suposición de que se publica tal proba, chegará a todos os demais participantes no mesmo tempo asignado.
Se un participante non apareceu en liña durante este período de tempo e tiña polo menos un compoñente incorrecto, entón ese participante en particular non poderá participar na xeración de números. Non obstante, o protocolo seguirá funcionando se o hai polo menos k participantes que ou ben recibiron os compoñentes correctos ou conseguiron deixar probas de incorrección no prazo previsto.
Probas de corrección de H_i
A última parte que queda por discutir é como probar a corrección do publicado Hi, é dicir, iso Hi = p(i)H, sen abrir p(i).
Lembremos que os valores H, G, p(i)G público e coñecido por todos. Operación de recepción p(i) sabendo p(i)G и G chamado logaritmo discreto, ou dlog, e queremos demostrar que:
dlog(p(i)G, G) = dlog(Hi, H)
sen revelación p(i). Existen construcións para tales probas, por exemplo.
Con este deseño, cada participante, xunto con Hi envía unha proba de corrección segundo o deseño.
Unha vez que se xera un número aleatorio, moitas veces ten que ser usado por participantes distintos dos que o xeraron. Estes participantes, xunto co número, deben enviar todos Hi e evidencia relacionada.
Un lector curioso pode preguntar: xa que o número aleatorio final é H0, e p(0)G – Esta é información pública, por que necesitamos probas para cada individuo Heu, por que non enviar probas diso
dlog(p(0)G, G) = dlog(H0, H)
O problema é que tal proba non se pode crear usando o protocolo Schnorr porque ninguén coñece o valor p (0), necesario para crear a proba e, ademais, todo o xerador de números aleatorios baséase no feito de que ninguén coñece este valor. Polo tanto é necesario ter todos os valores Hi e as súas probas individuais para demostrar a corrección H0.
Non obstante, se houbese algunha operación sobre puntos en curvas elípticas que sexa semánticamente semellante á multiplicación, a proba de corrección H0 sería trivial, simplemente asegurariamos que
H0 × G = p(0)G × H
Se a curva seleccionada admite , esta proba funciona. Neste caso H0 non é só a saída dun xerador de números aleatorios, que pode ser verificado por calquera participante que o saiba G, H и p(0)G. H0 tamén é unha sinatura na mensaxe que se utilizou como semente, o que confirma k и n os participantes asinaron esta mensaxe. Así, se semente - é o hash do bloque no protocolo blockchain, entón H0 é á vez unha multisinatura nun bloque e un moi bo número aleatorio.
En conclusión
Este artigo forma parte dunha serie de blogs técnicos . NEAR é un protocolo e unha plataforma blockchain para desenvolver aplicacións descentralizadas con énfase na facilidade de desenvolvemento e de uso para os usuarios finais.
O código do protocolo está aberto, a nosa implementación está escrita en Rust, pódese atopar .
Podes ver como é o desenvolvemento de NEAR e experimentar no IDE en liña .
Podes seguir todas as novidades en ruso en e , e en inglés no oficial .
Vémonos pronto!
Fonte: www.habr.com