There is great uncertainty about when “Q-day” arrives for blockchains— when a cryptographically relevant quantum computer (CRQC for short) will exist that can recover private keys that control major digital assets, such as bitcoin and ethereum. Reflecting that uncertainty, there is a wide range of opinions on the urgency of post-quantum transition. Some voices are already sounding the alarm, while others dismiss such talk as crying wolf and urge a cautious, incremental upgrade path. Meanwhile a proposal from BitMEX research tries to make the concept of Q-day more concrete, by attempting to create a challenge on-chain such that when the challenge is successfully cracked, it becomes indisputable proof of a quantum computer in existence. This blog post will take a look at the options for constructing such “quantum canaries” and outline why smart-contract capable chain such as Ethereum can host even more powerful constructs, without requiring any changes to the underlying blockchain.

Recap: proof-of-quantum

The idea behind a quantum challenge is exactly same as the one around creating unusable public keys covered in a previous post: we invert the usual order of operations for key generation. Instead of generating an ECDSA private key first and deriving the public-key from the private scalar, we start by picking a public-key as the output of some hash function or other pseudo-random process operating on a natural input such as digits of pi or an English sentence. In the literature these are known as “NUMS” schemes, for nothing-up-my-sleeve: anyone else can verify those bytes were generated as part of a deterministic process without sneaking in arbitrary choice of parameters that could influence the result. Assuming the resulting public key is valid— in the sense of being a valid curve point, and there is roughly 50% chance of that for any random starting point— there is good reason to believe the private key was not known in advance. Recovering that unknown private key from the public key we picked is computationally intractable for classical computers. This is why we treat such keys as “unusable:” no one can sign with them, even the person who generated the corresponding public key. If a lock is designed to only open for those in possession of the private key, we can assert that door will never open.

Quantum computers invalidate that core assumption: they can efficiently solve the discrete logarithm problem and recover the private key. This provides a straightforward way to prove the existence of a quantum attack: pose a suitable challenge and wait for a solution.¹

Quantum challenges on blockchains

On paper a blockchain would be a great platform for posing such a challenge: anyone can participate and if the challenge is structured appropriately, the winner does not have to worry about whether they will get paid. Contrast this with competitions run by a centralized entity with private submissions: whether the reward is given is very much at the discretion of that organization.

In fact, many observers have wryly pointed out that all blockchains operate a massive, unofficial bug-bounty with all attacks considered fair-game, including quantum computing. If one can recover private keys— or at a lower bar, trick the legitimate owner into signing with those keys— they can “collect a bounty” or in more colloquial terms, commit theft.

Unfortunately when any attack is fair-game, it becomes difficult to distinguish a ground-breaking quantum computer advance from garden-variety security breach or disgruntled insider. This is where the NUMS approach comes into pay: if one can prove no one could have known the private key to begin with, it could only have been a quantum attack.

There are some subtleties around realizing this purely on-chain. The first problem is that blockchain addresses are not same aspublic-keys. Addresses are typically commitments to public-keys that are derived from the key. For example a Bitcoin address is obtained from the ECDSA public-key by applying two hash functions in a sequence. This process is one-way: it is not possible to infer the public-key from the address. The original public key is not revealed until withdrawing from that address. That means merely depositing the bounty bitcoin at some address is not enough; one must also disclose the public-key.

That could be done either by:

1. Out-of-band, for example in a blog post announcing the challenge
2. On chain, by withdrawing a symbolic fraction of the bounty while leaving the majority of the funds at the same address.

The second solution is appealing in that it operates entirely on-chain without relying on additional communication channels. That also means it can be used to create tripwires: quantum-canaries that are not publicized ahead of time, and therefore unknown to attackers. A rational attacker armed with a quantum computer may deliberately want to stay under the radar, and avoid attacking known bounty addresses. But if some collection of coins looks like any other address on chain, there is a real possibility they will accidentally target that address and unwittingly herald the arrival of Q-day.

