北京大学肖臻老师《区块链技术与应用》公开课学习笔记

比特币中用到的密码学原理

Crypto-Currency

Cryptographic hash function

• collision resistance 哈希碰撞，没有好办法制造人为碰撞
• hiding 计算过程单向不可逆， x->H(x) 反过来不能实现， 实现digital commitment(digital equivalent of a sealed envelope)
  • 输入空间足够大
  • 分布均匀
• puzzle friendly 不可预测, 找到nonce
  H(block header) <= target,
  difficult to solve, but easy to verify

SHA256, Secure Hash Algorithm， 上面的三个特性都满足。

比特币用到密码学的两个功能，Hash和签名

账户：本地(public key, private key)

比特币中签名用私钥，验证用公钥
Asymmetric encryption algorithm 非对称加密

A good source of randomness, 好的随机源 ！！！

比特币中的数据结构

hash pointers
Block chain is a linked list using hash pointers
第一个区块：创世纪块（genesis block）
最新区块：most recent block
tamper-evident log

Merkle Tree

block header: 根哈希值
block body
Merkle Proof

全节点
轻节点，只有header

Proof of membership O(log(n))
Proof of inclusion

Proof of non-membership O(n)
证明交易不存在：Sorted Merkle tree, 比特币中不需要该种证明。

比特币的共识协议

double spending attack 双花攻击

每笔交易：

• 输入： 币的来源&公钥
• 输出：

Block header:

• version
• hash of previous block hader
• Merkle root hash
• target 挖矿 H() <= target
• nonce
  Block body:
• transaction list

Full node, Fully validating node
Light node, 大部分是轻节点

distributed consensus 分布式共识

FLP impossibility result: 一个失败就会无法达成共识
CAP Theorem: Consistency, Availability, Partition tolerance

Consensus in BitCoin

sybil attack 女巫攻击

longest valid chain
forking attack ,通过插入区块，回滚已经存在的区块

block reward
coin-based transaction
每21w个区块，奖励减半，21w10分钟/(60分钟24*365) 约4年时间，平均 10分钟产生一个块
初块奖励 50BTC -> 25BTC -> 12.5BTC

争夺记账权（挖矿 mining），计算的机器叫矿工。

比特币系统的实现

transaction-based ledger 基于交易的账本

total inputs = total outputs
UTXO： Unspent Transaction Output,

transaction fee: 交易费

account-based ledger

求hash只使用header的内容

coin-base修改 extra nonce。

Bernoulli trial(伯努利): a random experiment with binary outcome.
Bernoulli process: a sequence of independent Bernoulli trials. memoryless， 每次互不影响
Poisson process,
出块时间符合指数分布，exponential distribution

geometric series 几何序列

21w50 + 21w25 + 21w * 12.5 + ...
= 21w * 50 * (1 + 1/2 + 1/4 + ...) = 2100w

BitCoin is secured by mining.

Selfish mining. 分叉攻击

比特币网络

Simple, Robust, but not efficient

消息传播 flooding

区块大小 限制 1M。 耗带宽，带宽是瓶颈。

比特币挖矿难度调整

H(block header) <= target
用的哈希算法 SHA-256， 2^256种
difficulty = difficulty_1_target/target

51% attack,

orphan block, uncle reward

调整难度： 2016 * 10 / (60 * 24) = 14天
target = target * (actual time / expected time)
actual time = time to mine the last 2016 blocks

如果有节点故意不调整难度，挖出的节点，其他节点不认

比特币挖矿

全节点

• 一直在线
• 在本地硬盘上维护完整的区块链信息
• 在内存里维护UTXO集合，以便快速检验交易的正确性
• 监听比特币网络上的交易信息，验证每个交易的合法性
• 决定哪些交易会被打包到区块里
• 监听别的矿工挖出来的区块，验证其合法性
• 挖矿
• 决定沿着哪条链挖下去？ 最长有效链
• 当出现等长的分叉的时候，选择哪一个分叉？ 默认是最先听到的

轻节点、

• 不是一直在线
• 不用保存整个区块链，只要保存每个区块的块头
• 不用保存全部交易，只保存与自己相关的交易
• 无法检验大多数交易的合法性，只能检验与自己相关的那些交易的合法性。
• 无法检测网上发布的区块的正确性
• 可以验证挖矿的难度
• 只能检测哪个是最长链，不知道哪个是最长合法链

CPU -> GPU -> ASIC(Application Specific Integrated Circuit)
mining puzzle, Alternative mining puzzle( ASIC resistance)
merge mining.

矿池
pool manager: (miner, miner ....)
share, almost valid block.

Boycott attack, 抵制某个用户上链

比特币脚本

Proof of Burn
AlternativeCoin
Digital commitment
coinbase 只有获得记账权的才可以写