ড্যাগার-হাশিমোতো

ড্যাগার-হাশিমোতো ছিল ইথিরিয়ামের মাইনিং এ্যালগরিদমের মূল গবেষণা বাস্তবায়ন এবং স্পেসিফিকেশন। ড্যাগার-হাশিমোতো পরবর্তীতে Ethash দ্বারা প্রতিস্থাপিত হয়। ১৫ই সেপ্টেম্বর ২০২২-এ The Merge-এর মাধ্যমে মাইনিং সম্পূর্ণভাবে বন্ধ করে দেওয়া হয়। এরপর থেকে, ইথিরিয়ামকে সুরক্ষিত করার জন্য এর পরিবর্তে একটি প্রুফ-অফ-স্টেক মেকানিজম ব্যবহার করা হচ্ছে। এই পেজটি ঐতিহাসিক আগ্রহের জন্য - এখানকার তথ্যগুলো মার্জ-পরবর্তী ইথিরিয়ামের জন্য আর প্রাসঙ্গিক নয়।

পূর্বশর্ত

এই পেজটি ভালোভাবে বোঝার জন্য, আমরা সুপারিশ করছি যে আপনি প্রথমে প্রুফ-অফ-ওয়ার্ক কনসেন্সাস, মাইনিং, এবং মাইনিং এ্যালগরিদম সম্পর্কে পড়ে নিন।

ড্যাগার-হাশিমোতো

ড্যাগার-হাশিমোতো দুটি লক্ষ্য পূরণের উদ্দেশ্যে তৈরি:

1. ASIC-প্রতিরোধ (ASIC-resistance): এ্যালগরিদমের জন্য বিশেষায়িত হার্ডওয়্যার তৈরি করার সুবিধা যতটা সম্ভব কম হওয়া উচিত
2. লাইট ক্লায়েন্ট যাচাইযোগ্যতা (Light client verifiability): একটি ব্লক একটি লাইট ক্লায়েন্ট দ্বারা দক্ষতার সাথে যাচাইযোগ্য হওয়া উচিত।

একটি অতিরিক্ত পরিবর্তনের মাধ্যমে, আমরা প্রয়োজনে কীভাবে তৃতীয় একটি লক্ষ্য পূরণ করা যায় তাও নির্দিষ্ট করি, তবে এর জন্য অতিরিক্ত জটিলতা স্বীকার করতে হবে:

সম্পূর্ণ চেইন স্টোরেজ (Full chain storage): মাইনিং এর জন্য সম্পূর্ণ ব্লকচেইন স্টেট সংরক্ষণ করা প্রয়োজন (ইথিরিয়াম স্টেট ট্রাই-এর অনিয়মিত কাঠামোর কারণে, আমরা আশা করি যে কিছু প্রুনিং বা ছাঁটাই সম্ভব হবে, বিশেষ করে কিছু বহুল ব্যবহৃত কন্ট্রাক্টের ক্ষেত্রে, তবে আমরা এটি ন্যূনতম রাখতে চাই)।

ড্যাগ (DAG) জেনারেশন

এ্যালগরিদমের কোডটি নিচে পাইথনে সংজ্ঞায়িত করা হবে। প্রথমে, আমরা নির্দিষ্ট নির্ভুলতার আনসাইনড ইন্টিজারগুলোকে স্ট্রিংয়ে রূপান্তর করার জন্য 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 # 2**512 এর চেয়ে ছোট সবচেয়ে বড় সেফ প্রাইম
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS, # ডেটাসেটের আকার (৪ গিগাবাইট); অবশ্যই ৬৫৫৩৬ এর গুণিতক হতে হবে
5      "n_inc": 65536, # প্রতি পিরিয়ডে n এর মান বৃদ্ধি; অবশ্যই ৬৫৫৩৬ এর গুণিতক হতে হবে
6                                        # epochtime=20000 এর সাথে প্রতি বছর ৮৮২ মেগাবাইট (MB) বৃদ্ধি পায়
7      "cache_size": 2500, # লাইট ক্লায়েন্টের ক্যাশের আকার (লাইট দ্বারা নির্বাচন করা যেতে পারে
8                                        # ক্লায়েন্ট; অ্যালগো স্পেকের অংশ নয়)
9      "diff": 2**14, # ডিফিকাল্টি (ব্লক মূল্যায়নের সময় সমন্বয় করা হয়)
10      "epochtime": 100000, # ব্লকে একটি ইপকের দৈর্ঘ্য (কত ঘন ঘন ডেটাসেট আপডেট করা হয়)
11      "k": 1, # একটি নোডের প্যারেন্টের সংখ্যা
12      "w": w, # মডুলার এক্সপোনেনসিয়েশন হ্যাসিং এর জন্য ব্যবহৃত হয়
13      "accesses": 200, # হ্যাসিমোতো এর সময় ডেটাসেট অ্যাক্সেসের সংখ্যা
14      "P": SAFE_PRIME_512 # হ্যাসিং এবং র‍্যান্ডম নম্বর জেনারেশনের জন্য সেফ প্রাইম
15}
সব দেখান
কপি করুন

