一. 简介

Bitcoin是基于区块链的一种货币

参考：以太坊白皮书、黄皮书、源代码 / Solidity文档 / 比特币官网 / 比特币实时信息

二. 密码学原理

哈希函数指将哈希表中元素的关键值映射为元素存储位置的函数。

Collision resistance（拒绝碰撞）

哈希碰撞指x不等于y，但是H(x) = H(y)。

可以利用上述性质，对文件计算哈希值，然后校验是否篡改。

但是这个性质并不能在数学上证明，例如对于MD5来说，曾经大家认为它很安全，但现在已经找到了人为制造碰撞的方法。

Hiding

指计算过程是单向的，能通过x得到H(x)，但不能通过H(x)得到x。

破解方法有：蛮力求解，即遍历x，要确保x的输入空间足够大，数据分布较均匀。

digital commitment

digital equivalent of a sealed envelope：

在现实世界中，如果一个很有名气的股神提前一天预测某股票涨停，可能会影响真实结果。但是如果不提前公布预测结果，就不知道预测内容是否被篡改。所以要由第三方公正机构（就是这个envelope）来证明。

在电子世界中，我们利用Hash的Hiding性质，将H(x)公布出去，然后再公布x。如果输入空间不够大，可以拼接一个随机数，例如H(x || nonce)。

puzzle friendly

指要得到某个区间的哈希值，只能一个个去试x的输入（没有捷径），可以作为工作量证明（proof of work）。

以挖矿为例，H(block header) 要小于等于 target。区块链是由一个个区块组成的链表，每个区块都有个header，header中有很多域，其中有个随机数，挖矿就是要不断寻找随机数，使得上述表达式成立。

比特币中用的Hash函数是SHA-256 (Secure Hash Algorithm)。

总的来说，就是：difficult to solve, but easy to verify。

公钥和私钥

对于比特币系统来说，开户就是在本地创建一对公钥和私钥的过程。

对称加密体系：使用密钥先加密发送，然后再用该密钥解密（前提是有安全渠道分发给通讯双方）。

非对称加密体系：加密用公钥，解密用私钥。公钥相当于比特币账户，私钥相当于比特币密码。签名用私钥，验证签名用公钥（先对message取一个哈希，然后再对哈希值签名）。

公私钥虽然在本地产生，重复的可能性十分小（要求选取一个好的随机源 a good source of randness）。

三. 比特币的数据结构

哈希指针不仅要保存地址，还要保存结构体的哈希值。通过哈希指针不仅能找到数据的位置，还能检测出数据有没有被篡改（因为保存了哈希值）。

区块链

区块链就是一个个区块（block）组成的链表。和普通链表的区别是：用哈希指针代替了普通的指针。

区块链表

取哈希的时候是把整个区块的内容（包括其保存的指向下一个区块的哈希指针）一起取哈希。

使用这种数据结构可以实现tamper-evident log（防篡改日志），即如果某个区块被篡改，会导致最后与系统保存的的哈希值对应不上。

用户可以只保存最近的一些区块，如果要用到以前的区块，可以找别的节点要，然后通过上述性质去验证别人给的块是否正确。

Merkle tree

用哈希指针代替了普通二叉树中的普通指针，最底下的一层叶子结点是数据块，其上的若干层非叶子结点都是存储哈希指针的。

Merkle tree

只需要记住根哈希值，可以检测出data block是否被修改。在比特币系统中，每个data块相当于一次交易

结点

在区块链中，每个区块分为两部分，块头（block header）和块身（block body）。在块头中存储了这个区块所包含的所有交易组成的Merkle Tree的根哈希值。只在块身中存储了交易列表。

全结点：既有块头又有块身的区块，保存了交易的具体信息。

轻结点：只保存了块头，没有保存块身。例如手机上的比特币钱包就使用的是轻结点。

如何向轻结点证明某个交易是写入了区块链的？

Merkle proof

交易的data块到根结点的路径，时间复杂度是θ(logn)。

Merkle proof

要证明某个交易不存在，先对data block的哈希进行排序，然后二分查找，但是比特币中不需要证明交易不存在。

只要数据结构是无环的，都可以用哈希指针替代普通指针，否则会出现循环依赖。

四. 协议

数字货币与纸质货币

直接为货币的面额等信息，用央行的私钥签名，然后使用的时候，用户直接拿央行的公钥验证签名。

问题：虽然保证货币的真实性，但是会遇到 花两次攻击（double spending attack），不像纸质货币，花出去了就没了。

