Victoria Island

be curious, be free

0%

肖臻区块链公开课笔记

发表于 更新于 分类于 本文字数： 8k 阅读时长 ≈ 7 分钟

肖臻区块链北大公开课笔记–BTC 部分

密码学原理

主要两个技术：

哈希

密码学中用到的哈希函数： cryptographic hash function

需要满足的性质：

  • collision（哈希碰撞） resistance

    $$
    x 不等于y，H(x) = H(y)
    $$

    对一个 message 求 digest（H(m)）

    必定会出现哈希碰撞，没办法篡改内容使得哈希值一样（除非暴力遍历，但是工作量很大）

    md5, 最开始认为 collision resistance，但是后面知道如何人为制造哈希碰撞了

  • hiding

    没法从哈希值 H(x)反推出 x

    前提：输入空间足够大，输入空间足够均匀

    与 collision resistance 结合，实现 digital commitment（ditital equavalent of a sealed envelope）

sealed envelope: 预测股市的结果，但是预测信息不能提前公布（会影响最终的结果），需要放在信封里先封存起来，等到第二天休市了再公布

将预测结果，哈希完之后公布出去。hiding：不能通过哈希值反推。collision resistance：预测结果不能篡改，改了对不上哈希值

要求：输入空间要足够大，一般接上随机数，保证输入足够随机且分布均匀，一起做哈希：H(x || nonce)

puzzle friendly（比特币要求的性质）

H(x)落在的范围不可预测

000…0XX…X 事先是不知道哪个输入能算出这种类型的哈希值

挖矿：找一个 nonce，和区块的块头拼在一起，使得哈希值要小于等于某个指定的目标阈值

H(block header(nonce)) <= target

这个挖矿的过程没有捷径，所以才可以作为工作量证明 proof of work

一旦有人找到这个 nonce，其他人的验证很容易，只要算一次（difficult to solve, easy to verify），设计 mining puzzle 需要注意这个性质

SHA-256(比特币的哈希函数)

secure hash algorithm

签名

比特币开户：创建公钥私钥对儿（public key, private key），来源于非对称加密体系（asymmetric encryption algorithm）

加密的公钥不需要保密，解密的私钥保密

别人转账只要知道你的公钥就可以，私钥相当于密码

用私钥来签名交易，链上用公钥去解密验证，证明交易是某人的

万一两人生成的公私钥相同？实际概率微乎其微

生成公私钥对，需要好的随机源。

不仅生成公私钥对需要好的随机源，每次签名的时候也需要好的随机源，否则可能会泄露私钥

数据结构

哈希指针

保存结构体的地址和结构体的哈希值，防止结构体被篡改

不光找到结构体的地址，还能检测结构体的内容是否被篡改

区块链

Block chain is a linked list using hash pointers

哈希指针代替了普通的指针

第一个区块叫 genesis block，最后一个区块是 most recent block(最近产生区块)，由 hash pointer 连接起来，最后一个区块也有一个哈希值，保存在系统里，供下一个产生的区块直接引用，注意 hash 值是对前一个区块整体取 hash 得到的（包括里面的 hash pointer）——tamper-evident log

只要记住最后一个系统里的哈希值，就能检测区块链里所有的块是否被改动

普通链表修改一个节点，对其他节点是没有影响的

由于这个性质，比特币里的区块可以不用保存以前所有的区块的 hash pointer，只要前面几千个就可以。如果要用到之前的区块，向之前的区块要 hash pointer 就行。但是如果某个区块是有恶意的，也可以通过自己区块的 hash pointer 校验，看他是否发生改动。

bitcoin数据结构1

如果有环哈希指针会有问题（循环依赖，哪个区块都定不下来）

Merkle Tree

和 Binary Tree 的区别是用 hash pointer 代替 binary tree 的指针

bitcoin数据结构2

内部节点都是 hash pointer，leaf 是 data block（交易数据 transaction），对根节点取 hash 就是 root hash

只要记住 root hash，就能检测出树中任何部位的修改

底下每个数据块是交易（transaction）

block header：只有根哈希值，没有交易内容

block body：交易内容

全节点（保存 block header 和 block body）和轻节点（只保存 block header，比如手机比特币钱包应用）

