北大-区块链与应用 Part 1
课程链接：https://www.bilibili.com/video/BV1Vt411X7JF
因为工作原因，想要对区块链进行一个较为系统性的学习，这里会记录上课过程中的一些笔记以及总结，可能会有错误，还望能够在评论区指正，谢谢。
BTC-密码学原理
哈希
比较基本的hash性质解释，这包含了
- Collision resistance (i.e. computationally difficult to find two values that would result in the same hash)
- Hiding (i.e. the hash function is one-way, i.e. one shall not be able to derive the input value x, from the result hash H(x), where H is the hash function that meets this criteria)
- Puzzle friendly (i.e. the computation of hash is not predictable, when trying to find x that would result in H(x), it should be computationally hard to solve, but easy to verify)
签名
同样是解释了AE的基本性质，未涉及到底层crypto的证明。
主要是阐述了公私密钥的生成以及使用，BTC中并非用来加密（较为传统的用法可能是使用AE交换Symmetric Encryption会使用到的密钥），而是用来签名。顺带提到了一嘴随机数生成的重要性，这块需要深挖。
BTC-数据结构
“链表”
Blockchain本身可以理解为一个Linked List，但是每一个节点当中会包含上一个block的hash，从而达到了tamper-evident logging（i.e. 任意对于链表中的更改都可以较为轻松的检测到，因为在一个index为1...x的区块链中，修改index=i where 0<i<x的block时，你同时需要修改index i...x block中的hash pointer。
Merkle Tree
概念上相比于二叉树，类似于Blockchain和普通链表的区别，同样是使用hash pointer代替了传统意义上的指针。
由data blocks（由于区块链中的应用，也可以成为交易/transaction）在最底层构成，在那之上的每一个node都是hash(left, right)，最终得到一个root hash。任何一个对于data block的更改都会导致root hash的变更。
Merkle Proof
在这之前，我们或许应该熟悉一下他的应用案例。
web3，区块链，加密货币这些名词的底层，是p2p网络（a.k.a. 去中心化）。这个p2p的网络中自然有形形色色的参与者，其中有一部分会承担运营整个网络的行为，将自己设置为full node。有full node自然也有lite node，他们的主要区别如下图（我也不知道为什么做这个图的人要用pros&cons来表示，看看就行了）
Proof of membership
可以理解为lite node是最轻量化的加入到网络中的方式，但由于资源受限，部分操作需要依赖于full node，比方说：A向B转了一笔钱，并且声明转账成功，这时候B想要验证，但由于是lite node，并不存储所有的交易数据，也自然无法得知特定block的Markle Tree的信息。这时，B会向一个full node发送请求，full node则会把下图中标为红色的hash发送给B，B可以根据待验证的交易，生成并且验证Merkle Root。
Proof of non-membership
上面的案例解释的是如何证明某一个transaction确实被写入到了区块链当中，而接下来的则是如何证明某一个transaction不在区块链当中。
需要知道的是，如果我们不对现有的Merkle tree进行更改，那么就只能通过获取到完整的tree，验证root hash之后再看Leaf node中是否有我们想要查找的那个transaction。
但是我们如果将Leaf node根据他们的hash排序，我们则可以将验证的时间复杂度降低到O(log(n))，如下：
假设待验证的transaction x有的hash为H_x, 那么我们去找到相邻于这个hash的Leaf node A和B，where H_a < H_x < H_B，之后要求full node提供H_a以及H_b的Merkle Proof，如果最终的hash计算出来符合Root hash，那么便证明了x并不在Merkle Tree当中（因为如果x在的话，那么他应该和A或者B成为相邻的Leaf Node，而如果A和B的Merkle Proof的结果和Root hash吻合，则代表A和B才是Tree当中的相邻Leaf Node，x并不存在。