区块链知识点总结BTC-2,3 密码学基础和数据结构 （北大肖臻老师）
说明：这些都是北大肖臻老师在B站上视频的总结和汇总，全网最全版本，希望可以帮助大家了解区块链，掌握区块链知识
第一节 课程简介
区块链不等于比特币，比特币只不过是基于区块链的一种加密货币。
第二节 BTC-密码学原理
比特币叫做加密货币，但是实际上是”不加密“的，包括转账等操作都是公开的。
比特币中主要是用到了密码学中两个功能，一个是哈希，一个是签名。
1 哈希
密码学中用到的哈希函数被称为cryptographic hash function。
它有两个重要的性质，一个是collision resistance，这里的collision是指哈希碰撞，如果有两个输入x和y，x不等于y，但是H(x)=H(y)，这就是哈希碰撞，两个不同的输入，算出来的哈希值是相等的。
哈希碰撞是很常见的，像我们使用过程中就会遇到哈希碰撞，不同的输入可能会被映射到哈希表上的同一个位置。一般来说，哈希碰撞是不可避免地，因为输入空间是远远大于输出空间的，比如说我们有一个256位的哈希值，那输出空间有多大呢？所有哈希值取值的可能性是2的256次方，这就是输出空间。但是输入空间可以是无限大的，所以它是有任意多种输入的可能性。按照鸽笼原理，必然会出现有两个输入映射到同一个输出的情况。
我们这里说的不是不会出现collision resistance，意思是没有什么方法人为的去制造哈希碰撞。也是就没有什么方法去找H(x)=H(y)，除非蛮力求解，brute-force 遍历取值来找。但是如果输入空间比较大，那工作量可太大了。
那么这个性质有什么用呢？它可以用来用一个message求digest，比如我们有一个message叫m，他的哈希值为H（m），这个哈希值可以认为i是message digest ，用来检测对这个message的篡改，比如说有人改这个message，那么它的哈希值就会发生变化，那么这个collision resistance就是说你找不到m’，使得这个m’取哈希之后，和原来的哈希值恰好相等。没有办法篡改内容而又不被检测出来的。
有一点注意没有那个哈希函数在数学上证明是collision resistance的，也就是我们说着这个冲突是证不出来的，只能靠实际的经验。有些哈希函数经过长期的实践检验，世界上这么多密码学专家，谁也没有找到人为制造哈希碰撞的方法，所以我们就认为这些哈希函数是collision resistance的。
也有一些哈希函数，以前我们是collision resistance的，但是后来大家找到了制造哈希碰撞的方法，这里面很著名的一个例子就是MD5，它曾经是个很流行的哈希函数，原来我们以为他是很安全的，但是现在我们已经知道如何制造哈希碰撞了。
第二个性质hiding，hiding是说哈希函数的计算过程是单向的，是不可逆的，给定一个输入x，可以算出他的哈希值H（x）。但是从哈希值没法反推出原来的输入x，也就是说这个哈希值没有透露有关这个x的任何信息。但是如果想知道这个输入也是有办法的，还是可以用蛮力的方法，挨着输入对比。hiding这个性质成立的前提是这个输入空间要足够答，使得这个蛮力求解的办法是不可行的，而且这个输入的分布要比较军援，各种可能的分布是差不多的，如果这个输入空间虽然是很大，但是大多数情况下，集中在几个值也是不行的。
hiding这个性质有什么用呢？它可以和这个collision resistance结合一起用来实现digital commitment，有时候也叫做digital equivalent of a sealed envelope。
现实生活中sealed envelope是做什么的呢？比如说有一个人说它可以预测股市，怎么证明这个人预测是否准确呢，一种办法是在电视台发布说哪只股票涨停，第二天可以看一下是否真正涨停，这样做有什么问题吗？如果你预测结果提前公布了可能会影响股市，比如说会买很多，变成涨停了。这说明预测结果不能够提前公开，但是你第二天公开，那怎么知道这个结果有没有被篡改过？这个就要用到sealed envelope，你把预测结构写出来放到一个密封的信封里，然后把这个信封放到权威的第三方来保管，等第二天收盘之后再验证准不准。
但是在电子世界里怎么实现呢？把预测结果作为输入x，算出一个哈希值来，把这个哈希中公布出去，因为我们有hiding性质，我们拿到这个哈希值不知道是什么，又因为有这个collision resistance性质，所以我们这个预测结果是不可能篡改的，这个起到一个sealed envelope的性质。操作中要注意我们hiding这个性质前提是输入空间比较大，分布比较均匀，如果输入不满足这个性质，常用的输入是后面拼接一个随机数，然后一起取哈希，H（x || nonce），保证这个输入是足够随机的，然后输入也是足够均匀的。
处了以上两个性质以外，比特币中用哈希函数还要求第三个性质，叫puzzle friendly ，他的意思是说哈希值的计算事先是不可预测的，如果你预测它落在那个范围之内，没有好办法，只能一个一个去试一下。如果说你想得到一个哈希值前面k的0后面是x，我们根本不知道那个输入输出是这个。这个性质为什么叫puzzle friendly，后面会讲到挖矿，挖矿实际上是找一个nonce，nonce和区块的块头里其他信息合在一起作为输入，取出一个哈希来，哈希值要小于等于一个指定的目标阈值。即下图
比特币就是区块链，区块链就是一个一个区块组成的链表，每个区块有一个块头，里面有很多域其中有一个域是我们可以设置的随机数nonce，挖矿的过程就是不断地取随机数，使得block取哈希后落在指定的范围之内。
比如下图，下图是个指定的输出空间,我们要求算出的哈希值只有落在前面这一点才是合法的。
puzzle friendly就是说这个挖矿的过程没有捷径，只能不停的试大量的nonce才能找到符合要求的解，所以这个过程才可以被用来做工作量证明，叫做proof of work（POW）。你挖到矿了找到符合要求的nonce一定是因为你做大量的工作，其他没有捷径.。
但是有人找到这个nonce，发布出去，其他人验证是不是符合要求很容易，只有算一次哈希值就行了
挖矿很难，验证很容易。(difficult to solve ,but easy to verify)
比特币中用的哈希函数叫作SHA-256(secure hash algorithm )以上三个性质它都是满足的。
2.签名
日常生活中想开个账户就要去银行办理，而比特币是去中心的，它开账户每个用户自己决定开户，不需要任何人批准。
在比特币系统中开账户:在本地创立一个公私钥匙对(public key ,private key)，这就是一个账户。公私钥匙对是来自于非对称的加密技术(asymmetric encryption algorithm)。
之前是对称加密技术，比如说两个人之间通信是可能被窃听的，那我们事先可以商量一个密钥，我把这个信息加密后发给你，你收到后再用密钥解密，加密和解密用的是一套系统，所以是对称体系。但是进行通信前要把这个密钥给双方，也就是双方都要提前知道才行，传输过程中可能被窃听，所以不方便。
所以就提出非对称加密，有一个公钥和一个私钥，加密用公钥，解密用私钥，加密和解密用的是同一个人的公钥和私钥，都是接收方的公钥和私钥。
这有什么好处呢？公钥是不用保密的，私钥要保密，因为解密是用私钥，但是私钥只要保存在本地就行，不用传给对方，给你信息的那个人不需要知道你的私钥。这就解决了通信不方便问题。比特币系统中你要创建一个账户，就在本地产生一对公钥和私钥。公钥相当于银行账号，别人转账只要知道你的公钥就行，私钥相当于你的账户密码，知道私钥可以把账户上钱转走。
公钥和私钥是用来做签名的。
假如A想向B转10个比特币，A把交易放在区块链上，别人怎么知道这笔交易是A发起的呢?这就需要A要用自己的私钥给交易签名，其他人收到这笔交易后，要用A的公钥去验证签名正确性。签名用私钥，验证用公钥，用的仍然是同一个人的。
恰好产生的公私钥相同怎么办？创建账户产生相同公私钥的可能性微乎其微，所以大量创建账户来窃取其他人账户是不可行的。可能性太小了，即使有一台超级计算机一直算，老师说产生和区块链上相同的公私钥比地球爆炸的概率还小。
我们这里假设产生公私钥时是有一个好的随机源(a good source of randomness)，产生公私钥的过程是随机的，如果随机源不好，就有可能产生相同的公私钥。比特币中用的签名算法，不仅是生成公私钥的时候要有好的随机源，之后每一次签名时也要有好的随机源。只要有一次签名用的随机源不好的话，就有可能泄露私钥。
比特币系统中一般是先对一个message去哈希，在对哈希值签名。
第三节 BTC-数据结构
这里用到的一个重要概念就是哈希指针。
普通指针存储的是某个结构体在内存中的地址。假如P是指向一结构体的指针，那么P里面存放的就是该结构体在内存中的起始位置。而哈希指针除了要存地址之外，还要保存该结构体的哈希值H()。这样做的好处是:从哈希值这个哈希指针，不仅可以找到该结构体的位置，同时还能够检测出该结构体的内容有没有被篡改，因为我们保存了它的哈希值。
比特币中最基本的结构就是区块链，区块链就是一个一个区块组成的链表。区块链和普通的链表相比有什么区别呢:
①用哈希指针代替了普通指针(B block chain is a linked list using hash pointers)
区块链第一个区块叫作创世纪块(genesis block) 最后一个区块 是最近产生的区块(most recent block) 每一个区块都包含指向前一个区块的哈希指针 。里面都有一个hash point。
这种数据结构的好处是什么？这个取哈希的时候是把整个哈希内容合在一起取哈希，
比如要求最后一个，要把前面那个区块，包括里面的hash point 加上一起去哈希求出来指针。
一个区块的哈希指针怎么算:是把前面整个区块的内容，包括里面的hash pointer ，合在一起取哈希值。通过这种结构，可以实现tamper-evident log。如果有人改变了一个区块的内容，后面一个区块的哈希指针就对不上，因为后一个区块哈希指针是根据前一个区块的内容算出来的，所以后一个哈希指针也得改，以此类推，我们保留的是最后一个哈希值也会变化。而最后这个哈希值是我们保存下来的，所以这个数据结构的好处是我只要记住最后这个哈希值，就可以检测出对区块链中任何部位的修改。
这个是区块链和普通链表的区别，区块链是牵一发而动全身，而普通链表不知道改变了。
所以有这个性质，比特币没有要保存所有区块的内容，可以只保留最近的几千个区块。如果要用到以前的区块，可以向系统中其他节点要这个区块。有些节点是有恶意的（去中心化）
怎么判断?这里要用到哈希值一个性质，如下:
其他节点给你一个区块，如何判断它是正确的?算出它的哈希值，与保留的区块的哈希值对比，即可。
比特币中的另外一个结构是:Merkle tree，可能没有听说过
这种结构的好处:**只要记住根哈希值，就能检测出对树中任何部位的修改。**只要有一个区块被纂改了，那么它的哈希值就对不上了，往上那个，上面那个哈希值也要被修改，层层传导到根哈希值。
但可能听过binary tree。
它们的区别:①用哈希指针代替了普通指针。
比特币当中各区块之间用哈希指针连接在一起，每个区块所包含的交易组织成一个merkle tree的形式，最下面一行data blocks每个区块实际上是一个交易（tx），每个区块分为两部分，分别是块头和块身(block header ,block body)。块头里面有根哈希值，每个区块所包含的所有交易组成的merkle tree的根哈希值存在于区块的块头里面，但是，块头里没有交易的具体内容，只有一个根哈希值，块身（block body）里面是有交易的列表的。
merkle tree 的作用:①提供merkle proof
比特币中的节点分为两类:全节点(保存整个区块的内容，即块头块身都有，有交易的具体信息)和轻节点(例如手机上的比特币钱包)(只有块头)
这时存在一个问题:如何向一个轻节点证明某个交易是写入区块链的?
（比如说你向我买一些东西，需要给我转一笔钱，你告诉我说你转给我钱的交易已经写到区块链中去了，这个支付已经完成了，我是个轻节点，我怎么知道你这个交易已经写入到区块链上去了？）
这时需要用到merkle proof :找到交易所在的位置(图中最底行的其中一个区块)，这时该区块一直往上到根节点的路径就叫merkle proof。
最上面一行是小型的区块链，该图展现的是一个区块的merkle tree，最下面一行是包含的交易。假设某个轻节点想知道图中黄色的交易，是否包含在了merkle tree里面。该轻节点没有包含交易列表，没有这颗merkle tree的具体内容，只有一个根哈希值（因为根哈希值是保存在block head里面的，这个轻节点是有的）。这时轻节点向一个全节点发出请求，请求证明黄色的交易被包含在这颗merkle tree里面的merkle proof。全节点收到这个请求之后，只需要将图中标为红色的这三个哈希值发给轻节点即可。有了这些哈希值之后，轻节点可以在本地计算出图中标为绿色三个哈希值。首先算出黄色交易的哈希值，即它正上方的那个绿的哈希值，然后跟旁边红色的哈希值拼接起来，可以算出上层节点绿色的哈希值。然后再跟它旁边红色哈希值拼接，再算出上层绿色哈希值，再拼接，就可以算出整棵树的根哈希值。轻节点把这个根哈希值和block header里的根哈希值比较一下，就能知道黄色的交易是否在这颗merkle tree里。
全节点在merkle proof里提供的这几个哈希值，就是从黄色的交易所在的叶节点的位置到树根的路径上用到的这些哈希值。轻节点收到这样一个merkle proof之后，只要从下往上验证，沿途的哈希值都是正确的即可。(验证时只能验证该路径的哈希值，其他路径是验证不了的，即该图中红色的哈希值是验证不了的)
这样是否不安全呢?假如黄色交易被篡改，它的哈希值发生了变化，那能不能调整旁边红色的哈希值，使得它们拼接起来的哈希值是不变的呢?不行，根据collision resistance，在人为制造哈希碰撞，因为根本制造不出来，这是不可行的。
我们刚才说的是merkle proof可以证明merkle tree里面包含了某个交易，所以这种证明又叫proof of membership或 proof of inclusion。
对于一个轻节点来说，验证一个merkle proof 复杂度是多少?假设最底层有n个交易，则merkle proof 复杂程度是θ(log(n))。
如何证明merkle tree里面没有包含某个交易?即proof of non-membership。可以把整棵树传给轻节点，轻节点收到后验证树的构造都是对的，每一层用到的哈希值都是正确的，说明树里只有这些叶节点，要找的交易不在里面，就证明了proof of non-membership。问题在于，它的复杂度是线性的θ(n)，是比较笨的方法。
那有没有高效的方法呢？
如果不对叶节点的排列顺序不做改变的话是没有办法的。因为我们要找的那个交易在n个交易当中，只能把这n个交易（叶节点发过去）
如果对叶节点的排列顺序做一些要求，比如按照交易的哈希值排序（比如说从小到大）。每一个叶节点都是一次交易，对交易的内容取一次哈希，按照哈希值从小到大排列。要查的交易先算出一个哈希值，看看如果它在里面该是哪个位置。比如说在第三个第四个之间，这时提供的proof是第三个第四个叶节点都要往上到根节点。如果其中哈希值都是正确的，最后根节点算出的哈希值也是没有被改过的，说明第三、四个节点在原来的merkle tree里面，确实是相邻的点。要找的交易如果存在的话，应该在这两个节点中间。但是它没有出现，所以就不存在。其复杂度也是log（n）形式的，代价是要排序。排好序的叫作sorted merkle tree。比特币中没有用到这种排好序的merkle tree，因为比特币中不需要做不存在证明。
这节讲了比特币中两种最基本的结构:区块链和merkle tree，都是用哈希指针来构造的。除了这两种之外，哈希指针还能用另一个方面。
只要一个数据结构是无环的(非循环链表)，都能用哈希指针代替普通指针。有环的话存在一个问题，他们的哈希值没法计算，没法确定一个哈希值固定的区块。
有环的就成了循环依赖了，一直循环，哪个区块都定不下来。