五、为一次性密钥定制的区块链化后量子签名

大多数（如果不是所有的）少次哈希签名方案都使用了默克尔树（Merkle tree）。一个基本默克尔树（Merkle tree）签名方案最多可签名的信息数量是2＾h，其中h是树的高度。此外，所有子叶（密钥）应该是在密钥生成期间计算以形成根。由于上述原因，要构建一棵高度为h ＝ 40的树，这样的密钥生成将被认为是不切实际的，因为我们需要计算2＾40 个OTS密钥，而每个OTS密钥都需要很多哈希调用（例如Lamport OTS就需要512哈希调用，或者当使用SHA256的WOTS （w ＝ 16）时就需要67哈希调用）。保持密钥生成时间切实可行的同时，还可以允许大量签名使用一棵多层次树。

BPQS是XMSS类协议［5］的一个简化单链变体，字面上讲，它是基础默克尔树签名方案（见图1）的一种扩展。 BPQS理论上可签名很多次，但其设计着眼于短和快速的一次性签名，如果有需要的话，有额外的选项可重新签名。以上的要求是典型的区块链或分布式账本技术（DLT）所需要的，因为使用一次性密钥可保持匿名性。但是，很多事情可能会出错，例如，一笔交易可能无法通过，或者区块链中可能会出现分叉，在这种情况下，应该能够在不损害安全性或冻结资产的情况下签署多次（见IOTA的问题［21］， ［42］）

此外，BPQS的另一个好处在于，它对于相反要求（用同一个密钥签名多次）而言也是一个理想的候选方案，这个有趣的属性是因为，区块链和分布式账本系统的底层图形结构，较其他基于哈希的后量子（PQ）解决方案而言，它以最小的代价有效地允许多次签名。这是通过引用过去已被使用的相同BPQS密钥的区块（或交易）来实现的。简而言之，只有一小部分的新签名是需要被提交的。实际上，因为先前的交易已经在账本上得到了验证，因此验证者们不需要验证路径的其余部分，因为它在过去已经被验证过了。这个特性使得BPQS对基于公证的分布式账本特别有用，例如Corda ［22］以及Fabric ［43］，因为公证节点通常会用相同已知的密钥来签名交易。

A． BPQS方案

BPQS需要一个基层的OTS方案。理论上，任何OTS方案都是可应用的，但我们的方案与 XMSS系列协议的逻辑是相同的，因此我们会选择WOTS ［19］变体，使用L树以及位掩码的生成定义了安全假设以及证明，类似于XMSS ［5］，其多级版本XMSS－MT［44］以及XMSS－T ［27］。此外，根据［39］，使用量子算法的碰撞阻力实际上会更便宜，因此它类似于Gravity SPHINCS ［33］方案，而位掩码和L树可能会被省略。

你也可以说BPQS是XMSS系列方案的一个子集，它主要面向的是快速一次性签名。其中存在的主要区别在于，XMSS通过使用哈希树克服了每个密钥对消息的限制，其会减少很多OTS验证密钥对一次公共XMSS根密钥的真实性；相反，BPQS使用了一个包含小型2子叶默克尔树的链。从几何定义上，XMSS在宽度和高度上都会增长（见图1），而BPQS仅在链高度上成长（见图2）。总而言之，我们强调，BPQS是一个通用的区块链结构，其中的区块是“微小”的默克尔树，这意味着，根据应用的要求，它是可被参数化的。如果遮掩码得到应用，它们的确定性生成应该遵循与相应XMSS系列方案相同的逻辑。

BPQS签名方案有两个基本构建部分：

1．BPQS－FEW：其严格支持少次性签名，如图2所示（左侧）；

2．BPQS－EXT：理论上可扩展到支持多次性签名，见图2（右侧）；

在BPQS－FEW当中，所有的密钥都是在密钥生成过程中预先计算的，每个额外签名的惩罚，仅仅是1个额外的哈希输出，但它不能扩展到实际支持“无限的”签名。

