Saltar al contenido principal
Change page

Dagger-Hashimoto

Dagger-Hashimoto fue la implementación de investigación y especificación original para el algoritmo de minería de Ethereum. Dagger-Hashimoto fue reemplazado por Ethash. La minería se desactivó por completo en La Fusión el 15 de septiembre de 2022. Desde entonces, Ethereum se ha protegido utilizando un mecanismo de prueba de participación (PoS) en su lugar. Esta página es de interés histórico: la información aquí ya no es relevante para el Ethereum posterior a La Fusión.

Requisitos previos

Para comprender mejor esta página, le recomendamos que primero lea sobre el consenso de prueba de trabajo (PoW), la minería y los algoritmos de minería.

Dagger-Hashimoto

Dagger-Hashimoto tiene como objetivo satisfacer dos objetivos:

  1. Resistencia a los ASIC: el beneficio de crear hardware especializado para el algoritmo debe ser lo más pequeño posible.
  2. Verificabilidad por cliente ligero: un bloque debe ser verificable de manera eficiente por un cliente ligero.

Con una modificación adicional, también especificamos cómo cumplir un tercer objetivo si se desea, pero a costa de una complejidad adicional:

Almacenamiento completo de la cadena: la minería debería requerir el almacenamiento del estado completo de la cadena de bloques (debido a la estructura irregular del trie de estado de Ethereum, anticipamos que será posible realizar alguna poda, particularmente de algunos contratos de uso frecuente, pero queremos minimizar esto).

Generación de DAG

El código para el algoritmo se definirá en Python a continuación. Primero, damos encode_int para la serialización de enteros sin signo de precisión especificada a cadenas. También se da su inversa:

A continuación, asumimos que sha3 es una función que toma un número entero y genera un número entero, y dbl_sha3 es una función double-sha3; si convierte este código de referencia en una implementación, use:

Parámetros

Los parámetros utilizados para el algoritmo son:

P en este caso es un número primo elegido de tal manera que log₂(P) es un poco menos de 512, lo que corresponde a los 512 bits que hemos estado usando para representar nuestros números. Tenga en cuenta que en realidad solo es necesario almacenar la última mitad del DAG, por lo que el requisito de RAM de facto comienza en 1 GB y crece 441 MB por año.

Construcción del grafo Dagger

La primitiva de construcción del grafo Dagger se define de la siguiente manera:

Esencialmente, inicia un grafo como un solo nodo, sha3(seed), y a partir de ahí comienza a agregar secuencialmente otros nodos basados en nodos anteriores aleatorios. Cuando se crea un nuevo nodo, se calcula una potencia modular de la semilla para seleccionar aleatoriamente algunos índices menores que i (usando x % i arriba), y los valores de los nodos en esos índices se usan en un cálculo para generar un nuevo valor para x, que luego se introduce en una pequeña función de prueba de trabajo (basada en XOR) para generar finalmente el valor del grafo en el índice i. La lógica detrás de este diseño en particular es forzar el acceso secuencial del DAG; el siguiente valor del DAG al que se accederá no se puede determinar hasta que se conozca el valor actual. Finalmente, la exponenciación modular aplica un hash adicional al resultado.

Este algoritmo se basa en varios resultados de la teoría de números. Consulte el apéndice a continuación para obtener una explicación.

Evaluación del cliente ligero

La construcción del grafo anterior tiene la intención de permitir que cada nodo en el grafo se reconstruya calculando un subárbol de solo un pequeño número de nodos y requiriendo solo una pequeña cantidad de memoria auxiliar. Tenga en cuenta que con k=1, el subárbol es solo una cadena de valores que sube hasta el primer elemento en el DAG.

La función de cálculo del cliente ligero para el DAG funciona de la siguiente manera:

Esencialmente, es simplemente una reescritura del algoritmo anterior que elimina el bucle de cálculo de los valores para todo el DAG y reemplaza la búsqueda de nodo anterior con una llamada recursiva o una búsqueda en caché. Tenga en cuenta que para k=1 la caché es innecesaria, aunque una optimización adicional en realidad precalcula los primeros miles de valores del DAG y los mantiene como una caché estática para los cálculos; consulte el apéndice para ver una implementación de código de esto.