Unfortunately this design also runs into a circularity: if the private key is not known to the organizer of the challenge, they can not execute an ordinary withdrawal to deliberately leak the public-key either. One might suspect multisig could solve that problem. For example, one could create a 1-of-2 multisig address, with one known and one provably unknown key. Then a withdrawal using the known key ends up revealing both public keys. But this also poses a problem for the canary: since both keys are exposed, the attacker also gets their choice of targets. In fact a rational attacker would always choose to break the private key that was already used on-chain instead of the canary, since that pattern blends in with existing attack patterns. At that point we are back to the original problem: was it a garden variety compromise of the known private-key or was it a quantum attack?

Taproot addresses as ideal tripwires

This is where the new Taproot addresses come in, solving both problems at once. Unusual among blockchain address formats, Taproot addresses are public keys. They are also commitments to alternative spending paths, defined by ordinary Bitcoin script and efficiently compacted into a compact Merkle tree. Funds can be spent either by doing a Schnorr signature with the public-key defined in the address or by disclosing the internal structure of the address, including the specific node in the Merkle tree selected for a particular transaction.

This structure allows for an optimal bug-bounty structure:

• Merely depositing funds into a taproot address creates a target for a quantum computer. No withdrawals or publishing additional data offline requierd.
• That address looks no different than any other taproot address. In other words, the setup can also function as a tripwire if one does not publicize it in advance. (You can still prove after the fact that it was generated in a NUMS fashion.)
• If no one trips the alarm after a given period of time, it is possible to reclaim the funds. This solves for another problem with the deposit-and-publish approach: if the private key is truly unknown, those funding the reward program will never be able to get their funds back, even if the reward is never claimed and the early-warning system is no longer necessary.

Canaries and tripwires with smart-contracts

Not surprisingly, it is possible to construct much better canaries on layer-ones with smart-contract capabilities. Turing completeness overcomes two limitations of the Bitcoin canary approach:

1. Each canary requires recovering a specific private key. Consider a benevolent quantum capable intelligence agency that wants to tip off the world or for that matter a Snowden-type insider who wants to signal that capability exists. In order to announce the discovery using the Bitcoin blockchain, they would have to break that specific private key. But what if they had already solved other NUMS-style challenges internally as part of demonstrating that capability? Those demonstrations can not be used to meet the canary requirement. (Of course they can be leaked through other traditional channels whistle-blowers have historically relied on.)
2. Finding out about Q-day is one thing, taking action is another. While a tripwire getting hit would be front-page news, it leaves everyone scrambling to decide on how to protect their funds. This is why the BitMEX proposal is coupled to a soft-fork that freezes certain funds if the canary is ever triggered.

Purpose built contracts for quantum-canaries

Smart-contract capable blockchains can improve on both of these aspects. This sketch will use Ethereum for concreteness but the same ideas translate equally well to layer-two rollups or Solana.

First a smart-contract can be written to accept a much more generalized type of CRQC proof. Instead of requiring that the prover solve any specific challenge, they can be broaden criteria to accept a much wider selection of NUMS-type schemes. This ideas has been explored in previous work, such as Brace for impact: ECDLP challenges for quantum cryptanalysis. Adopting it to the Ethereum setting involves creating a smart-contract to validate more generalized proofs:

• Prover supplies a seed W, scalar Y, message M and signature S
• A cryptographic hash function such as SHA256 is applied to the seed to generate 32 bytes that are interpreted as the X-coordinate of a public key point.
• This is combined with the supplied Y value to get an alleged² curve point <X, Y>
• The public-point is hashed with Ethereum’s own variant of pre-standard SHA3 (“Keccak”) to generate the corresponding 20 byte address A.
• The built-in ecrecover() primitive is used to recover the expected address E, which corresponds to a public key that would have generated a valid signature S on M
• Check if A ≟ E
• If equality holds, send all funds held by this contract—the reward for disclosing the existence of a quantum computer— to the prover.

Effectively this logic checks that the prover was able to sign some message using a private-key corresponding to a public-key that was generated deterministically from a hash function. Note how much freedom the prover has: they can sign any message. It does not have to be a Bitcoin or Ethereum transaction. (But if a BitMEX-type canary did trigger on Bitcoin, the exact same signed message could be replayed on Ethereum and accepted as proof that Q-day arrived.)

