延伸阅读
Cryptocurrency System（1）：Bitcoin机制的朴素理解
来源：知乎 · 查看原文
如果你要做DEX相关的套利（如跨链套利、Defi、DEX/CEX的套利），对于Chain上协议的彻底理解是一个刚需知识点。这个系列的文章会从经典BitCoin开始介绍，从浅入深讲清楚主流Chain的协议。
在银行 App 里给别人转账，最直观的结果是双方余额发生变化。支撑这件事的是银行维护的账本：谁付了多少，谁收到了多少。Bitcoin 要做的也是记账，难点在于它没有银行。
在这个场景里面，我们可以先问一个更朴素的问题：一个账本系统必须解决哪些问题？银行怎样解决它们？如果不要银行，哪些问题仍能解决，哪些会卡住？区块链正是为卡住的那部分设计的。概念讲清以后，再用伪代码搭一个Toy BlockChain来彻底理解bitcoin的核心机制。
全文的顺序如下：
账本要解决的五个问题
中心化账本：把问题交给一个可信机构
去中心化账本：卡在交易顺序上
区块链：让所有节点对同一份历史达成一致
用伪代码搭一个Toy BlockChain
Bitcoin 的真实实现：签名与地址、UTXO、Merkle 树、候选区块、工作量证明、P2P 传播、分叉处理、SPV 和确认风险
端到端：用时序图和伪代码串起花掉一个 UTXO 的完整流程
账本要解决的五个问题
先放下加密货币。几个朋友经常互相垫付饭钱，与其每次都转账，不如维护一份公共账本，把每笔付款记下来，月底统一结算。此处推荐一个3B1B的学习视频：Blue1Brown：Bitcoin 是怎样运行的
1 Alice 付给 Bob 20 #2 Bob 付给 Carol 40 #3 Carol 付给 Alice 30
记录只有几行，可一旦谁都能往里写，问题就来了。
前两个问题只看单笔交易；顺序问题要在多笔交易之间比较；不可改问题涉及时间，今天确认的历史明天是否仍然算数；发行问题决定账本里的总额怎样变化。
第三个问题对数字货币格外棘手。一张纸币不能同时交到两个人手里，一条数字记录却可以几乎零成本地复制、分别发给两个人。用同一笔钱付两次，叫作双重支付（double spending）。Michael Nielsen 在解释 Bitcoin 协议时，把它和伪造并列为“用信息当钱”首先要克服的两个问题。How the Bitcoin protocol actually works
中心化账本：把问题交给一个可信机构
银行的做法是自己维护唯一的权威账本，所有转账都要经过它。
这套方案很高效，顺序问题几乎是顺带解决的：只有一份账本、一个记账人，谁先谁后由它说了算。
代价是信任。所有人都要相信银行记账准确、系统不宕机、员工不舞弊；银行还能冻结账户，包括依政府要求冻结。Rutgers 讲义：Bitcoin 中本聪在论文引言中写道，金融机构无法回避纠纷调解，交易因而可以撤销；调解成本推高了交易费用，商户也要为防范欺诈向顾客索取更多信息。Bitcoin 白皮书
早期的数字现金方案也走过这条路：设立一个可信的铸币方，由它检查每笔交易是否Double Spending，每次交易后把币交回铸币方换新。论文的评价是，整个货币系统的命运系于运营铸币方的公司，每笔交易都得经过它，和银行没有区别。Bitcoin 白皮书
于是问题变成：能不能不要这个中心？
去中心化账本：交易顺序达成共识是一个难点
最直接的办法是取消中心账本，让每个参与者都保存一份完整副本。要付款时，把交易广播出去，大家各自检查，再记入自己的账本。3Blue1Brown：Bitcoin 是怎样运行的
在 Bitcoin 中，运行 Bitcoin 软件、参与网络通信的计算机叫作节点。其中全节点按完整规则检查账本内容，维护自己认可的账本状态。节点收到新数据后会检查并转发给邻居，记录由此在网络中逐跳传播。Bitcoin.org：Bitcoin 如何运行
没有了中心，把文章开头提到的五个问题再过一遍。
授权仍能解决。 银行靠密码核验身份，去中心化账本靠数字签名。每个人持有一对密钥：私钥自己保管，用来签名；公钥公开，任何人都能用它核对签名。签名同时取决于私钥和被签署的内容，挪到另一笔交易上就无法通过验证。所以不需要银行，每个节点都能独立判断一笔付款是否经过付款人同意。不过，把整笔已签名的交易原样再提交一次，签名依然有效，交易还需要带上能区分彼此的唯一信息。Bitcoin 的 UTXO 模型顺带处理了这一点，后文展开。
余额也能解决，代价是保存全部历史。 没有银行替你记余额，节点就从第一笔记录开始重放全部交易，自己算出每个人有多少钱。验证一笔新交易，需要知道它之前的完整历史。3Blue1Brown：Bitcoin 是怎样运行的 这也意味着，所谓拥有比特币，就是账本里有一些金额，而你掌握着支出它们所需的私钥。
顺序卡住了。 假设 Alice 只有一份钱，却签了两笔交易：tx1 付给 Bob，tx2 付给 Carol。她把 tx1 发给网络的一侧，把 tx2 发给另一侧。节点 1 先收到 tx1，签名和余额都没问题，记账；随后收到 tx2，发现钱已花掉，拒绝。节点 2 的经历正好相反。
每个节点都严格执行了规则，结果却是两个版本的账本。签名只能证明两笔交易都经过 Alice 授权；余额检查只能在某个既定顺序下进行。二者都回答不了哪一笔在先。网络延迟本来就让各节点看到的到达顺序不同，Alice 还可以故意放大这种差异。
论文把这个问题说得很直接：要确认某笔交易之前没有冲突交易，唯一的办法是知道所有交易；没有可信方时，交易必须公开广播，参与者还需要一套机制，对交易先后形成同一份历史。Bitcoin 白皮书
投票也不行。 一个自然的想法是让节点投票，多数说哪笔先到就算哪笔。问题在于网络身份几乎没有成本。Alice 可以开出十亿个傀儡身份，分别告诉 Bob 和 Carol“你那笔已经被多数确认”。How the Bitcoin protocol actually works 论文也指出，若按“一个 IP 地址一票”计票，任何能分配大量 IP 的人都能操纵结果。Bitcoin 白皮书 投票权必须绑定在某种难以伪造的稀缺资源上。
不可改和发行也失去了依托。 每个人手里都有一份账本，任何人都能修改自己的副本，再声称它才是真的；没有审计方，就要让篡改历史在技术上能被发现，在经济上代价高昂。没有央行，新钱的发行规则只能写进所有节点共同执行的协议。
区块链：让所有节点对同一份历史达成一致
问题集中到了一点：一群互不信任、身份可以伪造、收到消息的次序又各不相同的节点，怎样对交易顺序达成一致？Bitcoin 的答案可以拆成四步。3Blue1Brown：Bitcoin 是怎样运行的、Bitcoin 白皮书
第一步，按批排序，不按笔排序。 不再为每笔交易单独达成一致，而是把一批交易装进一个区块。块内顺序由提出区块的人决定，网络只需对“下一块是哪一块”达成一致。到达时间不再参与排序，交易的先后取决于它所在的区块和块内位置。
第二步，用哈希把区块串起来。 哈希是对一段数据计算出的固定长度摘要：同样的数据总得到同样的摘要，内容稍有变化，摘要就几乎完全不同，可以把它当作数据的指纹。每个区块都保存前一个区块的哈希，沿着这些引用向前追溯，最终到达第一个区块，即创世区块。这种前后引用形成的数据结构，就是区块链（blockchain）。
如果有人修改 A 中的付款，A 的哈希随之改变，B 里保存的旧哈希就对不上了；他若连 B 的引用一起改，B 的哈希又会变化，继续影响 C。哈希链让篡改能被发现。反过来，接受一个区块也就接受了它之前的全部历史，因为它的哈希已经间接固定了前面的每一块。区块链的数据结构
第三步，让提出区块变得昂贵。 哈希链只能发现篡改，阻止不了篡改：任何人都可以改完数据，再把后面所有哈希重算一遍，成本微乎其微。Bitcoin 因而要求每个区块附带工作量证明（Proof of Work，PoW）：找到一个数，使区块的哈希满足一个很难碰上的条件，比如前 30 位全为 0。哈希输出无法预测，除了逐个尝试别无他法；单次尝试命中的概率是 2³⁰ 分之一，约十亿分之一。验证却只需计算一次哈希。3Blue1Brown：Bitcoin 是怎样运行的
这一步同时解决了两件事。其一是谁来提出下一块：所有愿意计算的人同时尝试，先找到的人获得提出权，相当于一次按算力加权的抽签，开再多傀儡身份也不会增加中签机会，论文称之为“一 CPU 一票”。其二是改写历史的成本：改动某个区块，就要重做它以及之后所有区块的工作量证明。Bitcoin 白皮书
第四步，冲突时跟随累计工作量最大的链。 两名矿工几乎同时找到区块时，网络会暂时出现两个分支。规则是：在所有有效的链中，跟随累计工作量最大的一条；难度不变时，它就是最长的链。新区块会接在某一条分支上，让它领先，其他节点随之切换过去。攻击者想用另一段历史取而代之，就要让自己的分支在累计工作量上反超；算力少于一半时只能靠运气，落后越多，机会越小。
剩下的问题是：为什么有人愿意花电费去算？每个区块的第一笔交易可以凭空给出块者一笔奖励，再加上块内交易的手续费。这同时解决了发行问题：新币按协议规定的节奏，通过区块奖励进入流通，不需要发行机构。负责组装区块、寻找工作量证明的参与者，叫作矿工。Bitcoin 白皮书
回到 Alice 的双花。tx1 和 tx2 都在网络里传播，矿工各自从中挑选。若某个矿工把 tx1 打包进区块，并率先找到工作量证明，其他节点验证该块后，会发现 Alice 那份钱已经花掉，tx2 就成了无效交易。若两个区块几乎同时出现，分别包含 tx1 和 tx2，分叉会在后续区块中分出胜负。
付款所在的区块被接到链上，付款就获得一次确认；此后每增加一个后继区块，确认数加一。Bob 等到包含 tx1 的区块后面又接上几个区块，这笔付款被推翻的可能性就已经很小了。这就是“等待确认”的含义，最后一节会算出具体概率。
用伪代码搭一个Toy BlockChain
先看中心化账本。只有一个记账人时，一次转账只要几行：
balance = Map<Account, Amount> # 银行数据库里的权威余额
log = [] # 银行自己保存的流水
function transfer(from, to, amount, credential):
require authenticate(from, credential) # 授权：查银行的密码库
require balance[from] >= amount # 余额：查银行说了算的状态
balance[from] -= amount
balance[to] += amount
log.append({from, to, amount}) # 不可改：相信银行不改流水
# 顺序：所有调用由银行串行执行，冲突的第二笔会因余额不足被拒绝
每一行都依赖银行：authenticate 查的是银行的密码库，balance 由银行说了算，串行执行靠的是银行的系统，log 是否可信取决于银行是否诚实。去掉银行，这些隐含保证要逐一换掉。
下面的Toy Model沿用账户余额，对整个区块计算哈希，用前导零的位数表示难度。H 表示一个密码学哈希函数，|| 表示拼接，require 表示检查失败就拒绝，Map 中不存在的键读作 0。先定义交易和区块：
Tx = {from_key, to_key, amount, seq, signature} # seq：付款人的第几笔交易
Block = {prev_hash, transactions, nonce}
DIFFICULTY = 30 # 区块哈希的前 30 位必须为 0
REWARD = 50 # 每块的出块奖励
function block_hash(block):
return H(block.prev_hash || serialize(block.transactions) || block.nonce)
function has_work(block):
return leading_zero_bits(block_hash(block)) >= DIFFICULTY
账户直接用公钥表示。签名覆盖除签名之外的全部字段；seq 使同一付款人的每笔交易都不相同，原样重放旧交易会因序号不符被拒绝。Alice 的 tx1 和 tx2 若使用同一个序号，其中一笔上链后，另一笔会因序号不符失败；即使换成不同序号，余额检查也会拦下第二笔。
全节点不保存可信的余额表，而是从创世区块开始重放整条链。任何一步检查失败，整条链都无效：
State = {balance: Map<Key, Amount>, next_seq: Map<Key, Int>}
function apply_block(state, block):
s = copy(state)
reward = block.transactions[0] # 第一笔：出块奖励，没有付款人
require reward.amount == REWARD
s.balance[reward.to_key] += REWARD
for tx in block.transactions[1:]:
require verify(tx.from_key, digest(tx), tx.signature) # 授权：用签名代替密码库
require tx.seq == s.next_seq[tx.from_key] # 防止重放
require s.balance[tx.from_key] >= tx.amount # 余额：在这条链的历史上检查
s.balance[tx.from_key] -= tx.amount
s.balance[tx.to_key] += tx.amount
s.next_seq[tx.from_key] += 1
return s
function replay(chain):
state = empty_state()
for i in indices(chain):
if i > 0:
require chain[i].prev_hash == block_hash(chain[i - 1]) # 不可改：哈希链
require has_work(chain[i]) # 不可改：工作量
state = apply_block(state, chain[i])
return state
余额检查仍然存在，只是检查的对象从“银行的数据库”换成了“这条链重放出来的状态”。节点的其余工作，是收交易、挑链和挖矿：
my_chain = [GENESIS]
pending = set() # 收到但尚未上链的交易
function total_work(chain): # 难度固定，每块工作量相同，累计工作量与块数成正比
return len(chain) * 2^DIFFICULTY
function on_transaction(tx):
pending.add(tx)
broadcast(tx)
function on_chain(candidate): # 顺序：只认累计工作量最大的有效链
if total_work(candidate) <= total_work(my_chain):
return
if try_replay(candidate) is invalid: # 与 replay 相同，任一 require 失败时返回 invalid
return # 违反规则的链，算力再多也不接受
my_chain = candidate
broadcast(my_chain)
function mine_one_block(my_key):
tip = last(my_chain)
state = replay(my_chain)
block = {prev_hash: block_hash(tip),
transactions: [reward_to(my_key)] + valid_subset(pending, state),
nonce: 0}
while not has_work(block): # 没有捷径，只能逐个尝试
if last(my_chain) != tip:
return # 别人先出了块：放弃，基于新链顶重来
block.nonce += 1
my_chain.append(block)
broadcast(my_chain)
valid_subset 按顺序挑出在当前状态上仍然有效的交易，tx1 和 tx2 只能选中一笔。为简洁起见，这里省略了从 pending 中删除已上链交易的步骤。
把前面的双花代进去：矿工甲的 pending 里先有 tx1，矿工乙的先有 tx2，两人各自开始计算。甲先算出来并广播，其他节点重放甲的链，验证通过后切换过去；乙发现链顶变了，放弃手里的块，基于新链重新组装时，tx2 已经通不过序号或余额检查。账本又回到了同一个版本。
这个Toy Model可以运行，但离 Bitcoin 还有不少距离。下表列出两者的主要差别，也是后文各节的顺序。
下面进入 Bitcoin 的真实实现。金额以聪为单位，1 BTC 等于 100,000,000 聪。
钱包、私钥、公钥与签名
Toy Model直接把公钥当作账户。真实的 Bitcoin 把这件事拆给了几个不同的东西：用户通过钱包收付款，钱包是一种管理密钥、生成收款地址、构造交易的软件。
以用户自己掌握密钥的钱包为例，钱包会管理一组密钥。私钥是一段秘密数值，钱包用它为付款生成签名；公钥可以由私钥计算出来，用于核对签名。公钥可以公开，持有公钥的人能够验证签名，却无法在可行的计算成本内据此反推出私钥，或替持有人签出新的付款。公钥、私钥与签名
前文说过，数字签名同时依赖私钥和被签署的内容，不是每次都贴上去的同一张签名图片。Alice 签署的内容包括 Bob 的收款条件和金额；这些内容被改动后，原签名就无法通过验证。
把签名这件事单独取出来，只有三步：
钱包根据私钥得到公钥 public_key = derive_public_key(private_key) # 付款时，用私钥对约定的交易内容摘要签名 signature = sign(private_key, transaction_digest) # 其他节点用公钥核对签名，全程不需要拿到私钥 valid = verify(public_key, transaction_digest, signature)
签名证明的是授权，交易内容本身仍然公开。公钥在这里用于验证，不是拿来把付款内容加密成只有收款人能看的消息。
实际收款时，Bob 发给 Alice 的通常是一个地址。地址把收款条件编码成钱包能够识别的字符串，付款方据此指定这笔钱将来可以怎样花费。公钥负责核对签名，地址负责表达收款条件，二者并非同一个数据。不同地址格式表达条件的方式也不同。
Alice 给 Bob 付款时，用的是 Alice 的私钥，因为正在花费的是 Alice 控制的钱。Bob 的地址决定新产生的收款金额归什么条件支配。等 Bob 要把这笔钱继续付出去时，才轮到 Bob 用自己的私钥签名。交易授权与收款条件
钱包里保存或调用的是密钥，金额的归属记录在链上。钱包显示余额时，会根据链上的记录找出自己能够花费的金额。因此，拿到收款地址可以给人付款；拿到私钥则意味着掌握相应的花费能力。钱包的工作方式
和前文的双花例子一样，签名不替节点决定付款的先后。两笔冲突付款的签名可以都来自 Alice，节点要结合账本中的已有记录，判断哪笔交易还有权花费那份钱。
一笔交易改变了什么
Toy Model给每个公钥记一个余额，再用序号防止重放。Bitcoin 不维护账户余额：钱包显示的是一个余额数字，全节点核对的则是一份份具体的可花费记录。这些记录叫作 UTXO，即 Unspent Transaction Output，尚未花费的交易输出。普通交易消耗一个或多个旧输出，再创建新的输出，分别指定金额和花费条件。
这样一来，防重放和防双花变成了同一条规则：每个输出只能被花费一次。一笔交易花掉某个输出后，该输出就从可花费集合中消失；把这笔交易原样再提交一次，或者另签一笔交易引用同一个输出，都会因为找不到它而失败。UTXO 是 Bitcoin 的设计选择，并非去中心化的必要条件，Ethereum 就采用账户余额模型。Rutgers 讲义：Bitcoin
可以把一个输出看成一张带有领取条件的票据。它有金额，也有锁定条件；下一笔交易引用它，并提供满足条件的证据。全节点维护的 UTXO 集合，记录当前链上还有哪些票据可以使用。钱包显示的余额，则是它能够花费的那些输出的金额总和。一个输出用 (txid, 输出序号) 唯一定位：交易标识符 txid 指出是哪笔交易，输出序号指出是其中的哪一个输出，从 0 开始编号。这个二元组叫作 outpoint。交易结构与 UTXO
假如 Alice 有一个 100,000 聪的输出，要向 Bob 支付 60,000 聪，并给矿工 1,000 聪手续费，交易会长这样。
输入一次用掉整个旧输出。找零是新建的输出；手续费是总输入和总输出的金额差额。
下面的伪代码采用单密钥付款，签名摘要、脚本与锁定条件交给具名函数处理。require 表示检查失败就拒绝；range(a, b) 包含 a、不包含 b；^ 表示乘方。
Outpoint = (txid, output_index)
Output = {value, locking_condition}
Coin = {output, created_height, is_coinbase} # 最后一项标记它是否来自区块奖励
UTXO = Map<Outpoint, Coin>
tx.inputs = [{previous_output: (A, 0)}]
tx.outputs = [
{value: 60_000, locking_condition: pay_to(Bob)},
{value: 39_000, locking_condition: pay_to(Alice_change_key)}
]
previous = lookup_previous_outputs(tx)
for i in indices(tx.inputs):
# 对本次花费的内容签名，私钥不进入交易记录中
digest = signature_digest(tx, i, previous, mode=ALL)
tx.inputs[i].authorization = sign(Alice_private_key, digest)
这里的 ALL 表示签名承诺这笔付款的输入引用和所有输出等内容。若有人把 Bob 的收款输出换成自己的，签名验证就会失败。
全节点验证普通交易时，核心工作是检查引用、授权是否合法和金额守恒。下面的函数只计算状态变更，所有检查通过之后才把它应用到 UTXO；中途失败就不会留下“已经扣款”的半个状态。
function check_regular_transaction(tx, view, context):
require not is_coinbase(tx) # 区块奖励交易另行处理
require valid_structure_and_money_ranges(tx)
require inputs_are_unique(tx)
require locks_are_satisfied(tx, view, context)
previous = []
for input in tx.inputs:
coin = view.get(input.previous_output)
require coin exists # 已花费的输出不在这里
if coin.is_coinbase: # 区块奖励的输出要等到成熟才能花费
require context.height - coin.created_height >= 100
previous.append(coin)
# 所有输入的授权均通过后，再生成账本变更
for i in indices(tx.inputs):
require verify_spend(tx, i, previous, context)
input_value = checked_sum(coin.output.value for coin in previous)
output_value = checked_sum(output.value for output in tx.outputs)
require input_value >= output_value
delta = {
remove: all input.previous_output,
add: each (txid(tx), i) -> Coin(tx.outputs[i], context.height, false)
}
return {delta, fee: input_value - output_value}
result = check_regular_transaction(tx, view, context)
view.apply_atomically(result.delta)
view 是某个明确链状态的视图。检查新区块时，它从该块父节点的 UTXO 状态开始，并按区块内交易顺序变化。因此，一笔交易可以花费同一区块里排在前面的普通交易输出；同一个输出被花掉后，第二次引用就会失败。对金额范围、重复输入、coinbase 成熟期的具体检查，可对照 Core 的 交易结构检查 和 输入检查。
Alice 仍然能构造另一笔交易，引用 A:0，把钱转给自己。孤立地验证两笔交易的签名，都会成功。只有把它们放进同一个不断更新的 UTXO 状态，冲突才会显现。这也是 Bitcoin 需要全网共同历史的原因。这笔交易从钱包签名到被区块确认的完整经过，见后文“端到端：花掉一个 UTXO 的完整流程”。
区块怎样固定一批交易
Toy Model把整个区块拿来算哈希。真实区块分成两部分：主体保存交易列表，区块头保存这批交易的摘要以及前一个区块头的哈希。挖矿和链接都只针对 80 字节的区块头，交易再多，每次哈希的输入也一样大。交易列表怎样汇总成一个摘要？Bitcoin 使用 Merkle 树，最后得到的根哈希称为 Merkle root。
下文用 H(x) 表示 SHA256(SHA256(x))，即 Bitcoin 用于区块头和这里的 Merkle 树的双 SHA-256；a || b 表示拼接字节。
Merkle 树的叶子是交易标识，父节点是左右子节点拼接后的哈希。假设区块里有四笔交易：
h0 = txid(tx0)