比特币中的密码学

比特币主要应用了密码学中的两个技术：哈希、签名

哈希

哈希函数性质：
collision resistance：很难人为的制造哈希碰撞，也就是说很难人为去制造一个哈希值一样的输入。
hiding：从哈希值无法反推到输入（前提是输入空间足够大，且分布均匀）。
puzzle friendly：很难通过输入值来预测哈希输出。
比特币中使用的哈希函数：SHA-256。

签名

在比特币中，创建一个账户只用在本地创建一个公私钥对即可。私钥用于签名，认证比特币中的交易身份。

比特币中的数据结构

区块链

用哈希指针所形成的链表：

区块链.jpg

上图就是一个小型区块链，最左边的区块是系统中产生的第一个区块，叫做创世纪块，最右边的区块是最近产生的区块。每一个区块分为两部分：块头和块身。每一个区块都包含指向前一个区块的哈希指针（前一个区块整个取哈希），存在块头里。最后一个区块也有一个哈希指针，保存在系统里。
使用哈希指针的好处是，只要我们保存好系统里最后一个区块的哈希指针，就可以防止任何人试图修改整条区块链任何位置的信息（改了任何地方，都会导致与系统里保存的最后一个区块的哈希指针对不上）。有了这个性质后，比特币中有些节点就不一定要保存整条区块链的内容了，比如说它可以只保存最近的几千个区块，以前的区块就不用存了。如果要用到以前的区块，可以向系统中的其它节点要这些区块，并且可以通过哈希指针判断其它节点提供的区块是否正确。

Merkle tree

Mercle tree.jpg

在比特币中，各个区块通过哈希指针连接在一起，每个区块所包含的交易是组织成一个Merkle tree，如上图，蓝色的链表就是一个小型的区块链，而下方就是其中一个区块里的Merkle tree，树的最底层就是每一笔的交易，对这些交易取哈希，然后形成的二叉树就是一个Merkle tree。树的根哈希值存在对应区块的块头里，而具体的交易信息则存在块身里。

比特币里的节点分为两类，一类是全节点，它包含整个区块的信息。另一类是轻节点（手机钱包），它只保存了块头，所以它并不知道本区块具体有哪些交易。当轻节点需要证明它所在区块里存在某笔特定交易时，如上图，它会向某个全节点请求可以证明黄色交易存在的Merkle proof（相邻路径的哈希值，也就是红色的哈希值，如果这个交易不存在，这个Merkle proof肯定是不存在的，但有人可能会冒充），然后轻节点会自己计算上图绿色的哈希值，最后计算出根哈希值，并与存在块头里的根哈希值进行比较，如果哈希值一样，则说明这笔交易存在。
另外一提，轻节点如何证明A交易不存在？对Mercle tree的叶子节点按哈希值大小排序，然后算出A交易的哈希值，然后向全节点所要与这个哈希值相邻的两个交易的Merkle proof，如果轻节点通过这两个proof可以计算出正确的根哈希值，则说明这两个交易在Merkle tree里本就是相邻的，不存在A交易。比特币并不支持这样的方法，因为它的叶子节点不是有序的。