Second, other contracts can be written to depend on this canary. For example, before performing an important operation such as releasing funds, an institutional wallet can check on the canary status to ensure that ECDSA signatures are still reliable. (Recall that Ethereum contracts can call other contracts to retrieve information as part of their execution flow. Retrieving a yes/no answer from another contract would be a relatively “cheap” operation in gas terms.) Every other application is free to use this information as they see fit: for example, a contract could fall-back to an “emergency mode” where it will only accept signatures from a set of backup-keys that have never been used on chain before.

Alternatively one could implement a contract with two authorization paths:

1. Standard ECDSA-based signing. Efficient because ECDSA signature verification is a native operation for Ethereum.
2. Quantum-safe hash based signatures. These would be more costly and possibly have limitations such as a limit on how many messages can be signed.

As long as the canary has not been tripped, the first path is executed. But once the canary signals Q-day, only the second type of authorization is accepted.

Paradoxically, the same power that makes it possible to create such generalized canaries makes it much harder to create tripwires. Recall that a tripwire must be stealthy and look like any other vulnerable blockchain address. A smart-contract carefully crafted to serve as early-warning system to be invoked by other contracts clearly does not fit the bill. Using a plain “externally owned” address controlled by a single ECDSA key runs into the same problem as bitcoin: it is not possible to deliberately leak the public-key without doing a withdrawal, and by definition withdrawal is impossible without the unknown private key. (Ethereum does not have an alternative address format comparable to Taproot that directly reveals public keys.)

Designing for incentives

Dealing with front-running on Ethereum

Building a bug-bounty is one thing. Whether it will work to incentivize disclosure is a different problem. Same goes for tripwires: they are only effective if the attacker is likely to stumble into one early on in their rampage through the blockchain, otherwise the warning comes too late. Before exploring this complex topic of game-theoretical incentives for the hypothetical attacker, we need to address one flaw in the design sketched above.

Let’s posit that the actors deliberately signaling the canary are financially motivated. (Note this does not apply to an attacker unwittingly hitting the tripwire.) They want to collect the associated financial reward. By design the bitcoin held in the Taproot canary is only claimable by the entity who wields the private key corresponding to that address and can sign a specific message. More importantly, that signed message is a bitcoin transaction and unambiguously specifies where the rewards are to be sent: those are the outputs of the transaction. That is not the case on Ethereum: any signed message for a suitably constructed key works and that message need not have any particular structure.

That leads to a problem: since transactions sit in mempool before they are confirmed, there is a window of vulnerability where anyone can observe the proof before it has been officially recorded. They can then construct another transaction with higher gas to tempt the block builders into prioritizing it ahead of the original. If this second transaction executes first, the reward for proving a quantum attack goes to the copycat reporter, not the original person who deserves credit.

There are two complementary ways of dealing with this, depending on the expected disclosure mode:

1. If the entity triggering the canary has access to the full private key, they have full control over what message is getting signed. The protocol sketched above assumed no particular structure in that message, which is useful for accepting the widest spectrum of evidence as proof-of-quantum. While keeping that property we can add an additional check: if the message consists of exactly two blockchain addresses, one being the address of the canary contract, interpret the second address as the destination where rewards will be sent. These transactions can still be front-run but now doing so has no effect: the address where rewards are sent is hard-wired in the signed message. Racing to broadcast the same evidence from a different address only delivers the bug-bounty faster to the deserving recipient.
2. That still leaves open the question of how to safely submit evidence in cases where the person does not control the private-key. For example, a conscientious employee working for an organization that achieved a surreptitious CRQC breakthrough. In this case, they may only have access to a handful of signed message examples, but not the ability to use the CRQC for a selected public-key of their choice. To prevent front-running in that scenario, the contract logic must be modified. Instead of disclosing the evidence outright, there is a two step commit-and-reveal protocol:

• First the reporter commits to the triple <message, signature, rewards address> by sending its hash to the contract. This alone does not trigger the canary since anyone can make up commitments. The canary contract still makes a note of all such commitments, along with the time when they were first made.
• Only after that first transaction has executed and the contract recorded the commitment, the reporter follows up by disclosing the full evidence. The contract checks the evidence as before and also confirms there is a prior commitment serving as a promise to deliver the evidence. There is also a deadline imposed, to make sure commitments are opened within say 24 hours.
• The canary is immediately triggered to indicate proof of a quantum attack. However the rewards payout will have to wait until a few checks are cleared.
• In the best case scenario, there are no earlier unopened, unexpired commitments. In that case the bounty can be paid out immediately.
• Otherwise the priority of the disclosure is being contested. A countdown begins to select among multiple submissions, with the current reporter becoming the leading contender for the reward.
• If any earlier commitment is successfully opened by providing valid evidence consistent with that commitment, it becomes the new leading contender.
• At the end of the 24 hour period, the winning submission can make a final call to the contract to collect the reward.