另一方面，BPQS－EXT最初只需要两个OTS密钥，这与BPQS－FEW形成了对比，在一个OTS回滚密钥的每个2子叶默克尔树的左侧叶，当有需要时，它可被用于签署下一个区块。不幸的是，可扩展属性是需要付出代价的，每个新签名都需要一个额外的WOTS密钥。

图片2 ：BPQS－FEW（左侧），一个少次性签名方案。BPQS－EXT（右侧），一个线性可扩展多次性签名方案；

完整的BPQS方案通过一种方式（其中BPQS－FEW链中的最后一个子叶在一个BPQS－EXT回滚密钥中），从而结合了BPQS－FEW以及BPQS－EXT。这种技巧，允许我们把少次签名方案变体转换为多次签名方案。实际上，BPQS－EXT可以被认为是BPQS的一个特例，其中它没有初始的BPQS－FEW链。

图3： 完整的BPQS协议，其具有高度为3的BPQS－FEW顶层和一个BPQS－EXT回滚密钥，以允许扩展性。

BPQS的参数包括：

1、使用的WOTS变体（例如，WOTS－T ［27］）； 2、Winternitz参数（例如w ＝ 16），其定义解释初始哈希的基础。类似于XMSS ［5］，w 定义了每个WOTS链的实际大小，这反过来会影响签名大小。请注意，文献中对Winternitz参数的说明没有达成一致。例如，在 LMS ［45］当中，它被定义为2＾w，因此 wBPQS ＝ 16 ＝ 2＾4 这就相当于wLMS ＝ 4， 3、底层哈希函数（例如SHA384）； 4、预先计算的OTS密钥的数量，即初始值高度（例如，h ＝ 4）；

B． 混合型BPQS

BPQS的可扩展性属性，可实现各种自定义结构。 BPQS可被用作一个构建块，将任何哈希签名方案转换成一种 ｛一次性或少次｝优化方案。例如，在图4当中，BPQS－FEW被用作第一个（较短的）签名，然后它回滚到另一个后量子（PQ）方案。虽然在描述的方法当中，回滚（其它）后量子（PQ）方案的密钥对应该是先验已知的和预先计算的，你也可使用类似的方式来应用BPQS－EXT，所以，这不一定是一个要求，而“其他”后量子（PQ）密钥仅在（几次性）签名耗尽时才会被生成。

而且，如果“其他”后量子（PQ）方案是无状态的，比如说SPHINCS，那么最终的协议差不多就是一个“启动时有状态，然后转到无状态”的方案。

应该强调的是，“其他”后量子（PQ）方案可能会是另一个BPQS方案，所以最终可以创建一个不同BPQS方案的链。后者会导致较短的签名，以及每次仅使用BPQS－EXT来扩展它。

关于“其他PQ关键参数”，则如图4所示，重要的是，需要一些方案发布位掩码（或者在XMSS－T ［27］中的种子）作为初始公告公钥的一部分。否则，它将允许敌对方在一次伪造活动中选择种子／位掩码。然而，如果BPQS使用具有更大输出的哈希函数（例如SHA384 或者SHA512），这可能就不是必需的，因为其所提供的抗量子碰撞攻击安全性，仍然足以防止此类攻击。

图4： 一种通用的BPQS协议（BPQS－VERS1），其带有高度为3的顶层BPQS－FEW，其最后的一个根是另一个后量子（PQ）方案（例如XMSSMT ［44］ 或SPHINCS＋ ［32］）的公钥。

C． 组合后量子（PQ）方案

如前所述，如果有需要的话，BPQS可以回滚到另一个后量子（PQ）方案，通过应用一个类似的逻辑，图5展示了将多个后量子（PQ）方案组合成一个方案的多种定制模型。方法是非常简单的，但它允许非常有用的结构，例如在图5 A和B当中的“有状态和无状态”方案，或者在图5 C中的“带有无状态回滚的有状态”方案。后者为集群环境（其中多个节点需要在签名状态上达成共识）提供了一个解决方案，而回滚机制，是当共识由于某些原因失败，而确保系统能够继续运作（保持功能）的一个先决条件。

