Introduccion

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

Como en el caso del concepto de cifrado de criptografía absolutamente seguro, los protocolos de baliza aleatoria verificables públicamente (en adelante PVRB) solo intentan acercarse lo más posible al esquema ideal. en redes reales en su forma pura, no es aplicable: es necesario ponerse de acuerdo estrictamente en un bit, debe haber muchas rondas y todos los mensajes deben ser perfectamente rápidos y siempre entregados. Por supuesto, en redes reales esto no es así. Por lo tanto, al diseñar PVRB para tareas específicas en blockchains modernos, además de la incapacidad de controlar la aleatoriedad resultante y la fuerza criptográfica, surgen muchos problemas puramente arquitectónicos y técnicos.

La cadena de bloques en sí misma es para PVRB esencialmente un medio de comunicación en el que mensajes = transacciones. Esto le permite ignorar parcialmente los problemas de red, la entrega de mensajes, los problemas de middleware: todos estos riesgos son asumidos por una red descentralizada, y su valor principal para PVRB es la incapacidad de retirar o arruinar una transacción ya enviada; esto no permite a los participantes negarse a participar en el protocolo, a menos que hayan tenido un ataque exitoso por consenso. Este nivel de seguridad es aceptable, por lo que PVRB debe ser resistente a la colusión entre los participantes exactamente de la misma manera que la cadena principal de blockchain. Además, esto sugiere que PVRB debería ser parte del consenso, si la red acordó la cadena de bloques principal, permítale acordar al mismo tiempo sobre el único resultado aleatorio honesto. O bien, PVRB es solo un protocolo independiente implementado por un contrato inteligente que funciona de forma asincrónica con respecto a blockchain y bloques. Ambos métodos tienen sus ventajas y desventajas, y la elección entre ellos es extremadamente no trivial.

Dos formas de implementar PVRB

Describamos con más detalle dos opciones para implementar PVRB: la versión independiente, que funciona utilizando un contrato inteligente independiente de la cadena de bloques, e integrada por consenso, que está integrada en el protocolo según el cual la red acuerda una cadena de bloques y transacciones incluidas. En todos los casos, tendré en cuenta los motores populares de blockchain: Ethereum, EOS y todos similares en la forma de colocar y procesar contratos inteligentes.

Contrato independiente

En esta realización, PVRB es un contrato inteligente que acepta transacciones de productores aleatorios (en adelante RP), las procesa, combina los resultados y, como resultado, llega a algún valor que cualquier usuario de este contrato puede obtener. Es posible que este valor no se almacene directamente en el contrato, sino que se represente solo con datos a partir de los cuales se pueda obtener de manera determinista uno y solo un valor de la aleatoriedad resultante. En este esquema, los RP son usuarios de blockchain, y cualquiera puede participar en el proceso de generación.

La opción de contrato independiente es buena:

• portabilidad (los contratos se pueden arrastrar de blockchain a blockchain)
• simplicidad en la implementación y prueba (los contratos son convenientes para escribir y probar)
• conveniencia en la implementación de esquemas económicos (es fácil hacer su propio token, cuya lógica sirve a los objetivos de PVRB)
• la capacidad de correr en blockchains existentes

También tiene desventajas:

• fuertes limitaciones en recursos en cálculos, volumen de transacciones y almacenamiento (en otras palabras, cpu / mem / io)
• restricciones en las operaciones dentro del contrato (no todas las instrucciones están disponibles, es difícil conectar bibliotecas externas)
• La incapacidad para organizar la mensajería más rápido que las transacciones están incluidas en la cadena de bloques

Esta opción es adecuada para implementar PVRB, que debe ejecutarse en una red existente que no contiene criptografía compleja y no requiere una gran cantidad de interacciones.

Integrado por consenso

En esta realización, PVRB se implementa en el código de nodo de blockchain, está incorporado o funciona en paralelo con el intercambio de mensajes entre nodos de blockchain. Los resultados del protocolo se escriben directamente en los bloques producidos, y los mensajes de protocolo se envían a través de la red p2p entre los nodos. Dado que el protocolo da como resultado que los números se escriban en bloques, la red debe llegar a un consenso sobre ellos. Esto significa que los mensajes PVRB, así como las transacciones, deben ser validados por nodos e incluidos en bloques para que cualquier participante de la red pueda verificar el cumplimiento del protocolo PVRB. Esto automáticamente nos lleva a la decisión obvia: si la red negocia el consenso sobre el bloque y las transacciones en él, entonces PVRB debería ser parte del consenso, no un protocolo independiente. De lo contrario, es posible que el bloque sea válido desde el punto de vista del consenso, pero no se respeta el protocolo PVRB y, desde el punto de vista de PVRB, el bloque no puede aceptarse. Entonces, si se elige la opción "integrada por consenso", PVRB se convierte en una parte importante del consenso.