解决方法：中心化方法，再维护一个数据库保存数字化货币对应的用户。那么去中心化的方法呢？

去中心化

数字货币举例

BTC系统中每个交易都分为输入部分和输出部分，输入部分要给出这笔交易的BTC的来源以及付款方的公钥，输出部分要给出收款人的公钥的哈希值。比如A要转给B钱，就需要给出B的哈希。

这里涉及两种哈希指针，将各个区块串起来的哈希指针；另一种是为了说明币的来源是从哪个交易来的。

收款地址：通过 收款人的公钥取哈希再经过一些转换 得到。

A转账给B，收款的时候，B要知道A的公钥，因为要验证A的签名。

区块结构

Block header :

  1. Version
  2. 指向前一个区块的哈希指针，这里的哈希值是通过计算前一个区块的块头得到的
  3. Merkle root hash：整颗Merkle Tree的根哈希值
  4. Target：挖矿难度目标阈值
  5. Nonce：挖矿用的随机数，目标是H(BlockHeader)小于等于target

Block body :

  1. 交易列表

分布式共识 distributed consensus

区块链可以看成去中心化的账本，如何保证写入区块后的一致性？账本的内容要取得分布式的共识。

分布式系统的不可能结论 impossibility result

  • FLP impoossibility result

    在一个异步的系统中，网络传输时延没有上限，即使只有一个成员有问题（faulty），也不能取得共识。

  • CAP Theorem

    任何一个分布式系统，Consistency一致性、Availability可用性、Partition tolerance分区容忍性，只能满足其中两个。

BTC共识机制

投票方式（按照账户数量）：

将所有交易写入一个候选区块，然后发给所有结点，大家验证这个区块中的交易是不是都是合法的，然后投赞成和反对票，按一定投票比通过后将候选区块写入区块链中。

但是存在membership问题，即谁有投票权，例如hyperledger（联盟链）只有一些大公司可以加入。

还可以进行sybil attack（女巫攻击），只要不断产生账户，就可以取得大量投票权并控制区块链。

比特币投票方式（按照计算力）：

每个结点在本地组装一个候选区块，把认为合法的区块放进去，尝试各种nonce值，使得H(BlockHeader)小于等于target。如果找到了nonce，就获得了记账权，其他结点收到这个区块后要验证合法性。

分叉攻击

候选区块如果合法就接收吗？检查有没有double spending是看一条链上有没有花过两次，如果有分叉呢？

分叉攻击

上面转账给自己的区块是合法的，但是不应当被接受（以最长合法链为准）。

如果一个结点收到一个区块后，沿着这个区块继续往下扩展，那么就算该结点接受了这个区块。

如果两个结点同时获得记账权，都能插入候选区块，会维持多条最长合法链的情况，直到某个分支找到了下一个合法区块，另一个区块就会变成orphan block。

出块奖励

为什么要去竞争记账权？BTC系统设计来希望所有交易都能被公平写入账本。出块奖励机制解决了这个问题。

根据BTC协议，获得记账权的结点，在发布的区块可以进行铸币交易，可以发布一定数量的BTC（产生新BTC的唯一方法），不用指定币的来源。最早的时候，BTC出块奖励是50个，规定每21万个区块后奖励减半。

如今（2022.11），1 BTC 的价值大约在2万美元左右，比最开始的时候值钱了很多，所以虽然现在奖励少了，但是依然会有很多结点去竞争记账权（挖矿）。

五. 实现

BTC采用的是基于交易的账本模式（transaction-based ledger），只记录了转账交易和铸币交易，并没有直接记录每个账户上有多少钱。如果想知道某个BTC账户上有多少钱，要通过交易记录来推算。

相反，以太坊采用的是基于账户的账本模式（account-based ledger）。

UTXO（Unspent Transaction Output）：没有被花出去的交易的输出

UTXO举例

UTXO集合中的每个元素要给出产生这个输出的交易的哈希值，以及它在这个交易中是第几个输出。用这两个信息就可以定位到一个确定的交易中确定的输出。

使用UTXO可以用来快速检测双花攻击，想知道新发布的交易是不是合法的，要查一下全结点存在内存中的UTXO。要花掉的币只有在这个UTXO这个集合里才是合法的，否则要么是不存在的，要么是已经花过了的。

如果一个人拥有比特币一直不花，那么这个记录会永久存储在UTXO中。

交易费（transaction fee）

有些交易的总输入可能略微大于总输出（total inputs > total outputs），

例如总输入是1BTC，总输出是0.99BTC，其中的差额作为记账费给了获得记账权的结点（为了激励别人去记账）。