向轻节点如何证明某个交易是写到区块链的？

Merkel proof：找到这个交易所在的位置，从这个交易往上往根节点就是 merkel proof

merkel_tree

merkel proof 是转钱者要提供的，收钱方的钱包的的轻节点，向全节点请求 merkel proof 路径上这些红色的哈希值，就能往上算出每一层的哈希值，最后算到根哈希值与自己轻节点的哈希头的根哈希值做对比

proof of membership (proof of inclusion)

时间复杂度：O（logn）

proof of non-membership

若叶子节点按照哈希值排序（sorted merkel tree），就可以找到要查找的交易是在哪两个叶子之间。只要证明这两个边上的叶子是 membership，就能证明要查找的交易不存在（如果存在不应该夹在中间）

时间复杂度：O（logn）代价是 sorted merkel tree（比特币没用到，不需要这个性质）

比特币协议

数字货币存在 double spending attack

区块链：每个交易要包含输入和输出，输入包含钱的来源——铸币交易 coinbase transaction（使用 hash 指针）以及转账人的公钥，输出包含收款人公钥的 hash，还需要转账人的签名

每个节点都需要知道转账人的公钥，因为交易签名使用的是转账人的私钥，大家验证需要使用其公钥验证

铸币交易的输出包含获得人的公钥，后续交易的输入公钥需要和最初的 coinbase 交易的公钥对得上

实际上 BTC 上每个区块链上都也很多交易组成 Merkle Tree

每个区块分成 Block header 和 Block body

Block header Block body
version transaction list
hash of previous block header (only caculate block header)
Merkle root hash
nBits（256 位 target 的压缩编码 4bytes）
nonce

BTC 每个节点可分为 full node (fully validating node) 和 light node (只保存 block header)，主要是后者

账本内容要取得分布式的共识 distributed consensus，共同维护 distributed hash table

有人提出 FLP impossibility result，即在一个异步且时延没有上限的网络中，只要有一个人是 faulty，整个网络就无法达成共识；另外有人提出 CAP Theorem (Consistency, Availability, Partition tolerance)，即这三个性质最多得到两个

BTC 的共识协议：

若采用投票，需要确定 membership（如 hyperledger fabric 联盟链，只有某些大公司能参与，投票可以），BTC 中恶意者不断产生公私钥就一直获得投票权 sybil attack。

在 BTC 中，$H(block~header)\le target$中有一个 4bytes 的$nonce$，求出符合该式的$nonce$即可获得记账权

当 hash of previous block header 不是指向 longest valid chain 的最后的时候，这个区块就新开了一个分支（分叉攻击 forking attack），正常情况应该是接在最长合法链的后面。

但是还有一种情况，两个区块同时获得记账权，都接在 longest valid chain 的最后产生分叉，此时各个本地区块会根据网络延迟先接上两者之一。之后如果在两者其中之一继续先扩展下一个区块（看算力和运气）就变成了最长合法链，另外一个就变成了 orphan block 被丢弃掉

BTC 设置 block reward 来让大家争夺记账权，因为这是铸币的唯一方式

BTC-系统实现

BTC：transaction-base ledger

全节点在内存中维护 UTXO (Unspent Transaction Output)，防止 double spending

除了出块奖励之外，为了防止某人在打包区块链的时候只打包自己的交易记录，于是提供了 transaction fee 作为奖励

为了增大 nonce 的搜索空间，可以使用 coinbase txn 的前几个字节作为 extra nonce，因为 coinbase txn 的内容是随意的但是修改它会导致 Merkle Tree Root 的 hash 值发生改变

尝试 nonce 成功是伯努利过程，接近于 Possion 分布，无记忆性（将来挖的时间和过去挖的时间没有关系），系统平均出块时间为 10min

BTC 的数量：

$$
\begin{align}
210000 \times 50 + 210000 \times 25 + \dots &= 210000 \times 50 \times \left(1 + \frac{1}{2} + \frac{1}{4} + \dots \right) \
&= 21{,}000{,}000
\end{align}
$$

挖矿求解过程没有意义，但是 Bitcoin is secured by mining：当大部分算力掌握在诚实节点上的时候就是安全的（用算力投票）

