டாகர்-ஹாஷிமோட்டோ (Dagger-Hashimoto)

டாகர்-ஹாஷிமோட்டோ என்பது Ethereum இன் மைனிங் அல்காரிதத்திற்கான அசல் ஆராய்ச்சி செயலாக்கம் மற்றும் விவரக்குறிப்பு ஆகும். டாகர்-ஹாஷிமோட்டோ Ethash ஆல் மாற்றப்பட்டது. 15 செப்டம்பர் 2022 அன்று The Merge இல் மைனிங் முழுமையாக நிறுத்தப்பட்டது. அதிலிருந்து, Ethereum அதற்குப் பதிலாக proof-of-stake பொறிமுறையைப் பயன்படுத்தி பாதுகாக்கப்படுகிறது. இந்தப் பக்கம் வரலாற்று ஆர்வத்திற்காக மட்டுமே - இங்குள்ள தகவல்கள் மெர்ஜுக்குப் பிந்தைய Ethereum-க்கு இனி பொருந்தாது.

முன்நிபந்தனைகள்

இந்தப் பக்கத்தை நன்கு புரிந்துகொள்ள, முதலில் proof-of-work consensus, mining, மற்றும் mining algorithms பற்றிப் படிக்குமாறு பரிந்துரைக்கிறோம்.

டாகர்-ஹாஷிமோட்டோ

டாகர்-ஹாஷிமோட்டோ இரண்டு இலக்குகளைப் பூர்த்தி செய்வதை நோக்கமாகக் கொண்டுள்ளது:

1. ASIC-எதிர்ப்பு: அல்காரிதத்திற்காக சிறப்பு வன்பொருளை உருவாக்குவதன் மூலம் கிடைக்கும் நன்மை முடிந்தவரை சிறியதாக இருக்க வேண்டும்
2. லைட் கிளையண்ட் சரிபார்ப்பு: ஒரு பிளாக்கை லைட் கிளையண்ட் மூலம் திறமையாக சரிபார்க்க முடியும்.

கூடுதல் மாற்றத்துடன், விரும்பினால் மூன்றாவது இலக்கை எவ்வாறு நிறைவேற்றுவது என்பதையும் நாங்கள் குறிப்பிடுகிறோம், ஆனால் கூடுதல் சிக்கலான செலவில்:

முழு செயின் சேமிப்பு: மைனிங்கிற்கு முழு பிளாக்செயின் நிலையின் சேமிப்பு தேவைப்பட வேண்டும் (Ethereum ஸ்டேட் ட்ரையின் ஒழுங்கற்ற அமைப்பு காரணமாக, சில கத்தரித்து (pruning) சாத்தியமாகும் என்று நாங்கள் எதிர்பார்க்கிறோம், குறிப்பாக அடிக்கடி பயன்படுத்தப்படும் சில ஒப்பந்தங்களில், ஆனால் இதை நாங்கள் குறைக்க விரும்புகிறோம்).

DAG உருவாக்கம்