Describiendo la implementación de PVRB a nivel de consenso en la red, en ningún caso puede evitar los problemas de finalidad. La finalidad es un mecanismo utilizado en el consenso determinista, un bloque de bloqueo (y una cadena que conduce a él) que es final y nunca se eliminará, incluso si aparece una bifurcación paralela. Por ejemplo, no existe tal mecanismo en Bitcoin: si publica una cadena de mayor complejidad, reemplazará a una menos compleja, independientemente de la longitud de la cadena. Y en EOS, por ejemplo, los últimos son los llamados últimos bloques irreversibles, que aparecen en promedio cada 432 bloques (12 * 21 + 12 * 15, pre-voto + pre-compromiso). Este proceso esencialmente está esperando 2/3 de las firmas de productores de bloques (en adelante, BP). Cuando aparecen bifurcaciones que son más antiguas que la última LIB, simplemente se descartan. Este mecanismo le permite garantizar que la transacción se incluya en la cadena de bloques y que nunca se extraiga, sin importar los recursos que tenga el atacante. Además, los bloques finales son bloques firmados por 2/3 BP en Hyperledger, Tendermint y otros consensos basados ​​en pBFT. Además, un protocolo para garantizar la finalidad tiene sentido hacer un complemento de consenso, ya que puede funcionar de forma asíncrona con la producción y publicación de bloques. Aquí hay un buen artículo sobre cómo finalizar Ethereum.

La finalidad es extremadamente importante para los usuarios que, sin ella, pueden ser víctimas del ataque de "doble gasto" cuando BP "retiene" los bloques y los publica después de que la red "vio" una buena transacción. Si no hay finalidad, la bifurcación publicada reemplaza el bloque con la transacción "buena" con otra, desde la bifurcación "mala", en la que los mismos fondos se transfieren a la dirección del atacante. En el caso de PVRB, los requisitos para la finalidad todavía se están ajustando, ya que la construcción de horquillas para PVRB significa que un atacante puede preparar varias opciones para una casa aleatoria para publicar la más rentable para él, y limitar el tiempo de un posible ataque es una buena solución.

Por lo tanto, la mejor opción es combinar PVRB y finalidad en un protocolo; luego, el bloque finalizado = finalizado al azar, y esto es exactamente lo que tenía que obtener. Ahora los jugadores recibirán una aleatoriedad garantizada en N segundos, y pueden estar seguros de que es imposible retroceder o reproducirlo.

La opción integrada por consenso es buena:

• La posibilidad de una implementación asincrónica con respecto a la producción de bloques: los bloques se producen como de costumbre, pero en paralelo con esto, el protocolo PVRB puede funcionar, lo que no hace que cada bloque sea aleatorio
• la capacidad de implementar incluso criptografía pesada, sin las restricciones impuestas a los contratos inteligentes
• La capacidad de organizar los mensajes más rápido que las transacciones se incluyen en la cadena de bloques, por ejemplo, parte del protocolo puede funcionar entre nodos sin difundir mensajes a través de la red

También tiene desventajas:

• dificultades en las pruebas y el desarrollo: debe emular errores de red, nodos faltantes, horquillas de red
• los errores de implementación requieren una red hard fork

Ambos métodos de implementación de PVRB tienen derecho a la vida, pero la implementación de contratos inteligentes en blockchains modernos todavía es bastante limitada en recursos informáticos, y cualquier transición a una criptografía seria a menudo es simplemente imposible. Necesitaremos criptografía seria, como se demostrará más adelante. Aunque este problema es claramente temporal, se necesita una criptografía seria en los contratos para resolver muchos problemas, y aparece gradualmente (por ejemplo, contratos del sistema para zkSNARK en Ethereum)

La cadena de bloques, que proporciona un canal de mensajería de protocolo transparente y confiable, lo hace por una razón. Cualquier protocolo descentralizado debe tener en cuenta la posibilidad de un ataque de Sybil, cualquier acción puede ser realizada por las fuerzas coordinadas de muchas cuentas, por lo tanto, al diseñar, es necesario tener en cuenta las capacidades de los atacantes para crear un número arbitrario de participantes en el protocolo que actúan en colusión.

PVRB y variables de bloque.

