首先介绍比特币系统中用到的密码学原理。比特币被称为叫加密货币，但其实区块链上所有的交易内容都是公开的，包括账户的地址、转账的金额。比特币中主要用到的密码学的两个个功能，一个是哈希，另外一个是签名。

哈希函数的工作原理大家应该很熟悉。密码学中的hash函数被称为cryptographic hash function。它有2个重要的性质，一个叫做collision resistance一个叫做hiding。除了密码学中要求的这两个性质外，比特币中用到的哈希函数的性质还有puzzle friendly和Secondary Preimage Resistance。

Collision Resistance是指哈希碰撞，如果有2个输入X和Y且X不等于Y，但是哈希函数函数h算出来的h(X)等于h(Y)，那么这就叫做哈希碰撞。哈希碰撞指，2个不同的输入算出来的hash是相等的。

哈希碰撞是很常见的，一般哈希碰撞是不可避免的，因为输入空间远远大于输出空间。比如，对于一个256位的哈希值，输出空间即所有哈希值的取值可能性是2的256次方，输出空间就只有这么大。但是输入空间可以是无限大的，所以它有任意多种输入的可能性。按照鸽笼原理，必然会出现有2个输入被映射到同一个输出的情况。所以collision resistance并不是指不会出现hash碰撞，而是指没有什么高效的方法来人为地去制造哈希碰撞。给定一个x，没有什么好办法能找到另外一个y使得x和y的hash值恰好相等。一定要找的话可以用蛮力求解brute force的方法，比如对于x和哈希值h(x)，遍历所有输入的可能性，然后看看哪一个算出来是相等的。但是如果输入空间比较大，brute force并不实际。

Collision resistance这个性质有什么用呢？它可以用来对一个Message求digest。比如说我们有一个Message叫M，我们取它的哈希值H(M)。这个哈希值可以认为是这个Message的digest，用来检测对这个Message的篡改。如果有人改这个Message的内容，它的哈希值就会发生变化。collision resistance性质保证你找不到另外一个使得取hash之后跟原来的hash值恰好相等，所以没有办法能够篡改内容而又不被检测出来。比如你有一个很大的文件，你想把它存放到某个云存储服务。将来你用到的时候，再把它下载回来。那么你怎么知道你下载的版本跟你当初上传的版本是一样的呢？这就可以用到这个哈希函数的collision resistance性质。在你上传这个文件之前，算一个哈希值出来，将这个哈希值保存在本地。将来你下载之后，再算一个哈希值跟原来你存的哈希值比较，如果是一样的，说明上传的这个文件没有被篡改。

有一点需要注意，没有哪个哈希函数能够在数学上证明是collision resistant。也就是说这么重要的一个性质从理论上是证不出来的，只能靠实践中的经验。有些哈希函数经过长期的实践检验，世界上有那么多密码学的专家谁也没能找到人为制造哈希碰撞的方法，所以我们就认为这些哈希函数是collision resistant。也有一些哈希函数以前我们认为是collision resistant，但是后来大家找到了制造哈希碰撞的方法。这里面一个很著名的例子就是MD5。MD5曾经是个很流行的哈希函数，大家原来以为它很安全的，但是现在已经不行了，我们已经知道怎么去人为地制造哈希碰撞。

密码学用的hash函数还有第2个性质叫做Hiding。Hiding是说哈希函数的计算过程是单向的、不可逆的。给定一个输入X可以算出它的哈希值H(X)，但是从这个哈希值H(X)没有办法反推出原来的输入X。换句话说，这个哈希值没有泄露有关这个输入的任何信息，这叫做Hiding。当然，如果想要知道这个输入也是有办法的。还是用brute force把这个输入所有可能的取值遍历一遍，看看哪个hash值跟这个相等，就能猜出来原来的输入。所以hiding性质成立的前提是，输入空间要足够的大，使得brute force的求解的方法是不可行的。而且这个输入的分布要比较均匀、各种取值的可能性都是差不多的。如果这个输入空间虽然是很大，但是取值都是集中在少数几个值，那么也是比较容易被破解的。

hiding性质有什么用呢？它可以和collision resistant性质结合在一起，用来实现digital commitment。digital commitment也被称为digital equivalent of a sealed envelope。我们先说一下现实生活中sealed envelope是干嘛用的。比如有一个人说他能够预测股市，可以预测第2天哪些股票会涨停。证明这个人的预测是否准确的一种办法是，他提前一天在电视台上公布预测结果：我预测明天某某股票会涨停。第2天收盘之后，检查这个股票是不是真的涨停了，就知道预测是否准确。但这样做的问题在于，前一天做出的预测可能会影响第2天的股市行情。比如巴菲特前一天说某某股票会大涨，那么大家都会去购买，从而人为导致这支股票大涨。如果巴菲特的对头唱反调，通过某些手段让这支股票大跌，这种相反的结果也是人为造成的。可是如果等第2天开盘之后，你再公开自己前一天的预测结果，这样如何使大家相信你是前一天做出的预测呢？sealed envelope可以用来解决这个问题。前一天将预测放入一个封口的信封里，将它交给第三方机构保管。第2天收盘之后，这个第三方机构再打开信封来验证预测是否准确。电子世界里，预测可以视为输入x，hash值h(x)可以视为这个sealed envelope。首先将哈希值h(x)公开，等到要验证预测的时候再公布x，因为collision resistance，可以保证与哈希值h(x)相对应的输入就是x。实际使用的时候有些小细节需要注意。比如股票一共只有几千支，如果将一支股票作为预测，那么输入空间很小，只有几千个。可以将这个股票和一串随机数nonce进行拼接，这样就能保证输入空间很大，从而保障brute force不容易将其破解。

