Pular para o conteúdo principal
Change page

Dagger-Hashimoto

Editar página (opens in a new tab)

Dagger-Hashimoto foi a implementação de pesquisa e especificação original para o algoritmo de mineração do Ethereum. Dagger-Hashimoto foi substituído pelo Ethash. A mineração foi totalmente desativada no The Merge em 15 de setembro de 2022. Desde então, o Ethereum tem sido protegido usando um mecanismo de Prova de Participação (PoS) em vez disso. Esta página é de interesse histórico - as informações aqui não são mais relevantes para o Ethereum pós-Merge.

Pré-requisitos

Para entender melhor esta página, recomendamos que você leia primeiro sobre o consenso de Prova de Trabalho (PoW), mineração e algoritmos de mineração.

Dagger-Hashimoto

O Dagger-Hashimoto visa 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 por cliente leve: um bloco deve ser verificável de forma eficiente por um cliente leve.

Com uma modificação adicional, também especificamos como cumprir um terceiro objetivo, se desejado, mas ao custo de 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 frequentemente usados, mas queremos minimizar isso).

Geração do DAG

O código para o algoritmo será definido em Python abaixo. Primeiro, fornecemos encode_int para organizar inteiros sem sinal de precisão especificada em strings. Seu inverso também é fornecido:

Em seguida, assumimos que sha3 é uma função que recebe um inteiro e gera um inteiro, e dbl_sha3 é uma função double-sha3; se for converter 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 número primo escolhido de forma que log₂(P) seja um pouco menor que 512, o que corresponde aos 512 bits que temos usado para representar nossos números. Observe que apenas a segunda metade do DAG realmente precisa ser armazenada, portanto, o requisito de RAM de fato começa em 1 GB e cresce 441 MB por ano.

Construção do grafo Dagger

A primitiva de construção do grafo 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 é calculada 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, em última análise, gerar o valor do grafo no índice i. A lógica por trás desse 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 a geração de hash do resultado ainda mais.

Este algoritmo depende de vários resultados da teoria dos números. Veja o apêndice abaixo para uma discussão.

Avaliação de cliente leve

A construção do grafo acima pretende permitir que cada nó no grafo seja reconstruído calculando uma subárvore de apenas um pequeno número de nós e exigindo apenas uma pequena quantidade de memória auxiliar. Observe que com k=1, a subárvore é apenas uma cadeia de valores que vai até o primeiro elemento no 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 para todo o DAG e substitui a pesquisa de nó anterior 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é-calcule os primeiros milhares de valores do DAG e os mantenha 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, um buffer duplo (opens in a new tab) de 2 DAGs produzidos pela fórmula acima é usado. A ideia é que os DAGs sejam produzidos a cada número epochtime de blocos de acordo com os parâmetros acima. Em vez de o cliente usar o último DAG produzido, ele usa o anterior. O benefício disso é que permite que os DAGs sejam substituídos ao longo do tempo sem precisar incorporar uma etapa em que os mineradores devam recalcular repentinamente todos os dados. Caso contrário, há o potencial de uma desaceleração temporária abrupta no processamento da cadeia em intervalos regulares e um aumento dramático da centralização. Assim, há riscos de ataque de 51% naqueles poucos minutos antes que todos os dados sejam recalculados.

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

Hashimoto

A ideia por trás do Hashimoto original é usar a blockchain como um conjunto de dados, realizando uma computação que seleciona N índices da blockchain, reúne as transações nesses índices, realiza um XOR desses dados e retorna o hash do resultado. O algoritmo original de Thaddeus Dryja, traduzido para Python por 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, embora o Hashimoto seja considerado difícil para a RAM (RAM hard), ele depende de aritmética de 256 bits, o que tem uma sobrecarga computacional considerável. No entanto, o Dagger-Hashimoto usa apenas os 64 bits menos significativos ao indexar seu conjunto de dados para resolver esse 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)

O uso de double SHA3 permite uma forma de pré-verificação quase instantânea e sem dados, verificando apenas se um valor intermediário correto foi fornecido. Esta camada externa de Prova de Trabalho é altamente amigável a ASIC e bastante fraca, mas existe para tornar os ataques DDoS ainda mais difíceis, já que essa pequena quantidade de trabalho deve ser feita para produzir um bloco que não será rejeitado imediatamente. Aqui está a versão para 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 juntar tudo 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 para 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, observe que o Dagger-Hashimoto impõe requisitos adicionais ao cabeçalho do bloco:

  • Para que a verificação de duas camadas funcione, um cabeçalho do bloco deve ter tanto o nonce quanto o valor intermediário pré-sha3
  • Em algum lugar, um cabeçalho do bloco deve armazenar o sha3 do conjunto de sementes atual

Leitura adicional

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

Apêndice

Como observado acima, o RNG (Gerador de Números Aleatórios) usado para a geração do DAG depende de alguns resultados da teoria dos números. Primeiro, fornecemos a garantia de que o RNG de Lehmer, que é a base para a variável picker, tem um período amplo. Em segundo lugar, 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 hash.

Gerador de números aleatórios de Lehmer

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

Para evitar isso, recorre-se a um resultado da teoria dos números. Um Primo Seguro (opens in a new tab) é definido como um número 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, pois 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 que P é 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 superior de dois, 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), calculamos 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) assume apenas os valores {1,18}.

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

Observação 3. Seja P um número primo; w e P-1 são primos entre si se e somente se para todos 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 entre si em relação a P-1, temos que |{pow(x, w, P) : x ∈ ℤ}| = P, implicando que a função de hash tem a taxa de colisão mínima possível.

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

Algoritmo de avaliação baseado em cache mais eficiente

Ú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