Dagger-Hashamoto

Dagger-Hashimoto زیرساخت و مشخصات اولیه تحقیقاتی برای الگوریتم استخراج اتریوم بود. Dagger-Hashimoto به Ethash تغییر نام داده شد. استخراج به طور کامل در ادغام در 15 سپتامبر 2022 خاموش شد. از آن زمان، اتریوم با استفاده از مکانیزم اثبات سهام ایمن شده است. این صفحه برای رجوع تاریخی است - اطلاعات اینجا دیگر مرتبط به اتریوم پس از ادغام نیست.

موارد مورد نیاز

برای فهم بهتر این مقاله، پیشنهاد می کنیم ابتدا اجماع اثبات کار،استخراج و الگوریتم استخراج را مطالعه کنید.

Dagger-Hashamato دو هدف را برآورده می کند:

مقاومت در برابر اسیک: مزیت حاصل از ایجاد سخت افزار تخصصی برای الگوریتم باید تا حد امکان کم باشد
تأیید پذیری کاربر سبک: یک بلوک باید به طور مؤثر توسط کاربر سبک قابل تأیید باشد.

با یک تغییر اضافی، همچنین مشخص می کنیم که چگونه می توان یک هدف سوم را در صورت تمایل برآورده کرد، هر چند با بهای افزایش پیچیدگی همراه باشد:

ذخیره‌سازی زنجیره کامل: استخراج باید به ذخیره‌سازی حالت بلاک چین کامل نیاز داشته باشد (به دلیل ساختار نامنظم درخت حالت اتریوم، پیش‌بینی می‌کنیم برخی هرس‌ها امکان‌پذیر باشد، به ویژه در بعضی قراردادهای پرمصرف، ولی می خواهیم این را به حداقل برسانیم).

تولید 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 یک تابع double-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 در واقع باید ذخیره شود، بنابراین نیاز واقعی RAM از 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 ها در هر تعداد زمان ایپوک بلوک، مطابق با پارامترهای بالا تولید می شوند. به جای اینکه مشتری از آخرین DAG تولید شده استفاده کند، از 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"]}}
نمایش همه
 کپی

هاشیموتو

ایده پشت هاشیموتو اصلی استفاده از بلاک چین به عنوان مجموعه داده، انجام محاسباتی است که N شاخص را از زنجیره بلوکی انتخاب می‌کند، تراکنش‌ها را در آن شاخص‌ها جمع‌آوری می‌کند، XOR این داده‌ها را انجام می‌دهد و هشِ نتیجه را برمی‌گرداند. الگوریتم اصلی Thaddeus Dryja که برای سازگاری به 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)
 کپی

متأسفانه، در حالی که هاشیموتو برای RAM سخت در نظر گرفته می شود، بر محاسبات 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 الزامات اضافی را بر روی سر بلوک اعمال می کند:

برای اینکه تأیید دو لایه کار کند، یک سر بلوک باید هم مقدار نانس و هم مقدار میانی pre-sha3 را داشته باشد
در جایی، یک سر بلوک باید sha3 مجموعه seedset فعلی را ذخیره کند

اطلاعات بیشتر

آیا منبعی اجتماعی می‌شناسید که به شما کمک کرده باشد؟ این صفحه را ویرایش کنید و آن را اضافه کنید!

پیوست‌

همانطور که در بالا ذکر شد، RNG مورد استفاده برای تولید DAG به برخی نتایج نظریه اعداد متکی است. اول، ما اطمینان می دهیم که Lehmer RNG که مبنایی برای متغیر picker است دارای یک دوره گسترده است. دوم، نشان می‌دهیم که pow(x,3,P) x را به 1 یا P-1</0 نگاشت نمی‌کند. > <code>x ∈ [2,P-2] برای شروع ارائه شده است. در نهایت، نشان می‌دهیم که pow(x,3,P) وقتی به عنوان یک تابع هش در نظر گرفته می‌شود، نرخ برخورد پایینی دارد.

مولد اعداد تصادفی Lehmer

در حالی که تابع produce_dag نیازی به تولید اعداد تصادفی بی طرفانه ندارد، یک تهدید بالقوه این است که seed**i % P فقط تعداد انگشت شماری از مقادیر را دریافت کند. این می تواند مزیتی برای استخراجگرها ایجاد کند که الگو را نسبت به کسانی که این کار را نمی شناسند، تشخیص دهند.

برای جلوگیری از این امر، از یک نتیجه نظریه اعداد استفاده می شود. Safe Prime(opens in a new tab) به صورت اول P تعریف شده است، طوری که (P-1)/2 نیز اول باشد. ترتیب یک عضو x از گروه ضربی(opens in a new tab) ℤ/nℤ حداقل m تعریف شده است، طوری که

1xᵐ 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 یک عدد اول امن است، پس با [قضیه لاگرانژ] [لاگرانژ] می‌بینیم که ترتیب x یا 1 است یا 2 یا (P-1)/2 یا P-1.

ترتیب x نمی تواند 1 باشد، زیرا با قضیه کوچک فرما داریم:

1xP-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</ 0> و <code>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-Hashamoto

موارد مورد نیاز