比特币背后的算法和数学，以太坊背后的算法和数学

一、比特币背后的算法和数学

比特币实现中的哈希算法

可以说，比特币的整个实现都是基于计算机科学领域已经存在多年的现有技术或概念的整合。 哈希算法在比特币中的应用几乎是方方面面的，主要包括SHA256和RIPEMD160，比特币将这两种哈希算法的应用结合成两个函数：hash256(d)=sha256(sha256(d))和hash160(d)=ripemd160 (sha256(d))，其中d是待哈希的字节数组，两者分别生成256位（32字节）和160位（20字节）的十六进制值。 Hash256主要用于生成标识符，如区块ID、交易ID等，而Hash160主要用于生成比特币地址。

值得一提的是为什么两个函数都做两次哈希？ hash160比较赞的答案是ripemd160可以让生成的地址更短，但是只做一个ripemd160的hash可能会有安全漏洞，所以同时使用sha256可以增强安全性； 至于hash256，两次使用sha256 hash算法的原因来自sha1算法，因为一次sha1 hash有生日攻击的风险，所以在使用sha1运算时，一个有效的方法是做两次sha1 hash，sha256本身没有有生日攻击漏洞，但防御使用从sha1借来的两个sha256哈希。

默克尔树

比如SPV这样只保存区块头信息，没有交易信息的比特币轻节点，如何验证一笔交易存在于哪个区块？ 默克尔树。 （图片来自精通比特币）

Merkle树的基本原理是将叶子节点成对配对进行哈希运算（如果叶子节点的个数为奇数，则复制最后一个叶子）生成一个父节点，迭代这个过程最后生成唯一的根节点默克尔根。 如果要验证Merkle树中是否存在叶子节点，只需要传入一条从该节点到根节点的merkle路径，SPV比特币节点只需要保存根节点即可。 例如，根据上图，如果我们要验证第k笔交易是否在区块中，只需要传递路径HL、HIJ、HMNOP和HABCDEFGH即可。

椭圆曲线函数EC（Elliptic Curve）

比特币使用公钥加密来保护个人隐私，并选择了椭圆曲线函数来实现。 选择EC的综合原因不太清楚，但至少我觉得够安全，够高效。 在比特币的实现中比特币标志图片，EC起着三个方面的作用，密钥对生成、私钥签名和签名验证。

椭圆曲线的数学表达式为y2=x3+ax+b。 椭圆曲线有两个重要特征。 1.任何不垂直的直线与曲线相交于两点，则该直线必须与曲线相交于第三点； 2. 任何非垂直曲线的切线必须与曲线相交于另一点。 根据这两个特性，设点Q和P为曲线上的点，得到如下定义，加运算：通过Q和P的直线与曲线相交于第三点R'，则Q+P= R，其中R为点R'，关于x坐标轴对称； 同理，移动直线使Q点和P点相近重合形成点D，则直线与曲线相切，根据特征2，与曲线相交于一点R'，这不是 很难得到D+D=R，其中R是点R'相对于x坐标轴的对称点。 乘法运算：设Q=aP，假设a=3，会有：

Q=3P

Q=P+2P

这样，乘法运算就分解为两个加法运算，即交加和切加。 椭圆曲线图（图片来自Mastering bitcoin）：

现在让我们看一下比特币协议中的椭圆曲线特性。 在比特币使用的曲线版本中，a=0，b=7，即y2=x3+7。 同时，为了保证函数的取值在一个限定的范围内，所以在EC的实际应用中，会对结果进行取模运算，以获得限定范围内的结果。 比如模数为7, 8 mod 7 = 1，那么x mod 7的取值就限制在0到6之间。比特币协议中的EC有如下参数设置：

模数 p=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFC2F

基点G=0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

序数 n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141

这些参数的设置经过了大量的研究，既复杂又微妙。 这些都是巨大的价值，使得反向操作不可能。 简单的说，p是曲线的取值范围，n是我们可以得到的最大私钥值，也就是私钥必须小于n值。 根据上图，计算公钥的过程就是私钥和G点的乘法运算。 G点和n的取值是基于当私钥的值无限接近n时，与椭圆曲线相交的直线的斜率无限接近垂直。