এই ক্ষেত্রে P হলো এমন একটি মৌলিক সংখ্যা (prime) যা এমনভাবে বেছে নেওয়া হয়েছে যেন log₂(P) ৫১২-এর চেয়ে সামান্য কম হয়, যা আমাদের সংখ্যাগুলোকে উপস্থাপন করতে ব্যবহৃত ৫১২ বিটের সাথে মিলে যায়। মনে রাখবেন যে ড্যাগ (DAG)-এর শুধুমাত্র শেষ অর্ধেক অংশটি সংরক্ষণ করা প্রয়োজন, তাই ডি-ফ্যাক্টো RAM-এর প্রয়োজনীয়তা 1 GB থেকে শুরু হয় এবং প্রতি বছর 441 MB করে বৃদ্ধি পায়।

ড্যাগার গ্রাফ তৈরি

ড্যাগার গ্রাফ তৈরির প্রাথমিক রূপটি নিচে সংজ্ঞায়িত করা হলো:

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-এর চেয়ে ছোট কিছু সূচক (index) র্যান্ডমভাবে নির্বাচন করার জন্য সিডের একটি মডুলার পাওয়ার গণনা করা হয় (উপরে x % i ব্যবহার করে), এবং সেই সূচকগুলোতে থাকা নোডগুলোর মান ব্যবহার করে x-এর জন্য একটি নতুন মান তৈরি করার হিসাব করা হয়, যা পরে একটি ছোট প্রুফ-অফ-ওয়ার্ক ফাংশনে (XOR-এর ওপর ভিত্তি করে) পাঠানো হয় যাতে শেষ পর্যন্ত i সূচকে গ্রাফের মান তৈরি করা যায়। এই নির্দিষ্ট ডিজাইনের পেছনের যুক্তি হলো ড্যাগ (DAG)-এর সিকোয়েন্সিয়াল অ্যাক্সেস বাধ্য করা; বর্তমান মান জানা না যাওয়া পর্যন্ত ড্যাগ-এর পরবর্তী কোন মানটি অ্যাক্সেস করা হবে তা নির্ধারণ করা যায় না। সবশেষে, মডুলার এক্সপোনেনসিয়েশন ফলাফলটিকে আরও হ্যাস করে।

এই এ্যালগরিদমটি সংখ্যাতত্ত্বের (number theory) বেশ কয়েকটি ফলাফলের ওপর নির্ভর করে। আলোচনার জন্য নিচের পরিশিষ্টটি দেখুন।

লাইট ক্লায়েন্ট মূল্যায়ন

