Pular para o conteúdo principal
Change page

Dagger-Hashimoto

Última atualização da página: 3 de abril de 2026

MCreimerM (opens in a new tab)
rafarochar (opens in a new tab)
henderson.mateus1h (opens in a new tab)
+5

Dagger-Hashimoto foi a implementação original de pesquisa e especificação para o algoritmo de mineração do Ethereum. O Dagger-Hashimoto foi substituído pelo Ethash. A mineração foi completamente desligada em A Fusão em 15 de setembro de 2022. Desde então, o Ethereum tem sido protegido usando um mecanismo de prova de participação. Esta página é para fins históricos. As informações aqui não são mais relevantes para o Ethereum posterior à Fusão.

Pré-requisitos

Para entender melhor esta página, recomendamos que você leia primeiro sobre consenso de prova de trabalho, mineração e algoritmos de mineração.

Dagger-Hashimoto

Dagger-Hashimoto pretende satisfazer dois objetivos:

  1. Resistência a ASIC: o benefício de criar hardware especializado para o algoritmo deve ser o menor possível
  2. Verificabilidade de cliente leve: um bloco deve ser eficientemente verificável por um cliente leve.

Com uma modificação adicional, também especificamos como atingir um terceiro objetivo se desejado, mas à custa de uma complexidade adicional:

Armazenamento completo da cadeia: a mineração deve exigir o armazenamento do estado completo da blockchain (devido à estrutura irregular da trie de estado do Ethereum, prevemos que alguma poda será possível, particularmente de alguns contratos usados com frequência, mas queremos minimizar isso).

Geração de DAG

O código do algoritmo será definido em Python abaixo. Primeiro, apresentamos o encode_int para o empacotamento (marshaling) de inteiros sem sinal de precisão especificada em strings. Sua inversa também é dada:

Em seguida, assumimos que sha3 é uma função que recebe um inteiro e retorna um inteiro, e dbl_sha3 é uma função double-sha3; se estiver convertendo este código de referência em uma implementação, use:

Parâmetros

Os parâmetros usados para o algoritmo são:

P neste caso é um primo escolhido tal que log₂(P) é apenas um pouco menor que 512, o que corresponde aos 512 bits que temos usado para representar nossos números. Observe que apenas a última metade do DAG precisa realmente ser armazenado, assim o requisito de RAM de-facto começa em 1 GB e cresce 441 MB por ano.

Construção do grafo Dagger

A construção primitiva de gráfico dagger é definida da seguinte forma:

Essencialmente, ele inicia um grafo como um único nó, sha3(seed), e a partir daí começa a adicionar sequencialmente outros nós com base em nós anteriores aleatórios. Quando um novo nó é criado, uma potência modular da semente é computada para selecionar aleatoriamente alguns índices menores que i (usando x % i acima), e os valores dos nós nesses índices são usados em um cálculo para gerar um novo valor para x, que é então alimentado em uma pequena função de prova de trabalho (baseada em XOR) para finalmente gerar o valor do grafo no índice i. A lógica por trás deste design específico é forçar o acesso sequencial do DAG; o próximo valor do DAG que será acessado não pode ser determinado até que o valor atual seja conhecido. Finalmente, a exponenciação modular faz o hash do resultado ainda mais.

Este algoritmo depende de vários resultados da teoria numérica. Veja o apêndice abaixo para uma discussão.

Avaliação do cliente leve

A construção do gráfico acima pretende permitir que cada nó no gráfico seja reconstruído computando uma subárvore com apenas um pequeno número de nós e exigindo uma pequena quantidade de memória auxiliar. Note que com k=1, a subárvore é apenas uma cadeia de valores que vai subindo até o primeiro elemento do DAG.

A função de computação do cliente leve para o DAG funciona da seguinte forma:

Essencialmente, é simplesmente uma reescrita do algoritmo acima que remove o loop de computação dos valores de todo o DAG e substitui a pesquisa anterior de nó por uma chamada recursiva ou uma pesquisa de cache. Observe que para k=1 o cache é desnecessário, embora uma otimização adicional na verdade pré-compute os primeiros milhares de valores do DAG e mantenha isso como um cache estático para computações; veja o apêndice para uma implementação de código disso.

Buffer duplo de DAGs

Em um cliente completo, é usado um buffer duplo (opens in a new tab) de 2 DAGs produzidos pela fórmula acima. A ideia é que os DAGs sejam produzidos a cada epochtime número de blocos, de acordo com os parâmetros acima. Em vez do cliente usar o último DAG produzido, ele usa o anterior. A vantagem disto é permitir que os DAG sejam substituídos com o passar do tempo, sem necessidade de incorporar um passo em que os mineradores devem, de repente, recriar todos os dados. Caso contrário, existe o potencial para um abrandamento abrupto temporário do processamento da cadeia a intervalos regulares e um aumento dramático da centralização. Assim, existe o risco de ataques de 51% dentro desses poucos minutos antes de todos os dados serem recomputados.

O algoritmo usado para gerar o conjunto de DAGs usados para computar o trabalho de um bloco é o seguinte:

Hashimoto

A ideia por trás do Hashimoto original é usar a blockchain como um conjunto de dados, executando um cálculo que seleciona N índices da blockchain, reúne as transações nesses índices, executa um XOR desses dados e retorna o hash do resultado. O algoritmo original de Thaddeus Dryja, convertido para Python para consistência, é o seguinte:

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)

