相信大家都清楚的知道以太坊是什么，但是并不知道內(nèi)部使用的算法，今天就來(lái)介紹一下以太坊所以用的算法，Ethash

Ethash 是 Ethereum 1.0 的計(jì)劃的PoW算法。這是最新版本的Dagger-Hashimoto, 雖然它不能再恰當(dāng)?shù)乇环Q(chēng)為Dagger-Hashimoto,

因?yàn)檫@兩種算法的許多原始特性已經(jīng)在上個(gè)月的研究和開(kāi)發(fā)中發(fā)生了翻天覆地的變化。

請(qǐng)參見(jiàn) https://github.com/ethereum/wiki/blob/master/Dagger-Hashimoto.md 的原始版本。

該算法所采用的一般流程如下所示:

1. 存在一個(gè)種子, 可以通過(guò)塊高度直到該點(diǎn)來(lái)計(jì)算每個(gè)塊。

2. 從種子, 你可以計(jì)算一個(gè) 16 MB 的偽隨機(jī)緩存, 用于輕客戶(hù)端存儲(chǔ)緩存。

2. 從緩存中, 我們可以生成一個(gè) 1 GB 的數(shù)據(jù)集, 該屬性表示數(shù)據(jù)集中的每個(gè)項(xiàng)只依賴(lài)于緩存中的少量項(xiàng)。完整的客戶(hù)和礦工存儲(chǔ)這個(gè)數(shù)據(jù)集。數(shù)據(jù)集會(huì)隨時(shí)間線(xiàn)性增長(zhǎng)。

挖礦涉及抓取數(shù)據(jù)集的隨機(jī)切片并將它們一起哈希?？梢酝ㄟ^(guò)使用緩存來(lái)重新生成所需的數(shù)據(jù)集的特定部分, 從而低內(nèi)存的機(jī)器可以進(jìn)行驗(yàn)證, 因?yàn)橹恍璐鎯?chǔ)緩存即可驗(yàn)證。

完整的大數(shù)據(jù)集每隔30000塊更新一次, 因此大多數(shù)礦工的工作將是讀取數(shù)據(jù)集, 而不是對(duì)其進(jìn)行更改。

有關(guān)此算法的設(shè)計(jì)基本原理注意事項(xiàng), 請(qǐng)參見(jiàn) https://github.com/ethereum/wiki/wiki/Ethash-Design-Rationale。

算法使用python來(lái)字義和描述, 幾個(gè)重要的庫(kù)函數(shù)要查清文檔，別望文生義, 如:

1.map是遍歷數(shù)組的作為參數(shù)去調(diào)用函數(shù)，得到一個(gè)新的數(shù)組.

2. **這個(gè)指數(shù)運(yùn)算符等,

3. //是整除

4. [::-1]是大小

5. RLP是一個(gè)編碼算法，請(qǐng)另外查閱和理解

...

***全局常量定義

我們使用以下定義:

WORD_BYTES = 4? ? ? ? ? ? ? ? ? ? # 一個(gè)字的字節(jié)數(shù)

DATASET_BYTES_INIT = 2**30? ? ? ? # 創(chuàng)世塊的字節(jié)數(shù)

DATASET_BYTES_GROWTH = 2**23? ? ? # 每個(gè)紀(jì)元(30000塊一次)的數(shù)據(jù)集增長(zhǎng)字節(jié)數(shù)

CACHE_BYTES_INIT = 2**24? ? ? ? ? # 創(chuàng)世塊的緩沖字節(jié)數(shù)

CACHE_BYTES_GROWTH = 2**17? ? ? ? # 每個(gè)紀(jì)元(30000塊一次)的緩沖增長(zhǎng)字節(jié)數(shù)

CACHE_MULTIPLIER=1024? ? ? ? ? ? # 相對(duì)于DAG緩存的大小

EPOCH_LENGTH = 30000? ? ? ? ? ? ? # 每個(gè)紀(jì)元的塊數(shù)

MIX_BYTES = 128? ? ? ? ? ? ? ? ? # 混合體的字節(jié)數(shù)

HASH_BYTES = 64? ? ? ? ? ? ? ? ? # 哈希的字節(jié)數(shù)

DATASET_PARENTS = 256? ? ? ? ? ? # 每個(gè)數(shù)據(jù)集元素的父級(jí)數(shù)

CACHE_ROUNDS = 3? ? ? ? ? ? ? ? ? # 緩存生產(chǎn)中的回合數(shù)

