一，比特币背后的算法与数学
比特币实现中的哈希算法
可以说比特币的整个实现就是建立在已有的甚至存在多年的计算机科学领域里的技术或概念的整合，其中哈希算法在比特币中的应用几乎是方方面面，主要包括SHA256和RIPEMD160，比特币将这两个哈希算法的应用组合成两个函数：hash256(d)=sha256(sha256(d))和hash160(d)=ripemd160(sha256(d))，其中d为待哈希的字节数组，两者分别生成256位（32字节）和160位（20字节）的16进制数值。hash256主要用于生成标志符，如区块ID，交易ID等，而hash160主要用于生成比特币地址。
值得一提的是，为什么两个函数都是做两次哈希呢？对于hash160比较认同的答案是ripemd160可以使得生成的地址更短，但是只做ripemd160一次哈希可能会存在安全漏洞所以同时使用sha256起到安全加固；至于hash256使用两次sha256哈希算法的原因来源于sha1算法，由于一次sha1哈希存在被生日攻击（birthday attack）的风险，所以当使用sha1运算时一种有效方式就是做两次sha1哈希，sha256本身并不存在生日攻击漏洞，但是防御性的使用两次sha256哈希借鉴于sha1.
默克树
对于例如SPV这种本身只保存区块头信息而没有交易信息的比特币轻节点是如何验证一笔交易存在于哪一个区块的呢--默克树。（图片来自Mastering bitcoin）
默克树的基本原理就是将叶子节点两两配对做哈希运算（如果叶子节点为奇数，那么将最后一个叶子复制）生成父节点，不断迭代这一过程最终生成唯一的根节点merkle root。如果要验证一个叶子节点是否存在于默克树中只需要传入一个该节点到根节点路径merkle path，而SPV比特币节点只需保存root节点即可。例如，依上图如果想验证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就有：p分页标题e
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=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
基点G=0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
序数n=FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
这些参数的设定经过大量的研究，复杂而精妙，这些都巨大的数值，使得逆向运算不可能，简单的说p为曲线的取值区间，n为我们可以取得的最大私钥值，即私钥必须小于n值，依照上图，计算公钥的过程就是私钥与G点的乘法运算。G点与n的取值依据是，当私钥的取值无限接近于n时与椭圆曲线相交的直线的斜率无限接近于垂直。
该来看看椭圆曲线如何在比特币三个应用方面发挥作用的了。
1.密钥对生成
正如上面提到的，公钥=私钥xG，就是将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.使用私钥为数据签名
为了隐私保护，交易中使用私钥签名而非私钥来验证一笔unspent的归属，抛开比特币的使用环境，那么签名操作就是使用私钥dA加密一段数据z，具体如下：
(1).选择一个数k范围在大于0小于n（上文中的序数，即私钥的上限）
(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.数字签名验证
比特币交易的链式操作就是不断的私钥签名和公钥验签的过程，有了上面的signature，验签过程如下（令公钥为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*dPp分页标题e
(6).验证r==x mod n，如果等式不成立，那么验证失败
至于验证过程为什么有效，可以参考这里，简单来说就是将公钥dP展开为dA*G，然后将u1和u2定义分别带入求得。
二,以太坊背后的算法与数学
以太坊所以用的算法，Ethash
Ethash 是 Ethereum 1.0 的计划的PoW算法。这是最新版本的Dagger-Hashimoto, 虽然它不能再恰当地被称为Dagger-Hashimoto,
因为这两种算法的许多原始特性已经在上个月的研究和开发中发生了翻天覆地的变化。
请参见 https://github.com/ethereum/wiki/blob/master/Dagger-Hashimoto.md 的原始版本。
该算法所采用的一般流程如下所示:
1. 存在一个种子, 可以通过块高度直到该点来计算每个块。
2. 从种子, 你可以计算一个 16 MB 的伪随机缓存, 用于轻客户端存储缓存。
2. 从缓存中, 我们可以生成一个 1 GB 的数据集, 该属性表示数据集中的每个项只依赖于缓存中的少量项。完整的客户和矿工存储这个数据集。数据集会随时间线性增长。
挖矿涉及抓取数据集的随机切片并将它们一起哈希。可以通过使用缓存来重新生成所需的数据集的特定部分, 从而低内存的机器可以进行验证, 因为只需存储缓存即可验证。
完整的大数据集每隔30000块更新一次, 因此大多数矿工的工作将是读取数据集, 而不是对其进行更改。
有关此算法的设计基本原理注意事项, 请参见 https://github.com/ethereum/wiki/wiki/Ethash-Design-Rationale。
算法使用python来字义和描述, 几个重要的库函数要查清文档，别望文生义, 如:
1.map是遍历数组的作为参数去调用函数，得到一个新的数组.
2. **这个指数运算符等,
3. //是整除
4. [::-1]是大小
5. RLP是一个编码算法，请另外查阅和理解
...
***全局常量定义
我们使用以下定义:
WORD_BYTES = 4 一个字的字节数
DATASET_BYTES_INIT = 2**30 创世块的字节数
DATASET_BYTES_GROWTH = 2**23 每个纪元(30000块一次)的数据集增长字节数
CACHE_BYTES_INIT = 2**24 创世块的缓冲字节数
CACHE_BYTES_GROWTH = 2**17 每个纪元(30000块一次)的缓冲增长字节数
CACHE_MULTIPLIER=1024 相对于DAG缓存的大小
EPOCH_LENGTH = 30000 每个纪元的块数
MIX_BYTES = 128 混合体的字节数
HASH_BYTES = 64 哈希的字节数
DATASET_PARENTS = 256 每个数据集元素的父级数
CACHE_ROUNDS = 3 缓存生产中的回合数
ACCESSES = 64 hashimoto循环的访问次数
有关本规范中描述的 "SHA3" 哈希的说明
Ethereum 的发展恰逢 SHA3 标准的发展, 标准过程在最终的哈希算法的填充上做了后期的更改, 因此 Ethereum 的 "sha3_256" 和 "sha3_512" 哈希不是标准的 sha3 哈希, 而是一个变体在其他语境中经常被称为 "Keccak-256" 和 "Keccak-512"。p分页标题e
请记住, 这个算法仍然当做 "sha3" 哈希在下面的算法描述中被引用。
***参数
Ethash 的缓存和数据集的参数取决于块号。
高速缓存大小和数据集大小均呈线性增长。
然而, 我们总是把最高的素数放在线性增长的阈值之下, 以减少偶然的规律性,从而导致循环行为的风险。
isprime来定义这个是不是素数，请看附录。
根据给出的块号, 计算cache的大小， 如果大小除法HASH_BYTES不是符合定义的素数, 会一直减少这个直至这个大小是符合定义的素数
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
根据给出的块号, 计算DAG的完整大小， 如果大小除以MIX_BYTES不是符合定义的素数, 会一直减少这个直至这个大小是符合定义的素数
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
附录中提供了数据集和缓存大小值的表。
***缓存生成
下面是现在我们指定用于生成缓存的函数:
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
缓存生产过程首先需要依次填充 32 MB 内存, 然后从严格的内存难度型哈希函数 (2014) 执行两次Sergio Demian Lerner的 RandMemoHash 算法。
输出是一组 524288 个64 字节的值。
***数据聚合函数
在某些情况下, 我们使用由 FNV hash算法作为 XOR 的关联替换。请注意, 我们将素数与完整的32位输入相乘, 与 FNV-1 规范相比, 它反过来将素数与一个字节 (八进制) 相乘。
FNV_PRIME = 0x01000193
def fnv(v1, v2):
return ((v1 * FNV_PRIME) ^ v2) % 2**32
请注意, 即使是黄皮书指定FNV 为 v1 * (FNV_PRIME ^ v2), 但所有当前的实现始终使用上述定义。
***完整数据集计算
完整的 1 GB 数据集中的每个64字节项都按如下方式计算:
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)
实质上, 我们将来自 256个伪随机的选定缓存节点的数据和哈希值合并到一起以计算 数据集的 节点。然后生成整个数据集，算法如下:p分页标题e
def calc_dataset(full_size, cache):
return [calc_dataset_item(cache, i) for i in range(full_size // HASH_BYTES)]
***主循环
现在, 我们说明类"hashimoto"的循环, 在这里我们从完整的数据集收集资料, 以便为特定的Header和nonce生成我们的最终值。
在下面的代码中, header表示截取过的块头部(即不包括 mixHash字段 和nonce的头部)使用RLP 表示的 SHA3-256 哈希。
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
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])
本质上, 我们保持一个 "混合体" 128 字节宽, 并重复地从完整的数据集中获取128个字节, 并使用FNV函数将它与"混合体" 组合在一起。
128字节顺序访问的方法, 可以使每一个回合的算法总是从 RAM 中提取一个完整的页面, 这样可以最小化TLB的命中失败次数, 这个主要是为防ASIC。
如果该算法的输出小于目标值, 则nonce就是正确的解。
解释一下TLB: Translation Lookaside Buffer. 根据功能可以译为快表，直译可以翻译为旁路转换缓冲，也可以把它理解成页表缓冲。里面存放的是一些页表文件（虚拟地址到物理地址的转换表）。当处理器要在主内存寻址时，不是直接在内存的物理地址里查找的，而是通过一组虚拟地址转换到主内存的物理地址，TLB就是负责将虚拟内存地址翻译成实际的物理内存地址，而CPU寻址时会优先在TLB中进行寻址。处理器的性能就和寻址的命中率有很大的关系。
ASIC在理论上是有能力做到避免TLB的命中失败次数的, 但这样做了ASIC就没有优势了, 因为这个命中失败率已经是很小的了, 改进这个无法显著提高处理速度。
请注意, 最后的一次sha3_256 哈希用来来确保存在一个中间的nonce,它可以提供证明至少有少量的工作被完成。 这个快速的PoW验证可以用于反 DDoS 的目的。p分页标题e
它也可以为结果是一个不偏不倚的256 位数，提供统计性的保证。
*** 挖矿
挖矿算法定义如下:
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
*** 定义种子哈希
为了计算将用于在给定块顶部挖矿的种子哈希值, 我们使用以下算法:
def get_seedhash(block):
s = &39;\x00&39; * 32
for i in range(block.number // EPOCH_LENGTH):
s = serialize_hash(sha3_256(s))
return s
请注意, 为了平滑地进行挖矿和验证, 我们建议在单独的线程中 预先生成和计算 下一个要使用到的种子哈希和数据集。
*** 附录
如果您有兴趣将上面的 python 规范作为代码运行, 则应预置以下代码。
import sha3, copy
Assumes little endian bit ordering (same as Intel architectures)
def decode_int(s):
return int(s[::-1].encode(&39;hex&39;), 16) if s else 0
def encode_int(s):
a = "%x" % s
return &39;&39; if s == 0 else (&39;0&39; * (len(a) % 2) + a).decode(&39;hex&39;)[::-1]
def zpad(s, length):
return s + &39;\x00&39; * max(0, length - len(s))
def serialize_hash(h):
return &39;&39;.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 &39;&39;.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
*** 数据大小
下面的查找表提供了大约2048个纪元的数据集大小和缓存大小的表格。它们是使用下面的 Mathematica 函数生成的:
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 = []