Infelizmente, enquanto Hashimoto é considerado de uso intenso de RAM, ele depende da aritmética de 256 bits, o que tem uma sobrecarga computacional considerável. No entanto, Dagger-Hashimoto usa apenas os 64 bits menos significativos ao indexar seu conjunto de dados para resolver esta questão.

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)

O uso duplo do SHA3 permite uma forma de zero dados, pré-verificação quase instantânea, verificando apenas se foi fornecido um valor intermediário correto. Esta camada exterior de prova de trabalho é altamente favorável a ASIC e razoavelmente fraca, mas existe para tornar a DDoS ainda mais difícil, uma vez que essa pequena quantidade de trabalho tem de ser feita para produzir um bloco que não seja imediatamente rejeitado. Aqui está a versão de cliente leve:

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)

Mineração e verificação

Agora, vamos colocar tudo junto no algoritmo de mineração:

Aqui está o algoritmo de verificação:

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

Verificação amigável do cliente leve:

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

Além disso, note que Dagger-Hashimoto impõe requisitos adicionais no cabeçalho do bloco:

  • Para que a verificação em duas camadas funcione, um cabeçalho de bloco deve ter ambos o nonce e o valor do meio pre-sha3
  • Um cabeçalho de bloco deve armazenar o sha3 do seedset atual em algum lugar

Leitura adicional

Conhece um recurso da comunidade que o ajudou? Edite esta página e adicione-a!

Apêndice

Como mencionado acima, o RNG usado para geração de DAGs depende de alguns resultados da teoria de números. Primeiro, fornecemos a garantia de que o Lehmer RNG, que é a base para a variável picker, tem um período amplo. Segundo, mostramos que pow(x,3,P) não mapeará x para 1 ou P-1, desde que x ∈ [2,P-2] para começar. Finalmente, mostramos que pow(x,3,P) tem uma baixa taxa de colisão quando tratado como uma função de hashing.

Gerador de números aleatórios de Lehmer

Embora a função produce_dag não precise produzir números aleatórios imparciais, uma ameaça em potencial é que seed**i % P assuma apenas um punhado de valores. Isto poderia proporcionar uma vantagem aos mineradores reconhecendo o padrão em relação aos que não o fazem.

Para evitar isso, apela-se a um resultado da teoria dos números. Um Primo Seguro (opens in a new tab) é definido como um primo P tal que (P-1)/2 também é primo. A ordem de um membro x do grupo multiplicativo (opens in a new tab) ℤ/nℤ é definida como o m mínimo tal que 

xᵐ mod P ≡ 1
Dadas essas definições, temos:

Observação 1. Seja x um membro do grupo multiplicativo ℤ/Pℤ para um primo seguro P. Se x mod P ≠ 1 mod P e x mod P ≠ P-1 mod P, então a ordem de x é P-1 ou (P-1)/2.

Prova. Como P é um primo seguro, então, pelo [Teorema de Lagrange][lagrange], temos que a ordem de x é 1, 2, (P-1)/2 ou P-1.

A ordem de x não pode ser 1, uma vez que, pelo Pequeno Teorema de Fermat, temos:

xP-1 mod P ≡ 1

Portanto, x deve ser uma identidade multiplicativa de ℤ/nℤ, que é única. Como assumimos que x ≠ 1 por suposição, isso não é possível.

A ordem de x não pode ser 2 a menos que x = P-1, pois isso violaria o fato de P ser primo.

A partir da proposição acima, podemos reconhecer que a iteração de (picker * init) % P terá um comprimento de ciclo de pelo menos (P-1)/2. Isso ocorre porque selecionamos P para ser um primo seguro aproximadamente igual a uma potência de dois mais alta, e init está no intervalo [2,2**256+1]. Dada a magnitude de P, nunca devemos esperar um ciclo da exponenciação modular.

Quando estamos atribuindo a primeira célula no DAG (a variável rotulada init), nós computamos pow(sha3(seed) + 2, 3, P). À primeira vista, isso não garante que o resultado não seja nem 1 nem P-1. No entanto, como P-1 é um primo seguro, temos a seguinte garantia adicional, que é um corolário da Observação 1:

Observação 2. Seja x um membro do grupo multiplicativo ℤ/Pℤ para um primo seguro P, e seja w um número natural. Se x mod P ≠ 1 mod P e x mod P ≠ P-1 mod P, bem como w mod P ≠ P-1 mod P e w mod P ≠ 0 mod P, então xʷ mod P ≠ 1 mod P e xʷ mod P ≠ P-1 mod P

Exponenciação modular como uma função de hash

Para certos valores de P e w, a função pow(x, w, P) pode ter muitas colisões. Por exemplo, pow(x,9,19) só assume os valores {1,18}.

Dado que P é primo, um w apropriado para uma função de hashing de exponenciação modular pode ser escolhido usando o seguinte resultado:

Observação 3. Seja P um primo; w e P-1 são primos entre si se, e somente se, para todo a e b em ℤ/Pℤ:

aʷ mod P ≡ bʷ mod P se e somente se a mod P ≡ b mod P

Assim, dado que P é primo e w é primo em relação a P-1, temos que |{pow(x, w, P) : x ∈ ℤ}| = P, o que implica que a função de hashing tem a taxa de colisão mínima possível.

No caso especial em que P é um primo seguro, como o que selecionamos, P-1 tem apenas os fatores 1, 2, (P-1)/2 e P-1. Como P > 7, sabemos que 3 é primo em relação a P-1, portanto w=3 satisfaz a proposição acima.

Algoritmo de avaliação mais eficiente baseado em cache

Este artigo foi útil?