Pular para o conteúdo principal
Change page

Dagger-Hashimoto

Última edição: @MCreimer(opens in a new tab), 23 de fevereiro de 2024

Dagger-Hashimoto foi a implementação original de pesquisa e especificação para o algoritmo de mineração do Ethereum. Dagger-Hashimoto foi substituído por Ethash. A mineração foi completamente desligada na Fusão no dia 15 de setembro de 2022. Desde então, o Ethereum foi protegido usando um mecanismo 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 melhor entender esta página, recomendamos que você leia primeiro o 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. Cliente leve verificável: um bloco deve ser verificável eficientemente 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 deveria exigir o armazenamento do estado completo da blockchain (devido à estrutura irregular da árvore de estado Ethereum, esperamos que haja um pouco de perda, especialmente de alguns contratos muitas vezes usados, mas queremos minimizar isso).

Geração do DAG

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

1NUM_BITS = 512
2
3def encode_int(x):
4 "Encode an integer x as a string of 64 characters using a big-endian scheme"
5 o = ''
6 for _ in range(NUM_BITS / 8):
7 o = chr(x % 256) + o
8 x //= 256
9 return o
10
11def decode_int(s):
12 "Unencode an integer x from a string using a big-endian scheme"
13 x = 0
14 for c in s:
15 x *= 256
16 x += ord(c)
17 return x
Exibir tudo
Copiar

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 converter este código de referência em uma implementação de uso:

1from pyethereum import utils
2def sha3(x):
3 if isinstance(x, (int, long)):
4 x = encode_int(x)
5 return decode_int(utils.sha3(x))
6
7def dbl_sha3(x):
8 if isinstance(x, (int, long)):
9 x = encode_int(x)
10 return decode_int(utils.sha3(utils.sha3(x)))
Exibir tudo
Copiar

Parâmetros

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

1SAFE_PRIME_512 = 2**512 - 38117 # Largest Safe Prime less than 2**512
2
3params = {
4 "n": 4000055296 * 8 // NUM_BITS, # Size of the dataset (4 Gigabytes); MUST BE MULTIPLE OF 65536
5 "n_inc": 65536, # Increment in value of n per period; MUST BE MULTIPLE OF 65536
6 # with epochtime=20000 gives 882 MB growth per year
7 "cache_size": 2500, # Size of the light client's cache (can be chosen by light
8 # client; not part of the algo spec)
9 "diff": 2**14, # Difficulty (adjusted during block evaluation)
10 "epochtime": 100000, # Length of an epoch in blocks (how often the dataset is updated)
11 "k": 1, # Number of parents of a node
12 "w": w, # Used for modular exponentiation hashing
13 "accesses": 200, # Number of dataset accesses during hashimoto
14 "P": SAFE_PRIME_512 # Safe Prime for hashing and random number generation
15}
Exibir tudo
Copiar

P neste caso é uma primeira escolha tal que log(P) é apenas ligeiramente menor que 512, 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 de gráfico Dagger

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

1def produce_dag(params, seed, length):
2 P = params["P"]
3 picker = init = pow(sha3(seed), params["w"], P)
4 o = [init]
5 for i in range(1, length):
6 x = picker = (picker * init) % P
7 for _ in range(params["k"]):
8 x ^= o[x % i]
9 o.append(pow(x, params["w"], P))
10 return o
Exibir tudo
Copiar

Essencialmente, ele começa um gráfico como um único nó, sha3(seed), e de lá começa a adicionar sequencialmente outros nós com base em nós aleatórios anteriores. Quando um novo nó é criado, uma potência modular da semente é computada para aleatoriamente selecionar alguns índices menores que i (usando x % i acima), e os valores dos nós desses índices são usados em um cálculo para gerar um novo valor para x, que é então alimentada em uma pequena função de prova de trabalho (baseada em XOR) para finalmente gerar o valor do gráfico 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 de 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:

1def quick_calc(params, seed, p):
2 w, P = params["w"], params["P"]
3 cache = {}
4
5 def quick_calc_cached(p):
6 if p in cache:
7 pass
8 elif p == 0:
9 cache[p] = pow(sha3(seed), w, P)
10 else:
11 x = pow(sha3(seed), (p + 1) * w, P)
12 for _ in range(params["k"]):
13 x ^= quick_calc_cached(x % p)
14 cache[p] = pow(x, w, P)
15 return cache[p]
16
17 return quick_calc_cached(p)
Exibir tudo
Copiar

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 maior na verdade pré-calcula os primeiros poucos milhares de valores do DAG e o mantém como um cache estático para computações; ver 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 DAGs são 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:

