Ergo y el Mecanismo de Consenso Autolykos: Parte II

La semana pasada, presentamos una exploración en profundidad del mecanismo de consenso Autolykos de Ergo. Con este artículo, completamos la segunda parte de esa discusión y profundizamos en más detalles. Antes de leer este documento, se recomienda que los lectores echen un vistazo a la Parte I.

Como recordatorio, aquí están los pseudocódigos de minería de bloques y función hash.

Pseudocódigo de Minería de Bloques Autolykos

Función Hash Basada en Blake2b256

Líneas 3, 4 – comienza el bucle while y la adivinanza

Después de calcular list R, el minero crea una adivinanza de nonce y entra en un bucle para probar si el nonce finalmente crea una salida que esté por debajo del valor objetivo dado.

Líneas 5, 6 – semilla para generar índices

La línea 5, i = takeRight(8, H(m||nonce)) mod N, produce un entero en [0,N). Se utiliza el Algoritmo 3 pero con m y el nonce como entradas. Una vez que se devuelve el hash H(m||nonce), se conservan los 8 bytes menos significativos y luego se pasan por mod N. Como nota al margen, el valor entero más alto posible con 8 bytes es 2⁶⁴ – 1, y asumiendo N = 2²⁶, un hash de 8 bytes mod N resultará en que los primeros dígitos sean cero. El número de ceros en i disminuye a medida que N crece.

La línea 6 produce e, una semilla para la generación de índices. Se llama al Algoritmo 3 con las entradas i (generado en la línea 5), h, y M. Luego, se descarta el byte más significativo del hash numérico, y los 31 bytes restantes se conservan como valor e. También debe notarse que el valor e puede ser recuperado de list R en lugar de ser computado, ya que e es un valor r.

Línea 7 – generador de índices

El índice de elemento J se crea utilizando el Algoritmo 6 con las entradas e, m, y nonce. La función genIndexes es una pseudorandom que devuelve una lista de k (=32) números en [0,N).

función genIndexes

Hay un par de pasos adicionales que no se muestran en el pseudocódigo, como un byteswap. La creación y aplicación de genIndexes se puede explicar a través del siguiente ejemplo:

GenIndexes(e||m||nonce)...

hash = Blake2b256(e||m||nonce) = [0xF963BAA1C0E8BF86, 0x317C0AFBA91C1F23, 0x56EC115FD3E46D89, 0x9817644ECA58EBFB]

hash64to32 = [0xC0E8BF86, 0xF963BAA1, 0xA91C1F23, 0x317C0AFB, 0xD3E46D89 0x56EC115F, 0xCA58EBFB, 0x9817644E]

extendedhash (es decir, byteswap y concatenar 4 bytes repitiendo los primeros 4 bytes) = [0x86BFE8C0, 0xA1BA63F9, 0x231F1CA9, 0xFB0A7C31, 0x896DE4D3, 0x5F11EC56, 0xFBEB58CA, 0x4E641798, 0x86BFE8C0]

El siguiente código en python muestra el proceso de segmentación del hash extendido, devolviendo índices k. En este ejemplo asumimos que h < 614,400, por lo tanto N = 2²⁶ (67,108,864).

Segmentación y mod N[1]
for i in range(8):
idxs[i << 2] = r[i] % np.uint32(ItemCount)
idxs[(i << 2) + 1] = ((r[i] << np.uint32(8)) | (r[i + 1] >> np.uint32(24))) % np.uint32(ItemCount)
idxs[(i << 2) + 2] = ((r[i] << np.uint32(16)) | (r[i + 1] >> np.uint32(16))) % np.uint32(ItemCount)
idxs[(i << 2) + 3] = ((r[i] << np.uint32(24)) | (r[i + 1] >> np.uint32(8))) % np.uint32(ItemCount)

La conclusión principal es que la segmentación devuelve k índices que son valores pseudorandom derivados de la semilla, es decir, e, m, y nonce.

return [0x2BFE8C0, 0x3E8C0A1, 0xC0A1BA, 0xA1BA63, 0x1BA63F9, 0x263F923, 0x3F9231F, 0x1231F1C, 0x31F1CA9, 0x31CA9FB, 0xA9FB0A, 0x1FB0A7C, 0x30A7C31, 0x27C3189, 0x31896D, 0x1896DE4, 0x16DE4D3, 0x1E4D35F, 0xD35F11, 0x35F11EC, 0x311EC56, 0x1EC56FB, 0x56FBEB, 0x2FBEB58, 0x3EB58CA, 0x358CA4E, 0xCA4E64, 0x24E6417, 0x2641798, 0x179886, 0x39886BF, 0x86BFE8]

Este índice se puede traducir a valores en base 10 ya que se refiere a números en [0, N). Por ejemplo, 0x2BFE8C0 = 46131392, 0x3E8C0A1 = 65585313, 0xC0A1BA = 12624314, y así sucesivamente. El minero utiliza estos índices para recuperar k r valores.

