DAORayaki｜抗量子攻击的密码协议金丝雀

DAOrayaki DAO 研究奖金池：

资金地址：DAOrayaki.eth

研究类型：量子计算

贡献者：Siyu Chen@DAORayaki

本文感谢 Felix Cai、Eric Zhang 对 Canary 设计中的问题的反馈。

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

基本概念

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

这些是一些合约的基本变量，由合约所有者设置。 当挑战成功时，最后一个变量将变为假。

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

这些功能只能由所有者触发，这是设置合约的基本变量。

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;
}

这些是可以由外部挑战者（证明者）触发的功能。 挑战者可以得到哈希后的消息，并随消息一起返回一个伪造的签名。 如果能够通过测试，挑战者将获得一定数量的代币作为奖励。

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);
}

实际应用设计

在实践中，上述由所有者设定并由所有者奖励的合约不具有设置挑战的激励性质，也不能阻止所有者作为赏金信息提供者反复挑战合约。 因此，我们提出以下两种可以投入实际应用的量子金丝雀经济模型。

无限签名池

从广义上讲，任何使用量子金丝雀保护的签名机制的用户都可以从中受益。 例如，如果目前使用的keccak256算法受到一定程度的量子威胁，那么任何人都可以通过量子金丝雀获得预警，并有一定的时间修改（甚至自动修改）算法。 因此，我们可以建立一个签名池，让任何人都可以上传自己签名的消息。 为了鼓励更多人上传签名，我们可以承诺，当量子金丝雀检测到可信的量子攻击时，它会向所有上传签名的地址发送信号，从而在第一时间防止量子攻击造成的灾难。 为了防止投机上传者反复测试量子金丝雀获取自己上传的签名并索取赏金，我们可以设置上传签名的成本等于破解密码获得的赏金（甚至略大，如果考虑发送信号燃料费）； 另一方面，只有超过一定比例的签名被破解后，量子金丝雀的安全变量才会变为假。

从另一个角度来说，为了保护上传签名者的私钥，我们也会建议上传的签名可以使用与msg.sender不同的私钥进行签名，即当我要参与时量子金丝雀的签名池在构建的时候，不需要用自己真实的私钥签名。

这种经济模型的优点是每个人都可以参与到量子金丝雀的建设中，但是缺点也很明显，就是无法保证签名的质量； 签名池可能被恶意污染，无法保证签名的有效性（即是否使用了量子金丝雀对应的签名机制）。 要让更多的人参与进来，上传签名的成本一定要低，但这也减少了污染的成本。

授权签名池

为了保证签名的质量，防止签名的上传者不断挑战，我们可以寻求链上有影响力的人上传签名并设置奖金。 这将对签名的质量产生一些保证，但它也大大降低了参与度。 我们认为这种授权签名池不符合去中心化的思想，不利于量子金丝雀的推广。

预测市场

为了让更多的人参与到量子金丝雀项目中破解以太坊私钥方法，我们将量子金丝雀设置为在规定时间内能否突破挑战的预测市场。 我们可以设置多轮挑战，通过增加私钥长度依次增加难度。 在最早的挑战中，挑战的难度较低，我们可以预估一下暴力分解所需的时间，然后规定在这个时间的一半内破解大部分的签名算挑战成功。 以后暴力破解的时间对量子计算机的破解时间没有任何参考意义。 我们将根据量子计算与私钥长度的关系来计算量子计算机所需的时间。

这个过程类似于猜球，不同的是最后获胜的人也可以瓜分一部分奖池。

下注阶段：双方均可下注。 投注金额是固定的。 挑战不可能成功的赌注还需要包括从正确长度的私钥生成的公钥和自定义消息。

比赛阶段：当双方数量达标后，量子金丝雀开启，任何人都可以下载包含多个“公钥信息”的样本，并上传自己破解的“公钥签名信息”。 如果这几个样本中的大部分都被破解，则认为挑战成功。

结算阶段：若在规定时间内没有挑战者成功，则视为挑战失败。 投注挑战失败者，可瓜分奖金池中的所有奖金。 反之，第一个挑战成功的人拿走奖励，下注挑战成功的人可以瓜分奖金池中剩余的奖金。

定量分析

赏金设置

设置一个对挑战者有吸引力的赏金是非常重要的。 我们认为赏金需要为有意义的 128 位私钥提供合理的奖励。 例如，在以太坊网络中，1000 个代币可能是一个合理的赏金。 假设破解签名的难度与私钥长度呈多项式增长关系，则可以设置如下对照表。

参与成本设定

由于我们需要大量的签名才能得出具有统计意义的结论，因此我们需要大量的参与者。 假设双方每次有1000名参与者开始比赛阶段，则每位参与者的成本应为赏金的0.15%：投注挑战成功者的回报率为1:2； 挑战失败者投注比3:4略低； 这是因为如果挑战成功，第一个挑战成功的人将获得部分奖金（100%的赏金）。

作为挑战者，参与挑战也是需要一定的成本的。 这个成本很低，但不能为零：这是为了防止一些人故意反复下载挑战样本破解以太坊私钥方法，直到大部分获得的“公钥信息”样本自己上传。 . 从下一节的有效威胁假设可以推断，下载样本的成本至少应该控制在赏金的0.01%。

有效威胁假说

我们要考虑一种情况，就是挑战者根本不具备破解签名的能力，只是“非常幸运”而已。 假设挑战者在没有量子计算的情况下破解一个签名的概率为p，那么他在每n个签名中破解k个以上签名的概率为：

在，

是常规 beta 函数。假设我们有 10 个签名

以下列表说明了“猜测足够多的签名以领取赏金的概率”：

上面列表的最后一行看起来不太可能：猜测 1024 位（或 512 位，因此）数字几乎是一种无法达到的运气水平。 然而，我们应该换个角度来看：量子技术可能不稳定或不完善，所以即使量子计算机只有 60% 或 80% 的把握可以破解签名，我们也会认为这种技术是有效的威胁。 我个人认为，当一种破解技术达到60%的正确率时，我们就可以认为量子金丝雀受到了量子的威胁。

挑战周期

在预测市场部分的讨论中，我们认为，对于初始挑战，挑战期应视为暴力分解所需时间的一半。 我们估计对于 32 位或 8 个十六进制私钥，挑战时间可以设置为 3 小时。 接下来的挑战周期依然遵循赏金设置部分的多项式增长规律，由此可以得出如下对照表。

综上所述

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

必须强调的是，虽然整个项目的命名与量子高度相关，但我们无法确定是否使用量子计算机来破解签名。 这只量子金丝雀不能回答“我们是否已经来到一个受到量子威胁的时代”，更多的是“是否存在一种计算能力类似于量子计算机的技术”。 我们认为后一个问题更有意义，更值得关注。