Перейти к основному контенту
Change page

Dagger-Hashimoto

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

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

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

Dagger-Hashimoto

Dagger-Hashimoto стремится достичь двух целей:

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

С помощью дополнительной модификации мы также определяем, как при желании достичь третьей цели, но ценой дополнительной сложности:

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

Генерация DAG

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

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

Параметры

Параметры, используемые для алгоритма:

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

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

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

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

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

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

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

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

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

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

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

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

Hashimoto

Идея оригинального алгоритма Hashimoto заключается в использовании блокчейна в качестве набора данных, выполнении вычисления, которое выбирает N индексов из блокчейна, собирает транзакции по этим индексам, выполняет XOR этих данных и возвращает хеш результата. Оригинальный алгоритм Таддеуса Драйи (Thaddeus Dryja), переведенный на 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 младших бита при индексировании своего набора данных для решения этой проблемы.

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-атаки еще более сложными, поскольку этот небольшой объем работы должен быть выполнен для создания блока, который не будет немедленно отклонен. Вот версия для легкого клиента:

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)

Майнинг и проверка

Теперь давайте соберем все это вместе в алгоритм майнинга:

Вот алгоритм проверки:

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

Проверка, дружественная к легкому клиенту:

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 текущего набора сидов.

Дополнительная литература

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

Приложение

Как отмечалось выше, генератор случайных чисел (ГСЧ), используемый для генерации 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, так как по малой теореме Ферма мы имеем:

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

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

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

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