比特币技术原理与应用-1 密码学基础

本系列文章： 比特币技术原理与应用-1 密码学基础 比特币技术原理与应用-2 数据结构

密码学基础

刚开始接触比特币的同学，可能会听说比特币采用了多么高级的密码学技术，没有人能够破解。但是实际上比特币采用的密码学技术是非常成熟的，已经广泛应用于传统金融机构中。比特币中的密码学技术主要采用了哈希函数和数字签名。

哈希函数

哈希函数(Hash Function)，其实有一个更通俗的名字——散列函数。(哈希是对Hash的音译，散列则是意译，中文博大精深啊)

举一个生活中常见的例子，来帮助大家理解一下散列函数。在学校里我们平常去取快递，快递小姐姐会让你报一下手机尾号后四位，然后去对应的货架上找你的快递。根据手机尾号KXXX，小姐姐会去货架K上面按照顺序一个一个查找你的快递。这就是一个散列函数，提高了找快递的效率。但是，散列函数会遇到碰撞的问题，先假设货架都是空的，第一个快递，手机尾号为0086的快递放在了货架0的左上角第一个位置，第二个快递，手机尾号是0010，小姐姐拿着0010快递来到货架0，发现左上角第一个位置被占了，已经有0086快递放着了。这就是两个元素取哈希之后发生了碰撞。但是小姐姐想着把0010这个快递放在0086快递的右边空位就好了。往后要是还有0XXX尾号的快递，就从货架0左上角开始查找空位置，找到空位摆放快递就行了。这就是采用线性探测法解决了碰撞问题。

比特币中使用的哈希函数是SHA-256(Secure Hash Algorithm: 安全哈希算法)，SHA-256接收输入数据后，无论输入数据1MB还是1TB还是更大，都会输出256位的二进制数，并且不同的数据输入会得到不同的256位二进制数。

比特币使用的哈希函数有三个重要特性：碰撞阻力(collision resistance)，隐秘性(hiding)和谜题友好性(puzzle friendly)。

碰撞阻力

上面列举的快递手机尾号例子，两个手机尾号以0开头的快递可能会发生碰撞，那要如何才能保证两个0XXX快递不会碰撞？如果我们在货架0上准备1000个小隔间，编号0000-0999，这样对应的手机尾号可以直接找到对应的隔间，并且也不会被别的快递占位置。这样相当于我们扩大了输出空间，原本所有的手机尾号只可能有10个输出——货架0-货架9，现在是有10000个输出——小隔间0000-9999。

SHA-256的输出空间为$$2^{256}$$ 换算成10进制，约为$$10^{77}$$这个数是个什么概念呢？地球大约由$$10^{50}$$个原子构成，也就是说给地球上的每一个原子分配一个哈希值，还有剩余。

碰撞阻力是指很难找到两个不同的输入，经过SHA-256计算后得到相同的哈希值。 注意，这里没有说不可能找到，而是很难找到。因为输入空间是有限的，2的256次方，而输入空间是无限的，在理论上是可以找到的。但是在实际中，就算调用全世界的计算机来做运算，算到地球爆炸那一天都不一定能找到满足条件的输入，因此说在实际操作中很难找到哈希值相同的两个不同输入。

隐秘性

隐秘性是指通过H(x)无法推算出x。这样保证了哈希函数的单向性，x经过SHA-256计算得到H(x)，但是想要通过H(x)逆运算得到x是不可行的。

谜题友好性

比特币中矿工挖矿，就是在解一个谜题，谁先解出来谁就拥有了记账权，就会得到比特币奖励。为了保持公平性，这个谜题肯定不能有最优解，只能通过暴力运算的方法来解题。

谜题友好性是指想得到满足某个条件的H(x)，只能蛮力求解x，没有什么优美解法。

举个例子，有个谜题是求一个输入x, 使得 $$ H(x)<2^{128} $$ 我想解这个谜题，并没有什么优美的解法，我只能通过暴力运算的方法，不断试各种不同的输入x1,x2,...，直到求得xn使得 $$ H(x_n)<2^{128} $$

数字签名

我们日常生活中的需要签名的场景，比如很多材料需要给领导审批签字，领导的这个签名代表了领导已经审批并批准了该文件，签名将领导的公信力赋予一份文件，即领导为这份文件背书。

比特币中的数字签名是在你发起一笔交易的时候，证明你对即将支付的比特币拥有支配权。 也就是说你得证明这些币是你的，你才能转账给别人，数字签名就是为了干这事的。

数字签名采用了非对称加密算法，首先我们了解一下非对称加密算法和对称加密算法的区别。

对称加密算法在加密和解密两个环节用的是同一个密钥，比如你事先知道我的密钥，我用同样的密钥加密一条消息并发送给你，你用密钥解开密文就可以看到我的消息。对称加密的缺点是一个密钥同时掌握在两个人手里，易丢失，难以保证安全性。

而非对称加密算法，包含两个密钥：公钥和私钥，公钥是公开的，所有人都可以看到，私钥则是自己保存的。

在场景1中，小明想要发一条消息给所有人，首先小明公开自己的公钥，然后用自己的私钥加密消息并把密文发布出去，知道小明公钥的所有人都可以用公钥来验证这条消息，能够证实这条消息确实是小明发出来的。相反，大家想要给小明发消息，可以用小明的公钥加密一条消息，密文只有小明用自己的私钥能够解密。

在场景2中，如果是小明和小花都希望双方的通信消息是加密的，则小明生成公钥A和私钥A，小花生成公钥B和私钥B，公钥是公开的，双方互相知道对方的公钥。小明想要发消息c给小花，用小花的公钥B加密消息c，把密文cx发给小花，小花用自己的私钥B解密cx，得到消息c。相反，小花要发消息d给小明，就用小明的公钥A加密消息d生成密文dx发送给小花，小明用私钥A解密dx后得到消息d。

在比特币系统中，当你发起一笔转账交易的时候，用你的私钥签名，将交易信息和私钥广播发送给所有人，所有人都可以用公钥来验证签名，从而证实这笔交易确实是由你发出的。

小结

以上介绍了比特币中使用的密码学基础知识，其中哈希函数具有三个特性：碰撞阻力、隐秘性和谜题友好性，数字签名则通过非对称加密算法提高了消息发送的安全性。

参考文献：

1. 北京大学肖臻老师《区块链技术与应用》公开课
2. 《区块链 技术驱动金融：数字货币与智能合约技术》[美] 阿尔文德·纳拉亚南（Arvind Narayanan），约什·贝努 等 著，林华，王勇，帅初 等 译

欢迎大家提出问题，批评指正。