Dagger-Hashimoto

Dagger-Hashimoto был изначальной исследовательской реализацией и спецификацией алгоритма майнинга Ethereum. Dagger-Hashimoto был заменен на Ethash. Майнинг был полностью отключен во время Слияния 15 сентября 2022 года. С тех пор безопасность Ethereum обеспечивается с помощью механизма доказательства доли владения. Эта страница представляет исторический интерес — информация на ней больше не актуальна для Ethereum после Слияния.

Предварительные условия

Чтобы лучше понять эту страницу, мы рекомендуем вам сначала ознакомиться с консенсусом на основе доказательства выполнения работы, майнингом и алгоритмами майнинга.

Dagger-Hashimoto нацелен на достижение двух целей:

Устойчивость к ASIC: преимущество от создания специализированного оборудования для этого алгоритма должно быть как можно меньшим
Верифицируемость легким клиентом: блок должен эффективно верифицироваться легким клиентом.

С дополнительной модификацией мы также указываем, как при желании достичь третьей цели, но за счет дополнительной сложности:

Полное хранение цепочки: майнинг должен требовать хранения полного состояния блокчейна (из-за нерегулярной структуры дерева состояний Ethereum мы предполагаем, что будет возможно некоторое усечение, в частности, некоторых часто используемых контрактов, но мы хотим свести это к минимуму).

Генерация DAG

Код алгоритма будет определен на Python ниже. Сначала приведем encode_int для маршалинга беззнаковых целых чисел указанной точности в строки. Также приведена обратная функция:

1NUM_BITS = 512
2
3def encode_int(x):
4    "Кодирует целое число x в виде строки из 64 символов с использованием схемы с прямым порядком байтов"
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    "Декодирует целое число x из строки с использованием схемы с прямым порядком байтов"
13    x = 0
14    for c in s:
15        x *= 256
16        x += ord(c)
17    return x
Показать все

Далее мы предполагаем, что sha3 — это функция, которая принимает и возвращает целое число, а dbl_sha3 — это функция двойного sha3; при преобразовании этого эталонного кода в реализацию используйте:

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)))
Показать все

Параметры

Для алгоритма используются следующие параметры:

1SAFE_PRIME_512 = 2**512 - 38117     # Наибольшее безопасное простое число, меньшее, чем 2**512
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS,  # Размер набора данных (4 гигабайта); ДОЛЖЕН БЫТЬ КРАТЕН 65536
5      "n_inc": 65536,                   # Приращение значения n за период; ДОЛЖНО БЫТЬ КРАТНО 65536
6                                        # при epochtime=20000 дает прирост 882 МБ в год
7      "cache_size": 2500,               # Размер кэша легкого клиента (может быть выбран легким клиентом; не является частью спецификации алгоритма)
8      "diff": 2**14,                    # Сложность (корректируется во время оценки блока)
9      "epochtime": 100000,              # Длительность эпохи в блоках (как часто обновляется набор данных)
10      "k": 1,                           # Количество родителей узла
11      "w": w,                          # Используется для хэширования модульным возведением в степень
12      "accesses": 200,                  # Количество обращений к набору данных во время хэширования
13      "P": SAFE_PRIME_512               # Безопасное простое число для хэширования и генерации случайных чисел
14}
Показать все

В данном случае P является простым числом, выбранным таким образом, чтобы log₂(P) был незначительно меньше 512, что соответствует 512 битам, которые мы использовали для представления наших чисел. Обратите внимание, что фактически необходимо хранить только вторую половину DAG, поэтому фактическое требование к ОЗУ начинается с 1 ГБ и увеличивается на 441 МБ в год.

Построение графа Dagger

Примитив построения графа Dagger определяется следующим образом:

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
Показать все

По сути, он начинает граф с одного узла sha3(seed), а затем последовательно добавляет другие узлы на основе случайных предыдущих узлов. При создании нового узла вычисляется модульная степень начального числа для случайного выбора некоторых индексов, меньших i (с использованием x % i выше), и значения узлов по этим индексам используются в вычислении для генерации нового значения x, которое затем подается в небольшую функцию доказательства выполнения работы (на основе XOR) для окончательной генерации значения графа по индексу i. Обоснование этого конкретного дизайна заключается в том, чтобы принудить к последовательному доступу к DAG; следующее значение DAG, к которому будет осуществлен доступ, не может быть определено, пока не станет известно текущее значение. Наконец, модульное возведение в степень далее хэширует результат.

Этот алгоритм опирается на несколько результатов из теории чисел. См. обсуждение в приложении ниже.

Оценка легкого клиента

Приведенная выше конструкция графа предназначена для того, чтобы каждый узел в графе можно было реконструировать путем вычисления поддерева из небольшого числа узлов и требуя лишь небольшого количества вспомогательной памяти. Обратите внимание, что при k=1 поддерево представляет собой лишь цепочку значений, ведущую к первому элементу в DAG.

