Análisis del principio del algoritmo Chia VDF

Con el surgimiento del popular producto Chia, la industria minera tiene una forma más novedosa y amigable de jugar, es decir, el método de minería de disco duro de bajo umbral. Este método de minería permite que cada vez más personas comunes participen en la minería. , Siente el auge de la industria blockchain juntos.

Según el libro blanco de Chia, los mecanismos de consenso adoptados por Chia son prueba de espacio (POS, Prueba de espacio) y prueba de tiempo (POT, Prueba de tiempo). POS se utiliza principalmente para comprobar que el usuario tiene espacio de almacenamiento sin utilizar, mientras que POT se utiliza para garantizar la seguridad de todo el sistema. Su algoritmo principal es VDF (Función de retardo verificable), y los resultados de cálculo obtenidos por VDF deben ser posteriores. un cierto período de tiempo, y puede ser autenticado rápidamente por cualquier nodo de la red, lo que aumenta la probabilidad de que POS obtenga el bloque correcto.

Verificable: después de un cierto número de cálculos, el probador puede generar rápidamente una pequeña prueba para probar la validez del cálculo, y el verificador puede saber la exactitud del cálculo sin repetir el cálculo;

Retraso: es decir, el probador solo puede obtener el resultado correcto después de realizar la cantidad correcta de cálculos, y no habrá ninguna situación en la que se obtenga el resultado correcto antes de alcanzar la cantidad especificada de veces;

Función: es decir, el resultado es determinista, si ingresa x, obtendrá y.

La Oficina del Fiscal General de Nueva York emitió una advertencia sobre la inversión en criptomonedas: el 4 de marzo, la Oficina del Fiscal General de Nueva York (NYAG) emitió dos advertencias sobre la inversión en criptomonedas, recordando a los inversores de Nueva York que estén atentos a los riesgos de invertir en criptomonedas. La advertencia recomienda extrema precaución al invertir en monedas virtuales, ya que la negociación en el mercado actual expone a los inversores a riesgos extremos, como cambios bruscos de precios, conflictos de intereses entre los operadores de la plataforma de negociación y mayores oportunidades de manipulación del mercado.

La procuradora general Letitia James recordó a los corredores, comerciantes, vendedores y asesores de inversiones que podrían enfrentar “responsabilidad civil y penal” si no cumplen con sus obligaciones relacionadas con el registro en el estado de Nueva York al hacer negocios con el estado. (noticias de amsterdam) [2021/3/4 18:14:46]

Figura 1 BOTE

Cálculo de VDF

Según el patrón de diseño de Chia, si la velocidad de cálculo de VDF de un nodo es mayor que la de otros nodos, puede lanzar algún tipo de ataque de seguridad. Por lo tanto, para evitar esta amenaza, Chia espera que el algoritmo VDF que se ejecuta en los nodos sea el más eficiente, por lo que básicamente no hay espacio para la optimización. Con este fin, Chia también realizó dos competencias de eficiencia de VDF, atrayendo a las élites de la industria a participar en este evento con altas recompensas y absorbiendo ampliamente la sabiduría de todos para obtener el VDF más eficiente.

Como se muestra en la figura anterior, el algoritmo VDF utilizado en Chia es realmente muy simple, que consiste en realizar cálculos continuos de T cuadrados en un número x, donde x es un elemento de un grupo de orden desconocido. La razón por la que es un grupo de orden desconocido también es muy simple:

Si el orden del grupo es d, entonces según la naturaleza del grupo: x2^T = x(2^T) % d

Habrá un resultado correcto antes de llegar al número especificado de veces T, lo cual es inconsistente con el diseño de Chia, por lo tanto, no se puede saber el orden del grupo, hay dos formas de generar un grupo de orden desconocido:

grupo basado en RSA;

Grupo de campo cuadrático virtual;

Al elegir el método basado en RSA, el orden del grupo es N=pq, donde p y q son ambos números primos grandes y no se pueden hacer públicos, por lo que la dificultad de calcular el orden de este grupo es tan difícil como descomponer el gran numero n Por lo tanto, se considera seguro, pero este método requiere configuraciones confiables, es decir, p y q son generados por un tercero confiable, y también se puede usar MPC, pero en resumen, requiere configuraciones confiables;

El grupo basado en el campo cuadrático imaginario puede eliminar la configuración creíble, porque es difícil calcular el orden de un grupo generado por un número primo grande negativo que satisface la relación |d|=3 mod 4 (por qué es difícil, será en otro artículo elaborado en detalle, involucrando muchos conceptos matemáticos, trataré de escribir conciso y fácil de entender), porque este gran número primo puede hacerse público, por lo que este método puede generar fácilmente grupos de orden desconocido que no requieren configuraciones creíbles .

Después de comprender los conceptos matemáticos detrás de esto, echemos un vistazo a cómo calcular el cuadrado de los elementos en función de grupos de dominios cuadráticos imaginarios, como se muestra en la figura a continuación (los algoritmos se refieren a los documentos NUDUPL):

Figura 2 si a <L

Figura 3 si a >L

El algoritmo NUDUPL es, con diferencia, el método más eficaz para calcular el cuadrado del campo cuadrático imaginario, y también es el método más utilizado por los participantes en los dos concursos de algoritmos VDF. La Figura 2 y la Figura 3 muestran las dos ramas principales del algoritmo, donde m = (a,b,c) y M = (A,B,C) son las representaciones de los elementos del grupo.

Certificado de VDF

Se puede ver en la Figura 1 que además de hacer cálculos T, el probador también necesita generar una prueba para probar la corrección del cálculo. Con respecto a la prueba de la corrección de VDF, este documento proporciona dos métodos clásicos. Chia usa es El método de argumentación de Wesolowski, y el proceso de este método se muestra en la siguiente figura:

El algoritmo en sí es simple y fácil de entender. Comparado con el algoritmo de Pietrzak en el documento, este algoritmo genera pruebas más pequeñas y verifica las pruebas más rápido.

Conclusión

Después de un período de investigación y pruebas, el algoritmo VDF utilizado actualmente por Chia es bastante eficiente Desde el punto de vista del algoritmo, no se ha encontrado ningún punto que pueda optimizarse en gran medida. “Si no es suave, entonces es difícil.” Esta es una de las razones por las que todavía insistimos en investigar muy profundamente el algoritmo VDF de Chia, y ya hemos comenzado el diseño de optimización de hardware. Teóricamente hablando, con un cálculo de VDF de mayor eficiencia, se puede obtener una mayor eficiencia de minería, que también es nuestro objetivo.

Tags：

Bitcoin