1def get_prevhash(n):
2 from pyethereum.blocks import GENESIS_PREVHASH
3 from pyethereum import chain_manager
4 if num <= 0:
5 return hash_to_int(GENESIS_PREVHASH)
6 else:
7 prevhash = chain_manager.index.get_block_by_number(n - 1)
8 return decode_int(prevhash)
9
10def get_seedset(params, block):
11 seedset = {}
12 seedset["back_number"] = block.number - (block.number % params["epochtime"])
13 seedset["back_hash"] = get_prevhash(seedset["back_number"])
14 seedset["front_number"] = max(seedset["back_number"] - params["epochtime"], 0)
15 seedset["front_hash"] = get_prevhash(seedset["front_number"])
16 return seedset
17
18def get_dagsize(params, block):
19 return params["n"] + (block.number // params["epochtime"]) * params["n_inc"]
20
21def get_daggerset(params, block):
22 dagsz = get_dagsize(params, block)
23 seedset = get_seedset(params, block)
24 if seedset["front_hash"] <= 0:
25 # No back buffer is possible, just make front buffer
26 return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
27 "block_number": 0}}
28 else:
29 return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
30 "block_number": seedset["front_number"]},
31 "back": {"dag": produce_dag(params, seedset["back_hash"], dagsz),
32 "block_number": seedset["back_number"]}}
Exibir tudo
Copiar

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:

1def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):
2 hash_output_A = sha256(prev_hash + merkle_root + nonce)
3 txid_mix = 0
4 for i in range(64):
5 shifted_A = hash_output_A >> i
6 transaction = shifted_A % len(list_of_transactions)
7 txid_mix ^= list_of_transactions[transaction] << i
8 return txid_max ^ (nonce << 192)
Copiar

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.

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

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:

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

Mineração e verificação

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

1def mine(daggerset, params, block):
2 from random import randint
3 nonce = randint(0, 2**64)
4 while 1:
5 result = hashimoto(daggerset, get_dagsize(params, block),
6 params, decode_int(block.prevhash), nonce)
7 if result * params["diff"] < 2**256:
8 break
9 nonce += 1
10 if nonce >= 2**64:
11 nonce = 0
12 return nonce
Exibir tudo
Copiar

Aqui está o algoritmo de verificação:

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

Verificação amigável do cliente leve:

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

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 algum recurso da comunidade que o ajudou? Edite essa página e adicione!

Apêndice

Como mencionado acima, o RNG usado para geração de DAGs depende de alguns resultados da teoria de números. Primeiro, nós fornecemos garantias de que o Lehmer RNG, que é a base para a variável picker, tenha um longo período. Segundo, mostramos que pow(x,3,P) não vai correlacionar x para 1 ou P-1 fornecer 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 Lehmer

Enquanto a função produce_dag não precisa produzir números aleatórios sem viés, uma ameaça potencial é que seed**i % P só absorve 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 número primo seguro(opens in a new tab) é definido como sendo um P primo tal que (P-1)/2 também é primo. A ordem de um membro x do grupo multiplicativo(opens in a new tab) Z/nZ é definido como o mínimo de m tal que

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

Observação 1. Deixe x ser um membro do grupo multiplicador Z/PZ para um P primo seguro. 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. Já que 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, já que pelo Pequeno Teorema de Fermat, nós temos:

1xP-1 mod P ≡ 1

Daí x deve ser uma identidade multiplicadora de Z/nZ, que é única. Como partimos do princípio de 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, já que isso violaria o princípio de que P é primo.

A partir da proposta acima, podemos reconhecer que a iteração (picker * init) % P terá um ciclo de comprimento de pelo menos (P-1)/2. Isso acontece 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 como init), nós computamos pow (sha3(seed) + 2, 3, P). À primeira vista, isso não garante que o resultado não é 1 nem P-1. No entanto, como P-1 é um primo seguro, temos a seguinte garantia adicional, que é uma afirmação deduzida da Observação 1:

Observação 2. Deixe x ser um membro do grupo multiplicador Z/PZ para um P primo seguro, e deixe w ser um número natural. Se x mod P ≠ 1 mod P e x mod P ≠ P-1 mod P, assim 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 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) recebe apenas valores {1,18}.

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

Observação 3. Considere P um primo; w e P-1 são relativamente primos, se e somente se para todos a e b em Z/PZ:

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

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

No caso especial que P é um primo seguro como selecionamos, então P-1 só tem fatores 1, 2, (P-1)/2 e P-1. Como P > 7, sabemos que 3 é relativamente primo de P-1, daí w=3 satisfaz a proposta acima.

Algoritmo de avaliação baseado em cache mais eficiente

1def quick_calc(params, seed, p):
2 cache = produce_dag(params, seed, params["cache_size"])
3 return quick_calc_cached(cache, params, p)
4
5def quick_calc_cached(cache, params, p):
6 P = params["P"]
7 if p < len(cache):
8 return cache[p]
9 else:
10 x = pow(cache[0], p + 1, P)
11 for _ in range(params["k"]):
12 x ^= quick_calc_cached(cache, params, x % p)
13 return pow(x, params["w"], P)
14
15def quick_hashimoto(seed, dagsize, params, header, nonce):
16 cache = produce_dag(params, seed, params["cache_size"])
17 return quick_hashimoto_cached(cache, dagsize, params, header, nonce)
18
19def quick_hashimoto_cached(cache, dagsize, params, header, nonce):
20 m = dagsize // 2
21 mask = 2**64 - 1
22 mix = sha3(encode_int(nonce) + header)
23 for _ in range(params["accesses"]):
24 mix ^= quick_calc_cached(cache, params, m + (mix & mask) % m)
25 return dbl_sha3(mix)
Exibir tudo
Copiar

Este artigo foi útil?