Вычислительная функция легкого клиента для DAG работает следующим образом:

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)
Показать все

По сути, это просто переписанный вышеуказанный алгоритм, который удаляет цикл вычисления значений для всего DAG и заменяет предыдущий поиск узла рекурсивным вызовом или поиском в кэше. Обратите внимание, что для k=1 кэш не нужен, хотя дальнейшая оптимизация фактически предварительно вычисляет первые несколько тысяч значений DAG и сохраняет их в качестве статического кэша для вычислений; см. приложение для реализации этого кода.

Двойной буфер DAG

В полном клиенте используется двойной буфер (opens in a new tab) из 2 DAG, созданных по приведенной выше формуле. Идея заключается в том, что DAG создаются каждые epochtime блоков в соответствии с приведенными выше параметрами. Вместо того чтобы клиент использовал последний созданный DAG, он использует предыдущий. Преимущество этого заключается в том, что это позволяет заменять DAG со временем без необходимости включать шаг, на котором майнеры должны внезапно пересчитывать все данные. В противном случае существует вероятность резкого временного замедления обработки цепочки через равные промежутки времени и резкого усиления централизации. Таким образом, в течение тех нескольких минут, пока все данные не будут пересчитаны, возникают риски атаки 51 %.

Алгоритм, используемый для генерации набора DAG, который, в свою очередь, используется для вычисления работы для блока, следующий:

1def get_prevhash(n):
2    from pyethereum.blocks import GENESIS_PREVHASH
3    from pyethereum import chain_manager
4    if n <= 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        # Создание резервного буфера невозможно, создается только передний буфер
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"]}}
Показать все

Hashimoto

Идея оригинального Hashimoto заключается в использовании блокчейна в качестве набора данных, выполняя вычисление, которое выбирает N индексов из блокчейна, собирает транзакции по этим индексам, выполняет операцию XOR над этими данными и возвращает хэш результата. Оригинальный алгоритм Таддеуша Дрии, переведенный на Python для согласованности, следующий:

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_mix ^ (nonce << 192)

К сожалению, хотя Hashimoto считается сложным для ОЗУ, он опирается на 256-битную арифметику, что влечет за собой значительные вычислительные накладные расходы. Однако для решения этой проблемы Dagger-Hashimoto использует только младшие 64 бита при индексации своего набора данных.

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)

Использование двойного SHA3 позволяет осуществлять своего рода почти мгновенную предварительную верификацию с нулевыми данными, проверяя только то, что было предоставлено правильное промежуточное значение. Этот внешний уровень доказательства выполнения работы очень дружелюбен к ASIC и довольно слаб, но существует для того, чтобы еще больше усложнить DDoS-атаки, поскольку этот небольшой объем работы должен быть выполнен для создания блока, который не будет немедленно отклонен. Вот версия для легкого клиента:

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)

Майнинг и верификация

Давайте соберём это всё в алгоритм майнинга:

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
Показать все

И в алгоритм верификации:

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

Верификация, дружественная к легким клиентам:

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

Также обратите внимание, что Dagger-Hashimoto накладывает дополнительные требования на заголовок блока:

Чтобы двухслойная верификация работала, заголовок блока должен содержать как nonce, так и промежуточное значение до применения sha3.
Где-то в заголовке блока должен храниться sha3 текущего набора начальных чисел

Дополнительные материалы

Знаете ресурс сообщества, который вам пригодился? Измените эту страницу и добавьте его!

Приложение

Как отмечалось выше, ГСЧ, используемый для генерации DAG, основывается на некоторых результатах теории чисел. Во-первых, мы даем гарантию, что ГСЧ Лемера, который лежит в основе переменной picker, имеет большой период. Во-вторых, мы показываем, что pow(x,3,P) не отобразит x в 1 или P-1 при условии, что x изначально находится в диапазоне [2,P-2]. Наконец, мы показываем, что pow(x,3,P) имеет низкий уровень коллизий при использовании в качестве хэш-функции.

Генератор случайных чисел Лемера

Хотя функция produce_dag не обязана генерировать несмещенные случайные числа, потенциальная угроза заключается в том, что seed**i % P принимает лишь небольшое количество значений. Это может дать преимущество майнерам, распознающим закономерность, перед теми, кто ее не распознает.

Чтобы избежать этого, используется результат из теории чисел. Безопасное простое число (opens in a new tab) определяется как простое число P, такое что (P-1)/2 также является простым числом. Порядок члена x мультипликативной группы (opens in a new tab) ℤ/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, поскольку по Малой теореме Ферма мы имеем:

x^P-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:

Наблюдение 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

Модульное возведение в степень как хэш-функция

Для определенных значений 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 удовлетворяет вышеприведенному утверждению.

Более эффективный алгоритм оценки на основе кэша

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)
Показать все

Dagger-Hashimoto

Предварительные условия