அல்காரிதத்திற்கான குறியீடு கீழே Python இல் வரையறுக்கப்படும். முதலில், குறிப்பிட்ட துல்லியத்தின் கையொப்பமிடப்படாத முழு எண்களை (unsigned ints) சரங்களாக (strings) மாற்றுவதற்கு 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 என்பது ஒரு முழு எண்ணை எடுத்து ஒரு முழு எண்ணை வெளியிடும் ஒரு சார்பு (function) என்றும், 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 # 2**512 ஐ விட குறைவான மிகப்பெரிய பாதுகாப்பான பகா எண்
2
3params = {
4      "n": 4000055296 * 8 // NUM_BITS, # தரவுத்தொகுப்பின் அளவு (4 ஜிகாபைட்); 65536 இன் மடங்காக இருக்க வேண்டும்
5      "n_inc": 65536, # ஒவ்வொரு காலகட்டத்திற்கும் n இன் மதிப்பில் அதிகரிப்பு; 65536 இன் மடங்காக இருக்க வேண்டும்
6                                        # epochtime=20000 உடன் வருடத்திற்கு 882 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 என்பது log₂(P) 512 ஐ விட சற்று குறைவாக இருக்கும்படி தேர்ந்தெடுக்கப்பட்ட ஒரு பகா எண் (prime) ஆகும், இது நமது எண்களைக் குறிக்க நாம் பயன்படுத்தும் 512 பிட்களுக்கு ஒத்திருக்கிறது. 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) என்ற ஒற்றை முனையாக (node) தொடங்குகிறது, அங்கிருந்து சீரற்ற முந்தைய முனைகளின் அடிப்படையில் மற்ற முனைகளை வரிசையாகச் சேர்க்கத் தொடங்குகிறது. ஒரு புதிய முனை உருவாக்கப்படும் போது, i ஐ விடக் குறைவான சில குறியீடுகளை (indices) தோராயமாகத் தேர்ந்தெடுக்க (மேலே உள்ள x % i ஐப் பயன்படுத்தி) விதையின் (seed) மாடுலர் பவர் கணக்கிடப்படுகிறது, மேலும் அந்த குறியீடுகளில் உள்ள முனைகளின் மதிப்புகள் x க்கான புதிய மதிப்பை உருவாக்க ஒரு கணக்கீட்டில் பயன்படுத்தப்படுகின்றன, இது பின்னர் குறியீடு i இல் வரைபடத்தின் மதிப்பை இறுதியாக உருவாக்க ஒரு சிறிய proof of work சார்புக்குள் (XOR அடிப்படையில்) செலுத்தப்படுகிறது. இந்த குறிப்பிட்ட வடிவமைப்பின் பின்னணியில் உள்ள காரணம் DAG இன் தொடர்ச்சியான அணுகலைக் கட்டாயப்படுத்துவதாகும்; தற்போதைய மதிப்பு அறியப்படும் வரை அணுகப்படும் DAG இன் அடுத்த மதிப்பைத் தீர்மானிக்க முடியாது. இறுதியாக, மாடுலர் எக்ஸ்போனென்சியேஷன் முடிவை மேலும் ஹாஷ் செய்கிறது.

இந்த அல்காரிதம் எண் கோட்பாட்டின் பல முடிவுகளை நம்பியுள்ளது. விவாதத்திற்கு கீழே உள்ள பிற்சேர்க்கையைப் பார்க்கவும்.

லைட் கிளையண்ட் மதிப்பீடு

மேலே உள்ள வரைபடக் கட்டுமானம், வரைபடத்தில் உள்ள ஒவ்வொரு முனையையும் ஒரு சிறிய எண்ணிக்கையிலான முனைகளின் துணை மரத்தை (subtree) கணக்கிடுவதன் மூலம் மறுகட்டமைக்க அனுமதிக்க உத்தேசித்துள்ளது மற்றும் இதற்கு ஒரு சிறிய அளவு துணை நினைவகம் மட்டுமே தேவைப்படுகிறது. 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 க்கான மதிப்புகளைக் கணக்கிடும் லூப்பை அகற்றி, முந்தைய முனை தேடலை ஒரு சுழல்நிலை அழைப்பு (recursive call) அல்லது கேச் தேடலுடன் (cache lookup) மாற்றும் மேலே உள்ள அல்காரிதத்தின் மறுஎழுத்து மட்டுமே. k=1 க்கு கேச் தேவையற்றது என்பதை நினைவில் கொள்ளவும், இருப்பினும் மேலும் மேம்படுத்துதல் உண்மையில் DAG இன் முதல் சில ஆயிரம் மதிப்புகளை முன்கூட்டியே கணக்கிட்டு, கணக்கீடுகளுக்கான நிலையான கேச் ஆக வைத்திருக்கிறது; இதற்கான குறியீடு செயலாக்கத்திற்கு பிற்சேர்க்கையைப் பார்க்கவும்.

DAGகளின் இரட்டை இடையகம் (Double buffer)

ஒரு முழு கிளையண்டில், மேலே உள்ள சூத்திரத்தால் உருவாக்கப்பட்ட 2 DAGகளின் இரட்டை இடையகம் (double buffer) (opens in a new tab) பயன்படுத்தப்படுகிறது. மேலே உள்ள அளவுருக்களின்படி ஒவ்வொரு epochtime பிளாக்குகளின் எண்ணிக்கைக்கும் 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        # பின் இடையகம் சாத்தியமில்லை, முன் இடையகத்தை மட்டும் உருவாக்கவும்
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-பிட் எண்கணிதத்தை நம்பியுள்ளது, இது கணிசமான கணக்கீட்டு மேல்நிலையைக் (computational overhead) கொண்டுள்ளது. இருப்பினும், டாகர்-ஹாஷிமோட்டோ இந்த சிக்கலைத் தீர்க்க அதன் தரவுத்தொகுப்பை அட்டவணைப்படுத்தும் போது குறைந்த முக்கியத்துவம் வாய்ந்த 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 இன் பயன்பாடு பூஜ்ஜிய-தரவு, உடனடி முன்-சரிபார்ப்பு வடிவத்தை அனுமதிக்கிறது, சரியான இடைநிலை மதிப்பு வழங்கப்பட்டதா என்பதை மட்டுமே சரிபார்க்கிறது. proof-of-work இன் இந்த வெளி அடுக்கு மிகவும் 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
நகலெடு

மேலும், டாகர்-ஹாஷிமோட்டோ பிளாக் தலைப்பில் கூடுதல் தேவைகளை விதிக்கிறது என்பதை நினைவில் கொள்ளவும்:

• இரண்டு அடுக்கு சரிபார்ப்பு செயல்பட, ஒரு பிளாக் தலைப்பில் நான்ஸ் (nonce) மற்றும் நடுத்தர மதிப்பு pre-sha3 ஆகிய இரண்டும் இருக்க வேண்டும்
• எங்காவது, ஒரு பிளாக் தலைப்பு தற்போதைய சீட்செட்டின் (seedset) sha3 ஐ சேமிக்க வேண்டும்

மேலும் படிக்க

உங்களுக்கு உதவிய சமூக வளம் பற்றி தெரியுமா? இந்தப் பக்கத்தைத் திருத்தி அதைச் சேர்க்கவும்!

பிற்சேர்க்கை

மேலே குறிப்பிட்டுள்ளபடி, DAG உருவாக்கத்திற்குப் பயன்படுத்தப்படும் RNG எண் கோட்பாட்டின் சில முடிவுகளை நம்பியுள்ளது. முதலாவதாக, picker மாறிக்கு அடிப்படையான Lehmer RNG ஒரு பரந்த காலத்தைக் கொண்டுள்ளது என்பதற்கான உத்தரவாதத்தை நாங்கள் வழங்குகிறோம். இரண்டாவதாக, x ∈ [2,P-2] எனத் தொடங்கினால் pow(x,3,P) ஆனது x ஐ 1 அல்லது P-1 க்கு மேப் செய்யாது என்பதைக் காட்டுகிறோம். இறுதியாக, pow(x,3,P) ஒரு ஹாஷிங் சார்பாகக் கருதப்படும்போது குறைந்த மோதல் விகிதத்தைக் (collision rate) கொண்டுள்ளது என்பதைக் காட்டுகிறோம்.

லெஹ்மர் சீரற்ற எண் உருவாக்கி (Lehmer random number generator)

produce_dag சார்பு சார்பற்ற சீரற்ற எண்களை உருவாக்க வேண்டிய அவசியமில்லை என்றாலும், seed**i % P ஒரு சில மதிப்புகளை மட்டுமே எடுப்பது ஒரு சாத்தியமான அச்சுறுத்தலாகும். இது பேட்டர்னை அங்கீகரிக்கும் மைனர்களுக்கு, அங்கீகரிக்காதவர்களை விட ஒரு நன்மையை வழங்கக்கூடும்.

இதைத் தவிர்க்க, எண் கோட்பாட்டிலிருந்து ஒரு முடிவு பயன்படுத்தப்படுகிறது. ஒரு பாதுகாப்பான பகா எண் (Safe Prime) (opens in a new tab) என்பது (P-1)/2 என்பதும் ஒரு பகா எண்ணாக இருக்கும்படி ஒரு பகா எண் P என வரையறுக்கப்படுகிறது. பெருக்கல் குழுவின் (multiplicative group) (opens in a new tab) ℤ/nℤ இன் உறுப்பினர் x இன் வரிசை (order) என்பது

xᵐ mod P ≡ 1

கவனிப்பு 1. பாதுகாப்பான பகா எண் P க்கான பெருக்கல் குழு ℤ/Pℤ இன் உறுப்பினராக x இருக்கட்டும். 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 ஆக இருக்கும்.

ஃபெர்மட்டின் சிறிய தேற்றத்தின்படி (Fermat's Little Theorem) நாம் பெறுவதால், x இன் வரிசை 1 ஆக இருக்க முடியாது:

xP-1 mod P ≡ 1

எனவே x என்பது ℤ/nℤ இன் பெருக்கல் அடையாளமாக (multiplicative identity) இருக்க வேண்டும், இது தனித்துவமானது. அனுமானத்தின்படி x ≠ 1 என்று நாம் கருதியதால், இது சாத்தியமில்லை.

x = P-1 ஆக இல்லாவிட்டால் x இன் வரிசை 2 ஆக இருக்க முடியாது, ஏனெனில் இது P ஒரு பகா எண் என்பதை மீறும்.

மேற்கண்ட முன்மொழிவிலிருந்து, (picker * init) % P ஐ மீண்டும் மீண்டும் செய்வது குறைந்தபட்சம் (P-1)/2 சுழற்சி நீளத்தைக் கொண்டிருக்கும் என்பதை நாம் அங்கீகரிக்கலாம். ஏனென்றால், P ஐ தோராயமாக இரண்டின் அதிக பவருக்கு சமமான பாதுகாப்பான பகா எண்ணாகத் தேர்ந்தெடுத்தோம், மேலும் init என்பது [2,2**256+1] இடைவெளியில் உள்ளது. P இன் அளவைக் கருத்தில் கொண்டு, மாடுலர் எக்ஸ்போனென்சியேஷனிலிருந்து ஒரு சுழற்சியை நாம் ஒருபோதும் எதிர்பார்க்கக்கூடாது.

DAG இல் முதல் கலத்தை (cell) ஒதுக்கும்போது (init என பெயரிடப்பட்ட மாறி), நாம் pow(sha3(seed) + 2, 3, P) ஐக் கணக்கிடுகிறோம். முதல் பார்வையில், முடிவு 1 அல்லது P-1 ஆக இருக்காது என்பதற்கு இது உத்தரவாதம் அளிக்காது. இருப்பினும், P-1 ஒரு பாதுகாப்பான பகா எண் என்பதால், கவனிப்பு 1 இன் விளைவான பின்வரும் கூடுதல் உத்தரவாதம் நமக்கு உள்ளது:

கவனிப்பு 2. பாதுகாப்பான பகா எண் P க்கான பெருக்கல் குழு ℤ/Pℤ இன் உறுப்பினராக x இருக்கட்டும், மேலும் 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 ஐ பின்வரும் முடிவைப் பயன்படுத்தி தேர்ந்தெடுக்கலாம்:

கவனிப்பு 3. P ஒரு பகா எண்ணாக இருக்கட்டும்; ℤ/Pℤ இல் உள்ள அனைத்து a மற்றும் b க்கும் பின்வருமாறு இருந்தால் மட்டுமே w மற்றும் P-1 ஆகியவை சார்புப் பகா எண்களாக (relatively prime) இருக்கும்:

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)
அனைத்தையும் காட்டு
நகலெடு