区块链 1.0

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

比特币中的密码学原理

哈希函数性质

1. Collision Resistance：
   • 碰撞：x≠y，但H(x) = H(y)
   • 含义：对于输入x，没有特定的方法（除了遍历x）能找到y（≠x），使得H(x) = H(y).
   • 输入空间应足够大且分布均匀
2. Hiding：
   • 无法由哈希函数输出H(y), 反推输入x（除非遍历x）
   • 输入空间应足够大，且分布均匀
3. Puzzle friendly：
   • 无法找到特定方法x，可以构造特定的输出H(y)。→ 这也是为什么nonce可以作为工作量证明PoW

目前区块链采用的哈希函数SHA-256 （Secure Hash Algorithm)，256位

非对称加密

1. 私钥对交易（tx）签名，公钥用于验证
2. 具备好的随机元的情况下，生成相同公私钥对的概率几乎为0

数据结构

1. 哈希指针（Hash Pointer）：包含所指向的结构体的哈希值（指针只是形象的说法，其实只有哈希，没有指针）
2. 区块链：使用哈希指针构成的链表，每个哈希指针保存的哈希值为前一个区块（包含哈希指针）的哈希值。只要保存根哈希指针，即可判断整条链的block是否被篡改
3. 区块：Block Header（包含Block Data的Merkel Tree的根哈希值） + Block Body
   • Block Header包含：
     • Version -- 区块链版本
     • 前一个区块block header的哈希指针
     • Merkel tree的根哈希
     • nBits -- 挖矿目标阈值（r字节，target简略版）
     • nonce（4bytes） -- 挖矿所求随机数
4. Merkel Tree： 叶节点为所有交易，父节点包含两个指向子节点的哈希指针。 Block Body中的交易由Merkel Tree组成，用于验证某项交易存在。任意交易被篡改，则根哈希值改变
5. 全节点和轻节点：
   • 全节点（full node）：保存区块链所有信息，验证每个交易
   • 轻节点（light node）：只包含block header，无法独立验证交易，只是利用区块链的信息
   • Merkel proof：轻节点验证与自己相关的某个交易合法性时，只需向临近的全节点请求该交易Merkel Tree路径上相对的哈希值即可验证
6. 交易： 输入为比特币来源，输出为接收者的公钥，交易通过发送者的私钥签名。发送者需提供自身公钥做验证

共识协议

1. 联盟链中多数节点是诚实的，可以采用投票。公链中账户可以随意创建，如果仍采用投票，则会出现女巫攻击（即一个节点创建多于半数的公私钥对，赢取投票）
2. 求解computational puzzle，获得nonce（工作量证明PoW）的节点获得记账权
3. 其他节点接收到新的区块后，先验证nonce合法性，再验证每条交易的合法性
4. 即使nonce和每条交易合法，如果哈希指针指向的不是最长合法链，则区块不会被节点接受
5. 若两个节点几乎同时获得记账权，区块均合法，则其他节点接受先收到的区块。进行算力竞赛，直达一条链胜出，成为最长合法链。而另一区块作废
6. 矿工的区块被接受，则获得出块奖励block reward（称为铸币交易coinbase transaction），该交易位于block body中，称作coinbase transaction 。每21万个区块（约4年），奖励减半。50→25→12.5，现在为12.5BTC
7. 这种情况下女巫攻击无效，因为创建多个账户并不会增加算力（记账权）

比特币具体实现

UTXO

1. transaction-based ledger 基于交易的账本，没有记录每个账户中有多少余额。所以交易的输入中需要包含交易的来源。比特币系统中每个全节点内存中需要维护一个UTXO，记录为被花掉的交易（没有写入区块链里）。（更安全，但需要查询以往的交易。而以太坊是基于账户的账本account-based ledger）
2. Unspent Transaction Output
3. total input = total output，但有的时候output略小（包含traction fee给矿工，否则矿工没有动力将别人的交易打包成区块）
4. Bitcoin is secured by mining.