উপরের গ্রাফ নির্মাণের উদ্দেশ্য হলো গ্রাফের প্রতিটি নোডকে শুধুমাত্র অল্প সংখ্যক নোডের একটি সাবট্রি গণনা করে পুনর্গঠন করার সুযোগ দেওয়া এবং এর জন্য শুধুমাত্র অল্প পরিমাণ সহায়ক মেমরি প্রয়োজন হয়। মনে রাখবেন যে 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) ব্যবহার করা হয়। ধারণাটি হলো উপরের প্যারামিটার অনুযায়ী প্রতি epochtime সংখ্যক ব্লকস-এ ড্যাগ তৈরি হয়। ক্লায়েন্ট সর্বশেষ উৎপাদিত ড্যাগ ব্যবহার করার পরিবর্তে, এর আগেরটি ব্যবহার করে। এর সুবিধা হলো এটি সময়ের সাথে সাথে ড্যাগগুলোকে প্রতিস্থাপন করার সুযোগ দেয়, যেখানে মাইনারদের হঠাৎ করে সমস্ত ডেটা পুনরায় গণনা করার কোনো ধাপ অন্তর্ভুক্ত করার প্রয়োজন হয় না। অন্যথায়, নিয়মিত বিরতিতে চেইন প্রসেসিংয়ে হঠাৎ করে অস্থায়ী ধীরগতি এবং নাটকীয়ভাবে কেন্দ্রীকরণ বৃদ্ধির সম্ভাবনা থাকে। ফলে সমস্ত ডেটা পুনরায় গণনা করার আগের কয়েক মিনিটের মধ্যে ৫১% এ্যাটাক-এর ঝুঁকি থাকে।

একটি ব্লক-এর কাজ গণনা করতে ব্যবহৃত ড্যাগগুলোর সেট তৈরি করার এ্যালগরিদমটি নিচে দেওয়া হলো:

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        # কোনো ব্যাক বাফার সম্ভব নয়, শুধু ফ্রন্ট বাফার তৈরি করুন
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) মূল এ্যালগরিদমটি, সামঞ্জস্যের জন্য পাইথনে অনুবাদ করা হয়েছে, যা নিচে দেওয়া হলো:

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-বিট পাটিগণিতের ওপর নির্ভর করে, যার উল্লেখযোগ্য কম্পিউটেশনাল ওভারহেড রয়েছে। তবে, ড্যাগার-হাশিমোতো এই সমস্যা সমাধানের জন্য এর ডেটাসেট ইনডেক্স করার সময় শুধুমাত্র সবচেয়ে কম গুরুত্বপূর্ণ (least significant) 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
কপি করুন

এছাড়াও, মনে রাখবেন যে ড্যাগার-হাশিমোতো ব্লক হেডারের ওপর অতিরিক্ত প্রয়োজনীয়তা আরোপ করে:

• দুই-স্তরের যাচাইকরণ কাজ করার জন্য, একটি ব্লক হেডারে অবশ্যই নন্স এবং মধ্যবর্তী মান pre-sha3 উভয়ই থাকতে হবে
• কোনো এক জায়গায়, একটি ব্লক হেডারকে অবশ্যই বর্তমান সিডসেটের sha3 সংরক্ষণ করতে হবে

আরও পড়ুন

এমন কোনো কমিউনিটি রিসোর্স সম্পর্কে জানেন যা আপনাকে সাহায্য করেছে? এই পেজটি সম্পাদনা করুন এবং এটি যোগ করুন!

পরিশিষ্ট

উপরে যেমন উল্লেখ করা হয়েছে, ড্যাগ (DAG) জেনারেশনের জন্য ব্যবহৃত RNG সংখ্যাতত্ত্বের কিছু ফলাফলের ওপর নির্ভর করে। প্রথমত, আমরা এই নিশ্চয়তা প্রদান করি যে লেহমার (Lehmer) RNG, যা picker ভেরিয়েবলের ভিত্তি, তার একটি বিস্তৃত পর্যায় (wide period) রয়েছে। দ্বিতীয়ত, আমরা দেখাই যে pow(x,3,P) x-কে 1 বা P-1-এ ম্যাপ করবে না, যদি শুরুতে x ∈ [2,P-2] হয়। সবশেষে, আমরা দেখাই যে pow(x,3,P)-কে একটি হ্যাসিং ফাংশন হিসেবে বিবেচনা করা হলে এর কলিশন রেট (collision rate) কম হয়।

লেহমার র্যান্ডম নম্বর জেনারেটর

যদিও produce_dag ফাংশনটির আনবায়াসড (unbiased) র্যান্ডম নম্বর তৈরি করার প্রয়োজন নেই, একটি সম্ভাব্য হুমকি হলো seed**i % P শুধুমাত্র কয়েকটি মান গ্রহণ করে। এটি সেই মাইনারদের সুবিধা দিতে পারে যারা প্যাটার্নটি চিনতে পারে, তাদের তুলনায় যারা পারে না।