图5： 使用并行BPQS逻辑将多种方案组合成一个实用后量子（PQ）方案的各种推荐设计。注意，如果底层方案需要额外的参数（如位掩码），这些应该和根公钥一起发布，类似图4所示 这三种描述到的方案，关于以下两个因素时，提供了不同程度的灵活性：

1．在密钥生成时间和签名大小之间选择一个平衡；

2．在稍后的时间里，决定是否允许选择底层算法；

例如，选项B需要生成两个PQ密钥，以形成待公告的组合公钥，同时选项A实际上是一个BPQS－EXT，它会被用于签署“即将到来”的PQ方案。沿着同样的路线，选项C是组合了A和B，但是左PQ方案不需要通过A－priori（先验）算法选择和计算。

注意，我们甚至还可以把两个不同的有状态的或无状态的方案结合起来，例如，如果出于兼容性需要，在两个不同的区块链中使用相同的密钥时，一个支持原有的SPHINCS－256 ［23］ 方案，而另一个则支持它的变体（或者其标准化版本）。

六、 实验结果

本节内容，将基于广泛的实验，展示BPQS方案的性能分析，并和一系列最先进的签名方案进行对比。选择这种对比方式，是因为它非常流行于今天的PKI和区块链社区。我们的实验结果，基于了一个可用BPQS签名方案的原型实现 ［46］，其中包括了如何重现基准测试的细节。

我们所选用的系统规格，包括八核的英特尔酷睿i7－7700HQ处理器（2．80GHz），15．5GB的内存，而系统运行的环境为 Linux 4．13．0－38以及JRE 1．8．0＿161。关于实施方案，标准JCE已经用于哈希函数调用，而用于其他方案的实现，则分别基于BouncyCastle （ECDSA，RSA， SPHINCS－256） ［47］以及 i2p （EdDSA） ［48］库。

性能比较

表2 比较了各种签名方案的性能，包括使用SHA256和SHA384作为底层哈希函数的BPQS签名方案（w ＝ 4和w ＝ 16这两种情况）。报告结果的平均运行时间，以毫秒为单位。我们选择一个消息列表，而不是选择单个或少量信息的主要原因，是为了避免签名及验证操作当中可能出现的任何偏见现象。

表2：密钥对生成时间（单位：ms），签名和验证第一条消息的时间（单位：ms）。

需要强调的是，目前我们实施的BPQS方案是没有对并行处理进行优化的，它也不会缓存WOTS哈希迭代的中间结果。而缓存密钥秘密可大幅加快签名的处理速度，这已是公认的［33］ 。在实践过程当中，因为BPQS签名方案最好是用于仅签名一次或几次的应用，因此OTS密钥的路径和数量相对较小，并且很容易放入内存当中。如果所有完整的WOTS结构，在密钥生成期间存入了内存当中，则签名无非就是一些内存查找，它不会涉及运行任何哈希操作，这就排除了前面所需的消息哈希。

即使没有实现并行化或缓存，BPQS签名方案和经典及后量子（PQ）数字签名算法的表现都是比较靠近的。需要强调的是，最简单的BPQS形式（BPQS－EXT），已被用于上述比较，其中会生成两个WOTS系列密钥，其中一个是签署第一则消息，另一个密钥则负责签署回滚操作。我们希望，一个区块链密钥的平均使用次数为1，而额外的签名只有在罕见和特殊的情况下才会进行，因此我们的比较也集中于第一次签名操作。在实践当中，我们期望区块链钱包都能够实现缓存和并行化，以进一步提升性能。

