抵御量子攻击的密码协议金丝雀

Siyu Chen

感谢Felix Cai, Eric Zhang对金丝雀设计中的问题的反馈。

对于任何基于密码学的协议，密码算法的安全性是保证协议运行的基础。在区块链中被广泛使用的密码算法，其安全性通常都经过了严格的证明。但随着人类掌握新型能源以及计算范式，这些密码算法并不是永远安全的。例如，基于离散对数困难的加密和数字签名算法将在可预见的将来被量子计算机攻破。而在此之前，需要一定的缓冲时间进行签名算法和基础设施的更换，这时一个有效的预警机制就很有价值。密码协议金丝雀就是这样的一种机制，这篇文章讨论以悬赏（bounty）为基础的密码协议金丝雀两种实现方式: 有权限的签名池和基于预测市场的不设限签名池。

基本概念

我们可以通过智能合约实现抵御量子攻击的密码协议金丝雀（quantum canary）。这个智能合约的目的是探测对签名机制有威胁的量子攻击，从而对区块链协议签名机制的安全性进行预警。具体来说，合约的所有者会不定期地更新一个“消息”。任何人都可以索要这个消息参与挑战，并伪造签名试图通过测试。如果挑战者的测试通过，则合约发放一定数量的代币给他/她，并且标记其使用的签名机制的安全性为 false。

这是一些合约的基本变量，由合约所有者（owner）设定。最后一个变量会在挑战成功的时候变成 false。

address private immutable owner;
bytes32 messageHash;
uint8 bounty = 1;
bool safety = true;

这些函数只能由 owner 触发，在于设置合约的基本变量。

constructor() {
    owner = msg.sender; 
}

function setMessage(string memory _message) public {
    require(msg.sender == owner, "You are not the owner.");
    messageHash = getMessageHash(_message);
}

function setBounty(uint8 _bounty) public {
    require(msg.sender == owner, "You are not the owner.");
    bounty = _bounty;
}

这些是可以由外部的挑战者（prover）触发的函数。挑战者可以得到 hash 之后的消息，并且连同消息返还一个伪造的签名。如果能够通过测试，则挑战者获得一定数量的 token 作为奖励。

function request() public view returns (bytes32) {
    return messageHash;
}

function claim(address payable _prover, bytes memory _signature) public {
    require(recover(messageHash, _signature) == owner, "Verification failed.");
    safety = false;
    _prover.transfer(bounty);
}

实际运用设计

在实际运用中，以上这样一个由 owner 设定、由 owner 奖赏的合约不具备激励设立挑战的性质，也不能避免 owner 作为 bounty 的信息知情者来反复挑战这个合约。我们由此提出以下两种实际可以投入使用的 quantum canary 的经济学模型。

不设限的签名池

广义上说，任何由 quantum canary 守护的签名机制的使用者都从中受益。例如，目前使用的 keccak256 算法如果受到一定程度的量子威胁，那么任何人都可以通过 quantum canary 得到预警，有一定的时间来修改（甚至自动修改）算法。所以，我们可以设定一个签名池，让任何人都可以上传自己签名后的 message。为了鼓励更多的人上传签名，我们可以承诺，在 quantum canary 检测到可信的量子攻击时，会对所有上传签名的地址发去信号，从而第一时间防御量子攻击带来的灾害。为了避免投机的上传签名者反复试探 quantum canary 来获得自己上传的签名，从而领走 bounty，我们可以设定，上传签名的费用等于破解一个密码所获得的 bounty（甚至略大于，如果考虑到发送信号的 gas fee 的话）；另一方面，quantum canary 的安全性变量也只会在超过一定比例的签名都被破解之后才变为 false。

从另一个角度考虑，为了使上传签名者的私钥得到保护，我们也会建议上传的签名可以使用与 msg.sender 不同的私钥签名，也就是说，当我想要参与 quantum canary 的签名池建设的时候，我不需要用自己的真实私钥签名。

这种经济学模型的好处是能够使每个人都参与到 quantum canary 的建设中，然而坏处也非常明显，那就是签名的质量无法得到保证；签名池可能被恶意污染，签名的有效性（即是否使用了 quantum canary 对应的签名机制）也得不到保证。为了促使更多的人参与，上传签名的费用必须要低，然而这也降低了污染的成本。

有权限的签名池

为了保证签名的质量，也防止签名的上传者不停地挑战，我们可以寻求链上有影响力的人物来上传签名，并且设置奖金。这将对签名的质量形成一定的保证，然而也大大降低了参与程度。我们认为，这种有权限的签名池不符合去中心化的思想，因此不利于 quantum canary 的推广。

预测市场