出块概率

1. 多次伯努利实验，近似于泊松分布
2. Memoryless -- 过去的工作量不会影响后续出块的概率
3. 当区块链节点中，诚实的节点占大多数（指算力，不是账户数）时，恶意节点篡改数据的概率是很小的（恶意节点算力必须占大多数）
4. 挖矿时除了修改nonce外，由于难度加大，可能穷尽所有取值也得不到合法值。还可以尝试修改merkel tree的根hash（通过修改coinbase域 -- extra nonce）

比特币网络

1. 应用层：区块链协议
2. 网络层：P2P overlay 网络
3. overflooding，对带宽消耗很大，带宽是瓶颈。默认每个区块1M字节（每个区块包含大概4k个交易）
4. best effort
5. 比特币设计原则：简单、鲁棒而不是高效

挖矿

1. difficult to solve, but easy to verify

2. 挖矿难度difficulty x target = difficulty_1_target（难度为1时的target，为常数），即成反比

3. 默认每2016个block调整一次出块难度，即14天。new target = current target x (actual time / expected time)，调整倍数限制在（4分之1到4倍）

4. 之所以要控制出块时间，是为了避免分叉攻击。如果target固定，难度越来越小，出块时间越来越短。同一时间出现的分叉数可能会很大，导致诚实节点的算力被分散。恶意节点只需用较小的算力就能把自己的链挖成最长合法链。出块时间没有最优值，但需要稳定在某个范围。

5. 全节点&轻节点：

   全节点	轻节点
   一直在线	不是一直在线
   在本地硬盘上维护完整区块链信息	不用保存整个区块链，只要保存每个区块块头
   在内存里维护UTXO集合，以便快速检验交易正确性	不用保存全部交易，只保存与自己相关的交易
   监听比特币网络上的交易信息，验证每个交易合法性	无法检验大多数交易合法性，只能检验于自己相关交易的合法性
   决定哪些交易会被打包到区块里	无法检测网上发布的区块正确性
   挖矿： 决定沿哪条链挖下去 当出现等长分叉时，选择哪一个分叉	可以验证挖矿难度 只能检测哪个是最长链，不知道哪个是最长合法链

6. 比特币安全性保证：

   • 密码学上公私钥签名
   • 共识机制

7. 挖矿历史演进：CPU→GPU→ASIC芯片（Application Specific Integrated Circuit）→ 矿池

   • 由通用到专业化
   • 矿池的出现：
     • 由一个矿主pool manager管理多个矿工miner，miner只计算哈希值，由矿主负责全节点事务
     • 通过工作量证明进行收益分配。矿主通过降低挖矿难度，让每个miner提交almost valid block，以此作为PoW
     • 优点：相比miner单干，收益更稳定（miner单干要么挖到中大奖，要么打水漂）
     • 缺点：单个矿池算力达到50%更为可能。矿主不需要实际拥有那么多miner，只要发动攻击时号召就够了

8. 算力大于51%时的攻击形式

   • 分叉攻击（Forking Attack）：某笔待回滚交易后面连接6个区块确认后，矿池开始从该交易的分叉开始挖，追赶最长合法链。因为算力足够大，总能追上的
   • 抵制攻击（Boycott Attack）：只要链上出现包含某笔A交易的区块，就从另一分叉开始挖，直到挖成最长合法链，使A交易作废
   • 盗币?: 因为没有对方私钥，所以无法盗币。即使强行加到链上，诚实的节点也只会从另一条合法链去延伸

比特币脚本

验证形式

1. Input Script 接上输入来源交易的Output Script
2. 一开始是拼接后验证，现在input和output一般分开验证
3. 只利用堆栈stack

脚本形式

1. P2PK(Pay to Public Key)
   • input: PUSHDATA(Sig)
   • output：PUSHDATA(PubKey) + CHECKSIG
