డాగర్-హాషిమోటో

ఇథిరియం మైనింగ్ అల్గారిథమ్ కోసం డాగర్-హాషిమోటో అసలైన పరిశోధన అమలు మరియు నిర్దేశం. డాగర్-హాషిమోటోను Ethash అధిగమించింది. సెప్టెంబర్ 15, 2022న ది మెర్జ్ వద్ద మైనింగ్ పూర్తిగా నిలిపివేయబడింది. అప్పటి నుండి, ఇథిరియం బదులుగా ప్రూఫ్-ఆఫ్-స్టేక్ పద్ధతిని ఉపయోగించి సురక్షితం చేయబడింది. ఈ పేజీ చారిత్రక ఆసక్తి కోసం మాత్రమే - ఇక్కడ ఉన్న సమాచారం విలీనం తర్వాత ఇథిరియం కోసం ఇకపై సంబంధితమైనది కాదు.

అవసరాలు

ఈ పేజీని బాగా అర్థం చేసుకోవడానికి, ముందుగా మీరు ప్రూఫ్-ఆఫ్-వర్క్ ఏకాభిప్రాయం, మైనింగ్, మరియు మైనింగ్ అల్గారిథమ్స్ గురించి చదవాలని మేము సిఫార్సు చేస్తున్నాము.

డాగర్-హాషిమోటో

డాగర్-హాషిమోటో రెండు లక్ష్యాలను సాధించడం లక్ష్యంగా పెట్టుకుంది:

1. ASIC-నిరోధకత: అల్గారిథమ్ కోసం ప్రత్యేక హార్డ్‌వేర్‌ను సృష్టించడం వల్ల ప్రయోజనం వీలైనంత తక్కువగా ఉండాలి
2. లైట్ క్లయింట్ ధృవీకరణ: ఒక బ్లాక్‌ను లైట్ క్లయింట్ ద్వారా సమర్థవంతంగా ధృవీకరించగలగాలి.

అదనపు మార్పుతో, మేము కోరుకుంటే మూడవ లక్ష్యాన్ని ఎలా నెరవేర్చాలో కూడా నిర్దేశిస్తాము, కానీ అదనపు సంక్లిష్టత ఖర్చుతో:

పూర్తి చైన్ నిల్వ: మైనింగ్‌కు పూర్తి బ్లాక్‌చెయిన్ స్థితిని నిల్వ చేయడం అవసరం (ఇథిరియం స్టేట్ ట్రై యొక్క క్రమరహిత నిర్మాణం కారణంగా, కొన్ని తరచుగా ఉపయోగించే ఒప్పందాలను కత్తిరించడం సాధ్యమవుతుందని మేము ఊహిస్తున్నాము, కానీ మేము దీనిని కనిష్టంగా ఉంచాలనుకుంటున్నాము).

DAG ఉత్పత్తి

అల్గారిథమ్ కోసం కోడ్ క్రింద పైథాన్‌లో నిర్వచించబడుతుంది. మొదట, మేము నిర్దిష్ట ఖచ్చితత్వంతో సంతకం చేయని పూర్ణాంకాలను స్ట్రింగ్‌లకు మార్షలింగ్ చేయడానికి encode_int ఇస్తాము. దాని విలోమం కూడా ఇవ్వబడింది:

1NUM_BITS = 512
2
3def encode_int(x):
4    "ఒక పూర్ణాంకం xను బిగ్-ఎండియన్ స్కీమ్‌ను ఉపయోగించి 64 అక్షరాల స్ట్రింగ్‌గా ఎన్‌కోడ్ చేయండి"
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    "బిగ్-ఎండియన్ స్కీమ్‌ను ఉపయోగించి ఒక స్ట్రింగ్ నుండి పూర్ణాంకం xను అన్‌కోడ్ చేయండి"
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,  # డేటాసెట్ పరిమాణం (4 గిగాబైట్లు); 65536 యొక్క గుణకం అయి ఉండాలి
5      "n_inc": 65536,                   # ప్రతి కాలానికి n విలువలో పెరుగుదల; 65536 యొక్క గుణకం అయి ఉండాలి
6                                        # epochtime=20000తో సంవత్సరానికి 882 MB పెరుగుదల
7      "cache_size": 2500,               # లైట్ క్లయింట్ కాష్ పరిమాణం (లైట్ క్లయింట్ ద్వారా ఎంచుకోవచ్చు; అల్గో స్పెసిఫికేషన్‌లో భాగం కాదు)
8      "diff": 2**14,                    # క్లిష్టత (బ్లాక్ మూల్యాంకన సమయంలో సర్దుబాటు చేయబడుతుంది)
9      "epochtime": 100000,              # బ్లాకులలో ఒక యుగం యొక్క పొడవు (డేటాసెట్ ఎంత తరచుగా నవీకరించబడుతుంది)
10      "k": 1,                           # ఒక నోడ్ యొక్క తల్లిదండ్రుల సంఖ్య
11      "w": w,                           # మాడ్యులర్ ఘాతాంక హాషింగ్ కోసం ఉపయోగించబడుతుంది
12      "accesses": 200,                  # హాషిమోటో సమయంలో డేటాసెట్ యాక్సెస్‌ల సంఖ్య
13      "P": SAFE_PRIME_512               # హాషింగ్ మరియు యాదృచ్ఛిక సంఖ్య ఉత్పత్తి కోసం సురక్షిత ప్రైమ్
14}
అన్నీ చూపించుకాపీ