是时候看看椭圆曲线在比特币的三种应用中是如何工作的了。

1.密钥对生成

上面说了公钥=私钥x G，也就是G点加到私钥值上的次数。 这里有个小问题。 上图展示了点在一个连续区间内的分布，但是在取模的时候，以后就需要使用特定的公式来达到目的了。 设Q和P为曲线上的两点，则曲线上两点相加相交的R点为：

d = (Qy-Py) / (Qx-Px)

Rx= d2- Px- Qx

Ry = d (Px- Rx) - Py

两点重合在一点Q的切线上时，交点R的计算公式为：

d = (3Qx2+ a) / 2Qy

Rx= d2- 2Qx

Ry = d (Qx- Rx) - Qy

就像上面说的曲线乘法运算一样，乘法过程就是把运算拆成无数个切线和交线运算，也就是分别用上面两个公式的计算过程。

2.使用私钥对数据进行签名

为了隐私保护，在交易中使用私钥签名代替私钥来验证未花费的归属。 不管比特币的使用环境如何，签名操作都是使用私钥dA加密一段数据z，如下：

(1). 在大于0小于n的​​范围内选择一个数k（上面的序数，即私钥的上限）

(2). 计算点p(x,y)=k*G

(3). 计算r=x mod n，如果r部分为0，则返回第一步，重新选择

(4). 计算s=(z+r*dA)/k mod n，如果段s为0，则返回第一步重新计算

(5). 生成了数字签名signature(r,s)

3.数字签名验证

比特币交易的链上运行就是私钥签名和公钥签名验证不断进行的过程。 有了上面的签名，签名验证过程如下（假设公钥为dP）：

(1). 验证 r 和 s 段在 0 和 n 之前

(2). 计算w=s-1mod n

(3). 计算 u1=z*w mod n

(4). 计算u2=r*w mod n

(5). 计算p(x,y)=u1*G+u2*dP

(6). 验证r==x mod n，如果不等式则验证失败

至于为什么验证过程有效，可以参考这里。 简单的说就是将公钥dP展开为dA*G，然后将u1和u2的定义带入计算。

2. 以太坊背后的算法和数学

以太坊使用的算法，Ethash

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))

回报

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

*** 附录

如果您有兴趣将上述 python 规范作为代码运行，则应添加以下代码。

导入 sha3，复制

# 假定小端位排序（与 Intel 架构相同）

def decode_int(s):

返回 int(s[::-1].encode('hex'), 16) 如果 s 否则 0

def encode_int(s):

一个 = "%x" %s

返回 '​​' 如果 s == 0 else ('0' * (len(a) % 2) + a).decode('hex')[::-1]

def zpad（s，长度）：

返回 s + '\x00' * max(0, 长度 - len(s))

def serialize_hash(h):

返回 '​​'.join([zpad(encode_int(x), 4) for x in h])

def deserialize_hash(h):

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

def hash_words(h, sz, x):

如果是实例（x，列表）：

x = serialize_hash(x)

y = h(x)

返回 deserialize_hash(y)

def serialize_cache（ds）：

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

serialize_dataset = serialize_cache

# sha3 哈希函数，输出 64 字节

def sha3_512(x):

返回 hash_words(lambda v: sha3.sha3_512(v).digest(), 64, x)

def sha3_256(x):

返回 hash_words(lambda v: sha3.sha3_256(v).digest(), 32, x)

def 异或（a，b）：

返回 a^b

def 是素数（x）：

对于范围内的我（2，整数（x**0.5））：

如果 x % i == 0:

返回假

返回真

*** 数据大小

下面的查找表提供了大约 2048 个时期的数据集大小和缓存大小的表格。 它们是使用以下 Mathematica 函数生成的：

def get_datasize(block_number):

返回 data_sizes[block_number // EPOCH_LENGTH]

def get_cachesize(block_number):

返回 cache_sizes[block_number // EPOCH_LENGTH]

数据大小 = []