ACCESSES = 64? ? ? ? ? ? ? ? ? ? # hashimoto循環(huán)的訪(fǎng)問(wèn)次數(shù)

有關(guān)本規(guī)范中描述的 "SHA3" 哈希的說(shuō)明

Ethereum 的發(fā)展恰逢 SHA3 標(biāo)準(zhǔn)的發(fā)展, 標(biāo)準(zhǔn)過(guò)程在最終的哈希算法的填充上做了后期的更改, 因此 Ethereum 的 "sha3_256" 和 "sha3_512" 哈希不是標(biāo)準(zhǔn)的 sha3 哈希, 而是一個(gè)變體在其他語(yǔ)境中經(jīng)常被稱(chēng)為 "Keccak-256" 和 "Keccak-512"。

請(qǐng)記住,? 這個(gè)算法仍然當(dāng)做 "sha3" 哈希在下面的算法描述中被引用。

***參數(shù)

Ethash 的緩存和數(shù)據(jù)集的參數(shù)取決于塊號(hào)。

高速緩存大小和數(shù)據(jù)集大小均呈線(xiàn)性增長(zhǎng)。

然而, 我們總是把最高的素?cái)?shù)放在線(xiàn)性增長(zhǎng)的閾值之下, 以減少偶然的規(guī)律性,從而導(dǎo)致循環(huán)行為的風(fēng)險(xiǎn)。

isprime來(lái)定義這個(gè)是不是素?cái)?shù)，請(qǐng)看附錄。

#根據(jù)給出的塊號(hào), 計(jì)算cache的大小， 如果大小除法HASH_BYTES不是符合定義的素?cái)?shù), 會(huì)一直減少這個(gè)直至這個(gè)大小是符合定義的素?cái)?shù)

def get_cache_size(block_number):

? ? sz = CACHE_BYTES_INIT + CACHE_BYTES_GROWTH * (block_number // EPOCH_LENGTH)

? ? sz -= HASH_BYTES

? ? while not isprime(sz / HASH_BYTES):

? ? ? ? sz -= 2 * HASH_BYTES

? ? return sz

#根據(jù)給出的塊號(hào), 計(jì)算DAG的完整大小， 如果大小除以MIX_BYTES不是符合定義的素?cái)?shù), 會(huì)一直減少這個(gè)直至這個(gè)大小是符合定義的素?cái)?shù)

def get_full_size(block_number):

? ? sz = DATASET_BYTES_INIT + DATASET_BYTES_GROWTH * (block_number // EPOCH_LENGTH)

? ? sz -= MIX_BYTES

? ? while not isprime(sz / MIX_BYTES):

? ? ? ? sz -= 2 * MIX_BYTES

? ? return sz

附錄中提供了數(shù)據(jù)集和緩存大小值的表。

***緩存生成

下面是現(xiàn)在我們指定用于生成緩存的函數(shù):

def mkcache(cache_size, seed):

? ? n = cache_size // HASH_BYTES

? ? # Sequentially produce the initial dataset

? ? o = [sha3_512(seed)]

? ? for i in range(1, n):

? ? ? ? o.append(sha3_512(o[-1]))

? ? # Use a low-round version of randmemohash

? ? for _ in range(CACHE_ROUNDS):

? ? ? ? for i in range(n):

? ? ? ? ? ? v = o[i][0] % n

? ? ? ? ? ? o[i] = sha3_512(map(xor, o[(i-1+n) % n], o[v]))

? ? return o

緩存生產(chǎn)過(guò)程首先需要依次填充 32 MB 內(nèi)存, 然后從嚴(yán)格的內(nèi)存難度型哈希函數(shù) (2014) 執(zhí)行兩次Sergio Demian Lerner的 RandMemoHash 算法。

輸出是一組 524288 個(gè)64 字節(jié)的值。

***數(shù)據(jù)聚合函數(shù)

在某些情況下, 我們使用由 FNV hash算法作為 XOR 的關(guān)聯(lián)替換。請(qǐng)注意, 我們將素?cái)?shù)與完整的32位輸入相乘, 與 FNV-1 規(guī)范相比, 它反過(guò)來(lái)將素?cái)?shù)與一個(gè)字節(jié) (八進(jìn)制) 相乘。

FNV_PRIME = 0x01000193

def fnv(v1, v2):

? ? return ((v1 * FNV_PRIME) ^ v2) % 2**32