ఈ సందర్భంలో P అనేది log₂(P) 512 కంటే కొంచెం తక్కువగా ఉండేలా ఎంచుకున్న ఒక ప్రైమ్, ఇది మన సంఖ్యలను సూచించడానికి మనం ఉపయోగిస్తున్న 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) అనే ఒకే నోడ్‌గా గ్రాఫ్‌ను ప్రారంభించి, అక్కడి నుండి యాదృచ్ఛిక మునుపటి నోడ్‌ల ఆధారంగా ఇతర నోడ్‌లను క్రమంగా జోడించడం ప్రారంభిస్తుంది. కొత్త నోడ్ సృష్టించబడినప్పుడు, i కంటే తక్కువ కొన్ని సూచికలను (పైన ఉన్న x % i ఉపయోగించి) యాదృచ్ఛికంగా ఎంచుకోవడానికి సీడ్ యొక్క మాడ్యులర్ పవర్ లెక్కించబడుతుంది, మరియు ఆ సూచికల వద్ద ఉన్న నోడ్‌ల విలువలు x కోసం కొత్త విలువను ఉత్పత్తి చేయడానికి ఒక గణనలో ఉపయోగించబడతాయి, ఇది చివరికి i సూచిక వద్ద గ్రాఫ్ విలువను ఉత్పత్తి చేయడానికి ఒక చిన్న ప్రూఫ్ ఆఫ్ వర్క్ ఫంక్షన్‌లోకి (XOR ఆధారంగా) ఇవ్వబడుతుంది. ఈ ప్రత్యేక రూపకల్పన వెనుక ఉన్న కారణం 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ల డబుల్ బఫర్

పూర్తి క్లయింట్‌లో, పైన ఉన్న ఫార్ములా ద్వారా ఉత్పత్తి చేయబడిన 2 DAGల డబుల్ బఫర్ (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        # 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 ను ప్రదర్శించడం మరియు ఫలితం యొక్క హాష్‌ను తిరిగి ఇవ్వడం. తడ్డియస్ డ్రైజా యొక్క అసలు అల్గారిథం, స్థిరత్వం కోసం పైథాన్‌లోకి అనువదించబడింది, ఈ క్రింది విధంగా ఉంది:

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-బిట్ అంకగణితంపై ఆధారపడి ఉంటుంది, దీనికి గణనీయమైన కంప్యూటేషనల్ ఓవర్‌హెడ్ ఉంటుంది. అయినప్పటికీ, డాగర్-హాషిమోటో ఈ సమస్యను పరిష్కరించడానికి దాని డేటాసెట్‌ను ఇండెక్స్ చేసేటప్పుడు అతి తక్కువ ముఖ్యమైన 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
కాపీ

అలాగే, డాగర్-హాషిమోటో బ్లాక్ హెడర్‌పై అదనపు అవసరాలను విధిస్తుందని గమనించండి:

• రెండు-పొరల ధృవీకరణ పని చేయడానికి, ఒక బ్లాక్ హెడర్‌లో నాన్స్ మరియు మధ్య విలువ రెండూ ప్రీ-sha3 కలిగి ఉండాలి
• ఎక్కడో, ఒక బ్లాక్ హెడర్ ప్రస్తుత సీడ్‌సెట్ యొక్క sha3ను నిల్వ చేయాలి

మరింత సమాచారం

మీకు సహాయపడిన కమ్యూనిటీ వనరు గురించి తెలుసా? ఈ పేజీని సవరించి, దాన్ని జోడించండి!

అనుబంధం

పైన చెప్పినట్లుగా, DAG ఉత్పత్తికి ఉపయోగించే RNG సంఖ్యా సిద్ధాంతం నుండి కొన్ని ఫలితాలపై ఆధారపడి ఉంటుంది. మొదట, picker వేరియబుల్ ఆధారంగా ఉన్న లెహ్మర్ RNGకి విస్తృత కాలం ఉందని మేము హామీ ఇస్తున్నాము. రెండవది, 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 కూడా ప్రైమ్ అయ్యేలా నిర్వచించబడింది. గుణకార సమూహం (opens in a new tab) ℤ/nℤ లోని ఒక సభ్యుడు x యొక్క ఆర్డర్ అనేది కనీస m గా నిర్వచించబడింది, దీని ప్రకారం

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] ప్రకారం x యొక్క ఆర్డర్ 1, 2, (P-1)/2, లేదా P-1 అని మనకు తెలుసు.

x యొక్క ఆర్డర్ 1 కాలేదు, ఎందుకంటే ఫెర్మాట్ యొక్క చిన్న సిద్ధాంతం ప్రకారం మనకు ఇది ఉంది:

xP-1 mod P ≡ 1

అందువల్ల x అనేది ℤ/nℤ యొక్క గుణకార గుర్తింపు అయి ఉండాలి, ఇది ప్రత్యేకమైనది. మేము ఊహించినట్లుగా x ≠ 1 కాబట్టి, ఇది సాధ్యం కాదు.

x = P-1 అయితే తప్ప, x యొక్క ఆర్డర్ 2 కాలేదు, ఎందుకంటే ఇది 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. సురక్షిత ప్రైమ్ 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) ఫంక్షన్‌కు అనేక ఘర్షణలు ఉండవచ్చు. ఉదాహరణకు, pow(x,9,19) కేవలం {1,18} విలువలను మాత్రమే తీసుకుంటుంది.

P ప్రైమ్ అని ఇవ్వబడినప్పుడు, ఒక మాడ్యులర్ ఘాతాంక హాషింగ్ ఫంక్షన్ కోసం సరైన w ను ఈ క్రింది ఫలితాన్ని ఉపయోగించి ఎంచుకోవచ్చు:

పరిశీలన 3. P ఒక ప్రైమ్ అనుకుందాం; ℤ/Pℤ లోని అన్ని a మరియు b లకు w మరియు P-1 సాపేక్షంగా ప్రైమ్ అయితే మరియు అయితేనే:

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)
అన్నీ చూపించుకాపీ