为了能让更多的人参与到 quantum canary 项目中来，我们把 quantum canary 设置成关于挑战是否能在规定时间内被打破的预测市场。我们可以设置多轮挑战，用通过增加私钥长度的方法使难度依次增加。在最早期的挑战中，挑战难度低，我们可以估算暴力分解所需的时间，然后规定在这个时间的一半内破解掉大部分签名的才能算挑战成功。往后，暴力分解的时间对于量子计算机破解时间没有了参考性，我们则通过量子计算和私钥长度的关系推算量子计算机需要的时间。

这个过程类似于足球竞猜，不同的是，最后赢球的人也可以分走奖金池中的一部分。

  1. 下注阶段：双方可以下注。下注的金额固定。认为挑战不可能成功的下注还需要包含一个正确长度的私钥生成的公钥，以及一个自定义消息。
  2. 竞赛阶段：当双方人数都达到标准，quantum canary 开启，任何人都可以下载一个包含了若干“公钥–信息”的样本，并且上传他们破解后的“公钥–签名后的信息”。如果这若干个样本的大部分都被破解了，则视为挑战成功。
  3. 结算阶段：如果规定时间内没有出现成功的挑战者，则视为挑战失败。下注了挑战失败的人可以分走奖金池里的所有奖金。反之，第一个成功的挑战者领走悬赏，而下注了挑战成功的人可以分走奖金池里剩下的奖金。

定量分析

Bounty 的设置

设定一个对挑战者具有吸引力的 bounty 是非常重要的。我们认为，对于有现实意义的 128-bit 的私钥来说，bounty 需要提供合理的奖励。例如在以太坊网络中，1000 个代币或许是一个合理的 bounty。假设破解签名的难度和私钥的长度成多项式增长关系，可以设定以下的对照表。

参与成本设置

由于我们需要大量的签名来得到一个统计学上有意义的结论，我们需要大量的参与者。假设每次双方都要有 1000 名参与者才能开始竞赛阶段，那么每个参与者的成本应当是 bounty 的 0.15%：押注挑战成功的人的回报率为 1:2；而押注挑战不能成功的人略低，为 3:4；这是因为如果挑战成功，那么第一个挑战成功的人会领走一部分奖金（bounty 的 100%）。

作为挑战者，参与挑战也需要一定的成本，这个成本非常低廉，但不能为零：这是为了避免一些人故意反复下载挑战样本，直到得到的“公钥–信息”样本大部分是自己上传的。由下一节的有效威胁假设可以推断，下载样本的成本至少要控制在 bounty 的 0.01%。

有效威胁假设

我们必须要考虑一种情况，那就是挑战者其实根本没有破解签名的能力，只是“非常幸运”。假设一个挑战者在没有 quantum computing 的情况下破解一个签名的概率为 ，那么他在每 个签名里破解大于 个签名的概率为：

其中， 是正则贝塔函数。假设我们有 10 个签名 ，以下列表说明了“猜中足够多签名从而领取 bounty 的概率”：

以上列表的最后一行看起来非常不可能：猜中一个 1024 位（或者 512 位，for that reason）的数几乎是难以达成的幸运程度。然而我们应该从另一方面来考虑：量子技术可能是不稳定或者不完美的，所以即使一个量子计算机只有六成或者八成的把握可以破解签名，我们也将这样的技术看成有效的威胁。个人认为，当一个破解技术达到 60% 的正确率的时候，我们就可以认为 quantum canary 受到了量子威胁。

挑战周期

在预测市场一节的讨论中，我们认为，对于最初期的挑战，挑战周期应当视为暴力分解所需时间的一半。我们估算，对于 32-bit，或者 8 个 16 进制的私钥，这个挑战周期可以设定为 3 小时。之后的挑战周期，仍然遵循 bounty 的设置一节中的多项式增长规律，由此可以得出以下的对照表。

结论

以破解签名为基本原理设计的抵御量子攻击的 quantum canary 可以看作是一种有效检测量子威胁的方法。为了提高 quantum canary 的参与性，我们提出了以预测挑战是否能够在规定时间内成功为目标的有奖竞猜。参与竞猜和参与挑战的成本都需要通过定性的概率分析来确定，以保证整个竞猜的公平性。最后，在时间和 bounty 的设置方面，我们使用了多项式增长的假设，来预测量子计算机破解签名对应的价值和所需的时间。

我们必须要强调的一点是，虽然整个项目的命名和 quantum 高度相关，但我们并没有办法确定签名的破解是否使用了量子计算机。这个 quantum canary 无法回答“我们是否来到了一个受量子威胁的时代”，更多是回答了“是否有类似量子计算机那样计算能力的技术出现”。我们认为，后面这个问题更有意义，也更值得关注。

更多阅读