Casper FFG及轻客户端
每晚八点，我们在社区分享知识，等你。
NervosFans 微信公号：Nervosfans
入群请加乐乐微信：sensus113 美果大冰微信：xj73226
备注入群，谢谢！
我脚着该站出来主持一下Casper beacon链（或者说Casper FFG一大家子）的轻客户端设计了。先说点已有的问题：
1. 验证人集有可能会非常大，而且需要验证的签名也会很多。
2. 原始的Casper FFG规范中，验证人集可以在2代（注：dynasty=朝代，每代换掉3%验证人）之内（40分钟的样子）改变，意思是说轻客户端无法快速“跳”链，原因是验证第N时期（epoch）没法（向轻客户端）保证验证第N+4时期要信任哪些签名。
3. 验证人集变更的验证需要Merkle证明，从而导致额外的O（log（N））因素开销。
下面与老版Casper FFG对比下，假设押金数额为32ETH。假设有1000万枚ETH参与（验证），意思是有1000万/32 = 312500个验证人。
每个时期都需要所有验证人的签名：312500 * 100（64 +开销）= 31.2 MB
每代都要检查新的验证人集，原因是验证人集与许多其他数据一起保存在（Casper）合约中，所以验证人集有可能是个有312500个条目，一共带（比方说）1亿个密钥的特里结构。
这个的大小大约是：
128 *（log（1亿）- log（312500））* 312500 + 32 * 312500 = 227 MB
意思是说必须每20分钟或以107 KB/秒的速度下载并检查这么多数据。然后，完成这项任务的还得是轻客户端。
我们试试看能否做出优化。
首先，将验证人集存储在一个单独的树中，就整个Merkle树好了。
所以，检查新验证人集的数据复杂程度就变成了32 * 312500 = 10 MB。
下一步，用BLS聚合签名代替64字节签名；就按照2.1规范来好了，意思是每个时期有1280个BLS签名。
因此，签名数据复杂度降至1280 * 64 = 81920字节，再加上312500位的位字段（39062字节）。这时，签名大小为121 KB，总大小为10.1 MB。
还可以在数据结构中引入一个叫做“最近变更日志”的链接列表，就是个“索引87124使用密钥0x7182641b5登录，索引88029已退出，索引40125使用密钥登录0xab41265b3......”形式的流水账。
鉴于登录或退出会有4个月（约等于8333个时期）的延迟，即便所有ETH（1亿个）都快速的登录和退出，折到每个时期的话，至多是750个变化（登录然后退出），一般来说这个变化范围约在1-50。
那，我们姑且假设这个变化量是100，登录约36个字节、退出约4个字节，平均下来约20个字节，那么折到每个时期就是20 * 100 = 2000个字节大小的变化。
规定轻客户端需验证所有权证明（proofs-of-possession），则登录大小增加64个字节，因此每个时期验证人集更新的大小为5200个字节。昂，就是126 KB！
我们再接再厉，看看能否接着优化。前面说了，每个时期客户端需要验证1280个BLS签名。那，要是客户端愿意接受概率性保证呢？
假设客户端每个块检查两个签名：提议者和随机选取的签名，因此每个时期需要验证的签名数量变成128个。
这代表了一个随机选取的分数，因此很难在不知道所有签名的情况下，蒙出来随机签名，这样就够用了。50%攻击者或许能够跳脱轻客户端欺诈，剩下的想攻破一个门限签名都很难。
下面我们看看这个12.1 KB的签名。可以将登录/注销痕迹与所有权证明相分离，并允许客户端信任验证人去验证所有权证明，不必躬亲。这样一来，验证人集痕迹被压缩至2 KB。昂，签名变14.1 KB了。
最后一步优化叫‘跳时期’，意思是每12个时期签名验证一次。
代变化至多每四个时期一次（当前是这样的），只有3%的验证人集有发生变化，因此客户端检查（跳检）验证人集的签名时，（验证人集）变化至多为12%。
客户端为验证聚合签名，仍需下载全部的验证人集变更日志，但不用全部签名查一遍。那么现在，每个时期验证的签名大小降至约1.01 kB。终于到3 KB了。
当前的PoW链要求每14秒检查500个字节，或者每20分钟检查约42.8 KB，没有随机采样签名的话，效率其实是降低的，但是有了之后效率显着提高效率。愿意的话，轻客户端还可以要求发送过来的是聚合BLS签名，又省出来足1KB，但不是计算开销。剩下的开销将维持最新的验证人集。
