---
title: Dagger-Hashimoto
description: "Подробный обзор алгоритма Dagger-Hashimoto."
lang: ru
---
Dagger-Hashimoto был первоначальной исследовательской реализацией и спецификацией алгоритма майнинга Эфириума. На смену Dagger-Hashimoto пришел [Этхэш](/developers/docs/consensus-mechanisms/pow/mining/mining-algorithms/#ethash). Майнинг был полностью отключен во время [Слияния](/roadmap/merge/) 15 сентября 2022 года. С тех пор безопасность Эфириума обеспечивается с помощью механизма [доказательства доли владения (PoS)](/developers/docs/consensus-mechanisms/pos). Эта страница представляет исторический интерес — представленная здесь информация больше не актуальна для Эфириума после Слияния.
## Предварительные требования {#prerequisites}
Для лучшего понимания этой страницы мы рекомендуем сначала прочитать про [консенсус доказательства выполнения работы (PoW)](/developers/docs/consensus-mechanisms/pow), [майнинг](/developers/docs/consensus-mechanisms/pow/mining) и [алгоритмы майнинга](/developers/docs/consensus-mechanisms/pow/mining/mining-algorithms).
## Dagger-Hashimoto {#dagger-hashimoto}
Dagger-Hashimoto стремится достичь двух целей:
1. **Устойчивость к ASIC**: выгода от создания специализированного оборудования для алгоритма должна быть как можно меньше.
2. **Проверяемость легким клиентом**: блок должен эффективно проверяться легким клиентом.
С помощью дополнительной модификации мы также определяем, как при желании достичь третьей цели, но ценой дополнительной сложности:
**Хранение полной цепи**: майнинг должен требовать хранения полного состояния блокчейна (из-за нерегулярной структуры дерева состояний Эфириума мы предполагаем, что будет возможно некоторое усечение, в частности, некоторых часто используемых контрактов, но мы хотим свести это к минимуму).
## Генерация DAG {#dag-generation}
Код алгоритма будет определен на Python ниже. Сначала мы приводим `encode_int` для преобразования беззнаковых целых чисел заданной точности в строки. Также приводится обратная функция:
```python
NUM_BITS = 512
def encode_int(x):
"Encode an integer x as a string of 64 characters using a big-endian scheme"
o = ''
for _ in range(NUM_BITS / 8):
o = chr(x % 256) + o
x //= 256
return o
def decode_int(s):
"Unencode an integer x from a string using a big-endian scheme"
x = 0
for c in s:
x *= 256
x += ord(c)
return x
```
Далее мы предполагаем, что `sha3` — это функция, которая принимает целое число и возвращает целое число, а `dbl_sha3` — это функция двойного SHA-3; при преобразовании этого эталонного кода в реализацию используйте:
```python
from pyethereum import utils
def sha3(x):
if isinstance(x, (int, long)):
x = encode_int(x)
return decode_int(utils.sha3(x))
def dbl_sha3(x):
if isinstance(x, (int, long)):
x = encode_int(x)
return decode_int(utils.sha3(utils.sha3(x)))
```
### Параметры {#parameters}
Параметры, используемые для алгоритма:
```python
SAFE_PRIME_512 = 2**512 - 38117 # Наибольшее безопасное простое число, меньшее 2**512
params = {
"n": 4000055296 * 8 // NUM_BITS, # Размер набора данных (4 гигабайта); ДОЛЖЕН БЫТЬ КРАТЕН 65536
"n_inc": 65536, # Приращение значения n за период; ДОЛЖНО БЫТЬ КРАТНО 65536
# при epochtime=20000 дает рост на 882 МБ в год
"cache_size": 2500, # Размер кеша легкого клиента (может быть выбран легким
# клиентом; не является частью спецификации алгоритма)
"diff": 2**14, # Сложность (корректируется во время оценки блока)
"epochtime": 100000, # Длина эпохи в блоках (как часто обновляется набор данных)
"k": 1, # Количество родителей узла
"w": w, # Используется для хеширования с модульным возведением в степень
"accesses": 200, # Количество обращений к набору данных во время hashimoto
"P": SAFE_PRIME_512 # Безопасное простое число для хеширования и генерации случайных чисел
}
```
`P` в данном случае — это простое число, выбранное таким образом, чтобы `log₂(P)` было чуть меньше 512, что соответствует 512 битам, которые мы использовали для представления наших чисел. Обратите внимание, что фактически нужно хранить только вторую половину DAG, поэтому фактические требования к оперативной памяти начинаются с 1 ГБ и растут на 441 МБ в год.
### Построение графа Dagger {#dagger-graph-building}
Примитив построения графа Dagger определяется следующим образом:
```python
def produce_dag(params, seed, length):
P = params["P"]
picker = init = pow(sha3(seed), params["w"], P)
o = [init]
for i in range(1, length):
x = picker = (picker * init) % P
for _ in range(params["k"]):
x ^= o[x % i]
o.append(pow(x, params["w"], P))
return o
```
По сути, он начинает граф с одного узла, `sha3(seed)`, и оттуда начинает последовательно добавлять другие узлы на основе случайных предыдущих узлов. При создании нового узла вычисляется модульная степень сида для случайного выбора некоторых индексов меньше `i` (с использованием `x % i` выше), и значения узлов по этим индексам используются в вычислении для генерации нового значения для `x`, которое затем подается в небольшую функцию доказательства выполнения работы (на основе XOR) для окончательной генерации значения графа по индексу `i`. Обоснование этого конкретного дизайна заключается в принудительном последовательном доступе к DAG; следующее значение DAG, к которому будет осуществлен доступ, не может быть определено до тех пор, пока не будет известно текущее значение. Наконец, модульное возведение в степень дополнительно хеширует результат.
Этот алгоритм опирается на несколько результатов из теории чисел. См. обсуждение в приложении ниже.
## Оценка легким клиентом {#light-client-evaluation}
Вышеупомянутое построение графа предназначено для того, чтобы позволить каждому узлу в графе быть реконструированным путем вычисления поддерева, состоящего лишь из небольшого числа узлов, и требующего лишь небольшого объема вспомогательной памяти. Обратите внимание, что при k=1 поддерево представляет собой только цепь значений, идущую до первого элемента в DAG.
Функция вычисления легкого клиента для DAG работает следующим образом:
```python
def quick_calc(params, seed, p):
w, P = params["w"], params["P"]
cache = {}
def quick_calc_cached(p):
if p in cache:
pass
elif p == 0:
cache[p] = pow(sha3(seed), w, P)
else:
x = pow(sha3(seed), (p + 1) * w, P)
for _ in range(params["k"]):
x ^= quick_calc_cached(x % p)
cache[p] = pow(x, w, P)
return cache[p]
return quick_calc_cached(p)
```
По сути, это просто переписывание вышеупомянутого алгоритма, которое удаляет цикл вычисления значений для всего DAG и заменяет более ранний поиск узла рекурсивным вызовом или поиском в кэше. Обратите внимание, что для `k=1` кэш не нужен, хотя дальнейшая оптимизация фактически предварительно вычисляет первые несколько тысяч значений DAG и сохраняет их в качестве статического кэша для вычислений; см. приложение для реализации этого в коде.
## Двойной буфер DAG {#double-buffer}
В полном клиенте используется [_двойной буфер_](https://wikipedia.org/wiki/Multiple_buffering) из 2 DAG, созданных по приведенной выше формуле. Идея заключается в том, что DAG создаются каждые `epochtime` блоков в соответствии с параметрами выше. Вместо того чтобы клиент использовал последний созданный DAG, он использует предыдущий. Преимущество этого заключается в том, что это позволяет заменять DAG с течением времени без необходимости включать шаг, на котором майнеры должны внезапно пересчитывать все данные. В противном случае существует вероятность резкого временного замедления обработки цепи через регулярные промежутки времени и резкого увеличения централизации. Таким образом, возникают риски атаки 51% в течение тех нескольких минут, пока все данные не будут пересчитаны.
Алгоритм, используемый для генерации набора DAG, применяемых для вычисления работы для блока, выглядит следующим образом:
```python
def get_prevhash(n):
from pyethereum.blocks import GENESIS_PREVHASH
from pyethereum import chain_manager
if n <= 0:
return hash_to_int(GENESIS_PREVHASH)
else:
prevhash = chain_manager.index.get_block_by_number(n - 1)
return decode_int(prevhash)
def get_seedset(params, block):
seedset = {}
seedset["back_number"] = block.number - (block.number % params["epochtime"])
seedset["back_hash"] = get_prevhash(seedset["back_number"])
seedset["front_number"] = max(seedset["back_number"] - params["epochtime"], 0)
seedset["front_hash"] = get_prevhash(seedset["front_number"])
return seedset
def get_dagsize(params, block):
return params["n"] + (block.number // params["epochtime"]) * params["n_inc"]
def get_daggerset(params, block):
dagsz = get_dagsize(params, block)
seedset = get_seedset(params, block)
if seedset["front_hash"] <= 0:
# Задний буфер невозможен, просто создайте передний буфер
return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
"block_number": 0}}
else:
return {"front": {"dag": produce_dag(params, seedset["front_hash"], dagsz),
"block_number": seedset["front_number"]},
"back": {"dag": produce_dag(params, seedset["back_hash"], dagsz),
"block_number": seedset["back_number"]}}
```
## Hashimoto {#hashimoto}
Идея оригинального алгоритма Hashimoto заключается в использовании блокчейна в качестве набора данных, выполнении вычисления, которое выбирает N индексов из блокчейна, собирает транзакции по этим индексам, выполняет XOR этих данных и возвращает хеш результата. Оригинальный алгоритм Таддеуса Драйи (Thaddeus Dryja), переведенный на Python для единообразия, выглядит следующим образом:
```python
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)
```
К сожалению, хотя Hashimoto считается требовательным к оперативной памяти (RAM hard), он опирается на 256-битную арифметику, которая имеет значительные вычислительные накладные расходы. Однако Dagger-Hashimoto использует только 64 младших бита при индексировании своего набора данных для решения этой проблемы.
```python
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)
```
Использование двойного SHA-3 позволяет осуществлять форму почти мгновенной предварительной проверки с нулевыми данными, проверяя только то, что было предоставлено правильное промежуточное значение. Этот внешний уровень доказательства выполнения работы очень дружелюбен к ASIC и довольно слаб, но существует для того, чтобы сделать DDoS-атаки еще более сложными, поскольку этот небольшой объем работы должен быть выполнен для создания блока, который не будет немедленно отклонен. Вот версия для легкого клиента:
```python
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)
```
## Майнинг и проверка {#mining-and-verifying}
Теперь давайте соберем все это вместе в алгоритм майнинга:
```python
def mine(daggerset, params, block):
from random import randint
nonce = randint(0, 2**64)
while 1:
result = hashimoto(daggerset, get_dagsize(params, block),
params, decode_int(block.prevhash), nonce)
if result * params["diff"] < 2**256:
break
nonce += 1
if nonce >= 2**64:
nonce = 0
return nonce
```
Вот алгоритм проверки:
```python
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
```
Проверка, дружественная к легкому клиенту:
```python
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
```
Также обратите внимание, что Dagger-Hashimoto налагает дополнительные требования на заголовок блока:
- Для работы двухуровневой проверки заголовок блока должен содержать как нонс, так и среднее значение до применения SHA-3.
- Где-то заголовок блока должен хранить SHA-3 текущего набора сидов.
## Дополнительная литература {#further-reading}
_Знаете ресурс сообщества, который вам помог? Отредактируйте эту страницу и добавьте его!_
## Приложение {#appendix}
Как отмечалось выше, генератор случайных чисел (ГСЧ), используемый для генерации DAG, опирается на некоторые результаты из теории чисел. Во-первых, мы предоставляем гарантию того, что ГСЧ Лемера, который является основой для переменной `picker`, имеет широкий период. Во-вторых, мы показываем, что `pow(x,3,P)` не будет отображать `x` в `1` или `P-1` при условии, что для начала задано `x ∈ [2,P-2]`. Наконец, мы показываем, что `pow(x,3,P)` имеет низкий уровень коллизий при использовании в качестве хеш-функции.
### Генератор случайных чисел Лемера {#lehmer-random-number}
Хотя функция `produce_dag` не обязана генерировать несмещенные случайные числа, потенциальная угроза заключается в том, что `seed**i % P` принимает лишь небольшое количество значений. Это могло бы дать преимущество майнерам, распознающим закономерность, перед теми, кто этого не делает.
Чтобы избежать этого, мы обращаемся к результату из теории чисел. [_Безопасное простое число_](https://en.wikipedia.org/wiki/Safe_prime) определяется как простое число `P` такое, что `(P-1)/2` также является простым. _Порядок_ элемента `x` [мультипликативной группы](https://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n) `ℤ/nℤ` определяется как минимальное `m` такое, что xᵐ mod P ≡ 1
Учитывая эти определения, мы имеем:
> Наблюдение 1. Пусть `x` является элементом мультипликативной группы `ℤ/Pℤ` для безопасного простого числа `P`. Если `x mod P ≠ 1 mod P` и `x mod P ≠ P-1 mod P`, то порядок `x` равен либо `P-1`, либо `(P-1)/2`.
_Доказательство_. Поскольку `P` является безопасным простым числом, то по [теореме Лагранжа][lagrange] мы имеем, что порядок `x` равен либо `1`, `2`, `(P-1)/2`, либо `P-1`.
Порядок `x` не может быть равен `1`, так как по малой теореме Ферма мы имеем:
xP-1 mod P ≡ 1
Следовательно, `x` должно быть мультипликативной единицей `ℤ/nℤ`, которая уникальна. Поскольку мы предположили, что `x ≠ 1` по условию, это невозможно.
Порядок `x` не может быть равен `2`, если только не `x = P-1`, так как это нарушило бы условие, что `P` является простым числом.
Из приведенного выше утверждения мы можем понять, что итерация `(picker * init) % P` будет иметь длину цикла не менее `(P-1)/2`. Это связано с тем, что мы выбрали `P` как безопасное простое число, приблизительно равное более высокой степени двойки, а `init` находится в интервале `[2,2**256+1]`. Учитывая величину `P`, мы никогда не должны ожидать цикла от модульного возведения в степень.
Когда мы назначаем первую ячейку в DAG (переменная с меткой `init`), мы вычисляем `pow(sha3(seed) + 2, 3, P)`. На первый взгляд, это не гарантирует, что результат не равен ни `1`, ни `P-1`. Однако, поскольку `P-1` является безопасным простым числом, мы имеем следующую дополнительную гарантию, которая является следствием Наблюдения 1:
> Наблюдение 2. Пусть `x` является элементом мультипликативной группы `ℤ/Pℤ` для безопасного простого числа `P`, и пусть `w` — натуральное число. Если `x mod P ≠ 1 mod P` и `x mod P ≠ P-1 mod P`, а также `w mod P ≠ P-1 mod P` и `w mod P ≠ 0 mod P`, то `xʷ mod P ≠ 1 mod P` и `xʷ mod P ≠ P-1 mod P`
### Модульное возведение в степень как хеш-функция {#modular-exponentiation}
Для определенных значений `P` и `w` функция `pow(x, w, P)` может иметь много коллизий. Например, `pow(x,9,19)` принимает только значения `{1,18}`.
Учитывая, что `P` является простым числом, подходящее `w` для хеш-функции модульного возведения в степень можно выбрать, используя следующий результат:
> Наблюдение 3. Пусть `P` — простое число; `w` и `P-1` взаимно просты тогда и только тогда, когда для всех `a` и `b` в `ℤ/Pℤ`:`aʷ mod P ≡ bʷ mod P` тогда и только тогда, когда `a mod P ≡ b mod P`
Таким образом, учитывая, что `P` является простым числом, а `w` взаимно просто с `P-1`, мы имеем, что `|{pow(x, w, P) : x ∈ ℤ}| = P`, что означает, что хеш-функция имеет минимально возможный уровень коллизий.
В частном случае, когда `P` является безопасным простым числом, как мы выбрали, то `P-1` имеет только множители 1, 2, `(P-1)/2` и `P-1`. Поскольку `P` > 7, мы знаем, что 3 взаимно просто с `P-1`, следовательно, `w=3` удовлетворяет приведенному выше утверждению.
## Более эффективный алгоритм оценки на основе кэша {#cache-based-evaluation}
```python
def quick_calc(params, seed, p):
cache = produce_dag(params, seed, params["cache_size"])
return quick_calc_cached(cache, params, p)
def quick_calc_cached(cache, params, p):
P = params["P"]
if p < len(cache):
return cache[p]
else:
x = pow(cache[0], p + 1, P)
for _ in range(params["k"]):
x ^= quick_calc_cached(cache, params, x % p)
return pow(x, params["w"], P)
def quick_hashimoto(seed, dagsize, params, header, nonce):
cache = produce_dag(params, seed, params["cache_size"])
return quick_hashimoto_cached(cache, dagsize, params, header, nonce)
def quick_hashimoto_cached(cache, dagsize, params, header, nonce):
m = dagsize // 2
mask = 2**64 - 1
mix = sha3(encode_int(nonce) + header)
for _ in range(params["accesses"]):
mix ^= quick_calc_cached(cache, params, m + (mix & mask) % m)
return dbl_sha3(mix)
```