Note it is still possible to front-run all transactions from the original prover and resubmit them with identical payloads, with higher gas to ensure they are processed ahead of the legitimate submission. But since an adversary has no way to open binding commitments to reveal a different payout address, all they accomplish is accelerating the reward payout to the rightful owner.

Questioning incentives

Underlying all this discussion is an implicit premise: that establishing a high-enough monetary reward is enough to incentivize disclosure on-chain. We now turn our attention to sanity-checking that.

The original BitMEX proposal hinges on a core assumption: a benevolent organization with a CRQC will choose to deliberately reveal that capability on-chain by solving one very specific challenge and reaping the modest associated rewards. This is at best a dubious assumption. If they are financially motivated, there is no need for an artificial bug-bounty. There are exposed public-keys controlling BTC collectively worth billions of dollars that are vulnerable to recovery by a CRQC. As long as compute time on CRQC remains precious, incentives favor chasing after the maximum gain possible with the targeted private key. For example the third-highest balance bitcoin address today has an exposed public-key and a balance north of 140,000₿, a figure that dwarfs any reasonable bounty. An unscrupulous actor can help themselves to a fraction of that amount while retaining plausible deniability that it was an ordinary security breach or human error.

At best a monetary reward can incentivize disclosure by a legitimate organization such as one of the pioneering quantum-computing companies who are already committed to operating within the bounds of the law. But even in that case, why should that company have to jump through the hoops of solving one particular challenge on one particular blockchain? Why not put out a press release with a solution to one of the many previous quantum-computing challenges published in the literature?

By contrast, a quantum-tripwire is useful precisely because it does not depend on good faith actions by the CRQC owner. One would expect an actor unconstrained by legal or ethical rules to chase moderately concentrated holdings of bitcoin first: not too large to panic the market with a major theft—even if there is plausible deniability on root cause— and not too small to waste precious CRQC time on economically unprofitable targets. If the tripwire address falls into that sweet-spot, an attacker could accidentally end up revealing their capabilities. On the other hand, it is also easy for threat actors to avoid that fate: while Taproot transactions account for 15-20% of activity today, they only account for ~1% of stored value. So an attacker can avoid hitting a tripwire by simply steering clear of all Taproot addresses, without meaningfully reducing their expected gain.

The more generalized quantum-canary for Ethereum opens up new incentives, by exploiting the schism between the organization wielding the CRQC and individuals associated with that work. An organization may have no official policy around wanting to protect the bitcoin community by warning of impending capabilities. But there may well exist conscientious whistle-blowers within that organization with access to CRQC development, who choose to take matters into their own hands by disclosing a cryptographically verifiable proof on-chain. These individuals need not even harbor a profit motive. Since the protocol is flexible enough to specify that the bug-bounty is burned (by using the 0 address for rewards destination) it is compatible with disclosure motivated by ideological reasons. On the flip-side of the coin, there is a clear lesson for CRQC operators hoping to remain under the radar: avoid solving any NUMS challenges, even for internal testing purposes. This is rational guidance anyway. By definition a NUMS challenge is an artificial target: no one relied on that key to encrypt highly sensitive traffic or authenticate critical actions. Therefore recovering the corresponding private key will not result in learning useful intelligence from intercepted traffic or impersonating some high-value target to gain access to some system. Given that CRQC time is going to remain extremely valuable, wasting cycles on such a demonstration is unwise even without the added risk of creating undeniable proof that can be leaked.

CP

1 Assuming that discrete logarithm problem is indeed as intractable as believed— it is worth nothing that there is no mathematical lower-bound established on its complexity.

2 Note “alleged” part because there is no guarantee this point is actually on the curve. This turns out not to matter for the correctness of the protocol, because the address generated from such an off-curve point can not be equal to one returned by ecrecover.