Bitcoin

北京大学肖臻老师《区块链技术与应用》公开课
肖臻老师的网站

1. 密码学原理

1.1. 哈希

• 加密货币: crypto-currency

• 加密函数:cryptographic hash function

  • collision resistance: 加密碰撞避免, x!=y, H(x)=H(y)
  • hiding: hash函数计算过程单向不可逆
    • digital commitment( digital equivalent of a sealed envelope )
    • H( x || nonce )
  • puzzle friendly

• 比特币里的hash函数: SHA-256 ( secure hash algorithm )

1.2. 签名

• ( public key, private key ): 公钥加密( 不需保密 ), 私钥解密( 需要保密, 本地保存 )
• 非对称加密体系( asymmetric encryption algorithm )
  • encryption key: 对称加密
• 私钥签名, 公钥验证签名

2. 数据结构

哈希指针: hash pointers
Block chain is a linked list using hash pointers

Block[H()]<-Block[H()]<-Block[H()]<-Block[H()]<-Block[H()]<-Block[H()]<-H()

• 每个 H() 是计算所有区块的哈希值
• merkle tree: 用哈希指针代替普通指针( 只有最底层是数据区块 ) [data blocks]-[hash pointers]
• data block: [ block header- block body]
• merkle proof ( 验证路径上的哈希值 )

proof of membership (有...交易)
proof of inclusion

proof of non-membership( 每个验证, O(n))

sorted merkle tree( 比特币中未使用 )

3. 共识协议

双花问题( double spending attack ): 重复支付

coinbase tx: 铸币交易

• [Block header]
  • version
  • hash of previous block header
  • merkle root hash
  • target 挖矿难度阈值
  • nonce 随机数
• [Block body]

全节点( full node ): 保存所有信息
轻节点( light node ): 只有block header

3.1 分布式共识 distributed consensus

distributed hash table 分布式哈希表

• FLP impossibility: 在异步通信场景, 即使只有一个进程失败, 也没有任何算法能保证非失败进程达到一致
• CAP Theorem: Consistency, Availability, Partition tolerance( 只可能满足两个 )
• Paxos( Consistency一致性 )

Consensus in Bitcoin

• menbership: 投票资格问题->女巫攻击( sybil attack )
• 最长合法链( longest valid chain )
• 分叉攻击( forking attack )
• 如果两个等长区块链 -> 维持一段时间, 直至一个变为最长合法链
• block reward
• coinbase transaction: 发行比特币的唯一方法

4. 比特币系统的实现

4.1 基于交易 transaction-based ledger 的账本模式

UTXO (Unspent Transaction Output): 未花费的交易输出, 交易构成了一组链式结构, 所有合法的比特币交易都可以追溯到前向一个或多个交易的输出, 这些链条的源头都是挖矿奖励, 末尾则是当前未花费的交易输出
->
检测double spending

total inputs所有输入金额 = total outputs所有输出金额

4.2 两个激励机制

1. 出块奖励( 每隔21W个区块减半 )
2. transaction fee

4.3 基于账户的模式 account-based ledger ( 以太坊 )

4.4 挖矿: 求解nonce

每次求解nonce相当于一次 Bernoulli trial: a random experiment with binary outcome( 掷硬币 )
->
Bernoulli process: a sequence of independent Bernoulli trails
memoryless ( 无记忆性 )

用 poisson process 近似

出块时间服从指数分布( exponential distribution ): progress free -> 公平

4.5 出块奖励构成几何序列 geometric series

系统中所有比特币总量: 21万 x 50 - 21万 x 25 - 21万 x 12.5 - ... = 2100万

Bitcoin is secured by mining

4.6 安全性分析

大多数为诚实, 即使小概率 m 获得了发布权:

1. 不能伪造签名, 所以无法转账
2. 如果写进区块, 诚实节点不接受区块( 有非法交易 ), 由于最长合法链存在, 失败( 付出代价太大, 且无法成功 )
3. double spending: forking attack -> 原本交易产生了外部影响: 需要不断获得记账权
   防范: 等待几个区块后( 比特币中是 six confirmation 大概一小时 )
   selfish mining: 提前挖多个区块, 一起发布, 称为最长链
4. 不发布合法交易

区块链是 irrevocable ledger ( 只是概率上的保证 )

5. 网络 The Bitcoin Network

• 应用层 application layer - Bitcoin Blockchain
• 网络层 network layer - P2P Overlay Network

simple, robust, but not efficient

消息采用: flooding

6. 挖矿难度

H( block header ) <= target( 难度目标阈值 )

sha-256 2^256 可能取值

difficulty = difficulty_1_target / target

出块时间太短: 容易出现分叉 -> 51% attack

每14天调整target ( 2016 x 10 ) / ( 60 x 24 ) = 14天
target = target x ( actual time / expected time)
actual time: 最近2016个区块实际挖矿时间

7. 挖矿

• 全节点: 一直在线
  • 本地硬盘维护完整区块链信息
  • 内存里维护UTXO集合, 快速检验交易正确性
  • 监听交易信息, 验证每个交易合法性
  • 决定哪些交易打包
  • 监听别的区块, 验证合法性
  • 挖矿: 决定沿哪个方向挖, 选择分叉
• 轻节点
  • 不是一直在线
  • 不用保存整个区块链, 只保存每个区块块头
  • 只保存与自己相关交易 -> 无法检验大多数交易合法性 & 无法检测网上发布区块的正确性
  • 可以验证挖矿难度
  • 只能检测最长链, 不知道哪个是最长合法链

大部分节点都是轻节点

memoryless; progress free

比特币的安全性

• 密码学原理( 基于大多数节点为"好"节点 )
• 共识机制

CPU挖矿 -> GPU挖矿 -> ASIC芯片( Application Specific Integrated Circuit )

矿池 - 矿主 - 矿工 -> 解决收入问题

收入分配

矿池如果占到51% 以上算力可能的攻击:

1. 分叉攻击
2. boycott 封锁账户

8. 比特币脚本

基于栈的语言

通过销毁比特币向区块链写入内容

9. 比特币分叉 fork

• state fork 临时性的分叉( 两个不同区块 )
• forking attack ( 故意造成 deliberate fork )
• protocol fork 协议升级造成的分叉
  • 硬分叉
  • 软分叉

9.1 硬分叉

hard fork

比特币中区块大小控制 block size limit
1M的大小限制
-> 4000左右交易
-> 每秒7笔交易左右

以太坊分叉 ETH ETC -> chain ID 防止回放

• 只有所有节点都更新, 才不会出现永久分叉

9.2 软分叉

soft fork

对比特币协议加以限制, 以前的交易可能变为不合法

• coinbase域 给某个域添加限制和功能

P2SH: payto script hash

不转给公钥hash 而是 redeem script
添加一个阶段, 旧交易依旧合法

• 只要有半数以上节点更新后, 不会出现永久分叉

10. 比特币中的匿名性

Bitcoin and anonymity ?= privacy

pseudonymity( 像"网名" )

多重签名( 多个账户输入 )

coin mixing

10.1 零知识证明

一方( 证明者 )向另一方( 验证者 )证明一个陈述是正确的, 而无需透露除该陈述是正确的外的任何信息
例: 签名

同态隐藏:

• 如果x, y不同, E(x) E(y) 不同 -> 如果E(x) E(y) 相同, xy相同
• 给定E(x) 很难推出x ( 不可逆 )
  同态运算
• 同态加法 通过E(x) E(y) 算出 E(x+y)
• 同态乘法 通过E(x) E(y) 算出 E(xy)

10.2 盲签方法