Ergo y el Mecanismo de Consenso Autolykos: Parte I

Lo siguiente es un desglose técnico y detallado del mecanismo de consenso de Ergo, Autolykos. Dado que este es un tema extenso y detallado, lo publicaremos en segmentos durante las próximas dos semanas. En la Parte I, el autor comienza a desglosar el pseudocódigo de minería de bloques y nos guía a través de la creación de "lista R."

Parte I

Autolykos, el mecanismo de consenso de Ergo, es uno de los pocos rompecabezas de prueba de trabajo, asimétricos y resistentes a ASIC, que sigue siendo resistente a ASIC, asegurando así que la blockchain se mantenga lo más descentralizada posible. Autolykos se basa en el documento de Equihash[1] y el problema del cumpleaños. Para resumir, se le encarga al minero encontrar k (=32) de N elementos, de tal manera que el hash de la suma de los elementos sea menor que el objetivo. El siguiente pseudocódigo explica el proceso de minería y este análisis desglosará cada línea extensamente, ya que hay muy pocos recursos en línea que expliquen Autolykos en su totalidad.

Pseudocódigo de Minería de Bloques Autolykos

Antes de discutir el procedimiento de minería de bloques, el algoritmo primero requiere un grupo cíclico muy grande G de orden primo q con generador fijo g y elemento identidad e. Este grupo primo se utiliza para devolver enteros en Z/qZ durante la función de hash basada en Blake2b256.

Ejemplo de grupo cíclico con generador z, elemento identidad 1, orden 6[2]

No nos centraremos extensamente en el grupo cíclico, ya que solo cubre un pequeño segmento del esquema de PoW. Ahora, abordemos la minería de bloques de Autolykos línea por línea.

Línea 1 – Entrada h y m

El PoW comienza con las dos entradas: la altura del bloque h y el hash del encabezado del próximo bloque m. El hash del encabezado del bloque es un hash de los componentes del encabezado del bloque, como el hash del encabezado del bloque anterior, raíz de Merkle, nonce, etc.

Línea 2 – Calcular lista R

En primer lugar, es importante notar la notación H() en la línea 2. Esta notación llama a la función de hash Algoritmo 3. El Algoritmo 3 es una función hash basada en Blake2b256 y se utiliza a lo largo de Autolykos. El Algoritmo 3 establece que si el hash de Blake de las entradas está por debajo de 2²⁵⁶ (= 16⁶⁴ = 0xFFFFFFFFFFFF86633A9E8F1256D61ED5325EBF2A4B4366BA0000000000000000), entonces se devuelve hash.mod(q). Si no, el Algoritmo 3 se repite hasta que alcanza un hash numérico dentro del rango válido. Para referencia, note que q es el orden primo del grupo G, las salidas del hash de Blake2b256 son de 256 bits, 64 dígitos de longitud, y el Algoritmo 3 siempre devolverá un hash numérico en Z/qZ.

Función de Hash Basada en Blake2b256

En la línea 2, el enfoque es la creación de lista R. Lista R contiene r valores que son hashes numéricos de 31 bytes creados a partir de enteros en [0, N). Los valores r se generan mediante takeright(31,H(j||h||M)). Las variables son las siguientes:

• j, entero en [0, N)
• h, altura del bloque
• M, 8kb de datos constantes - relleno para ralentizar el cálculo del hash

La sección takeRight(31,H(…)) significa que dado H(…), una salida de 32 bytes de Blake2b256, se devuelven los 31 bytes a la derecha (es decir, en little endian (mientras que otros algoritmos de hash son bit endian)). En otras palabras, se descarta el byte más significativo, el byte más a la izquierda. Como resultado, cada valor r es los 31 bytes menos significativos derivados de la salida de 32 bytes H(j||h||M)). Por ejemplo, si j = 1, r1 = takeRight(31,H(1||h||M)). Lista R consiste en N elementos y puede generarse para cada bloque incrementando j en 1 N-1 veces. Dado que H(…) devuelve hash.mod(q), podemos afirmar que lista R consiste en r0, 1, 2, 3 … N-1 y lista R ⊂ Z/qZ. Como se indica en el libro blanco de Autolykos v2[3], “N elementos se derivan de la altura del bloque y constantes, a diferencia de Autolykos v1, por lo que los mineros pueden recalcular fácilmente los candidatos a bloque ahora (solo los índices dependen de ellos).” En otras palabras, j siempre está en [0,N), N está determinado por h, M es siempre constante, y h cambia cada bloque, la única variable que un minero necesita para calcular lista R es h.

La lista R se almacena en RAM. En Autolykos, N = 2²⁶ (67,108,864 enteros) se utiliza en la implementación para cada bloque antes de 614400. Por lo tanto, el requisito de memoria para bloques antes del bloque 614400 es (226 * 31 bytes =) 2.08GB. N aumentó por primera vez en el bloque 614400. Después del bloque 614400, cada 51200 bloques, N aumenta en un 5%. En otras palabras, el requisito de memoria de un minero de Ergo aumenta en un 5% cada ~71 días. En el bloque 4198400, el valor de N se vuelve constante y es igual a 2,143,944,600[4]. Tenga en cuenta que los últimos 2 valores listados en la tabla deberían ser 2,143,944,600 y no 2,147,387,550. Después del bloque 4198400, el requisito de almacenamiento de lista R será (31 bytes * 2,143,944,600) = 66.46GB.

N elementos basados en la altura del bloque

N elementos, Ethash vs. Autolykos

Autolykos es como Ethash en el sentido de que la altura del bloque determina N elementos que se almacenan en RAM. Con Autolykos, la altura del bloque determina N hashes numéricos de 31 bytes que se almacenan. Con Ethash, la altura del bloque determina N páginas DAG de 128B que se almacenan. Podrías preguntarte, si un bloque de Ergo ocurre cada 2 minutos, ¿cómo pueden los mineros de Ergo generar un conjunto de datos de más de 2GB tan rápido? Los mineros de Ethereum solo regeneran el DAG cada 100 horas porque toma tanto tiempo... Para un minero de Ergo, la carga de calcular lista R son N instancias del Algoritmo 3; recuerda, cada valor r se calcula como takeRight(31,H(j||h||M)). Sin embargo, una GPU puede hacer esto muy rápidamente, las GPUs generalmente tienen multiprocesadores de 32 o 64 anchos, lo que significa que 32 o 64 instancias del Algoritmo 3 pueden hacerse simultáneamente dependiendo de la GPU. Por ejemplo, una GPU de 32 anchos como la RTX570 puede llenar lista R en solo unos segundos.

Para la Parte II, continuaremos desde aquí y seguiremos la explicación de Autolykos v2. Mantente atento a los canales de redes sociales de Ergo para actualizaciones sobre la Parte II de esta serie.

[1] https://www.researchgate.net/publication/316904748_Equihash_Asymmetric_Proof-of-Work_Based_on_the_Generalized_Birthday_Problem
[2] https://en.wikipedia.org/wiki/Cyclic_group#/media/File:Cyclic_group.svg
[3] https://www.docdroid.net/mcoitvK/ergopow-pdf
[4] https://www.ergoforum.org/t/autolykos-v-2-details/480
[5] Crédito a Wolf9466#9466 en Discord