No mentí cuando dije que hasta ahora nadie ha implementado un buen PVRB, verificado por muchas aplicaciones de juego, en blockchains. ¿Dónde, entonces, de tantas aplicaciones de juego en Ethereum y EOS? Me sorprende tanto como tú, bueno, ¿de dónde obtuviste tantos números aleatorios "persistentes" en un entorno completamente determinista?

La forma favorita de ser aleatorio en la cadena de bloques es tomar algún tipo de información "impredecible" del bloque, y basarse en ella para hacerla al azar, solo almacenar en caché uno o más valores. Un buen artículo sobre los problemas de tales esquemas aquí . Puede tomar algunos de los valores "impredecibles" en el bloque, por ejemplo, el hash del bloque, el número de transacciones, la complejidad de la red y otros valores desconocidos de antemano. Luego, almacénelos en caché, uno o más, y, en teoría, debería obtener un verdadero azar. Incluso puede agregar a wihitepaper que su esquema es "seguro post-cuántico" (ya que hay funciones hash a prueba cuántica :)).

Pero incluso los hashes seguros post-cuánticos no son suficientes, por desgracia. El secreto está en los requisitos para PVRB, los recuerdo de un artículo anterior:

1. El resultado debe tener una distribución demostrablemente uniforme, es decir, basada en una criptografía demostrablemente fuerte.
2. No es posible controlar ninguno de los bits del resultado. Como resultado, el resultado no se puede predecir de antemano.
3. No puede sabotear el protocolo de generación al no participar en el protocolo o al sobrecargar la red con mensajes de ataque
4. Todo lo anterior debe ser resistente a la colusión del número permitido de participantes deshonestos en el protocolo (por ejemplo, 1/3 de los participantes).

En este caso, solo se cumple el requisito 1 y no se cumple 2. Al generar valores impredecibles del bloque, obtenemos una distribución uniforme y una buena aleatoriedad. Pero BP tiene al menos la capacidad de "publicar un bloque o no". Por lo tanto, BP puede al menos elegir entre DOS opciones de aleatoriedad: "la nuestra" y una que resultará si alguien más hace el bloqueo. BP puede "espiar" de antemano lo que sucede si publica un bloqueo y simplemente decide hacerlo o no. Por lo tanto, jugando, por ejemplo, "impar-par" o "rojo / negro" en la ruleta, puede publicar un bloque solo si ve una victoria. También hace una estrategia inoperativa para usar, por ejemplo, un hash de un bloque del futuro. En este caso, dicen que “se usará un azar, que se obtiene al aplicar hash a los datos actuales y al hash del bloque futuro con una altura, por ejemplo, N + 42, donde N es la altura actual del bloque. Esto fortalece un poco el esquema, pero aún permite a BP, aunque en el futuro, elegir, retener el bloque o publicar.

BP suave en este caso es complicado, pero no mucho. Es solo que al validar e incluir una transacción en el bloque, se realiza una verificación rápida para ver si habrá una ganancia y, posiblemente, la selección de los parámetros de una transacción para obtener una alta probabilidad de ganar. Al mismo tiempo, atrapar un BP inteligente, para tales manipulaciones es casi imposible, cada vez que puede usar nuevas direcciones y ganar un poco, sin causar sospechas.

Por lo tanto, los métodos que utilizan la información del bloque no son adecuados para el papel de la implementación universal de PVRB. En una versión limitada, con restricciones en el tamaño de las apuestas, restricciones en el número de jugadores y / o registro KYC (para evitar que un jugador use múltiples direcciones), estos esquemas pueden funcionar para juegos pequeños, pero nada más.

PVRB y commit-revelar.

De acuerdo, gracias al hash y al menos a la relativa imprevisibilidad del hash del bloque y otras variables. Si resuelve el problema de los mineros de primera línea, debería obtener algo más adecuado. Agreguemos usuarios a este esquema, aunque también afectan la aleatoriedad: cualquier persona de soporte técnico le dirá que lo más aleatorio en los sistemas de TI son las acciones del usuario :)

