1703864383
区块链技术驱动金融：数字货币与智能合约技术 [:1703863907]
1703864384
区块链技术驱动金融：数字货币与智能合约技术 1.1 密码学哈希函数
1703864385
1703864386
我们需要理解的第一个密码学的基础知识是密码学哈希函数，哈希函数是一个数学函数，具有以下三个特性：
1703864387
1703864388
● 其输入可为任意大小的字符串。
1703864389
1703864390
● 它产生固定大小的输出。为使本章讨论更具体，我们假设输出值大小为256位，但是，我们的讨论适用于任意规模的输出，只要其足够大。
1703864391
1703864392
● 它能进行有效计算，简单来说就是对于特定的输入字符串，在合理时间内，我们可以算出哈希函数的输出。更准确地说，对应n位的字符串，其哈希值计算的复杂度为O（n）。
1703864393
1703864394
这些特性定义了一般哈希函数，以这个函数为基础，我们可以创建数据结构，例如哈希表。我们将只专注于加密的哈希函数，要使哈希函数达到密码安全，我们要求其具有以下三个附加特性：（1）碰撞阻力（collision-resistance）；（2）隐秘性（hiding）；（3）谜题友好（puzzle-friendliness）。
1703864395
1703864396
我们会仔细研究这些特性，并会逐步阐释我们为什么需要这样的函数。学习过密码学的读者可能会注意到，我们这里对于哈希函数的论述与一般的密码学课程会有所不同，特别是关于谜题友好。在一般密码学中，谜题友好并非加密的哈希函数的一般要求，却对加密数字货币这一特性非常有用。
1703864397
1703864398
特性1：碰撞阻力
1703864399
1703864400
加密的哈希函数的第一个特性是它要具有碰撞阻力。这里的碰撞指对于两个不同的输入，产生相同的输出。如果对于哈希函数H(·)，没有人能够找到碰撞，我们则称该函数具有碰撞阻力（见图1.1）。即：
1703864401
1703864402
碰撞阻力 如果无法找到两个值，x和y，x≠y，而H(x)=H(y)，则称哈希函数H具有碰撞阻力。
1703864403
1703864404
1703864405
1703864406
1703864407
图1.1 哈希碰撞
1703864408
1703864409
注：x和y分别是不同输入，当作为哈希函数的输入时，会产生相同的输出。这时我们就说这个函数是哈希碰撞的。
1703864410
1703864411
注意，我们说没人能找到碰撞，并不表示不存在碰撞。事实上，通过简单的计数论证（counting argument），我们可以证明碰撞的确存在。哈希函数的输入空间包含所有长度的任意字符串，但输出空间则只包含特定固定长度的字符串。因为输入空间比输出空间大（输入空间是无限的，而输出空间是有限的），一定会有输入字符串映射到相同的输出字符串。实际上，根据鸽巢原理（Pigeonhole Principle），我们可以得出，必然会有大量可能的输入被映射到任意特定输出（见图1.2）。
1703864412
1703864413
1703864414
1703864415
1703864416
图1.2 必然的碰撞
1703864417
1703864418
注：因为输入的数量超过输出的数量，我们可以确定某一个输出肯定对应多个输入。
1703864419
1703864420
而更糟糕的是，对于加密的哈希函数，我们虽然说应该找不到碰撞，但有些方法是能保证找到碰撞的。考虑以下对应于一个256位输出大小的哈希函数，选择2256+1个不同数值，计算每个数的哈希值，并检查是否有两个相等的输出。因为我们这里选择的输入多于输出，因此在应用哈希函数时，一些数对必将产生碰撞。
1703864421
1703864422
使用上述方法一定能找到碰撞。但如果我们随机性地选择输入，并计算哈希值，我们在检验第2256+1个输入之前便很可能找到碰撞。实际上，如果我们随机选择2130+1个输入值，找到至少两个等同哈希值的概率为99.8%。仅仅通过检验可能输出数量的平方根次数，便大体能找到碰撞，这一事实在概率学中被称为是生日悖论（birthday paradox）[1]。
1703864423
1703864424
这个碰撞检测算法对每个哈希函数都有效，但是它的问题是其计算需要花很长很长时间才能完成。对于一个256位输出的哈希函数来说，最坏的情况是你需要进行2256+1次哈希函数计算，平均次数为2128次，这简直是一个天文数字——如果一台电脑每秒计算10 000个哈希值，计算2128个哈希值，需要花1027多年时间！换个角度，我们可以说，如果人类制造的每台电脑在整个宇宙起源时便开始计算，到目前为止，它们找到碰撞的概率仍然无穷小，比下两秒钟地球将被大陨石摧毁的概率还要小得多。
1703864425
1703864426
因此，为了寻找一个任意的哈希函数的碰撞，我们只是有了一个一般，但并不实用的算法。一个更艰涩的问题是：有没有其他的方法，可以用于对于某一特定哈希函数找到碰撞？也就是说，虽然一般的碰撞测试算法不适用，但仍可能有其他的算法，可以有效地找到某个哈希函数的碰撞。
1703864427
1703864428
以下面的哈希函数为例：
1703864429
1703864430
H(x)=x mod 2256
1703864431
1703864432
这个函数接受任何长度的输入，产生一个固定大小输出（256位），且能进行有效计算，因此符合我们对哈希函数的要求。但是对于这个函数，我们确实具备一个有效的能够寻找碰撞的方法。注意，这个函数仅返回输入的最后256位，因此，数值3和3+2256就构成了碰撞[2]。这个简单的例子表明，虽然我们的一般碰撞测试方法在实践中不可行，但至少对于某些哈希函数，存在有效的测试碰撞的方法。