记账权的获得有时候看运气，所以可能会落入恶意节点，此时

  • 不能偷币（因为没有转账人的私钥签名，即使写到链上，它不是最长合法链所以诚实节点不会接上去，所以此恶意攻击者甚至拿不到出块奖励）
  • 可能出现 double spending——难度较大（forking attack，同时写入转账和回滚产生分支，交易平台看到写入转账的区块就认为交易成功，但是之后可能回滚分支成为最长合法链，如果本来转账分支之后就已经接着很多区块了，这种方法就比较困难，所以 BTC 的防范方法是 six confirmation，需要 1 小时时间，故 BTC 的不可篡改性是概率上的保证；另一种方法是 zero confirmation，直接选择最先被接受的节点，或者电商平台本来交易完到发货就有时间差可以用来检验合法性）
  • 故意不包含合法交易，但是总有合法的区块会发布这些交易
  • selfish mining——正常情况下挖到区块直接发布，但是也可以挖到多块区块连在一起然后 forking attack 一次性接上去。但是前提是恶意算力比较大的时候才比较容易成功篡改。但是这种方法也有好处，减少竞争，关键还是需要算力比较大，风险在于当别人比你早挖出来的时候要赶紧接上去

ETH：account-based ledger

系统显式地记录每个账户上的币

BTC-网络

BTC 工作在 application layer，底层 network layer 是 P2P Overlay Network，在这个网络里所有节点都是平等的，没有 super node/master node，加入网络需要知道 seed node 种子节点

BTC 网络的目标：简单，鲁棒而不是高效

BTC 协议对区块大小的限制为 1M

best effort，一个交易不一定让所有节点都收到，顺序也不一定一样，有些节点可能转发错误的交易

BTC-挖矿难度的调整

Double subscripts: use braces to clarify

$difficulty=\frac{difficulty_1_target}{target}$

分子是当难度为 1（最低）的时候的目标阈值，是一个很大的数

出块时间太短导致：这个区块在网络上来不及广播，使得多分叉变成常态，一旦出现多分叉，善意的算力被分散，而恶意算力可以集中在一个分叉上使得其不断延伸成为最长合法链，使得 51% attack 的数字会变小

每 2016 个区块调整一下难度，大概是 14 天一次，$target=target\times \frac{actualtime}{expectedtime}$

恶意节点无法执行调整 nBits 来降低难度因为别的区块验证会通不过

BTC-脚本

基于栈的语言

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"result": {
   "txid":"921a...dd24",
   "hash":"921a...dd24",
   "version":1,
   "size":226,
   "locktime":0,
   "vin":[],
     "vout":[],
     "blockhash":"00000000002c510d...5c0b",
     "confirmations":23,
     "time":1530846727,
     "blocktime":1530846727}
 // locktime为0表示立刻生效"vin": [{
   "txid":"",
   "vout":0,
   "scriptSig": {
     "asm":"",
     "hex":""}
 }]
 // 上面vout的值表示是txid交易的第几个输出"vout": [{
   "value":0.1,
   "n":0,
   "scriptPubKey": {
     "asm":"DUP HASH160 628e... EQUALVERIFY CHECKSIG",
     "hex":"76a9...",
     "reqSigs":1,
     "type":"pubkeyhash",
     "addresses":["...."]
   }
 }]
 // 上面n表示为当前输出的第几个，asm输出脚本的内容，reqSigs表示需要的签名数量

某个区块 A 的输入来源于区块 B 的输出，那么将 A 的 input script 和 B 的 output script（注意不是A 的 output script）拼接在一起，先执行前者，后执行后者，如果结果为 true 就表示合法