এটি এড়ানোর জন্য, সংখ্যাতত্ত্বের একটি ফলাফলের আশ্রয় নেওয়া হয়। একটি সেফ প্রাইম (Safe Prime) (opens in a new tab)-কে এমন একটি মৌলিক সংখ্যা P হিসেবে সংজ্ঞায়িত করা হয় যার জন্য (P-1)/2-ও একটি মৌলিক সংখ্যা। মাল্টিপ্লিকেটিভ গ্রুপ (multiplicative group) (opens in a new tab) ℤ/nℤ-এর একটি সদস্য x-এর অর্ডার (order)-কে ন্যূনতম m হিসেবে সংজ্ঞায়িত করা হয় যাতে

xᵐ mod P ≡ 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's Theorem)][lagrange] অনুযায়ী আমরা পাই যে x-এর অর্ডার হলো 1, 2, (P-1)/2, অথবা P-1।

x-এর অর্ডার 1 হতে পারে না, কারণ ফার্মার লিটল থিওরেম (Fermat's Little Theorem) অনুযায়ী আমরা পাই:

xP-1 mod P ≡ 1

অতএব x-কে অবশ্যই ℤ/nℤ-এর একটি মাল্টিপ্লিকেটিভ আইডেন্টিটি হতে হবে, যা অনন্য। যেহেতু আমরা ধরে নিয়েছি যে x ≠ 1, তাই এটি সম্ভব নয়।

x-এর অর্ডার 2 হতে পারে না যদি না x = P-1 হয়, কারণ এটি P একটি মৌলিক সংখ্যা হওয়ার শর্ত লঙ্ঘন করবে।

উপরের প্রস্তাবনা থেকে, আমরা বুঝতে পারি যে (picker * init) % P ইটারেট করলে এর সাইকেল লেংথ (cycle length) কমপক্ষে (P-1)/2 হবে। এর কারণ হলো আমরা P-কে এমন একটি সেফ প্রাইম হিসেবে নির্বাচন করেছি যা প্রায় দুই-এর একটি উচ্চ ঘাতের (higher power of two) সমান, এবং init হলো [2,2**256+1] ব্যবধানের মধ্যে। P-এর বিশালতার কারণে, আমাদের কখনোই মডুলার এক্সপোনেনসিয়েশন থেকে কোনো সাইকেল আশা করা উচিত নয়।

যখন আমরা ড্যাগ (DAG)-এর প্রথম সেলটি (যাকে init ভেরিয়েবল হিসেবে লেবেল করা হয়েছে) অ্যাসাইন করি, তখন আমরা pow(sha3(seed) + 2, 3, P) গণনা করি। প্রথম দেখায়, এটি গ্যারান্টি দেয় না যে ফলাফলটি 1 বা P-1 কোনোটিই নয়। তবে, যেহেতু P-1 একটি সেফ প্রাইম, তাই আমাদের কাছে নিচের অতিরিক্ত নিশ্চয়তা রয়েছে, যা পর্যবেক্ষণ ১-এর একটি অনুসিদ্ধান্ত:

পর্যবেক্ষণ ২. ধরি 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) ফাংশনটিতে অনেক কলিশন (collisions) থাকতে পারে। উদাহরণস্বরূপ, pow(x,9,19) শুধুমাত্র {1,18} মানগুলো গ্রহণ করে।

যেহেতু P একটি মৌলিক সংখ্যা, তাই মডুলার এক্সপোনেনসিয়েশন হ্যাসিং ফাংশনের জন্য একটি উপযুক্ত w নিচের ফলাফলটি ব্যবহার করে বেছে নেওয়া যেতে পারে:

পর্যবেক্ষণ ৩. ধরি P একটি মৌলিক সংখ্যা; w এবং P-1 সহমৌলিক (relatively prime) হবে যদি এবং কেবল যদি ℤ/Pℤ-এর সমস্ত a এবং b-এর জন্য:

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)
সব দেখান
কপি করুন