La función genIndexes previene optimizaciones ya que es extremadamente difícil, básicamente imposible, encontrar una semilla tal que genIndexes(seed) devuelva los índices deseados.

Línea 8 – suma de elementos r dados k

Usando el índice generado en línea 7, el minero recupera los correspondientes k (=32) r valores de list R y suma estos valores. Esto puede sonar confuso, pero desglosémoslo.

Continuando con el ejemplo anterior, el minero almacena los siguientes índices:

{0 | 46,131,392},
{1 | 65,585,313},
{2 | 12,624,314},
{3 | 10,599,011},
…
{31 | 8,830,952}

Dado los índices anteriores, el minero recupera los siguientes valores r de list R almacenados en memoria.

{0 | 46,131,392} → dropMsb(H(46,131,392||h||M))
{1 | 65,585,313} → dropMsb(H(65,585,313||h||M))
{2 | 12,624,314} → dropMsb(H(12,624,314||h||M))
{3 | 10,599,011} → dropMsb(H(10,599,011||h||M))
…
{31 | 8,830,952} → dropMsb(H(8,830,952||h||M))

Nota que Takeright(31) operado en un hash de 32 bytes también se puede escribir como dropMsb – eliminar el byte más significativo.

Dado que el minero ya almacena list R en RAM, no necesita computar k (= 32) funciones Blake2b256 y en su lugar busca los valores. Esta es una característica clave de la resistencia ASIC. Un ASIC con memoria limitada necesita computar 32 iteraciones de Blake2b256 para obtener los valores que podrían haber sido buscados en memoria, y la búsqueda en memoria toma mucho menos tiempo. Sin mencionar que, un ASIC con memoria limitada requeriría 32 instancias de Blake2b256 físicamente en el chip para lograr un hash por ciclo, lo que requeriría más área y costos más altos. Es simple demostrar que almacenar list R en memoria vale la pena el sacrificio. Supongamos lo siguiente, una GPU tiene una tasa de hash de G = 100MH/s, _N = 2²⁶, k = 32, intervalo de bloque t = 120 segundos, y los elementos se buscan cada 4 hashes. Me gusta suponer que los elementos se buscan cada 4 hashes porque, para cada adivinanza de nonce, múltiples elementos como i, J, y H(f) requieren instancias del Algoritmo 3, es decir, instancias de hash blake2b. Podemos estimar que cada valor r se utilizará, en promedio, (G * k * t)/(N*4) = 1430.51 veces.

Una vez que se buscan los 32 valores r, se suman.

Líneas 9, 10, 11, 12 – verificar si el hash de la suma está por debajo del objetivo

La suma de los 32 valores r se hashea utilizando el Algoritmo 3, y si la salida está por debajo del objetivo b, el PoW es exitoso, m y nonce se devuelven a los nodos de la red, y el minero es recompensado en ERG. Si el hash de la suma está por encima del objetivo, se repiten Líneas 4 – 11 con un nuevo nonce.

Si has llegado hasta aquí, ¡felicitaciones! Después de leer toda esta información, deberías tener una buena comprensión de Autolykos v2. Si deseas ver una demostración visual de Autolykos, consulta el gráfico al final de este documento. Si deseas una explicación en video, puedes encontrarla aquí.

Resistencia ASIC

Sabemos por Ethereum que los algoritmos 'difíciles de memoria' pueden ser conquistados integrando memoria en ASICs. Ergo es diferente, pero primero revisemos por qué un ASIC con memoria limitada es no competitivo y por qué un minero necesita almacenar list R. La línea 8 de la minería de bloques Autolykos disuade a las máquinas con memoria limitada. Si un minero ASIC no almacena list R, requiere muchos núcleos para generar los hashes numéricos de 31 bytes sobre la marcha. No se pueden calcular eficientemente 32 valores r utilizando un bucle de un solo núcleo porque solo se generaría una salida cada 32 ciclos de hash. Dado J, para computar un nonce por ciclo de hash, se necesitan al menos 32 instancias de Blake2b256 ejecutando dropMsb(H(j||h||M)). Como mencionamos anteriormente, esto aumenta significativamente el tamaño del chip y el costo. Está claro que almacenar list R vale la pena porque tener 32, o incluso 16, núcleos es muy caro. Más al punto, leer memoria es más rápido que computar instancias de Blake cada vez que se prueba un nonce.

Veamos si un ASIC con suficiente memoria es competitivo porque eso es más relevante para la discusión. Comparando Ethash y Autolykos, la diferencia es que Ethash involucra N elementos al hashear el nonce y mezcla el encabezado 64 veces, mientras que Autolykos involucra N elementos al recuperar 32 valores r basados en índices generados. Para cada nonce probado, Autolykos ejecuta alrededor de 4 instancias de Blake2b256 y 32 búsquedas de memoria, mientras que Ethash ejecuta alrededor de 65 instancias similares a SHA-3 y 64 búsquedas de memoria. Sin mencionar que, k está actualmente establecido en 32, pero este valor puede aumentarse para recuperar más valores r si es necesario. Los ASIC que ejecutan Ethash tienen mucho margen para aumentar la velocidad de hash SHA3, ya que se completan 65 hashes por nonce probado en comparación con alrededor de 4 en Autolykos. La proporción de búsquedas de memoria a instancias de hash es mucho mayor en Autolykos. Por esta razón, Autolykos es más difícil de memoria que Ethash, ya que el ancho de banda de memoria juega un papel mucho más grande en comparación con la velocidad de hash.