关于签名大小，所有BPQS模式，在前（log2（h） ? 1） 次签名的表现都要优于XMSS签名方案，BPQS签名大小随密钥被重用次数而线性增长，因此签名输出的长度是动态的。它开始会很小，但会随着签名数的增长而增长。参数应该在初始密钥生成成本和签名大小之间进行权衡。在最好的情况下，签名的大小会随每个额外签名的一次哈希输出大小的增长而增长，而最坏的情况，则是随一次WOTS ［19］的大小而变化。

图6： 不同模式BPQS和XMSS ［5］签名方案支持32个OTS密钥的签名大小对比。所有方案的签名输出为 ｜W OT S｜ ＋ x ｜H｜，其中x是完全签名路径所需的额外哈希数。在这个图表当中，X轴代表签名的数量，而y轴代表x； 在大多数BPQS模式中，第一次签名输出的大小为 ｜W OT S｜ ＋ ｜H｜，而对XMSS而言，它的签名输出大小为｜ W OT S ｜ ＋ h×｜ H ｜，其中h是所用默克尔树的高度。当最为常用之一的WOTS（w ＝ 16）被用作底层OTS方案时，则每个WOTS的大小为 ｜W OT S｜，这就等于67 × ｜H｜，其中 ｜H｜是底层哈希函数的摘要大小（例如对于SHA256而言，就等于256位）。图6描绘了对于以下方案，每个额外签名的签名大小：

1．BPQS－FEW （图2左侧），其中 h ＝ 32；

2．XMSS ［5］，h ＝ 5，其中h代表树高；

3．BPQS－VERS1 （图4），回滚到XMSS，高度h均为5；

4．BPQS－GEN－B （图 5 B），右侧是BPQS－FEW，左侧是XMSS，俩者高度都为5；

七、结论及未来的工作

在这篇论文当中，我们介绍了BPQS签名方案及其扩展方案，以支持 ｛一次性和少次性｝优化后量子（PQ）签名方案。我们还提出了区块链和分布式账本技术即将面临的安全挑战，然后解释了为什么我们不建议将纯OTS方案作为抗量子计算的替代品。如上所述， BPQS较传统的非量子签名方案（例如RSA、ECDSA以及EdDSA）会更具一些优势，它可以提供更可靠的量子安全性，这是因为它的加密哈希函数会更安全。

其中，BPQS协议的主要特征包括：

1、更短的签名、更快的密钥生成，当签名只进行一次或少数次数时，其签名和验证时间会比XMSS ［5］和SPHINCS［23］ 系列后量子（PQ）协议也会更短，而在区块链系统当中，这样做也可以实现更好的匿名性； 2、它在计算上与非量子方案相当。人们可以利用易于应用的多哈希链WOTS并行化和缓存，以提供几乎即时的签名和更快的验证； 3、其可扩展性属性，允许多次签名，它也可以很容易地进行定制，如果需要的话，它也可以回滚到另一种多次签名方案； 4、将其应用于区块链和分布式账本应用时，它可以通过引用先前的交易（其中相同的密钥会被重用），从而利用底层链或图结构的优势。这可能意味着，每个新的BPQS签名，只需要一次OTS方案的努力，因为其余到根的签名路径已经在账本当中了，因此可省略它们； 5、它可被用作一个构建块，用于实施新颖的PQ方案，例如同时的“有状态和无状态”方案，其可能会使集群环境受益，当共识消失时，其中的节点可回滚到无状态方案；另外，这样的方案可以用于向前和向后兼容的目的，或者当要求在两个独立和不兼容的区块链中重用一个密钥时；

这种原始BPQS协议的主要缺点在于，其签名输出大小是会随签名数量线性增长的。但是，我们可使用一种组合PQ方案或利用区块链应用当中现有的图形结构来减轻这种影响。总而言之，BPQS存在的可定制、缓存以及可扩展性属性，使其成为区块链理想的候选签名方案，它可以作为无状态、有状态以及其他PQ方案之间的一个桥梁协议。