請(qǐng)注意, 即使是黃皮書(shū)指定FNV 為 v1 * (FNV_PRIME ^ v2), 但所有當(dāng)前的實(shí)現(xiàn)始終使用上述定義。

***完整數(shù)據(jù)集計(jì)算

完整的 1 GB 數(shù)據(jù)集中的每個(gè)64字節(jié)項(xiàng)都按如下方式計(jì)算:

def calc_dataset_item(cache, i):

? ? n = len(cache)

? ? r = HASH_BYTES // WORD_BYTES

? ? # initialize the mix

? ? mix = copy.copy(cache[i % n])

? ? mix[0] ^= i

? ? mix = sha3_512(mix)

? ? # fnv it with a lot of random cache nodes based on i

? ? for j in range(DATASET_PARENTS):

? ? ? ? cache_index = fnv(i ^ j, mix[j % r])

? ? ? ? mix = map(fnv, mix, cache[cache_index % n])

? ? return sha3_512(mix)

實(shí)質(zhì)上, 我們將來(lái)自 256個(gè)偽隨機(jī)的選定緩存節(jié)點(diǎn)的數(shù)據(jù)和哈希值合并到一起以計(jì)算 數(shù)據(jù)集的 節(jié)點(diǎn)。然后生成整個(gè)數(shù)據(jù)集，算法如下:

def calc_dataset(full_size, cache):

? ? return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]

***主循環(huán)

現(xiàn)在, 我們說(shuō)明類(lèi)"hashimoto"的循環(huán), 在這里我們從完整的數(shù)據(jù)集收集資料, 以便為特定的Header和nonce生成我們的最終值。

在下面的代碼中, header表示截取過(guò)的塊頭部(即不包括 mixHash字段 和nonce的頭部)使用RLP 表示的 SHA3-256 哈希。

nonce是一個(gè)64位無(wú)符號(hào)整數(shù)的八個(gè)字節(jié)。因此, [:-1] 是該值的八字節(jié)小字節(jié)表示:

def hashimoto(header, nonce, full_size, dataset_lookup):

? ? n = full_size / HASH_BYTES

? ? w = MIX_BYTES // WORD_BYTES

? ? mixhashes = MIX_BYTES / HASH_BYTES

? ? # combine header+nonce into a 64 byte seed

? ? s = sha3_512(header + nonce[::-1])

? ? # start the mix with replicated s

? ? mix = []

? ? for _ in range(MIX_BYTES / HASH_BYTES):

? ? ? ? mix.extend(s)

? ? # mix in random dataset nodes

? ? for i in range(ACCESSES):

? ? ? ? p = fnv(i ^ s[0], mix[i % w]) % (n // mixhashes) * mixhashes

? ? ? ? newdata = []

? ? ? ? for j in range(MIX_BYTES / HASH_BYTES):

? ? ? ? ? ? newdata.extend(dataset_lookup(p + j))

? ? ? ? mix = map(fnv, mix, newdata)

? ? # compress mix

? ? cmix = []

? ? for i in range(0, len(mix), 4):

? ? ? ? cmix.append(fnv(fnv(fnv(mix[i], mix[i+1]), mix[i+2]), mix[i+3]))

? ? return {

? ? ? ? "mix digest": serialize_hash(cmix),

? ? ? ? "result": serialize_hash(sha3_256(s+cmix))

? ? }

def hashimoto_light(full_size, cache, header, nonce):

? ? return hashimoto(header, nonce, full_size, lambda x: calc_dataset_item(cache, x))

def hashimoto_full(full_size, dataset, header, nonce):

? ? return hashimoto(header, nonce, full_size, lambda x: dataset[x])

本質(zhì)上, 我們保持一個(gè) "混合體" 128 字節(jié)寬, 并重復(fù)地從完整的數(shù)據(jù)集中獲取128個(gè)字節(jié), 并使用FNV函數(shù)將它與"混合體" 組合在一起。

128字節(jié)順序訪(fǎng)問(wèn)的方法, 可以使每一個(gè)回合的算法總是從 RAM 中提取一個(gè)完整的頁(yè)面, 這樣可以最小化TLB的命中失敗次數(shù), 這個(gè)主要是為防ASIC。

如果該算法的輸出小于目標(biāo)值, 則nonce就是正確的解。

解釋一下TLB:? Translation Lookaside Buffer. 根據(jù)功能可以譯為快表，直譯可以翻譯為旁路轉(zhuǎn)換緩沖，也可以把它理解成頁(yè)表緩沖。里面存放的是一些頁(yè)表文件（虛擬地址到物理地址的轉(zhuǎn)換表）。當(dāng)處理器要在主內(nèi)存尋址時(shí)，不是直接在內(nèi)存的物理地址里查找的，而是通過(guò)一組虛擬地址轉(zhuǎn)換到主內(nèi)存的物理地址，TLB就是負(fù)責(zé)將虛擬內(nèi)存地址翻譯成實(shí)際的物理內(nèi)存地址，而CPU尋址時(shí)會(huì)優(yōu)先在TLB中進(jìn)行尋址。處理器的性能就和尋址的命中率有很大的關(guān)系。

ASIC在理論上是有能力做到避免TLB的命中失敗次數(shù)的, 但這樣做了ASIC就沒(méi)有優(yōu)勢(shì)了, 因?yàn)檫@個(gè)命中失敗率已經(jīng)是很小的了, 改進(jìn)這個(gè)無(wú)法顯著提高處理速度。

