Ethereum Algorithm，以太坊的Ethash算法

每一种数字货币都有自己的算法，我们在数字货币挖矿的过程中需要通过这些算法来计算自己的收益。 以太坊作为知名的数字货币，自然有自己的以太坊算法。 毕竟算法比较复杂。 接下来介绍以太坊的一个Ethash算法。

认真阅读，理解，计算，调试，顺便自己翻译一下，一起学习。 微笑

本规范是修订版 23。

Ethash 是以太坊 1.0 计划中的 PoW 算法。 这是 Dagger-Hashimoto 的最新版本，虽然它不能再被称为 Dagger-Hashimoto，

因为这两个算法很多原有的特性在最后一个月的研发中发生了翻天覆地的变化。

请参阅原始版本。

该算法使用的一般过程如下：

1.存在一个种子，可以通过到该点的块高度为每个块计算。

2. 从种子中，您可以为轻客户端存储缓存计算一个 16 MB 的伪随机缓存。

2. 从缓存中，我们可以生成一个 1 GB 的数据集，其属性是数据集中的每个项目仅依赖于缓存中的少量项目。 完整的客户和矿工存储此数据集。 数据集随时间线性增长。

挖掘涉及抓取数据集的随机切片并将它们散列在一起。 低内存机器可以通过使用缓存重新生成所需数据集的特定部分来进行验证，因为只需要存储缓存来进行验证。

完整的大型数据集每 30000 个区块更新一次，因此大多数矿工的工作将是读取数据集，而不是对其进行更改。

有关此算法的设计基本原理注意事项，请参阅 。

算法使用python来定义和描述，几个重要的库函数需要查文档，不要照字面意思，比如：

1.map是遍历数组作为参数调用函数得到一个新的数组。

2. **这个指数运算符等，

3. // 是可分割的

4. [::-1]是翻转元组或列表的内容

5. RLP是一种编码算法，请单独阅读理解

...

***全局常量定义

我们使用以下定义：

WORD_BYTES = 4 # 一个字的字节数

DATASET_BYTES_INIT = 2**30 # 创世块中的字节数

DATASET_BYTES_GROWTH = 2**23 # 每个epoch的数据集增长字节数（30000块一次）

CACHE_BYTES_INIT = 2**24 # 创世块的缓冲字节数

CACHE_BYTES_GROWTH = 2**17 # 每个epoch缓冲区增长字节数（30000块一次）

CACHE_MULTIPLIER=1024 # 相对于DAG缓存的大小

EPOCH_LENGTH = 30000 # 每个纪元的块数

MIX_BYTES = 128 # 混合字节

HASH_BYTES = 64 # 要散列的字节数

DATASET_PARENTS = 256 # 每个数据集元素的父元素个数

CACHE_ROUNDS = 3 # 缓存生产的轮数

ACCESSES = 64 # 桥本循环的访问次数

关于本规范中描述的“SHA3”散列的注释

以太坊的发展恰逢SHA3标准的发展，标准过程对最终哈希算法的padding做了后期修改，所以以太坊的“sha3_256”和“sha3_512”哈希不是标准的sha3哈希，而是一个变量Body在其他情况下通常称为“Keccak-256”和“Keccak-512”。

请记住，此算法在下面的算法描述中仍称为“sha3”散列。

***范围

Ethash 的缓存和数据集参数取决于块号。

缓存大小和数据集大小都线性增长。

但是，我们总是将最高素数置于线性增长阈值以下，以降低偶然规律性导致循环行为的风险。

isprime 定义这个是否是质数以太坊算法，请看附录。

#根据给定的块号，计算缓存的大小，如果size划分HASH_BYTES不是满足定义的素数，则递减直到size为满足定义的素数

def get_cache_size(block_number):

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

sz -= HASH_BYTES

而不是 isprime(sz / HASH_BYTES)：

sz -= 2 * HASH_BYTES

返回尺寸

#根据给定的块号，计算DAG的全尺寸，如果尺寸除以MIX_BYTES不是定义的素数，则缩小直到尺寸为定义的素数

def get_full_size(block_number):

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

sz -= MIX_BYTES

而不是 isprime(sz / MIX_BYTES)：

sz -= 2 * MIX_BYTES

返回尺寸

附录中提供了数据集和缓存大小值的表格。

***缓存生成

这是我们现在指定生成缓存的函数：

def mkcache（缓存大小，种子）：

n = cache_size // HASH_BYTES

# 依次产生初始数据集

o = [sha3_512(种子)]

对于范围内的我（1，n）：

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

# 使用低轮版本的 randmemohash

对于范围内的_（CACHE_ROUNDS）：

对于范围内的我（n）：

v = o[i][0] % n

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

回车

缓存生产过程首先需要顺序填充32MB内存，然后从严格内存难度哈希函数（2014）开始执行Sergio Demian Lerner的RandMemoHash算法两次。

输出是一组 524288 个 64 字节值。

***数据汇总功能

