Перейти до основного вмісту
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 — це функція подвійного sha3; якщо перетворювати цей еталонний код на реалізацію, використовуйте:

Параметри

Параметри, що використовуються для алгоритму:

P у цьому випадку є простим числом, обраним так, щоб log₂(P) було трохи меншим за 512, що відповідає 512 бітам, які ми використовували для представлення наших чисел. Зверніть увагу, що фактично потрібно зберігати лише другу половину DAG, тому фактична вимога до оперативної пам'яті починається з 1 ГБ і зростає на 441 МБ на рік.

Побудова графа Dagger

Примітив побудови графа Dagger визначається так:

По суті, він починає граф як єдиний вузол, sha3(seed), і звідти починає послідовно додавати інші вузли на основі випадкових попередніх вузлів. Коли створюється новий вузол, обчислюється модульний степінь початкового значення (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)

Використання подвійного SHA3 дозволяє здійснювати форму майже миттєвої попередньої перевірки без даних, перевіряючи лише те, що було надано правильне проміжне значення. Цей зовнішній рівень доказу виконання роботи є дуже дружнім до 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 накладає додаткові вимоги на заголовок блоку:

  • Щоб дворівнева перевірка працювала, заголовок блоку повинен мати як нонс, так і середнє значення до застосування sha3
  • Десь заголовок блоку повинен зберігати sha3 поточного набору початкових значень (seedset)

Подальше читання

Знаєте ресурс спільноти, який вам допоміг? Відредагуйте цю сторінку та додайте його!

Додаток

Як зазначалося вище, генератор випадкових чисел (RNG), що використовується для генерації DAG, спирається на деякі результати з теорії чисел. По-перше, ми надаємо гарантію, що генератор Лемера (Lehmer RNG), який є основою для змінної 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 задовольняє наведене вище твердження.

Більш ефективний алгоритм оцінки на основі кешу