比特币-密码学原理以及数据结构

1.比特币概述

比特币是中本聪在2008年发明的一种去中心化的点对点电子支付系统。是区块链技术的第一个应用。

比特币是国际交易中的价值传递的载体， 优于传统的国际贸易货币兑换体系。

技术上来说，包含了密码学，计算机网络，金融经济等学问，是各方面技术以及经济学的综合运用。

开创性地发明了区块链技术。传统数据结构中的链表中的指针就是单纯地指向前一个区块的地址，在区块链中，中本聪开创性地讲密码学原理hash与指针结合发明了hash指针，hash指针不光能够指向前一个区块，还包含前一个区块内容的hash值，从而保证区块链中的任意一个位置的内容被更改都可以被监测到，实现了区块链的不可篡改性。

2.比特币的密码学原理

2.1 hash

hash函数的几个性质：

• collision resistance
• hiding
• puzzle friendly

collision resistance是指无法人为去构造两个不同的输入，使得这两个输入算出来的hash值是相等的。这个性质目前从数学理论上是没法证明的，是通过经验去保证的。世界上有很多密码学的专家，谁也没有找到人为制造hash碰撞的方法，所以我们人为这些函数是具有collision resistance性质的。

hiding是指hash函数的计算过程是单向不可逆的。hiding这个性质成立的前提条件是输入空间足够大，分布足够均匀。给定x可以算出H(x)，但是给定H(x)没有办法反推出x，即H(x)中没有保存x的相关信息。

puzzle friendly是指hash值事先是不可预测的，即给定一个x，你很难猜出这个H(x)是多少，也很难确定这个hash值是在哪个范围之内，要想知道的话，就只能一个一个去试。

比特币中使用的hash函数是sha256，满足以上三个性质。

2.2 签名

我们可以通过密码学算法生成一个密钥对(公私钥)，用私钥对交易进行签名，用公钥来进行验证，以告诉别人这个交易确实是由我(私钥持有人)所发起的。

在比特币系统中可以简单把公钥理解为账户，私钥理解为密码。通过公钥是没有办法推导出私钥的，但是公钥却能够通过私钥使用椭圆曲线乘法推算出来。所以私钥是千万不能够泄露的，一旦泄露，你的btc资产将会非常危险。

3.数据结构

与传统的数据结构相比，是把普通指针替换成了hash指针。

hash指针不光能存储地址，还能存储hash值(用于检测内容是否被篡改)。

3.1区块链

区块链是比特币中的最主要的数据结构。相当于用hash指针替换了普通指针的链表。

只要前面任意一个区块中的任意内容被修改，那么最后的H()哈希值就会改变。从而实现防篡改的目的。

3.2 Merkel tree

将binary tree中的普通指针替换为了hash指针。

图中的TX是一个个的交易，通过merkel tree将其组织起来，最终会得到一个根hash指针，这个hash指针存储在block header之中。Merkel tree中任何部位被修改，都会引起这个根hash值得变化，从而实现防篡改的功能。

此外，Merkel tree还能够提供Merkel proof。

比特币中有两类节点：

1. 全节点：保存整个区块的内容，包含block header和block body，有交易的具体信息。
2. 轻节点：只保存一个block header，比如比特币钱包的应用。

Merkel proof就是用于向轻节点提供证明，证明某个交易是写入到区块链中的。从需要证明的交易一直往上到根节点，这条路径就是Merkel proof。

轻节点向全节点请求途中红色部分的hash值，计算出绿色部分的hash值，一直到根hash值，如果根hash值与轻节点block header中所保存的Merkel tree的根hash值是一样的，就说明这个交易是在区块链里面的。

比特币中，Merkel tree是没有排序的，所以这里的Merkel proof只能用来做交易的存在性证明，不能用于做不存在证明，而比特币系统中也不需要提供交易的不存在证明。

对于排好序的Merkel tree，如何做不存在证明？

找到交易在排好序中的位置，提供它相邻两个交易的Merkel proof，证明这两个交易是存在的，由于交易是排好序的，且这相邻两个交易是连续的，那么需要证明的这个交易就不可能在他们之间。