简介
针对交易验证问题（需要验证最难链）
现有的SPV：需要下载和验证所有块头，网络和存储开销大
PoPoW（proofs of proof of work）：PoW的证明，依赖于超级块的概念，需要对数级别的通信和时间开销
- 只能应用于出块难度不变的PoW
PoPoW可能被攻击：
- 难度提升攻击（difficulty raising attack），恶意矿工专门去开采难度较大的块，虽然这样的块出块较慢，但恶意矿工可以用这样的块去欺骗轻节点，形成一条看似有效的链
- 更容易出现贿赂（贿赂矿工来丢弃超级块，因为开采超级块不会获得更高的奖励）或自私挖矿的现象（selfish mining）
super block超级块：解决了比当前PoW目标问题更难的问题
NIPoPoW（noninteractive proofs of proof-of-work）：PoW的非交互式证明，存储开销降低到对数级别
- 只能应用于出块难度不变的PoW
- 为了避免遭到难度提升攻击，轻节点可以检查难度变化是否是合法的，或是检查难度变化是否给矿工带来了相应的好处（？）
- 在有恶意节点时（面对贿赂或自私挖矿攻击时）复杂度较高（变回了传统的SPV）
FlyClient能够做到
- 块头数据的对数级别存储
- 非交互性证明
- 不基于超级块
- 可以用于出块难度变化的链
- 经过验证后，只需要保存单个块，即可验证链上的所有数据（？）
SPV
SPV假设：最长的链符合出块规则且最终会被大部分节点所接受
SPV在跨链中也有广泛应用
SPV开销随着链的增长线性增加
FlyClient
概率抽样：抽取logn的块进行验证，保证恶意节点在伪造真实链c部分时仍能使用
高效的承诺：使用MMR的数据结构，只需要提供固定大小的承诺
可变难度MMR检查：让用户可以检查到难度的变化是否遵循链的规则，避免遭到伪造超级块的攻击
非交互式验证及可转换证明：使用FiatShamir heuristic，轻节点和全节点都可以将证明转发给其他节点，不需要进行另外的计算
场景
区块链系统中存在最长有效链C，用户需要验证链上的一条交易存在
唯一有效链为迄今为止网络中存在的最高难度链
验证流程：
- 用户连接到一组全节点（至少有一个诚实的全节点），暂时考虑两个全节点的情况（论文提出可以将两个验证者的情况扩展到多个验证者）
- 每个全节点都向用户发送最新块，或是整条链的区块头，并说明链长
- 全节点都提供了相同的链长和最新块，则用户选择信任该信息
- 提供了不同的信息，需要使用概率抽样协议来进行进一步确认
- 全节点发送最新块$B_n$和MMR根，用户根据概率分布g ( x )从全节点中采样若干随机块；对于每个需要采样的块，全节点提供块头和对应的mmr根
- 用户进行验证，如果任意块的MMR对应的根错误，或PoW结果不正确，则认为该链是无效的，否则认为该链有效，$B_n$为最新块
- 最后验证交易tx在块B中，使用merkle proof即可