請(qǐng)注意, 最后的一次sha3_256 哈希用來(lái)來(lái)確保存在一個(gè)中間的nonce,它可以提供證明至少有少量的工作被完成。 這個(gè)快速的PoW驗(yàn)證可以用于反 DDoS 的目的。

它也可以為結(jié)果是一個(gè)不偏不倚的256 位數(shù)，提供統(tǒng)計(jì)性的保證。

*** 挖礦

挖礦算法定義如下:

def mine(full_size, dataset, header, difficulty):

? ? target = zpad(encode_int(2**256 // difficulty), 64)[::-1]

? ? from random import randint

? ? nonce = randint(0, 2**64)

? ? while hashimoto_full(full_size, dataset, header, nonce) > target:

? ? ? ? nonce = (nonce + 1) % 2**64

? ? return nonce

*** 定義種子哈希

為了計(jì)算將用于在給定塊頂部挖礦的種子哈希值, 我們使用以下算法:

def get_seedhash(block):

? ? s = '\x00' * 32

? ? for i in range(block.number // EPOCH_LENGTH):

? ? ? ? s = serialize_hash(sha3_256(s))

? ? return s

請(qǐng)注意, 為了平滑地進(jìn)行挖礦和驗(yàn)證, 我們建議在單獨(dú)的線(xiàn)程中 預(yù)先生成和計(jì)算 下一個(gè)要使用到的種子哈希和數(shù)據(jù)集。

*** 附錄

如果您有興趣將上面的 python 規(guī)范作為代碼運(yùn)行, 則應(yīng)預(yù)置以下代碼。

import sha3, copy

# Assumes little endian bit ordering (same as Intel architectures)

def decode_int(s):

? ? return int(s[::-1].encode('hex'), 16) if s else 0

def encode_int(s):

? ? a = "%x" % s

? ? return '' if s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]

def zpad(s, length):

? ? return s + '\x00' * max(0, length - len(s))

def serialize_hash(h):

? ? return ''.join([zpad(encode_int(x), 4) for x in h])

def deserialize_hash(h):

? ? return [decode_int(h[i:i+WORD_BYTES]) for i in range(0, len(h), WORD_BYTES)]

def hash_words(h, sz, x):

? ? if isinstance(x, list):

? ? ? ? x = serialize_hash(x)

? ? y = h(x)

? ? return deserialize_hash(y)

def serialize_cache(ds):

? ? return ''.join([serialize_hash(h) for h in ds])

serialize_dataset = serialize_cache

# sha3 hash function, outputs 64 bytes

def sha3_512(x):

? ? return hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)

def sha3_256(x):

? ? return hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)

def xor(a, b):

? ? return a ^ b

def isprime(x):

? ? for i in range(2, int(x**0.5)):

? ? ? ? if x % i == 0:

? ? ? ? ? ? return False

? ? return True

*** 數(shù)據(jù)大小

下面的查找表提供了大約2048個(gè)紀(jì)元的數(shù)據(jù)集大小和緩存大小的表格。它們是使用下面的 Mathematica 函數(shù)生成的:

def get_datasize(block_number):

? ? return data_sizes[block_number // EPOCH_LENGTH]

def get_cachesize(block_number):

? ? return cache_sizes[block_number // EPOCH_LENGTH]

data_sizes = []