2. P2PKH(Pay to Public Key Hash)
   • input: PUSHDATA(Sig) + PUSHDATA(PubKey)
   • output：DUP + Hash160 + PUSHDATA(PubKeyHash) + EqualVerify + CHECKSIG
3. P2SH(Pay to Script Hash)
   • input: PUSHDATA(Sig) + PUSHDATA(SeriRS)
   • output: PUSHDATA(RSH) + Equal
   • 第二阶段：执行反序列化的赎回脚本，验证签名
   • 用处：主要用于多重签名，将签名的复杂性转移到输入端
4. Proof of Burn
   • output：RETURN + ...
   • 销毁比特币证明。由于比特币不可篡改性质，可在输出脚本RETURN后加任意内容，如专利hash作为证明。也用于作为PoW，换取某些小币种

分叉形式

1. State Fork：因出块时间接近而导致的分叉。恶意节点故意延伸的分叉也算state fork（又叫delibrate fork）
2. Protocol Fork：因协议更新导致
   • Hard Fork: 只要部分节点不更新协议，分叉会一直存在。e.g. 大部分算力修改出块大小上限1M → 4M，新旧节点将沿各自认可的合法链延伸（新节点认旧节点，但新节点链更长，将沿新链延伸）
   • Soft Fork：分叉是临时性的，不会一直存在。e.g. 大部分算力出块大小上限1M → 4M，将主要沿新节点链延伸（因为旧节点也认新节点，且新节点链更长）

比特币的匿名性

1. 由于比特币的公开性，匿名性是比较差的（或者说，pseudonomity较好，但无法防范linkability）
2. 获取BTC用户信息方式
   • 关联账户：一个交易中的多个input关联。输出中若存在一个output小于所有input（input个数 ≥ 2，商家只有一个)，则该output为零钱账户
   • 交易：买入卖出BTC、用BTC进行现实世界的交易
3. 比特币保护匿名性措施：
   • Mixing服务
   • 某些比特币钱包也能实现mixing服务
   • 比特币交易所其实也实现了mixing的功能
4. 零知识证明
   • 含义：证明者A向验证者B证明一个陈述是正确的，过程中不需要透露出除该陈述是正确的之外的任何信息
   • 同态隐藏
     • 若x ≠ y，则其加密函数值E(x) ≠ E(y) → 逆否命题：若E(x) = E(y)，则x = y
     • 隐匿性：很难由E(x)反推出x
     • 同态运算：
       • 同态加法：E(x) + E(y) = E(x + y)
       • 同态乘法：E(x) * E(y) = E(x * y)
       • 多项式运算类推
   • 例子
     • Alice向Bob证明自己知道一组x、y满足x + y = 7，但不想向Bob透露x和y值。→通过E(x)和E(y)
     • 盲签方法：用户A自己生成serialNum，银行在不知道serialNum的情况下为序列号签名生成Token。交易后用户B向银行提交SerialNum和Token验证货币真实性
     • 零币(zerocoin)和零钞(zerocash)：相比BTC实现更好的匿名性，但用户较少。原因是性能损耗、用户需求不大、未解决与现实世界交易时的匿名性

比特币思考

1. 哈希指针：只包含哈希，不包含指针。区块是存储在key-value数据库中的，key为hash，value为区块（比特币和以太坊为levelDB）
2. 私钥截断分开保存的做法存在安全风险（且死账残留在UTXO中，对矿工不友好），更好的做法是采用多重签名
3. 分布式共识理论上是不可能的，但实践上区块链将其变成可能
4. 不要被学术界的思维限制了头脑，不要被程序员的思维限制了想象力
5. 量子计算：离真正可用还很遥远，而且最先受到冲击的会是传统金融业；比特币中output中的公钥哈希本身丢失了部分数据，是不可逆的（所以公钥也不要随意泄露，每次交易后就应更换账号）