El esquema ingenuo, cuando los usuarios simplemente envían números aleatorios, y el resultado se calcula como, por ejemplo, un hash de su suma, no es adecuado. En este caso, el último jugador puede elegir su propio control aleatorio de cuál será el resultado. Por lo tanto, se utiliza el patrón de confirmación-revelación muy utilizado. Los participantes primero envían hashes desde sus aleatorios (commit) s, y luego abren los aleatorios ellos mismos. La fase de "revelación" comienza solo después de que se ha recopilado la confirmación necesaria, por lo que los participantes pueden enviar exactamente el azar desde el que enviaron un hash antes. Ahora cegamos todo esto con los parámetros del bloque, y es mejor que el que se tomó del futuro (puede encontrar la aleatoriedad solo en uno de los bloques futuros), y listo, ¡el azar está listo! Ahora, cualquier jugador influye en la aleatoriedad resultante, y puede "derrotar" al BP malicioso bloqueándolo con su propio, previamente desconocido, aleatorio ... También puede agregar protección contra el sabotaje del protocolo al no abrirlo en la etapa de revelación, solo requiere aplicar una cierta cantidad a la transacción - depósito de seguro, que se devolverá solo durante el procedimiento de revelación. En este caso, hacer commit y no revelar será desventajoso.

Fue un buen intento, y tales esquemas también están en DApps de juegos, pero, por desgracia, esto nuevamente no es suficiente. Ahora, no solo el minero, sino cualquier participante en el protocolo puede influir en el resultado. Todavía es posible controlar el valor en sí, con un menor grado de variabilidad y por dinero, pero, como en el caso del minero, si los resultados del sorteo son más valiosos que la tarifa de participación en el protocolo PVRB, entonces el productor aleatorio (RP) puede decidir si revela y aún puede elegir entre al menos dos opciones aleatorias.
Pero hubo una oportunidad para castigar a quienes se comprometen y no revelan, y este esquema sigue siendo útil. Su simplicidad es una gran ventaja: los protocolos más serios requieren una informática mucho más potente.

PVRB y firmas deterministas.

Hay otra forma de obtener un RP para proporcionar un número pseudoaleatorio que no puede afectar si se le proporciona un "prototipo": esta es una firma determinista. Tal firma es, por ejemplo, RSA, y no es ECS. Si RP tiene un par de claves: RSA y ECC, y firma algún valor con su clave privada, en el caso de RSA obtendrá UNA Y SOLO UNA firma, y ​​en el caso de ECS puede generar cualquier cantidad de firmas válidas diferentes. Esto se debe al hecho de que al crear una firma ECS, se utiliza un número aleatorio, elegido por los firmantes, y se puede elegir según se desee, lo que le da al firmante la oportunidad de elegir una de varias firmas. En el caso de RSA: "un valor de entrada" + "un par de claves" = "una firma". Es imposible predecir cuál será la firma del otro RP, por lo que PVRB con firmas deterministas se puede organizar combinando las firmas RSA de varios participantes que firmaron el mismo valor. Por ejemplo, el anterior al azar. En este esquema, se ahorran muchos recursos, porque Las firmas son tanto una confirmación de la corrección del comportamiento del protocolo como una fuente de aleatoriedad.

Sin embargo, incluso con firmas deterministas, el esquema sigue siendo vulnerable al problema del "último actor". El último participante aún puede decidir si publica su firma o no, controlando así el resultado. Puede refinar el esquema, agregar bloques hash, hacer rondas para que el resultado no pueda predecirse con anticipación, pero todos estos métodos, incluso teniendo en cuenta muchas mejoras, aún dejan sin resolver el problema de la influencia de un participante en el resultado colectivo en un entorno no confiable y solo pueden funcionar en condiciones de limitaciones económicas y de tiempo. Además, el tamaño de las claves RSA (1024 y 2048 bits) es bastante grande, y el tamaño de las transacciones de blockchain es un parámetro extremadamente importante. Aparentemente de una manera simple no funcionará, vamos más allá.

PVRB y esquemas de intercambio secreto

En criptografía, existen esquemas que pueden permitir que la red acuerde uno y solo un valor de PVRB, mientras que dichos esquemas son resistentes a cualquier acción maliciosa de parte de los participantes. Un protocolo útil para conocer es el esquema de intercambio secreto de Shamir. Sirve para dividir un secreto (por ejemplo, una clave secreta) en varias partes y para distribuir estas partes a N participantes. El secreto se distribuye de tal manera que M partes de N son suficientes para su restauración, mientras que puede ser cualquier parte M. Si está en los dedos, luego de tener un gráfico de una función desconocida, los participantes intercambian puntos en el gráfico, y después de recibir M puntos, se puede restaurar toda la función.
Se da una buena explicación en el wiki y jugar con él prácticamente para perder el protocolo en tu cabeza es útil en la página de demostración .

Si el esquema FSSS (Fiat-Shamir Secret Sharing) fuera aplicable en su forma pura, sería un PVRB indestructible. En la versión más simple, el protocolo puede verse así:

• Cada participante genera su propio azar y distribuye acciones a los demás 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, -.

Conclusión

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

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

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

, , , , :)