密码学原理

比特币是加密货币，但是其实是公开的？

比特币用到的两个加密技术：

  • 哈希
  • 签名

比特币的hash function：SHA-256

  • s: secure
  • h: Hash
  • a: algorithm

Hash

哈希方法的两个特性：

  • Collision resistance(哈希碰撞)
  • hiding

除此之外比特币还用到了个独有的特性

  • puzzle friendly

Collision resistance

其实就是哈希值的冲突

Hash(x)=Hash(y)

collision free: 没有高效的方法，人为制造碰撞，也意味着很难篡改内容而不被发现

符合这个性质的哈希函数为collision free function，但是无法证明是collision free的，可以证明不是collision free的,比如MD5已被证明为可构造的

hiding

无法通过输出反推输入，已知H(x)值和哈希函数，很难得到x，除非依靠大量的算力去穷举

但是有两个前提：

  • 输入空间足够大
  • 输入分布均匀

这里举一个例子：某个人证明自己预测股票的能力，他可以提前一天告知电视台自己对明天的预测结果，电视台公布给大众，等到明天去验证正误。但是带来了一个问题，他的预测被公众得知后，已经影响了明天的股票价格。这里就可以用这种hiding的原理，它将自己的预测构造成hash，把hash公布出去，但谁也没办法反推出他的预测内容，只要到明天结果公布后去比对他的预测hash与该hash即可。

puzzle friendly

没有捷径获得指定结果范围的输入

先简单介绍一下挖矿：

挖矿就是去找一个nonce(一个随机数值,是block header的一部分) 使得H(block header)<=target,这就是一个工作量证明

之所以是工作量证明就是因瓦诶这条性质使得获得nonce只能依靠穷举，无捷径可走

difficult to solve, but easy to verify

挖矿很难，但是很容易验证挖矿的结果

签名

签名由两部分组成：

  • public key
  • private key

是一种非对称的加密体系，两种应用方法：

  1. 用接收方的公钥加密，发送给接收方，接收方用自己的私钥解密（保证消息不泄露）
  2. 用发送方的私钥加密，发送被接收方，接收方用发送方的公钥解密（保证消息不被篡改，也保证是发送发出的）

密钥的构造使用了hash方法，保证了几乎不可能存在两个相同的公私钥

比特币的加密方式

数据结构

比特币主要是用到两种数据结构：

  • hash pointers
  • merkle tree

hash pointers

哈希指针，哈希指针除了包括block的地址外，还包括block的hash值

block chain is a linked list using hash pointers

一个哈希指针内的哈希值由前一整个块的内容生成，要想改块内容，后面的hash都得改

比特币中有些节点并不保存整个链，仅保存最近的一部分，需要之前的内容时会想其他节点询问，通过哈希值的验证就可以判断拿到的是不是正确的（因为有恶意节点的存在）

merkle tree

类似二叉树，只是指针变成了hash pointers

全节点与轻节点

  • 全节点保存block header+blocke body
  • 轻节点仅保存block header

轻节点如何验证对方已经给自己转账了呢？

首先会要求转账方发送给自己一个merkle proof，是提条从交易节点一直到根节点的路径（下图绿色所示）

然后自己去向全节点请求一些节点的哈希指针（下图红色所示）

然后根据tx交易块获得hash指针，再加上请求的hash指针值，可以求得上一个的hash值，一直推到根节点，再与header中记录的根节点的hash值比较，一致则交易信息正确

时间复杂度log2n

如何判断交易不存在呢？

方法一

拿到整棵树，遍历叶节点，判断每个叶节点的正确性并查看有没有某个交易存在

时间复杂度为n

方法二

需要时sorted merkle tree 即树是根据hash值排序的（比特币没有证明不存在的需求，所以未排序）

可以根据待验证交易的hash 算得其处于哪两个交易节点之间，然后证明这两个交易节点是正确的，name该交易自然就是不存在的。