تخطي إلى المحتوى الرئيسي
Change page

⁦Dagger-Hashimoto⁩

كانت Dagger-Hashimoto هي التنفيذ البحثي الأصلي والمواصفات لخوارزمية تعدين إيثيريوم. تم استبدال Dagger-Hashimoto بـ إيثاش. تم إيقاف التعدين تمامًا عند الدمج في 15 September 2022. منذ ذلك الحين، يتم تأمين إيثيريوم باستخدام آلية إثبات الحصة (PoS) بدلاً من ذلك. هذه الصفحة ذات أهمية تاريخية - المعلومات الواردة هنا لم تعد ذات صلة بإيثيريوم ما بعد الدمج.

المتطلبات الأساسية

لفهم هذه الصفحة بشكل أفضل، نوصيك بقراءة المزيد أولاً عن إجماع إثبات العمل (PoW)، والتعدين، وخوارزميات التعدين.

⁦Dagger-Hashimoto⁩

تهدف ⁦Dagger-Hashimoto⁩ إلى تحقيق هدفين:

  1. مقاومة ASIC: يجب أن تكون الفائدة من إنشاء أجهزة متخصصة للخوارزمية صغيرة قدر الإمكان.
  2. قابلية التحقق من قبل عميل خفيف: يجب أن تكون الكتلة قابلة للتحقق بكفاءة بواسطة عميل خفيف.

مع تعديل إضافي، نحدد أيضًا كيفية تحقيق هدف ثالث إذا رغبت في ذلك، ولكن على حساب تعقيد إضافي:

تخزين السلسلة بالكامل: يجب أن يتطلب التعدين تخزين حالة سلسلة الكتل بالكامل (نظرًا للبنية غير المنتظمة لشجرة الحالة في إيثيريوم، نتوقع أن يكون بعض التقليم ممكنًا، خاصة لبعض العقود المستخدمة غالبًا، لكننا نريد تقليل ذلك إلى الحد الأدنى).

إنشاء DAG

سيتم تعريف كود الخوارزمية بلغة Python أدناه. أولاً، نقدم encode_int لتحويل الأعداد الصحيحة غير الموقعة (unsigned ints) ذات الدقة المحددة إلى سلاسل نصية. كما يتم إعطاء معكوسها:

نفترض بعد ذلك أن sha3 هي دالة تأخذ عددًا صحيحًا وتخرج عددًا صحيحًا، وأن dbl_sha3 هي دالة double-sha3؛ إذا كنت تقوم بتحويل هذا الكود المرجعي إلى تنفيذ، فاستخدم:

المعلمات

المعلمات المستخدمة للخوارزمية هي:

P في هذه الحالة هو عدد أولي تم اختياره بحيث يكون log₂(P) أقل بقليل من 512، وهو ما يتوافق مع 512 bits التي كنا نستخدمها لتمثيل أرقامنا. لاحظ أن النصف الأخير فقط من DAG يحتاج فعليًا إلى التخزين، لذلك تبدأ متطلبات ذاكرة الوصول العشوائي (RAM) الفعلية من 1 GB وتنمو بمقدار 441 MB سنويًا.

بناء رسم Dagger البياني

يتم تعريف الأساس لبناء رسم Dagger البياني على النحو التالي:

بشكل أساسي، يبدأ الرسم البياني كعقدة واحدة، sha3(seed)، ومن هناك يبدأ في إضافة عقد أخرى بالتسلسل بناءً على عقد سابقة عشوائية. عند إنشاء عقدة جديدة، يتم حساب قوة معيارية (modular power) للبذرة (seed) لاختيار بعض المؤشرات عشوائيًا التي تكون أقل من i (باستخدام x % i أعلاه)، وتُستخدم قيم العقد عند تلك المؤشرات في عملية حسابية لإنشاء قيمة جديدة لـ x، والتي يتم إدخالها بعد ذلك في دالة إثبات عمل صغيرة (تعتمد على XOR) لتوليد قيمة الرسم البياني في النهاية عند المؤشر i. الأساس المنطقي وراء هذا التصميم المعين هو فرض الوصول التسلسلي إلى DAG؛ لا يمكن تحديد القيمة التالية لـ DAG التي سيتم الوصول إليها حتى تُعرف القيمة الحالية. أخيرًا، تقوم عملية الأس المعياري (modular exponentiation) بتجزئة النتيجة بشكل أكبر.

