区块链的后量子迁移

《应用后量子密码学》本章的全部代码：共 3 段，其中 3 段可在此运行。编辑任意单元格，然后点击运行。

书中的代码片段在一章之内层层相依，但 Sage Cell 内核每次只运行一个单元格，运行后不保留任何状态，因此每个单元格都会用 apqc_book 重放此前的代码。这一调用是在书中原有代码之外唯一添加的内容。

← 在线演练

代码 1：SageMath 实验：承诺与求值协议

这两幅图都短到可以直接运行。第一个代码清单是在一个玩具版环 R_q=ℤ₁₂₂₈₉[x]/(x¹⁶+1) 中实现的书中的图，取 =2、n=8：一个均匀随机的 A，一个三元见证，承诺 t=As，以及验证者的两项检查。这些参数对安全性而言太小了；之所以这样选取，是为了让每个对象都可以打印出来。

代码 2：SageMath 实验：承诺与求值协议

第二个代码清单接续第一个，运行书中的图：一个由短环元素组成的 n× m 矩阵 F，m 个内层承诺，到 16 进制数字的小工具分解以及外层承诺 u，然后是三轮交互和五项检查。digits 即 G^-1，undigits 即 G；除了通过 u 和交给它的数字之外，验证者从未看到 F 或各 t_j。篡改一个部分求值会使检查 5 失败，这正是 z 所强制的一致性。

代码 3：迁移受区块空间的限制

这是路线图争论往往略过的约束。迁移一枚币不是一次数据库更新；它是一笔交易，而交易要争夺固定且相当小的区块空间。因此，任何迁移可能的推进速度都有一个下限，而它只取决于算术——需要移动的输出数量、一次后量子花费的尺寸，以及链的吞吐量。

记 N 为需要迁移的未花费输出数量，w 为单笔迁移交易消耗的权重，W 为每个区块可用的权重，T 为出块间隔。即使把每个区块的每一个单位都交给迁移，仍然需要

而在区块空间份额为 σ 时，这个数字按 1/σ 放大。

这个界有两个特点值得强调。它是一个下界，假设链的全部容量都用于迁移而别无他用——没有支付，没有普通的经济活动——这是任何运行中的链都无法容忍的。而且它由 w 驱动，而对于后量子花费，这一项由签名和公钥主导，而这恰恰是比其所替换者大一到两个数量级的量。本书通篇列出的尺寸不仅仅是带宽上的麻烦：它们决定了迁移本身的时钟。

一项已发表的针对 Bitcoin 的此类分析报告称，在其关于哪些输出必须移动以及一次迁移花费代价的自身假设下，所需的停机时间约为数月的独占区块空间。下面的练习构建了一个更粗糙的模型，并得到了一个更大的结果；这种差异正是有启发性的部分，而调和两者正是目的所在。

remark[为何这重塑了整章的框架] 本章中其他每一个量都存在争议：Q-Day 何时到来，冻结是否正当，哪种签名方案胜出。吞吐量界则不然。它由区块大小、签名尺寸和算术推出，它表明，即使是一个协调完美、意见完全一致、钱包支持即时到位的生态系统，也无法迅速完成迁移。这是支持尽早开始的最有力论据，而且它不需要在任何关于量子硬件的争论中获胜。 remark

*练习：计算这个界

公式对 w 的敏感性最好通过求值来体会。使用“面向后量子密码的 SageMath 基础”一章的工具：