几种类型：

  • P2PK (Pay to Public Key)

    • input script

      • PUSHDATA (Sig)

    • output script

      • PUSHDATA (PubKey)
      • CHECKSIG

  • P2PKH (Pay to Public Key Hash) 最常用

    • input script

      • PUSHDATA (Sig) 压栈
      • PUSHDATA (PubKey) 压栈

    • output script

      • DUP 复制一份栈顶并压栈
      • HASH160 弹出栈顶 pubkey 取 hash 压入栈
      • PUSHDATA (PubKeyHash) 压入 pubkeyhash
      • EQUALVERIFY 弹出栈顶两个 hash 值是否相等，防止某人以自己的公钥顶替
      • CHECKSIG 最后将 sig 和 pubkey 进行 check 正确就返回 true

  • P2SH (Pay to Script Hash)

    • input script

      • …
      • PUSHDATA (Sig)
      • …
      • PUSHDATA (serialized redeemScript)

    • output script

      • HASH160
      • PUSHDATA (redeemScriptHash)
      • EQUAL

    • 简单来说就是另外有一个 redeem script，首先执行 input 和 output，最后执行 redeem 的内容

    • 支持多重签名
      将 input script 中改成

      • false (Bitcoin 的实现 BUG，这里多压入一个没用的元素)
      • PUSHDATA (Sig_1)
      • …
      • PUSHDATA (Sig_M)
      • PUSHDATA (serialized redeemScript)
        将 redeemScript 写成
      • M 表示总的签名数
      • PUSHDATA (pubkey_1)
      • …
      • PUSHDATA (pubkey_N)
      • N
      • CHECKMULTISIG

  • Proof of Burn

    • output script

      • RETURN [zero or more ops or text]
      • 这种形式的 output 被称为 Provably Unspendable/Prunable Outputs

    • 脚本说明：return 直接返回 false，这个 output 无法被花出去，UTXO 可以剪枝

    • 应用

      • AltCoin (Alternative Coin) 销毁 Bitcoin 获得小币
      • 花费非常少的 BTC 将某些内容取 hash 放到 return 后面，这样就能放到区块链上 （coinbase 中也是随意记东西的，但是只有获得记账权的节点才能写东西）

BTC-分叉

  • state fork 状态分叉，意见分歧

    • 包括 forking attack，也被称为 deliberate fork

  • protocol fork 协议分叉

    • 不同协议造成的分叉

    • 进一步分成 hard fork 和 soft fork

    • hard fork

      • 扩展新的特性（如修改 block size 为 4M）时如果不认可新的特性就会产生硬分叉
      • 旧节点在原来的链上不断延伸，新节点在新的链上延伸，产生永久性的分叉
      • 当前交易速度约为每秒 7 笔交易
      • 由此社区分裂成两帮人，一个币拆成了两个币，各自有自己的 chain id

    • soft fork

      • 临时的分叉（如修改 block size 为 1M）
      • 旧节点会放弃旧链，在新链上延伸，但是此时新节点又不会认当前链为最长合法链而新开一个分叉，使得旧节点一直是白挖
      • 最终还是会变成一条链
      • 例子：给原来的某些域一些新的含义，比如给 coinbase 域增加含义 extra nonce+UTXO 的根 hash

匿名性

pseudonymity 匿名性不如纸币高于银行

不同账户之间可以建立关联、BTC 和现实世界也可以形成关联

在 network layer 上实现匿名性：使用 TOR

在 application layer 上实现匿名性：coin mixing、在线钱包本身可能带有 coin mixing 功能、交易所天然有 coin mixing 功能（如果交易所不暴露提币存币的记录）

Q&A

  • 如果收款人没有连接到 BTC 网络？
    没有关系
  • OP_RETURN 永远返回 false 为啥会写到区块链上？
    因为这个 RETURN 语句是写在 output script，因此在验证这笔交易的时候并不执行
  • 交易费给哪位？
    交易费等于总输入减总输出，剩下的直接给挖到的矿工即可

证明者向验证者证明一个陈述是正确的，而无需透露该陈述是正确的外任何信息

数学基础：同态隐藏

  • 如果$x,y$不同，那么$E(x)$和$E(y)$也不同
  • 给定$E(x)$，很难反对出$x$的值（类似 hiding）
  • 同态运算：同态加法、同态乘法、扩展到多项式

为匿名性设计的加密货币：零币和零钞

  • hash pointer 只有本地的地址，发布到区块链网络上会咋样？
    网络上没有指针，只有 hash，全节点维护一个数据库保存(key, value)，常用的是 levelDB
  • 分布式共识
    BTC 实际上也没有取得 真正的共识，但是实际和理论是不一样的