Doble búfer de DAG

En un cliente completo, se utiliza un doble búfer (opens in a new tab) de 2 DAG producidos por la fórmula anterior. La idea es que los DAG se producen cada número epochtime de bloques de acuerdo con los parámetros anteriores. En lugar de que el cliente use el último DAG producido, usa el anterior. El beneficio de esto es que permite que los DAG sean reemplazados con el tiempo sin necesidad de incorporar un paso donde los mineros deban recalcular repentinamente todos los datos. De lo contrario, existe la posibilidad de una desaceleración temporal abrupta en el procesamiento de la cadena a intervalos regulares y un aumento drástico de la centralización. Por lo tanto, existen riesgos de un ataque del 51% en esos pocos minutos antes de que se recalculen todos los datos.

El algoritmo utilizado para generar el conjunto de DAG utilizados para calcular el trabajo de un bloque es el siguiente:

Hashimoto

La idea detrás del Hashimoto original es usar la cadena de bloques como un conjunto de datos, realizando un cálculo que selecciona N índices de la cadena de bloques, recopila las transacciones en esos índices, realiza un XOR de estos datos y devuelve el hash del resultado. El algoritmo original de Thaddeus Dryja, traducido a Python por coherencia, es el siguiente:

def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
    hash_output_A = sha256(prev_hash + merkle_root + nonce)
    txid_mix = 0
    for i in range(64):
        shifted_A = hash_output_A >> i
        transaction = shifted_A % len(list_of_transactions)
        txid_mix ^= list_of_transactions[transaction] << i
    return txid_mix ^ (nonce << 192)

Desafortunadamente, aunque Hashimoto se considera difícil para la RAM, se basa en aritmética de 256 bits, lo que tiene una sobrecarga computacional considerable. Sin embargo, Dagger-Hashimoto solo usa los 64 bits menos significativos al indexar su conjunto de datos para abordar este problema.

def hashimoto(dag, dagsize, params, header, nonce):
    m = dagsize / 2
    mix = sha3(encode_int(nonce) + header)
    for _ in range(params["accesses"]):
        mix ^= dag[m + (mix % 2**64) % m]
    return dbl_sha3(mix)

El uso de doble SHA3 permite una forma de preverificación casi instantánea y sin datos, verificando solo que se proporcionó un valor intermedio correcto. Esta capa externa de prueba de trabajo es muy amigable con los ASIC y bastante débil, pero existe para hacer que los ataques DDoS sean aún más difíciles, ya que esa pequeña cantidad de trabajo debe realizarse para producir un bloque que no sea rechazado de inmediato. Aquí está la versión para cliente ligero:

def quick_hashimoto(seed, dagsize, params, header, nonce):
    m = dagsize // 2
    mix = sha3(nonce + header)
    for _ in range(params["accesses"]):
        mix ^= quick_calc(params, seed, m + (mix % 2**64) % m)
    return dbl_sha3(mix)

Minería y verificación

Ahora, juntemos todo en el algoritmo de minería:

Aquí está el algoritmo de verificación:

def verify(daggerset, params, block, nonce):
    result = hashimoto(daggerset, get_dagsize(params, block),
                       params, decode_int(block.prevhash), nonce)
    return result * params["diff"] < 2**256

Verificación amigable para el cliente ligero:

def light_verify(params, header, nonce):
    seedset = get_seedset(params, block)
    result = quick_hashimoto(seedset["front_hash"], get_dagsize(params, block),
                             params, decode_int(block.prevhash), nonce)
    return result * params["diff"] < 2**256

Además, tenga en cuenta que Dagger-Hashimoto impone requisitos adicionales en el encabezado del bloque:

  • Para que funcione la verificación de dos capas, un encabezado del bloque debe tener tanto el nonce como el valor medio pre-sha3
  • En algún lugar, un encabezado del bloque debe almacenar el sha3 del conjunto de semillas actual

Lecturas adicionales

¿Conoce algún recurso de la comunidad que le haya ayudado? ¡Edite esta página y agréguelo!

Apéndice