تعتمد هذه الخوارزمية على عدة نتائج من نظرية الأعداد. راجع الملحق أدناه للمناقشة.

تقييم العميل الخفيف

يهدف بناء الرسم البياني أعلاه إلى السماح بإعادة بناء كل عقدة في الرسم البياني عن طريق حساب شجرة فرعية لعدد صغير فقط من العقد وتتطلب كمية صغيرة فقط من الذاكرة المساعدة. لاحظ أنه مع k=1، تكون الشجرة الفرعية مجرد سلسلة من القيم تصل إلى العنصر الأول في DAG.

تعمل دالة حوسبة العميل الخفيف لـ DAG على النحو التالي:

بشكل أساسي، إنها ببساطة إعادة كتابة للخوارزمية أعلاه التي تزيل حلقة حساب القيم لـ DAG بالكامل وتستبدل البحث السابق عن العقدة باستدعاء متكرر (recursive call) أو بحث في ذاكرة التخزين المؤقت (cache). لاحظ أنه بالنسبة لـ k=1، فإن ذاكرة التخزين المؤقت غير ضرورية، على الرغم من أن التحسين الإضافي يقوم فعليًا بحساب الآلاف القليلة الأولى من قيم DAG مسبقًا ويحتفظ بها كذاكرة تخزين مؤقت ثابتة للعمليات الحسابية؛ راجع الملحق للحصول على تنفيذ برمجي لذلك.

التخزين المؤقت المزدوج لـ DAGs

في العميل الكامل، يتم استخدام تخزين مؤقت مزدوج (opens in a new tab) لـ 2 DAGs تم إنتاجهما بواسطة الصيغة أعلاه. الفكرة هي أن DAGs يتم إنتاجها كل عدد epochtime من الكتل وفقًا للمعلمات أعلاه. بدلاً من أن يستخدم العميل أحدث DAG تم إنتاجه، فإنه يستخدم السابق. تكمن فائدة ذلك في أنه يسمح باستبدال DAGs بمرور الوقت دون الحاجة إلى دمج خطوة حيث يجب على المعدنين فجأة إعادة حساب جميع البيانات. خلاف ذلك، هناك احتمال لحدوث تباطؤ مؤقت مفاجئ في معالجة السلسلة على فترات منتظمة وزيادة المركزية بشكل كبير. وبالتالي مخاطر هجوم 51% خلال تلك الدقائق القليلة قبل إعادة حساب جميع البيانات.

الخوارزمية المستخدمة لإنشاء مجموعة DAGs المستخدمة لحساب العمل لكتلة هي كما يلي:

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-bit، والتي لها عبء حسابي كبير. ومع ذلك، تستخدم ⁦Dagger-Hashimoto⁩ فقط أقل 64 bits أهمية عند فهرسة مجموعة بياناتها لمعالجة هذه المشكلة.

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)

يسمح استخدام double 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⁩ تفرض متطلبات إضافية على رأس الكتلة:

  • لكي يعمل التحقق ثنائي الطبقة، يجب أن يحتوي رأس الكتلة على كل من الرقم الفريد (nonce) والقيمة الوسطى قبل sha3.
  • في مكان ما، يجب أن يخزن رأس الكتلة sha3 لمجموعة البذور (seedset) الحالية.

قراءة إضافية

هل تعرف موردًا مجتمعيًا ساعدك؟ قم بتعديل هذه الصفحة وأضفه!

الملحق

كما لوحظ أعلاه، يعتمد منشئ الأرقام العشوائية (RNG) المستخدم لإنشاء DAG على بعض النتائج من نظرية الأعداد. أولاً، نقدم تأكيدًا على أن Lehmer RNG الذي يمثل الأساس للمتغير picker له فترة واسعة. ثانيًا، نوضح أن pow(x,3,P) لن يقوم بتعيين x إلى 1 أو P-1 بشرط 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 في المجموعة الضربية (multiplicative group) (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 يفي بالافتراض أعلاه.

خوارزمية تقييم أكثر كفاءة تعتمد على ذاكرة التخزين المؤقت