Un área donde se podría optimizar Autolykos es el llenado de list R. El llenado de list R requiere N instancias de una función Blake2b256. N es grande y solo está creciendo, así que eso es mucho hashing. Un ASIC podría optimizar la velocidad de Blake2b256, lo que daría más tiempo para la minería de bloques ya que list R se llena más rápido. Aunque esto se puede hacer, llenar list R requiere recorrer [0, N) y una GPU con multiprocesadores de 32 anchos ya puede llenar list R muy rápido (en segundos). Se necesitaría un ASIC con muchos núcleos Blake para ser significativamente más rápido, nuevamente, muy caro, y probablemente no valga la pena ya que el cuello de botella podría convertirse en el ancho de banda de escritura de memoria (es decir, escribir list R en RAM en lugar de la velocidad de hash).

La última área que se puede optimizar para Autolykos es la velocidad de lectura/escritura de memoria. Los mineros ASIC de Ethash tienen una velocidad de lectura ligeramente más rápida en comparación con las GPUs, ya que la memoria está cronometrada más alta sin el efecto de estrangulación de la GPU. Sin embargo, esta diferencia es bastante insignificante y se espera que se vuelva más insignificante a medida que las GPUs avancen. Esto se debe a que el hardware de memoria en sí es el mismo: DRAM. Uno podría cuestionar si se podría utilizar un hardware de memoria más rápido donde la velocidad de lectura y escritura de memoria sea mucho más rápida... SRAM, por ejemplo, podría ser un paso imaginativo para romper algoritmos difíciles de memoria, sin embargo, SRAM no es una solución viable simplemente porque es menos densa.

SRAM en FPGA[2]

La foto anterior es un FPGA con 8 chips de memoria en el frente, y hay otros 8 en la parte posterior. La memoria total SRAM es solo 576MB. Colocar suficiente SRAM en un chip no funcionará porque la SRAM necesitará ser colocada más lejos del núcleo ya que no es lo suficientemente densa para caber en una capa alrededor del núcleo. Esto puede resultar en retrasos de lectura/escritura porque la electricidad necesita viajar distancias más largas, aunque el hardware en sí sea más rápido. Además, para minar Ergo, el requisito de memoria aumenta a medida que N aumenta, por lo que colocar suficiente SRAM no es factible con el tiempo. Por lo tanto, los ASIC de SRAM no valen la pena explorar, incluso si uno tuviera suficiente dinero para gastar en SRAM.

Blake2b256

Una gran diferencia entre un algoritmo como Autolykos y otros es el uso de Blake2b256. Esto no es una coincidencia. Blake depende en gran medida de operaciones de suma para la mezcla de hash en lugar de operaciones XOR. Una operación como XOR se puede hacer bit a bit, mientras que la suma requiere bits de acarreo. Por lo tanto, Blake requiere más potencia y área de núcleo en comparación con los algoritmos SHA, pero sigue siendo tan seguro y, de hecho, más rápido. Como se menciona en el sitio web de Blake2, “BLAKE2 es rápido en software porque explota características de las CPUs modernas, a saber, paralelismo a nivel de instrucción, extensiones de conjunto de instrucciones SIMD y múltiples núcleos.”[3] Por lo tanto, aunque un ASIC puede producir instancias de Blake más rápido, la naturaleza innata de la función limita las optimizaciones al requerir suma e involucrar características que se encuentran en CPUs así como en GPUs.

velocidad de Blake2b en relación con otras funciones hash

Conclusión

Autolykos es una gran innovación que es una respuesta necesaria para combatir el auge de las máquinas ASIC optimizadas para PoW. Esperamos que esta serie de 2 partes te haya ayudado a entender Autolykos a un nivel más técnico y por qué es más difícil de memoria que Ethash. A medida que Ethereum transiciona a una red PoS, habrá una gran comunidad de mineros buscando un lugar para dirigir su poder de hash, y Ergo debería ser un jugador significativo en atraer a esos mineros.

Si disfrutaste este artículo, el autor te invita a consultar más contenido a través de su cuenta de Twitter, @TheMiningApple.

[1] Crédito a Wolf9466#9466 en Discord
[2] http://www.ldatech.com/_images/imageGallery/SBM09P-3_front.jpg
[3] https://www.blake2.net/#:~:text=A%3A%20BLAKE2%20is%20fast%20in,of%20the%20designers%20of%20BLAKE2).