Como se señaló anteriormente, el RNG (generador de números aleatorios) utilizado para la generación de DAG se basa en algunos resultados de la teoría de números. Primero, brindamos la seguridad de que el RNG de Lehmer que es la base de la variable picker tiene un período amplio. En segundo lugar, mostramos que pow(x,3,P) no mapeará x a 1 o P-1 siempre que x ∈ [2,P-2] para comenzar. Finalmente, mostramos que pow(x,3,P) tiene una baja tasa de colisión cuando se trata como una función hash.

Generador de números aleatorios de Lehmer

Si bien la función produce_dag no necesita producir números aleatorios insesgados, una amenaza potencial es que seed**i % P solo tome un puñado de valores. Esto podría proporcionar una ventaja a los mineros que reconocen el patrón sobre los que no lo hacen.

Para evitar esto, se recurre a un resultado de la teoría de números. Un número primo seguro (opens in a new tab) se define como un número primo P tal que (P-1)/2 también es primo. El orden de un miembro x del grupo multiplicativo (opens in a new tab) ℤ/nℤ se define como el m mínimo tal que 

xᵐ mod P ≡ 1
Dadas estas definiciones, tenemos:

Observación 1. Sea x un miembro del grupo multiplicativo ℤ/Pℤ para un número primo seguro P. Si x mod P ≠ 1 mod P y x mod P ≠ P-1 mod P, entonces el orden de x es P-1 o (P-1)/2.

Prueba. Dado que P es un número primo seguro, entonces por el [Teorema de Lagrange][lagrange] tenemos que el orden de x es 1, 2, (P-1)/2 o P-1.

El orden de x no puede ser 1, ya que por el Pequeño Teorema de Fermat tenemos:

xP-1 mod P ≡ 1

Por lo tanto, x debe ser una identidad multiplicativa de ℤ/nℤ, que es única. Dado que asumimos que x ≠ 1 por suposición, esto no es posible.

El orden de x no puede ser 2 a menos que x = P-1, ya que esto violaría que P es primo.

De la proposición anterior, podemos reconocer que iterar (picker * init) % P tendrá una longitud de ciclo de al menos (P-1)/2. Esto se debe a que seleccionamos P para que sea un número primo seguro aproximadamente igual a una potencia superior de dos, y init está en el intervalo [2,2**256+1]. Dada la magnitud de P, nunca deberíamos esperar un ciclo de la exponenciación modular.

Cuando asignamos la primera celda en el DAG (la variable etiquetada init), calculamos pow(sha3(seed) + 2, 3, P). A primera vista, esto no garantiza que el resultado no sea ni 1 ni P-1. Sin embargo, dado que P-1 es un número primo seguro, tenemos la siguiente seguridad adicional, que es un corolario de la Observación 1:

Observación 2. Sea x un miembro del grupo multiplicativo ℤ/Pℤ para un número primo seguro P, y sea w un número natural. Si x mod P ≠ 1 mod P y x mod P ≠ P-1 mod P, así como w mod P ≠ P-1 mod P y w mod P ≠ 0 mod P, entonces xʷ mod P ≠ 1 mod P y xʷ mod P ≠ P-1 mod P

Exponenciación modular como función hash

Para ciertos valores de P y w, la función pow(x, w, P) puede tener muchas colisiones. Por ejemplo, pow(x,9,19) solo toma los valores {1,18}.

Dado que P es primo, entonces se puede elegir un w apropiado para una función hash de exponenciación modular utilizando el siguiente resultado:

Observación 3. Sea P un número primo; w y P-1 son primos relativos si y solo si para todo a y b en ℤ/Pℤ:

aʷ mod P ≡ bʷ mod P si y solo si a mod P ≡ b mod P

Por lo tanto, dado que P es primo y w es primo relativo a P-1, tenemos que |{pow(x, w, P) : x ∈ ℤ}| = P, lo que implica que la función hash tiene la tasa de colisión mínima posible.

En el caso especial de que P sea un número primo seguro como hemos seleccionado, entonces P-1 solo tiene los factores 1, 2, (P-1)/2 y P-1. Dado que P > 7, sabemos que 3 es primo relativo a P-1, por lo tanto, w=3 satisface la proposición anterior.

Algoritmo de evaluación basado en caché más eficiente