如果给定哈希函数的输入集合R和与之对应的输出集合Y，其中R是从高度分散分布的集合中选取的。那么对于H(R|X) ∈Y，很难有高效的方法找到集合X（即R的输入范围），也就是说只能brute force来定位到输入范围。这个性质就叫Puzzle Friendly，假如哈希值是00...0XX...X，一样事先无法知道哪个值更容易算出这个结果，还是要一个一个带入。

Puzzle Friendly常用与比特币挖矿。比特币挖矿的过程中实际就是找一个nonce，nonce跟区块的块头里的其他信息合一起作为输入，得出的哈希值要小于等于某个指定的目标预值。H(block header)≤target。block header 指块头，块头里有很多域，其中一个域是我们可以设置的随机数nonce，挖矿的过程是不停的试随机数，使得block header取哈希后落在指定的范围之内。

puzzle friendly是指挖矿过程中没有捷径，为了使输出值落在指定范围，只能一个一个去试。所以这个过程还可以作为工作量证明(proof of work)。挖矿很难，验证很容易(Difficult to solve, but easy to verify)。

Secondary preimage resistance是指给定一个哈希函数H和一个输入值x，很难找到另一个不等于x的输入值x’使得H(x)=H(x’)。这个性质可以防止攻击者伪造相同哈希值的消息。

比特币中用的哈希函数叫作SHA-256(secure hash algorithm )以上性质它都是满足的。

SHA-256由National Institute of Standards & Technology发明。SHA-256的输入哈希长度有256bits。SHA-256在比特币中的用处有两个，Proof of Work算法和创建比特币地址。

数字签名是一种用于鉴别数字信息的方法，它可以证明信息的发送者身份和信息的完整性并且防止信息被篡改或者伪造。数字签名是基于非对称加密算法的，也就是说，发送者用自己的私钥对信息加密生成一个签名，接收者使用发送者的公钥对签名进行解密。

具体步骤：首先发送者对原文使用哈希函数取得哈希值，使用自己的私钥对原文哈希值进行加密，生成一个字符串数字签名。然后发送者将原文和数字签名一起发送给接收者。接收者对收到的原文使用哈希函数取得哈希值，另外接收者还使用发送者的公钥对收到的数字签名进行解密，获得加密之前的原文哈希值。最后接收者将2个哈希值进行比较，如果相同就能够验证发送者身份并且信息完整安全。

创建账户产生相同公私钥的可能性微乎其微，所以大量创建账户来窃取其他人账户是不可行的。

我们假设产生公私钥时有一个好的随机源(a good source of randomness)，产生公私钥是随机的，如果随机源不好，就有可能产生相同的公私钥。比特币中用的签名算法，不仅是生成公私钥的时候要有好的随机源，之后每一次签名时也要有好的随机源。只要有一次签名用的随机源不好的话，就有可能泄露私钥。ECDSA就是比特币使用的签名算法。

ECDSA是Elliptic Curve Digital Signature Algorithm的简称，主要用于对数据（比如一个文件）创建数字签名。ECDSA当中有两个词需要注意：Curve（曲线）和Algorithm（算法），这意味着ECDSA基本上是基于数学的。并且，这些涉及非常复杂的数学原理。

使用ECDSA创建钥匙对的简要流程如下：随机生成一个数作为私钥，在ECDSA曲线上选取一个点作为原点G，计算出 $public\ key = secret\ key \times G$，将其作为公钥。

接下来简要介绍一下ECDSA的原理。Elliptic Curve的表达式为

ECDSA中使用的形式为

$4a^3+27b^2≠0$是为了避免奇点。

关于椭圆曲线需要了解的另外一个事情是椭圆曲线点加法的表示方法。它是这样定义的：将一个点P和另外一个点Q相加将得到点S，如果我们从P到Q画一条线，并延长与曲线相交于第三个点R，则R为 S的负值，别忘记曲线是关于X轴对称的。在这种情况下，我们定义R=-S来表示R在 x轴上面的对称点。具体可以看下面这张图。

根据点的加法，我们就可以定义椭圆上的点的乘法：$Q=kG=G+G+⋯+G$

一个椭圆曲线乘法的特性是有一个点$Q=kG$。知道Q和G但是无法据此求出K，因为并没有椭圆曲线减法或者椭圆曲线除法可以使用。并且最终只是知道在曲线上面结束的点，但具体是如何到达最终这个点的过程也是不知道的。即便知道原点和终点也无法知道被乘数，这样的性质是ECDSA算法背后安全性的所有基础。这也被称为离散对数问题。

接着我们谈谈ECDSA是如何使用这个离散对数问题来生成签名的。对于ECDSA算法，首先你需要知道你的曲线参数$\{a,b,p,N,G\},y^2=x^3+ax+b (4a^3+27b^2≠0)$。N是曲线上面点的个数，G表示你选中的一个参考的起始点，可以是曲线上面的任意的一个点。用户随机生成一个数作为私钥，在ECDSA曲线上计算出$public\ key = secret\ key \times G$，将其作为公钥。这就是一个公私钥匙对。将公钥经过哈希和编码就能得到一个比特币地址。比特币地址是用来接收和发送比特币的一个标识，类似于银行账户。每个比特币地址都有一个对应的私钥，用来对交易进行签名和验证。

为什么选择椭圆曲线加密Elliptic Curve Cryptography (ECC)，而不是其他的算法如RSA呢？因为ECC产生的keys和签名更小、生成key更快、美国政府更支持。