Dagger-Hashimoto

Dagger-Hashimoto — це початкова дослідницька реалізація та специфікація для алгоритму майнінгу Ethereum. Алгоритм Dagger-Hashimoto був замінений на Ethash. Майнінг було повністю вимкнено під час Злиття (The Merge) 15 вересня 2022 року. Відтоді безпека Ethereum забезпечується за допомогою механізму доказу частки володіння (proof-of-stake). Ця сторінка представляє історичний інтерес: інформація на ній більше не є актуальною для Ethereum після Злиття.

Передумови

Щоб краще зрозуміти цю сторінку, ми рекомендуємо вам спочатку ознайомитися з консенсусом доказу виконаної роботи (proof-of-work), майнінгом та алгоритмами майнінгу.

Dagger-Hashimoto має на меті досягнення двох цілей:

Стійкість до ASIC: вигода від створення спеціалізованого обладнання для цього алгоритму має бути якомога меншою
Верифікація легким клієнтом: блок має ефективно перевірятися легким клієнтом.

За допомогою додаткової модифікації ми також визначаємо, як за бажанням досягти третьої мети, але за рахунок додаткової складності:

Повне зберігання ланцюга: майнінг повинен вимагати зберігання повного стану блокчейну (через нерегулярну структуру дерева станів Ethereum ми припускаємо, що можливе деяке скорочення, зокрема, деяких часто використовуваних контрактів, але ми хочемо звести це до мінімуму).

Генерація DAG

Код для алгоритму буде визначено на Python нижче. По-перше, ми надаємо encode_int для маршалінгу беззнакових цілих чисел заданої точності в рядки. Його зворотний порядок також наведено:

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

Далі ми припускаємо, що 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     # 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}
Показати все

У цьому випадку 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        # 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"]}}
Показати все

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 є безпечним простим числом, ми маємо таку додаткову гарантію, що є наслідком Спостереження 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

Передумови