北京大学肖臻老师区块链课程笔记
密码学原理
比特币是加密货币，但是其实是公开的？
比特币用到的两个加密技术：
- 哈希
- 签名
比特币的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
是一种非对称的加密体系，两种应用方法：
- 用接收方的公钥加密，发送给接收方，接收方用自己的私钥解密（保证消息不泄露）
- 用发送方的私钥加密，发送被接收方，接收方用发送方的公钥解密（保证消息不被篡改，也保证是发送发出的）
密钥的构造使用了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该交易自然就是不存在的。
非对称加密体系方案
使用非对称加密体系，央行发行货币，使用私钥加密，每个人可以用公钥验证真伪。
缺点
- 双重支付问题（double spending attack）
中心化方案
央行发行货币，每个货币有唯一ID，维护一个数据库，每次交易都要记录交易过程，以验证所花的货币在支付人手中。
缺点
- 中心化方案，维护成本高
去中心化方案
待解决问题
- 谁来发放货币？
- 怎么防范双重支付问题
发放货币
通过“挖矿（mining）”实现，具体之后再细说
双重支付问题
通过区块链这一数据结构解决
交易过程
A向B转账
- A需要知道B的地址（由平台提供，比特币本身并不提供）
- B（或者其他所有节点）需要知道A的公钥（用于验证）
转账方的公钥应该与其资产来源的公钥相一致
比特币中的交易是输入和输出两个脚本，验证合法性时是将货币来源的输入脚本和输出脚本合并在一起来，通过是否能顺利执行来判断是否合法
比特币区块构成
Block header
- version
- hash of previous
block header - Merkle root hash
- target(挖矿的目标地址)
Hash(blocker header)<=target - nonce
仅取header的hash，因为Merkle root hash 已经能够保证body的正确性
Block body
- transaction list 交易列表
比特币中的共识协议 Consensus in BintCoin
每个账本的内容要取得分布式共识 distributed consensus
节点
full node
保存所有信息，需要验证每一个节点
light node
只保存block header，轻节点没办法独立验证交易的合法性
假设
系统中大多数节点是正常的，仅部分为恶意节点
投票可以吗?
谁可以投票呢？（membership问题）
比特币可不经过系统同意产生账户，那可以通过产生大量的新账号来进行投票以压倒正确方
比特币的投票
使用运算能力来投票
只有找到nonce的节点（由其他节点去判断难度和正确性以及其他的header内容）才有权利去发布下一个节点
仅插在区块链后面的区块才是合法的
2Xf2E6aEU7n685eHEbXGYHrmWn2y7a62UWBrtZzodVdD
比特币中怎么算是认可？
若节点在新节点之后继续延伸，则认为其是合法的
分叉会在系统中存在一段时间，过一段时间后有了一个新块，连接到了A块后面，则B块就被淘汰了，A块成为了最长合法链。
争夺记账权的动力
block reward
争夺到记账权的节点可以发行一定量的货币，这也是比特币唯一产生途径。
能造多少呢？
最开始是50个比特币，21万个区块之后，数量减半
非对称加密体系方案
使用非对称加密体系，央行发行货币，使用私钥加密，每个人可以用公钥验证真伪。
缺点
- 双重支付问题（double spending attack）
中心化方案
央行发行货币，每个货币有唯一ID，维护一个数据库，每次交易都要记录交易过程，以验证所花的货币在支付人手中。
缺点
- 中心化方案，维护成本高
去中心化方案
待解决问题
- 谁来发放货币？
- 怎么防范双重支付问题
发放货币
通过“挖矿（mining）”实现，具体之后再细说
双重支付问题
通过区块链这一数据结构解决
交易过程
A向B转账
- A需要知道B的地址（由平台提供，比特币本身并不提供）
- B（或者其他所有节点）需要知道A的公钥（用于验证）
转账方的公钥应该与其资产来源的公钥相一致
比特币中的交易是输入和输出两个脚本，验证合法性时是将货币来源的输入脚本和输出脚本合并在一起来，通过是否能顺利执行来判断是否合法
比特币区块构成
Block header
- version
- hash of previous
block header - Merkle root hash
- target(挖矿的目标地址)
Hash(blocker header)<=target - nonce
仅取header的hash，因为Merkle root hash 已经能够保证body的正确性
Block body
- transaction list 交易列表
比特币中的共识协议 Consensus in BintCoin
每个账本的内容要取得分布式共识 distributed consensus
节点
full node
保存所有信息，需要验证每一个节点
light node
只保存block header，轻节点没办法独立验证交易的合法性
假设
系统中大多数节点是正常的，仅部分为恶意节点
投票可以吗?
谁可以投票呢？（membership问题）
比特币可不经过系统同意产生账户，那可以通过产生大量的新账号来进行投票以压倒正确方
比特币的投票
使用运算能力来投票
只有找到nonce的节点（由其他节点去判断难度和正确性以及其他的header内容）才有权利去发布下一个节点
仅插在区块链后面的区块才是合法的
2Xf2E6aEU7n685eHEbXGYHrmWn2y7a62UWBrtZzodVdD
比特币中怎么算是认可？
若节点在新节点之后继续延伸，则认为其是合法的
分叉会在系统中存在一段时间，过一段时间后有了一个新块，连接到了A块后面，则B块就被淘汰了，A块成为了最长合法链。
争夺记账权的动力
block reward
争夺到记账权的节点可以发行一定量的货币，这也是比特币唯一产生途径。
能造多少呢？
最开始是50个比特币，21万个区块之后，数量减半
非对称加密体系方案
使用非对称加密体系，央行发行货币，使用私钥加密，每个人可以用公钥验证真伪。
缺点
- 双重支付问题（double spending attack）
中心化方案
央行发行货币，每个货币有唯一ID，维护一个数据库，每次交易都要记录交易过程，以验证所花的货币在支付人手中。
缺点
- 中心化方案，维护成本高
去中心化方案
待解决问题
- 谁来发放货币？
- 怎么防范双重支付问题
发放货币
通过“挖矿（mining）”实现，具体之后再细说
双重支付问题
通过区块链这一数据结构解决
交易过程
A向B转账
- A需要知道B的地址（由平台提供，比特币本身并不提供）
- B（或者其他所有节点）需要知道A的公钥（用于验证）
转账方的公钥应该与其资产来源的公钥相一致
比特币中的交易是输入和输出两个脚本，验证合法性时是将货币来源的输入脚本和输出脚本合并在一起来，通过是否能顺利执行来判断是否合法
比特币区块构成
Block header
- version
- hash of previous
block header - Merkle root hash
- target(挖矿的目标地址)
Hash(blocker header)<=target - nonce
仅取header的hash，因为Merkle root hash 已经能够保证body的正确性
Block body
- transaction list 交易列表
比特币中的共识协议 Consensus in BintCoin
每个账本的内容要取得分布式共识 distributed consensus
节点
full node
保存所有信息，需要验证每一个节点
light node
只保存block header，轻节点没办法独立验证交易的合法性
假设
系统中大多数节点是正常的，仅部分为恶意节点
投票可以吗?
谁可以投票呢？（membership问题）
比特币可不经过系统同意产生账户，那可以通过产生大量的新账号来进行投票以压倒正确方
比特币的投票
使用运算能力来投票
只有找到nonce的节点（由其他节点去判断难度和正确性以及其他的header内容）才有权利去发布下一个节点
仅插在区块链后面的区块才是合法的
2Xf2E6aEU7n685eHEbXGYHrmWn2y7a62UWBrtZzodVdD
比特币中怎么算是认可？
若节点在新节点之后继续延伸，则认为其是合法的
分叉会在系统中存在一段时间，过一段时间后有了一个新块，连接到了A块后面，则B块就被淘汰了，A块成为了最长合法链。
争夺记账权的动力
block reward
争夺到记账权的节点可以发行一定量的货币，这也是比特币唯一产生途径。
能造多少呢？
最开始是50个比特币，21万个区块之后，数量减半