在某些情况下，我们使用 FNV 哈希算法作为 XOR 的关联替代。 请注意，与 FNV-1 规范相比，我们将素数与完整的 32 位输入相乘，而 FNV-1 规范又将素数与一个字节（八进制）相乘。

FNV_PRIME = 0x01000193

def fnv(v1, v2):

返回 ((v1 * FNV_PRIME) ^ v2) % 2**32

请注意，尽管黄皮书将 FNV 指定为 v1 * (FNV_PRIME ^ v2)，但所有当前实现始终使用上述定义。

***全数据集计算

完整 1 GB 数据集中的每个 64 字节项目计算如下：

def calc_dataset_item（缓存，我）：

n = len（缓存）

r = HASH_BYTES // WORD_BYTES

#初始化混音

mix = copy.copy(缓存[i % n])

混合 [0] ^= 我

混合 = sha3_512（混合）

# fnv 它有很多基于 i 的随机缓存节点

对于范围内的 j（DATASET_PARENTS）：

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

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

返回 sha3_512（混合）

本质上，我们将来自 256 个伪随机选择的缓存节点的数据和哈希组合起来，以计算数据集的节点。 然后生成整个数据集，算法如下：

def calc_dataset（全尺寸，缓存）：

返回 [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]

*** 主循环

现在，我们说明类“桥本”的循环，我们从完整的数据集中收集材料，以便为特定的标头和随机数生成我们的最终值。

下面代码中，header表示截取到的块头（即除去mixHash字段和nonce的块头）的SHA3-256哈希，由RLP表示。

nonce 是一个 64 位无符号整数的八个字节。 因此，[:-1] 是值的八字节小端表示：

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

n = full_size / HASH_BYTES

w = MIX_BYTES // WORD_BYTES

mixhashes = MIX_BYTES / HASH_BYTES

# 将 header+nonce 组合成一个 64 字节的种子

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

# 开始与复制的 s 的混合

混合 = []

对于范围内的_（MIX_BYTES / HASH_BYTES）：

混合。 延长

# 混入随机数据集节点

对于范围内的我（访问）：

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

新数据 = []

对于范围内的 j（MIX_BYTES / HASH_BYTES）：

newdata.extend(dataset_lookup(p + j))

mix = map(fnv, mix, newdata)

# 压缩组合

cmix = []

对于我在范围内（0，len（混合），4）：

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

返回 {

“混合摘要”：serialize_hash（cmix），

“结果”：serialize_hash(sha3_256(s+cmix))

}

def hashimoto_light（全尺寸、缓存、标头、随机数）：

返回桥本（标题，随机数，full_size，lambda x：calc_dataset_item（缓存，x））

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

返回 hashimoto(header, nonce, full_size, lambda x: dataset[x])

本质上，我们保留一个 128 字节宽的“混合”，并重复从完整数据集中取出 128 个字节，并使用 FNV 函数将其与“混合”组合。

128字节的顺序访问方式可以使算法的每一轮总是从RAM中提取一个完整的页面，可以最大限度地减少TLB命中失败的次数，主要是为了抗ASIC。

如果算法的输出小于目标值，则 nonce 是正确的解决方案。

解释 TLB：Translation Lookaside Buffer。 按照功能可以翻译成快速表，直译可以翻译成bypass conversion buffer，也可以理解为page table buffer。 里面存放的是一些页表文件（虚拟地址到物理地址的转换表）。 当处理器要寻址主存时，并不是直接在内存的物理地址中查找以太坊算法，而是通过一组虚拟地址转换为主存的物理地址。 TLB 负责将虚拟内存地址翻译成实际的物理内存。 地址，而CPU在寻址时会优先在TLB中寻址。 处理器的性能与寻址命中率有很大关系。

ASIC理论上可以避免TLB命中失败的次数，但是ASIC这样做没有优势，因为命中未命中率已经很小了，再提高也不能显着提高处理速度。

请注意，最终的 sha3_256 哈希用于确保存在一个中间随机数，该随机数提供至少完成少量工作的证据。 这种快速的 PoW 验证可用于反 DDoS 目的。

它还提供统计保证，即结果是一个无偏的 256 位数字。

*** 挖矿

挖矿算法定义如下：

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

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

从随机导入 randint

随机数 = randint(0, 2**64)

while hashimoto_full(full_size, dataset, header, nonce) > 目标：

随机数 = (随机数 + 1) % 2**64

返回随机数

*** 定义种子哈希

为了计算将用于在给定块顶部进行挖掘的种子哈希，我们使用以下算法：

def get_seedhash（块）：

s = '\x00' * 32

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

s = serialize_hash(sha3_256(s))

回报

请注意，为了顺利进行挖掘和验证，我们建议预先生成和计算下一个种子哈希和数据集，以在单独的线程中使用。

事实上，每种数字货币的算法并不只有一种。 为了完善自己币种的盈利算法，很多数字货币提供的算法也各不相同。 以太坊也是如此。 Ethash算法只是其中一种方法。 还有其他以太坊数字货币算法尚未提供。 想了解更多可以关注伟峰。