Dagger-Hashimoto
Lần cập nhật trang lần cuối: 11 tháng 4, 2024
Dagger-Hashimoto là bản triển khai nghiên cứu và đặc tả ban đầu cho thuật toán khai thác của Ethereum. Dagger-Hashimoto đã được thay thế bằng Ethash. Hoạt động khai thác đã bị tắt hoàn toàn tại The Merge vào ngày 15 tháng 9 năm 2022. Kể từ đó, Ethereum đã được bảo mật bằng cơ chế bằng chứng cổ phần. Trang này mang tính chất lịch sử - thông tin ở đây không còn phù hợp với Ethereum sau The Merge.
Điều kiện tiên quyết
Để hiểu rõ hơn về trang này, chúng tôi khuyên bạn nên đọc trước về sự đồng thuận bằng chứng công việc, khai thác và các thuật toán khai thác.
Dagger-Hashimoto
Dagger-Hashimoto nhằm đáp ứng hai mục tiêu:
- Kháng ASIC: lợi ích từ việc tạo ra phần cứng chuyên dụng cho thuật toán phải nhỏ nhất có thể
- Khả năng xác minh của ứng dụng nhẹ: một khối phải có thể được xác minh hiệu quả bởi một ứng dụng nhẹ.
Với một sửa đổi bổ sung, chúng tôi cũng chỉ định cách thực hiện mục tiêu thứ ba nếu muốn, nhưng phải trả giá bằng sự phức tạp tăng thêm:
Lưu trữ toàn bộ chuỗi: việc khai thác phải yêu cầu lưu trữ toàn bộ trạng thái chuỗi khối (do cấu trúc bất thường của cây trạng thái Ethereum, chúng tôi dự đoán rằng có thể thực hiện một số cắt tỉa, đặc biệt là đối với một số hợp đồng thường được sử dụng, nhưng chúng tôi muốn giảm thiểu điều này).
Tạo DAG
Mã cho thuật toán sẽ được định nghĩa bằng Python bên dưới. Đầu tiên, chúng tôi cung cấp encode_int để sắp xếp các số nguyên không dấu có độ chính xác cụ thể thành các chuỗi. Nghịch đảo của nó cũng được đưa ra:
1NUM_BITS = 51223def encode_int(x):4 "Mã hóa một số nguyên x thành một chuỗi gồm 64 ký tự bằng cách sử dụng lược đồ big-endian"5 o = ''6 for _ in range(NUM_BITS / 8):7 o = chr(x % 256) + o8 x //= 2569 return o1011def decode_int(s):12 "Giải mã một số nguyên x từ một chuỗi bằng cách sử dụng lược đồ big-endian"13 x = 014 for c in s:15 x *= 25616 x += ord(c)17 return xHiện tất cảTiếp theo, chúng tôi giả định rằng sha3 là một hàm nhận một số nguyên và xuất ra một số nguyên, và dbl_sha3 là một hàm double-sha3; nếu chuyển đổi mã tham chiếu này thành một bản triển khai, hãy sử dụng:
1from pyethereum import utils2def sha3(x):3 if isinstance(x, (int, long)):4 x = encode_int(x)5 return decode_int(utils.sha3(x))67def dbl_sha3(x):8 if isinstance(x, (int, long)):9 x = encode_int(x)10 return decode_int(utils.sha3(utils.sha3(x)))Hiện tất cảCác tham số
Các tham số được sử dụng cho thuật toán là:
1SAFE_PRIME_512 = 2**512 - 38117 # Số nguyên tố an toàn lớn nhất nhỏ hơn 2**51223params = {4 "n": 4000055296 * 8 // NUM_BITS, # Kích thước của bộ dữ liệu (4 Gigabyte); PHẢI LÀ BỘI SỐ CỦA 655365 "n_inc": 65536, # Gia số trong giá trị của n mỗi kỳ; PHẢI LÀ BỘI SỐ CỦA 655366 # với epochtime=20000 cho tốc độ tăng trưởng 882 MB mỗi năm7 "cache_size": 2500, # Kích thước bộ nhớ đệm của ứng dụng nhẹ (có thể được chọn bởi ứng dụng nhẹ8 # ; không thuộc đặc tả của thuật toán)9 "diff": 2**14, # Độ khó (được điều chỉnh trong quá trình đánh giá khối)10 "epochtime": 100000, # Độ dài của một epoch trong các khối (tần suất bộ dữ liệu được cập nhật)11 "k": 1, # Số lượng nút mẹ của một nút12 "w": w, # Được sử dụng để băm lũy thừa theo mô-đun13 "accesses": 200, # Số lần truy cập bộ dữ liệu trong quá trình hashimoto14 "P": SAFE_PRIME_512 # Số nguyên tố an toàn để băm và tạo số ngẫu nhiên15}Hiện tất cảP trong trường hợp này là một số nguyên tố được chọn sao cho log₂(P) nhỏ hơn 512 một chút, tương ứng với 512 bit mà chúng ta đã sử dụng để biểu diễn các con số của mình. Lưu ý rằng chỉ có nửa sau của DAG thực sự cần được lưu trữ, vì vậy yêu cầu RAM trên thực tế bắt đầu ở mức 1 GB và tăng 441 MB mỗi năm.
Xây dựng đồ thị Dagger
Nguyên hàm xây dựng đồ thị dagger được định nghĩa như sau:
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) % P7 for _ in range(params["k"]):8 x ^= o[x % i]9 o.append(pow(x, params["w"], P))10 return oHiện tất cảVề cơ bản, nó bắt đầu một đồ thị dưới dạng một nút duy nhất, sha3(seed), và từ đó bắt đầu tuần tự thêm các nút khác dựa trên các nút ngẫu nhiên trước đó. Khi một nút mới được tạo, một lũy thừa theo mô-đun của seed được tính toán để chọn ngẫu nhiên một số chỉ số nhỏ hơn i (sử dụng x % i ở trên), và các giá trị của các nút tại các chỉ số đó được sử dụng trong một phép tính để tạo ra một giá trị mới cho x, sau đó được đưa vào một hàm bằng chứng công việc nhỏ (dựa trên XOR) để cuối cùng tạo ra giá trị của đồ thị tại chỉ số i. Lý do đằng sau thiết kế đặc biệt này là để buộc truy cập tuần tự vào DAG; giá trị tiếp theo của DAG sẽ được truy cập không thể được xác định cho đến khi giá trị hiện tại được biết. Cuối cùng, lũy thừa theo mô-đun sẽ băm kết quả sâu hơn nữa.
Thuật toán này dựa trên một số kết quả từ lý thuyết số. Xem phụ lục bên dưới để thảo luận.
Đánh giá ứng dụng nhẹ
Việc xây dựng đồ thị ở trên nhằm mục đích cho phép mỗi nút trong đồ thị được tái tạo bằng cách tính toán một cây con chỉ gồm một số lượng nhỏ các nút và chỉ yêu cầu một lượng nhỏ bộ nhớ phụ. Lưu ý rằng với k=1, cây con chỉ là một chuỗi các giá trị đi lên đến phần tử đầu tiên trong DAG.
Hàm tính toán của ứng dụng nhẹ cho DAG hoạt động như sau:
1def quick_calc(params, seed, p):2 w, P = params["w"], params["P"]3 cache = {}45 def quick_calc_cached(p):6 if p in cache:7 pass8 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]1617 return quick_calc_cached(p)Hiện tất cảVề cơ bản, nó chỉ đơn giản là một bản viết lại của thuật toán trên, loại bỏ vòng lặp tính toán các giá trị cho toàn bộ DAG và thay thế việc tra cứu nút trước đó bằng một lệnh gọi đệ quy hoặc một tra cứu bộ nhớ đệm. Lưu ý rằng đối với k=1, bộ nhớ đệm là không cần thiết, mặc dù một tối ưu hóa sâu hơn thực sự tính toán trước vài nghìn giá trị đầu tiên của DAG và giữ đó làm bộ nhớ đệm tĩnh cho các phép tính; xem phụ lục để biết mã triển khai của việc này.
Bộ đệm kép của các DAG
Trong một ứng dụng đầy đủ, một bộ đệm kép (opens in a new tab) gồm 2 DAG được tạo ra bởi công thức trên được sử dụng. Ý tưởng là các DAG được tạo ra mỗi epochtime khối theo các tham số ở trên. Thay vì ứng dụng sử dụng DAG mới nhất được tạo ra, nó sử dụng DAG trước đó. Lợi ích của việc này là nó cho phép các DAG được thay thế theo thời gian mà không cần phải kết hợp một bước mà các thợ đào phải đột ngột tính toán lại tất cả dữ liệu. Nếu không, có khả năng xử lý chuỗi sẽ bị chậm lại đột ngột và tạm thời ở các khoảng thời gian đều đặn và làm tăng đáng kể sự tập trung hóa. Do đó có rủi ro tấn công 51% trong vòng vài phút trước khi tất cả dữ liệu được tính toán lại.
Thuật toán được sử dụng để tạo tập hợp các DAG được sử dụng để tính toán công việc cho một khối như sau:
1def get_prevhash(n):2 from pyethereum.blocks import GENESIS_PREVHASH3 from pyethereum import chain_manager4 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)910def 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 seedset1718def get_dagsize(params, block):19 return params["n"] + (block.number // params["epochtime"]) * params["n_inc"]2021def get_daggerset(params, block):22 dagsz = get_dagsize(params, block)23 seedset = get_seedset(params, block)24 if seedset["front_hash"] <= 0:25 # Không thể có bộ đệm sau, chỉ cần tạo bộ đệm trước26 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"]}}Hiện tất cảHashimoto
Ý tưởng đằng sau Hashimoto ban đầu là sử dụng chuỗi khối làm bộ dữ liệu, thực hiện một phép tính chọn N chỉ số từ chuỗi khối, thu thập các giao dịch tại các chỉ số đó, thực hiện phép XOR dữ liệu này và trả về giá trị băm của kết quả. Thuật toán ban đầu của Thaddeus Dryja, được dịch sang Python để đảm bảo tính nhất quán, như sau:
1def orig_hashimoto(prev_hash, merkle_root, list_of_transactions, nonce):2 hash_output_A = sha256(prev_hash + merkle_root + nonce)3 txid_mix = 04 for i in range(64):5 shifted_A = hash_output_A >> i6 transaction = shifted_A % len(list_of_transactions)7 txid_mix ^= list_of_transactions[transaction] << i8 return txid_mix ^ (nonce << 192)Thật không may, mặc dù Hashimoto được coi là khó về RAM, nó lại dựa vào số học 256-bit, vốn có chi phí tính toán đáng kể. Tuy nhiên, Dagger-Hashimoto chỉ sử dụng 64 bit có trọng số thấp nhất khi lập chỉ mục cho bộ dữ liệu của mình để giải quyết vấn đề này.
1def hashimoto(dag, dagsize, params, header, nonce):2 m = dagsize / 23 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)Việc sử dụng double SHA3 cho phép một hình thức xác minh trước gần như tức thời, không có dữ liệu, chỉ xác minh rằng một giá trị trung gian chính xác đã được cung cấp. Lớp bằng chứng công việc bên ngoài này rất thân thiện với ASIC và khá yếu, nhưng tồn tại để làm cho việc tấn công DDoS trở nên khó khăn hơn vì một lượng nhỏ công việc đó phải được thực hiện để tạo ra một khối sẽ không bị từ chối ngay lập tức. Đây là phiên bản ứng dụng nhẹ:
1def quick_hashimoto(seed, dagsize, params, header, nonce):2 m = dagsize // 23 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)Khai thác và xác minh
Bây giờ, chúng ta hãy kết hợp tất cả lại thành thuật toán khai thác:
1def mine(daggerset, params, block):2 from random import randint3 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 break9 nonce += 110 if nonce >= 2**64:11 nonce = 012 return nonceHiện tất cảĐây là thuật toán xác minh:
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**256Xác minh thân thiện với ứng dụng nhẹ:
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**256Ngoài ra, lưu ý rằng Dagger-Hashimoto áp đặt các yêu cầu bổ sung đối với tiêu đề khối:
- Để xác minh hai lớp hoạt động, tiêu đề khối phải có cả nonce và giá trị trung gian trước khi qua sha3
- Ở đâu đó, tiêu đề khối phải lưu trữ sha3 của seedset hiện tại
Đọc thêm
Biết về nguồn lực cộng đồng đã giúp đỡ bạn? Chỉnh sửa trang này và bổ sung!
Phụ lục
Như đã lưu ý ở trên, RNG được sử dụng để tạo DAG dựa trên một số kết quả từ lý thuyết số. Đầu tiên, chúng tôi đảm bảo rằng Lehmer RNG, là cơ sở cho biến picker, có một chu kỳ dài. Thứ hai, chúng tôi chỉ ra rằng pow(x,3,P) sẽ không ánh xạ x tới 1 hoặc P-1 với điều kiện x ∈ [2,P-2] ban đầu. Cuối cùng, chúng tôi chỉ ra rằng pow(x,3,P) có tỷ lệ xung đột thấp khi được coi là một hàm băm.
Trình tạo số ngẫu nhiên Lehmer
Mặc dù hàm produce_dag không cần tạo ra các số ngẫu nhiên không thiên vị, một mối đe dọa tiềm tàng là seed**i % P chỉ nhận một vài giá trị. Điều này có thể mang lại lợi thế cho những thợ đào nhận ra quy luật so với những người không nhận ra.
Để tránh điều này, một kết quả từ lý thuyết số được sử dụng. Một Số nguyên tố an toàn (opens in a new tab) được định nghĩa là một số nguyên tố P sao cho (P-1)/2 cũng là một số nguyên tố. Bậc của một thành viên x của nhóm nhân (opens in a new tab) ℤ/nℤ được định nghĩa là m nhỏ nhất sao cho
xᵐ mod P ≡ 1Với các định nghĩa này, chúng ta có:
Quan sát 1. Cho
xlà một thành viên của nhóm nhânℤ/Pℤđối với một số nguyên tố an toànP. Nếux mod P ≠ 1 mod Pvàx mod P ≠ P-1 mod P, thì bậc củaxlàP-1hoặc(P-1)/2.
Bằng chứng. Vì P là một số nguyên tố an toàn, nên theo [Định lý Lagrange][lagrange], chúng ta có bậc của x là 1, 2, (P-1)/2 hoặc P-1.
Bậc của x không thể là 1, vì theo Định lý nhỏ Fermat, chúng ta có:
xP-1 mod P ≡ 1
Do đó, x phải là một phần tử đơn vị nhân của ℤ/nℤ, là duy nhất. Vì chúng ta đã giả định rằng x ≠ 1, điều này là không thể.
Bậc của x không thể là 2 trừ khi x = P-1, vì điều này sẽ vi phạm tính nguyên tố của P.
Từ mệnh đề trên, chúng ta có thể nhận ra rằng việc lặp (picker * init) % P sẽ có độ dài chu kỳ ít nhất là (P-1)/2. Điều này là do chúng tôi đã chọn P là một số nguyên tố an toàn xấp xỉ bằng một lũy thừa cao hơn của hai, và init nằm trong khoảng [2,2**256+1]. Với độ lớn của P, chúng ta không bao giờ nên mong đợi một chu kỳ từ phép lũy thừa theo mô-đun.
Khi chúng ta gán ô đầu tiên trong DAG (biến có nhãn init), chúng ta tính toán pow(sha3(seed) + 2, 3, P). Thoạt nhìn, điều này không đảm bảo rằng kết quả không phải là 1 cũng không phải là P-1. Tuy nhiên, vì P-1 là một số nguyên tố an toàn, chúng tôi có thêm sự đảm bảo sau đây, là hệ quả của Quan sát 1:
Quan sát 2. Cho
xlà một thành viên của nhóm nhânℤ/Pℤđối với một số nguyên tố an toànP, và chowlà một số tự nhiên. Nếux mod P ≠ 1 mod Pvàx mod P ≠ P-1 mod P, cũng nhưw mod P ≠ P-1 mod Pvàw mod P ≠ 0 mod P, thìxʷ mod P ≠ 1 mod Pvàxʷ mod P ≠ P-1 mod P
Lũy thừa theo mô-đun như một hàm băm
Đối với các giá trị nhất định của P và w, hàm pow(x, w, P) có thể có nhiều xung đột. Ví dụ, pow(x,9,19) chỉ nhận các giá trị {1,18}.
Với P là số nguyên tố, thì w thích hợp cho một hàm băm lũy thừa theo mô-đun có thể được chọn bằng cách sử dụng kết quả sau:
Quan sát 3. Cho
Plà một số nguyên tố;wvàP-1là nguyên tố cùng nhau khi và chỉ khi với mọiavàbtrongℤ/Pℤ:aʷ mod P ≡ bʷ mod Pkhi và chỉ khia mod P ≡ b mod P
Do đó, với P là số nguyên tố và w là nguyên tố cùng nhau với P-1, chúng ta có |{pow(x, w, P) : x ∈ ℤ}| = P, ngụ ý rằng hàm băm có tỷ lệ xung đột nhỏ nhất có thể.
Trong trường hợp đặc biệt mà P là một số nguyên tố an toàn như chúng ta đã chọn, thì P-1 chỉ có các ước số là 1, 2, (P-1)/2 và P-1. Vì P > 7, chúng ta biết rằng 3 là nguyên tố cùng nhau với P-1, do đó w=3 thỏa mãn mệnh đề trên.
Thuật toán đánh giá dựa trên bộ nhớ đệm hiệu quả hơn
1def quick_calc(params, seed, p):2 cache = produce_dag(params, seed, params["cache_size"])3 return quick_calc_cached(cache, params, p)45def 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)1415def 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)1819def quick_hashimoto_cached(cache, dagsize, params, header, nonce):20 m = dagsize // 221 mask = 2**64 - 122 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)Hiện tất cả