有些简单的交易可能没有交易费。

区块举例

区块举例

块头结构

1
2
3
4
5
6
7
8
9
10
class CBlockHeader
{
    public:
    int32_t nVersion;//BTC版本号，没法改
    uint256 hashPrevBlock;//前一个区块块头哈希值（32字节）：不能改
    uint256 hashMerkleRoot;//通过修改Merkle Tree中铸币交易的CoinBase域来调整其根哈希值
    uint32_t nTime;//区块产生时间，有一定的调整余地，BTC系统并不要求非常精确的时间，这个域可以在一定范围内调整
    uint32_t nBits;//挖矿目标阈值编码后的版本，只能按照协议中的要求定期进行调整，不能随便改
    uint32_t nNonce;
}

实际挖矿时，一般也是为此设计了两层循环，外层循环调整铸币交易的CoinBase域的extra nonce，然后算出Merkle Tree的根哈希值；内层循环调整块头的nonce，计算整个块头的哈希值。

交易举例

交易举例

概率分析

伯努利实验，由于n（次数）很大，p（概率）很小，近似泊松分布。

公平性保证（progress free）

出块时间服从的指数分布也是无记忆性的， 也就是说从任何一个位置将其截断，剩下的部分仍然是服从指数分布的。“将来还要挖多少时间”和“过去已经挖了多少时间”没有关系。

安全性分析

  1. 转走别人的比特币

    假设一个有恶意的结点M获得了记账权，它想把结点A的钱转走，但因为没法伪造A的签名（没有A的私钥），写个任何不正确的签名上去，都会导致诚实的结点不会接受这个候选区块，而是继续沿着上一个区块扩展。因为这个区块是不合法的，所以多长都不是最长合法链，这样的攻击是无效的。

  2. 分叉攻击

    M把BTC转给A，然后紧接着挖到了一个区块，并填写M->M的交易，希望沿着这个区块成为最长合法链，这样就能将转给A的记录挤掉，从而将花出去的BTC回滚。这是双花攻击的一种。

    区块链的不可篡改性是从概率上出发的，刚写入的区块还是有可能被篡改。防范分叉攻击的方法是多等几次确认（confirmation），一般要等6个confirmation（即一小时左右）。

    zero confirmation的应用比较广泛，1）两个交易冲突，结点一般接收最先听到的交易。2）委托全结点监听区块链，如果发现最后交易不合法，可以取消交易。

  3. selfish mining

    指挖到的区块先留着，例如在分叉攻击中一次性发布出去，替换最长合法链，但要求恶意结点算力超过全网50%才有可能。

六. 网络

比特币区块链运行在应用层，网络层是一个P2P网络。所有网络都是对等的，没有超级结点（super node）或主结点（master node）。结点间采用TCP通信。

设计原则：简单（simple）、鲁棒（robust），而不是高效（but not efficient）

消息在网络中采用flooding方式传播，结点第一次听到消息会传播给所有邻居结点，并记录已经收到过该消息，下次再收到就不传播。

邻居结点的选取是随机的，没有考虑底层拓扑结构，增强了鲁棒性，牺牲了效率。

七. 挖矿难度

什么是挖矿难度？

前面提到挖矿的目标是 H(block header) ≤ target，target越小则mining难度越大。

BTC中使用的哈希函数是SHA-256，产生的哈希值是256位的，所以整个输出空间是2^256。

挖矿难度difficulty = difficulty_1_target / target

挖矿难度最小为1，上面 指挖矿难度为1时对应的目标阈值 / 目标阈值，得到的就是挖矿难度。

为什么要调整挖矿难度？

因为算力越来越高，如果mining难度不变，平均出块时间会缩短，会导致多分叉。

实际上，BTC中的平均出块时间10分钟未必是最优的，后面要学的以太坊的出块时间就降低到了15秒。

如何调整？

BTC协议规定每隔2016个区块（大约两星期）要调整一下 target = target * (actual time / expected time)

其中expected time = 2016*10分钟，为了避免系统中出现某些意外情况，导致系统出现非常大的波动，每次对目标阈值target的调整最大不能超过4倍，最小不能小于1/4。

如果遇到恶意结点不调整target？

target是写在BTC系统的代码里的，代码也都是开源的，如果有结点到了该调整的时候不调整target怎么办。这也是一个大部分结点诚实的问题， 如果不调整target，那么发布的区块块头里的4字节nBits域（32字节的target压缩编码后的版本） 就不是正确的，诚实的结点不会接收这样的区块。

八. 挖矿

