¡Hola, Habr!
В En este artículo, analizamos por qué podría ser necesario generar números aleatorios para los participantes que no confían entre sí, qué requisitos se plantean para dichos generadores de números aleatorios y consideramos dos enfoques para su implementación.
En esta parte del artículo, analizaremos más de cerca otro enfoque que utiliza firmas de umbral.
Un poco de criptografía
Para comprender cómo funcionan las firmas de umbral, es necesario comprender un poco de criptografía básica. Usaremos dos conceptos: escalares, o simplemente números, que denotaremos con letras minúsculas (x, y) y puntos de la curva elíptica, que denotaremos con letras mayúsculas.
Para comprender los conceptos básicos de las firmas de umbral, no es necesario comprender cómo funcionan las curvas elípticas, aparte de algunas cosas básicas:
-
Los puntos en una curva elíptica se pueden sumar y multiplicar por un escalar (denotaremos la multiplicación por un escalar como xG, aunque la notación Gx también se utiliza a menudo en la literatura). El resultado de la suma y la multiplicación por un escalar es un punto en una curva elíptica.
-
Conociendo sólo el punto G y su producto con un escalar xG no se puede calcular x.
También usaremos el concepto de polinomio. p (x) grados k-1. En particular, usaremos la siguiente propiedad de los polinomios: si conocemos el valor p (x) para cualquier k diferente x (y no tenemos más información sobre p (x)), podemos calcular p (x) para cualquier otra persona x.
Es interesante que para cualquier polinomio p (x) y algún punto en la curva Gconociendo el significado p(x)G para cualquier k diferentes significados x, también podemos calcular p(x)G para cualquier x.
Esta es información suficiente para profundizar en los detalles de cómo funcionan las firmas de umbral y cómo usarlas para generar números aleatorios.
Generador de números aleatorios en firmas de umbral
digamos que n Los participantes quieren generar un número aleatorio y queremos que cualquiera participe. k Había suficientes para generar un número, pero para que los atacantes que controlan k-1 o menos participantes no pudieron predecir ni influir en el número generado.
Supongamos que existe tal polinomio. p (x) grados k-1 lo que sabe el primer participante p (1), el segundo sabe pag(2), etcétera (n-th sabe p(n)). También suponemos que para algún punto predeterminado G todos saben p(x)G para todos los valores x. llamaremos Pi) “componente privado” iº participante (porque sólo iel décimo participante la conoce), y cerdo “componente público” i-ésima participante (porque todos los participantes la conocen). Como recordarás, el conocimiento. cerdo no es suficiente para restaurar Pi).
Creando tal polinomio de modo que solo i-El primer participante y nadie más conocía su componente privado: esta es la parte más compleja e interesante del protocolo, y la analizaremos a continuación. Por ahora, supongamos que tenemos dicho polinomio y que todos los participantes conocen sus componentes privados.
¿Cómo podemos usar tal polinomio para generar un número aleatorio? Para empezar, necesitamos alguna cadena que no se haya utilizado previamente como entrada al generador. En el caso de una blockchain, el hash del último bloque h es un buen candidato para esa línea. Deje que los participantes quieran crear un número aleatorio usando h como semilla. Los participantes se convierten primero h a un punto de la curva usando cualquier función predefinida:
H = escalarAPunto(h)
Luego cada participante i calcula y publica Hola = p(i)H, ¿Qué pueden hacer porque saben? p(i) y H. Divulgación HNo permito que otros participantes restauren el componente privado. iº participante y, por lo tanto, se puede utilizar un conjunto de componentes privados de un bloque a otro. Por lo tanto, el costoso algoritmo de generación de polinomios que se describe a continuación solo necesita ejecutarse una vez.
¿Cuándo k los participantes fueron autopsiados Hola = p(i)H, todos pueden calcular Hx = p(x)H para todos x gracias a la propiedad de los polinomios que comentamos en la última sección. En este momento, todos los participantes calculan H0 = p(0)H, y este es el número aleatorio resultante. Tenga en cuenta que nadie lo sabe. pag(0), y por lo tanto la única manera de calcular pag(0)H – esto es interpolación p(x)H, que sólo es posible cuando k valores p(yo)H conocido. Abrir cualquier cantidad menor p(yo)H no proporciona ninguna información sobre pag(0)H.
El generador anterior tiene todas las propiedades que queremos: los atacantes controlan sólo k-1 participantes o menos no tienen información o influencia en la conclusión, mientras que cualquier k Los participantes pueden calcular el número resultante y cualquier subconjunto de k los participantes siempre llegarán al mismo resultado para la misma semilla.
Hay un problema que evitamos cuidadosamente anteriormente. Para que la interpolación funcione, es importante que el valor Hi que fue publicado por cada participante i realmente era lo mismo p(yo)H. Ya que nadie excepto i-ésimo participante no sabe Pi), nadie excepto i-El participante no puede verificar que Hi realmente calculado correctamente y sin ninguna prueba criptográfica de corrección Hi un atacante puede publicar cualquier valor como Hola, e influir arbitrariamente en la salida del generador de números aleatorios:
Diferentes valores de H_1 enviados por el primer participante dan lugar a diferentes H_0 resultantes
Hay al menos dos formas de demostrar la corrección. Hi, los consideraremos después de analizar la generación del polinomio.
Generación polinomial
En la última sección asumimos que tenemos tal polinomio p (x) grados k-1 que el participante i sabe Pi), y nadie más tiene información sobre este valor. En la siguiente sección también lo necesitaremos para algún punto predeterminado. G todos sabían p(x)G para todos x.
En esta sección asumiremos que cada participante localmente tiene alguna clave privada. xi, de modo que todos conozcan la clave pública correspondiente Xi.
Un posible protocolo de generación de polinomios es el siguiente:
-
Cada participante i crea localmente un polinomio arbitrario pi(x) grado k-1. Luego envían a cada participante j значение pi(j), cifrado con clave pública Xj. Así sólo i-th и j-th el participante sabe pyo(j). Partícipe i también anuncia públicamente pi(j)G para todos j de 1 a k Incluido.
-
Todos los participantes utilizan algún consenso para elegir. k participantes cuyos polinomios se utilizarán. Dado que algunos participantes pueden estar desconectados, no podemos esperar hasta que todos n Los participantes publicarán polinomios. El resultado de este paso es un conjunto Z consistente en al menos k polinomios creados en el paso (1).
-
Los participantes se aseguran de que los valores que conocen pi(j) corresponden a lo anunciado públicamente pi(j)G. Después de este paso en Z sólo polinomios para los cuales se transmiten de forma privada pi(j) corresponden a lo anunciado públicamente pi(j)G.
-
Cada participante j calcula su componente privado pag(j) como una suma pi(j) para todos i в Z. Cada participante también calcula todos los valores. p(x)G como una suma pi(x)G para todo i в Z.
Tenga en cuenta que pag(x) – es realmente un polinomio k-1, porque es la suma del individuo pi(x), cada uno de los cuales es un polinomio de grado k-1. Luego, tenga en cuenta que si bien cada participante j sabe pag(j), no tienen información sobre p (x) para x ≠ j. De hecho, para calcular este valor, necesitan saber todo pi(x), y siempre y cuando el participante j no conoce al menos uno de los polinomios seleccionados, no tiene información suficiente sobre p(x).
Este es todo el proceso de generación de polinomios que se necesitaba en la última sección. Los pasos 1, 2 y 4 anteriores tienen una implementación bastante obvia. Pero el paso 3 no es tan trivial.
Específicamente, debemos poder demostrar que los archivos cifrados pi(j) realmente corresponden a los publicados pi(j)G. Si no podemos probarlo, el atacante i puede enviar basura en su lugar pi(j) al participante jy participante j no podrá entender el verdadero significado pi(j), y no podrá calcular su componente privado.
Existe un protocolo criptográfico que permite crear un mensaje adicional pruebai(j), de modo que cualquier participante, que tenga algún valor e, así como pruebai(j) и pi(j)G, puede verificar localmente que e - es realmente pi(j), cifrado con la clave del participante j. Desafortunadamente, el tamaño de dicha evidencia es increíblemente grande, y dado que es necesario publicar O (nk) Estas pruebas no pueden utilizarse para este fin.
En lugar de demostrar que pi(j) partido pi(j)G podemos asignar un período de tiempo muy grande en el protocolo de generación de polinomios, durante el cual todos los participantes verifican el cifrado recibido. pi(j), y si el mensaje descifrado no corresponde al público pi(j)G, publican una prueba criptográfica de que el mensaje cifrado que recibieron es incorrecto. Demostrar que el mensaje no partido cerdo) mucho más fácil que demostrar que coincide. Cabe señalar que esto requiere que cada participante aparezca en línea al menos una vez durante el tiempo asignado para crear dicha evidencia, y se basa en el supuesto de que si publican dicha prueba, llegará a todos los demás participantes en el mismo tiempo asignado.
Si un participante no apareció en línea durante este período de tiempo y tenía al menos un componente incorrecto, ese participante en particular no podrá participar en la generación posterior de números. Sin embargo, el protocolo seguirá funcionando si hay al menos k participantes que acaban de recibir los componentes correctos o lograron dejar pruebas de la incorrección dentro del tiempo asignado.
Pruebas de corrección de H_i
La última parte que queda por discutir es cómo probar la exactitud de los datos publicados. Hyo, es decir, que Hola = p(i)H, sin abrir Pi).
Recordemos que los valores H, GRAMO, p(i)G público y conocido por todos. Recibir operación Pi) sabiendo cerdo и G llamado logaritmo discreto, o blogger, y queremos demostrar que:
dlog(p(i)G, G) = dlog(Hi, H)
sin divulgación Pi). Existen construcciones para tales pruebas, por ejemplo..
Con este diseño, cada participante, junto con Hi envía una prueba de corrección según el diseño.
Una vez que se genera un número aleatorio, a menudo es necesario que otros participantes además de quienes lo generaron lo utilicen. Dichos participantes, junto con el número, deberán enviar todos Hi y evidencia relacionada.
Un lector curioso puede preguntar: dado que el número aleatorio final es H0, y pag(0)G – Esta es información pública, ¿por qué necesitamos pruebas para cada individuo? HYo, ¿por qué no enviar pruebas de que en su lugar?
blogger(p(0)G, G) = dlog(H0, H)
El problema es que dicha prueba no se puede crear utilizando el Protocolo Schnorr porque nadie conoce el valor. p (0), necesario para crear la prueba y, además, todo el generador de números aleatorios se basa en el hecho de que nadie conoce este valor. Por lo tanto es necesario tener todos los valores. Hi y su evidencia individual para demostrar la corrección. H0.
Sin embargo, si hubiera alguna operación en puntos de curvas elípticas que fuera semánticamente similar a la multiplicación, la prueba de corrección H0 sería trivial, simplemente nos aseguraríamos de que
H0 × G = pag(0)G × H
Si la curva seleccionada admite , esta prueba funciona. En este caso H0 no es sólo el resultado de un generador de números aleatorios, que puede ser verificado por cualquier participante que sepa G,H и p(0)G. h0 también es una firma en el mensaje que se usó como semilla, lo que confirma que k и n Los participantes firmaron este mensaje. Así, si semilla - es el hash del bloque en el protocolo blockchain, entonces H0 Es a la vez una firma múltiple en un bloque y un muy buen número aleatorio.
en conclusión
Este artículo es parte de una serie de blogs técnicos. . NEAR es un protocolo y una plataforma blockchain para desarrollar aplicaciones descentralizadas con énfasis en la facilidad de desarrollo y uso para los usuarios finales.
El código del protocolo está abierto, nuestra implementación está escrita en Rust, se puede encontrar .
Puedes ver cómo es el desarrollo para NEAR y experimentar en el IDE en línea. .
Puedes seguir todas las novedades en ruso en y , y en inglés en el oficial .
Hasta pronto!
Fuente: habr.com