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 两个激励机制
- 出块奖励( 每隔21W个区块减半 )
- 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 获得了发布权:
- 不能伪造签名, 所以无法转账
- 如果写进区块, 诚实节点不接受区块( 有非法交易 ), 由于最长合法链存在, 失败( 付出代价太大, 且无法成功 )
- double spending: forking attack -> 原本交易产生了外部影响: 需要不断获得记账权
防范: 等待几个区块后( 比特币中是 six confirmation 大概一小时 )
selfish mining: 提前挖多个区块, 一起发布, 称为最长链 - 不发布合法交易
区块链是 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% 以上算力可能的攻击:
- 分叉攻击
- 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)