全节点

  1. 一直在线

  2. 在本地硬盘上维护完整的区块链信息

  3. 在内存中维护UTXO集合，以便快速检验交易的正确性

  4. 监听比特币网络上的交易信息，验证每个交易的合法性

  5. 监听别的矿工挖出的区块，验证其合法性

轻节点

Tips：BTC中大部分节点都是轻节点，只需要交易不需要mining的话，只需要用轻结点即可

  1. 不是一直在线

  2. 不用保存完整区块链，只要保存每个区块块头（大小比全节点小的很多）

  3. 不用保存全部交易，只需要保存和自己相关的交易

  4. 没法验证大多数交易的合法性，只能检验与自己相关的交易的合法性

  5. 无法检测比特币网络上发布的区块的正确性

  6. 可以验证挖矿的难度（因为挖矿时候计算哈希值只用到了块头信息）

  7. 只能检测哪个是最长链，不知道哪个是最长合法链（因为无法检测这条链上所包含的交易都是合法的）

设备

第一代：CPU，只用到部分指令，性价比太低

第二代：GPU，主要用于大规模并行计算，但是用于浮点运算的部件没有使用，不划算

第三代：ASIC（Application Specific Integrated Circuit）芯片，例如专门为了挖矿而设计的芯片，没有多余的电路。为某一种加密货币设计的ASIC芯片只能挖这一种加密货币的矿，除非两个货币用同一个mining puzzle

矿池

参考：https://buybitcoinworldwide.com/mining/pools/

单个矿工的收益不够稳定，而矿池则是将很多矿工组织起来，一般的架构就是一个矿主（pool manager）全结点去驱动很多矿机，下属矿工只负责计算哈希值，全结点的其它职能只由矿主来承担，有收益后大家一起分配。

对单个矿工而言挖矿难度太大（相比比特币系统的平均出块区间），所以可以考虑矿池将挖矿的难度降下来。比如本来要求前面有70个0，现在矿池只要求前面有60个0，这样挖到的是一个share（almost valid block），即这个区块差不多在一定程度上是符合难度要求的。

这些区块仅作为证明矿工所做的工作量的证明。等到某个矿工真正挖到矿，获取出块奖励之后，再按照提交的share的多少来进行分配。

矿工能独吞出块奖励吗？

答案是不行，因为任务是矿主分配的，铸币交易中收款人地址是矿主的地址，如果矿工改为自己的地址，这样就相当于单干了，矿主不会认可矿工提交的share，跟矿池就没有关系了。但是矿工可以丢弃掉合法的区块，这样做损人不利己。

矿池危害

有了矿池以后，算力被集中起来，攻击者未必拥有很多算力，只要吸引大量的不明真相的群众将算力集中到自己的矿池就可以发起攻击（分叉攻击、Boycott）。

九. BTC脚本

交易结构

1
2
3
4
5
6
7
8
9
10
11
12
13
"result":{
    "txid":"921a...dd24", // 交易id
    "hash":"921a...dd24", // 交易的哈希值
    "version":1, // 使用的比特币协议版本号
    "size":226, // 交易的大小
    "locktime":0, // 交易的生效时间，0代表立即生效，非0代表经过几个区块后才允许上链
    "vin":[...], // 交易的输入
    "vout":[...], // 交易的输出
    "b1 ockhash":"0000000000000000002c510d..5c0b", // 交易所在区块的哈希值
    "confirmations":23, // 目前已经有几个确认，包括自己及其后面有多少区块上链
    "time":1530846727, // 交易产生的时间戳
    "b1ocktime":1530846727 // 该交易所在的区块的产生时间
}

交易的输入

这是一个列表，一个交易可以有多个输入，每个输入要指明来源并给出签名。

1
2
3
4
5
6
7
8
"vin":[{
    "txid":"c0cb...c57b", // 该输入的来源交易的哈希值
    "vout":0, // 该输入对应“来源交易”的哪一个输出。是一个索引值
    "scriptsig":{ // 输入脚本，这里是最简单的形式，只有签名    
        "asm":"3045...0018",
        "hex":"4830...0018"
    }	
}]

交易的输出

交易的输出也可以有多个，形成列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
"vout":[{
    "va1ue":0.22684000, // 金额，即转过去多少BTC
    "n":0, // 序号，表示这个输出在这个交易中的索引
    "scriptPubKey":{ // 输出脚本
        "asm":"DUP HASH160 628e...d/43 EQUALVERTFY CHECKSTG",
        "hex":"76a9.88ac",
        "regsigs":1, // 这个输出需要多少个签名才能兑现，有的输出需要多重签名
        "type":"pubkeyhash", // 输出的类型，此处pubkeyhash是公钥的哈希
        "addresses":["19z8LJkNXLrTv2QK5jgTncJCGUEEfpQvSr"] // 输出的地址
    }
},{
    "va1ue":0.53756644,
    "n":1,
    "scriptPubKey":{
        "asm":"DUP HASH160 da7d...2cd2 EQUALVERIFY CHECKSIG",
        "hex":"76a9...88ac",
        "regsigs":1,
        "type":"pubkeyhash",
        "addresses":["1LVGTpdyeVLCLCDK2m9f7Pbh7zwhs7NYhX"]
    }
}]

脚本举例

脚本举例

如图，B转账给C的交易中指明了币的来源（即A转给B的输出要作为B转给C的输入）。

在早期的比特币系统中，B->C这个交易的输入脚本和A->B这个交易的输出脚本拼在一起执行。

后来，出于安全因素的考虑，这两个脚本改为分别执行，首先执行输入脚本，如果没有出错，那么再执行输出脚本，如果能顺利执行，并且最后得到非零值（true），那么这个交易就是合法的。

如果一个交易有多个输入，每个输入脚本都要去找到前面特定区块中所对应的输出脚本，匹配之后来进行验证。全部验证通过后，这个交易才是合法的。

脚本形式

  1. P2PK（Pay to Public Key）

    1
    2
    3
    4
    5
    input script：
        PUSHDATA(Sig)
    output script：
        PUSHDATA(PubKey)
        CHECKSIG

    例如A->B，B->C，这里的Sig用的是B（后一个交易付款人）的私钥对输入脚本所在整个交易的签名，PubKey则是B的公钥。

    第一条：将输入脚本的签名压入栈

    第二条：将输出脚本的公钥压入栈

    第三条：弹出栈顶的两个元素，用PubKey检查Sig是否正确

  2. P2PKH（Pay to Public Key Hash）

    和P2PK区别是这里没有给出收款人的公钥，给出的是公钥的哈希值

    1
    2
    3
    4
    5
    6
    7
    8
    9
    input script:
        PUSHDATA(Sig)
        PUSHDATA(PubKey)
    output script:
        DUP
        HASH160
        PUSHDATA(PubKeyHash)
        EQUALVERIEY
        CHECKSIG

    第一条：将输入脚本的签名压入栈

    第二条：将输入脚本的公钥压入栈

    第三条：复制栈顶元素（相当于又压入一次输入脚本公钥）

    第四条：将栈顶元素取出来哈希，再压入栈

    第五条：将输出脚本中提供的公钥哈希值压入栈

    第六条：弹出栈顶两个元素，比较是否相等

    第七条：弹出栈顶两个元素，用PubKey检查Sig是否正确

  3. P2SH（Pay to Script Hash）

    1
    2
    3
    4
    5
    6
    7
    8
    9
    input script:
        ...
        PUSHDATA (Sig) // 签名
        ...
        PUSHDATA(serialized redeemScript) // 序列化赎回脚本
    output script:
        HASH160
        PUSHDATA(redeemScriptHash) // 赎回脚本的哈希
        EQUAL

  4. 多重签名

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    inputScript:
        X // 在输入脚本里往栈中添加一个没用的元素，抵消掉BTC其中的一个bug。
        PUSHDATA(Sig 1)
        PUSHDATA(Sig 2)
        PUSHDATA(Sig M)
    outputScript:
        M
        PUSHDATA(pubkey_1)
        PUSHDATA(pubkey_2)
        ...
        PUSHDATA(pubkey N)
        N
        CHECKMULTISIG

Proof of Burn：销毁BTC

应用场景：

  1. 有些小的加密货币（AltCoin: Alternative Coin），要求销毁一定数量的比特币可以得到一定数量的这种币。这时Proof of Burn就可以证明自己销毁了这些比特币。
  2. 往区块链里写入一些内容。因为区块链是不可篡改的账本，有人就利用这个特性向其中写入一些需要永久保存的内容。比如第一节课学的digital commitment，即需要证明自己在某一时间知道某些内容。例如某些知识产权保护，可以将知识产权取哈希之后，将哈希值放在这种输出脚本的RETURN语句的后面。反正哈希值很小，而且哈希值没有泄露原来的内容，将来出现纠纷时，再将原来的内容公布出去，大家在区块链上找到这个交易的输出脚本里的哈希值，就可以证明自己在某个时间点已经掌握了这些知识了。